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

《《数据结构》课程设计报告new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、课程设计(论文)题目名称几种常见的排序算法的实现与性能分析课程名称数据结构课程设计学生姓名龚云学号0841330022系、专业信息工程系、电气信息类（信息类）指导教师黄同成2010年1月3日摘要设计一个测试程序比较起泡排序、直接排序、简单选择排序、快速排序、希尔排序、堆排序算法的关键字比较次数和移动次数。运用多种自定义函数，通过在主函数中调用自定义函数，实现其功能，最后输出相应算法的比较次数和移动次数。从而直观的判断各内部排序算法性能的优劣。关键词：内部排序；直观；比较次数；移动次数目录1问题描述错误！未定义书签。2需求分析错误！未定义书签。3概要设计43

2、.1抽象数据类型定义43.2模块划分54详细设计64.1数据类型的定义64.2主要模块的算法描述65测试分析96课程设计的总结与体会10参考文献11附录（源程序清单）错误！未定义书签。1问题描述设计一个测试程序比较起泡排序、直接排序、简单选择排序、快速排序、希尔排序、堆排序算法的关键字比较次数和移动次数以取得直观感受。待排序表的表长不小于10，表中数据随机产生，至少用5组不同数据作比较，比较指标有：关键字参加比较次数和关键字的移动次数（关键字交换记为3次移动）。最后输出比较结果。2需求分析（1）用数组S来存放系统随机产生的10个数据，并放到R数组中，数据由

3、程序随机产生，用户只需查看结果。（2）利用全局变量times和changes来分别统计起泡排序、直接排序、简单选择排序、快速排序、希尔排序、堆排序算法的比较次数和移动次数，然后输出结果，并在每一次统计之后，将times和changes都赋值为0。（3）在主函数中调用用户自定义函数，输出比较结果。（4）本程序是对几种内部排序算法的关键字进行性能分析的程序，它分为以下几个部分：a、建立数组；b、调用函数求比较和移动次数；c、输出结果。3概要设计3．1抽象数据类型定义排序数据类型定义：ADTpaixu{数据对象：D={aij

4、aij属于{1，2，3…},i,j>

5、0}数据关系：R={

6、ai-1,ai∈D，i=2,...,n}基本操作：Insertsort();初始条件：数组已经存在。操作过程：将一个记录插入到已经排好序的有序列表中，从而得到了一个新的、记录新增1的有序表。Bubblesort();初始条件：数组已经存在。操作过程：两两比较待排序记录的键值，并交换不满足顺序要求的那些偶对，知道全部满足顺序要求为止。Shellsort();初始条件：数组已经存在。操作过程：先取定一个正整数d1

7、述分组和排序工作，直至取di=1,即所有记录放在一个组中排序为止。Selectsort();初始条件：数组已经存在。操作过程：每次从待排序的记录中选出键值最小（或最大）的记录，顺序放在已经排序的记录序列的最好，直到全部排完。Heap();初始条件：数组已经存在。操作过程：对一组待排序的的键值，首先是把它们按堆的定义排列成一个序列，这就找到了最小键值，然后把最小的键值取出，用剩下的键值再重建堆，便得到次小键值，如此反复进行，知道把全部键值排好序为止。QuickSort(intlow,inthigh)；初始条件：数组已经存在。操作过程：在待排序的n个记录中任取

8、一个记录，以该记录的键值为基准用交换的方法将所有记录分成两部分，所有键值比它小的放在一边，大的放另一边，并把该记录放在中间，然后重复至完成。}ADT排序3．2模块划分本程序包括两个模块：（1）主程序模块voidmain(){初始化；随机数的产生；调用子函数}；（2）子函数模块：实现各种排序的抽象数据类型。4详细设计4．1数据类型的定义(1)直接插入排序类型：voidInsertsort();(2)冒泡排序类型：voidBubblesort();(3)快速排序类型：voidQuickSort(intlow,inthigh);(4)希尔排序类型：voidShe

9、llsort();(5)选择排序类型：voidSelectsort();(6)堆排序类型：voidHeap();4．2主要模块的算法描述以下是源程序的流程图：图4.21图4.22ch2!=’0’ch2==’2’

10、

11、…YNNprintf(“t排序演示…Yprintf(“t请按回车…q!=’xA’getchar();ch1=’n’;YN图4.235测试分析6课程设计的总结与体会看到这个课程设计的题目的时候，我觉得很亲切。因为这个学期的第七章我们学了几种内部排序方法并进行了比较。对这几种算法的比较主要是通过其算法的时间复杂度以及其算法是否稳定。但是

12、我们所进行的比较主要是通过主观比较而并没有编写相应的算法。而此次课