數(shù)據(jù)結(jié)構(gòu)課程設(shè)計

1、大 連 科 技 學(xué) 院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計題 目 排序綜合 學(xué)生姓名 專業(yè)班級 指導(dǎo)教師 職 稱 副教授 所在單位 信息科學(xué)系軟件教研室 教學(xué)部主任 完成日期 2013年1月11日課程設(shè)計報告單學(xué)號1106090119姓名王復(fù)之專業(yè)班級網(wǎng)絡(luò)工程11-1考 核 項 目評分備注1平時工作態(tài)度及遵守紀(jì)律情況（10分）2掌握基本理論、關(guān)鍵知識、基本技能的程度和閱讀參考資料的水平（10分）3獨立工作能力、綜合運用所學(xué)知識分析和解決問題能力及實際工作能力提高的程度（20分）4完成課程設(shè)計說明書及軟件的情況與水平（小組分工情況、規(guī)范性、整潔清楚、敘述完整性、思路清晰程度、工作量及實際運行情況和創(chuàng)新性）（60分）

2、總評成績綜 合 評 定：（優(yōu)、良、中、及格、不及格） 指導(dǎo)教師簽字：2013年1月11日數(shù)據(jù)結(jié)構(gòu)課程設(shè)計任務(wù)書一、任務(wù)及要求：1. 設(shè)計（研究）任務(wù)和要求研究內(nèi)容：排序綜合任務(wù)和要求：（1）學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)知識，掌握數(shù)據(jù)結(jié)構(gòu)典型的算法的使用。（2）對指導(dǎo)教師下達(dá)的題目進行系統(tǒng)分析。（3）根據(jù)分析結(jié)果完成系統(tǒng)設(shè)計。（4）編程：在計算機上實現(xiàn)題目的代碼實現(xiàn)。（5）完成對該系統(tǒng)的測試和調(diào)試。（6）提交課程設(shè)計報告。要求完成課程設(shè)計報告3000字以上(約二十頁)。完成若干綜合性程序設(shè)計題目，綜合設(shè)計題目的語句行數(shù)的和在100行語句以上。2.原始依據(jù)結(jié)合數(shù)據(jù)結(jié)構(gòu)課程中的基本理論和基本算法，正確分析出數(shù)據(jù)

3、的邏輯結(jié)構(gòu)，合理地選擇相應(yīng)的存儲結(jié)構(gòu)，并能設(shè)計出解決問題的有效算法。提高程序設(shè)計和調(diào)試能力。學(xué)生通過上機實習(xí)，驗證自己設(shè)計的算法的正確性。學(xué)會有效利用基本調(diào)試方法，迅速找出程序代碼中的錯誤并且修改。3.參考題目：二、工作量2周（10個工作日）時間三、計劃安排第1個工作日：查找相關(guān)資料、書籍，閱讀示例文檔，選擇題目。第2個工作日第3個工作日：設(shè)計程序結(jié)構(gòu)、模塊圖。第4個工作日第9個工作日：完成程序的編碼，并且自己調(diào)試、測試。穿插進行課程設(shè)計報告的撰寫。第10個工作日：上交課程設(shè)計報告，由教師檢查軟件測試效果、檢查課程設(shè)計報告，給出學(xué)生成績。指導(dǎo)教師簽字： 2012年12月24日目 錄排序綜合11

4、.需求分析11.1任務(wù)描述11.2功能分析12.概要設(shè)計1 2.1主要全程變量和數(shù)據(jù)結(jié)構(gòu)1 2.2程序模塊結(jié)構(gòu)23.詳細(xì)設(shè)計3 3.1程序的主要結(jié)構(gòu)如下圖所示。3 3.3顯示各排序算法排序后的的數(shù)據(jù)。4 3.4函數(shù)實現(xiàn)（例如直接插入排序）44.調(diào)試分析55.測試結(jié)果及運行效果7參考文獻11附錄 全部代碼12數(shù)據(jù)結(jié)構(gòu)課程設(shè)計總結(jié)24排序綜合1.需求分析1.1任務(wù)描述 至少采用3種方法實現(xiàn)上述問題求解，并把排序后的結(jié)果保存在不同的文件中。1.2功能分析 顯示隨機數(shù)，是調(diào)用rand()函數(shù)輸出數(shù)組a。數(shù)組a中保存有隨機產(chǎn)生的隨機數(shù)；直接選擇排序，是通過n-1次關(guān)鍵字之間的比較，從n-i+1個記錄中選

