《数据结构》课程设计实验报告

1、HUBEI UNIVERSITY OF AUTOMOTIVE TECHNOLOGY数据结构课程设计报告课设题目：多种排序方式的比较专 业：计算机科学与技术班 级：姓 名：张浩然完成日期：指导教师：目录1、引言 1.1课设目的-3 1.2课设内容-3 2、需求分析 2.1任务与分析-3 2.2功能模块的划分-3 3、总体设计- 4、详细设计- 4.1冒泡排序-5 4.2快速排序-6 4.3直接插入排序-7 4.5折半插入排序-7 4.4堆排序-7 5、调试结果- 5.1冒泡排序测试-8 5.2快速排序测试-8 5.3直接插入排序测试-9 5.4折半插入排序测试-9 5.5堆排序测试-10 5.6

2、输入错误-10 6、课程设计总结-111.1课程设计目的学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及相应的算法。另一方面，通过团队合作、文档编制、主页设计等环节对学生进行全方位的训练，最终达到培养数据抽象能力和软件设计的能力。通过全部过程培养和锻炼的钻研能力、动手能力、分析问题和解决问题的实际能力。1.2课程设计内容本程序把对数列的排序转化为对数组元素的排序，用户可以根据自己的实际问题选择系统提供的几种排序方法的任意一种进行排序。包括冒泡排序，直接插入排序，折半插入排序，堆排序和快速排序。对于每一种排序算法可以输出初始序列和每一趟的排序结果。2.1

3、任务与分析任务：利用随机函数产生N个随机整数，对这些数进行多种方法进行排序。分析：本系统实现了几种常用的排序方法，包括：折半插入排序、直接插入排序、冒泡排序、快速排序（递归）、堆排序。2.2功能模块的划分2.2.1 输入模块利用随机函数产生N个随机整数，个数由用户从键盘中自己输入。2.2.2选择模块在菜单中选择相应的编号来选择采用何种排序算法，算法包括：冒泡排序、直接插入排序、折半插入、快速排序（递归）、堆排序。2.2.3输出模块输出排序前或排序后的数据元素到屏幕显示，并且输出每一趟的排序结果显示在屏幕上。2.2.4各个排序模块具体的设计思路在后序的详细设计中将系统的介绍。3. 总体设计（框图

4、结构） 排序小软件错误再次输入堆排序折半插入排序快速排序冒泡排序直接插入排序退出 开始调用欢迎界面函数showmenu()Startface()选择操作项错误再次输入直接插入排序冒泡排序折半插入排序退出堆排序快速排序结束4. 详细设计4.1冒泡排序 冒泡排序是对所有相邻的记录进行比较，若这两个元素刚好与排序结果逆序，则将这两个元素的位置进行交换。 过程描述如下图所示：图3.3 冒泡排序的比较结果（1）、将整个的待排序序列的记录序列划分为有序区和无序区，初始状态有序区为空，无序区包括所有待排序的记录。（2）、对无序区从前向后依次将相邻记录的数据进行比较，若两结果的大小刚好与排序结果相反，则将其交

5、换，从而始数据值大的记录向右边移动。计较完无序区的最后两个记录，一趟冒泡排序结束。无序区最后一个记录进入有序区。（3）、重复步骤（2），直到无序区中只剩下一个记录。4.2快速排序 首先用两个指针i、j分别指向首，以第一个元素为关键字，该关键字所属的记录另存储在一个x变量中。从文件右端元素rj.key开始与控制字x.key相比较，当rj.key大于等于x.key时，rj不移动，修改指针j，j-，直到rj.key<x.key，把记录rj移动到文件左边i所指向的位置;然后在文件左边修改i指针,i+，让ri.key与x.key相比较，当ri.key小于等于x.key时，ri不移动，修改指针i，i

6、-，直到ri.key<x.key, 把记录ri移动到文件右边j所指向的位置;然后在文件右边修改j指针j-。重复上面的步骤. 初始关键字序列 72 6 57 88 60 42 83 73 48 85 i j j 进行1次交换之后 48 6 57 88 60 42 83 73 85 i i j进行2次交换之后 48 6 57 60 42 83 73 88 85 I j j进行3次交换之后 48 6 57 42 60 83 73 48 85 I j j完成一趟排序 48 6 57 42 60 72 83 73 88 85图4.2.1一趟快速排序过程初始状态 72 6 57 88 60 42 8

