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

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