《2023年数据结构排序实验报告.docx》由会员分享，可在线阅读，更多相关《2023年数据结构排序实验报告.docx（10页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构课程设计报告实验五排序一、需求分析:本演示程序用C+ 6 .0编写，完毕各种排序的实现，对输入的一组数字实现不同的排序方法，对其由小到大顺序输出。(1 )分别对直接插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序算法 进行编写。(2 )、对存储的函数即输入的数字进行遍历。(3)、初始化函数对输入的数字进行保存。(4)、主函数实现使用者操作界面的编写，对输入、选择、保存、输出的各种实现。这当中还涉及了各个函数的调用的实现。上：最后的浜程没计口0协9序、6-李乔J速择 顿选直希同展选生 欢请1234567李乔J速择 顿选直希同展选生 欢请1234567请输入你需要的操作:0: 丫:
2、最后的深星设计Debug0E序exe4 5 6: : : 谢 作 作 作 7谢 口架 桑 桑的如46然的阳46殂46的阳熬76弗 要序3序8!要序3序6!要序3序8!选程 需字2字5续需字2字7续需录2录5 翁76数46继沿76数58继你记76记46继操用 入一刖8后3键入一刖8后6键入一刖8后3键入使 普5序5序4=01 5序2二篇迎 靠t12排t12任靠bL2排123隹靠BL2排bL2任请欢（3）各种排序的结果:凌卷入隹需要的操作：1 堤岸前数字序列:12 58 76 23 46排序后数字序列：12 23 46 58 76任意键继续!请输入你需要的操作：2 排序刖数子序列：12 58 76
3、 23 46排序后数字序列：12 23 46 58 76任总键继续！凌趣入徐霞整的操作: 排序刖数子序列：12 58 76 23 46排序后数字序列：58 76 76 23 46键继续I六、设计局限性以及存在问题本程序是基于C+6.0的实现,其实在设计上的改善可以运用类进行操作,这种类的改 善了存储上的局限性还可以实现了，对各种的函数基于类的实现，这就是对本程序的改善, 这是十分重要的与是改善的基础。本程序出现过的问题是主函数对个函数的调用以及对存储数组的调用上出现了问题， 导致排序的结果以及排序的界面出现了问题,的不到实现。后来对算法进行改善，最终把问 题得以解决。(5)、程序所能达成的功能
4、：完毕对输入的数字的生成，并通过对各排序的选择实现数字从小到大的输出。二、程序重要功能以及基本规定:(1)、设计一个菜单，格式如下：1、直接插入排序2、希尔排序3、冒泡排序4、快速排序5、选择排序6、堆排序7、退出(2)、选择不同的菜单但进行相应的排序，并给出排序的关键字序列。三、系统框架图：本程序包含了 9个函数，它们分别是： (1)、直接插入排序的算法函数InsertSort。(2)、希尔排序的算法函数ShellS。r t ()o主函数各对输操作个入的界面排数组的设序进行计,函算遍历数的加拓调田一主函数(3)、冒泡排序算法函数B u bbleSo r t ()。(4)、快速排序的算法函数P
5、artition ()。(5)、选择排序算法函数SelectSort。(6)、堆，序算法函数H e apAdjust ()。(7)、对存储数字的遍历函数Vis i t ()o (8)、初始化函数 Ini t S qListOo(9 )、主函数ma i n()o四、具体设计实现各个算法的重要内容，下面是各个函数的重要信息：(1)各个排序函数的算法：一、直接插入排序v oid I n sertS o rt (Sq List &L)(“n t i, j;f o r ( i =2；i=L. leng t h;i+) i f(L. ri .key L. r i -1 .key)00 。L.r0 =L.
6、rf i ;0L.ri = L. ri-1 ;d f or( j=i-2; (L. r 0 . ke y L.r j. ke y )；j-)。 L.rj+lJ = L. rj；a L. r j+1 = L.r 0;do)二、希尔排序void ShellS o rt (SqLis t &L)(int i , j;int d k = 1 ; / / 增量w h il e (dk 0)(Mk / = 3;减小增量ftf 0 r (i = dk; i = dk) & (L.rj-dk. k ey L .r 0 . key) (g dL. r j .ke y = L. r j-dk .key;j -=
7、dk;)doL.rj.k e y = L. r OJ.key; 。)三、冒泡排序void BubbleSo r t (SqLis t &L)(aint i, j ;for(i= 0 ;iL.length- 2 ;i+ + )(in t flag = 1;f or (j=O;jL. rj+l. key)aoftf 1 ag = 0;g int temp；， temp = L. r j .key；g L. r jj.key = L. rLj + l.k e y;L.rj+ 1 . key = temp;do)。若无互换说明已有序g i f( f lag= 1)oo b reak；)四、快速排序in
8、 t Pa r ti t ion(S q List &L,in t low,int 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.rlow = L. rhigh；w h i 1 e( 1 owhigh & L,r lowl， k ey= p i votk e y)g1ow+;L. r high = L. r low;0L.rlowJ = L.r OJ； 返回枢轴位置
9、re t u rn low;)void Q S o r t (Sq List &L, i n t low, i n t high)(每张子表的快速排序di f (low low, high);ooQ 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 L ist &L)(QSort(L,l,L. 1 e ngth);)五、简朴选择排序v oid S e le c tSo r t(S qList & L )int mi n;int j ； f or (int i = 0
10、; i L.len g th； i +)/选择第i小的记录，并互换L.rfil. key ；4 m i n =f or (in t k = i; k L.l e ngth; k+)/在Ri. nl中选择最小的记录，i f (L.rkJ.ke y m i n)。 d m i n = L.r k .ke y ; 叼=k;， 。“f (i != j)。 /与第i个记录互换 int temp = L. ril.k e y;L.riJ.key = L. rj.key;L.rj.ke y = temp; )0)六、堆排序vo i d Hea p Adjust( H e apTyp es,in t m)(。
11、堆调整,将记录调整为小顶堆i ntj;dR e dTy pe r c = H.r s 1； 暂时存储根结点3 f or(j=2* s ; jif ( j m &H. rj .k ey= H.r j l.ke y )go b r e a k ；H. r s = H. r j；s = j ;)dH.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.lengt h ; i 0；-i)He a pAdju s t ( H,i, H. Ie n g t h);f or(i= H.leng t h ;
12、 il; -i)o temp = H. r 1;H.r 1 = H.r i ；H. r i = t e mp; He a pAd j us t (H, 1, i-1);)(2)遍历函数与初始化void Vi s i t (SqL i stL)for (in t i=l; i =L. leng t h ; i+)cout L .ril.keyM ；coute n dl;)void I n it S q List(SqLis t &L,i n t a )f o r(int i=l;i= L.len g t h ;i+)L .r i .ke y = a i；)五、测试结果以下是各种界面的测试结果:(1)输入的界面(1)输入的界面，任:最后的课里设计DebugWE序.exe(2)