2023年全國碩士研究生考試考研英語一試題真題(含答案詳解+作文范文)_第1頁
已閱讀1頁,還剩24頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

1、<p><b>  課程設(shè)計(jì)任務(wù)書</b></p><p><b>  摘 要</b></p><p>  計(jì)算機(jī)中存儲的數(shù)據(jù),初始時(shí)沒有任何排列規(guī)律,根據(jù)實(shí)際需求,經(jīng)常要排列成有規(guī)律的數(shù)據(jù)序列也就是將數(shù)據(jù)序列按關(guān)鍵字升序或降序規(guī)律排列。</p><p>  選擇排序是排序法中很經(jīng)典的算法,選擇排序法可以分為簡單

2、選擇排序、樹形選擇排序和堆排序。</p><p>  本文采用C++語言實(shí)現(xiàn)了選擇排序功能,設(shè)計(jì)了模板類,實(shí)現(xiàn)了int型float型和char型數(shù)組的排序,設(shè)計(jì)了簡單選擇排序、樹形選擇排序和堆排序的三個函數(shù)體,采用Visual C++ 6.0的控制臺工程和MFC工程分別實(shí)現(xiàn)了各類型數(shù)組的排序,通過對兩種程序的測試結(jié)果表明:簡單選擇排序是選擇排序的基礎(chǔ),而樹形選擇排序和堆排序是簡單選擇排序的改進(jìn)。</p>

3、;<p>  關(guān)鍵詞:模板類;簡單選擇排序;樹形選擇排序;堆排序;控制臺工程;MFC工程。</p><p><b>  目 錄</b></p><p><b>  1 需求分析1</b></p><p>  2 算法基本原理1</p><p><b>  3 類設(shè)計(jì)

4、3</b></p><p>  4 基于控制臺的應(yīng)用程序3</p><p>  4.1 類的接口設(shè)計(jì)4</p><p>  4.2 類的實(shí)現(xiàn)4</p><p>  4.3 主函數(shù)設(shè)計(jì)9</p><p>  4.4 基于控制臺的應(yīng)用程序測試11</p><p> 

5、 5 基于MFC的應(yīng)用程序13</p><p>  5.1 基于MFC的應(yīng)用程序設(shè)計(jì)13</p><p>  5.1.1 MFC程序界面設(shè)計(jì)13</p><p>  5.1.2 MFC程序代碼設(shè)計(jì)15</p><p>  5.2基于MFC的應(yīng)用程序測試21</p><p><b>  結(jié) 論

6、22</b></p><p><b>  參考文獻(xiàn)23</b></p><p><b>  1 需求分析</b></p><p> ?。?)當(dāng)進(jìn)行數(shù)據(jù)處理時(shí),經(jīng)常遇到需要進(jìn)行查找操作,通常希望待處理的數(shù)據(jù)按關(guān)鍵字大小有序排序,因?yàn)檫@樣就可以采用查找效率較高的查找算法。</p><p&g

7、t;  (2)對有序的順序表可以采用查找效率較高的折半查找算法,而對無序的</p><p>  順序表只能采用順序查找算法。由此可見排序是計(jì)算機(jī)程序設(shè)計(jì)中一種基礎(chǔ)性操</p><p>  作,研究和掌握各種排序方法是非常重要的。</p><p> ?。?)排序算法對于計(jì)算機(jī)信息處理很重要,一個好的排序不僅可以使信息 查找的效率提高,而且直接影響著計(jì)算機(jī)的工作效率。

8、</p><p>  本實(shí)驗(yàn)題目為基于選擇排序方法的類模板設(shè)計(jì)與實(shí)現(xiàn),要求建立一維數(shù)組數(shù)據(jù)結(jié)構(gòu)的模板類,使一維數(shù)組中的數(shù)據(jù)元素可以是char, int, float等多種數(shù)據(jù)類型,并對數(shù)組元素實(shí)現(xiàn)選擇類排序。因此實(shí)驗(yàn)采用類模板,可以對不同的數(shù)據(jù)類型的數(shù)據(jù)進(jìn)行排序,并通過函數(shù)采用不同的方法進(jìn)行排序。</p><p><b>  2 算法基本原理</b></p&g

