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

《数据结构课程设计实习报告》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、数据结构课程设计实习报告（排序操作）学院：计算机学院专业：班级：学号：姓名：指导教师：完成日期：目录一、需求分析………………………………………………11.运行环境……………………………………………12.程序所实现的功能…………………………………13.程序的输入…………………………………………14.程序的输出…………………………………………1二、设计说明………………………………………………11.算法设计的思想……………………………………12.主要的数据结构设计说明…………………………23.程序的主要流程图…………………………………34.程序的主要模块…………………………………3

2、5.程序的主要函数及其伪代码说明…………………4三、上机结果及体会………………………………………71.实际完成的情况说明………………………………72.程序算法的性能分析………………………………73.程序运行时的初值和运行结果……………………84.程序中可以改进的地方说明………………………115.收获及体会…………………………………………116.源程序及注释………………………………………12四、参考文献………………………………………………19一、需求分析1.运行环境：软件环境：MicrosoftVisualC++6.0。2.程序所实现的功能本程序实现了直接插入排序、折半插入排序

3、、冒泡排序、简单选择排序、快速排序、堆排序、归并排序等多种排序算法的功能，并且对每一种而言，都能输出每一趟的排序结果。3.程序的输入：本程序的输入的格式为：元素+空格+元素，并按回车键结束输入。如（49_38_65_97_76_13_27_49回车键），且本程序仅适用于整形数据。4.程序的输出：本程序能输出每一趟的排序结果，且输出的格式和输入的格式基本一致。二、设计说明1.算法设计的思想：(1)直接插入排序的算法设计思想为：将一个记录插入到已排好的有序表中，从而得到一个新的、记录数增1的有序表。一般情况下，第i趟直接插入排序的操作为：在含有i-1个记录的有序子序列R[1...

4、i-1]中插入一个记录R[i]后，变成含有i个记录的有序的子序列R[1...i]；并且，和顺序表类似，为了在查找插入位置的过程中避免数组下标出界，在R[0]出设置监视哨。(2)折半插入排序的算法思想为：在一个有序表中进行折半查找和插入。第1页(3)冒泡排序的算法思想为：首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序（即L->R[1].key>L->R[2].key），则将两个记录交换之，然后比较第二个记录的关键字和第三个记录的关键字。依次类推，直至第n-1个记录和第n个记录的关键字进行过比较为止。一般地，第i趟冒泡排序是从L->R[1]到L->R[n-i+1]

5、依次比较相邻事物两个记录的关键字，并在“逆序”是交换记录，其结果是这n-i+1个记录中关键字最大的记录被交换到第n-i+1的位置上。(4)简单选择排序的算法设计思想为：通过n-i次关键字之间的比较，从n-i+1个记录中选择出关键字最小的记录，并和第i个记录交换之。(5)快速排序的算法设计思想为：通过每一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。(6)堆排序的算法设计思想为：将初始序列建成一个堆，若在输出堆顶的最小值后，使得剩余的n-1个元素的序列重又建成一个堆，则得到n个元素中

6、的次小值，如此反复执行，便能得到一个有序的序列。(7)归并排序的算法设计思想为：假设初始序列含有n个记录，则可看成n个有序的子序列，每个子序列的长度为1，然后两两归并，得到[n2]个长度为2或1的有序子序列；再两两归并，……，如此重复，直至得到一个长度为n的有序序列为止。1.主要的数据结构设计说明：(1)本程序的储存结构主要采用顺序表储存结构：typedefstruct{intkey;//关键字}RedType;//记录类型typedefstruct{RedTypeR[MAXSIZE+1];//R[0]闲置为哨兵intlength;//顺序表长度}*SqList,sq;//顺

7、序表类型(2)本程序的输入与输出均采用了“do-while”语句，而主函数的功能选择采用了“case”语句。如下是输入函数的一段代码：do{i++;scanf("%d%c",&L->R[i].key,&ch);第2页}while(ch!='');1.程序的主要流程图：菜单退出堆排序直接插入排序折半插入排序冒泡排序归并排序快速排序简单选择排序输入待排序列按任意键返回输出每一趟结果2.程序的主要模块：(1)菜单模块由Menu()函数实现。第3页(2)各排序功能：直接插入排序模块由InsertSort(S