北理工数据结构实验报告4

1、数据结构与算法统计实验报告实验四学院:班级:学号:姓名:、实验目的1、熟悉VC环境，学会使用 C语言利用顺序表解决实际问题。2、通过上机、编程调试，加强对线性表的理解和运用的能力。3、锻炼动手编程，独立思考的能力。二、实验内容从键盘输入10个数，编程实现分别用插入排序、交换排序、选择排序算法进行排序, 输出排序后的序列。三、程序设计1 、概要设计为了实现排序的功能，需要将输入的数字放入线性表中，进行进一步的排序操作。 (1)抽象数据类型：ADT SqList数据对象：d= ai |ai ElemSet,i1,2,K,n, n 0数据关系：R1= ai 1,aiD,i1,2,K ,n基本操作：I

2、nput(Sqlist & L)操作结果：构造一个线性表L。output(SqList L)初始条件：线性表 L已存在。操作结果：按顺序在屏幕上输出L的数据元素。BiI nsertio nsort (Sqlist L)初始条件：线性表 L已存在。操作结果：对L的数据元素进行折半插入排序。Quicksort (Sqlist L)初始条件：线性表 L已存在。操作结果：对L的数据元素进行交换排序。SelectSort(SqList &L)初始条件：线性表 L已存在。操作结果：对L的数据元素进行选择排序。ADT SqList宏定义#defi ne KeyType int#define

3、MAXSIZE 10#define ok 1#defi ne error 0主程序流程由主程序首先调用In put(L)函数创建顺序表，先调用BiInsertionsort(L)函数进行折半插入排序，调用output(L)函数显示排序结果。再调用QuickSort (L)函数进行交换排序，调用output (L)函数显示排序结果。函数显示排序结果。最后调用SelectSort(L)函数进行选择排序，调用output(L)模块调用关系由主函数模块调用创建顺序表模块，排序模块与显示输出模块。(5)流程图开始输入待排数字创建线性表进行插入排序输出排序结果进行交换排序输出排序结果进行选择排序输出排序结

