数据结构排序实验报告.docx

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

2、1）、设计一个菜单，格式如下：1、直接插入排序2、希尔排序3、冒泡排序4、快速排序5、选择排序6、堆排序 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 ShellSort(SqList &L) int i, j; int dk = 1;/增量 while(dk 0) dk /= 3;/减小增量 for (i = dk

3、; i = dk) & (L.rj-dk.key L.r0.key) L.rj.key = L.rj-dk.key; j -= 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; temp = L.rj.key; L.rj.key = L.rj+1.key; L.rj+1.key = temp; /若无交换说明已经有序 if(flag=1) break;

4、四、快速排序int Partition(SqList &L,int low,int high) /分割区域函数 L.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.rhigh = L.rlow; L.rlow = L.r0;/返回枢轴位置 return low;void QSort(SqList &L,int low,in

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

6、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*=2) /沿着结点记录较小的向下筛选 if(jm &

7、 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,1,i-1); （2）遍历函数与初始化void Visit(SqList L) for(int i=1; i=L.length; i

8、+) coutL.ri.key ; coutendl;void InitSqList(SqList &L,int a) for(int i=1;i=L.length;i+) L.ri.key = ai;五、测试结果以下是各种界面的测试结果：（1）输入的界面 :（2）排序操作界面：（3）各种排序的结果： 六、设计不足以及存在问题本程序是基于C+6.0的实现，其实在设计上的改进可以利用类进行操作，这种类的改进了存储上的不足还可以实现了，对各种的函数基于类的实现，这就是对本程序的改进，这是十分重要的与是改进的基础。本程序出现过的问题是主函数对个函数的调用以及对存储数组的调用上出现了问题，导致排序的结果以及排序的界面出现了问题，的不到实现。后来对算法进行改进，最终把问题得以解决。