完整的課程設(shè)計(jì)

1、目 錄摘 要 .2前 言.3正 文.4一、采用類 C語(yǔ)言定義相關(guān)的數(shù)據(jù)類型.4二、程序操作過(guò)程圖.6三、程序流程圖.7四、程序調(diào)試分析和結(jié)果.9五、源程序（帶注釋）.11六、各種排序算法的性能分析.20總 結(jié).21心 得 體 會(huì).23參 考 文 獻(xiàn).24致 謝.26附件 I 部分源程序代碼.27摘 要排序（sorting）是計(jì)算機(jī)程序設(shè)計(jì)的一種重要操作，他的功能是將一個(gè)數(shù)據(jù)元素（或記錄）的任意序列，重新排列一個(gè)按關(guān)鍵字有序的序列。由于待排序的記錄數(shù)量不同，使得排序過(guò)程中涉及的儲(chǔ)存器不同，可將排序方法分為兩大類：一類是內(nèi)部排序，指的是待排序記錄存放在計(jì)算機(jī)隨機(jī)儲(chǔ)存器中進(jìn)行的排序過(guò)程；另一類是外部

2、排序，指的是待排序記錄的數(shù)量很大，以致內(nèi)存一次不能容納全部記錄，在排序過(guò)程中尚需對(duì)外存進(jìn)行訪問(wèn)的排序過(guò)程。內(nèi)部排序又分為：插入排序、快速排序、選擇排序、歸并排序和基數(shù)排序。其中插入排序又分為：直接插入排序、其他插入排序和希爾排序；選擇排序分為：簡(jiǎn)單選擇排序、樹(shù)形選擇排序和堆排序；基數(shù)排序又分為：多關(guān)鍵字的排序和鏈?zhǔn)交鶖?shù)排序。本次課程設(shè)計(jì)就是內(nèi)部排序中的幾個(gè)排序方法。關(guān)鍵字： 內(nèi)部排序關(guān)鍵字重新排列前 言“天之道，損有余而補(bǔ)不足”，自然萬(wàn)物發(fā)展的規(guī)律， 都是傾向于消除差異。無(wú)獨(dú)有偶，熱力學(xué)第二定律也指出：任意封閉的系統(tǒng)，都會(huì)朝著熵增加的方向發(fā)展。從信息論的角度來(lái)看，也就是傾向于更加無(wú)序。然而，“

3、 人之道，則不然，損不足以奉有余”，人總是偏好有序。就數(shù)據(jù)處理而言，有序性的確十分有用。所謂排序， 就是按照某種次序，重新排列某一序列中的所有元素。為此，任意一對(duì)元素之間 都應(yīng)該能比較大小，即在所有元素之間可以定義一個(gè)全序關(guān)系。排序不僅可以作為查找等操作的預(yù)處理計(jì)算，而且也是實(shí)際應(yīng)用中需要反復(fù)進(jìn)行的一項(xiàng)基本操作。前言很多涉及計(jì)算器程序的算法都是以棧的相關(guān)操作為基礎(chǔ)，通過(guò)對(duì)計(jì)算器算法的設(shè)計(jì)，有利于在學(xué)習(xí)中更好的理解棧及其相關(guān)的操作。但是，這款計(jì)算器主要是通過(guò)數(shù)組進(jìn)行的。沒(méi)有直接使用棧，但用到棧的思想。我們?cè)趯懗绦驎r(shí)，大框架已成的情況下，仍然發(fā)現(xiàn)有些錯(cuò)誤很難找到，對(duì)于這樣的問(wèn)題，可以利用計(jì)算機(jī)糾錯(cuò)

