基于選擇排序方法的類模板設(shè)計與實現(xiàn)C++課程設(shè)計

1、 成成 績績 評評 定定 表表 學(xué)生姓名吳瓊班級學(xué)號 專 業(yè)通信工程課程設(shè)計題目 基于選擇排序方法的類 模板設(shè)計與實現(xiàn) 評 語 組長簽字： 成績 日期 20 年 月 日 課程設(shè)計任務(wù)書課程設(shè)計任務(wù)書 學(xué) 院信息科學(xué)與工程專 業(yè)通信工程 學(xué)生姓名吳瓊班級學(xué)號 課程設(shè)計題目基于選擇排序方法的類模板設(shè)計與實現(xiàn) 實踐教學(xué)要求與任務(wù)實踐教學(xué)要求與任務(wù) 建立一維數(shù)組數(shù)據(jù)結(jié)構(gòu)的模板類，使一維數(shù)組中的數(shù)據(jù)元素可以是 char, int, float 等多種數(shù)據(jù)類型，并對數(shù)組元素實現(xiàn)選擇類排序。主要完成如下功能： （1） 實現(xiàn)數(shù)組數(shù)據(jù)的輸入和輸出； （2） 實現(xiàn)簡單選擇排序功能； （3） 實現(xiàn)樹形選擇排序功能；

2、 （4） 實現(xiàn)堆排序功能； （5） 將每種排序功能作為類的成員函數(shù)實現(xiàn)，編寫主函數(shù)測試上述排序功能。 工作計劃與進度安排工作計劃與進度安排 第 17 周：分析題目，查閱課題相關(guān)資料，進行類設(shè)計、算法設(shè)計； 第 18 周：程序的設(shè)計、調(diào)試與實現(xiàn)； 第 19 周：程序測試與分析，撰寫課程設(shè)計報告，進行答辯驗收。 指導(dǎo)教師： 201 年 月 日 專業(yè)負責(zé)人： 201 年 月 日 學(xué)院教學(xué)副院長： 201 年 月 日 摘 要 計算機中存儲的數(shù)據(jù)，初始時沒有任何排列規(guī)律，根據(jù)實際需求，經(jīng)常要排列成 有規(guī)律的數(shù)據(jù)序列也就是將數(shù)據(jù)序列按關(guān)鍵字升序或降序規(guī)律排列。 選擇排序是排序法中很經(jīng)典的算法，選擇排序法可

3、以分為簡單選擇排序、樹形選擇排 序和堆排序。 本文采用 c+語言實現(xiàn)了選擇排序功能，設(shè)計了模板類，實現(xiàn)了 int 型 float 型和 char 型數(shù)組的排序，設(shè)計了簡單選擇排序、樹形選擇排序和堆排序的三個函數(shù)體，采 用 visual c+ 6.0 的控制臺工程和 mfc 工程分別實現(xiàn)了各類型數(shù)組的排序，通過對兩 種程序的測試結(jié)果表明：簡單選擇排序是選擇排序的基礎(chǔ)，而樹形選擇排序和堆排序 是簡單選擇排序的改進。 關(guān)鍵詞：模板類；簡單選擇排序；樹形選擇排序；堆排序；控制臺工程；mfc 工 程。 目 錄 1 需求分析.1 2 算法基本原理.1 3 類設(shè)計.3 4 基于控制臺的應(yīng)用程序.3 4.1

4、類的接口設(shè)計.4 4.2 類的實現(xiàn).4 4.3 主函數(shù)設(shè)計.9 4.4 基于控制臺的應(yīng)用程序測試.11 5 基于 mfc 的應(yīng)用程序.13 5.1 基于 mfc 的應(yīng)用程序設(shè)計.13 5.1.1 mfc 程序界面設(shè)計.13 5.1.2 mfc 程序代碼設(shè)計.15 5.2 基于 mfc 的應(yīng)用程序測試.21 結(jié) 論.22 參考文獻.23 1 需求分析 （1）當(dāng)進行數(shù)據(jù)處理時,經(jīng)常遇到需要進行查找操作,通常希望待處理的數(shù) 據(jù)按關(guān)鍵字大小有序排序,因為這樣就可以采用查找效率較高的查找算法。 （2）對有序的順序表可以采用查找效率較高的折半查找算法，而對無序的 順序表只能采用順序查找算法。由此可見排序是

