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

1HUBEIUNIVERSITYOFAUTOMOTIVETECHNOLOGY数据结构课程设计报告课设题目：多种排序方式的比较专业：计算机科学与技术班级：姓名：张浩然完成日期：指导教师：2目录1、引言1.1课设目的---------------------------------------------------------31.2课设内容---------------------------------------------------------32、需求分析2.1任务与分析------------------------------------------------------32.2功能模块的划分-------------------------------------------------33、总体设计------------------------------------------4、详细设计------------------------------------------4.1冒泡排序-----------------------------------------------------------54.2快速排序-----------------------------------------------------------64.3直接插入排序-----------------------------------------------------74.5折半插入排序-----------------------------------------------------74.4堆排序--------------------------------------------------------------75、调试结果-------------------------------------------5.1冒泡排序测试----------------------------------------------------85.2快速排序测试----------------------------------------------------85.3直接插入排序测试----------------------------------------------95.4折半插入排序测试----------------------------------------------95.5堆排序测试-------------------------------------------------------105.6输入错误----------------------------------------------------------106、课程设计总结--------------------------------------1131.1课程设计目的学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及相应的算法。另一方面，通过团队合作、文档编制、主页设计等环节对学生进行全方位的训练，最终达到培养数据抽象能力和软件设计的能力。通过全部过程培养和锻炼的钻研能力、动手能力、分析问题和解决问题的实际能力。1.2课程设计内容本程序把对数列的排序转化为对数组元素的排序，用户可以根据自己的实际问题选择系统提供的几种排序方法的任意一种进行排序。包括冒泡排序，直接插入排序，折半插入排序，堆排序和快速排序。对于每一种排序算法可以输出初始序列和每一趟的排序结果。2.1任务与分析任务：利用随机函数产生N个随机整数，对这些数进行多种方法进行排序。分析：本系统实现了几种常用的排序方法，包括：折半插入排序、直接插入排序、冒泡排序、快速排序（递归）、堆排序。2.2功能模块的划分2..2.1输入模块利用随机函数产生N个随机整数，个数由用户从键盘中自己输入。2.2.2选择模块在菜单中选择相应的编号来选择采用何种排序算法，算法包括：冒泡排序、直接插入排序、折半插入、快速排序（递归）、堆排序。2.2.3输出模块输出排序前或排序后的数据元素到屏幕显示，并且输出每一趟的排序结果显示在屏幕上。2.2.4各个排序模块具体的设计思路在后序的详细设计中将系统的介绍。3.总体设计（框图结构）4直接插入排序冒泡排序快速排序折半插入排序堆排序退出错误再次输入排序小软件开始调用欢迎界面函数showmenu()Startface()选择操作项错误再次输入直接插入排序冒泡排序快速排序折半插入排序堆排序退出结束54.详细设计4.1冒泡排序冒泡排序是对所有相邻的记录进行比较，若这两个元素刚好与排序结果逆序，则将这两个元素的位置进行交换。过程描述如下图所示：图3.3冒泡排序的比较结果（1）、将整个的待排序序列的记录序列划分为有序区和无序区，初始状态有序区为空，无序区包括所有待排序的记录。（2）、对无序区从前向后依次将相邻记录的数据进行比较，若两结果的大小刚好与排序结果相反，则将其交换，从而始数据值大的记录向右边移动。计较完无序区的最后两个记录，一趟冒泡排序结束。无序区最后一个记录进入有序区。（3）、重复步骤（2），直到无序区中只剩下一个记录。4.2快速排序首先用两个指针i、j分别指向首，以第一个元素为关键字，该关键字所属的记录另存储在一个x变量中。从文件右端元素r[j].key开始与控制字x.key相比较，当r[j].key大于等于x.key时，r[j]不移动，修改指针j，j--，直到r[j].keyx.key，把记录r[j]移动到文件左边i所指向的位置;然后在文件左边修改i指针,i++，让r[i].key与x.key相比较，当r[i].key小于等于x.key时，r[i]不移动，修改指针i，i--，直到r[i].keyx.key,把记录r[i]移动到文件右边j所指向的位置;然后在文件右边修改j指针j--。重复上面的步骤.初始关键字序列72657886042837348856ijj进行1次交换之后48657886042837385iij进行2次交换之后48657604283738885Ijj进行3次交换之后48657426083734885Ijj完成一趟排序4865742607283738885图4.2.1一趟快速排序过程初始状态{7265788604283734885}一次划分之后{486574260}72{83734885}分别进行快速排序{426}48{5760}{6}42结束57{60}结束{73}83{8885}结束{85}88结束有序序列{6424857607273838588}图4.2.2快速排序的完整过程4.3直接插入排序设有一组关键字{K1,K2,…….,Kn},排序开始变认为K1是一个有序的序列,让K2插入到表长为1的有序序列,使之成为一个表长为2的有序序列,让K3插入到表长为2的有序序列,使之成为一个表长为3的有序序列,依次类推,最后让Kn插入上述表长为n-1的有序序列,得到一7个表长为n的有序序列.4.4折半插入排序因为关键字{K1,K2,…….,Kn}是一个按关键字有序的有序序列，则可以利用折半查找实现“在关键字{K1,K2,…….,Kn}中查找k[i]的插入位置”，如此实现的插入排序为折半插入排序。如同直接插入排序，只是确定插入的位置时，选择折半查找的方法。4.5堆排序把n个记录存于向量r之中，把它看成完全二叉树，此时关键字序列不一定满足堆的关系。堆排序大体分为两步处理：初建堆，从堆的定义出发，当i=1、2、。。。。、[2/n]时应满足ki=k2i和ki=k2i+1.所以先取i=[n/2](它一定是第n个结点的双亲编号),将以i结点为根的子树调整为堆，然后令i=i-1，将以不结点为根的子树调整为堆。此时可能会反复调整某些结点，直到i=1为止，堆初步建成。堆排序，首先输出堆顶元素（一般是最小值）,让堆中最后一个元素上移到原堆顶位置，然后恢复堆。因为经过第一步输出堆顶元素的操作后，往往破坏了堆关系，所以要恢复堆；重复执行输出堆顶元素、堆尾元素上移和恢复堆的步骤。5.系统测试系统主界面85.1冒泡排序5.2快速排序95.3直接插入排序5.4折半插入排序105.5堆排序5.6输入错误116.课设总结通过这次课程设计的学习让我学会了许多，加深了对数据结构排序算法的认识。在这次课程设计中，完成了每种排序算法。排序算法选了五个，包括：冒泡排序、直接插入排序、折半插入排序、快速排序（递归）、堆排序。同时也实现了随机数的生成。以及生成任意范围内的随机数。虽然在算法完成的过程中从网上参考了一些资料和实验内容，但对这次课程设计的成果还是比较满意的。这次的课程设计还有很多不足之处，如链表存储结构中的堆排序算法，当排序个数过多时，就会等待很长时间。可能时调用的函数过多的原因造成的，但排序是正确的。用指针代替函数的调用。还有就是随机数不能随时更改，只能设定一次。程序还存在的问题是如果用户输入错误，不能及时的进行提醒，在这方面还有提高的空间。同时在完成这个课程设计后，我也学到了很多知识，并能熟练的掌握他们了。首先学会了随机数的产生。熟练的撑握了C语言的函数调用、嵌套操作。撑握了每种排序算法的基本思想，并学会了编写程序的一般步骤：思考问题，写出解决方案，写出伪代码，完成代码，调试程序。不像以前那样开始就直接写代码。当然，还包括如何写出操作简便，比较友好的界面。但我还是认为自己还有很多不足，希望以后能弥补。12附（源代码）：#includestdio.h#includetime.h#includestdlib.h#defineMAX100voidproduce_data(inta[],intn){//产生数据inti;srand((unsigned)time(NULL));//产生随机数for(i=0;in;i++){a[i]=rand()%100;}}voidproduce1_data(intdata[],intnum)//随机产生一批数{//专门用于堆排序，数据从data[1]开始存放inti;srand((unsigned)time(NULL));for(i=1;i=num;i++)data[i]=rand()%100;}voidprint_data(inta[],intn){//打印数据inti;intcount;for(i=0;in;i++){printf(%5d,a[i]);13count++;if(count%10==0)printf(\n);}printf(\n);}voidprint1_data(intdata[],intnum)//输出数据{//专门用于堆排序，数据从data[1]开始输出inti;intcount;for(i=1;i=num;i++){printf(%5d,data[i]);count++;if(count%10==0)printf(\n);}}voidorder_data(int*a,intn){//冒泡排序inti,j,temp;intflag=1;intk=0;//一定要赋初值，否则会产生随机数for(i=0;in-1&&flag==1;i++){flag=0;//利用进行标记,减少比较次数14for(j=0;jn-i-1;j++){if(a[j]a[j+1]){flag=1;temp=a[j];a[j]=a[j+1];a[j+1]=temp;}}k++;printf(第%d趟的排序结果为:,k);print_data(a,n);//函数的调用}}voidQuickSort(int*a,intleft,intright,intn)//(a,0,n-1,n){//利用快速排序算法，完成对数组list中的index个数进行排序。inti=left;intj=right;inttemp=a[i];intk;for(k=0;kn;k++){whi