完整版数据结构排序试验报告文档良心出品

1、?数据结构?课程设计报告实验五排序一、需求分析：本演示程序用 C+6.0编写,完成各种排序的实现,对输入的一组数字实现不同的排序 方法,对其由小到大顺序输出.(1)分别对直接插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序算法 进行编写.(2)、对存储的函数即输入的数字进行遍历.(3)、初始化函数对输入的数字进行保存.(4)、主函数实现使用者操作界面的编写,对输入、选择、保存、输出的各种实现.这当中还包括了各个函数的调用的实现.(5)、程序所能到达的功能：完成对输入的数字的生成,并通过对各排序的选择实现数字从小到大的输出.二、程序主要功能以及根本要求：(1)、设计一个菜单,格式如下：1

2、、直接插入排序2、希尔排序3、冒泡排序4、快速排序5、选择排序6、堆排序7、退出(2)、选择不同的菜单但进行相应的排序,并给出排序的关键字序列.三、系统框架图：本程序包含了 9个函数,它们分别是：(1)、直接插入排序的算法函数InsertSort ().主函数各对输操作个入的界面排数组的设序进行计,函算遍历数的法初始调用.函 数化(2)、希尔排序的算法函数ShellSort ().(3)、冒泡排序算法函数 BubbleSort ().(4)、快速排序的算法函数Partition ().(5)、选择排序算法函数 SelectSort ().(6)、堆排序算法函数 HeapAdjust ().(7

3、)、对存储数字的遍历函数Visit ().(8)、初始化函数 InitSqList ().(9)、主函数 main ().四、详细设计实现各个算法的主要内容,下面是各个函数的主要信息:(1)各个排序函数的算法：一、直接插入排序void InsertSort(SqList &L)(int i,j;for( i=2; i<=L.length;i+)(if(L.ri.key < L.ri-1.key)(L.r0 = L.ri;L.ri = L.ri-1;for( j=i-2; (L.r0.key < L.rj.key); j-)L.rj+1 = L.rj;L.rj+1 =

4、L.r0;二、希尔排序void ShellSort(SqList &L)(int i, j;int dk = 1;/ 增量while(dk <=L.length/3)dk = 3*dk+1;/增大增量while(dk>0)(dk /= 3;/减小增量for (i = dk; i <=L.length; i+)(L.r0.key = L.ri.key;j = i;while (j >= dk) && (L.rj-dk.key > L.r0.key) (L.rj.key = L.rj-dk.key;j -= dk;)L.rj.key = L.r

5、0.key;)三、冒泡排序void BubbleSort(SqList &L)(int i,j;for(i=0;i<L.length-2;i+)(int flag = 1;for(j=0;j<L.length-i-2;j+)if(L.rj.key > L.rj+1.key)(flag = 0;int temp;temp = L.rj.key;L.rj.key = L.rj+1.key;L.rj+1.key = temp;)假设无交换说明已经有序if(flag=1)break;)四、快速排序int Partition(SqList &L,int low,int

6、high)(/分割区域函数L.r0 = L.rlow;int pivotkey = L.rlow.key;/ 一般将顺序表第一个元素作为支点 while(low < high)(while(low<high && L.rhigh.key>=pivotkey)high-;L.rlow = L.rhigh;while(low<high && L.rlow.key<=pivotkey)low+;L.rhigh = L.rlow;)L.rlow = L.r0;/返回枢轴位置return low;)void QSort(SqList &

7、;L,int low,int high)(/每张子表的快速排序if(low<high)(int pivotloc = Partition(L,low,high);QSort(L,low,pivotloc-1);QSort(L,pivotloc+1,high);)void QuickSort(SqList &L)QSort(L,1,L.length);)五、简单项选择择排序void SelectSort(SqList &L)(int min;int j;for (int i = 0; i <L.length; i+)/选择第i小的记录,并交换j = i;min = L

8、.ri.key;for (int k = i; k < L.length; k+)/在Ri.n-1中选择最小的记录if (L.rk.key < min)min = L.rk.key ;j = k;)if (i != j) 与第i个记录交换int temp = L.ri.key;L.ri.key = L.rj.key;L.rj.key = temp;)六、堆排序void HeapAdjust(HeapType &H,int s,int m)堆调整,将记录调整为小顶堆int j;RedType rc = H.rs;/暂时存储根结点 for(j=2*s; j<=m; j*=

9、2)(/沿着结点记录较小的向下筛选if(j<m && H.rj.key<H.rj+1.key) +j;if(rc.key>= H.rj.key) break;H.rs = H.rj;s = j;H.rs = rc;void HeapSort(HeapType &H)(int i;RedType temp;for(i = H.length; i>0; -i)HeapAdjust(H,i,H.length);for(i=H.length; i>1; -i)(temp = H.r1;H.r1 = H.ri;H.ri = temp;HeapAdju

10、st(H,1,i-1);(2)遍历函数与初始化void Visit(SqList L)(for(int i=1; i<=L.length; i+)cout<<L.ri.key<<""cout<<endl;)void InitSqList(SqList &L,int a口)(for(int i=1;i<=L.length;i+)L.ri.key = ai;)五、测试结果以下是各种界面的测试结果：任:最后的:凑程设计 De b u 口以E序exu'(1)输入的界面一照那么史照刖也弓knrJ'KnB 酉glT

11、?亭竽庠舁人人入人入入2 8 6 315 7 2面 界 作 操 序 三 ' E：羁峰程倒nDebugGE序点xH序二|E L: L; iH 二.速择 晚选真希日展选蓑 一 * | , , 12 3 4 5 6 7请输入你需要的操作(3)各种排序的结果:非序后数字序列攵字序列' E 最后的侯亨设讨Dc b ugaE序e xe ,非序前数字序列：.2 58 76 23 46序后数字序列工.2 23 46 S8 76一意键继续！领A你需要的操侣2 二洋箭数字序司：.2 58 76 23 46*序后数字序列;.2 23 46 58 76:意键继续！输入你籥要取操作：3 列 46F序后数字序列 46,2 23 46 58 76一意键维续就疆即512 58 76 23 46排序后数字序列：23 46 SB 76 46任意键继续！醯密置鬻操作,6排序刖记录序列：12 58 76 23 46排序后记录序列：l2 23 46 58 76六、设计缺乏以及存在问题本