9、t;<p><b> ?。?)簡單選擇排序</b></p><p>  從無序的記錄序列中選出一個關(guān)鍵字值最小的記錄存入到指定的位置。</p><p><b>  //簡單選擇排序</b></p><p>  SelectSort(Type ar[]) </p><p><b

10、>  {</b></p><p><b>  int i,j;</b></p><p><b>  Type t;</b></p><p>  for(i=1;i<len;i++)</p><p>  for(j=i+1;j<=len;j++)</p>&

11、lt;p>  if(array[i]>array[j])</p><p>  {t=array[i];array[i]=array[j];array[j]=t;}</p><p><b>  }</b></p><p><b> ?。?)樹形選擇排序</b></p><p>  樹形選擇

12、排序的基本思想:樹形選擇排序又稱錦標(biāo)賽排序(Tournament Sort),是一種按照錦標(biāo)賽的思想進(jìn)行選擇排序的方法。首先對n個記錄的關(guān)鍵字進(jìn)行兩兩比較,然后在n/2個較小者之間再進(jìn)行兩兩比較,如此重復(fù),直至選出最小的記錄為止。 </p><p><b>  (3).堆排序</b></p><p>  堆排序由建初始堆和調(diào)整堆兩個過程組成。再次,所謂篩選是指對一棵左

13、右子樹均為堆的完全二叉樹,經(jīng)調(diào)整根節(jié)點(diǎn)后使之成為堆的過程。建堆時(shí)一定要從最后一個非葉子結(jié)點(diǎn)開始。</p><p>  堆排序的關(guān)鍵是調(diào)整堆,建初始堆時(shí)也是要從最后一個非葉子結(jié)點(diǎn)開始向根結(jié)點(diǎn)方向進(jìn)行調(diào)整建堆。假設(shè)完全二叉樹的第i個結(jié)點(diǎn)的左子樹,右子樹已是堆,則對第i個結(jié)點(diǎn)進(jìn)行調(diào)整時(shí),需要將r[2i].key與r[2i+1].key之中的最大者與r[i].key進(jìn)行比較,若r[i].key較小則與之交換。這有可能破壞

14、下一級的堆,因此,需要繼續(xù)采用上述方法調(diào)整構(gòu)造下一級的堆。如此反復(fù),直到將以第i個結(jié)點(diǎn)為根的子樹構(gòu)成堆為止。</p><p><b>  算法:</b></p><p>  HeapSort(Type ar[]) </p><p><b>  {</b></p><p><b>  i

15、nt i;</b></p><p>  Type t; //循環(huán)建立初始堆</p><p>  for(i=len/2;i>=1;i--) </p><p>  AdjustTree(array,i,len);</p><p>  //進(jìn)行n-1次循環(huán),完成堆排序</p>&

16、lt;p>  for(i=len;i>=2;i--) </p><p>  {t=array[i];</p><p>  array[i]=array[1];</p><p>  array[1]=t;</p><p>  AdjustTree(array,1,i-1);</p><p><b&g

17、t;  }</b></p><p><b>  }</b></p><p><b>  3 類設(shè)計(jì)</b></p><p>  從上面的算法分析可以看到,本設(shè)計(jì)面臨的問題的關(guān)鍵是類模板??梢远x一個模板類sort,模板類sort功能有輸入,輸出數(shù)組,用三種方法對數(shù)組進(jìn)行排序。</p><p

18、>  從問題的需要來看,在模板類中定義三個成員函數(shù)。成員函數(shù)SelectSort()對數(shù)組進(jìn)行簡單選擇排序,成員函數(shù)tree_select_sort()對數(shù)組進(jìn)行樹形選擇排序,成員函數(shù)HeapSort()對數(shù)組進(jìn)行堆排序。成員函數(shù)AdjustTree()通過始建和調(diào)整堆輔助堆排序,而成員函數(shù)write( ) 和print( ) 輸入輸出數(shù)組。主函數(shù)中應(yīng)用if( ) 判斷語句確定數(shù)組數(shù)據(jù)類型,swich()語句選擇使用的排序方法。定

