快捷導(dǎo)航

C語言對磁盤文件進(jìn)行快速排序簡單實(shí)例

更新時(shí)間：2017年06月25日 11:56:10 投稿：lqh

這篇文章主要介紹了C語言對磁盤文件進(jìn)行快速排序簡單實(shí)例的相關(guān)資料,需要的朋友可以參考下

C語言對磁盤文件進(jìn)行快速排序簡單實(shí)例

快速排序（quick sort）是由C.A.R.Hoare發(fā)明并命名的，這種排序被認(rèn)為是目前最好的一種排序算法。快速排序基于交換排序，與同樣的基于交換排序的冒泡排序法相比，其效果非常明顯。

它的基本思想是：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。

本例中快速排序是通過函數(shù)quick_disk(FILE* fp,int count)中反復(fù)調(diào)用排序函數(shù)qs_disk(FILE* fp,int left,int right)實(shí)現(xiàn)快速排序。在qs_disk()中，通過函數(shù)get_name(fp,(long)(i+j)/2)返回中間值作為比較數(shù)進(jìn)行快速排序。

下面是具體的源代碼：

#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"
 
};
/*對后面要用到的函數(shù)進(jìn)行聲明*/
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("將未排序的數(shù)據(jù)寫入文件\n");
  /*將數(shù)組Sdata[NUM]寫入文件中*/
  fwrite(addrs,sizeof(addrs),1,fp);
  /*將文件中的數(shù)組Sdata[NUM]依次取出并打印*/
  for(i=0;i<NUM;i++)
  {
    struct data *p;
    p = get_data(fp,i);   /*得到Sdata[i]的指針*/
    print_data(p);     /*將結(jié)構(gòu)體Sdata[i]各個(gè)成員變量打印出*/
    printf("\n");
  }
 
  fclose(fp);         /*關(guān)閉文件指針*/
  /*以二進(jìn)制方式再次打開文件datalist.txt*/
  if((fp=fopen("datalist.txt","rb+"))==NULL)
  {
    printf("不能以讀寫方式打開文件\n");
    exit(1);
  }
 
  printf("將文件數(shù)據(jù)排序\n");
  /*調(diào)用字符串排序函數(shù)將文本中的字符串結(jié)構(gòu)體排序*/
  quick_disk(fp,NUM);     
 
  printf("排序結(jié)束\n");
  /*將排序結(jié)束后的數(shù)組數(shù)據(jù)打印出來*/
  for(i=0;i<4;i++)
  {
    struct data *p;
    p = get_data(fp,i);
    print_data(p);
    printf("\n");
  }
  fclose(fp);
 
  return 0;
}
/*應(yīng)用快速排序方法對字符串進(jìn)行排序*/
void quick_disk(FILE *fp,int count)
{
  qs_disk(fp,0,count-1);
}
/*排序函數(shù)*/
void qs_disk(FILE *fp,int left,int right)
{
  long int i,j;
  char x[30];
  i = left;
  j = right;
  /*比較字符串x為Sdata數(shù)組中間一個(gè)結(jié)構(gòu)變量的name成員變量*/
  strcpy(x,get_name(fp,(long)(i+j)/2));
  do
  {  /*比較當(dāng)前結(jié)構(gòu)變量的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對應(yīng)的數(shù)據(jù)*/
      i++;
      j--;
    }
  }while(i<j);
 
  if(left<j)          /*反復(fù)調(diào)用此排序函數(shù)，直到j(luò)達(dá)到數(shù)據(jù)的最左端*/
    qs_disk(fp,left,(int)j);
  if(i<right)         /*反復(fù)調(diào)用此排序函數(shù)，直到i達(dá)到數(shù)據(jù)的最右端*/
    qs_disk(fp,(int)i,right);
}
/*交換i和j在文件中對應(yīng)的數(shù)據(jù)*/
void exchangedata(FILE *fp,long i,long j)
{
  char a[sizeof(info)],b[sizeof(info)];
  fseek(fp,sizeof(info)*i,SEEK_SET);   /*找到i在文件中對應(yīng)的數(shù)據(jù)位置*/
  fread(a,sizeof(info),1,fp);       /*將該位置數(shù)據(jù)讀到字符串?dāng)?shù)組a中*/
 
  fseek(fp,sizeof(info)*j,SEEK_SET);   /*找到j(luò)在文件中對應(yīng)的數(shù)據(jù)位置*/
  fread(b,sizeof(info),1,fp);       /*將該位置數(shù)據(jù)讀到字符串?dāng)?shù)組b中*/
 
  fseek(fp,sizeof(info)*j,SEEK_SET);   /*找到j(luò)在文件中對應(yīng)的數(shù)據(jù)位置*/
  fwrite(a,sizeof(info),1,fp);      /*將剛才讀入a中的數(shù)據(jù)寫入到該位置*/
  fseek(fp,sizeof(info)*i,SEEK_SET);   /*找到i在文件中對應(yīng)的數(shù)據(jù)位置*/
  fwrite(b,sizeof(info),1,fp);      /*將剛才讀入b中的數(shù)據(jù)寫入到該位置*/
  /*完成文件中i和j處對應(yīng)數(shù)據(jù)的交換*/
}
/*得到文件fp中變量rec對應(yīng)的結(jié)構(gòu)體變量的name成員變量*/
char *get_name(FILE *fp,long rec)
{
  struct data *p;
  p = &info;
  rewind(fp);
  /*找到該結(jié)構(gòu)體變量得的位置*/
  fseek(fp,rec*sizeof(struct data),SEEK_SET);
  /*將其讀到指針p*/
  fread(p,sizeof(struct data),1L,fp);
  return p->name;     /*返回該結(jié)構(gòu)體變量的name成員變量*/
}
/*得到文件fp中變量rec對應(yīng)的結(jié)構(gòu)體變量的指針*/
struct data *get_data(FILE *fp,long rec)
{
  struct data *p;
  p = &info;
  rewind(fp);
  /*找到該結(jié)構(gòu)體變量得的位置*/
  fseek(fp,rec*sizeof(info),SEEK_SET);
  /*將其讀到指針p*/
  fread(p,sizeof(info),1,fp);
  return p;        /*返回該結(jié)構(gòu)體指針*/
}
/*將指針p對應(yīng)的結(jié)構(gòu)體的各個(gè)成員變量打印出來*/
void print_data(struct data *p)
{
  printf("姓名：%s\n",p->name);
  printf("學(xué)校：%s\n",p->school);
  printf("城市：%s\n",p->city);
  printf("省 ：%s\n",p->province);
}

感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！

您可能感興趣的文章: