數(shù)據(jù)結(jié)構(gòu)實(shí)訓(xùn)報(bào)告

1、目錄1課程設(shè)計(jì)目標(biāo)與任務(wù)11.1 課程設(shè)計(jì)目標(biāo)11.2 課程設(shè)計(jì)任務(wù)12分析與設(shè)計(jì)22.1題目需求分析22.2結(jié)構(gòu)設(shè)計(jì)22.3算法描述32.4 算法比較分析72.5 程序流程圖82.6 測試程序說明93程序.104測試164.1 測試數(shù)據(jù)164.2分析165總結(jié)18參考文獻(xiàn)191 課程設(shè)計(jì)目標(biāo)與任務(wù)1.1 課程設(shè)計(jì)目標(biāo)通過本課程設(shè)計(jì)，使學(xué)生在數(shù)據(jù)結(jié)構(gòu)的選擇和應(yīng)用、算法的設(shè)計(jì)與實(shí)現(xiàn)方面得到訓(xùn)練，加深對數(shù)據(jù)結(jié)構(gòu)基本內(nèi)容的理解和靈活應(yīng)用，同時(shí)，在程序設(shè)計(jì)方法及上機(jī)操作方面受到比較系統(tǒng)嚴(yán)格的訓(xùn)練，培養(yǎng)工作所需要的動手能力。數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)是在學(xué)完數(shù)據(jù)結(jié)構(gòu)課程之后的實(shí)踐教學(xué)環(huán)節(jié)。該實(shí)踐教學(xué)是設(shè)計(jì)的綜合訓(xùn)

2、練,包括問題分析，總體結(jié)構(gòu)設(shè)計(jì)用戶界面設(shè)計(jì)，程序設(shè)計(jì)基本技能和技巧。要求學(xué)生在設(shè)計(jì)中逐步提高程序設(shè)計(jì)能力培養(yǎng)科學(xué)的工作方法學(xué)生通過數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)各方面得到鍛煉：（1）能根據(jù)實(shí)際問題的具體情況結(jié)合數(shù)據(jù)結(jié)構(gòu)課程中的基本理論和基本算法，正確分析出數(shù)據(jù)的邏輯結(jié)構(gòu)，合理地選擇相應(yīng)的結(jié)構(gòu)，并能設(shè)計(jì)出解決問題的有效算法；（2）通過上機(jī)實(shí)習(xí),驗(yàn)證自己設(shè)計(jì)的算法的正確性，學(xué)會有效利用基本調(diào)試方法，迅速找出程序代碼中的錯(cuò)誤并且修改；（3）培養(yǎng)算法分析能力，分析所設(shè)計(jì)算法的時(shí)間復(fù)雜度和空間復(fù)雜度，進(jìn)一步提高程序設(shè)計(jì)水平；（4）盡可能借助語言環(huán)境實(shí)現(xiàn)圖形顯示功能，以便將抽象的數(shù)據(jù)結(jié)構(gòu)以圖形方式顯示出來，將復(fù)雜的運(yùn)行

3、過程以動態(tài)方式顯示出來，獲得算法的直觀感受。1.2 課程設(shè)計(jì)任務(wù)設(shè)計(jì)排序相關(guān)函數(shù)庫，以便在程序設(shè)計(jì)中調(diào)用，要求設(shè)計(jì)程序完成下面功能：（1）對這些數(shù)分別進(jìn)行直接排序、折半排序、排序、起泡排序、快速排序、簡單選擇排序、堆排序、2-路歸并排序，并把排序結(jié)果進(jìn)行保存；（2）最好能借助語言環(huán)境實(shí)現(xiàn)圖形顯示功能，以便將抽象的數(shù)據(jù)結(jié)構(gòu)以圖形方式顯示出來，將復(fù)雜的運(yùn)行過程以動態(tài)方式顯示出來；（3）給出若干例程，演示通過調(diào)用自己所寫程序來實(shí)現(xiàn)相關(guān)問題的求解。2 分析與設(shè)計(jì)2.1 題目實(shí)現(xiàn)步驟為了實(shí)現(xiàn)題目要求：（1）先理解程序的功能，知道并會利用排序的算法。（2）首先設(shè)計(jì)數(shù)據(jù)的結(jié)構(gòu)，構(gòu)建程序框架，設(shè)計(jì)程序流程圖如