4、功能，先運(yùn)行，再根據(jù)題提示修改和完善程序。在計(jì)算器用到的算法中，c 語(yǔ)言算法可讀性很強(qiáng)，一方面，是因?yàn)?c 語(yǔ)言是高級(jí)語(yǔ)言，是面向程序員的語(yǔ)言，二是 c 語(yǔ)言的功能是很完備的，可以達(dá)到事半功倍的效果，和其他語(yǔ)言相比量是比較少。正 文一、采用類 C 語(yǔ)言定義相關(guān)的數(shù)據(jù)類型（11、輸入2、選擇3、輸出（21、輸入模塊的功能：利用隨機(jī)函數(shù)產(chǎn)生N 個(gè)數(shù)（超過(guò)20000確，所以在本程序中只隨機(jī)產(chǎn)生100個(gè)數(shù)。create(a,b,&n) 是一個(gè)隨機(jī)函數(shù)，它可以隨機(jī)產(chǎn)生 100個(gè)隨機(jī)數(shù) 。2、選擇模塊的功能：選擇數(shù)字則進(jìn)行對(duì)應(yīng)的排序；選擇字母則進(jìn)行重新產(chǎn)生隨機(jī)數(shù)和退出的操作。1插入排序insertsort

5、(a,n)2希爾排序xiersort(a,n)3快速排序quicksort(a,1,n)4堆排序duisort(a,n)C(c)重新產(chǎn)生20個(gè)隨機(jī)數(shù)create(a,b,&n)N(n)退出程序3、輸出模塊的功能：把利用各種排序方法排好順序的數(shù)輸出到一個(gè)文件夾中。writefile1(a,n)向指定的文件中寫入排序前的數(shù)writefile2(a,n)向指定的文件中寫入用各種排序方法排好序的數(shù)二、程序操作過(guò)程圖開(kāi)始123456插 入排 序希 爾排 序冒 泡排序快 速排序簡(jiǎn)單排序堆排序把利用排序方法排好序的數(shù)輸出到指定的文件夾N(n)C（c）重新產(chǎn)生隨機(jī)數(shù)三、程序流程圖開(kāi)始N(n)退插 入排 序希

6、爾排 序冒 泡排序快 速排序簡(jiǎn)單排序堆（c）重 新產(chǎn) 生隨 機(jī)排序把用各種排序方法排好的數(shù)的順序輸出到指定的文件夾中四、程序調(diào)試分析和結(jié)果（1 100 個(gè)數(shù)，選擇“1序；在選擇“2（3）選擇“34下：（45五、源程序（帶注釋）#include#include#include#include#define SIZE 20000struct elementint key;listSIZE;/創(chuàng)建一個(gè)數(shù)組/int creat()int i,n;int num;n=0;printf(請(qǐng)輸入元素個(gè)數(shù):);scanf(%d,&num);for( i = 0;i num; i+ )listn.key = r

