数据结构课程设计

1、数据结构课程设计报告的主要内容：一、 设计题目 二、 运行环境（软、硬件环境） 三、 算法设计的思想 四、 算法的流程图 五、 算法设计分析 六、 源代码 七、 运行结果分析 八、 收获及体会 一、 设计题目：排序算法比较 设计目的： 1掌握各种排序的基本思想。 2掌握各种排序方法的算法实现。 3掌握各种排序方法的优劣分析及花费的时间的计算。 4掌握各种排序方法所适应的不同场合。 设计内容和要求： 利用随机函数产生3000个随机整数，利用插入排序、起泡排序、选择排序、快速排序、堆排序、归并排序等排序方法进行排序，并统计每一种排序上机所花费的时间。 二、 运行环境（软、硬件环境） 这次使用的编译

2、软件是C-FREE5，该软件感觉比VC+6.0和TC要好使用一些，查找错误时非常方便，调试也非常方便。硬件是计算机。 三、 算法设计的思想：首先设置主菜单，菜单主要有7个功能，分别是6种排序算法以及退出系统的功能。每输入相应的数字就对应一种功能，主程序会根据所选的功能命令来执行相应的操作。以下主要讲一下6种排序算法的思想。插入排序：先将第一个数看作是一个有序序列，然后从第二个记录开始，依次将未排序的记录插入到这个有序的序列中去，直到整个文件中的全部记录排序完毕。在排序的过程中，前面的记录序列是已经排好序的，而后面的记录序列有待排序处理。冒泡排序：假设待排序的文件为（R1，R2，Rn），对应的关

3、键字为（K1，K2，Kn）。从K1开始，依次比较两个相邻的关键字Ki和Ki+1(i=1,2,3,n-1).若Ki Ki+1,则交换Ri和Ri+1的位置；否则，不交换。经过一遍处理之后，其中关键字最大的记录移到了第N个位置上，然后再对前面的N-1个记录进行第二遍排序，重复上叙过程。继续进行下去，直到不需要交换记录为止。选择排序：n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果：初始状态：无序区为R1.n，有序区为空。第1趟排序在无序区R1.n中选出关键字最小的记录Rk，将它与无序区的第1个记录R1交换，使R1.1和R2.n分别变为记录个数增加1个的新有序区和记录个数减少1个的新

4、无序区。第i趟排序第i趟排序开始时，当前有序区和无序区分别为R1.i-1和Ri.n(1in-1)。该趟排序从当前无序区中选出关键字最小的记录Rk，将它与无序区的第1个记录Ri交换，使R1.i和Ri+1.n分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。这样，n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。快速排序： 附设两个指针LOW和HIGH，它们的初值分别是LOW和HIGH，设枢轴记录的关键字的记录为KEY，然后首先从HIGH所指的位置起向前搜索到第一个关键小于KEY的记录和枢轴记录互相交换，从LOW所指的位置起向后搜索，找到第一个关键字大于KEY的记录

5、和枢轴记录互相交换，重复这两步的操作直到LOW=HIGH为止。归并排序：假设初始的序列含有N个记录，则这些记录可以看成是N个有序序列的子序列，每个子序列的长度为1，然后两两归并，得到N/2个长度为2或1的有序序列，再两两归并如此重复，直到得到一个长度为N的有序序列为止。堆排序：将待排序的记录按照堆的定义建初堆，并输出堆顶元素，然后调整剩余的记录序列，利用筛选法进行N-1次筛选。新筛选成的堆会越来越小，而新的堆后面有序关键字会越来越多，最后使得待排序的记录成为一个有序的序列。四、 算法的流程图 主程序输入数字退 出 系 统堆 排 序归 并 排 序快 速 排 序选 择 排 序冒 泡 排 序插 入

6、排 序插入排序 结束五、 算法设计分析 几种排序方法的性能比较：排序方法 平均时间复杂度 最坏时间复杂度 辅助存储空间插入排序 O（n*n） O(n*n) O(1)快速排序 O(n log2 n) O(n*n) O(log h)堆排序 O(n log2 n) O(n log2n) O(1)归并排序 O(n log2 n) O(n log2 n) O(n)选择排序：1）关键字比较次数无论文件初始状态如何，在第i趟排序中选出最小关键字的记录，需做n-i次比较，因此，总的比较次数为：n(n-1)/2=0(n2)（2）记录的移动次数 当初始文件为正序时，移动次数为0,文件初态为反序时，每趟排序均要执行

7、交换操作，总的移动次数取最大值3(n-1)。直接选择排序的平均时间复杂度为O(n2)。冒泡排序：其算法时间复杂度是O(n2)。 其中稳定的排序有以下几种：冒泡排序，插入排序，归并排序。不稳定的排序有：选择排序，堆排序，快速排序。 六、 源代码 #include stdio.h #include time.h#include malloc.h#include stdlib.h#include#include#include int menu_select()int c;printf( 按任意键进入系统:nn);getch();printf( 欢迎来到排序系统 ！nn);printf( * 菜 单

