C语言对磁盘文件进行快速排序简单实例

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);

}

感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!

以上是 C语言对磁盘文件进行快速排序简单实例 的全部内容, 来源链接: utcz.com/z/329446.html

回到顶部