19、義了兩個對象分別是整型和字符型的。</p><p>  類用template<class Type> 限定,其中的數(shù)據(jù)類型用type代替,所有的成員函數(shù)都用template<class Type> 修飾,使之能適用于多種數(shù)據(jù)類型。</p><p>  4 基于控制臺的應(yīng)用程序</p><p>  整個程序只用一個獨(dú)立的文檔,文件中包含一個模

20、板類,主函數(shù)中定義多個對象來實(shí)現(xiàn)調(diào)用三個成員函數(shù)對數(shù)組進(jìn)行簡單選擇排序,樹形選擇排序,堆排序這三種排序,在此定義了三個對象分別是整型、字符型和浮點(diǎn)型的。</p><p>  4.1 類的接口設(shè)計(jì)</p><p>  #include<stdio.h></p><p>  #include<string.h></p><p

21、>  #include<stdlib.h></p><p>  #include<iostream.h></p><p>  #define num 50</p><p>  #define M 50</p><p>  #define MIN_VALUE -10000</p><p> 

22、 template<class Type>class Sort</p><p><b>  {</b></p><p>  public: //外部接口</p><p>  void AdjustTree(Type ar[],int n,int k);</p><p>  void wri

23、te();</p><p>  void SelectSort(Type ar[]);</p><p>  void tree_select_sort(Type arr[],int n);</p><p>  void HeapSort(Type ar[]);</p><p>  void print(); </p><p

24、><b>  int len;</b></p><p>  Type array[num]; </p><p><b>  };</b></p><p>  在此定義了模板類,類中所有的成員函數(shù)和成員變量均定義為public的公有類型,是類的對外接口,數(shù)據(jù)類型用type代替。成員函數(shù)在類中只有函數(shù)類型,函數(shù)名,參

25、數(shù),對函數(shù)進(jìn)行內(nèi)部聲明,函數(shù)體在類體外定義</p><p><b>  4.2 類的實(shí)現(xiàn)</b></p><p><b>  //簡單選擇排序</b></p><p>  template <class Type></p><p>  void Sort<Type>::Se

26、lectSort(Type ar[]) </p><p><b>  {</b></p><p><b>  int i,j;</b></p><p><b>  Type t;</b></p><p>  for(i=1;i<len;i++)</p>

27、<p>  for(j=i+1;j<=len;j++)</p><p>  if(array[i]>array[j])</p><p>  {t=array[i];array[i]=array[j];array[j]=t;}</p><p><b>  }</b></p><p>  templat

28、e <class Type></p><p>  void Sort<Type>::tree_select_sort(Type arr[],int n) //樹形選擇排序</p><p><b>  {</b></p><p>  Type tree[M]; // 樹 </p><p>  in

29、t baseSize; // 當(dāng)n是2的冪次時(shí),baseSize是n, 當(dāng)n不是時(shí),baseSize是大于n的最小的2的冪次 </p><p>  // 就是構(gòu)造成滿二叉樹的最下層的大小,即葉子數(shù) </p><p><b>  int i;</b></p><p>  Type max; // 最大值 </p><p>

30、  int maxIndex; // 最大數(shù)的下標(biāo) </p><p>  int treeSize; // 最終這棵樹會達(dá)到的大小 </p><p>  baseSize = 1;</p><p>  while (baseSize < n)</p><p><b>  {</b></p><p

31、>  baseSize *= 2;</p><p><b>  }</b></p><p>  treeSize = baseSize * 2 - 1;//滿二叉樹的所有結(jié)點(diǎn)個數(shù)等于葉子數(shù)的2倍減一</p><p>  for (i = 0;i < n;i++) // 從數(shù)組的后面部分開始填充, 不使用tree[0]</

32、p><p><b>  {</b></p><p>  tree[treeSize - i] = arr[i];</p><p><b>  }</b></p><p>  for (;i < baseSize;i++) // 用MIN_VALUE填充tree,直到一共有baseSize個&l

33、t;/p><p><b>  {</b></p><p>  tree[treeSize - i] = MIN_VALUE;</p><p><b>  }</b></p><p><b>  // 構(gòu)造一棵樹 </b></p><p>  for (i =

34、 treeSize;i > 1;i -= 2)</p><p><b>  {</b></p><p>  // 以arr[i]和arr[i + 1]為子結(jié)點(diǎn)的數(shù)的根是arr[i]和arr[i + 1]中的較大者 </p><p>  tree[i / 2] = (tree[i] > tree[i - 1] ? tree[i] :

35、tree[i - 1]);</p><p><b>  }</b></p><p>  n = n - 1; //此時(shí)的n表示當(dāng)前tree[1]應(yīng)該放到arr中的位置 </p><p>  // 不斷把樹中值為最大值的結(jié)點(diǎn)移走,直到n的值為-1 </p><p>  while (n != -1)</p>

36、<p><b>  {</b></p><p>  max = tree[1];</p><p>  arr[n--] = max;</p><p>  maxIndex = treeSize;</p><p>  // 在葉子上找到最大值對應(yīng)的下標(biāo) </p><p>  while (

37、tree[maxIndex] != max)</p><p><b>  {</b></p><p>  maxIndex--;</p><p><b>  }</b></p><p>  tree[maxIndex] = MIN_VALUE;</p><p>  // 沿著

38、葉子上的結(jié)點(diǎn)到根的路徑更新 </p><p>  while (maxIndex > 1) // 當(dāng)結(jié)點(diǎn)還有父結(jié)點(diǎn)時(shí) </p><p><b>  {</b></p><p>  if (maxIndex % 2 == 0) // 如果值為最大值的結(jié)點(diǎn)是左子結(jié)點(diǎn) </p><p><b>  {</

39、b></p><p>  // 用子結(jié)點(diǎn)中較大值代替父結(jié)點(diǎn) </p><p>  tree[maxIndex / 2] = (tree[maxIndex] > tree[maxIndex + 1] ? tree[maxIndex] : tree[maxIndex + 1]);</p><p><b>  }</b></p>

40、;<p>  else // 如果不是左子結(jié)點(diǎn) </p><p><b>  {</b></p><p>  // 用子結(jié)點(diǎn)中較大值代替父結(jié)點(diǎn) </p><p>  tree[maxIndex / 2] = (tree[maxIndex] > tree[maxIndex - 1] ? tree[maxIndex] : tre

41、e[maxIndex - 1]);</p><p><b>  }</b></p><p>  maxIndex /= 2; // 繼續(xù)處理父結(jié)點(diǎn) </p><p><b>  }</b></p><p><b>  }</b></p><p><

42、b>  }</b></p><p>  template <class Type></p><p>  void Sort<Type>::AdjustTree(Type ar[],int k,int n) //調(diào)整堆</p><p><b>  {</b></p><p>&l

43、t;b>  int i,j;</b></p><p><b>  i=k;</b></p><p>  j=2*i; //arrau[j]是array[i]的左孩子</p><p>  Type temp=array[i];</p><p>  while(j<=n)</p>&

44、lt;p>  {if(j<n&&array[j]<array[j+1]) //若有孩子較大,把j指向右孩子</p><p><b>  j=j+1;</b></p><p>  if(temp<array[j]) </p><p><b>  {</b></p>&l

45、t;p>  array[i]=array[j]; //array[j]調(diào)整到雙親結(jié)點(diǎn)</p><p><b>  i=j;</b></p><p><b>  j=2*i;</b></p><p><b>  }</b></p><p>  else break;&

46、lt;/p><p><b>  }</b></p><p>  array[i]=temp;</p><p><b>  }</b></p><p>  template <class Type></p><p>  void Sort<Type>::He

47、apSort(Type ar[]) //堆排序</p><p><b>  {</b></p><p><b>  int i;</b></p><p><b>  Type t;</b></p><p>  for(i=len/2;i>=1;i--) //循環(huán)建立

