数据结构课程设计实习报告.docx

数据结构课程设计实习报告（排序操作）学 院：计算机学院 专 业： 班 级： 学 号： 姓 名： 指导教师： 完成日期： 目录一、 需求分析 11. 运行环境 12. 程序所实现的功能 13. 程序的输入 14. 程序的输出 1二、 设计说明 11. 算法设计的思想 12. 主要的数据结构设计说明 23. 程序的主要流程图 34. 程序的主要模块 35. 程序的主要函数及其伪代码说明 4三、 上机结果及体会 71. 实际完成的情况说明 72. 程序算法的性能分析 73. 程序运行时的初值和运行结果 84. 程序中可以改进的地方说明 115. 收获及体会 116. 源程序及注释 12四、 参考文献 19一、需求分析1. 运行环境：软件环境：Microsoft Visual C+ 6.0。2. 程序所实现的功能 本程序实现了直接插入排序、折半插入排序、冒泡排序、简单选择排序、快速排序、堆排序、归并排序等多种排序算法的功能，并且对每一种而言，都能输出每一趟的排序结果。3. 程序的输入： 本程序的输入的格式为：元素+空格+元素，并按回车键结束输入。如（49_38_65_97_76_13_27_49回车键），且本程序仅适用于整形数据。4. 程序的输出： 本程序能输出每一趟的排序结果，且输出的格式和输入的格式基本一致。 二、设计说明1. 算法设计的思想：(1)直接插入排序的算法设计思想为：将一个记录插入到已排好的有序表中，从而得到一个新的、记录数增1的有序表。一般情况下，第i趟直接插入排序的操作为：在含有i-1个记录的有序子序列R1.i-1中插入一个记录Ri后，变成含有i个记录的有序的子序列R1.i；并且，和顺序表类似，为了在查找插入位置的过程中避免数组下标出界，在R0出设置监视哨。(2)折半插入排序的算法思想为：在一个有序表中进行折半查找和插入。第1页(3)冒泡排序的算法思想为：首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序（即L-R1.keyL-R2.key），则将两个记录交换之，然后比较第二个记录的关键字和第三个记录的关键字。依次类推，直至第n-1个记录和第n个记录的关键字进行过比较为止。一般地，第i趟冒泡排序是从L-R1到L-Rn-i+1依次比较相邻事物两个记录的关键字，并在“逆序”是交换记录，其结果是这n-i+1个记录中关键字最大的记录被交换到第n-i+1的位置上。(4)简单选择排序的算法设计思想为：通过n-i次关键字之间的比较，从n-i+1个记录中选择出关键字最小的记录，并和第i个记录交换之。(5)快速排序的算法设计思想为：通过每一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。(6)堆排序的算法设计思想为：将初始序列建成一个堆，若在输出堆顶的最小值后，使得剩余的n-1个元素的序列重又建成一个堆，则得到n个元素中的次小值，如此反复执行，便能得到一个有序的序列。(7)归并排序的算法设计思想为：假设初始序列含有n个记录，则可看成n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n2个长度为2或1的有序子序列；再两两归并，如此重复，直至得到一个长度为n的有序序列为止。2. 主要的数据结构设计说明：(1) 本程序的储存结构主要采用顺序表储存结构：typedef structint key; /关键字RedType; /记录类型typedef struct RedType RMAXSIZE+1;/R0闲置为哨兵int length; /顺序表长度*SqList,sq; /顺序表类型(2)本程序的输入与输出均采用了“do-while”语句，而主函数的功能选择采用了“case”语句。如下是输入函数的一段代码： do i+;scanf(%d%c,&L-Ri.key,&ch); 第2页while(ch!=n); 3. 程序的主要流程图：菜单退出堆 排 序直接插入排序折半插入排序冒 泡 排 序归 并 排 序快 速 排 序简单选择排序输入待排序列按任意键返回输出每一趟结果4. 程序的主要模块： (1)菜单模块由Menu()函数实现。第3页 (2)各排序功能：直接插入排序模块由InsertSort(SqList L)函数实现，折半插入排序模块由BInsertSort(SqList L)函数实现，冒泡排序模块由BubbleSort(SqList L)函数实现，简单选择排序模块由SelectSort(SqList L)函数和SelectMinKey(SqList L,int i)函数实现，快速排序模块由QSort(SqList L,int low ,int high)函数、QuickSort(SqList L)函数和Partition(SqList L,int low ,int high)函数实现，堆排序模块由HeapAdjust(SqList L,int s,int m)函数和HeapSort(SqList L)函数实现，归并排序模块由MergeSort(SqList L, int length)函数实现。 (3)输入与输出模块：输入模块由CreatSqList(SqList L)函数实现，输出模块由PrintSort(SqList L)函数和FiPrintSort(SqList L)函数实现。5. 程序的主要函数及其伪代码说明： (1)直接插入排序： void InsertSort(SqList L) /直接插入排序 int i,j; for(i=2;ilength;+i)if(L-Ri.keyRi-1.key) /需将L-Ri插入有序子表L-R0=L-Ri; /复制为哨兵L-Ri=L-Ri-1;for(j=i-2;(L-R0.keyRj.key);-j)L-Rj+1=L-Rj;/记录后移L-Rj+1=L-R0;/插入到正确的位置PrintSort(L); /输出排序结果a=1; (2)折半插入排序： void BInsertSort(SqList L) /折半插入排序int i,j,m,low,high;for(i=2;ilength;+i) L-R0=L-Ri;/将L-Ri暂存到L-R0 low=1;high=i-1; while(lowR0.keyRm.key) high=m-1; /插入点在低区else low=m+1; /插入点在高区for(j=i-1;j=high+1;-j) L-Rj+1=L-Rj; /记录后移 L-Rhigh+1=L-R0; /插入PrintSort(L); /输出排序结果a=1;/将a重新初始化为 (3)冒泡排序： void BubbleSort(SqList L) /冒泡排序；int i,j,m;for(i=1;ilength;i+) for(j=0;jlength;j+) /选择表L中最大的依次放到最后面的位置中去 if(L-Rj.keyL-Rj+1.key&jlength) m=L-Rj.key;L-Rj.key=L-Rj+1.key; L-Rj+1.key=m;PrintSort(L);/输出排序结果 a=1; (4)简单选择排序： void SelectSort(SqList L) /简单选择排序int i,j,m;int SelectMinKey(SqList L,int i);for(i=1;ilength;+i) /选择第i小的记录，并交换到位j=SelectMinKey(L,i); /在L-Ri.L-length中选择key最小记录if(i!=j) /与第i个记录交换m=L-Ri.key;L-Ri.key=L-Rj.key;L-Rj.key=m; PrintSort(L);a=1; (5)快速排序： void QuickSort(SqList L) /快速排序QSort(L,1,L-length); /对顺序表L调用快速排序第5页a=1; void QSort(SqList L,int low ,int high)int pivotloc;if(lowlength/2;i0;-i) /把L-R1.L-length建成大顶堆 HeapAdjust(L,i,L-length);for(i=L-length;i1;-i)m=L-R1.key;/将堆顶记录和当前未经排序子序列L-R1.i中L-R1.key=L-Ri.key; /最后一个记录相互交换L-Ri.key=m;PrintSort(L);HeapAdjust(L,1,i-1); /将L-R1.i-1重新调整为大顶堆a=1;(7)归并排序： void MergeSort(SqList L, int length) /归并排序 int i, left_min, left_max, right_min, right_max, next; int *tmp = (int*)malloc(sizeof(int) * length); if (tmp = NULL) fputs(Error: out of memoryn, stderr); for (i = 1; i length; i *= 2) / i为步长，1,2,4,8 for (left_min = 1; left_min length) right_max = length+1; next = 1;第6页 while (left_min left_max & right_min Rleft_min.key L-Rright_min.key ? L-Rright_min+.key : L-Rleft_min+.key; while (left_min R-right_min.key = L-R-left_max.key; while (next 1) L-R-right_min.key = tmp-next; PrintSort(L); a=1; free(tmp);三、上机结果及体会1. 实际完成的情况说明： 本程序基本完成了直接插入排序、折半插入排序、冒泡排序、简单选择排序、快速排序、堆排序以及归并排序的算法功能，并能输出各种排序算法的每一趟排序结果。 本程序仅支持整形数据（int 类型）。2. 程序算法的性能分析：第7页3. 程序运行时的初值和运行结果： (1)直接插入排序： (2)折半插入排序：第8页 (3)冒泡排序： (4)简单选择排序：第9页 (5)快速排序： (6)堆排序：第10页 (7)归并排序：4. 程序中可以改进的地方说明 本程序对误操作的处理不是很理想，而且对数据的要求也比较严格，只能是int类型的数据才行，另外，堆排序不能将生成的堆以二叉树的形式输出。以上这些都是可以改进的地方。5. 收获及体会：通过这次课程设计的学习让我学会了许多。让我对数据结构知识有了很大理解！在这次课程设计中，我独立完成了直接插入排序、折半插入排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序等几种排序算法。虽然在算法完成的过程中出现了好多问题，但我对这次课程设计的成果还是非常满意的。 第11页这次的课程设计还有很多不足之处，如用指针代替函数的调用。在完成这个课程设计后，我也学到了很多知识，并能训练的掌握他们了。我撑握了每种排序算法的基本思想，并从同学那里学会了编写程序的一般步骤：思考问题，写出解决方案，写出伪代码，完成代码，调试程序。不像以前那样开始就直接写代码。 但我还是认为自己有些不足，希望以后能弥补这些不足。所以，这次的课程设计我学会了很多，不光让我认识了数据结构知识，还让我学会了一些道理，那就是做事情的时候即使不会做也不能慌张，要慢慢放下心来，不要光想着自己怎么、怎么不会了！不要去想不会，而是冷下心来慢慢思考、思考。这样你就会有了思路的。 6. 源程序及注释：#include#include# define MAXSIZE 30 /顺序表的最大长度int a=1; /全局变量，用于标记排序的趟数typedef structint key; /关键字RedType; /记录类型typedef struct RedType RMAXSIZE+1;/R0闲置为哨兵int length; /顺序表长度*SqList,sq; /顺序表类型Void PrintSort(SqList L) /输出函数 int i=1;printf(#n);printf(第%d 趟排序结果为:,a+);while(ilength) printf(%d ,L-Ri.key);i+; printf(n); void FiPrintSort(SqList L) /输出最终结果int i=1;printf(#n);printf(最终的排序结果为:);while(ilength) printf(%d ,L-Ri.key); i+; printf(n); int CreatSqList(SqList L) /顺序表的创建第12页int i=0; int j=1; char ch;printf(#n); printf(请输入待排整数(整数之间用空格隔开,按回车结束):);do i+; scanf(%d%c,&L-Ri.key,&ch); while(ch!=n); L-length=i;printf(#n); printf(初始的待排序列为:);while(jlength) printf(%d ,L-Rj.key); j+; printf(n); return 1; int artition(SqList L,int low ,int high) int key; /枢纽记录L-R0=L-Rlow; /表的第一元素记录枢纽关键字key=L-Rlow.key; while(lowhigh)while(lowRhigh.key=key)-high;/将比枢纽记录小的移到低端L-Rlow=L-Rhigh;while(lowRlow.keyRhigh=L-Rlow;L-Rlow=L-R0; /枢纽记录到位PrintSort(L); /输出排序结果return low; void sertSort(SqList L) /直接插入排序 int i,j;for(i=2;ilength;+i)if(L-Ri.keyRi-1.key) /需将L-Ri插入有序子表L-R0=L-Ri; /复制为哨兵L-Ri=L-Ri-1;for(j=i-2;(L-R0.keyRj.key);-j) L-Rj+1=L-Rj;/记录后移L-Rj+1=L-R0;/插入到正确的位置PrintSort(L); /输出排序结果a=1;第13页void BInsertSort(SqList L) /折半插入排序int i,j,m,low,high;for(i=2;ilength;+i)L-R0=L-Ri;/将L-Ri暂存到L-R0low=1;high=i-1;while(lowR0.keyRm.key) high=m-1; /插入点在低区else low=m+1; /插入点在高区for(j=i-1;j=high+1;-j)L-Rj+1=L-Rj; /记录后移 L-Rhigh+1=L-R0; /插入PrintSort(L); /输出排序结果a=1;/将a重新初始化为1void BubbleSort(SqList L) /冒泡排序int i,j,m;for(i=1;ilength;i+) for(j=0;jlength;j+) /选择表L中最大的依次放到最后面的位置中去 if(L-Rj.keyL-Rj+1.key&jlength) m=L-Rj.key; L-Rj.key=L-Rj+1.key; L-Rj+1.key=m;PrintSort(L);/输出排序结果 a=1;void SelectSort(SqList L) /简单选择排序int i,j,m;int SelectMinKey(SqList L,int i);for(i=1;ilength;+i)/选择第i小的记录，并交换到位j=SelectMinKey(L,i); /在L-Ri.L-length中选择key最小记录if(i!=j) /与第i个记录交换m=L-Ri.key; L-Ri.key=L-Rj.key; L-Rj.key=m; PrintSort(L);第14页a=1;int SelectMinKey(SqList L,int i) /在L-Ri.L-length中选择key最小记录int m=i,n=L-Ri.key;for(;ilength;i+)if(n=L-Ri.key) n=L-Ri.key;m=i;return m; void QSort(SqList L,int low ,int high)int pivotloc;if(lowlength); /对顺序表L调用快速排序a=1;void HeapAdjust(SqList L,int s,int m) /已知L-Rs.m中记录的关键字除int i,j; /L-s.key之外均满足堆的定义，本函数调整i=L-Rs.key;/L-Rs 的关键字，使L-Rs.m成为一个大顶堆(对其中记录的关键字而言)for(j=2*s;j=m;j*=2) /沿key较大的孩子结点向下筛选if(jRj.keyRj+1.key)+j;/j为key较大的记录的下标if(!(iRj.key)/i应插入在位置上break;L-Rs.key=L-Rj.key; s=j;/插入L-Rs.key=i;void HeapSort(SqList L) /堆排序int i,m;for(i=L-length/2;i0;-i) /把L-R1.L-length建成大顶堆HeapAdjust(L,i,L-length);for(i=L-length;i1;-i)第15页m=L-R1.key; /将堆顶记录和当前未经排序子序列L-R1.i中L-R1.key=L-Ri.key; /最后一个记录相互交换L-Ri.key=m; PrintSort(L);HeapAdjust(L,1,i-1); /将L-R1.i-1重新调整为大顶堆a=1; void MergeSort(SqList L, int length) /归并排序 int i, left_min, left_max, right_min, right_max, next; int *tmp = (int*)malloc(sizeof(int) * length); if (tmp = NULL) fputs(Error: out of memoryn, stderr); for (i = 1; i length; i *= 2) / i为步长，1,2,4,8 for (left_min = 1; left_min length) right_max = length+1; next = 1; while (left_min left_max & righ