4、果结束2、详细设计(1)数据类型设计/*顺序存储结构*/typedef structKeyType Key; / 关键字项 RedType;typedef structRedType rMAXSIZE+1;int len gth;/ =MAXSIZE; Sqlist;/(2)操作算法设计/*输入数据*/int In put(Sqlist & L)for(int i=1;i<=MAXSIZE;i+)sea nf("%d",&L.ri.Key);L.le ngth=MAXSIZE;return ok;/*输出排好的数字*/in t output(Sqlis

5、t L)for(i nt i=1;i<=MAXSIZE;i+)prin tf("%-4d",L.ri.Key);prin tf("n ”); return ok;/*折半插入排序法*/void BiI nserti on sort (Sqlist L)int i,j,low,high,m; for(i=2;i<=Len gth;i+)L.rO.Key=L.ri.Key; / low=1; high=i-1;while(low<=high) / m=(low+high)/2; if(L.rO.Key<L.rm.Key) else low=m+

6、1; for(j=i-1;j>=high+1;j-) /.rj+1=L.rj;L.rhigh+1=L.rO; II /lowprintf("折半插入排序:n");output(L);定义顺序表类型把要插入的当成哨兵 折半法找到要插入的位置high=m-1;插入位置后的袁术后移一位插入元素/BiI nserti on sort/*快速交换排序法*/int Partition(Sqlist &L,int low,int high)int pivotkey;L.r0.Key=L.rlow.Key; /用子表的第一个记录作枢轴记录pivotkey=L.rlow.Key

7、; /枢轴记录关键字while(low<high) / 从表的两端交替地向中间扫描while(low<high&&L.rhigh.Key>=pivotkey)-high;/ 将比枢轴记录小的记录移到低端/whileL.rlow.Key=L.rhigh.Key; while(low<high&&L.rlow.Key<=pivotkey) +low;将比枢轴记录大的记录移到高端/whileL.rhigh.Key=L.rlow.Key;/whileL.rlow.Key=L.r0.Key;枢轴记录到位return low;/返回枢轴位置/P

8、artiti onvoid QSort(Sqlist & L,i nt low,i nt high)int pivotloc;if(low<high)/长度大于 1pivotloc=Partition(L,low,high);将 L.rlow highQSort(L,low,pivotloc-1);/QSort(L,pivotloc+1,high);/ /if/QSortvoid QuickSort(Sqlist &L)/QSort(L,1,L.le ngth); printf("交换排序:n”); output(L);/QuickSort/*选择排序法*/vo

9、id SelectSort(Sqlist L)对低子表递归排序，pivotloc 对高子表递归排序对顺序表L做快速排序分为二是枢轴位置for(i=1;i<=Len gth;i+) k=i;/要确定排序元素的位置for(j=i+1;j<=Len gth;j+)if(L.rk.Key>L.rj.Key) k=j; /temp=L.ri.Key; 输出线性表 L L.ri.Key=L.rk.Key;L.rk.Key=temp;/forprintf("选择排序:n”);output(L);/SelectSort若后面有更小的记录下其位置主函数设计int mai n()Sql

10、ist L;In put(L);/BiI nserti on sort(L); /BubbleSort(L); /输入要排的数字，创建线性表L对L进行插入排序，输出线性表L 对L进行交换排序，输出线性表LSelectSort(L); /对L进行选择排序，输出线性表Lreturn ok;四、程序调试分析1 、由于本次实验中存储数据的线性表是在In put函数中进行的，所以开始时忘了将l.length 初始化，出现报错，开始我直接在定义线性表的结构中赋值为MAXSIZE还是有问题，原来是定义结构时不能直接在内部赋初值！通过这次错误让我对数组的用法有了一个更 深的了解，实践后记得更深。2、对于快速排

11、序一直都不太理解，编译时出现了各种报错提示，后来我又回头仔仔细细的看了书上的内容， 重新理解快排的算法思想，先设置枢轴，进行一趟简单的分大小， 再进行递归调用，直到排序结束，重新写了一遍程序，调试了几次就成功了，对于快排有了一个 较深的把握与理解。3、一直对于快排的交换环节存有疑虑，当出现第一个比枢轴小的关键字时就进行这句L.rlow.Key=L.rhigh.Key;原以为这样后low空间里的关键字被换成了 high的了，那low里的关键字就缺失了，但是调试却没有问题，经过单步运行后，发现原来low里的为枢轴量，放在了首单元地址里，后来又换回来了，所以没有缺失。4、在选择排序中，刚开始我的程序

12、是比较后就直接交换的，后来看书上是记住数组的下标全部比较后进行一次交换就可以了，少了不少的交换次数，效率提高了不少，让我看到了优化程序的重要性，在实现的基础上不断地去优化程序，让程序变得更好。五、用户使用说明1、本程序的运行环境为DOS操作系统，执行文件为：排序.exe。2、进入程序后，输入所需排序的十个整数，回车运行程序。3、程序运行后即在屏幕上输出计算结果。六、程序运行结果叵 *D：Program Files (x86)Vni<rosoft visual c+ + MSDc-v98MyProjcct1cpp4 1010073473 4475773344757733447577395

13、10096 1009S 10012 34 57 99 21折半插入排序:41012 Z1交换排序，1 IQ 1221孫择舟£序=41012 Z1Press anyto conti_n ue'D:Pragram File (xfiSmicnQSQFt visual c+MSDev5SMyProj21 3 34 1 54 3 67 54 10U 45 卅半插入排序二133213445545467100交按排序：1332124455454诜择排序：13321344554546?1QQFress on岁 k&y to continue七、程序清单#i nclude"

14、stdio.h"/*宏定义*/#defi ne KeyType int#defi ne MAXSIZE 10#defi ne ok 1#defi ne error 0 /*顺序存储结构*/typedef structKeyType Key; RedType;typedef structRedType rMAXSIZE+1;in t le ngth;/ =MAXSIZE; Sqlist;/*输入数据*/in tin put(Sqlist & L)for(int i=1;i<=MAXSIZE;i+)scan f("%d",&L.ri.Key);L

15、.le ngth=MAXSIZE;return ok;/*输出排好的数字*/in t output(Sqlist L)for(int i=1;i<=MAXSIZE;i+)prin tf("%-4d",L.ri.Key);prin tf("n");return ok;/*折半插入排序法*/void Bii nserti on sort (Sqlist L)int i,j,low,high,m;for(i=2;i<=Len gth;i+)L.rO.Key=L.ri.Key; /把要插入的当成哨兵low=1; high=i-1;while(low&

16、lt;=high)II折半法找到要插入的位置m=(low+high)I2;if(L.rO.Key<L.rm.Key) high=m-1;else low=m+1;for(j=i-1;j>=high+1;j-) II插入位置后的袁术后移一位L.rj+1=L.rj;L.rhigh+1=L.rO; II插入元素IIlowprintf("折半插入排序:n");output(L);IIBii nserti on sortI*快速交换排序法*Iint Partition(Sqlist &L,int low,int high)int pivotkey;L.r0.Key

17、=L.rlow.Key;用子表的第一个记录作枢轴记录pivotkey=L.rlow.Key;枢轴记录关键字while(low<high)从表的两端交替地向中间扫描while(low<high&&L.rhigh.Key>=pivotkey)-high;/将比枢轴记录小的记录移到低端/whileL.rlow.Key=L.rhigh.Key;while(low<high&&L.rlow.Key<=pivotkey)+low;将比枢轴记录大的记录移到高端/whileL.rhigh.Key=L.rlow.Key;/whileL.rlow.Ke

18、y=L.r0.Key;枢轴记录到位return low;/ 返回枢轴位置/Partitio n void QSort(Sqlist &L,int low,int high) int pivotloc;if(low<high)/长度大于 1分为二是枢轴位置pivotloc=Partitio n(L,low,high);QSort(L,low,pivotloc-1);QSort(L,pivotloc+1,high);将 L.rlow high-对低子表递归排序，pivotloc 对高子表递归排序对顺序表L做快速排序要确定排序元素的位置/if/QSortvoid QuickSort(Sqlist &L)/QSort(L,1, L.le ngth); printf("交换排序:n");output(L);/QuickSort/*选择排序法*/void SelectSort(Sqlist L)int i,j,k,temp;for(i