48、初始堆</p><p>  AdjustTree(array,i,len);</p><p>  for(i=len;i>=2;i--) //進(jìn)行n-1次循環(huán),完成堆排序</p><p>  {t=array[i];</p><p>  array[i]=array[1];</p><p>  array[1

49、]=t;</p><p>  AdjustTree(array,1,i-1);</p><p><b>  }</b></p><p><b>  }</b></p><p>  template<class Type></p><p>  void Sort&l

50、t;Type>::write() //輸入數(shù)組</p><p><b>  {</b></p><p><b>  int i,l;</b></p><p>  printf("請輸入數(shù)組長度:");</p><p>  scanf("%d",&

51、;l);</p><p><b>  len=l;</b></p><p>  printf("請輸入數(shù)組元素:\n");</p><p>  for(i=1;i<=l;i++)</p><p>  cin>>array[i];</p><p><b&g

52、t;  }</b></p><p>  template<class Type></p><p>  void Sort<Type>::print() //輸出數(shù)組</p><p><b>  {int i;</b></p><p>  printf("排序后的數(shù)組為:\n

53、");</p><p>  for(i=1;i<=len;i++)</p><p>  cout<<array[i]<<" ";</p><p>  cout<<endl;</p><p><b>  }</b></p><p&

54、gt;  在類的成員函數(shù)實(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)部完成。</p><p>  成員函數(shù)對成員變量進(jìn)行操作,實(shí)現(xiàn)排序功能,通過for( ) 循環(huán),實(shí)現(xiàn)輸入輸出數(shù)組元素的功能。</p><p>  4.3 主函數(shù)設(shè)計(jì)</p><p>  在程序的主函數(shù)部分,選擇了分別以int、c

55、har和float型為數(shù)據(jù)類型的對象作為實(shí)際例子來驗(yàn)證算法。首先,選擇數(shù)據(jù)類型;然后,通過write( ) 函數(shù)對成員變量數(shù)組array[ ] 進(jìn)行賦值,通過swich()語句選擇排序方式,用對象調(diào)用對應(yīng)的成員函數(shù)實(shí)現(xiàn)數(shù)組排序;最后,通過print()函數(shù)輸出排序后的結(jié)果。</p><p>  void main() //主函數(shù)</p><p>  { int i,j=1;<

56、/p><p>  Sort<int> s;</p><p>  Sort<char> p;</p><p>  Sort<float> z;</p><p>  cout<<"選擇輸入類型:1.int 2.char 3.float"<<endl;</p>

57、;<p><b>  cin>>i;</b></p><p><b>  if(i==1)</b></p><p>  {s.write();</p><p>  cout<<"請選擇排序方式:1.簡單選擇排序 2.樹形選擇排序 3.堆排序"<<endl

58、;</p><p><b>  cin>>i;</b></p><p><b>  switch(i)</b></p><p><b>  {</b></p><p>  case 1:s.SelectSort(s.array);break;</p>

59、<p>  case 2:s.tree_select_sort(s.array,s.len+1);break;</p><p>  case 3:s.HeapSort(s.array);break;</p><p>  default:break;</p><p><b>  }</b></p><p>  s

60、.print();}</p><p>  else if(i==2)</p><p>  {p.write();</p><p>  cout<<"請選擇排序方式:1.簡單選擇排序 2.樹形選擇排序 3.堆排序<<endl";</p><p><b>  cin>>i;<

61、/b></p><p><b>  switch(i)</b></p><p><b>  {</b></p><p>  case 1:p.SelectSort(p.array);break;</p><p>  case 2:p.tree_select_sort(p.array,p.len

62、+1);break;</p><p>  case 3:p.HeapSort(p.array);break;</p><p>  default:break;</p><p><b>  }</b></p><p>  p.print();}</p><p>  else if(i==3)<

63、/p><p>  {z.write();</p><p>  cout<<"請選擇排序方式:1.簡單選擇排序 2.樹形選擇排序 3.堆排序<<endl";</p><p><b>  cin>>i;</b></p><p><b>  switch(i)<

64、;/b></p><p><b>  {</b></p><p>  case 1:z.SelectSort(z.array);break;</p><p>  case 2:z.tree_select_sort(z.array,z.len+1);break;</p><p>  case 3:z.HeapSort

65、(z.array);break;</p><p>  default:break;</p><p><b>  }</b></p><p>  z.print();}</p><p><b>  }</b></p><p>  4.4 基于控制臺的應(yīng)用程序測試</p&

66、gt;<p>  用簡單選擇排序進(jìn)行int類型的排序</p><p><b>  圖1</b></p><p>  用樹形選擇排序進(jìn)行char類型的排序</p><p><b>  圖2 </b></p><p>  (3)用堆排序進(jìn)行float類型的排序</p><

67、;p><b>  圖3</b></p><p>  5 基于MFC的應(yīng)用程序</p><p>  MFC的圖形界面程序設(shè)計(jì)可在上述類設(shè)計(jì)的基礎(chǔ)上進(jìn)行改造,MFC的圖形界面程序與DOS界面程序的主要不同點(diǎn)是:MFC圖形界面程序與DOS界面程序的輸入輸出方式不同,DOS界面程序采用字符交互式實(shí)現(xiàn)數(shù)據(jù)輸入輸出,主要通過cin,cout等I/O流實(shí)現(xiàn),而MFC的圖形程

68、序界面采用標(biāo)準(zhǔn)Windows窗口和控件實(shí)現(xiàn)輸入輸出,因此必須在MFC類的框架下加入上面所設(shè)計(jì)的矩陣和方程組類,并通過圖形界面的輸入輸出改造來完成。</p><p>  5.1.1 MFC程序界面設(shè)計(jì)</p><p>  首先在VC中建立MFC AppWizard(exe)工程,名稱為1203060128,并在向?qū)У腟tep1中選擇基本對話框,即建立基于對話框的應(yīng)用程序,如下圖4、圖5所示

69、。</p><p>  圖4建立MFC AppWizard(exe)工程</p><p>  圖5 建立基于對話框的應(yīng)用程序</p><p>  將對話框資源中的默認(rèn)對話框利用工具箱改造成如下界面,如圖6所示。</p><p>  圖6 選擇排序方法的實(shí)現(xiàn)界面設(shè)計(jì)</p><p>  圖3所示的界面中包含了2個Stat

70、ic Text控件,3個Button控件,和10個Edit Box控件, 控件的基本信息列表如下表1所示。</p><p><b>  表1 控件基本信息</b></p><p>  5.1.2 MFC程序代碼設(shè)計(jì)</p><p>  為了能夠?qū)υ捒蚪缑嫔系目丶軌蚺c代碼聯(lián)系起來,需要為10個Edit Box控件建立Member Varia

71、bles,按Ctrl+w鍵進(jìn)入MFC ClassWizard界面,選擇Member Variables選項(xiàng)卡,可顯示成員變量設(shè)置界面,如圖7所示。</p><p>  圖7 成員變量設(shè)置界面</p><p>  通過該界面設(shè)置與10個Edit Box控件對應(yīng)的成員變量,具體如表2所示。</p><p><b>  表2 控件基本信息</b>&l

72、t;/p><p>  下面是編寫代碼的重要階段</p><p><b>  簡單選擇排序</b></p><p><b>  int a[5];</b></p><p>  UpdateData(true);</p><p>  a[0]=m_l1;</p><

73、;p>  a[1]=m_l2;</p><p>  a[2]=m_l3;</p><p>  a[3]=m_l4;</p><p>  a[4]=m_l5;</p><p>  int i,j,k;</p><p><b>  int temp;</b></p><p&g

74、t;  int len=5;</p><p>  for(i=0;i<=len;i++)</p><p><b>  { k=i;</b></p><p>  for(j=i+1;j<=len;j++)</p><p>  if(a[k]>a[j])</p><p><b

75、>  k=j;</b></p><p><b>  if(k!=i)</b></p><p><b>  {</b></p><p>  temp=a[k];</p><p>  a[k]=a[i];</p><p>  a[i]=temp;</p&g

76、t;<p><b>  }</b></p><p><b>  }</b></p><p>  m_l6=a[0];</p><p>  m_l7=a[1];</p><p>  m_l8=a[2];</p><p>  m_l9=a[3];</p>

