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

武漢理工大學(xué)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)說(shuō)明書(shū)課程設(shè)計(jì)任務(wù)書(shū)學(xué)生姓名： 胡達(dá) 專(zhuān)業(yè)班級(jí)： 計(jì)算機(jī)0708班 指導(dǎo)教師： 高曙 工作單位： 計(jì)算機(jī)科學(xué)系 題 目: 快速、冒泡排序算法比較 初始條件： 試通過(guò)隨機(jī)數(shù)據(jù)比較快速排序、起泡排序各算法的關(guān)鍵字比較次數(shù)和關(guān)鍵字移動(dòng)次數(shù)。（1）待排序表的表長(zhǎng)不小于100；其中的數(shù)據(jù)要用偽隨機(jī)數(shù)產(chǎn)生程序產(chǎn)生；至少要用5組不同的輸入數(shù)據(jù)作比較；比較的指標(biāo)為有關(guān)鍵字參加的比較次數(shù)和關(guān)鍵字的移動(dòng)次數(shù)（關(guān)鍵字交換計(jì)為3次移動(dòng)）。（2）最后要對(duì)結(jié)果作出簡(jiǎn)單分析，包括對(duì)各組數(shù)據(jù)得出結(jié)果波動(dòng)大小的解釋。（3）對(duì)冒泡排序應(yīng)指出進(jìn)行了多少趟。要求完成的主要任務(wù): （包括課程設(shè)計(jì)工作量及其技術(shù)要求，以及說(shuō)明書(shū)撰寫(xiě)等具體要求）課程設(shè)計(jì)報(bào)告按學(xué)校規(guī)定格式用A4紙打印（書(shū)寫(xiě)），并應(yīng)包含如下內(nèi)容： 1、 問(wèn)題描述簡(jiǎn)述題目要解決的問(wèn)題是什么。2、 設(shè)計(jì)存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)、主要算法設(shè)計(jì)（用類(lèi)C語(yǔ)言或用框圖描述）、測(cè)試用例設(shè)計(jì)；3、 調(diào)試報(bào)告調(diào)試過(guò)程中遇到的問(wèn)題是如何解決的；對(duì)設(shè)計(jì)和編碼的討論和分析。4、 經(jīng)驗(yàn)和體會(huì)（包括對(duì)算法改進(jìn)的設(shè)想）5、 附源程序清單和運(yùn)行結(jié)果。源程序要加注釋。如果題目規(guī)定了測(cè)試數(shù)據(jù)，則運(yùn)行結(jié)果要包含這些測(cè)試數(shù)據(jù)和運(yùn)行輸出，6、 設(shè)計(jì)報(bào)告、程序不得相互抄襲和拷貝；若有雷同，則所有雷同者成績(jī)均為0分。時(shí)間安排：1、第19周完成。2、7月X日X時(shí)到計(jì)算中心檢查程序、交課程設(shè)計(jì)報(bào)告、源程序（CD光盤(pán)）。指導(dǎo)教師簽名： 2009年07月26日系主任（或責(zé)任教師）簽名： 年 月 日快速、冒泡排序的算法比較1.問(wèn)題分析和任務(wù)定義1.1問(wèn)題分析 編程實(shí)現(xiàn)快速、冒泡兩種排序算法，兩者之間的算法好壞比較主要有兩個(gè)方面：數(shù)據(jù)比較次數(shù)和數(shù)據(jù)移動(dòng)次數(shù)。在該程序中，首先對(duì)兩種排序算法進(jìn)行實(shí)現(xiàn)，然后再進(jìn)行比較。1.2任務(wù)定義 1.2.1 快速排序定義 快速排序也叫做分區(qū)排序，是目前應(yīng)用最廣泛的排序算法。它采用分治法進(jìn)行排序。其基本思想是任取待排序元素序列中的某個(gè)元素（例如取第一個(gè)元素）作為基準(zhǔn)，按照該元素的排序碼大小，將整個(gè)元素序列劃分為左右兩個(gè)子序列；左側(cè)子序列中所有元素的排序碼都小于基準(zhǔn)元素的排序碼，右側(cè)子序列中所有元素的排序碼都大于或等于基準(zhǔn)元素的排序碼，基準(zhǔn)元素則排在這兩個(gè)子序列中間。然后分別對(duì)這兩個(gè)子序列重復(fù)實(shí)行上述方法，直到所有的元素都排在相應(yīng)的位置上為止。 1.2.2 冒泡排序定義 冒泡排序又稱(chēng)起泡排序，它也是一種簡(jiǎn)單實(shí)用的排序方法。其基本思想是通過(guò)相鄰記錄之間關(guān)鍵字的比較和交換，使關(guān)鍵字值較小的記錄逐漸的從底部移向頂部，即從下標(biāo)較大的單元移向下標(biāo)較小的單元，就像水底的氣泡一樣逐漸向上冒；而關(guān)鍵字較大的記錄就像石塊往下沉一樣，每一趟有一塊“最大”的石頭沉到水底。2.開(kāi)發(fā)平臺(tái)處 理 器：Intel Pentium 4 2.4GHz物理內(nèi)存：512M操作系統(tǒng)：Microsoft Windows XP開(kāi)發(fā)環(huán)境：Microsoft Visual Studio.NET 20033.程序設(shè)計(jì) 3.1快速排序 3.1.1排序表的類(lèi)定義datalist.h#ifndef DATALIST_H#define DATALIST_H#include const int DefaultSize = 100;template class dataList template class Element friend class dataList;private: Type key; /排序碼 field otherdata; /其它數(shù)據(jù)成員 public: Element ( ) : key(0), otherdata(NULL) Type getKey ( ) return key; /提取排序碼 void setKey ( const Type x ) key = x; /修改 Element & operator = /賦值 ( Element& x ) key = x-key; otherdata = x-otherdata; int operator = (Element& x ) return key = x-key; /判this = x int operator = (Element& x ) return key key; /判this x int operator (Element& x ) return key key; /判this (Element& x ) return key x-key; /判this x template class dataList private: Element * Vector; /存儲(chǔ)向量 int MaxSize, CurrentSize; /最大與當(dāng)前個(gè)數(shù)public: datalist ( int MaxSz = DefaultSize ) : MaxSize ( Maxsz ), CurrentSize (0) Vector = new Element MaxSz; void sort ( ); /排序 void swap ( Element & x, /對(duì)換 Element & y ) Element temp = x; x = y; y = temp; 3.1.2快速排序算法的描述QuickSort ( List ) if ( List的長(zhǎng)度大于1) 將序列List劃分為兩個(gè)子序列LeftList 和 Right List; QuickSort ( LeftList );QuickSort ( RightList ); 將兩個(gè)子序列 LeftList 和 RightList合并為一個(gè)序列List; 3.1.3快速排序的算法#include”datalisr.h”template void dataList : QuickSort ( const int left,const int right ) /在序列 leftright 中遞歸地進(jìn)行快速排序 if ( left right) int pivotpos = Partition ( left, right ); /劃分 /對(duì)左序列同樣處理 QuickSort ( left, pivotpos-1); /對(duì)右序列同樣處理 QuickSort ( pivotpos+1, right ); template int dataList : Partition ( const int low, const int high ) int pivotpos = low; /基準(zhǔn)位置 Element pivot = Vectorlow; for ( int i = low+1; i = high; i+ ) if ( Vectori pivot ) pivotpos+; if ( pivotpos != i ) Swap ( Vectorpivotpos, Vectori ); /小于基準(zhǔn)對(duì)象的交換到區(qū)間的左側(cè)去 Swap ( Vectorlow, Vectorpivotpos ); return pivotpos; 3.2冒泡排序 #include”datalist.h” template void dataList : BubbleSort ( ) int pass = 1; int exchange = 1; while ( pass = pass; j- ) if ( Vectorj-1 Vectorj ) /逆序 Swap ( Vectorj-1, Vectorj ); /交換 exchange = 1; /標(biāo)志置為1,有交換 pass+; 4.調(diào)試報(bào)告 4.1調(diào)試程序#include#includedatalist.h#includemaopao.h#includequicksort.husing namespace std;int main()int length,i;coutlength;int *a=new intlength+1;Element e;datalist list1;datalist list2;for(i=1;i=length;i+)ai=e.key=e.otherdata=rand();list1.add(e);cout排序前：endl;for(i=1;i=length;i+)coutait;list1.BubbleSort();list1.print(); cout冒泡排序的比較次數(shù)為：list1.getTimes()endl;cout冒泡排序的移動(dòng)到次數(shù)：list1.getKeyMove()endl; list2.QuickSort(1,length-1);list2.print(); cout快速排序的比較次數(shù)為：list2.getTimes()endl;cout快速排序的移動(dòng)到次數(shù)：list2.getKeyMove()endl;return 0;4.2調(diào)試過(guò)程中出現(xiàn)的問(wèn)題在實(shí)驗(yàn)過(guò)程中，發(fā)現(xiàn)了許多容易忽視的問(wèn)題，例如，在dataList類(lèi)中未對(duì)BubbleSort()進(jìn)行聲明，則無(wú)法再調(diào)試程序中進(jìn)行調(diào)用；還有在main函數(shù)中直接對(duì)list1對(duì)象中的函數(shù)進(jìn)行調(diào)用，則會(huì)發(fā)生錯(cuò)誤等等。 4.3調(diào)試程序產(chǎn)生的結(jié)果程序運(yùn)行界面5.算法效率分析 5.1冒泡排序算法的效率分析最壞的情形是算法執(zhí)行n-1趟起泡,第i趟 (1 i n) 做 n- i 次排序碼比較, 執(zhí)行 n-i 次對(duì)象交換。這樣在最壞情形下總的排序碼比較次數(shù)KCN和對(duì)象移動(dòng)次數(shù)RMN為：5.2快速排序算法的效率分析通過(guò)相關(guān)公式以及實(shí)驗(yàn)可以證明, 函數(shù)quicksort的平均計(jì)算時(shí)間也是O(nlog2n)。實(shí)驗(yàn)結(jié)果表明: 就平均計(jì)算時(shí)間而言, 快速排序是所有內(nèi)排序方法中最好的一個(gè)。6.經(jīng)驗(yàn)和體會(huì)通過(guò)此次試驗(yàn)，我明白了兩個(gè)方面的知識(shí)：學(xué)與做方面：在做了這次課程設(shè)計(jì)，我覺(jué)得課程設(shè)計(jì)這種形式真的是我們需要的，可以讓我們學(xué)到很多，包括書(shū)上的、書(shū)外的。理論永遠(yuǎn)!=實(shí)際。在學(xué)排序算法的時(shí)候，讀了書(shū)上的算法描述，覺(jué)得自己都會(huì)了，考試題目也都做出來(lái)了，但真的到編程去實(shí)現(xiàn)它的時(shí)候，卻不是一次就成功的，總會(huì)出點(diǎn)差錯(cuò)，循環(huán)的邊界條件啊，排序表的設(shè)計(jì)啊，等等，只得一次次改，等到程序終于正確運(yùn)行的時(shí)候，才算真正會(huì)了這些算法，理論和實(shí)際永遠(yuǎn)差那么一點(diǎn)，不去做是體會(huì)不出來(lái)的。坐在電腦前才真正知道自己會(huì)不會(huì)，眼高手低是要不得的。還有一個(gè)收獲是知道了什么是面向?qū)ο蟮某绦蛟O(shè)計(jì)方法。選擇C+作為實(shí)現(xiàn)語(yǔ)言而不是自己學(xué)過(guò)的也熟悉的C，是想深入掌握一門(mén)語(yǔ)言，都說(shuō)C+面向?qū)ο?，跟C完全不一樣，而以前學(xué)習(xí)C+時(shí)就覺(jué)得它跟C是一回事，只不過(guò)把換成了，把printf()換成了cout，換湯不換藥，即使引進(jìn)了類(lèi)，也只不過(guò)把函數(shù)移進(jìn)C的結(jié)構(gòu)體，換了個(gè)關(guān)鍵字而已，現(xiàn)在真正要用它編程了，想要設(shè)計(jì)一個(gè)合理的類(lèi)，卻發(fā)現(xiàn)無(wú)從下手，然后就看書(shū)上的例子，看有關(guān)知識(shí)點(diǎn)的講解，然后想如果是C，該怎么寫(xiě)，在嘗試了C+的運(yùn)算符重載、函數(shù)重載、類(lèi)模板、函數(shù)模板、錯(cuò)誤處理機(jī)制后，才發(fā)現(xiàn)C+真的跟C有本質(zhì)的不同，以前把C+當(dāng)C來(lái)學(xué)是徹底的錯(cuò)了，C+的這些機(jī)制對(duì)C來(lái)說(shuō)是質(zhì)的飛躍，類(lèi)是數(shù)據(jù)更安全，數(shù)據(jù)與對(duì)應(yīng)數(shù)據(jù)的特定的操作關(guān)系更緊密、多態(tài)性是編譯器為程序員分擔(dān)了很多工作，程序員再不必僅為不同的數(shù)據(jù)類(lèi)型浪費(fèi)精力寫(xiě)冗余的代碼、錯(cuò)誤處理機(jī)制使程序在出錯(cuò)時(shí)得到更適當(dāng)?shù)奶幚恚皇浅绦虮罎⑸踔潦谴直┑亟Y(jié)束程序C+對(duì)現(xiàn)實(shí)的模擬比C