如何用qsort对二维字符数组存的若干字符串排序?
我写了一个程序,有点问题:
#include
#include
#include
intqsort_compare_str_asc(constvoid*a,constvoid*b);
char*s[5]={"cattle","car","banana","cabet","cap"};
chart[5][100]={"cattle","car","banana","cabet","cap"};
intmain()
{
inti;
printf("s升序排列:\n");
qsort((void*)s,5,sizeof(char*),qsort_compare_str_asc);
for(i=0;i<5;i++)
printf("%s\n",s[i]);
printf("t升序排列:\n");
qsort((void*)t,5,sizeof(char*),qsort_compare_str_asc);
for(i=0;i<5;i++)
printf("%s\n",t[i]);
return0;
}
intqsort_compare_str_asc(constvoid*a,constvoid*b)
{
returnstrcmp(*(char**)a,*(char**)b);
}
程序运行结果:
s是字符指针数组,字符串升序排序成功
t是二维字符数组,字符串升序排序直接崩溃
请教高手:像t[5][100]这样用二位字符数组存储的若干字符串如何用qsort排序成功?
------解决思路----------------------
t[i]是指针常量,不能作为左值。所以会在qsort交换数组元素位置时出错。
要qsort排序的话,可以把t的每个元素赋给一个字符指针数组,就像s。
------解决思路----------------------
引用:我可以另外设一个字符指针数组char*pt[5]={t[0],t[1],t[2],t[3],t[4]}
下面只需要用qsort对pt排序,最后pt[0]、pt[1]、……指向的字符串就是有序的。
现在带来一个问题:
如果数据量很大,比如100万个字符串,额外加400万字节的指针,会不会消耗内存很厉害?
如果我想在pt排序完之后再写段代码让t有序,会不会是多此一举?
100万个字符串,明显会内存消耗很利害,要考虑其它的方法了。比如hash.
是多此一举。
------解决思路----------------------
仅供参考//文件1中的内容排序并去重,结果保存到文件2中
#include
#include
#include
#defineMAXCHARS128//能处理的最大行宽,包括行尾的\n和字符串尾的\0
intMAXLINES=10000,MAXLINES2;
char*buf,*buf2;
intc,n,hh,i,L;
FILE*f;
charln[MAXCHARS];
intignore_case=0;
inticompare(constvoid*arg1,constvoid*arg2){
returnstricmp((char*)arg1,(char*)arg2);
}
intcompare(constvoid*arg1,constvoid*arg2){
returnstrcmp((char*)arg1,(char*)arg2);
}
intmain(intargc,char**argv){
if(argc<3){
printf("Uniqueline.Designedbyzhao4zhong1@.-08-20\n");
printf("Usage:%ssrc.txtuniqued.txt[-i]\n",argv[0]);
return1;
}
if(argc>3)ignore_case=1;//若存在命令行参数3,忽略大小写
f=fopen(argv[1],"r");
if(NULL==f){
printf("Cannotfindfile%s!\n",argv[1]);
return1;
}
buf=(char*)malloc(MAXLINES*MAXCHARS);
if(NULL==buf){
fclose(f);
printf("Cannotmalloc(%dLINES*%dCHARS)!\n",MAXLINES,MAXCHARS);
return2;
}
n=0;
hh=0;
i=0;
while(1){
if(NULL==fgets(ln,MAXCHARS,f))break;//
hh++;
L=strlen(ln)-1;
if('\n'!=ln[L]){//超长行忽略后面内容
printf("%sLine%dtoolong(>%d),spilthignored.\n",argv[1],hh,MAXCHARS);
while(1){
c=fgetc(f);
if('\n'==c
------解决思路----------------------
EOF==c)break;//
}
}
while(1){//去掉行尾的'\n'和空格
if('\n'==ln[L]
------解决思路----------------------
''==ln[L]){
ln[L]=0;
L--;
if(L<0)break;//
}elsebreak;//
}
if(L>=0){
strcpy(buf+i,ln);i+=MAXCHARS;
n++;
if(n>=MAXLINES){
MAXLINES2=MAXLINES*2;
if(MAXLINES2==1280000)MAXLINES2=2500000;
buf2=(char*)realloc(buf,MAXLINES2*MAXCHARS);
if(NULL==buf2){
printf("Cannotmalloc(%dLINES*%dCHARS)!\n",MAXLINES2,MAXCHARS);
printf("WARNING:Lines>%dignored.\n",MAXLINES);
break;//
}
buf=buf2;
MAXLINES=MAXLINES2;
}
}
}
fclose(f);
if(n>1){
if(ignore_case)qsort(buf,n,MAXCHARS,icompare);
elseqsort(buf,n,MAXCHARS,compare);
}
f=fopen(argv[2],"w");
if(NULL==f){
free(buf);
printf("Cannotcreatefile%s!\n",argv[2]);
return2;
}
fprintf(f,"%s\n",buf);
if(n>1){
if(ignore_case){
hh=0;
L=MAXCHARS;
for(i=1;i
if(stricmp((constchar*)buf+hh,(constchar*)buf+L)){
fprintf(f,"%s\n",buf+L);
}
hh=L;
L+=MAXCHARS;
}
}else{
hh=0;
L=MAXCHARS;
for(i=1;i
if(strcmp((constchar*)buf+hh,(constchar*)buf+L)){
fprintf(f,"%s\n",buf+L);
}
hh=L;
L+=MAXCHARS;
}
}
}
fclose(f);
free(buf);
return0;
}
------解决思路----------------------
如果数据量很大的话,那一般在读取的时候不会用指针常量存的。而且数据量大的时候内存都会出问题,一般采用外部排序。
------解决思路----------------------
数据量大的话可以做归并排序
将数据按10万分段做排序,结果存储到文件中,然后作多路归并就可以了