4、圖。（3）實(shí)現(xiàn)程序的功能模塊，完成程序的調(diào)試。2.2結(jié)構(gòu)設(shè)計(jì)在排序的過程中需要以下兩種操作：（1）比較兩個(gè)關(guān)鍵字的大小；（2）將從一個(gè)位置移動到另一個(gè)位置。前一個(gè)操作對大多數(shù)的算法都是必要的，而后一個(gè)操作可以通過改變的方式來實(shí)行。待排序的序列可有三種存儲方式：（1）待排序的一組存放在地址連續(xù)的一組單元上。它類似于線性表的順序結(jié)構(gòu)，在序列中相鄰的兩個(gè)，他們的位置也相鄰。在這種方式中，之間的次序關(guān)系由其位置決定，實(shí)現(xiàn)排序必須借助移動；（2）待排序的一組存放在靜態(tài)鏈表中，之間的次序關(guān)系由指針指示，實(shí)現(xiàn)排序不需要移動，僅需修改指針即可；（3）待排序本身在一組地址連續(xù)的單元內(nèi)，同時(shí)令設(shè)一個(gè)指示各個(gè)位置的

5、地址向量，在排序過程中不需要移動本身。，而移動地址向量中這些的“地址”，在排序結(jié)束之后在地址向量中的值來調(diào)整的位置。在以下設(shè)計(jì)的算法中，待排的數(shù)據(jù)類型為：#define MAXSIZE 20 / 一個(gè)用作示例的小順序表的最大長度KeyType; / 定義關(guān)鍵字類型為整型InfoType; / 定義其它數(shù)據(jù)項(xiàng)的類型typedeftypedef類型struct RedType /KeyType key; / 關(guān)鍵字項(xiàng)InfoType otherinfo; / 其它數(shù)據(jù)項(xiàng)，具體類型在主程中定義;struct SqList / 順序表類型RedType rMAXSIZE+1; / r0閑置或用作哨兵單

6、元length; / 順序表長度;2.3 算法描述（1）直接排序這是一種最簡單的排序方法，基本操作是將一個(gè)到已經(jīng)排好序的有序表中，從而得到一個(gè)新的、數(shù)增一的有序表。第一趟比較前兩個(gè)數(shù)，然后把第二個(gè)數(shù)按大小到有序表中； 第二趟把第三個(gè)數(shù)據(jù)與前兩個(gè)數(shù)從前向后掃描，把第三個(gè)數(shù)按大小到有序表中；依次進(jìn)行下去，進(jìn)行了(n-1)趟掃描以后就完成了整個(gè)排序過程。直接排序?qū)儆诜€(wěn)定的排序，時(shí)間復(fù)雜性為O(n2)，空間復(fù)雜度為 O(1)?！纠筷P(guān)鍵字為 49 38 65 97 76 13 27 49 則直接做法如圖 2-1圖 直接法示例直接排序是由兩層嵌套循環(huán)組成的。外層循環(huán)標(biāo)識并決定待比較的數(shù)值。內(nèi)層循環(huán)為待比

7、較數(shù)值確定其最終位置。直接排序是將待比較的數(shù)值與它的前一個(gè)數(shù)值進(jìn)行比較，所以外層循環(huán)是從第二個(gè)數(shù)值開始的。當(dāng)前一數(shù)值比待比較數(shù)值大的情況下繼續(xù)循環(huán)比較，直到找到比待比較數(shù)值小的并將待比較數(shù)值置入其后一位置，結(jié)束該次循環(huán)。值得注意的是，需用一個(gè)空間來保存當(dāng)前待比較的數(shù)值，因?yàn)楫?dāng)一趟比較完成時(shí)，要將待比較數(shù)值置入比它小的數(shù)值的后一位排序類似玩牌時(shí)整理手中紙牌的過程。排序的基本初始關(guān)鍵字（49） 38 65 97 76 13 27 49I=2；（38） （3849）65 97 7613 27 49I=3；（65） （3849 65）97 7613 27 49I=4；（97） （3849 65 97）

8、7613 27 49I=5；（76） （3849 65 76 97） 13 27 49I=6；（13） （1338 49 65 76） 97 27 49I=7；（27） （1327 38 49 6576 97）49I=8；（49） （1327 38 49 4965 76 97 ）監(jiān)視哨L.r0方法是：每步將一個(gè)待排序的按其關(guān)鍵字的大小插到前面已經(jīng)排序的序列中的適當(dāng)位置，直到全部完畢為止。（2）折半它是對排序排序算法的一種改進(jìn)，由于排序算法過程中，就是不斷的依次將元素前面已排好序的序列中。由于前半部分為已排好序的數(shù)列，這樣不用按順序依次尋找點(diǎn)，可以采用折半查找的方法來加快尋找點(diǎn)的速度。在將一個(gè)新