7、and() % 10000;n+;return(n);/輸出數(shù)組/void print(struct element aSIZE,int n)int i;for(i=0;in;i+)printf(%5d,ai .key);printf(n);/保存到文件/void save(struct element aSIZE,int n, char fileName )int m_wr=0; / 寫入 TXT文件變量FILE *fp;if ( ( fp = fopen ( fileName, w ) ) = NULL )printf(File writer errorn);for (int m=0; m

8、n; m+ )m_wr = am.key;fprintf ( fp, %d , m_wr );/ 寫入 TXT中fclose ( fp );/ 直接插入排序/void insert_sort(element a, int n)int i, j;element next;for(i=1; i=0 & next.key =1;i-)ai.key=ai-1.key;k=n/2;while(k=1)for(i=k+1;ia0.key)&(j=0)aj+k.key=aj.key;j=j-k;aj+k=a0;k=k/2;for(i=0;in;i+)ai.key=ai+1.key;printf(輸出希爾排序

9、的結(jié)果:n);/快速排序/int hoare(struct element aSIZE,int l,int h)/分區(qū)處理函數(shù)int i,j;struct element x;i=l;j=h;x.key=ai.key;dowhile(i=x.key)j-;if(ij)ai.key=aj.key;i+;while(ij)&(ai.key=x.key)i+;if(ij)aj.key=ai.key;j-;while(ij);ai.key=x.key;return(i);/堆排序函數(shù)/調(diào)整堆的函數(shù)void heap(struct element aSIZE,int i,int m)/*i是根結(jié)點(diǎn)編號(hào),

10、m是以 i為根的子樹(shù)的最后一個(gè)結(jié)點(diǎn)編號(hào)*/struct element x;int j;x.key=ai.key;j=2*i;/保存記錄內(nèi)容/j 為左孩子編號(hào)while(j=m)if(jaj+1.key) /當(dāng)結(jié)點(diǎn) i有左,右兩個(gè)孩子時(shí),j取關(guān)鍵較小的孩子編號(hào)j+;if(aj.keym,以便結(jié)束循環(huán)ai.key=x.key;/堆排序的主體函數(shù)void heapsort(struct element aSIZE,int n)int i,v;struct element x;for(i=n;i0;i-)ai.key=ai-1.key;for(i=n/2;i=1;i-)heap(a,i,n);for

11、(v=n;v=2;v-)x.key=a1.key;a1.key=av.key;av.key=x.key;heap(a,1,v-1);/堆頂堆尾元素交換/這次比上次少處理一個(gè)記錄for(i=0;in;i+)ai.key=ai+1.key;for(i=0;in/2;i+)int k;k=ai.key;ai.key=an-i-1.key;an-i-1.key=k;void main()int num,l,h,c;clock_t start, end;c=1;char file150 = 直接插入排序.txt;char file250 = 希爾排序.txt;char file350 = 非遞歸的快速排

12、序.txt;char file450 = 堆排序.txt;printf(*歡迎使用本系統(tǒng)學(xué)習(xí)各種排序*n);printf(*溫馨提示：首先請(qǐng)生成用于排序的元素，以便進(jìn)行排序*n);printf(*主菜單*n);printf(*1生成隨機(jī)排序元素*n);printf(*printf(*printf(*printf(*printf(*23450直接插入排序希爾排序*n);*n);*n);*n);*n);非遞歸的快速排序堆排序退出printf(*n);while(c!=0)printf(*請(qǐng)輸入0-5進(jìn)行操作n);scanf(%d,&c);switch(c)case 1:num=creat();pr

13、int(list,num);break;case 2:start = clock();insert_sort(list,num);end = clock();print(list,num);save(list,num, file1) ;printf(The time : %d msn, end - start );break;case 3:start = clock();shell(list,num);end = clock();print(list,num);save(list,num,file2) ;printf(The time : %d msn, end - start );break

14、;case 4:l=0;h=num-1;start = clock();end = clock();printf(輸出遞歸快速排序結(jié)果:n);print(list,num);save(list,num,file3);printf(The time : %d msn, end - start );break;case 5:start = clock();heapsort(list,num);end = clock();print(list,num);save(list,num,file4);printf(The time : %d msn, end - start );break;/main e

15、nd六、各種排序算法的性能分析由于程序不能統(tǒng)計(jì)出運(yùn)行各種算法所需要的時(shí)間，所以在本程序中以各種算法的時(shí)間復(fù)雜度來(lái)分析各種算法的性能。2. 希爾排序：算法的時(shí)間復(fù)雜度為 n的 1.2次冪3. 冒泡排序 ：這是最原始，也是眾所周知的最慢的算法了。他的名字的由來(lái)因?yàn)樗墓ぷ骺磥?lái)象是冒泡。算法的時(shí)間復(fù)雜度為：O(n*n)。當(dāng)數(shù)據(jù)為正序，將不會(huì)有交換，復(fù)雜度為 O(0)。4. 快速排序：算法的平均時(shí)間復(fù)雜度為：log2(n)*n，所有內(nèi)部排。5.簡(jiǎn)單排序：算法的時(shí)間復(fù)雜度為：O(n*n)。6.堆排序：算法的時(shí)間復(fù)雜度為：log2(n)*n綜上：由各種算法的時(shí)間復(fù)雜度比較可知，堆排序和快速排序是漸進(jìn)最優(yōu)的