5、計算機程序設(shè)計中一種基礎(chǔ)性 操 作，研究和掌握各種排序方法是非常重要的。 （3）排序算法對于計算機信息處理很重要，一個好的排序不僅可以使信息 查找的效率提高，而且直接影響著計算機的工作效率。 本實驗題目為基于選擇排序方法的類模板設(shè)計與實現(xiàn)，要求建立一維數(shù)組 數(shù)據(jù)結(jié)構(gòu)的模板類，使一維數(shù)組中的數(shù)據(jù)元素可以是 char, int, float 等多種數(shù)據(jù) 類型，并對數(shù)組元素實現(xiàn)選擇類排序。因此實驗采用類模板，可以對不同的數(shù) 據(jù)類型的數(shù)據(jù)進行排序，并通過函數(shù)采用不同的方法進行排序。 2 算法基本原理 （1）簡單選擇排序 從無序的記錄序列中選出一個關(guān)鍵字值最小的記錄存入到指定的位置。 /簡單選擇排序 s

6、electsort(type ar) int i,j; type t; for(i=1;ilen;i+) for(j=i+1;jarrayj) t=arrayi;arrayi=arrayj;arrayj=t; （2）樹形選擇排序 樹形選擇排序的基本思想： 樹形選擇排序又稱錦標賽排序 （tournament sort），是一種按照錦標賽的思想進行選擇排序的方法。首 先對 n 個記錄的關(guān)鍵字進行兩兩比較，然后在n/2 個較小者之間再進行兩 兩比較，如此重復(fù)，直至選出最小的記錄為止。 （3） 堆排序 堆排序由建初始堆和調(diào)整堆兩個過程組成。再次，所謂篩選是指對一棵左 右子樹均為堆的完全二叉樹，經(jīng)調(diào)整根

7、節(jié)點后使之成為堆的過程。建堆時一定 要從最后一個非葉子結(jié)點開始。 堆排序的關(guān)鍵是調(diào)整堆，建初始堆時也是要從最后一個非葉子結(jié)點開始向 根結(jié)點方向進行調(diào)整建堆。假設(shè)完全二叉樹的第 i 個結(jié)點的左子樹，右子樹已 是堆，則對第 i 個結(jié)點進行調(diào)整時，需要將 r2i.key 與 r2i+1.key 之中的最大 者與 ri.key 進行比較，若 ri.key 較小則與之交換。這有可能破壞下一級的堆， 因此，需要繼續(xù)采用上述方法調(diào)整構(gòu)造下一級的堆。如此反復(fù)，直到將以第 i 個結(jié)點為根的子樹構(gòu)成堆為止。 算法: heapsort(type ar) int i; type t; /循環(huán)建立初始堆 for(i=l

8、en/2;i=1;i-) adjusttree(array,i,len); /進行 n-1 次循環(huán)，完成堆排序 for(i=len;i=2;i-) t=arrayi; arrayi=array1; array1=t; adjusttree(array,1,i-1); 3 類設(shè)計 從上面的算法分析可以看到，本設(shè)計面臨的問題的關(guān)鍵是類模板?？梢远?義一個模板類 sort，模板類 sort 功能有輸入，輸出數(shù)組，用三種方法對數(shù)組進 行排序。 從問題的需要來看，在模板類中定義三個成員函數(shù)。成員函數(shù) selectsort（）對數(shù)組進行簡單選擇排序，成員函數(shù) tree_select_sort（）對數(shù)組進

9、行樹形選擇排序，成員函數(shù) heapsort（）對數(shù)組進行堆排序。成員函數(shù) adjusttree（）通過始建和調(diào)整堆輔助堆排序，而成員函數(shù) write( ) 和 print( ) 輸入輸出數(shù)組。主函數(shù)中應(yīng)用 if( ) 判斷語句確定數(shù)組數(shù)據(jù)類型，swich（）語句 選擇使用的排序方法。定義了兩個對象分別是整型和字符型的。 類用 template 限定，其中的數(shù)據(jù)類型用 type 代替，所有的成 員函數(shù)都用 template 修飾，使之能適用于多種數(shù)據(jù)類型。 4 基于控制臺的應(yīng)用程序 整個程序只用一個獨立的文檔，文件中包含一個模板類，主函數(shù)中定義多 個對象來實現(xiàn)調(diào)用三個成員函數(shù)對數(shù)組進行簡單選擇排