9、元素已排好序的數(shù)組的過程中，尋找點(diǎn)時(shí)，將待區(qū)域的首元素設(shè)置為 alow，末元素設(shè)置為 ahigh，則輪比較時(shí)將待元素與am，其中 m=(low+high)/2 相比較,如果比參考元素小，則選擇 alow到 am-1為新的區(qū)域(即high=m-1)，否則選擇 am+1到 ahigh為新的區(qū)域（即low=m+1），如此直至 low=high 不成立，即將此位置之后所有元素后移一位，并將新元素ahigh+1。（3）排序排序(SSort)是排序的一種。是針對直接排序算法的改進(jìn)。該方法又稱縮小增量排序，因DLS于 1959 年提出而得名。先取一個(gè)小于 n的整數(shù)d1 作為第一個(gè)增量，把文件的全部錄放在同一

10、個(gè)組中。先在各組內(nèi)進(jìn)行直接分組。所有距離為 d1 的倍數(shù)的記排序；然后，取第二個(gè)增量 d2d1重復(fù)上述的分組和排序，直至所取的增量=1(d2d1)，即所有放在同一組中進(jìn)行直接排序?yàn)橹?。?）冒泡排序算法冒泡排序算法的如下：（從后往前）1比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。2對每一對相鄰元素作同樣的工作，從開始第一對到結(jié)尾的最后一對。在這一點(diǎn)，最后的元素應(yīng)該會是最大的數(shù)。3針對所有的元素重復(fù)以上的步驟，除了最后一個(gè)。4持續(xù)每次對越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較。（5）快速排序快速排序（Quicksort）是對冒泡排序的一種改進(jìn)。由C. A. R. Ho

11、are 在 1962 年提出。它的基本是：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。（6）歸并排序歸并排序是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱為二路歸并。歸并過程為：比較 ai和 aj的大小，若 aiaj，則將第一個(gè)有序表中的元素 ai到r

12、k中，并令i 和k 分別加上 1；否則將第二個(gè)有序表中的元素 aj到rk中，并令j 和k 分別加上 1，如此循環(huán)下去，直到其中一個(gè)有序表取完，然后再將另一個(gè)有序表中剩余的元素到 r 中從下標(biāo)k 到下標(biāo)t 的單元。歸并排序的算法通常用遞歸實(shí)現(xiàn)，先把待排序區(qū)間s,t以中點(diǎn)二分，接著把左邊子區(qū)間排序，再把右邊子區(qū)間排序，最后把左區(qū)間和右區(qū)間用一次歸并操作合并成有序的區(qū)間s,t。（7）堆排序堆排序(Heapsort)是指利用堆積樹（堆）這種資料結(jié)構(gòu)所設(shè)計(jì)的一種排序算法，可以利用數(shù)組的特點(diǎn)快速定位指定索引的元素。堆排序利用了大根堆(或小根堆)堆頂?shù)年P(guān)鍵字最大(或最小)這一特征，使得在當(dāng)前無序區(qū)中選取最大

