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

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告的主要內(nèi)容：一、 設(shè)計(jì)題目 二、 運(yùn)行環(huán)境（軟、硬件環(huán)境） 三、 算法設(shè)計(jì)的思想 四、 算法的流程圖 五、 算法設(shè)計(jì)分析 六、 源代碼 七、 運(yùn)行結(jié)果分析 八、 收獲及體會 一、 設(shè)計(jì)題目：排序算法比較 設(shè)計(jì)目的： 1掌握各種排序的基本思想。 2掌握各種排序方法的算法實(shí)現(xiàn)。 3掌握各種排序方法的優(yōu)劣分析及花費(fèi)的時間的計(jì)算。 4掌握各種排序方法所適應(yīng)的不同場合。 設(shè)計(jì)內(nèi)容和要求： 利用隨機(jī)函數(shù)產(chǎn)生3000個隨機(jī)整數(shù)，利用插入排序、起泡排序、選擇排序、快速排序、堆排序、歸并排序等排序方法進(jìn)行排序，并統(tǒng)計(jì)每一種排序上機(jī)所花費(fèi)的時間。 二、 運(yùn)行環(huán)境（軟、硬件環(huán)境） 這次使用的編譯

2、軟件是C-FREE5，該軟件感覺比VC+6.0和TC要好使用一些，查找錯誤時非常方便，調(diào)試也非常方便。硬件是計(jì)算機(jī)。 三、 算法設(shè)計(jì)的思想：首先設(shè)置主菜單，菜單主要有7個功能，分別是6種排序算法以及退出系統(tǒng)的功能。每輸入相應(yīng)的數(shù)字就對應(yīng)一種功能，主程序會根據(jù)所選的功能命令來執(zhí)行相應(yīng)的操作。以下主要講一下6種排序算法的思想。插入排序：先將第一個數(shù)看作是一個有序序列，然后從第二個記錄開始，依次將未排序的記錄插入到這個有序的序列中去，直到整個文件中的全部記錄排序完畢。在排序的過程中，前面的記錄序列是已經(jīng)排好序的，而后面的記錄序列有待排序處理。冒泡排序：假設(shè)待排序的文件為（R1，R2，Rn），對應(yīng)的關(guān)

3、鍵字為（K1，K2，Kn）。從K1開始，依次比較兩個相鄰的關(guān)鍵字Ki和Ki+1(i=1,2,3,n-1).若Ki Ki+1,則交換Ri和Ri+1的位置；否則，不交換。經(jīng)過一遍處理之后，其中關(guān)鍵字最大的記錄移到了第N個位置上，然后再對前面的N-1個記錄進(jìn)行第二遍排序，重復(fù)上敘過程。繼續(xù)進(jìn)行下去，直到不需要交換記錄為止。選擇排序：n個記錄的文件的直接選擇排序可經(jīng)過n-1趟直接選擇排序得到有序結(jié)果：初始狀態(tài)：無序區(qū)為R1.n，有序區(qū)為空。第1趟排序在無序區(qū)R1.n中選出關(guān)鍵字最小的記錄Rk，將它與無序區(qū)的第1個記錄R1交換，使R1.1和R2.n分別變?yōu)橛涗泜€數(shù)增加1個的新有序區(qū)和記錄個數(shù)減少1個的新

4、無序區(qū)。第i趟排序第i趟排序開始時，當(dāng)前有序區(qū)和無序區(qū)分別為R1.i-1和Ri.n(1in-1)。該趟排序從當(dāng)前無序區(qū)中選出關(guān)鍵字最小的記錄Rk，將它與無序區(qū)的第1個記錄Ri交換，使R1.i和Ri+1.n分別變?yōu)橛涗泜€數(shù)增加1個的新有序區(qū)和記錄個數(shù)減少1個的新無序區(qū)。這樣，n個記錄的文件的直接選擇排序可經(jīng)過n-1趟直接選擇排序得到有序結(jié)果?？焖倥判颍?附設(shè)兩個指針LOW和HIGH，它們的初值分別是LOW和HIGH，設(shè)樞軸記錄的關(guān)鍵字的記錄為KEY，然后首先從HIGH所指的位置起向前搜索到第一個關(guān)鍵小于KEY的記錄和樞軸記錄互相交換，從LOW所指的位置起向后搜索，找到第一個關(guān)鍵字大于KEY的記錄