8、*nn);printf( 0.使用插入排序n);printf( 1.使用冒泡排序n);printf( 2.使用选择排序n);printf( 3.使用快速排序n);printf( 4.使用归并排序n);printf( 5.使用堆排序n);printf(nn 6.退出n);printf( * 菜 单*nn);do printf(n 输入你想要使用的排序法的序号(06):); scanf(%d,&c);while(c6);return c; /*插入排序*/void insert(int *a,int n) int i,j,temp; for(i=1;i=0&tempaj) /*从ai-1开始找比a

9、i小的数，同时把数组元素向后移*/ aj+1=aj; j-; aj+1=temp; /*插入*/ /*冒泡排序*/void bubble(int *a,int n) /*定义两个参数：数组首地址与数组大小*/ int i,j,temp; for(i=0;in-1;i+) for(j=i+1;jaj) temp=ai; ai=aj; aj=temp; /*选择排序*/void selectsort(int *a,int n) int i,j,k,temp; for(i=0;in-1;i+) k=i; /*给记号赋值*/ for(j=i+1;jaj) k=j; /*是k总是指向最小元素*/ if(

10、i!=k) /*当k!=i是才交换，否则ai即为最小*/ temp=ai; ai=ak; ak=temp; /*快速排序*/void quick(int *a,int i,int j) int m,n,temp; int k; m=i; n=j; k=a(i+j)/2; /*选取的参照*/ do while(amk&mk&ni) n-; /* 从右到左找比k小的元素*/ if(m=n) /*若找到且满足条件，则交换*/ temp=am; am=an; an=temp; m+; n-; while(m=n); if(mi) quick(a,i,n); void merge(int a,int l

11、ow,int middle,int high)int h,i,j,k;int b3000;h=low;i=low;j=middle+1;while(h=middle&j=high)if(ahmiddle)for(k=j;k=high;k+)bi=ak;i+; elsefor(k=h;k=middle;k+) bi=ak;i+;for(k=low;k=high;k+)ak=bk;/*归并排序函数的具体实现*/void mergesort(int a,int low,int high)int middle;if(lowhigh)middle=(low+high)/2;mergesort(a,low

12、,middle);mergesort(a,middle+1,high);merge(a,low,middle,high);/*堆排序函数*/void sift(int r,int k,int m)int i,j,t,finished=0;t=rk;i=k;j=2*i;while(j=m&finished=0)if(jm&rj=rj)finished=1;elseri=rj;i=j;j=2*i;ri=t;void create_heap(int r,int length)int i,n=length;for(i=n/2;i=1;i-)sift(r,i,n);void heap_sort(int

13、r,int length)int i,t,n;create_heap(r,length);n=length;for(i=n;i=2;i-)t=ri;ri=r1;r1=t;sift(r,1,i-1);int main() /*主函数*/ srand(time(NULL); int i,a3000,n=3000;float start,end; /* 开始时间,结束时间*/ for( i=0;i3000;i+) ai=rand()%5000; /*产生5000以内的3000个随机函数*/ for(;) switch(menu_select() case 0: /*选择插入排序*/ start=(f

14、loat)clock(); insert(a,3000); printf(the sorted numbers:n); for(i=0;in;i+) printf(%8d,ai); printf(n); end=(float)clock(); printf( 插入排序时间是:%.f毫秒n,end-start); break; case 1: /*选择冒泡排序*/ start=(float)clock(); bubble(a,3000); printf(the sorted numbers:n); for(i=0;in;i+) printf(%8d,ai); printf(n); end=(fl

15、oat)clock(); printf( 冒泡排序时间是:%.f毫秒n,(end-start); break; case 2: /*选择排序*/ start=(float)clock(); selectsort(a,3000); printf(the sorted numbers:n); for(i=0;in;i+) printf(%8d,ai); printf(n); end=(float)clock(); printf( 选择排序时间是:%.f毫秒n,(end-start); break; case 3: /*快速排序*/ start=(float)clock(); quick(a,0,n

16、-1); printf(the sorted numbers:n); for(i=0;in;i+) printf(%8d,ai); printf(n); end=(float)clock(); printf( 快速排序时间是:%.f毫秒n,(end-start); break; case 4: /*归并排序*/ start=(float)clock(); mergesort(a,0,n-1); printf(the sorted numbers:n); for(i=0;in;i+) printf(%8d,ai); printf(n); end=(float)clock(); printf( 归并排序时间是:%.f毫秒n,(end-start); break; case 5: /*堆排序*/ start=(float)clock(); heap_sort(a,n); printf(the sorted numbers:n); for(i=0