C语言对磁盘文件进行快速排序简单实例
发布时间:2020-12-16 05:08:30 所属栏目:百科 来源:网络整理
导读:C语言对磁盘文件进行快速排序简单实例 快速排序(quick sort)是由C.A.R.Hoare发明并命名的,这种排序被认为是目前最好的一种排序算法。 快速排序基于交换排序,与同样的基于交换排序的冒泡排序法相比,其效果非常明显。 它的基本思想是:通过一趟排序将要排
C语言对磁盘文件进行快速排序简单实例 快速排序(quick sort)是由C.A.R.Hoare发明并命名的,这种排序被认为是目前最好的一种排序算法。快速排序基于交换排序,与同样的基于交换排序的冒泡排序法相比,其效果非常明显。 它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。 本例中快速排序是通过函数quick_disk(FILE* fp,int count)中反复调用排序函数qs_disk(FILE* fp,int left,int right)实现快速排序。在qs_disk()中,通过函数get_name(fp,(long)(i+j)/2)返回中间值作为比较数进行快速排序。 下面是具体的源代码: #include <stdio.h> #include <stdlib.h> #include <string.h> #define NUM 4 struct data { char name[20]; char school[20]; char city[20]; char province[20]; }info; struct data addrs[NUM]= { "OKBase","BIT","JiLin","TongWei","ZhengJiang","JiangSu","SunYou","WeiFang","ShangDong","XiaoMing","PKU","TaiYuan","ShanXi" }; /*对后面要用到的函数进行声明*/ void quick_disk(FILE *fp,int count); void qs_disk(FILE *fp,int right); void exchangedata(FILE *fp,long i,long j); char *get_name(FILE *fp,long rec); void print_data(struct data *p); struct data *get_data(FILE *fp,long rec); int main(void) { int i; FILE *fp; /*文件指针*/ /*以读写方式生成文本文件fp*/ if((fp = fopen("datalist.txt","w+")) == NULL) { printf("打开文件失败n"); exit(1); } printf("将未排序的数据写入文件n"); /*将数组Sdata[NUM]写入文件中*/ fwrite(addrs,sizeof(addrs),1,fp); /*将文件中的数组Sdata[NUM]依次取出并打印*/ for(i=0;i<NUM;i++) { struct data *p; p = get_data(fp,i); /*得到Sdata[i]的指针*/ print_data(p); /*将结构体Sdata[i]各个成员变量打印出*/ printf("n"); } fclose(fp); /*关闭文件指针*/ /*以二进制方式再次打开文件datalist.txt*/ if((fp=fopen("datalist.txt","rb+"))==NULL) { printf("不能以读写方式打开文件n"); exit(1); } printf("将文件数据排序n"); /*调用字符串排序函数将文本中的字符串结构体排序*/ quick_disk(fp,NUM); printf("排序结束n"); /*将排序结束后的数组数据打印出来*/ for(i=0;i<4;i++) { struct data *p; p = get_data(fp,i); print_data(p); printf("n"); } fclose(fp); return 0; } /*应用快速排序方法对字符串进行排序*/ void quick_disk(FILE *fp,int count) { qs_disk(fp,count-1); } /*排序函数*/ void qs_disk(FILE *fp,int right) { long int i,j; char x[30]; i = left; j = right; /*比较字符串x为Sdata数组中间一个结构变量的name成员变量*/ strcpy(x,get_name(fp,(long)(i+j)/2)); do { /*比较当前结构变量的name成员变量于比较字符串x的大小*/ while((strcmp(get_name(fp,i),x)<0)&&(i<right)) i++; while((strcmp(get_name(fp,j),x)>0)&&(j>left)) j--; if(i<=j) { exchangedata(fp,i,j); /*交换i和j对应的数据*/ i++; j--; } }while(i<j); if(left<j) /*反复调用此排序函数,直到j达到数据的最左端*/ qs_disk(fp,left,(int)j); if(i<right) /*反复调用此排序函数,直到i达到数据的最右端*/ qs_disk(fp,(int)i,right); } /*交换i和j在文件中对应的数据*/ void exchangedata(FILE *fp,long j) { char a[sizeof(info)],b[sizeof(info)]; fseek(fp,sizeof(info)*i,SEEK_SET); /*找到i在文件中对应的数据位置*/ fread(a,sizeof(info),fp); /*将该位置数据读到字符串数组a中*/ fseek(fp,sizeof(info)*j,SEEK_SET); /*找到j在文件中对应的数据位置*/ fread(b,fp); /*将该位置数据读到字符串数组b中*/ fseek(fp,SEEK_SET); /*找到j在文件中对应的数据位置*/ fwrite(a,fp); /*将刚才读入a中的数据写入到该位置*/ fseek(fp,SEEK_SET); /*找到i在文件中对应的数据位置*/ fwrite(b,fp); /*将刚才读入b中的数据写入到该位置*/ /*完成文件中i和j处对应数据的交换*/ } /*得到文件fp中变量rec对应的结构体变量的name成员变量*/ char *get_name(FILE *fp,long rec) { struct data *p; p = &info; rewind(fp); /*找到该结构体变量得的位置*/ fseek(fp,rec*sizeof(struct data),SEEK_SET); /*将其读到指针p*/ fread(p,sizeof(struct data),1L,fp); return p->name; /*返回该结构体变量的name成员变量*/ } /*得到文件fp中变量rec对应的结构体变量的指针*/ struct data *get_data(FILE *fp,rec*sizeof(info),fp); return p; /*返回该结构体指针*/ } /*将指针p对应的结构体的各个成员变量打印出来*/ void print_data(struct data *p) { printf("姓名:%sn",p->name); printf("学校:%sn",p->school); printf("城市:%sn",p->city); printf("省 :%sn",p->province); } 感谢阅读,希望能帮助到大家,谢谢大家对本站的支持! (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |