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

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

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

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

5、計(jì)算機(jī)程序設(shè)計(jì)中一種基礎(chǔ)性 操 作，研究和掌握各種排序方法是非常重要的。 （3）排序算法對(duì)于計(jì)算機(jī)信息處理很重要，一個(gè)好的排序不僅可以使信息 查找的效率提高，而且直接影響著計(jì)算機(jī)的工作效率。 本實(shí)驗(yàn)題目為基于選擇排序方法的類模板設(shè)計(jì)與實(shí)現(xiàn)，要求建立一維數(shù)組 數(shù)據(jù)結(jié)構(gòu)的模板類，使一維數(shù)組中的數(shù)據(jù)元素可以是 char, int, float 等多種數(shù)據(jù) 類型，并對(duì)數(shù)組元素實(shí)現(xiàn)選擇類排序。因此實(shí)驗(yàn)采用類模板，可以對(duì)不同的數(shù) 據(jù)類型的數(shù)據(jù)進(jìn)行排序，并通過函數(shù)采用不同的方法進(jìn)行排序。 2 算法基本原理 （1）簡(jiǎn)單選擇排序 從無序的記錄序列中選出一個(gè)關(guān)鍵字值最小的記錄存入到指定的位置。 /簡(jiǎ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）樹形選擇排序 樹形選擇排序的基本思想： 樹形選擇排序又稱錦標(biāo)賽排序 （tournament sort），是一種按照錦標(biāo)賽的思想進(jìn)行選擇排序的方法。首 先對(duì) n 個(gè)記錄的關(guān)鍵字進(jìn)行兩兩比較，然后在n/2 個(gè)較小者之間再進(jìn)行兩 兩比較，如此重復(fù)，直至選出最小的記錄為止。 （3） 堆排序 堆排序由建初始堆和調(diào)整堆兩個(gè)過程組成。再次，所謂篩選是指對(duì)一棵左 右子樹均為堆的完全二叉樹，經(jīng)調(diào)整根

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

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

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

10、序，樹形選擇排序，堆 排序這三種排序，在此定義了三個(gè)對(duì)象分別是整型、字符型和浮點(diǎn)型的。 4.1 類的接口設(shè)計(jì) #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 的公 有類型，是類的對(duì)外接口，數(shù)據(jù)類型用 type 代替。成員函數(shù)在類中只有函數(shù)類 型，函數(shù)名，參數(shù)，對(duì)函數(shù)進(jìn)行內(nèi)部聲明，函數(shù)體在類體外定義 4.2 類的實(shí)現(xiàn) /簡(jiǎ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 的冪次時(shí),basesize 是 n, 當(dāng) n 不是時(shí),basesize 是大 于 n 的最小的 2 的冪次 / 就是構(gòu)造成滿二叉樹的最下層的大小，即葉子數(shù) int i; type max; / 最大值 int maxindex; / 最大數(shù)的下標(biāo) int treesize; / 最終這棵樹會(huì)達(dá)到的大小 basesize = 1; while (basesize n) basesize

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

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

15、treemaxindex + 1 ? treemaxindex : treemaxindex + 1); else / 如果不是左子結(jié)點(diǎn) / 用子結(jié)點(diǎn)中較大值代替父結(jié)點(diǎn) treemaxindex / 2 = (treemaxindex treemaxindex - 1 ? treemaxindex : treemaxindex - 1); maxindex /= 2; / 繼續(xù)處理父結(jié)點(diǎn) 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é)點(diǎn) 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-) /進(jìn)行 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(請(qǐng)輸入數(shù)組長(zhǎng)度:); scanf(%d, len=l; printf(請(qǐng)輸入數(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ù)實(shí)現(xiàn)過程中，系統(tǒng)會(huì)自動(dòng)為類產(chǎn)生構(gòu)造函數(shù)，類的構(gòu)造函 數(shù)自動(dòng)調(diào)用，為類動(dòng)態(tài)分配了內(nèi)存空間，整個(gè)調(diào)用過程中完全是由系統(tǒng)內(nèi)部完 成。

18、 成員函數(shù)對(duì)成員變量進(jìn)行操作，實(shí)現(xiàn)排序功能，通過 for( ) 循環(huán)，實(shí)現(xiàn)輸入輸 出數(shù)組元素的功能。 4.3 主函數(shù)設(shè)計(jì) 在程序的主函數(shù)部分，選擇了分別以 int、char 和 float 型為數(shù)據(jù)類型的對(duì)象 作為實(shí)際例子來驗(yàn)證算法。首先，選擇數(shù)據(jù)類型；然后，通過 write( ) 函數(shù)對(duì) 成員變量數(shù)組 array 進(jìn)行賦值，通過 swich（）語句選擇排序方式，用對(duì)象調(diào) 用對(duì)應(yīng)的成員函數(shù)實(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請(qǐng)選擇排序方式:1.簡(jiǎn)單選擇排序 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請(qǐng)選擇排序方式:1.簡(jiǎn)單選擇排序 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請(qǐng)選擇排序方式:1.簡(jiǎn)單選擇排序 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 基于控制臺(tái)的應(yīng)用程序測(cè)試基于控制臺(tái)的應(yīng)用程序測(cè)試 （1）用簡(jiǎn)單選擇排序進(jìn)行 int 類型的排序 圖 1 （2） 用樹形選擇排序進(jìn)行 char 類型的排序 圖 2 （3）用堆排序進(jìn)行 float 類型的排序 圖 3 5 基于 mfc 的應(yīng)用程序 mfc 的圖形界面程序設(shè)計(jì)可在上述類設(shè)計(jì)的基礎(chǔ)上進(jìn)行改造，mfc 的圖 形界面程序與 dos 界面程序的主要不同點(diǎn)是：mfc 圖形界面程序與 dos 界面 程序的輸入輸出方式不同，dos 界面程序采用字符交互式實(shí)現(xiàn)數(shù)據(jù)

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

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

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

25、m_6m_10 下面是編寫代碼的重要階段 （1）簡(jiǎn)單選擇排序 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;/最大值的下標(biāo) int treesize;/最終這棵樹會(huì)達(dá)到的大小 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)用程序測(cè)試 運(yùn)行程序后，首先出現(xiàn)的界面如圖 8 所示。 圖 8 程序初始運(yùn)行界面 單擊簡(jiǎn)單選擇排序按鈕后，可將輸入前的字符進(jìn)行排序，如圖 6 所示。 圖 9 排序后的界面 結(jié)