数据结构课程设计--内部排序算法的比较

《数据结构课程设计--内部排序算法的比较》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、数据结构课程设计　　　　　　　　　　　　中国海洋大学　　　　　　　数据结构课程设计　　　　　　　　　题目：　　内部排序算法的比较　　　　　　　姓名：　　李吉倩　　　　　　　学号：　　020332010046　　　　　　　系年级：　计算机科学与技术2010级　　　　　　　完成时间：2012.8-2012.910　　　　　　　　　　　　　　　　　　　数据结构课程设计　　　　　　　　　　　　中国海洋大学　　　　　　　实验报告　　一、需求分析1.本程序对以下六种常用的内部排序进行实测比较：起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。2.待排序表的元素的

2、关键字为整数，雍正徐、逆序和随机数产生器产生的随机数做测试比较。比较的指标为有关键字参加的比较次数和关键字的移动次数（关键字交换记为3次移动）。3.程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”下，用户可由键盘输入产生随机数的种子，计算机终端显示各内部排序的比较参数。4.最终对结果做出简单分析，包括对各组数据得出结果波动大小给予解释。二、概要设计1.可排序表的抽象数据类型定义：ADTOrderableList{　　数据对象：D={ai

3、ai∈IntegerSet,i=1,2,……,n,n>=0}　　数据关系：R1={

4、ai-1,

5、ai∈D.i=2,……,n}　　基本操作：　　　SelectListType(c)　　　操作结果：打印提示信息，请用户选择待排序表的类型，顺序型、逆序型还是随机数组。　　　BubbleSort(&L)　　　操作结果：进行起泡排序，返回排序后的顺序表　　　InsertSort(&L)　　　操作结果：进行插入排序，返回排序后的顺序表　　　SelectSort(&L)　　　操作结果：进行选择排序，返回排序后的顺序表　　　QuickSort(&L)　　　操作结果：进行快速排序，返回排序后的顺序表　　　ShellSort(&L)　　　操作结果：进行希尔排序，返回排序后的顺序表

6、　　　HeapSort(&L)　　　操作结果：进行堆排序，返回排序后的顺序表　　　SelectSortMethod(&L,c1)　　　操作结果：打印提示信息，请用户选择排序方法，起泡排序、插入　　　　　　　　排序、选择排序、快速排序、希尔排序还是堆排序OutPut(L)　　　操作结果：打印排序中关键字的比较次数和移动次数}ADTOrderableList2.本程序包含两个模块：　1）.主程序模块10　　　　　　　　　　　　　　　　　　　数据结构课程设计　　　　　　　　　　　　中国海洋大学　　　　　　　　intmian()　{　　　　初始化；用户选择待测表的类型；输入

7、选择，用switch语句判断；While（“命令”！=“退出”）{接受命令；处理命令；}　}　２）．可排序表单元模块----实现可排序表的抽象数据类型各模块之间的调用关系：主程序模块可排序表单元模块三、详细设计1.根据题目要求何可排序表的基本操作特点，可排序表采用证书顺序表存储结构，并实现在头文件SqList.H。//******************基本操作的函数原型******************\#defineMAXSIZE20//用作示例的顺序表的最大长度typedefintKeyType;//定义关键字为整数类型typedefintInfoType

8、;//定义其他数据项也为整数类型inttime_key_compare=0;//定义全局变量，关键字比较次inttime_key_move=0;//数和移动次数均为0typedefstruct{KeyTypekey;//关键字项InfoTypeotherinfo;//其他数据项}RedType;//记录类型typedefstruct{RedTyper[MAXSIZE+1];//r[0]闲置或用做哨兵intlength;//顺序表长度}SqList;//顺序表类型//****************************基本操作*******************

9、**\boolLT(KeyTypea,KeyTypeb)//比较两个KeyType类型变量的大小{time_key_compare++;//比较次数+1if(a