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

    数据结构课程设计实习报告15200字    数据结构课程设计实习报告（排序操作）专业：班级：学号：姓名：指导教师：完成日期：目录一、 需求分析?????????????????? 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个记录的有序子序列R[1...i-1]中插入一个记录R[i]后，变成含有i个记录的有序的子序列R[1...i]；并且，和顺序表类似，为了在查找插入位置的过程中避免数组下标出界，在R[0]出设置监视哨2)折半插入排序的算法思想为：在一个有序表中进行折半查找和插入3)冒泡排序的算法思想为：首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序（即L->R[1].key>L->R[2].key），则将两个记录交换之，然后比较第二个记录的关键字和第三个记录的关键字。

依次类推，直至第n-1个记录和第n个记录的关键字进行过比较为止一般地，第i趟冒泡排序是从L->R[1]到L->R[n-i+1]依次比较相邻事物两个记录的第1页关键字，并在“逆序”是交换记录，其结果是这n-i+1个记录中关键字最大的记录被交换到第n-i+1的位置上4)简单选择排序的算法设计思想为：通过n-i次关键字之间的比较，从n-i+1个记录中选择出关键字最小的记录，并和第i个记录交换之5)快速排序的算法设计思想为：通过每一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序6)堆排序的算法设计思想为：将初始序列建成一个堆，若在输出堆顶的最小值后，使得剩余的n-1个元素的序列重又建成一个堆，则得到n个元素中的次小值，如此反复执行，便能得到一个有序的序列7)归并排序的算法设计思想为：假设初始序列含有n个记录，则可看成n个有序的子序列，每个子序列的长度为1，然后两两归并，得到[?个长度为2或1的有序子序列；再两两归并，??，如此重复，直至得到一个长度为n的有序序列为止2. 主要的数据结构设计说明：(1)本程序的储存结构主要采用顺序表储存结构：typedefstruct{int key; //关键字 ?}RedType; //记录类型typedefstruct{RedType R[MAXSIZE+1];//R[0]闲置为哨兵int length; //顺序表长度}*SqList,sq; //顺序表类型(2)本程序的输入与输出均采用了“do-while”语句，而主函数的功能选择采用了“case”语句。

如下是输入函数的一段代码：do{ i++; scanf("%d%c",&L->R[i].key,&ch);}while(ch!='\n');第2页3. 程序的主要流程图：4. 程序的主要模块：(1)菜单模块由Menu()函数实现2)各排序功能：直接插入排序模块由InsertSort(SqList L)函数实现，折半插入排序模块由BInsertSort(SqList L)函数实现，冒泡排序模块由BubbleSort(SqList L)函数实现，简单选择排序模块由SelectSort(SqList L)函数和SelectMinKey(SqListL,inti)函数实现，第3页快速排序模块由QSort(SqListL,int low ,int high)函数、QuickSort(SqList L)函数和Partition(SqListL,int low ,int high)函数实现，堆排序模块由HeapAdjust(SqListL,ints,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){//⑴直接插入排序inti,j; for(i=2;i<=L->length;++i){ if(L->R[i].keyR[i-1].key) //需将L->R[i]插入有序子表 { L->R[0]=L->R[i]; //复制为哨兵 L->R[i]=L->R[i-1]; for(j=i-2;(L->R[0].keyR[j].key);--j) L->R[j+1]=L->R[j]; //记录后移 //插入到正确的位置 L->R[j+1]=L->R[0]; }PrintSort(L);}a=1;} //输出排序结果(2)折半插入排序：void BInsertSort(SqList L){//折半插入排序inti,j,m,low,high; for(i=2;i<=L->length;++i){ L->R[0]=L->R[i]; low=1;high=i-1; while(low<=high) //在R[low..high]中折半查找有序插入的位置 {m=(low+high)/2; //折半 //将L->R[i]暂存到L->R[0] if(L->R[0].keyR[m].key) high=m-1; //插入点在低区第4页elselow=m+1; //插入点在高区 } for(j=i-1;j>=high+1;--j) //记录后移 L->R[j+1]=L->R[j]; L->R[high+1]=L->R[0]; PrintSort(L); a=1; //插入 //输出排序结果} //将a重新初始化为}(3)冒泡排序：void BubbleSort(SqList L){//冒泡排序；inti,j,m; for(i=1;ilength;i++){ for(j=0;jlength;j++) { //选择表L中最大的依次放到最后面的位置中去 if(L->R[j].key>L->R[j+1].key&&jlength){ m=L->R[j].key;L->R[j].key=L->R[j+1].key; L->R[j+1].key=m;}} //输出排序结果 } PrintSort(L); a=1;}(4)简单选择排序：void SelectSort(SqList L){ //简单选择排序inti,j,m; intSelectMinKey(SqListL,inti); for(i=1;ilength;++i){ //选择第i小的记录，并交换到位 j=SelectMinKey(L,i); //在L->R[i..L->length]中选择key最小记录 if(i!=j){ //与第i个记录交换 m=L->R[i].key;L->R[i].key=L->R[j].key;L->R[j].key=m;} PrintSort(L);} a=1;}(5)快速排序：void QuickSort(SqList L){//快速排序QSort(L,1,L->length); //对顺序表L调用快速排序 a=1;}第5页voidQSort(SqListL,int low ,int high){intpivotloc; if(lowlength/2;i>0;--i) //把L->R[1..L->length]建成大顶堆 HeapAdjust(L,i,L->length); for(i=L->length;i>1;--i){ m=L->R[1].key; //将堆顶记录和当前未经排序子序列L->R[1..i]中 L->R[1].key=L->R[i].key; //最后一个记录相互交换 L->R[i].key=m; PrintSort(L); HeapAdjust(L,1,i-1); //将L->R[1..i-1]重新调整为大顶堆 } a=1;}(7)归并排序：void MergeSort(SqList L, int length){//归并排序inti, left_min, left_max, right_min, right_max, next;int *tmp = (int*)malloc(sizeof(int) * length);if (tmp == NULL) {fputs("Error: out of memory\n", stderr);}for (i = 1; i< length; i *= 2) {// i为步长，1,2,4,8……for (left_min = 1; left_min<= length-i; left_min = right_max){right_min=left_max = left_min+i;right_max=left_max + i;if (right_max> length){right_max = length+1;}next = 1;while (left_min