1、 .PAGE29 / NUMPAGES30課程設(shè)計(jì)任務(wù)書題 目: 排序碼比較次數(shù)、記錄移動次數(shù)的定量分析初始條件：理論：學(xué)習(xí)了數(shù)據(jù)結(jié)構(gòu)課程，掌握了一種計(jì)算機(jī)高級語言。實(shí)踐：計(jì)算機(jī)技術(shù)系實(shí)驗(yàn)中心提供計(jì)算機(jī)與軟件開發(fā)環(huán)境。要求完成的主要任務(wù): （包括課程設(shè)計(jì)工作量與其技術(shù)要求，以與說明書撰寫等具體要求）1、系統(tǒng)應(yīng)具備的功能：（1）選擇書中35個排序算法，對它們稍作修改，即在算法中插入關(guān)于排序碼比較次數(shù)和元素移動次數(shù)的統(tǒng)計(jì)語句。用修改后的排序算法對同一個隨機(jī)數(shù)序分別進(jìn)行排序，統(tǒng)計(jì)排序過程中排序碼的比較次數(shù)和元素的移動次數(shù)。 （2）至少分析5組排序碼。每組排序碼由鍵盤輸入或者隨機(jī)函數(shù)產(chǎn)生。2、數(shù)據(jù)結(jié)構(gòu)

2、設(shè)計(jì)；3、主要算法設(shè)計(jì)；4、編程與上機(jī)實(shí)現(xiàn)；5、撰寫課程設(shè)計(jì)報(bào)告，包括：（1）設(shè)計(jì)題目；（2）摘要和關(guān)鍵字（中文和英文）；（3）正文，包括引言、需求分析、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)、算法設(shè)計(jì)、有關(guān)技術(shù)的討論、設(shè)計(jì)體會等；（4）結(jié)束語；（5）參考文獻(xiàn)。時間安排：2012年1月2日6日（第18周）1月2日 查閱資料1月3日 系統(tǒng)設(shè)計(jì)，數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)，算法設(shè)計(jì)1月4日-5日 編程并上機(jī)調(diào)試1月6日 撰寫報(bào)告1月7日 驗(yàn)收程序，提交設(shè)計(jì)報(bào)告書。指導(dǎo)教師簽名： 2012年1月2日系主任（或責(zé)任教師）簽名： 年 月 日目錄摘要1Abstract21引言 32需求分析 42.1基礎(chǔ)分析 4 2.2功能分析 43數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

3、 53.1頭文件 53.2結(jié)構(gòu)體定義 53.3功能函數(shù)與輔助函數(shù)的聲明 54算法程序的分析設(shè)計(jì) 64.1定義結(jié)構(gòu)體 64.2輸入函數(shù) 64.3輸出函數(shù) 74.4起泡排序的排列和輸出函數(shù) 74.5直接插入排序的排列和輸出函數(shù) 84.6簡單選擇排序的排列和輸出函數(shù) 94.7快速排序的排列函數(shù) 104.8快速排序的輸出函數(shù) 105程序?qū)崿F(xiàn) 125.1輔助輸出函數(shù) 125.2主函數(shù) 126運(yùn)行結(jié)果14 6.1初始界面 14 6.2第一次輸入長度 14 6.3第一次輸入排序碼與其所得結(jié)果 146.4第二次輸入長度 14 6.5第二次輸入排序碼與其所得結(jié)果 156.6第三次輸入長度 156.7第三次輸入排

4、序碼與其所得結(jié)果：166.8第四次輸入長度 17 6.9第四次輸入排序碼與其所得結(jié)果 18 6.10第五次輸入長度 196.11第五次輸入排序碼與其所得結(jié)果 207有關(guān)技術(shù)的討論 238設(shè)計(jì)體會 24結(jié)束語25參考文獻(xiàn) 26摘要:該程序主要是用來對同一個隨機(jī)數(shù)序分別進(jìn)行排序，并統(tǒng)計(jì)排序過程中排序碼的比較次數(shù)和元素的移動次數(shù)。通過輸入不同的隨機(jī)數(shù)序，從而辨別數(shù)序?qū)τ诓煌呐判蛩惴ǘ?，其排序的?fù)雜程度，從而選擇其中較為簡單的方法用于數(shù)序的排列。同時可以判斷同一組數(shù)據(jù)在輸入的順序不同時將得到不同的結(jié)果，從而證明輸入對排序結(jié)果和排序復(fù)雜度的影響。本程序是以VC+6.0為開發(fā)工具，并多用面向?qū)ο蟪绦蛟O(shè)

