2023年数据结构排序实验报告.pdf

《2023年数据结构排序实验报告.pdf》由会员分享，可在线阅读，更多相关《2023年数据结构排序实验报告.pdf（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、接插入排序2、希尔排序3、冒泡排序4、快速排序5、选择排序6、堆排序7,退出(2)、选择不同的菜单但进行相应的排序，并给出排序的关键字序列。三、系统框架图:本程序包含了 9 个函数，它们分别是:(1)、直接插入排序的算法函数InsertSort()。(2)、希尔排序的算法函数ShellS or t()(3)、冒泡排序算法函数B u bbleSo r t().(4)、快速排序的算法函数Partition(5)、选择排序算法函数Sele c tSort()o(6)、堆排序算法函数H eapAdjust O。(7)、对存储数字的遍历函数Vis i t()。(8)、初始化函数 In i t S q L

3、 i st。(9)、主函数ma i n()。主函数各对输操作个入的界面排数组的设序进行计,函算遍历数的却诵 田.四、具体设计实现各个算法的重要内容，下面是各个函数的重要信息：(1)各个排序函数的算法：一、直接插入排序v oid I n sertS o rt(SqL ist&L)(in t i,j;f o r(i=2；i=L.leng t h;i+)o i f(L.r i.key L.r i-1.key)g(0 L.r0=L.r i ;aL.ri=L.ri-1;6 f or(j=i-2;(L.r E 0.ke y L.r j.k ey)；。，L.rj+1=L.rj；a L.r j+1=L.r 0

4、;00 j)二、希尔排序void ShcllS o rt(SqLis t&L)nt i,j;int d k=1;/增量w h il e(dk 0)(dk/-3;/减小增量f o r(i=dk;i=dk)&(L.r.j-dk.k ey L.r 0.key)(L.r j .key=L.r j-dk.key;j=dk;)L.rj.k e y=L.r OJ.key;4)三、冒泡排序v oid B u bbleSo r t(Sq Li s t&L)(int i,j;for(i=0;iL.length-2；i+)in t flag=1;f or(j=O;j L.r|j+l.k ey)dftdf 1 ag=

5、0;g nnt temp；，temp=L.r j,k e y；g L.r j.key=L.rj+l.k e y;。L.rj+1.key=temp;g”若无互换说明已有序g i f(f lag=1)，g b reak；0)四、快速排序in t Pa r ti t ion(S Q List&L,in t low9int hi g h)(分割区域函数L.r0=L.r low；int pi v ot k e y=L.r low.key；一般将顺序表第一个元素作为支点w h il e(1 o w high)。whil e(low=p i v ot k ey)g high-;，L.rIow=L.rhigh

6、；w h i 1 e(1 owhigh&L.r low.key=p i votk e y)Mow+;L.r high=L.r low;L.rlow=L.r 0；返回枢轴位置re t u rn low;)void QS o r t(Sq L is t&L,i n t low,i n t high)(每张子表的快速排序di f(lowh i g h)(“n t pivot 1 o c=Partition(L,low,high);gQ S ort(L,l o w,p i v otloc-1);。Q Sort(L,pivo t lo c+1,h igh);vo i d QuickSo r t(S q

7、L ist&L)(dQSort(L,l,L.1 e ngth);五、简朴选择排序v oid S e le c tSo r t(S qList&L)(int mi n;int j；o f or(int i=0;i L.len g th；i+)/选择第i 小的记录，并互换，j=i；，m i n=L.ri.k e y；f or(in t k=i;k L.l e ngth;k+)/在 Ri.n l 中选择最小的记录，i f(L.rk.ke y m i n)dd(m in =L.r k.ke y;j=k;8)，if(i!=j)，/与 第 i 个记录互换 int temp=L.ri.k e y;L.ri.

8、key=L.rj.key;L.rj.ke y=temp;8 1)六、堆排序vo i d Hea p Adjust(H e apTyp e&H,int s,in t i。堆调整,将记录调整为小顶堆i ntj;aR ed T yp erc=H.r s；暂时存储根结点 f or(j=2*s;j=m;j*=2)”/沿着结点记录较小的向下筛选“f(j m&H.r j.k e y=H.r j.ke y)a。b r e a k；H.r s=H.r j;s=j；H.r s =r c;void Hea p S o rt(HeapType&H)(in t i;e d Type t e mp;fo r(i=H.le

9、ngt h;i 0；-i)He a pAdju s t(H,i,H.leng t h);f or(i=H.leng t h;il;i)do temp=H.r 1;H.r 1=H.r i；H.r i=t e mp;o He a pAd j us t(H 1 i-1);)(2)遍历函数与初始化v o i d Vi s i t(SqL i st L)for(in t i=l;i=L.leng t h;i+)cout L.ri.keyn ；dcoute n dl;)void InitS q List(SqLis t&L,in t a)(f o r(int i=l;i=L.len g t h;i+)L.

10、r i.ke y=a i；五、测试结果以下是各种界面的测试结果：，E:最后的俣程设计DebugBE序 exe界作操序2863615724数数数数?12345入入人入入入一即育主QE-fH月主DE主月主DE.ILL.(1)输 入 的 界 面：(2)-*E:最后的课程设计 D e b u g网 序.e xe”界陵妤序定序序*库乔述卜二:二二；非月人丰丰本丰非速择虬选直希闫展选用、犬生0-欢干1234567*请输入你需要的操作:面:作操的!要I继你键入8F序后数字序列意键继续!输 入 你 需 要 的 操 作上序后记录序列:（3）各种排序的结果:A序33I2AL2L刖8一后3键入一刖8岸5序2=05般2非12住靠123键入前8后6205序7，E:最后的课程设计 D e b u g E序.e xe”作操：,的列46列76作操：的列46列463序8!要序3序8!要序2字S续需字2字5续需字六、设计局限性以及存在问题本程序是基于C+6.0 的实现,其实在设计上的改善可以运用类进行操作,这种类的改善了存储上的局限性还可以实现了，对各种的函数基于类的实现，这就是对本程序的改善,这是十分重要的与是改善的基础。本程序出现过的问题是主函数对个函数的调用以及对存储数组的调用上出现了问题，导致排序的结果以及排序的界面出现了问题,的不到实现。后来对算法进行改善，最终把问题得以解决。