16、排序算法。總 結(jié)1、插入排序（InsertSort）插入排序通過(guò)把序列中的值插入一個(gè)已經(jīng)排序好的序列中，直到該序列的結(jié)束。插入排序是對(duì)冒泡排序的改進(jìn)。它比冒泡排序快 2 倍。一般不用在數(shù)據(jù)大于 1000的場(chǎng)合下使用插入排序，或者重復(fù)排序超過(guò) 200數(shù)據(jù)項(xiàng)的序列。2、 Shell排序（ShellSort）Shell 排序通過(guò)將數(shù)據(jù)分成不同的組，先對(duì)每一組進(jìn)行排序，然后再對(duì)所有的元素 進(jìn)行一 次插入排序 ，以減 少數(shù)據(jù) 交換和 移動(dòng)的次數(shù) 。平均 效率是O(nlogn)。其中分組的合理性會(huì)對(duì)算法產(chǎn)生重要的影響?，F(xiàn)在多用 D.E.Knuth的分組方法。Shell排序比冒泡排序快 5倍，比插入排序大致

17、快 2倍。Shell排序比起QuickSort，MergeSort，HeapSort 慢很多。但是它相對(duì)比較簡(jiǎn)單，它適合于數(shù)據(jù)量在 5000以下并且速度并不是特別重要的場(chǎng)合。它對(duì)于數(shù)據(jù)量較小的數(shù)列重復(fù)排序是非常好的。3、快速排序（QuickSort）快速排序是一個(gè)就地排序，分而治之，大規(guī)模遞歸的算法。從本質(zhì)上來(lái)說(shuō)，它是歸并排序的就地版本?？焖倥判蚩梢杂上旅嫠牟浇M成。（1） 如果不多于 1個(gè)數(shù)據(jù)，直接返回。（2） 一般選擇序列最左邊的值作為支點(diǎn)數(shù)據(jù)。（3） 將序列分成 2 部分，一部分都大于支點(diǎn)數(shù)據(jù)，另外一部分都小于支點(diǎn)數(shù)據(jù)。（4） 對(duì)兩邊利用遞歸排序數(shù)列。快速排序比大部分排序算法都要快。盡管我

18、們可以在某些特殊的情況下寫出比快速排序快的算法，但是就通常情況而言，沒(méi)有比它更快的了。快速排序是遞歸的，對(duì)于內(nèi)存非常有限的機(jī)器來(lái)說(shuō)，它不是一個(gè)好的選擇。4、堆排序（HeapSort）或者多維的暫存數(shù)組。這對(duì)于數(shù)據(jù)量非常巨大的序列是合適的。比如超過(guò)數(shù)百萬(wàn)條記錄，因?yàn)榭焖倥判?，歸并排序都使用遞歸來(lái)設(shè)計(jì)算法，在數(shù)據(jù)量非常大的時(shí)候，可能會(huì)發(fā)生堆棧溢出錯(cuò)誤。堆排序會(huì)將所有的數(shù)據(jù)建成一個(gè)堆，最大的數(shù)據(jù)在堆頂，然后將堆頂數(shù)據(jù)和序列的最后一個(gè)數(shù)據(jù)交換。接下來(lái)再次重建堆，交換數(shù)據(jù)，依次下去，就可以排序所有的數(shù)據(jù)。心 得 體 會(huì)說(shuō)實(shí)話，本次做數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)，時(shí)間非常緊，在課間我做的少，基本上都是在課后把本次課程