5、計(jì)語言C+來實(shí)現(xiàn)的。關(guān)鍵詞：結(jié)構(gòu)體 起泡排序 直接插入排序 簡單選擇排序 快速排序Abstract：The program is primarily used for the same sequence of random number respectively to sort and statistics in the process of sorting the comparison of the sort code number and element number of moves. Through the input different random sequence in orde

6、r to identify sequence number for different sort algorithm is concerned, its sort of sophistication, and choosing among the more simple method used in sequence of number. At the same time can judge the same set of data in the order of the input is not the same will get different results, so as to pr

7、ove the input to sort results and sort the influence of complexity. The program is based on vc + + 6.0 as a development tool, and multi-purpose object-oriented programming language C+ to fulfill.Keyword: StructureBubble Sort Bubble Sort simple selection sort Quicksort1 引言數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)程序設(shè)計(jì)的重要理論技術(shù)基礎(chǔ)，它不僅是計(jì)算

8、機(jī)學(xué)科的核心課稱，而且已成為其他理工專業(yè)的熱門選修課。數(shù)據(jù)結(jié)構(gòu)是一門專業(yè)選技術(shù)基礎(chǔ)科。一方面，它要求我們學(xué)會分析研究計(jì)算機(jī)加工的數(shù)據(jù)結(jié)構(gòu)的特性，以便為應(yīng)用涉與的數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲結(jié)構(gòu)與其相應(yīng)的算法，并初步掌握算法的時間分析和空間分析的技術(shù)；另一方面，數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)過程也是復(fù)雜程序設(shè)計(jì)的訓(xùn)練過程，要求我們編寫的程序結(jié)構(gòu)清楚和正確易讀，復(fù)合軟件工程的規(guī)，并培養(yǎng)我們的數(shù)據(jù)抽象能力。本次課程設(shè)計(jì)就是對數(shù)據(jù)結(jié)構(gòu)中的排序與其算法的應(yīng)用。排序是計(jì)算機(jī)程序設(shè)計(jì)中的一項(xiàng)重要操作，它的功能是講一個數(shù)據(jù)元素（或記錄）的任意序列，重新排列成一個按關(guān)鍵字有序的序列。為了查找方便，我們通常希望計(jì)算機(jī)中的表是按關(guān)

9、鍵字有序的。因?yàn)橛行虻捻樞虮砜梢圆捎貌檎倚瘦^高的折半查找法，而無序的順序表只能進(jìn)行順序查找，效率很低。因此，學(xué)習(xí)和研究各種排序算法是計(jì)算機(jī)工作者的重要課題之一。由于待排序的記錄數(shù)量不同，使得排序過程中涉與的存儲器不同，可將排序分為部排序和外部排序兩大類。此課程設(shè)計(jì)的容是對部排序的應(yīng)用。2需求分析2.1基礎(chǔ)分析根據(jù)要求，系統(tǒng)應(yīng)該具備以下兩種功能：1選擇書中35個部排序的算法，并對它們稍作修改，即在算法中插入關(guān)于排序碼比較次數(shù)和元素移動次數(shù)的統(tǒng)計(jì)的語句。并用修改后的排序算法對同一個隨機(jī)數(shù)序分別進(jìn)行排序，統(tǒng)計(jì)在此次排序過程中排序碼的比較次數(shù)和元素的移動次數(shù)。2至少要分析5組排序碼，且每組排序碼由鍵

10、盤輸入或者隨機(jī)函數(shù)產(chǎn)生。2.2功能分析針對以上兩個方面需求，對其仔細(xì)分析并得到的解決方案即程序應(yīng)具備的功能如下：要對同一個隨機(jī)數(shù)序分別進(jìn)行排序，并統(tǒng)計(jì)在排序過程中排序碼的比較次數(shù)和元素的移動次數(shù)，就需要建立一個共同的輸出函數(shù)和輸入函數(shù)，并且要對數(shù)序進(jìn)行各種排序，從而統(tǒng)一輸出。對于同一輸入的排序碼，由于要四次調(diào)用，則需要建立一個數(shù)組，并用for循環(huán)來使其排序時的初始值一樣，從而達(dá)到比較的目的。要至少分析五組排序碼，就要在主函數(shù)（即main函數(shù)）建立一個for循環(huán)，借此循環(huán)來使每組排序碼互不干擾，獨(dú)立輸出。3 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)3.1頭文件：#include using namespace std;3.

