2023年數(shù)據(jù)結構排序實驗報告

《數(shù)據(jù)結構》課程設計報告實驗五排序一、需求分析:本演示程序用C++6.0編寫，完畢各種排序的實現(xiàn)，對輸入的一組數(shù)字實現(xiàn)不同的排序方法，對其由小到大順序輸出。(1)分別對直接插入排序、希爾排序、冒泡排序、快速排序、選擇排序、堆排序算法進行編寫。(2)、對存儲的函數(shù)即輸入的數(shù)字進行遍歷。(3)、初始化函數(shù)對輸入的數(shù)字進行保存。(4)、主函數(shù)實現(xiàn)使用者操作界面的編寫，對輸入、選擇、保存、輸出的各種實現(xiàn)。這當中還涉及了各個函數(shù)的調用的實現(xiàn)。上：\最后的浜程沒計\口0協(xié)9\^序?、6-李喬李喬J^速擇頓選直希同展選生歡請1234567李喬李喬J^速擇頓選直希同展選生歡請1234567請輸入你需要的操作:0:0:■丫:\最后的深星設計■丫:\最后的深星設計\Debug0E序exe?456:::謝作作作7謝口架桑桑的如46然的陽46殂46的陽熬76弗要序3序8!要序3序6!要序3序8!選程需字2字5續(xù)需字2字7續(xù)需錄2錄5^^翁76數(shù)46繼沿76數(shù)58繼你記76記46繼操用入一刖8后3鍵入一刖8后6鍵入一刖8后3鍵入使普5序5序4=0^1^5序2二篇迎靠t12排t12任靠bL2排123隹靠BL2排bL2任請歡（3）各種排序的結果:凌卷入隹需要的操作：1堤岸前數(shù)字序列:1258762346排序后數(shù)字序列：1223465876任意鍵繼續(xù)!請輸入你需要的操作：2排序刖數(shù)子序列：1258762346排序后數(shù)字序列：1223465876任總鍵繼續(xù)！凌趣入徐霞整的操作:排序刖數(shù)子序列：1258762346排序后數(shù)字序列：5876762346鍵繼續(xù)I六、設計局限性以及存在問題本程序是基于C++6.0的實現(xiàn),其實在設計上的改善可以運用類進行操作,這種類的改善了存儲上的局限性還可以實現(xiàn)了，對各種的函數(shù)基于類的實現(xiàn)，這就是對本程序的改善,這是十分重要的與是改善的基礎。本程序出現(xiàn)過的問題是主函數(shù)對個函數(shù)的調用以及對存儲數(shù)組的調用上出現(xiàn)了問題，導致排序的結果以及排序的界面出現(xiàn)了問題,的不到實現(xiàn)。后來對算法進行改善，最終把問題得以解決。(5)、程序所能達成的功能：完畢對輸入的數(shù)字的生成，并通過對各排序的選擇實現(xiàn)數(shù)字從小到大的輸出。二、程序重要功能以及基本規(guī)定:(1)、設計一個菜單，格式如下：1、直接插入排序2、希爾排序3、冒泡排序4、快速排序5、選擇排序6、堆排序7、退出(2)、選擇不同的菜單但進行相應的排序，并給出排序的關鍵字序列。三、系統(tǒng)框架圖：本程序包含了9個函數(shù)，它們分別是：(1)、直接插入排序的算法函數(shù)InsertSort。。(2)、希爾排序的算法函數(shù)ShellS。rt()o主函數(shù)主函數(shù)各對輸操作個入的界面排數(shù)組的設序進行計,函算遍歷數(shù)的加拓調田一主函數(shù)(3)、冒泡排序算法函數(shù)BubbleSort()。主函數(shù)(4)、快速排序的算法函數(shù)Partition()。(5)、選擇排序算法函數(shù)SelectSort。。(6)、堆，序算法函數(shù)HeapAdjust()。(7)、對存儲數(shù)字的遍歷函數(shù)Visit()o(8)、初始化函數(shù)InitSqListOo(9)、主函數(shù)main()o四、具體設計實現(xiàn)各個算法的重要內容，下面是各個函數(shù)的重要信息：(1)各個排序函數(shù)的算法：一、直接插入排序voidInsertSort(SqList&L)(“nti,j;for(i=2；i<=L.length;i++){■if(L.r[i].key<L.r[i-1].key)00{。?L.r[0]=L.rfi];?0L.r[i]=L.r[i-1];dfor(j=i-2;(L.r[0].key<L.r[j].key)；j--)。。L.r[j+lJ=L.r[j]；aL.r[j+1]=L.r[0];do}))二、希爾排序voidShellSort(SqList&L)(inti,j;intdk=1;//增量while(dk<=L.1ength/3)。dk=3*dk+1;〃增大增量while(dk>0)(Mk/=3;〃減小增量ftf0r(i=dk;i<=L.length;i++)。(。?L.r[O].key=L.r[i].key;9=dwhi1e((j>=dk)&&(L.r[j-dk].key>L.r[0].key))(gdL.r[j].key=L.r[j-dk].key;j-=dk;)do?L.r[j].key=L.r[OJ.key;°}。})三、冒泡排序voidBubbleSort(SqList&L)(ainti,j;for(i=0;i<L.length-2;i++)(?intflag=1;for(j=O;j<L.Iength-i-2;j++)if(L.r[j].key>L.r[j+l].key)aoftf1ag=0;g?inttemp；，temp=L.r[j].key；gL.r[jj.key=L.rLj+l].key;?L.r[j+1].key=temp;do)。?！ㄈ魺o互換說明已有序gif(flag==1)?oobreak；?})四、快速排序intPartition(SqList&L,intlow,inthigh){〃分割區(qū)域函數(shù)L.r[0]=L.r[low]；intpivotkey=L.r[low].key；〃一般將順序表第一個元素作為支點while(1ow<high)?while(low<high&&L,r[high],key>=pivotkey)ghigh-?L.r[low]=L.r[high]；whi1e(1ow<high&&L,r[lowl，key<=pivotkey)g1ow++;L.r[high]=L.r[low];0}L.r[lowJ=L.r[OJ；〃返回樞軸位置returnlow;)voidQSort(SqList&L,intlow,inthigh)(〃每張子表的快速排序dif(low<high)(dintpivot1oc=Partition(L>low,high);ooQSort(L,low,pivotloc-1);?QSort(L,pivotloc+1,high);))voidQuickSort(SqList&L)(?QSort(L,l,L.1ength);)五、簡樸選擇排序voidSelectSort(SqList&L){intmin;intj；?for(inti=0;i<L.length；i++){//選擇第i小的記錄，并互換L.rfil.key；4min=for(intk=i;k<L.length;k++)L.rfil.key；{//在R[i..n?l]中選擇最小的記錄，if(L.r[kJ.key<min)。dmin=L.r[k].key;°叼=k;，}。}“f(i!=j)。{//與第i個記錄互換?inttemp=L.r[il.key;L.r[iJ.key=L.r[j].key;???L.r[j].key=temp;?)0})六、堆排序voidHeapAdjust(HeapTypes,intm)(。〃堆調整,將記錄調整為小頂堆intj;dRedTyperc=H.r[s1；〃暫時存儲根結點3for(j=2*s;j<=m;j*=2)?！ㄑ刂Y點記錄較小的向下篩選>if(j<m&&H.r[j].key<H.r[j+l].key)°0°++j；gif(rc.key>=H.r[jl.key)gobreak；H.r[s]=H.r[j]；s=j;)dH.r(s]=rc;}voidHeapSort(HeapType&H)(inti;edTypetemp;for(i=H.length;i>0；--i)HeapAdjust(H,i,H.Iength);for(i=H.length;i>l;-i)otemp=H.r[1];?H.r[1]=H.r[i]；?H.r[i]=temp;?HeapAdjust(H,1,i-1);))(2)遍歷函數(shù)與初始化voidVisit(SqListL)for(inti=l;i<=L.length;i++)cout?L.r[il.ke