數據結構實訓報告

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

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

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

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

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

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

7、較數值確定其最終位置。直接排序是將待比較的數值與它的前一個數值進行比較，所以外層循環(huán)是從第二個數值開始的。當前一數值比待比較數值大的情況下繼續(xù)循環(huán)比較，直到找到比待比較數值小的并將待比較數值置入其后一位置，結束該次循環(huá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方法是：每步將一個待排序的按其關鍵字的大小插到前面已經排序的序列中的適當位置，直到全部完畢為止。（2）折半它是對排序排序算法的一種改進，由于排序算法過程中，就是不斷的依次將元素前面已排好序的序列中。由于前半部分為已排好序的數列，這樣不用按順序依次尋找點，可以采用折半查找的方法來加快尋找點的速度。在將一個新

9、元素已排好序的數組的過程中，尋找點時，將待區(qū)域的首元素設置為 alow，末元素設置為 ahigh，則輪比較時將待元素與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)是排序的一種。是針對直接排序算法的改進。該方法又稱縮小增量排序，因DLS于 1959 年提出而得名。先取一個小于 n的整數d1 作為第一個增量，把文件的全部錄放在同一

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

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

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

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

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

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

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

17、用起泡算法調用快速排序算法調用歸并排序算法調用堆排序算法調用簡單選擇排序算法結束圖 程序流程圖調用pr 函數，輸出結果調用排序函數構建表初始化2.6 測試程序說明程序測試：根據自己的程序，在主程序中設定相應的函數操作，通過函數接口調用相應的函數對自己建立的順序表進行排序，并在屏幕顯示相應的結果。#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(進行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 趟排序結果: ,k+1);pr(L);SelectMinKey(SqList L,i) / 返回在 L.ri.L.length中 key 最小的的序號KeyType min;j,k;k=i; / 設第 i 個為最小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 個交換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歸并排序為 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、并返回其/ 所在位置，此時在它之前（后）的均不大（?。┯谒?。KeyTypvotkey;L.r0=L.rlow; / 用子表的第一個作樞軸pivotkey=L.rlow.key; / 樞軸關鍵字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