7、3 73 48 85一次划分之后 48 6 57 42 60 72 83 73 48 85分别进行快速排序 42 6 48 57 60 6 42 结束 57 60 结束 73 83 88 85 结束 85 88 结束有序序列 6 42 48 57 60 72 73 83 85 88图4.2.2快速排序的完整过程4.3直接插入排序设有一组关键字K1,K2,.,Kn,排序开始变认为K1是一个有序的序列,让K2插入到表长为1的有序序列,使之成为一个表长为2的有序序列, 让K3插入到表长为2的有序序列,使之成为一个表长为3的有序序列,依次类推,最后让Kn插入上述表长为n-1的有序序列,得到一个表长为n

8、的有序序列.4.4折半插入排序因为关键字K1,K2,.,Kn 是一个按关键字有序的有序序列，则可以利用折半查找实现“在关键字K1,K2,.,Kn中查找ki的插入位置”，如此实现的插入排序为折半插入排序。如同直接插入排序，只是确定插入的位置时，选择折半查找的方法。4.5堆排序 把n个记录存于向量r之中，把它看成完全二叉树，此时关键字序列不一定满足堆的关系。堆排序大体分为两步处理：初建堆，从堆的定义出发，当i=1、2、。、2/n时应满足ki<=k2i和ki<=k2i+1.所以先取i=n/2(它一定是第n个结点的双亲编号),将以i结点为根的子树调整为堆，然后令i=i-1，将以不结点为根的

9、子树调整为堆。此时可能会反复调整某些结点，直到i=1为止，堆初步建成。堆排序，首先输出堆顶元素（一般是最小值）,让堆中最后一个元素上移到原堆顶位置，然后恢复堆。因为经过第一步输出堆顶元素的操作后，往往破坏了堆关系，所以要恢复堆；重复执行输出堆顶元素、堆尾元素上移和恢复堆的步骤。5.系统测试系统主界面5.1冒泡排序5.2快速排序5.3直接插入排序5.4折半插入排序5.5堆排序5.6输入错误6. 课设总结通过这次课程设计的学习让我学会了许多，加深了对数据结构排序算法的认识。在这次课程设计中，完成了每种排序算法。排序算法选了五个，包括：冒泡排序、直接插入排序、折半插入排序、快速排序（递归）、堆排序。

10、同时也实现了随机数的生成。以及生成任意范围内的随机数。虽然在算法完成的过程中从网上参考了一些资料和实验内容，但对这次课程设计的成果还是比较满意的。这次的课程设计还有很多不足之处，如链表存储结构中的堆排序算法，当排序个数过多时，就会等待很长时间。可能时调用的函数过多的原因造成的，但排序是正确的。用指针代替函数的调用。还有就是随机数不能随时更改，只能设定一次。程序还存在的问题是如果用户输入错误，不能及时的进行提醒，在这方面还有提高的空间。同时在完成这个课程设计后，我也学到了很多知识，并能熟练的掌握他们了。首先学会了随机数的产生。熟练的撑握了C语言的函数调用、嵌套操作。撑握了每种排序算法的基本思想，

11、并学会了编写程序的一般步骤：思考问题，写出解决方案，写出伪代码，完成代码，调试程序。不像以前那样开始就直接写代码。当然，还包括如何写出操作简便，比较友好的界面。但我还是认为自己还有很多不足，希望以后能弥补。附（源代码）：#include<stdio.h>#include<time.h>#include<stdlib.h>#define MAX 100void produce_data(int a,int n)/产生数据int i; srand(unsigned)time(NULL);/产生随机数for(i=0;i<n;i+)ai=rand()%100;

12、void produce1_data(int data,int num) /随机产生一批数 /专门用于堆排序，数据从data1开始存放int i;srand(unsigned)time(NULL);for(i=1;i<=num;i+)datai=rand()%100;void print_data(int a,int n)/打印数据int i;int count;for(i=0;i<n;i+)printf("%5d",ai);count+;if(count%10=0)printf("n");printf("n");void

13、 print1_data(int data,int num) /输出数据 /专门用于堆排序，数据从data1开始输出int i;int count;for(i=1;i<=num;i+)printf("%5d",datai);count+;if(count%10=0)printf("n");void order_data(int *a,int n)/冒泡排序int i,j,temp;int flag=1;int k=0;/一定要赋初值，否则会产生随机数for(i=0;i<n-1&&flag=1;i+)flag=0;/利用进行标记