77、<p>  m_l10=a[4];</p><p>  UpdateData(false);</p><p><b>  樹形選擇排序</b></p><p><b>  int a[5];</b></p><p>  UpdateData(true);</p><

78、p>  a[0]=m_l1;</p><p>  a[1]=m_l2;</p><p>  a[2]=m_l3;</p><p>  a[3]=m_l4;</p><p>  a[4]=m_l5;</p><p>  char tree[50]; //樹 </p><p&

79、gt;  int max;//最大值</p><p>  int baseSize;</p><p><b>  int i;</b></p><p>  int maxIndex;//最大值的下標(biāo)</p><p>  int treeSize;//最終這棵樹會達(dá)到的大小</p><p>  in

80、t len=5;</p><p>  int MIN_VALUE=0;</p><p>  baseSize=1;</p><p>  while(baseSize<len)</p><p><b>  {</b></p><p>  baseSize*=2;</p><

81、p><b>  }</b></p><p>  treeSize=baseSize*2-1;</p><p>  for(i=0;i<len;i++)</p><p><b>  {</b></p><p>  tree[treeSize-i]=a[i];</p><

82、p><b>  }</b></p><p>  for(;i<baseSize;i++)</p><p><b>  {</b></p><p>  tree[treeSize-i]=MIN_VALUE;</p><p><b>  }//構(gòu)造一棵樹</b><

83、/p><p>  for(i=treeSize;i>1;i-=2)</p><p><b>  {</b></p><p>  tree[i/2]=(tree[i]>tree[i-1]?tree[i]:tree[i-1]);</p><p><b>  }</b></p>&l

84、t;p>  len=len-1;</p><p>  while(len!=-1)</p><p><b>  {</b></p><p>  max=tree[1];</p><p>  a[len--]=max;</p><p>  maxIndex=treeSize;</p>

85、;<p>  while(tree[maxIndex]!=max)</p><p><b>  { </b></p><p>  maxIndex--;</p><p><b>  }</b></p><p>  tree[maxIndex]=MIN_VALUE;</p>

86、<p>  while(maxIndex>1)</p><p><b>  {</b></p><p>  if(maxIndex%2==0)</p><p><b>  {</b></p><p>  tree[maxIndex/2]=(tree[maxIndex]>tr

87、ee[maxIndex+1]?tree[maxIndex]:tree[maxIndex+1]);</p><p><b>  }</b></p><p><b>  else</b></p><p><b>  {</b></p><p>  tree[maxIndex/2]=

88、(tree[maxIndex]>tree[maxIndex-1]?tree[maxIndex]:tree[maxIndex-1]);</p><p><b>  }</b></p><p>  maxIndex/=2;</p><p><b>  }</b></p><p><b>

89、  }</b></p><p>  m_l6=a[0];</p><p>  m_l7=a[1];</p><p>  m_l8=a[2];</p><p>  m_l9=a[3];</p><p>  m_l10=a[4];</p><p>  UpdateData(false);

90、</p><p><b>  堆排序</b></p><p><b>  int a[5];</b></p><p>  UpdateData(true);</p><p>  a[0]=m_l1;</p><p>  a[1]=m_l2;</p><p&

91、gt;  a[2]=m_l3;</p><p>  a[3]=m_l4;</p><p>  a[4]=m_l5;</p><p>  int i=0,j,temp;</p><p><b>  int p=10;</b></p><p><b>  int q=10;</b>

92、;</p><p>  int len=5;</p><p><b>  j=2*p;</b></p><p>  while(j<=q)//堆頂元素下篩</p><p>  {if((j<q)&&(a[j]<a[j+1]))//確定下篩位置</p><p>&l

93、t;b>  ++j;</b></p><p>  temp=a[i];</p><p>  if(temp>a[j])break;</p><p>  a[p]=a[j];p=j;</p><p><b>  j*=2;}</b></p><p>  a[p]=temp;&

