數(shù)據(jù)結構課程設計-排序算法實現(xiàn)

數(shù)據(jù)結構與算法課程設計成果報告排序算法實現(xiàn)學生學號： 學生姓名： 學 院： 計算機學院 專業(yè)班級： 軟件工程 1341 專業(yè)課程： 數(shù)據(jù)結構與算法 指導教師： 2014 年 12 月 29 日題 目排序算法實現(xiàn)考核項目考核內容得分平時考核（30分）出勤情況、態(tài)度、效率；知識掌握情況、基本操作技能、知識應用能力、獲取知識能力系統(tǒng)設計（20分）分析系統(tǒng)的功能模塊編程調試（20分）實現(xiàn)系統(tǒng)的各個功能模塊，并完成調試回答問題（15分）回答老師針對課程設計提出的問題課程設計報告撰寫（10分）嚴格按照規(guī)范要求完成課程設計報告源代碼（5分）按照規(guī)范要求完成課程設計源代碼的排版總 評 成 績指導教師評語： 日期： 年 月 日目 錄1課程設計目標與任務11.1 課程設計目標11.2 課程設計任務11.3 課程設計基本要求12 分析與設計22.1 題目需求分析22.2 存儲結構設計32.3 算法描述42.4 程序流程圖72.5 程序測試說明73 程序清單84.測試134.1 測試數(shù)據(jù)134.2 測試結果分析135 總結14參考文獻151 課程設計目標與任務1.1 課程設計目標數(shù)據(jù)結構課程設計是在學完數(shù)據(jù)結構課程之后的實踐教學環(huán)節(jié)。該實踐教學是軟件設計的綜合訓練,包括問題分析，總體結構設計用戶界面設計，程序設計基本技能和技巧。要求學生在設計中逐步提高程序設計能力培養(yǎng)科學的軟件工作方法學生通過數(shù)據(jù)結構課程設計各方面得到鍛煉。1.2 課程設計任務設計排序相關函數(shù)庫，以便在程序設計中調用，要求設計程序，產(chǎn)生20000個隨機數(shù)，完成下面功能：（1）對這些數(shù)分別進行直接插入排序、折半插入排序、希爾排序、起泡排序、快速排序、簡單選擇排序，堆排序，2路-歸并排序等排序，并把排序結果進行保存。（2）最好能借助語言環(huán)境實現(xiàn)圖形顯示功能，以便將抽象的數(shù)據(jù)結構以圖形方式顯示出來，將復雜的運行過程以動態(tài)方式顯示出來；（3）給出若干例程，演示通過調用自己所寫程序來實現(xiàn)相關問題的要求。1.3 課程設計基本要求嚴格按照題意要求，獨立進行設計，不能隨意更改。若確因條件所限，必須要改變課題要求時，應在征得指導教師同意的前提下進行。學生應制定實習工作計劃，認真完成實習的各個環(huán)節(jié)，并在老師的指導下認真組織實習工作，撰寫實習報告，做好實習總結。2 分析與設計2.1 題目需求分析1.直接插入排序思路：設有一組關鍵字K1,K2.Kn，排序開始便認為K1是一個有序的序列，讓K2插入到表長為1的有序序列，使之成為一個表長為2的有序序列，讓K3插入到表長為2的有序序列，使之成為表長為3的有序序列，依次類推，最后Kn插入到上述表長為n-1的有序序列，得到一個表長為n的有序序列。2.折半插入排序思路：在將一個新元素插入已排好序的數(shù)組的過程中，尋找插入點時，將待插入?yún)^(qū)域的首元素設置為alow,末元素設置為ahigh，則輪比較時將待插入元素與am,其中m=(low+high)/2相比較,如果比參考元素小，則選擇alow到am-1為新的插入?yún)^(qū)域(即high=m-1)，否則選擇am+1到ahigh為新的插入?yún)^(qū)域（即low=m+1），如此直至low=high不成立，即將此位置之后所有元素后移一位，并將新元素插入ahigh+1。3.希爾排序思路：先取一個小于n的整數(shù)d1作為第一個增量，把文件的全部記錄分組。所有距離為d1的倍數(shù)的記錄放在同一個組中。先在各組內進行直接插入排序；然后，取第二個增量d2,d2d1,再將到d2作為增量繼續(xù)分組，再進行直接插入排序，依次向下取值，直到完成排序。4.起泡排序思路：比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最后一對。在這一點，最后的元素應該會是最大的數(shù)。針對所有的元素重復以上的步驟，除了最后一個。持續(xù)每次對越來越少的元素重復上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較。5.快速排序思路：快速排序的實現(xiàn)基于分治法，具體分為三個步驟。假設待排序的序列為Lm.n。序列Lm . n被劃分成兩個可能為空的子序列Lm . pivot-1和Lpivot+1 . n，使Lm . pivot-1的每個元素均小于或等于Lpivot，同時Lpivot+1. n的每個元素均大于Lpivot。其中Lpivot稱為這一趟分割中的主元（也稱為樞軸、支點）。通過遞歸調用快速排序，對子序列Lm . pivot-1和Lpivot+1 . r排序。 由于兩個子序列是就地排序的，所以對它們的合并不需要操作，整個序列Lm . n已排好序。6.簡單選擇排序思路：序序列的記錄個數(shù)為。i取1,2,n-1,從所有n-i+1個記錄（R,Ri+1,Rn中找出排序碼最小的記錄，與第個記錄交換。執(zhí)行n-1趟 后就完成了記錄序列的排序。2.2 存儲結構設計此程序采用的是線性表的動態(tài)順序存儲結構：#define LIST_INIT_SIZE 100/線性表存儲空間的初始分配量#define LISTINCREMENT 10/線性表存儲空間的分配增量Typedef structElemType *elem;/存儲空間基址Int length;/當前長度Int listsize;/當前分配的存儲容量（以sizeof(ElemType)為單位）SqList;上述定義中，數(shù)組指針elem指示存儲空間基址，length表示線性表的當前長度，對線性表的初始化操作就是為順序表預定義大小的數(shù)組空間，并將線性表的當前長度設為“0”，listsize指示當前分配的存儲空間大小，一旦元素插入而空間不足，可進行再分配。1.3 算法描述1.直接插入排序 設置R0為哨兵，將剩下的數(shù)值逐個進行插入，直至完成一趟排序：void InsertSort ( elem R , int n) / 對記錄序列R1.n作直接插入排序。 for ( i=2; i=n; +i ) R0 = Ri; / 復制為監(jiān)視哨 for ( j=i-1; R0 Rj; -j ) Rj+1 = Rj; / 記錄后移 Rj+1 = R0; / 插入到正確位置 / InsertSort2.折半插入排序因為R1.i-1是一個按關鍵字有序的序列，則可以利用折半查找實現(xiàn)“在R1.i-1中查找Ri的插入位置：void BInsertSort (elem R ， int n) / 對記錄序列R1.n作折半插入排序。 for ( i=2; i=n; +i ) R0 = Ri; / 將Ri暫存到R0 low = 1; high = i-1; while ( low = high) /在Rlow.high中折半查找插入的位置 m = (low+high)/2; / 折半 if (R0 =high+1; -j ) Rj+1 = Rj; / 記錄后移 Rhigh+1 = R0; / 插入 / BInsertSort3.希爾排序先取一個正整數(shù)d1n，把所有相隔d1的記錄放一組，組內進行直接插入排序，然后取d2d1，重復上述分組和排序操作；直至di=1，即所有記錄放進一個組中排序為止：void ShellInsert ( elem R , int dk ) / 對待排序列R作一趟希爾插入排序 for ( i=dk+1; i=n; +i ) if ( Ri Ri-dk) void ShellSort (elem R , int d , int t) / 按增量序列d 0.t-1對順序表L作希爾排序。 for ( k=0; k0 & R01) for ( j = 1; j i; j+ ) if (R j+1 R j ) Swap(R j , R j+1 ); /if / while / BubbleSort5.快速排序選定一個中間數(shù)作為參考，所有元素與之比較，小的調到其左邊，大的調到其右邊：int Partition (Elem R, int low, int high) / 交換記錄子序列Rlow.high中的記錄，使樞軸記錄到位，并返回其所/ 在位置，此時，在它之前（后）的記錄均不大（?。┯谒黂0 = Rlow; / 用子表的第一個記錄作樞軸記錄pivotkey = Rlow; / 樞軸記錄關鍵字while (lowhigh) / 從表的兩端交替地向中間掃描while(low=pivotkey)-high;Rlow = Rhigh; / 將比樞軸記錄小的記錄移到低端while (lowhigh & Rlow=pivotkey) +low;Rhigh = Rlow; / 將比樞軸記錄大的記錄移到高端Rlow = R0; / 樞軸記錄到位return low; / 返回樞軸位置 / Partitionvoid QSort (Elem R, int low, int high) / 對記錄序列Rlow.high進行快速排序if (low high) / 長度大于1pivotloc = Partition(L, low, high); / 將L.rlow.high一分為二QSort(L, low, pivotloc-1); / 對低子表遞歸排序，pivotloc是樞軸位置QSort(L, pivotloc+1, high);/ 對高子表遞歸排序 / Qsort6.簡單選擇排序在待排序的數(shù)據(jù)中選出最大（?。┑脑胤旁谄渥罱K的位置：Void SelectSort(SqList &L)/對順序表做簡單選擇排序for(i=1;iL.length;+i)/選擇第i小的記錄，交換到位j=SelectMinKey(L,i);/在L.riL.length中選擇key最小記錄if(i!=j)Lri-L.rj;/與第i個記錄交換/ SelectSort開始2.4 程序流程圖顯示菜單輸入序號簡單選擇排序快速排序起泡排序希爾排序折半插入排序直接插入排序按輸入序號輸出結果結束圖1-2程序執(zhí)行流程圖開始執(zhí)行后，會出現(xiàn)提示語句，提示1-6分別代表6種排序方法，對于生成的數(shù)組，點擊1-6任意數(shù)字，調用相應的排序方法進行排序。輸出結果后，按任意鍵結束。2.5 程序測試說明主函數(shù)會調用rand()方法，隨機產(chǎn)生指定數(shù)目數(shù)值。并將數(shù)值賦予指定數(shù)組，通過提示語句輸入16數(shù)值，16分別代表不同的排序方式，當輸入數(shù)字1時，通過switch語句，將執(zhí)行直接插入排序函數(shù)，然后通過輸出函數(shù)，輸出所需結構。3 程序清單#include#include#include#define MAXE 20000typedef int KeyType;typedef struct /*記錄類型*/KeyType key; /*關鍵字項*/ /InfoType data; /*其他數(shù)據(jù)項,類型為InfoType*/ RecType;void InsertSort(RecType R,int length);/直接插入排序void BInsertSort (RecType R,int low,int high,int length);/折半插入排序void ShellSort(RecType R,int n);/希爾排序void bubble_sort(RecType R,int length);/起泡排序int FindPos(RecType R,int low,int high);void QuickSort(RecType R,int low,int high);int SelectMinKey(RecType R,int i,int length);void SelectSort(RecType R,int length);/簡單選擇排序void showSort(RecType R);/快速排序void showSort_F(RecType R);int main(void) int val;int i;RecType RMAXE;srand(unsigned)time(NULL); for(i=0;i=10;i+) Ri.key=(rand()%100+1); printf(產(chǎn)生的隨機數(shù)序列為：); for(i=0;i=10;i+) printf(%3d,Ri.key); printf(n); printf(隨機輸入1到6數(shù)字：); scanf(%d,&val); switch(val) case 1: InsertSort(R,10); printf(隨機數(shù)經(jīng)直接插入排序后：); showSort(R); break; case 2:BInsertSort(R,1,10,10); printf(隨機數(shù)經(jīng)折半插入排序后：); showSort(R); break; case 3:ShellSort(R,10); printf(隨機數(shù)經(jīng)希爾插入排序后：); showSort_F(R); break; case 4:bubble_sort(R,10); printf(隨機數(shù)經(jīng)起泡排序后：); showSort_F(R); break; case 5:QuickSort(R,0,9); printf(隨機數(shù)經(jīng)快速排序后：); showSort_F(R); case 6:SelectSort(R,10); printf(隨機數(shù)經(jīng)簡單選擇排序后：); showSort_F(R); return 0;void InsertSort(RecType R,int length) / 對數(shù)組a作直接插入排序 int i,j; for(i=2;i=length;+i) if(Ri.keyRi-1.key) / 需將ai插入有序子表 R0.key=Ri.key; / 復制為哨兵 Ri.key=Ri-1.key; for(j=i-2;R0.keyRj.key;-j) Rj+1.key=Rj.key; / 記錄后移 Rj+1.key=R0.key; / 插入到正確位置 void BInsertSort (RecType R,int low,int high,int length) int m; for ( int i=2; i=length; +i ) R0.key = Ri.key; / 將Ri暫存到R0 low = 1; high = i-1; while ( low = high) /在Rlow.high中折半查找插入的位置 m = (low+high)/2; / 折半 if (R0.key =high+1; -j ) Rj+1.key = Rj.key; / 記錄后移 Rhigh+1.key = R0.key; / 插入 / BInsertSortvoid ShellSort(RecType R,int n)/*希爾排序算法*/int i,j,d,k;RecType temp;d=n/2;/*d取初值n/2*/while (d0) for (i=d;i=0 & Rj.keyRj+d.key) temp=Rj; /*Rj與Rj+d交換*/Rj=Rj+d;Rj+d=temp;j=j-d;printf( d=%d: ,d);/*輸出每一趟的排序結果*/for (k=0;kn;k+)printf(%3d,Rk.key);printf(n); d=d/2; /*遞減增量d*/void bubble_sort(RecType R,int length) / 將a中整數(shù)序列重新排列成自小至大有序的整數(shù)序列(起泡排序) int i,j,t; for(i=0;ilength-1;i+) for(j=i+1;jRj.key) t=Ri.key; Ri.key=Rj.key; Rj.key=t; void QuickSort(RecType R,int low,int high)int pos;if(lowhigh)pos=FindPos(R,low,high); QuickSort(R,low,pos-1);QuickSort(R,pos+1,high);int FindPos(RecType R,int low,int high) int val=Rlow.key; while(lowhigh) while(low=val) -high; Rlow.key=Rhigh.key; while(lowhigh&Rlow.key=val) +low; Rhigh.key=Rlow.key; Rlow.key=val; return high; int SelectMinKey(RecType R,int i,int length) / 返回在ai.length中key最小的記錄的序號 int min; int j,k; k=i; / 設第i個為最小 min=Ri.key; for(j=i+1;jlength;j+) if(Rj.keymin) / 找到更小的 k=j; min=Rj.key; return k; void SelectSort(RecType R,int length) / 對數(shù)組a作簡單選擇排序 int i,j; int t; for(i=0;ilength-1;+i) / 選擇第i小的記錄，并交換到位 j=SelectMinKey(R,i,length); / 在ai.length中選擇最小的記錄 if(i!=j) / 與第i個記錄交換 t=Ri.key; Ri.key=Rj.key; Rj.key=t; void showSort(RecType R)int i;for(i=1;i=10;i+)printf(%d ,Ri.key);printf(n);void showSort_F(RecType R)int i;for(i=0;i10;i+)printf(%d ,Ri.key);printf(n);4 測試4.1 測試數(shù)據(jù)由函數(shù)rand()產(chǎn)生的隨機數(shù)進行測試。4.2 測試結果分析圖1-3直接插入排序當輸入數(shù)字1時，主函數(shù)通過switch語句調用直接插入排序，對數(shù)組進行從小到大的排序。圖1-4冒泡排序當輸入數(shù)字4時，主函數(shù)通過switch語句調用冒泡排序，對數(shù)組進行從小到大的排序。5 總結通過這次課程設計的學習讓我學會了許多，讓我對專業(yè)知識有了初步的了解。在這次課程設計中，首先實現(xiàn)隨機數(shù)的生成，將生成的指定數(shù)目的隨機數(shù)一一對應的賦予定義的空數(shù)組，經(jīng)選擇語句分別執(zhí)行直接插入排序，折半插入排序，希爾排序，起泡排序，快速排序，簡單選擇排序等6種排序對數(shù)組中的數(shù)值進行排序。這次課程設計還有許多不足，如部分排序方法編程代碼過于復雜，此外，由于編程各種排序方法的區(qū)別較大，使用了不同的輸出函數(shù)，增加了程序的復雜性。此外，由于能力有限，還有無法實現(xiàn)的2種排序。但我也學到了很多東西，如，掌握一些排序方法的實現(xiàn)，熟悉了編寫代碼的一般步驟：思考問題，寫出解決方案，寫出偽代碼，完成代碼，調試程序。我從編寫過程中，發(fā)現(xiàn)自己更多的不足，如對C語言的掌握不夠牢靠，對于C語言各種函數(shù)的調用也不夠靈活等。希望在以后的編程過程中，能更加耐心和細心，不熟悉也不要慌張，不慌不忙的進行程序編寫和調試。參考文獻1數(shù)據(jù)結構（C語言版）嚴蔚敏 清華大學出版社 20022數(shù)據(jù)結構-C語言描述 王路群 中國水利水電出版社 20073數(shù)據(jù)結構實驗教程（C語言版） 王國鈞 清華大學出版社 20094數(shù)據(jù)結構題集嚴蔚敏,吳偉民編 清華大學出版社 20025C語言程序設計譚浩強 清華大學出版社6C語言入門經(jīng)典霍頓（美）清華大學出版社#include#include#include#define MAXE 20000typedef int KeyType;typedef struct /*記錄類型*/KeyType key; /*關鍵字項*/ /InfoType data; /*其他數(shù)據(jù)項,類型為InfoType*/ RecType;void InsertSort(RecType R,int length);/直接插入排序void BInsertSort (RecType R,int low,int high,int length);/折半插入排序void ShellSort(RecType R,int n);/希爾排序void bubble_sort(RecType R,int length);/起泡排序int FindPos(RecType R,int low,int high);void QuickSort(RecType R,int low,int high);int SelectMinKey(RecType R,int i,int length);void SelectSort(RecType R,int length);/簡單選擇排序void showSort(RecType R);/快速排序void showSort_F(RecType R);int main(void) int val;int i;RecType RMAXE;srand(unsigned)time(NULL); for(i=0;i=10;i+) Ri.key=(rand()%100+1); printf(產(chǎn)生的隨機數(shù)序列為：); for(i=0;i=10;i+) printf(%3d,Ri.key); printf(n); printf(隨機輸入1到6數(shù)字：); scanf(%d,&val); switch(val) case 1: InsertSort(R,10); printf(隨機數(shù)經(jīng)直接插入排序后：); showSort(R); break; case 2:BInsertSort(R,1,10,10); printf(隨機數(shù)經(jīng)折半插入排序后：); showSort(R); break; case 3:ShellSort(R,10); printf(隨機數(shù)經(jīng)希爾插入排序后：); showSort_F(R); break; case 4:bubble_sort(R,10); printf(隨機數(shù)經(jīng)起泡排序后：); showSort_F(R); break; case 5:QuickSort(R,0,9); printf(隨機數(shù)經(jīng)快速排序后：); showSort_F(R); case 6:SelectSort(R,10); printf(隨機數(shù)經(jīng)簡單選擇排序后：); showSort_F(R); return 0;void InsertSort(RecType R,int length) / 對數(shù)組a作直接插入排序 int i,j; for(i=2;i=length;+i) if(Ri.keyRi-1.key) / 需將ai插入有序子表 R0.key=Ri.key; / 復制為哨兵 Ri.key=Ri-1.key; for(j=i-2;R0.keyRj.key;-j) Rj+1.key=Rj.key; / 記錄后移 Rj+1.key=R0.key; / 插入到正確位置 void BInsertSort (RecType R,int low,int high,int length) int m; for ( int i=2; i=length; +i ) R0.key = Ri.key; / 將Ri暫存到R0 low = 1; high = i-1; while ( low = high) /在Rlow.high中折半查找插入的位置 m = (low+high)/2; / 折半 if (R0.key =high+1; -j ) Rj+1.key = Rj.key; / 記錄后移 Rhigh+1.key = R0.key; / 插入 / BInsertSortvoid ShellSort(RecType R,int n)/*希爾排序算法*/int i,j,d,k;RecType temp;d=n/2;/*d取初值n/2*/while (d0) for (i=d;i=0 & Rj.keyRj+d.key) temp=Rj; /*Rj與Rj+d交換*/Rj=Rj+d;Rj+d=temp;j=j-d;printf( d=%d: ,d);/*輸出每一趟