19、設(shè)計(jì)做出來(lái)的。我們的課程設(shè)計(jì)安排在 17、18、19 周去做。但是在 16 周的星期 1、2 的上午和星期 4 的下午我都有考試，因此在星期 1 的上午的考試結(jié)束后，在下午的課程設(shè)計(jì)的課上我都在復(fù)習(xí)第二天要考試的內(nèi)容；而在星期2 上午考試結(jié)束后，星期 2 下午和星期三我都在復(fù)習(xí)星期 4 要考試的內(nèi)容。所以，我從星期 1 到星期 4 的課程設(shè)計(jì)課我基本上什么也沒(méi)有做。我真正開(kāi)始做課程設(shè)計(jì)是從星期 5 上午在寢室開(kāi)始的。做了星期 5 一天，我才把方案設(shè)計(jì)、程序操作過(guò)程、程序流程圖和很少一部分程序源代碼做好，然后在寢室花了整整一周才把所有內(nèi)容都寫完。然后星期 2 花了一整天的時(shí)間才整理出來(lái)這個(gè)課程設(shè)

20、計(jì)的論文。寫完后，我心里有兩個(gè)感受：第一是：累！我差不多花了整整 20 天時(shí)間來(lái)寫這個(gè)課程設(shè)計(jì)，在這其間，我只有在吃飯的時(shí)候看會(huì)兒電影，其余的時(shí)候我基本上都在做課程設(shè)計(jì)（睡覺(jué)的時(shí)間除外）。第二是：滿足！這個(gè)課程設(shè)計(jì)是我從搜集資料、整理資料、到寫好這份課程設(shè)計(jì)都是我一個(gè)人完成的，絕沒(méi)有抄襲別人的。通過(guò)這次課程設(shè)計(jì)，我收獲頗多。原來(lái)上課時(shí)沒(méi)有聽(tīng)懂的地方，通過(guò)這次課程設(shè)計(jì)，我自己翻書，查資料，我基本上都理解了；原來(lái)疑惑的地方現(xiàn)在也明白了！自從拿到題目到完成整個(gè)編程，從理論到實(shí)踐，在兩周多的時(shí)間里，通過(guò)查資料，向老師和同學(xué)請(qǐng)教，讓我學(xué)到很多很多的東西，同時(shí)鞏固了以前所學(xué)過(guò)的知識(shí)。在測(cè)試階段中發(fā)現(xiàn)了幾處

21、錯(cuò)誤導(dǎo)致程序運(yùn)行不正確，去上網(wǎng)查找相關(guān)的資料,向老師請(qǐng)教，又同學(xué)一起討論。通過(guò)耐心的分析源代碼終于編好了一個(gè)完整無(wú)誤的程序。在這次的算法與數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)中遇到了現(xiàn)實(shí)編程中必然見(jiàn)到的問(wèn)題，通過(guò)對(duì)這些問(wèn)題分析和解決積累了編程的實(shí)踐經(jīng)驗(yàn)。在實(shí)際的編程操作中發(fā)現(xiàn)自己對(duì)計(jì)算機(jī)編程語(yǔ)言知識(shí)的不足。總之，通過(guò)這次課程設(shè)計(jì)，我拓寬了知識(shí)面，鍛煉了能力。尤其是觀察、分析和解決問(wèn)題的實(shí)際工作能力。從課堂走向?qū)嵺`。通過(guò)課程設(shè)計(jì)，讓我們找出自身狀況與實(shí)際需要的差距，并在以后的學(xué)習(xí)期間及時(shí)補(bǔ)充相關(guān)知識(shí)。參 考 文 獻(xiàn)【1】嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C .清華大學(xué)出版社【2】鄧均輝. 數(shù)據(jù)結(jié)構(gòu)與算法.清華大學(xué)出版社【3】朱站立，張選平，韓家新.數(shù)據(jù)結(jié)構(gòu)-使用 c 語(yǔ)言.西安交通大學(xué)出版社【4】譚浩強(qiáng).c 語(yǔ)言程序設(shè)計(jì). 清華大學(xué)出版社.【5】 嚴(yán)蔚敏