5、和樞軸記錄互相交換，重復(fù)這兩步的操作直到LOW=HIGH為止。歸并排序：假設(shè)初始的序列含有N個記錄，則這些記錄可以看成是N個有序序列的子序列，每個子序列的長度為1，然后兩兩歸并，得到N/2個長度為2或1的有序序列，再兩兩歸并如此重復(fù)，直到得到一個長度為N的有序序列為止。堆排序：將待排序的記錄按照堆的定義建初堆，并輸出堆頂元素，然后調(diào)整剩余的記錄序列，利用篩選法進(jìn)行N-1次篩選。新篩選成的堆會越來越小，而新的堆后面有序關(guān)鍵字會越來越多，最后使得待排序的記錄成為一個有序的序列。四、 算法的流程圖 主程序輸入數(shù)字退 出 系 統(tǒng)堆 排 序歸 并 排 序快 速 排 序選 擇 排 序冒 泡 排 序插 入

6、排 序插入排序 結(jié)束五、 算法設(shè)計(jì)分析 幾種排序方法的性能比較：排序方法 平均時間復(fù)雜度 最壞時間復(fù)雜度 輔助存儲空間插入排序 O（n*n） O(n*n) O(1)快速排序 O(n log2 n) O(n*n) O(log h)堆排序 O(n log2 n) O(n log2n) O(1)歸并排序 O(n log2 n) O(n log2 n) O(n)選擇排序：1）關(guān)鍵字比較次數(shù)無論文件初始狀態(tài)如何，在第i趟排序中選出最小關(guān)鍵字的記錄，需做n-i次比較，因此，總的比較次數(shù)為：n(n-1)/2=0(n2)（2）記錄的移動次數(shù) 當(dāng)初始文件為正序時，移動次數(shù)為0,文件初態(tài)為反序時，每趟排序均要執(zhí)行

7、交換操作，總的移動次數(shù)取最大值3(n-1)。直接選擇排序的平均時間復(fù)雜度為O(n2)。冒泡排序：其算法時間復(fù)雜度是O(n2)。 其中穩(wěn)定的排序有以下幾種：冒泡排序，插入排序，歸并排序。不穩(wěn)定的排序有：選擇排序，堆排序，快速排序。 六、 源代碼 #include stdio.h #include time.h#include malloc.h#include stdlib.h#include#include#include int menu_select()int c;printf( 按任意鍵進(jìn)入系統(tǒng):nn);getch();printf( 歡迎來到排序系統(tǒng) ！nn);printf( * 菜 單