11、2結(jié)構(gòu)體定義：struct RecordNode int key; /排序碼字段 int value; /記錄的其他字段;struct SortObject int n; /n為文件中的記錄個數(shù) RecordNode *record; ;3.3功能函數(shù)與輔助函數(shù)的聲明： void InputData(SortObject *pvector) /*待排序的記錄關(guān)鍵碼的輸入*/void OutputData(SortObject *pvector) /*排序表的輸出*/void bubbleSort(SortObject * pvector,int &n,int &m) /*起泡排序的排列和輸出*

12、/void InsSort(SortObject * pvector,int &n,int &m) /*直接插入排序的排列和輸出*/void SelectSort(SortObject * pvector,int &n,int &m)bool road_empty(); /*簡單選擇排序的排列和輸出*/void quitsort(SortObject * pvector,int s,int e,int &n,int &m); /*快速排序的排列*/void quitsort_prin(SortObject * pvector,int &n,int &m); /*快速排序的輸出*/4 算法程序的

13、分析設(shè)計(jì)本程序主要方法是函數(shù)調(diào)用，函數(shù)比較多但都比較簡短，每次操作都有操作提示并且重新輸入以下是函數(shù)介紹：4.1定義結(jié)構(gòu)體定義整形結(jié)構(gòu)和指針。struct RecordNode int key; /排序碼字段 int value; /記錄的其他字段;struct SortObjectint n; /n為文件中的記錄個數(shù) RecordNode *record; ;4.2輸入函數(shù)將輸入的數(shù)組復(fù)制并等待應(yīng)用。void InputData(SortObject *pvector)cout輸入待排序的n個記錄關(guān)鍵碼：;int i;for(i=0;in;i+) cinpvector0-recordi.ke