10、序，樹形選擇排序，堆 排序這三種排序，在此定義了三個對象分別是整型、字符型和浮點型的。 4.1 類的接口設(shè)計 #include #include #include #include #define num 50 #define m 50 #define min_value -10000 templateclass sort public: /外部接口 void adjusttree(type ar,int n,int k); void write(); void selectsort(type ar); void tree_select_sort(type arr,int n); void h

11、eapsort(type ar); void print(); int len; type arraynum; ; 在此定義了模板類，類中所有的成員函數(shù)和成員變量均定義為 public 的公 有類型，是類的對外接口，數(shù)據(jù)類型用 type 代替。成員函數(shù)在類中只有函數(shù)類 型，函數(shù)名，參數(shù)，對函數(shù)進行內(nèi)部聲明，函數(shù)體在類體外定義 4.2 類的實現(xiàn) /簡單選擇排序 template void sort:selectsort(type ar) int i,j; type t; for(i=1;ilen;i+) for(j=i+1;jarrayj) t=arrayi;arrayi=arrayj;arra

12、yj=t; template void sort:tree_select_sort(type arr,int n) /樹形選擇排序 type treem; / 樹 int basesize; / 當(dāng) n 是 2 的冪次時,basesize 是 n, 當(dāng) n 不是時,basesize 是大 于 n 的最小的 2 的冪次 / 就是構(gòu)造成滿二叉樹的最下層的大小，即葉子數(shù) int i; type max; / 最大值 int maxindex; / 最大數(shù)的下標 int treesize; / 最終這棵樹會達到的大小 basesize = 1; while (basesize n) basesize

13、*= 2; treesize = basesize * 2 - 1;/滿二叉樹的所有結(jié)點個數(shù)等于葉子數(shù)的 2 倍減一 for (i = 0;i n;i+) / 從數(shù)組的后面部分開始填充, 不使用 tree0 treetreesize - i = arri; for (;i 1;i -= 2) / 以 arri和 arri + 1為子結(jié)點的數(shù)的根是 arri和 arri + 1中的較大者 treei / 2 = (treei treei - 1 ? treei : treei - 1); n = n - 1; /此時的 n 表示當(dāng)前 tree1應(yīng)該放到 arr 中的位置 / 不斷把樹中值為最大值

14、的結(jié)點移走,直到 n 的值為-1 while (n != -1) max = tree1; arrn- = max; maxindex = treesize; / 在葉子上找到最大值對應(yīng)的下標 while (treemaxindex != max) maxindex-; treemaxindex = min_value; / 沿著葉子上的結(jié)點到根的路徑更新 while (maxindex 1) / 當(dāng)結(jié)點還有父結(jié)點時 if (maxindex % 2 = 0) / 如果值為最大值的結(jié)點是左子結(jié)點 / 用子結(jié)點中較大值代替父結(jié)點 treemaxindex / 2 = (treemaxindex

15、treemaxindex + 1 ? treemaxindex : treemaxindex + 1); else / 如果不是左子結(jié)點 / 用子結(jié)點中較大值代替父結(jié)點 treemaxindex / 2 = (treemaxindex treemaxindex - 1 ? treemaxindex : treemaxindex - 1); maxindex /= 2; / 繼續(xù)處理父結(jié)點 template void sort:adjusttree(type ar,int k,int n) /調(diào)整堆 int i,j; i=k; j=2*i; /arrauj是 arrayi的左孩子 type te