8、*nn);printf( 0.使用插入排序n);printf( 1.使用冒泡排序n);printf( 2.使用選擇排序n);printf( 3.使用快速排序n);printf( 4.使用歸并排序n);printf( 5.使用堆排序n);printf(nn 6.退出n);printf( * 菜 單*nn);do printf(n 輸入你想要使用的排序法的序號(06):); scanf(%d,&c);while(c6);return c; /*插入排序*/void insert(int *a,int n) int i,j,temp; for(i=1;i=0&tempaj) /*從ai-1開始找比a

9、i小的數(shù)，同時把數(shù)組元素向后移*/ aj+1=aj; j-; aj+1=temp; /*插入*/ /*冒泡排序*/void bubble(int *a,int n) /*定義兩個參數(shù)：數(shù)組首地址與數(shù)組大小*/ int i,j,temp; for(i=0;in-1;i+) for(j=i+1;jaj) temp=ai; ai=aj; aj=temp; /*選擇排序*/void selectsort(int *a,int n) int i,j,k,temp; for(i=0;in-1;i+) k=i; /*給記號賦值*/ for(j=i+1;jaj) k=j; /*是k總是指向最小元素*/ if(

10、i!=k) /*當(dāng)k!=i是才交換，否則ai即為最小*/ temp=ai; ai=ak; ak=temp; /*快速排序*/void quick(int *a,int i,int j) int m,n,temp; int k; m=i; n=j; k=a(i+j)/2; /*選取的參照*/ do while(amk&mk&ni) n-; /* 從右到左找比k小的元素*/ if(m=n) /*若找到且滿足條件，則交換*/ temp=am; am=an; an=temp; m+; n-; while(m=n); if(mi) quick(a,i,n); void merge(int a,int l

11、ow,int middle,int high)int h,i,j,k;int b3000;h=low;i=low;j=middle+1;while(h=middle&j=high)if(ahmiddle)for(k=j;k=high;k+)bi=ak;i+; elsefor(k=h;k=middle;k+) bi=ak;i+;for(k=low;k=high;k+)ak=bk;/*歸并排序函數(shù)的具體實(shí)現(xiàn)*/void mergesort(int a,int low,int high)int middle;if(lowhigh)middle=(low+high)/2;mergesort(a,low

12、,middle);mergesort(a,middle+1,high);merge(a,low,middle,high);/*堆排序函數(shù)*/void sift(int r,int k,int m)int i,j,t,finished=0;t=rk;i=k;j=2*i;while(j=m&finished=0)if(jm&rj=rj)finished=1;elseri=rj;i=j;j=2*i;ri=t;void create_heap(int r,int length)int i,n=length;for(i=n/2;i=1;i-)sift(r,i,n);void heap_sort(int

13、r,int length)int i,t,n;create_heap(r,length);n=length;for(i=n;i=2;i-)t=ri;ri=r1;r1=t;sift(r,1,i-1);int main() /*主函數(shù)*/ srand(time(NULL); int i,a3000,n=3000;float start,end; /* 開始時間,結(jié)束時間*/ for( i=0;i3000;i+) ai=rand()%5000; /*產(chǎn)生5000以內(nèi)的3000個隨機(jī)函數(shù)*/ for(;) switch(menu_select() case 0: /*選擇插入排序*/ start=(f

14、loat)clock(); insert(a,3000); printf(the sorted numbers:n); for(i=0;in;i+) printf(%8d,ai); printf(n); end=(float)clock(); printf( 插入排序時間是:%.f毫秒n,end-start); break; case 1: /*選擇冒泡排序*/ start=(float)clock(); bubble(a,3000); printf(the sorted numbers:n); for(i=0;in;i+) printf(%8d,ai); printf(n); end=(fl

15、oat)clock(); printf( 冒泡排序時間是:%.f毫秒n,(end-start); break; case 2: /*選擇排序*/ start=(float)clock(); selectsort(a,3000); printf(the sorted numbers:n); for(i=0;in;i+) printf(%8d,ai); printf(n); end=(float)clock(); printf( 選擇排序時間是:%.f毫秒n,(end-start); break; case 3: /*快速排序*/ start=(float)clock(); quick(a,0,n

16、-1); printf(the sorted numbers:n); for(i=0;in;i+) printf(%8d,ai); printf(n); end=(float)clock(); printf( 快速排序時間是:%.f毫秒n,(end-start); break; case 4: /*歸并排序*/ start=(float)clock(); mergesort(a,0,n-1); printf(the sorted numbers:n); for(i=0;in;i+) printf(%8d,ai); printf(n); end=(float)clock(); printf( 歸并排序時間是:%.f毫秒n,(end-start); break; case 5: /*堆排序*/ start=(float)clock(); heap_sort(a,n); printf(the sorted numbers:n); for(i=0