14、y;for(int j=1;jrecordi.key=pvector0-recordi.key;4.3輸出函數(shù)利用指針和數(shù)組輸出。void OutputData(SortObject *pvector)cout當(dāng)前排序表為：; for(int i=0;in;i+) coutrecordi.key ; coutendl;4.4起泡排序的排列和輸出函數(shù)相鄰兩個數(shù)相互比較，將大一點(diǎn)的數(shù)置于后邊，直到所有數(shù)都符合要求。void bubbleSort(SortObject * pvector,int &n,int &m)n=0,m=0; /n為排序碼比較次數(shù)，m為元素移動次數(shù):int i, j, nos

15、wap; RecordNode temp; for(i=0; in-1; i+) / 做n-1次起泡noswap=1; for(j=0; jn-i-1; j+) /置交換標(biāo)志n+;if(pvector-recordj+1.keyrecordj.key) /從前向后掃描temp=pvector-recordj; / 交換記錄 pvector-recordj=pvector-recordj+1; pvector-recordj+1=temp; noswap=0;m+; if(noswap) break; /本趟起泡未發(fā)生記錄交換，算法結(jié)束cout起泡排序法: ;cout排序碼比較次數(shù): n 元素移

16、動次數(shù): m ; OutputData(pvector);4.5直接插入排序的排列和輸出函數(shù)依次將后面的數(shù)插入前面已排好的序列中，并進(jìn)行排序。void InsSort(SortObject * pvector,int &n,int &m) n=0,m=0;RecordNode temp;int i,j;for( i=1;in;+i)if(pvector-recordi.keyrecordi-1.key)temp=pvector-recordi;for(j=i-1;temp.keyrecordj.key&j-1;-j)pvector-recordj+1=pvector-recordj;m+;n+

17、;pvector-recordj+1=temp;n+;m+;n+;cout直接插入排序: ;cout排序碼比較次數(shù): n 元素移動次數(shù): m ; OutputData(pvector); 4.6簡單選擇排序的排列和輸出函數(shù)每次選出最小的數(shù)置于未排序的數(shù)之前，已排序的數(shù)之后。void SelectSort(SortObject * pvector,int &n,int &m)n=0,m=0;int i,j,k; for ( i=0 ; i n; +i) k=i;for ( j=i+1 ; j n ; +j) if (pvector-recordj.key recordk.key ) k=j;n+

18、;if ( k!=i) RecordNode x;x= pvector-recordi; pvector-recordi= pvector-recordk;pvector-recordk=x;m+;cout簡單選擇排序: ;cout排序碼比較次數(shù): n 元素移動次數(shù): mrecords;if(lr) return;while(lr)while(lrecordr.key=x.key)r-;n+;pvector-recordl=pvector-recordr;while(lrecordl.keyrecordr=pvector-recordl;m+;pvector-recordl.key=x.key

19、;quitsort(pvector,s,r-1,n,m);quitsort(pvector,r+1,e,n,m);4.8快速排序的輸出函數(shù)void quitsort_prin(SortObject * pvector,int &n,int &m) n=0,m=0;quitsort(pvector,0,pvector-n-1,n,m);cout快速排序: ;cout排序碼比較次數(shù): n 元素移動次數(shù): m ;OutputData(pvector);5 程序?qū)崿F(xiàn)5.1輔助輸出函數(shù)：幫助main函數(shù)輸入排序表，輸出四種排序算法所得到的結(jié)果。void Showout(int nn,int mm)Sor

20、tObject *pvector4;int i,n;for(i=0;i4;+i)pvectori=new SortObject; coutn;for(i=0;in=n;pvectori-record=new RecordNoden; InputData(pvector); bubbleSort(pvector0,nn0,mm0);InsSort(pvector1,nn1,mm1);SelectSort(pvector2,nn2,mm2);quitsort_prin(pvector3,nn3,mm3);5.2主函數(shù)此項(xiàng)主要輸出頁面。void main()cout*endl;cout 歡 迎 進(jìn)

21、入 排 序 頁 面 !endl;cout*endl;int n4=0;int m4=0;int i;for(i=0;i5;+i)cout第i+1組排序如下:endl;Showout(n,m);int n_min=0;int m_min=0;for(int j=1;j4;+j)if(njnn_min)n_min=j;if(mjmm_min)m_min=j;cout這次排序中，排序碼比較次數(shù)最少的是第n_min+1種排序方法.endl;cout這次排序中，元素移動的次數(shù)最少的是第m_min+1種排序方法.endl;coutendl;cout*endl;cout 排 序 結(jié) 束， 使 用! endl

22、;cout*endl;6 運(yùn)行結(jié)果6.1初始界面：6.2第一次輸入長度：6.3第一次輸入排序碼與其所得結(jié)果：6.4第二次輸入長度：6.5第二次輸入排序碼與其所得結(jié)果：6.6第三次輸入長度：6.7第三次輸入排序碼與其所得結(jié)果：6.8第四次輸入長度：6.9第四次輸入排序碼與其所得結(jié)果：6.10第五次輸入長度：6.11第五次輸入排序碼與其所得結(jié)果：7 有關(guān)技術(shù)的討論本程序多次地運(yùn)用函數(shù)調(diào)用，使程序簡潔易懂，并且很好地達(dá)到了代碼重用的效果，從而減少代碼量。在函數(shù)調(diào)用的同時，利用引用使得數(shù)據(jù)傳遞變得更加方便，但其它數(shù)據(jù)若不小心被修改也會影響到全局，這就是其不足。其次程序里用的比較多的就是for語句和wh

23、ile語句，前者既增加了代碼的可讀性也讓選擇操作得到很好的實(shí)現(xiàn)，而后者主要用于信息輸入錯誤需重新輸入和返回主菜單。對于算法設(shè)計(jì)這方面，我覺得只需給函數(shù)輸入的想法比較好，這樣既能夠無誤地達(dá)到目的，也可以大減少程序使用者的操作量。8 設(shè)計(jì)體會通過這次課程設(shè)計(jì)，我不僅提高了自己的編程能力，而且讓我學(xué)會了編寫一個程序應(yīng)該如何去做才能是程序更加完善，讓我懂得寫程序時應(yīng)該戒驕戒躁，要仔細(xì)閱讀題目利用更為簡潔的方法解決問題。其次，從其中我學(xué)會了編寫程序的比較好的方法就是要分析好題目、設(shè)計(jì)好程序的整體結(jié)構(gòu)、設(shè)計(jì)算法并列出所需函數(shù)、逐個編寫函數(shù)的代碼、和完善美觀函數(shù)。通過這次編程，我深深體會到了算法的重要性，算法的好壞直接影響到了程序編寫的難易與效率。剛拿到排序碼操作題目時，心中暗自竊喜，感覺題目不難，比起其他停車場管理系統(tǒng)、圖書館管理系統(tǒng)等題目，我需要寫的代碼并不會太繁雜，而且只需要加幾個統(tǒng)計(jì)語句就可以了。然而在實(shí)際編寫程序的時候，發(fā)現(xiàn)并不是那么簡單，因?yàn)橐_(dá)到目標(biāo)，不僅要學(xué)會應(yīng)用數(shù)組，還要學(xué)會應(yīng)用指針，當(dāng)然，還要考慮其他各個方面的問題，并非只是加幾個程序語句局可以完成的。此次課程設(shè)計(jì)讓我的設(shè)計(jì)能力和調(diào)試改錯能力大增強(qiáng)