数据结构课程设计实验报告(各种排序的实现与效率分析).doc

数据结构课程设计实验报告 实验题目各种排序的实现与效率分析自我评价功 能算法设计独立完成情况算法熟练程度测试通过成功失败独立帮助掌握了解不懂起泡排序直接排序简单选择排序快速排序希尔排序堆排序算法进行比较比较结果成绩l A-完成实验要求的全部功能并运行通过，算法有一定的新意，程序代码符合书写规范，实验报告叙述清晰完整，有详尽的分析和总结。l B-完成实验要求的全部功能，程序代码符合书写规范，实验报告叙述清晰完整。l C-完成实验要求的大部分功能，实验报告良好。l D-未按时完成实验，或者抄袭。 教师签名：1、需求分析(1)对起泡排序、直接排序、简单选择排序、快速排序、希尔排序、堆排序算法进行比较；(2)待排序表的表长不小于100，表中数据随机产生，至少用5组不同数据作比较，比较指标有：关键字参加比较次数和关键字的移动次数（关键字进行一次交换操作记为3次移动）；(3)输出比较结果。2、主要函数及数据类型函数名功能说明InitData ( )生成随机数组PrintDatat( )输出数组InsertSort ( )直接插入排序ShellInsert ( )对顺序表作一趟希尔插入排序ShellSort ( )希尔排序BubbleSort ( )起泡排序QuickSort ( )快速排序 SelectSort ( )简单选择排序 HeapSort ( )堆排序 SortCompare ( )比较各种排序方法typedef int KeyType;/定义关键字类型为整数类型typedef int InfoType;/定义关键字类型为整数类型typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */typedef int Boolean;/* Boolean是布尔类型,其值是TRUE或FALSE */typedef structKeyType key;/关键字项InfoType otherinfo;/其它数据项RedType;/记录类型typedef struct RedType rMAXSIZE+1;/r0闲置或用作哨兵单元int length;/顺序表长度SqList; /顺序表类型3、源代码/*头文件和宏定义部分*/#includestring.h#includectype.h#includetime.h#includemalloc.h /* malloc()等 */#includelimits.h /* INT_MAX等 */#includestdio.h /* EOF(=Z或F6),NULL */#includestdlib.h /* atoi() */#includeio.h /* eof() */#includemath.h /* floor(),ceil(),abs() */#includeprocess.h /* exit() */* 函数结果状态代码 */#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define MAXSIZE 100 /示例数据类型的最大长度typedef int KeyType;/定义关键字类型为整数类型typedef int InfoType;/定义关键字类型为整数类型typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */typedef structKeyType key;/关键字项InfoType otherinfo;/其它数据项RedType;/记录类型typedef struct RedType rMAXSIZE+1;/r0闲置或用作哨兵单元int length;/顺序表长度SqList;/顺序表类型void InitData(SqList *L,int dataCopy)int i;L-length=MAXSIZE;srand(unsigned)time(NULL); for(i=0;iri.otherinfo=0;dataCopyi=L-ri.key=rand();void PrintData(SqList L)int i;for(i=1;i=L.length;i+)printf(%dt,L.ri.key);void ResumeData(SqList *L,int dataCopy)int i;for(i=0;iri.key=dataCopyi;void PrintStatistic(int *compareCounts,int *moveCounts)printf(ntt各种排序方法比较结果:nn);printf(tt起泡排序: 比较次数 %d,移动次数 %dn,compareCounts0,moveCounts0);printf(tt直接插入排序:比较次数 %d,移动次数 %dn,compareCounts1,moveCounts1);printf(tt简单选择排序:比较次数 %d,移动次数 %dn,compareCounts2,moveCounts2);printf(tt快速排序: 比较次数 %d,移动次数 %dn,compareCounts3,moveCounts3);printf(tt希尔排序: 比较次数 %d,移动次数 %dn,compareCounts4,moveCounts4);printf(tt堆排序: 比较次数 %d,移动次数 %dn,compareCounts5,moveCounts5);/*直接插入排序*/void InsertSort(SqList *L,int *compareCounts,int *moveCounts )/直接插入排序int i,j;/for(i=2;ilength;i+)/从顺序表的第二个元素开始进行比较if(L-ri.keyri-1.key)/将每个元素与它的前一个元素关键字进行比较L-r0=L-ri;/如果关键字比前一个元素关键字小，就将元素复制作为哨兵L-ri=L-ri-1;(*moveCounts)+=2;/关键字移动了2次j=i-2;/从要比较的关键字的前第二个记录开始进行比较,然后后移while(L-r0.keyrj.key)L-rj+1=L-rj;/记录后移(*moveCounts)+;/每作一次后移,移动次数加1j-;(*compareCounts)+;/每作一次比较，比较次数加1L-rj+1=L-r0;/插入到正确位置(*compareCounts)+;/*希尔排序*/void ShellInsert(SqList *L,int increment,int *compareCounts,int *moveCounts)/对顺序表作一趟希尔插入排序int j,n;for(j=1+increment;jlength;j+)if(L-rj.keyrj-increment.key)/将L-i插入到有序增量子表L-r0=L-rj;/暂存在L-r0L-rj=L-rj-increment;(*moveCounts)+=2;for(n=j-2*increment;n0&L-r0.keyrn.key;n-=increment)L-rn+increment=L-rn;/记录后移，查找插入位置(*moveCounts)+;(*compareCounts)+;L-rn+increment=L-r0;/插入(*moveCounts)+;(*compareCounts)+;void ShellSort(SqList *L,int IncreList,int times,int *compareCounts,int *moveCounts)/希尔排序/按增量序列Increlist0.times-1对顺序表作希尔排序int k;/for(k=0;ktimes;k+)ShellInsert(L,IncreListk,compareCounts,moveCounts);/一趟增量为IncreListk的插入排序/*起泡排序*/void BubbleSort(SqList *L,int *compareCounts,int *moveCounts)/起泡排序int i,j;for(i=1;ilength;i+)for(j=L-length;ji;j-)/从后往前两两进行比较，将元素关键字小的交换到前面if(L-rj.keyrj-1.key)L-r0=L-rj;L-rj=L-rj-1;L-rj-1=L-r0;(*moveCounts)+=3;(*compareCounts)+;/*快速排序*/int Partition(SqList *L,int low,int high,int *compareCounts,int *moveCounts)/快速排序中的分int pivotkey;L-r0=L-rlow;(*moveCounts)+;pivotkey=L-rlow.key;while(lowhigh)while(lowrhigh.key=pivotkey)high-;(*compareCounts)+;L-rlow=L-rhigh;(*moveCounts)+;while(lowrlow.keyrhigh=L-rlow;(*moveCounts)+;(*compareCounts)+;L-rlow=L-r0;(*moveCounts)+;return low;void QSort(SqList *L,int low,int high,int *compareCounts,int *moveCounts)int pivotloc;if(lowlength,compareCounts,moveCounts);/*简单选择排序*/void SelectSort(SqList *L,int *compareCounts,int *moveCounts)int i,j,minPoint;for(i=1;ilength;i+)L-r0=L-ri;(*moveCounts)+;minPoint=i;for(j=i+1;jlength;j+)if(L-rj.keyr0.key)L-r0=L-rj;(*moveCounts)+;minPoint=j;(*compareCounts)+;L-rminPoint=L-ri;L-ri=L-r0;(*moveCounts)+;/*堆排序*/void HeapAdjust(SqList *L,int s,int m,int *compareCounts,int *moveCounts)RedType cmpKey;/待比较的值int j;cmpKey=L-rs;(*moveCounts)+;for(j=s*2;j=m;j*=2)(*compareCounts)+=2;if(jrj.keyrj+1.key) j+;if(!(cmpKey.keyrj.key) break;L-rs=L-rj;(*moveCounts)+;s=j;L-rs=cmpKey;(*moveCounts)+;void HeapSort(SqList *L,int *compareCounts,int *moveCounts)int i;RedType temp;for(i=L-length/2;i0;i-)HeapAdjust(L,i,L-length,compareCounts,moveCounts);for(i=L-length;i1;i-)temp=L-r1;L-r1=L-ri;L-ri=temp;(*moveCounts)+=3;HeapAdjust(L,1,i-1,compareCounts,moveCounts);void SortCompare()SqList L;/用顺序表存放待排序的元素int dataCopyMAXSIZE+1,i;int compareCounts7,moveCounts7;int increList6;for(i=0;i5;i+)increListi=(int)pow(2,7-i)-1;increList5=1;for(i=0;i7;i+)compareCountsi=0;moveCountsi=0;InitData(&L,dataCopy);/初始化数据，随机产生100个正整数的数列printf(ttt初始化数据后产生的数列:n);PrintData(L);/显示出未排序的数列printf(nnttt经过起泡排序后产生的数列:n);BubbleSort(&L,&compareCounts0,&moveCounts0);/对数列使用起泡排序PrintData(L);/显示出排序好的数列ResumeData(&L,dataCopy);printf(nnttt经过直接插入排序后产生的数列:n);InsertSort(&L,&compareCounts1,&moveCounts1);/对数列使用插入排序PrintData(L);/显示出排序好的数列ResumeData(&L,dataCopy);printf(nnttt经过简单选择排序后产生的数列:n);Select