数据结构排序试验报告

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

2、、直接插入排序2、希尔排序3、冒泡排序4、快速排序5、选择排序6、堆排序7、退出(2)、选择不同的菜单但进行相应的排序，并给出排序的关键字序列。三、系统框架图：本程序包含了9个函数，它们分别是：(1)、直接插入排序的算法函数InsertSort()。(2)、希尔排序的算法函数ShellSort ()。(3)、冒泡排序算法函数BubbleSort ()。(4)、快速排序的算法函数Partition()。(5)、选择排序算法函数SelectSort()。(6)、堆排序算法函数HeapAdjust ()。(7)、对存储数字的遍历函数Visit ()。(8)、初始化函数InitSqList()。(9)

3、、主函数main ()。四、详细设计实现各个算法的主要内容，下面是各个函数的主要信息：(1)各个排序函数的算法：主函数各个排序算法函 数对输 入的数组 进行遍历 初始化操作 界面的设 计，函数 的调用。3一、直接插入排序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 = L.r0;二、希尔排序void S

4、hellSort(SqList &L)(int i, j;int dk = 1;/增量while(dk 0)(dk /= 3;/减小增量for (i = dk; i = dk) & (L.rj-dk.key L.r0.key) (L.rj.key = L.rj-dk.key;4j -= dk;L.rj.key = L.r0.key;三、冒泡排序void BubbleSort(SqList &L)(int i,j;for(i=0;iL.length-2;i+)(int flag = 1;for(j=0;j L.rj+1.key)(flag = 0;int temp;tem

5、p = 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 high)(分割区域函数5L.r0 = L.rlow;int pivotkey = L.rlow.key;/一般将顺序表第一个元素作为支点while(low high)(while(low=pivotkey)high-;L.rlow = L.rhigh;while(lowhigh & L.rlow.key=pivotkey)low+;L.r

6、high = L.rlow;L.rlow = L.r0;/返回枢轴位置return low;void QSort(SqList &L,int low,int high)(每张子表的快速排序if(lowhigh)(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;6int j;

7、for (int i = 0; i L.length; i+)(/选择第i小的记录，并交换j = i;min = L.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;Re

8、dType rc = H.rs;/暂时存储根结点for(j=2*s; j=m; j*=2)(/沿着结点记录较小的向下筛选if(jm & H.rj.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; i0; -i)HeapAdjust(H,i,H.length);for(i=H.length; i1; -i) (temp = H.r1;H.r1 = H.ri;H.ri = temp;HeapAdjust(H,

9、1,i-1);8(2)遍历函数与初始化void Visit(SqList L)(for(int i=1; i=L.length; i+)coutL.ri.key;coutendl;void InitSqList(SqList &L,int a)(for(int i=1;i=L.length;i+)L.ri.key = ai;五、测试结果以下是各种界面的测试结果：最后的深睡没De b u. exe (1)输入的界面面界作操序三E.lzJrJE.lzJrJglr?glr?八入人入入入HiHiRn.Rn. - -HHn/HHn/ nHMNnHMN .-.- UHUH . . J JRn.-R

10、n.- DHDH有主照主启青者青9请输入你需要的操作,六、设计不足以及存在问题脸选真希日晨选疆_ _la!llla!ll llalBIllalBI1212 3 3 4 4 5 5 6 6 7 7(3)各种排序的结果:非序后数字序列I芾r黄就字序列E ： 1易后的深写没t+De b ugk啡字e非序前数字序列：.2 58 76 23 46序后数字序列:.2 23 46 S8 76二意键继续！需要的操作，2.谯前教字序列:.2 58 76 23 46非序后数字序列，.2 23 46 58 76二意键继续！输入你籥要如操作：3,2 23 46 58 76通键继续！ 福嬲操怕5nr M J* V W 5J ，J / J12 58 7& 23 46排序后数字序列：23 46 S8 76 46任尊键继续！ 融巍疆操怕6排序刖记录序列：12 58 76 23 46排序后记录序列：-2 23 46 56 7610本程序是基于C+6.0的实现，其