5、出關(guān)鍵字最小的記錄，并和第i個記錄交換之；起泡排序，是如果有n個數(shù)，則要進行n-1趟比較，在將整個待排記錄序列分割成為若干子序列分別進行直接插入排序，待整個排序中的記錄“基本有序”時，在對全體記錄進行一次直接插入排序；直接插入排序，是將一個記錄插入到以排序好的有序表中，從而得到一個新的記錄數(shù)增1的有序表。設(shè)整個排序有n個數(shù)，則 進行n-1趟排序，即:先將序列中的第一個記錄看成一個有序的子序列，然后第2個記錄起逐個進行插入，直接整個序列變成按關(guān)鍵字非遞減有序列為止；快速排序，是通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部

6、分?jǐn)?shù)據(jù)分別進行快速排序，整個排序過程可以遞歸進行，以此達(dá)到整個數(shù)據(jù)變成有序序列；堆排序，主要由建立初始堆和反復(fù)重建堆這兩部分的時間開銷構(gòu)成，它們均是通過調(diào)用Heapify實現(xiàn)的。2.概要設(shè)計2.1主要全程變量和數(shù)據(jù)結(jié)構(gòu)(1) 數(shù)據(jù)結(jié)構(gòu)：#include "stdlib.h"#include <stdio.h>#define s 100typedef struct recordint key;static struct record a1s,a2s,a3s,a4s,a5s,a6s,rec;int a7,b7;file()(2) 算法的入口及其說明 #include

7、<stdio.h> #define s 100 /宏定義命令 typedef struct record /記錄聲明的結(jié)構(gòu)體int key;/定義變量static struct record a1s,a2s,a3s,a4s,a5s,a6s,rec;int a7,b7; /記錄靜態(tài)變量結(jié)構(gòu)體file() /系統(tǒng)定義 printf(" * n"); printf(" * *1. 直接插入排序 * n"); printf(" * *2. 希爾排序 * n"); printf(" * *3. 起泡排序 * n"

8、); printf(" * *4. 快速排序 * n"); printf(" * *5. 簡單選擇排序 * n"); printf(" * *6. 堆排序 * n"); printf(" * *7. 總結(jié) * n"); printf(" * *0. 退出 * n"); printf(" * n"); 以上printf(" * n");為系統(tǒng)主菜單輸出2.2程序模塊結(jié)構(gòu) 程序劃分為以下幾個模塊（即實現(xiàn)程序功能所需的函數(shù)）主控菜單項選擇函數(shù):menu_sele

9、ct() 插入排序函數(shù):InsertSort（） 選擇排序函數(shù)：StlectSort() 起泡排序函數(shù)：BubbleSort() 堆排序函數(shù)：heapsort（） 快速排序函數(shù)：Quicksort（） 希爾排序：Shell Sort（）3.詳細(xì)設(shè)計3.1程序的主要結(jié)構(gòu)如下圖所示。圖3-1函數(shù)調(diào)用關(guān)系圖其中main()是主函數(shù)，它進行菜單驅(qū)動，根據(jù)選擇項10調(diào)用相應(yīng)的函數(shù)3.2數(shù)據(jù)結(jié)構(gòu)定義圖3-2課程設(shè)計流程圖3.3顯示各排序算法排序后的的數(shù)據(jù)。圖3-3程序工作流程圖3.4函數(shù)實現(xiàn)（例如直接插入排序）#include "stdlib.h"#include <stdio.

10、h>#define s 100typedef struct recordint key;static struct record a1s,a2s,a3s,a4s,a5s,a6s,rec;int a7,b7;file() printf(" * n");printf(" * *1. 直接插入排序 * n");printf(" * *0. 退出 * n");printf(" * n"); void Straight_insert_sort(r,n) /*直接插入*/struct record r;int n; in

11、t i,j; a1=0;b1=0; for(i=1;i<=n;i+) printf("%4d",ri.key); printf("n"); for(i=2;i<=n;i+) r0=ri; j=i-1; while(j>=0) && (r0.key<rj.key) b1+; rj+1=rj-; rj+1=r0; a1=a1+2; printf("*直接插入*n"); for(i=1;i<=n;i+) printf("%4d",ri); printf("n&quo

12、t;); printf("move:%d time, compete:%d time",a1,b1); printf("n"); 4.調(diào)試分析4.1 直接插入排序?qū)⒁粋€記錄插入到已排好的有序表中，從而得到一個新的，記錄數(shù)增加1的有序表4.2 起泡排序首先將第一個記錄的關(guān)鍵字和第二個記錄的關(guān)鍵字進行比較，若為逆序，則將兩個記錄交換，然后比較第二個記錄和第三個記錄的關(guān)鍵字。依此類推，知道第N-1個和第N個記錄的關(guān)鍵字進行過比較為止。上述為第一趟排序。其結(jié)果使得關(guān)鍵字的最大被安排到最后一個記錄的位置上。然后進行第二趟起泡排序，對前N-1個記錄進行同樣操作。一共

