1、 1 数据结构课程设计数据结构课程设计 题目：题目： 内部排序算法的比较内部排序算法的比较 2 实验报告实验报告 一、一、需求分析需求分析 1.1.本程序对以下六种常用的内部排序进行实测比较：起泡排序、直接插入本程序对以下六种常用的内部排序进行实测比较：起泡排序、直接插入 排序、简单选择排序、快速排序、希尔排序、堆排序。排序、简单选择排序、快速排序、希尔排序、堆排序。 2.2.待排序表的元素的关键字为整数，雍正徐、逆序和随机数产生器产生的待排序表的元素的关键字为整数，雍正徐、逆序和随机数产生器产生的 随机数做测试比较。比较的指标为有关键字参加的比较次数和关键字的移动次随机数做测试比较。比较的指
2、标为有关键字参加的比较次数和关键字的移动次 数（关键字交换记为数（关键字交换记为 3 3 次移动） 。次移动） 。 3.3.程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信 息”下，用户可由键盘输入产生随机数的种子息”下，用户可由键盘输入产生随机数的种子，计算机终端显示各内部排序的，计算机终端显示各内部排序的 比较参数。比较参数。 4.4.最终对结果做出简单分析，包括对各组数据得出结果波动大小给予解释。最终对结果做出简单分析，包括对各组数据得出结果波动大小给予解释。 二、概要设计二、概要设计 1.1.可排序表的抽象数据
3、类型定义：可排序表的抽象数据类型定义： ADT OrderableListADT OrderableList 数据对象：数据对象：D = aD = ai i |a|ai i IntegerSet,i = 1,2,IntegerSet,i = 1,2,n,n = 0,n,n = 0 数据关系：数据关系：R1 = |ai i- -1 1,a,ai i D.i = 2,D.i = 2,n,n 基本操作：基本操作： SelectListType(c)SelectListType(c) 操作结果：打印提示信息，请用户选择待排序表的类型，顺序操作结果：打印提示信息，请用户选择待排序表的类型，顺序型、型、
4、逆序型还是随机数组。逆序型还是随机数组。 BubbleSort( /typedef int KeyType; /定义关键字为整数类型定义关键字为整数类型 typedef int InfoType; /typedef int InfoType; /定义其他数据项也为整数类型定义其他数据项也为整数类型 int time_key_compare = 0; /int time_key_compare = 0; /定义全局变量，关键字比较定义全局变量，关键字比较次次 int time_key_move = 0; /int time_key_move = 0; /数和移动次数均为数和移动次数均为 0 0
5、typedef structtypedef struct KeyType key; /KeyType key; /关键字项关键字项 InfoType otherinfo; /InfoType otherinfo; /其他数据项其他数据项 RedType; /RedType; /记录类型记录类型 typedef structtypedef struct RedType rMAXSIZE + 1; /r0RedType rMAXSIZE + 1; /r0闲置或用做哨兵闲置或用做哨兵 intint length; /length; /顺序表长度顺序表长度 SqList; /SqList; /顺序表类型顺序表类型 /*/*基本操作基本操作* bool LT(KeyType a,KeyType b)/bool LT(KeyType a,KeyType b)/比较两个比较两个 KeyTypeKeyType 类型变量的大小类型变量的大小 time_key_compare +;