94、lt;/p><p>  {temp=a[1];</p><p>  a[1]=a[i];</p><p>  a[i]=temp;}</p><p>  m_l6=a[0];</p><p>  m_l7=a[1];</p><p>  m_l8=a[2];</p><p>

95、  m_l9=a[3];</p><p>  m_l10=a[4];</p><p>  UpdateData(false);</p><p>  5.2基于MFC的應(yīng)用程序測試</p><p>  運(yùn)行程序后,首先出現(xiàn)的界面如圖8所示。</p><p>  圖8 程序初始運(yùn)行界面</p><p&g

96、t;  單擊簡單選擇排序按鈕后,可將輸入前的字符進(jìn)行排序,如圖6所示。</p><p><b>  圖9 排序后的界面</b></p><p><b>  結(jié) 論</b></p><p>  本次課程設(shè)計(jì),在DOS界面中,先用template<class Type>class定義sort模板類,類中數(shù)據(jù)類型用t

97、ype代替,我定義了三個成員函數(shù),SelectSort(),tree_select_sort(),HeapSort(),分別實(shí)現(xiàn)對成員變量array[ ]數(shù)組的簡單選擇排序,樹形選擇排序,堆排序,又定義了兩個成員函數(shù)write( ) 和print( ),分別輸入和輸出成員變量,根據(jù)模板類的定義要求,成員函數(shù)都用template<class Type>修飾,使之能適用于多種數(shù)據(jù)類型,而不是局限于一種。我將函數(shù)的聲明與定義分離,

98、在類中聲明函數(shù),在類體外定義函數(shù),是程序清晰易讀。通過努力,程序正確運(yùn)行,并得到了實(shí)驗(yàn)要求的結(jié)果,說明本次程序?qū)崿F(xiàn)了其主要功能。而我通過本次實(shí)驗(yàn)學(xué)到了如何定義模板類,如何使用多種方法為數(shù)組排序。</p><p>  MFC程序與DOS界面程序編寫的最大不同是程序員需要將編程精力放在圖形界面設(shè)計(jì)、圖形界面輸入輸出以及界面各種排序的設(shè)計(jì)等問題上,而這些問題在DOS界面程序中是不存在的。本次課程設(shè)計(jì)作為編寫Window

99、s程序的初步嘗試,能夠?qū)崿F(xiàn)程序的主要功能,可以說是取得了成功,然而好的程序絕不僅僅是只有功能性這一個指標(biāo),編寫出一個基于Windows界面的程序時(shí),所獲得的滿足程度遠(yuǎn)遠(yuǎn)大于簡單的DOS界面程序,本次編寫的MFC程序雖然能實(shí)現(xiàn)所需功能,但從面向?qū)ο蟪绦蛟O(shè)計(jì)理念和圖形界面設(shè)計(jì)要求來說,尚存在不足,主要包括以下幾個方面。</p><p>  本次的MFC程序只能對整型數(shù)組排序,如果改為char型、float型的,需從屬

100、性的對話框中重復(fù)選擇。這樣確實(shí)很不實(shí)用。作者希望選擇的類型可以自主進(jìn)行轉(zhuǎn)換</p><p> ?。?)將類的定義與實(shí)現(xiàn)放在同一個頭文件中也違背了面向?qū)ο蟪绦蛟O(shè)計(jì)理念,需要將二者分開成定義文件和實(shí)現(xiàn)文件。</p><p><b>  參考文獻(xiàn)</b></p><p>  [1] 譚浩強(qiáng). C程序設(shè)計(jì). 北京:清華大學(xué)出版社,1991</p&

101、gt;<p>  [2] 鄭振潔C++程序設(shè)計(jì). 北京:人民郵電出版社,2005</p><p>  [3] 柴欣.C/ C++程序設(shè)計(jì). 河北大學(xué)出版社,2002</p><p>  [4] 余蘇寧、王明福.C++程序設(shè)計(jì). 北京:高等教育出版社,2003</p><p>  [5] 李云清、楊慶紅、揭安全.數(shù)據(jù)結(jié)構(gòu)[m] .人民郵電大學(xué)出版社,20

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論