13、(或最小)關(guān)鍵字的變得簡單。n 個(gè)關(guān)鍵字序列Kl，K2，Kn 稱為（Heap），當(dāng)且僅當(dāng)該序列滿足如下性質(zhì)（簡稱為堆性質(zhì)）：大根堆示例(1)ki=k(2i）且 ki=號。/k(i）相當(dāng)于二叉樹的非葉子結(jié)點(diǎn)，K(2i）則是節(jié)點(diǎn)，k(2i+1）是右子節(jié)點(diǎn)。將此序列所的向量R1.n看做是一棵完全二叉樹的結(jié)構(gòu)，則堆實(shí)質(zhì)上是滿足如下性質(zhì)的完全二叉樹：樹中任一非葉子結(jié)點(diǎn)的關(guān)鍵字均不大于（或不小于）其左右孩子（若存在）結(jié)點(diǎn)的關(guān)鍵字。【例】關(guān)鍵字序列（10，15，56，25，30，70）和（70，56，30，25，15，10）分別滿足堆性質(zhì)（1）和（2），故它們均是堆，其對應(yīng)的完全二叉樹分別如圖 2-3 根堆

14、示例和大根堆示例所示。101556253070705630251510圖 堆示例和大根堆示例大根堆和小根堆：根結(jié)點(diǎn)（亦稱為堆頂）的關(guān)鍵字是堆里所有結(jié)點(diǎn)關(guān)鍵字中最小者的堆稱為小根堆，又稱最小堆。根結(jié)點(diǎn)（亦稱為堆頂）的關(guān)鍵字是堆里所有結(jié)點(diǎn)關(guān)鍵字中最大者，稱為大根堆，又稱最大堆。注意：堆中任一亦是堆。以上的堆實(shí)際上是二叉堆（BinaryHeap），類似地可定義 k 叉堆。堆的高度：高度堆可以被看成是一棵樹，結(jié)點(diǎn)在堆中的高度可以被定義為從本結(jié)點(diǎn)到葉子結(jié)點(diǎn)的最長簡單下降路徑上邊的數(shù)目；定義堆的高度為樹根的高度。將看到，堆結(jié)構(gòu)上的一些基本操作的運(yùn)行時(shí)間至多是與樹的高度成正比，為 O（lgn）。（8）簡單選

15、擇排序設(shè)所排序序列的個(gè)數(shù)為。i 取 1,2,n-1,從所有 n-i+1 個(gè)記（R,Ri+1,Rn中找出排序碼最小的，與第個(gè)交換。執(zhí)行 n-1 趟 后就完成了序705630251510101556253070列的排序。在簡單選擇排序過程中，所需移動的次數(shù)比較少。最好情況下，即待排序初始狀態(tài)就已經(jīng)是正序排列了，則不需要移動。情況下，即待排序初始狀態(tài)是按逆序排列的，則需要移動的次數(shù)最多為 3（n-1）。簡單選擇排序過程中需要進(jìn)行的比較次數(shù)與初始狀態(tài)下待排序的序列的排列情況無關(guān)。當(dāng)i=1 時(shí)，需進(jìn)行n-1 次比較；當(dāng)i=2 時(shí)，需進(jìn)行n-2 次比較；依次類推，共需要進(jìn)行的比較次數(shù)是(n-1)+(n-2

16、)+2+1=n(n-1)/2，即進(jìn)行比較操作的時(shí)間復(fù)雜度為 O(n2)。2.4 算法比較分析算法復(fù)雜度分為時(shí)間復(fù)雜度和空間復(fù)雜度。其作用： 時(shí)間復(fù)雜度是度量算法執(zhí)行的時(shí)間長短；而空間復(fù)雜度是度量算法所需空間的大小。因此可以通過比較這幾個(gè)算法的時(shí)間復(fù)雜度，來選擇最適合的算法。這幾種排序算法比較如圖 2-4：圖 2-4 算法比較分析2.5 程序流程圖將所有的排序方法，打包成函數(shù)并設(shè)計(jì)實(shí)現(xiàn)相應(yīng)的函數(shù)接口，方便在Main函數(shù)中調(diào)用。設(shè)計(jì)結(jié)構(gòu)，實(shí)現(xiàn)排序算法，通過調(diào)用函數(shù)對測試數(shù)據(jù)進(jìn)行排序，并輸出結(jié)果。按照編程，實(shí)現(xiàn)相應(yīng)的程序，程序流程圖如圖 2-5：開始調(diào)用直接排序算法調(diào)用折半排序算法調(diào)用希爾排序算法調(diào)

17、用起泡算法調(diào)用快速排序算法調(diào)用歸并排序算法調(diào)用堆排序算法調(diào)用簡單選擇排序算法結(jié)束圖 程序流程圖調(diào)用pr 函數(shù)，輸出結(jié)果調(diào)用排序函數(shù)構(gòu)建表初始化2.6 測試程序說明程序測試：根據(jù)自己的程序，在主程序中設(shè)定相應(yīng)的函數(shù)操作，通過函數(shù)接口調(diào)用相應(yīng)的函數(shù)對自己建立的順序表進(jìn)行排序，并在屏幕顯示相應(yīng)的結(jié)果。#include#include / malloc()等#include / EOF(=Z 或 F6),NULL #define LQ(a,b) (a)=(b)void main()SqList l1,l2,l3,l4,l5,l7,l8,l9;/定義順序表 i;for(i=0;iN;i+) / 給l1.

18、r 賦值l1.ri+1=di;l1.length=N;l9=l8=l7=l5=l4=l2=l3=l1;prf(排序前:n); prInsertSort(l1);(l1);prf(直接BInsertSort(l2);排序后:n); pr prf(折半排序:n);(l1);排序后:n);pr(l3);f(進(jìn)行prdt3=5,3,1;Sort(l4,dt,3); prf(排序后:n );prS(l4);prf(簡單選擇排序后:n);SelectSort(l5);pr(l5);prf(歸并排序后:n);prf(快速排序后:n);prf(冒泡排序后:n);MergeSort(l7);pr(l7);Qui

19、ckSort(l8);pr(l8);bubble_sort(l9);pr(l9);3 程序void InsertSort(SqList &L)/ 對順序表L 作直接排序。i,j;for(i=2;i=L.length;+i)if LT(L.ri.key,L.ri-1.key) / ,需將L.ri有序子表為哨兵L.r0=L.ri; /for(j=i-1;LT(L.r0.key,L.rj.key);-j)后移L.rj+1=L.rj; /到正確位置L.rj+1=L.r0; /void BInsertSort(SqList &L) / 對順序表 L 作折半排序。i,j,m,low,high;for(i=

20、2;i=L.length;+i)L.r0=L.ri; / 將L.ri暫存到 L.r0low=1;high=i-1;while(low=high+1;-j)后移L.rj+1=L.rj; /L.rhigh+1=L.r0; /void pr(SqList L)i;for(i=1;i=L.length;i+)prf(%d,%d),L.ri.key,L.ri.otherinfo);prf(n);void SInsert(SqList &L,dk) / 對順序表 L 作一趟排序。i,j;for(i=dk+1;i0<(L.r0.key,L.rj.key);j-=dk)后移，查找位置L.rj+dk=L.r

21、j; /L.rj+dk=L.r0; /void SSort(SqList &L,dlta,t) / 按增量序列 dlta0.t-1對順序表 L 作排序。k;for(k=0;kt;+k)Insert(L,dltak); / 一趟增量為 dltak的排序Sprf(第%d 趟排序結(jié)果: ,k+1);pr(L);SelectMinKey(SqList L,i) / 返回在 L.ri.L.length中 key 最小的的序號KeyType min;j,k;k=i; / 設(shè)第 i 個(gè)為最小min=L.ri.key;for(j=i+1;j=L.length;j+)if(L.rj.keymin) / 找到更小

22、的k=j;min=L.rj.key;return k;void SelectSort(SqList &L) / 對順序表 L 作簡單選擇排序。i,j;RedType t;for(i=1;iL.length;+i) /選擇第 i 小的，并交換到位j=SelectMinKey(L,i); / 在L.ri.L.length中選擇 key 最小的if(i!=j) / 與第 i 個(gè)交換t=L.ri;L.ri=L.rj;L.rj=t;void Merge(RedType SR,RedType TR,i,m,n) / 將有序的 SRi.m和 SRm+1.n歸并為有序的 TRi.nj,k,l;for(j=m+

23、1,k=i;i=m&j=n;+k) / 將 SR 中由小到大地并入 TRif LQ(SRi.key,SRj.key)TRk=SRi+;elseTRk=SRj+;if(i=m)for(l=0;l=m-i;l+)TRk+l=SRi+l; / 將剩余的 SRi.m到 TRif(j=n)for(l=0;l=n-j;l+)TRk+l=SRj+l; / 將剩余的 SRj.n到 TRvoid MSort(RedType SR,RedType TR1,s,t) / 將 SRs.t歸并排序?yàn)?TR1s.t。m;RedType TR2MAXSIZE+1;if(s=t)TR1s=SRs;elsem=(s+t)/2;

24、 / 將 SRs.t平分為 SRs.m和 SRm+1.tMSort(SR,TR2,s,m); / 遞歸地將 SRs.m歸并為有序的 TR2s.mMSort(SR,TR2,m+1,t); / 遞歸地將 SRm+1.t歸并為有序的 TR2m+1.tMerge(TR2,TR1,s,m,t); / 將 TR2s.m和 TR2m+1.t歸并到 TR1s.tvoid MergeSort(SqList &L) / 對順序表 L 作歸并排序。MSort(L.r,L.r,1,L.length);Partition(SqList &L,low,high) / 交換順序表L 中子表 rlow.high的，樞軸到位，

25、并返回其/ 所在位置，此時(shí)在它之前（后）的均不大（?。┯谒?。KeyTypvotkey;L.r0=L.rlow; / 用子表的第一個(gè)作樞軸pivotkey=L.rlow.key; / 樞軸關(guān)鍵字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,low,high) / 對順序表 L 中的子序列 L.rlow.high作快速排序。算法 10.7pivotloc;if(lowhigh) / 長度大于 1pivotloc=Partition(L,low,high); / 將L.rlow.high一分為二QSort(L,low,pivotloc-1); / 對低子表遞歸排序，pivotloc 是樞軸位置QSort(L,pivotloc+1,high); / 對高子表遞歸排序void QuickSort