13、要進行N-1趟起泡排序。4.3 直接選擇排序每一趟從待排序的記錄中選出關(guān)鍵字最小的，順序放在以排好序的子文件的最后，知道全部記錄排序完畢。4.4 希爾排序先取一個小于n的整數(shù)d，作為第一個增量，把文件全部記錄全部分成d1個組。所有距離為d1的倍數(shù)的記錄放在同一個組中。先在個組中進行直接插入排序：然后，取第二個增量d2<d1重復(fù)上述的分組和排序，直至所取的增量dt=1（dt<dt-1<<d2<d1）,即所有記錄放在同一組中進行直接插入排序為止。4.5 快速排序設(shè)置兩個變量i、j，排序開始的時候：i=0，j=N-1； 以第一個數(shù)組元素作為關(guān)鍵數(shù)據(jù)，賦值給key，即 k

14、ey=A0；從j開始向前搜索，即由后開始向前搜索（j - ），找到第一個小于key的值A(chǔ)j，Ai與Aj交換；從i開始向后搜索，即由前開始向后搜索（i + ），找到第一個大于key的Ai，Ai與Aj交換；重復(fù)第3、4、5步，直到 I=J； (3,4步是在程序中沒找到時候j=j-1，i=i+1，直至找到為止。找到并交換的時候i， j指針位置不變。另外當(dāng)i=j這過程一定正好是i+或j-完成的最后令循環(huán)結(jié)束。）4.6 堆排序堆排序的時間，主要由建立初始堆和反復(fù)重建堆這兩部分的時間開銷構(gòu)成，它們均是通過調(diào)用Heapify實現(xiàn)的。堆排序的最壞時間復(fù)雜度為O(nlogn)。堆序的平均性能較接近于最壞性能。由

15、于建初始堆所需的比較次數(shù)較多，所以堆排序不適宜于記錄數(shù)較少的文件。堆排序是就地排序，輔助空間為O(1）。排序算法時間復(fù)雜度空間復(fù)雜度是否穩(wěn)定直接插入排序O（n²）O(1)穩(wěn)定起泡排序O（n²）O(1)穩(wěn)定直接選擇排序O（n²）O(1)不穩(wěn)定希爾排序O（n1.5）O(1)不穩(wěn)定快速排序O(nlog2n)O(nlog2n)不穩(wěn)定堆排序O(nlog2n)O(l)不穩(wěn)定圖4-1時間復(fù)雜度分析5.測試結(jié)果及運行效果（1） 運行程序進入程序開始菜單圖5-1開始菜單（2）開始菜單中會出現(xiàn)四個選項：完全有序的情況；逆序的情況；隨機排序的情況；退出。運行時選擇了隨機排序的情況，得到

16、100個隨機數(shù)的隨機排序，如下圖。圖5-2隨機排序（3） 得出隨機數(shù)字后，程序列出七個選項：冒泡排序；直接插入排序；簡單選擇排序；快速排序；希爾排序；堆排序；退出。選擇冒泡排序，對100個隨機數(shù)進行冒泡排序，得到結(jié)果如下圖。圖5-3起泡排序（4） 為了測試該程序，下面繼續(xù)嘗試進行了其他幾種排序方式，結(jié)果如下圖所示。圖5-4直接插入排序圖5-5簡單選擇排序簡單選擇排序結(jié)果如上圖圖5-6快速排序快速排序結(jié)果如上圖圖5-7希爾排序希爾排序結(jié)果如上圖圖5-8堆排序堆排序結(jié)果如上圖以上圖片為各種排序的結(jié)果，排序結(jié)果后顯示出各種方式排序所用移動次數(shù)和比較次數(shù)，以方便比較使用。參考文獻1 嚴(yán)蔚敏 吳偉民著.

17、數(shù)據(jù)結(jié)構(gòu)(C語言版).清華大學(xué)出版.1999年第一版2 陳一華等編.數(shù)據(jù)結(jié)構(gòu)-使用C 語言.電子科技大學(xué)出版社.1998年第一版3 譚浩強.C語言程序設(shè)計（第二版）.北京.高等教育出版社.2002附錄 全部代碼#include "stdlib.h"#include <stdio.h>#define s 100typedef struct recordint key;static struct record a1s,a2s,a3s,a4s,a5s,a6s,rec;int a7,b7;file() printf(" * n"); printf(&

18、quot; * *1. 直接插入排序 * n"); printf(" * *2. 希爾排序 * n"); printf(" * *3. 冒泡排序 * n"); printf(" * *4. 快速排序 * n"); printf(" * *5. 簡單選擇排序 * n"); printf(" * *6. 堆排序 * n"); printf(" * *7. 總結(jié) * n"); printf(" * *0. 退出 * n"); printf("

19、 * n"); void Straight_insert_sort(r,n) /*直接插入*/struct record r;int n; int i,j; a1=0;b1=0; for(i=1;i<=n;i+) printf("%4d",ri.key); printf("n"); for(i=2;i<=n;i+) r0=ri; j=i-1; while(j>=0) && (r0.key<rj.key) b1+; rj+1=rj-; rj+1=r0; a1=a1+2; printf("*直接插入

20、*n"); for(i=1;i<=n;i+) printf("%4d",ri); printf("n"); printf("move:%d time, compete:%d time",a1,b1); printf("n"); void Shell_sort(r,n) /* 希 爾 排 序 */struct record r;int n; struct record rec,temp; int i,j,t,h; a2=0;b2=0; for(i=1;i<=n;i+) printf("

21、%4d",ri.key); printf("n"); t=n/2; while(t>=1) h=t; for(j=h;j<n;j+) rec=rj; i=j-h; while(i>=0) && (ri.key>rec.key) b3+; temp=ri+h; ri+h=ri; ri=temp; i=i-h; a2=a2+3; t=t/2; b2+; printf("*希 爾 排 序*n"); for(i=0;i<n;i+) printf("%4d",ri); printf(&qu

22、ot;n"); printf("move:%d time, compete:%d time",a3,b3); printf("n"); void Bubblle_sort(r,n) /* 冒 泡 排 序 */struct record r;int n; struct record rec; int i,j,m,flag; a3=0;b3=0; for(i=1;i<=n;i+) printf("%4d",ri.key); printf("n"); m=n; flag=1; for(i=1;i<=

23、m-1;i+) flag=0; for(j=0;j<=m-i-1;j+) if(rj.key>rj+1.key) b3+; rec.key=rj.key; rj.key=rj+1.key; rj+1.key=rec.key; a3=a3+3; flag=1; if(flag=0) break; printf("*冒 泡 排 序*n"); for(i=0;i<n;i+) printf("%4d",ri.key); printf("n"); printf("move: %d time, compete: %d

24、time",a3,b3); printf("n"); int push(h,top,m,n)int h; int top ,m,n; h+top=m; h+top=n; return(top); int pop(h,top,m,n)int h, top,*m,*n; *m=htop-; *n=htop-; return(top); int quick(r,i,j)struct record r;int i,j; rec=ri; while(i<j) while(i<j)&&(rj.key>rec.key) j-; b4+; if(

25、i<j) ri+=rj; a4+; while(i<j)&&(ri.key<=rec.key) i+; b4+; if(i<j) rj-=ri; a4+; ri=rec; a4+; return(i); void Quick_sort(r,l,h) /* 快 速 排 序 */struct record r;int l,h; int sss; int top,i,j,k; for(i=1;i<=s;i+) printf("%4d",ri.key); printf("n"); i=l; j=h; top=-1;

26、do while(i<j) k=quick(r,i,j); if(j-k>1) top=push(ss,top,k+1,j); j=k-1; if(top>0) top=pop(ss,top,&j,&i); while(top>=0)|(i<j); printf("*快 速 排 序*n"); for(i=1;i<=s;i+) printf("%4d",ri.key); printf("n"); printf("move: %d time, compete: %d time&

27、quot;,a4,b4); void Simple_select_sort(r,n) /* 簡 單 選 擇 排 序 */struct record r;int n; int i,j,m; a5=0;b5=0; for(i=1;i<=n;i+) printf("%4d",ri.key); printf("n"); for(i=1;i<=n-1;i+) m=i; for(j=i+1;j<=n;j+) if(rj.key<rm.key) m=j; b5+; if(i!=m) rec=ri; ri=rm; rm=rec; a5=a5+3;

28、 printf("*簡 單 選 擇*n"); for(i=1;i<=s;i+) printf("%4d",ri.key); printf("n"); printf("move:%d time, compete:%d time",a5,b5); printf("n"); void p(r,n) /* 次數(shù)排列 */int r;int n; int rec; int i,j; for(i=1;i<=n;i+) rec=ri; j=i-1; while(j>0) &&

29、 (rec<rj) rj+1=rj; j=j-1; rj+1=rec; if(r=a) printf("關(guān) 鍵 字 移 動 次 數(shù) 排 列:n"); else printf("關(guān) 鍵 字 比 較 次 數(shù) 排 列:n"); for(i=1;i<=n;i+) printf("%8d",ri); printf("n");void heap(r,l,m) /* 堆的子函數(shù) */struct record r;int l,m; int i,j; i=l; j=2*i; rec=ri; while(j<=m)

30、 if(j<m)&&(rj.key>rj+1.key) j+; b6+; if(rec.key>rj.key) b6+; ri=rj; i=j; j=2*i; a6+; else j=m+1; ri=rec; void Heap_sort(r,n) /* 堆 排 序 */struct record r;int n; int l; a6=0;b6=0; for(l=1;l<=n;l+) printf("%4d",rl.key); printf("n"); for(l=n/2;l>=1;l-) heap(r,l,

31、n); for(l=n;l>=2;l-) rec=r1; r1=rl; rl=rec; a6=a6+3; heap(r,1,l-1); printf("*堆 排 序*n"); for(l=n;l>=1;l-) printf("%4d",rl.key); printf("n"); printf("move: %d time, compete: %d time ",a6,b6); printf("n"); compete() printf(" * 內(nèi) 部 排 序 結(jié) 果 匯 總

32、 * n"); printf(" - n"); printf(" 移動次數(shù) 比較次數(shù) n"); printf(" -n"); printf(" 直接插入 %6d %8d n ",a1,b1); printf(" 希爾排序 %6d %8d n ",a2,b2); printf(" 冒泡排序 %4d %8d n ",a3,b3); printf(" 快速排序 %4d %8d n ",a4,b4); printf(" 簡單選擇 %4d %8d

33、 n ",a5,b5); printf(" 堆的排序 %4d %8d n ",a6,b6); printf(" - n");main()char ch;int i,j,t,k; printf("*n "); printf("請選擇初始時數(shù)的順序n"); printf("1-完全有序的情況n"); printf("2-逆序的情況n"); printf("3-隨機排序的情況n"); printf("0-退出n"); printf(

34、"*n"); ch=getch(); switch(ch) case '1': rand(); for(i=0;i<s;i+) printf("%5d",ai=rand(5); for(i=0;i<s-1;i+) for(j=i+1;j<s;j+) if(ai>aj) t=ai; ai=aj; aj=t; printf("完全有序的數(shù)列為:n"); for(i=0;i<s;i+) printf("%5d",ai); printf("n"); for(

35、i=1;i<7;i+) printf("請選擇排序算法n"); printf(" 冒泡排序-1n"); printf(" 直接插入排序-2n"); printf(" 簡單選擇排序-3n"); printf(" 快速排序-4n"); printf(" 希爾排序-5n"); printf(" 堆排序-6n"); printf(" 退出-0n"); ch=getch(); switch(ch) case '0':exit

36、(0); case'1': Bubblle_sort(a,s);break; case'2': Straight_insert_sort(a,s);break; case'3': Simple_select_sort(a,s);break; case'4': Quick_sort(a,0,s-1);break; case'5': Shell_sort(a,s);break; case'6': Heap_sort(a,s);break; default:exit(0); break; case 

37、9;2': rand(); for(i=0;i<s;i+) printf("%5d",ai=rand(5); for(i=0;i<s-1;i+) for(j=i+1;j<s;j+) if(ai<aj) t=ai; ai=aj; aj=t; printf("逆序的數(shù)列為:n"); for(i=0;i<s;i+) printf("%5d",ai); printf("n"); for(i=0;i<7;i+) printf("請選擇排序算法n"); print

38、f(" 冒泡排序-1n"); printf(" 直接插入排序-2n"); printf(" 簡單選擇排序-3n"); printf(" 快速排序-4n"); printf(" 希爾排序-5n"); printf(" 堆排序-6n"); printf(" 退出-0n"); ch=getch(); switch(ch) case '0':exit(0); case'1': Bubblle_sort(a,s);break; case'2': Straight_insert_sort(a,s);break; case'3': Simple_select_sort(a,s);break; case'4': Quick_sort(a,0,s-1);break; case