14、,减少比较次数for(j=0;j<n-i-1;j+)if(aj>aj+1)flag=1;temp=aj;aj=aj+1;aj+1=temp;k+;printf("第%d趟的排序结果为:",k);print_data(a,n);/函数的调用void QuickSort(int *a,int left,int right,int n)/(a,0,n-1,n) /利用快速排序算法，完成对数组list 中的index 个数进行排序。int i=left;int j=right;int temp=ai;int k;for(k=0;k<n;k+)while(i<

15、j)while(j>i)&&(aj>temp)j-;if(i<j)ai=aj;i+;while(j>i)&&(ai<temp)i+;if(i<j)aj=ai;j-;ai=temp;printf("%6d", ak);printf("n");if(left<i-1)QuickSort(a,left,i-1,n);/(left,i-1)递归if(i+1<right)QuickSort(a,i+1,right,n);/(i+1,right)递归/直接插入排序void InsertS

16、ort(int *a,int n) int i,j;int temp; for(i=1;i<n;i+)/控制循环的次数 temp=ai; for(j=i-1;j>=0;j-) if(aj>temp) aj+1=aj; else break; aj+1=temp;print_data(a,n); void createHeap (int *heap, int root, int n)int j;int temp; /于数值交换时的暂存变量int finish; /判断堆是否建立完成j=2*root; /子结点的indextemp=heaproot; /暂存heap 的root

17、值finish=0; /默认堆建立尚未完成while (j<=n && finish=0)/最大的子结点if (j<n)if (heapj<heapj+1)j+;if (temp>=heapj)finish=1; /堆建立完成elseheapj/2=heapj; /父结点=目前结点j=2*j;heapj/2=temp; /父结点=root 值void HeapSort(int *heap,int n) /堆排序int i,j,temp;for(i=(n/2);i>=1;i-) /将二叉树转成heapcreateHeap(heap,i,n);for(

18、i=n-1;i>=1;i-) /开始进行堆排序temp=heapi+1; /heap 的root 值和最后一个值交换heapi+1=heap1;heap1=temp;createHeap(heap, 1, i); /对其余数值重建堆*/printf("n 目前的排序为:"); /打印堆处理过程*/for(j=1;j<=n;j+)printf("%3d",heapj);/printf("n");void bisort(int *a,int n)int low,high,m,k;int temp;for(k=2;k<=n

19、;k+)temp=ak-1;low=0;high=k-2;do m=(low+high)/2;if (temp<=am)high=m-1;/插入前半区else low=m+1;/插入后半区 while (low<=high);for (high=k-1;high>low;high-)ahigh=ahigh-1;/记录右移 ahigh=temp;/插入数据 print_data(a,n);void auther()printf("nnnnnnnnnttt 软件名称:数据排序软件nn");printf("ttt 技术开发:张浩然nn");p

20、rintf("ttt 请按任意键继续.");getch();system("cls");void showmenu() /显示菜单printf("tt*欢迎使用数据排序小软件*n");printf("tt1、冒泡排序n");printf("tt2、快速排序n");printf("tt3、直接插入排序n");printf("tt4、堆排序n");printf("tt5、折半插入排序n");printf("tt6、退出程序n&qu

21、ot;);main()int num,choice;int aMAX;system("color f9");/第一个为背景，第二个为前景(亮白色，浅蓝色)auther();while(1)showmenu();printf("请输入你的选择:n");scanf("%d",&choice);switch(choice)case 1:printf("你选择的是冒泡排序n");printf("请输入产生数据个数n");scanf("%d",&num);printf(

22、"排序前的数据n");produce_data(a,num);print_data(a,num);printf("排序过程为:n");order_data(a,num);printf("最终的排序结果为:n");print_data(a,num);system("pause");system("cls");break;case 2:printf("你选择的是快速排序n");printf("请输入产生数据个数n");scanf("%d",

23、&num);produce_data(a,num);printf("排序前的数据为:n");print_data(a,num);printf("n 排序过程如下：n");QuickSort(a,0,num-1,num);/函数的调用printf("n 最终的排序结果为:n");print_data(a,num);printf("n");system("pause");system("cls");break; case 3:printf("你选择的是直接插入排序n");printf("请输入产生数据个数n");scanf("%d",&num);produce_data(a,num);printf("排序前的数据为:n");print_data(a,num);printf("排序过程为:n");InsertSort(a,num);printf("n 最终的排序结果为:n");print_data(a,num);system("pause");system("cls