16、mp=arrayi; while(j=n) if(jn if(temparrayj) arrayi=arrayj; /arrayj調(diào)整到雙親結(jié)點 i=j; j=2*i; else break; arrayi=temp; template void sort:heapsort(type ar) /堆排序 int i; type t; for(i=len/2;i=1;i-) /循環(huán)建立初始堆 adjusttree(array,i,len); for(i=len;i=2;i-) /進行 n-1 次循環(huán)，完成堆排序 t=arrayi; arrayi=array1; array1=t; adjusttr

17、ee(array,1,i-1); template void sort:write() /輸入數(shù)組 int i,l; printf(請輸入數(shù)組長度:); scanf(%d, len=l; printf(請輸入數(shù)組元素:n); for(i=1;iarrayi; template void sort:print() /輸出數(shù)組 int i; printf(排序后的數(shù)組為:n); for(i=1;i=len;i+) coutarrayi ; coutendl; 在類的成員函數(shù)實現(xiàn)過程中，系統(tǒng)會自動為類產(chǎn)生構(gòu)造函數(shù)，類的構(gòu)造函 數(shù)自動調(diào)用，為類動態(tài)分配了內(nèi)存空間，整個調(diào)用過程中完全是由系統(tǒng)內(nèi)部完 成。

18、 成員函數(shù)對成員變量進行操作，實現(xiàn)排序功能，通過 for( ) 循環(huán)，實現(xiàn)輸入輸 出數(shù)組元素的功能。 4.3 主函數(shù)設(shè)計 在程序的主函數(shù)部分，選擇了分別以 int、char 和 float 型為數(shù)據(jù)類型的對象 作為實際例子來驗證算法。首先，選擇數(shù)據(jù)類型；然后，通過 write( ) 函數(shù)對 成員變量數(shù)組 array 進行賦值，通過 swich（）語句選擇排序方式，用對象調(diào) 用對應(yīng)的成員函數(shù)實現(xiàn)數(shù)組排序；最后，通過 print（）函數(shù)輸出排序后的結(jié)果。 void main() /主函數(shù) int i,j=1; sort s; sort p; sort z; cout選擇輸入類型:1.int 2.c

19、har 3.floati; if(i=1) s.write(); cout請選擇排序方式:1.簡單選擇排序 2.樹形選擇排序 3.堆排序i; switch(i) case 1:s.selectsort(s.array);break; case 2:s.tree_select_sort(s.array,s.len+1);break; case 3:s.heapsort(s.array);break; default:break; s.print(); else if(i=2) p.write(); cout請選擇排序方式:1.簡單選擇排序 2.樹形選擇排序 3.堆排序 i; switch(i)

20、case 1:p.selectsort(p.array);break; case 2:p.tree_select_sort(p.array,p.len+1);break; case 3:p.heapsort(p.array);break; default:break; p.print(); else if(i=3) z.write(); cout請選擇排序方式:1.簡單選擇排序 2.樹形選擇排序 3.堆排序 i; switch(i) case 1:z.selectsort(z.array);break; case 2:z.tree_select_sort(z.array,z.len+1);br

21、eak; case 3:z.heapsort(z.array);break; default:break; z.print(); 4.4 基于控制臺的應(yīng)用程序測試基于控制臺的應(yīng)用程序測試 （1）用簡單選擇排序進行 int 類型的排序 圖 1 （2） 用樹形選擇排序進行 char 類型的排序 圖 2 （3）用堆排序進行 float 類型的排序 圖 3 5 基于 mfc 的應(yīng)用程序 mfc 的圖形界面程序設(shè)計可在上述類設(shè)計的基礎(chǔ)上進行改造，mfc 的圖 形界面程序與 dos 界面程序的主要不同點是：mfc 圖形界面程序與 dos 界面 程序的輸入輸出方式不同，dos 界面程序采用字符交互式實現(xiàn)數(shù)據(jù)

22、輸入輸出， 主要通過 cin，cout 等 i/o 流實現(xiàn)，而 mfc 的圖形程序界面采用標準 windows 窗口和控件實現(xiàn)輸入輸出，因此必須在 mfc 類的框架下加入上面所設(shè)計的矩陣 和方程組類，并通過圖形界面的輸入輸出改造來完成。 5.1.1 mfc 程序界面設(shè)計 首先在 vc 中建立 mfc appwizard（exe）工程，名稱為 1203060128，并 在向?qū)У?step1 中選擇基本對話框，即建立基于對話框的應(yīng)用程序，如下圖 4、 圖 5 所示。 圖 4 建立 mfc appwizard（exe）工程 圖 5 建立基于對話框的應(yīng)用程序 將對話框資源中的默認對話框利用工具箱改造成

23、如下界面，如圖 6 所示。 圖 6 選擇排序方法的實現(xiàn)界面設(shè)計 圖 3 所示的界面中包含了 2 個 static text 控件，3 個 button 控件，和 10 個 edit box 控件, 控件的基本信息列表如下表 1 所示。 表 1 控件基本信息 輸入前 static textidc_static 輸入后 idc_button_1簡單選擇排序 idc_button_2樹形選擇排序botton idc_button_3堆排序 idc_edit_m1 idc_edit_m5輸入的 5 個元素 edit box idc_edit_m6 idc_edit_m10輸出的 5 個元素 5.1.2

24、 mfc 程序代碼設(shè)計 為了能夠?qū)υ捒蚪缑嫔系目丶軌蚺c代碼聯(lián)系起來，需要為 10 個 edit box 控件建立 member variables，按 ctrl+w 鍵進入 mfc classwizard 界面，選 擇 member variables 選項卡，可顯示成員變量設(shè)置界面，如圖 7 所示。 圖 7 成員變量設(shè)置界面 通過該界面設(shè)置與 10 個 edit box 控件對應(yīng)的成員變量，具體如表 2 所示。 表 2 控件基本信息 控件 id成員變量類型成員變量名稱 idc_edit_m1 idc_edit_m5intm_1m_5 idc_edit_m6 idc_editm_10int

25、m_6m_10 下面是編寫代碼的重要階段 （1）簡單選擇排序 int a5; updatedata(true); a0=m_l1; a1=m_l2; a2=m_l3; a3=m_l4; a4=m_l5; int i,j,k; int temp; int len=5; for(i=0;i=len;i+) k=i; for(j=i+1;jaj) k=j; if(k!=i) temp=ak; ak=ai; ai=temp; m_l6=a0; m_l7=a1; m_l8=a2; m_l9=a3; m_l10=a4; updatedata(false); （2）樹形選擇排序 int a5; update

26、data(true); a0=m_l1; a1=m_l2; a2=m_l3; a3=m_l4; a4=m_l5; char tree50; /樹 int max;/最大值 int basesize; int i; int maxindex;/最大值的下標 int treesize;/最終這棵樹會達到的大小 int len=5; int min_value=0; basesize=1; while(basesizelen) basesize*=2; treesize=basesize*2-1; for(i=0;ilen;i+) treetreesize-i=ai; for(;i1;i-=2) t

27、reei/2=(treeitreei-1?treei:treei-1); len=len-1; while(len!=-1) max=tree1; alen-=max; maxindex=treesize; while(treemaxindex!=max) maxindex-; treemaxindex=min_value; while(maxindex1) if(maxindex%2=0) treemaxindex/2=(treemaxindextreemaxindex+1?treemaxindex:treemaxindex+1); else treemaxindex/2=(treemaxi

28、ndextreemaxindex-1?treemaxindex:treemaxindex-1); maxindex/=2; m_l6=a0; m_l7=a1; m_l8=a2; m_l9=a3; m_l10=a4; updatedata(false); （3）堆排序 int a5; updatedata(true); a0=m_l1; a1=m_l2; a2=m_l3; a3=m_l4; a4=m_l5; int i=0,j,temp; int p=10; int q=10; int len=5; j=2*p; while(j=q)/堆頂元素下篩 if(jq) ap=aj;p=j; j*=2; ap=temp; temp=a1; a1=ai; ai=temp; m_l6=a0; m_l7=a1; m_l8=a2; m_l9=a3; m_l10=a4; updatedata(false); 5.2 基于 mfc 的應(yīng)用程序測試 運行程序后，首先出現(xiàn)的界面如圖 8 所示。 圖 8 程序初始運行界面 單擊簡單選擇排序按鈕后，可將輸入前的字符進行排序，如圖 6 所示。 圖 9 排序后的界面 結(jié)