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","JiLin", "TongWei","BIT","ZhengJiang","JiangSu", "SunYou","BIT","WeiFang","ShangDong", "XiaoMing","PKU","TaiYuan","ShanXi" };/*對后面要用到的函數進行聲明*/void quick_disk(FILE *fp,int count);void qs_disk(FILE *fp,int left,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,0,count-1);}/*排序函數*/void qs_disk(FILE *fp,int left,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 i,long j){ char a[sizeof(info)],b[sizeof(info)]; fseek(fp,sizeof(info)*i,SEEK_SET); /*找到i在文件中對應的數據位置*/ fread(a,sizeof(info),1,fp); /*將該位置數據讀到字符串數組a中*/ fseek(fp,sizeof(info)*j,SEEK_SET); /*找到j在文件中對應的數據位置*/ fread(b,sizeof(info),1,fp); /*將該位置數據讀到字符串數組b中*/ fseek(fp,sizeof(info)*j,SEEK_SET); /*找到j在文件中對應的數據位置*/ fwrite(a,sizeof(info),1,fp); /*將剛才讀入a中的數據寫入到該位置*/ fseek(fp,sizeof(info)*i,SEEK_SET); /*找到i在文件中對應的數據位置*/ fwrite(b,sizeof(info),1,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,long rec){ struct data *p; p = &info; rewind(fp); /*找到該結構體變量得的位置*/ fseek(fp,rec*sizeof(info),SEEK_SET); /*將其讀到指針p*/ fread(p,sizeof(info),1,fp); return p; /*返回該結構體指針*/}/*將指針p對應的結構體的各個成員變量打印出來*/void print_data(struct data *p){ printf("姓名:%s/n",p->name); printf("學校:%s/n",p->school); printf("城市:%s/n",p->city); printf("省 :%s/n",p->province);}
感謝閱讀,希望能幫助到大家,謝謝大家對本站的支持!
新聞熱點
疑難解答
圖片精選