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

下載本文檔

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

文檔簡介

1、<p>  數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(論文)</p><p>  題 目: 多種排序的實現(xiàn)與比較 </p><p>  學生姓名: </p><p>  學 號: </p><p>  所在院(系): </p><p>  專

2、 業(yè): </p><p>  班 級: </p><p>  指 導 教 師: 職稱: </p><p>  2013年 6 月 21 日</p><p><b>  課程設(shè)計任務(wù)書</b></p><p>  注:任務(wù)書由指導教師填寫。</p>

3、<p><b>  目 錄</b></p><p><b>  摘 要5</b></p><p>  1《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計的目的、意義和任務(wù)6</p><p>  1.1《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計的目的和意義6</p><p>  1.1.1 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計的目的6</

4、p><p>  1.1.2 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計的意義6</p><p>  1.2 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計的主要任務(wù)6</p><p>  2 綜合排序的主要功能分析7</p><p>  2.1 數(shù)據(jù)對象分析7</p><p>  2.2 功能分析7</p><p>  3 綜合排序的結(jié)

5、構(gòu)、基本操作及算法設(shè)計8</p><p>  3.1 綜合排序的結(jié)構(gòu)設(shè)計8</p><p>  3.1.1綜合排序的邏輯結(jié)構(gòu)設(shè)計8</p><p>  3.1.2 綜合排序的物理結(jié)構(gòu)設(shè)計8</p><p>  3.2綜合排序算法設(shè)計9</p><p>  3.2.1 冒泡排序算法的基本思想和算法描述9<

6、;/p><p>  3.2.2 希爾排序算法的基本思想和算法描述9</p><p>  3.2.3快速排序算法的基本思想和算法描述10</p><p>  3.2.4插入排序算法的基本思想和算法描述10</p><p>  3.2.5選擇排序算法的基本思想和算法描述11</p><p>  4 綜合排序的代碼設(shè)計及

7、編程實現(xiàn)12</p><p>  4.1程序結(jié)構(gòu)設(shè)計12</p><p>  4.1.1流程圖及詳細算法12</p><p>  4.1.2流程圖模塊說明13</p><p>  4.2代碼設(shè)計13</p><p>  4.2.1函數(shù)聲明14</p><p>  4.2.2源程序代

8、碼14</p><p>  4.3系統(tǒng)運行及分析22</p><p>  4.3.1系統(tǒng)運行結(jié)果23</p><p>  4.3.2排序算法的分析29</p><p><b>  5 結(jié)束語30</b></p><p><b>  參考文獻31</b></p

9、><p><b>  摘 要</b></p><p>  數(shù)據(jù)結(jié)構(gòu)是由數(shù)據(jù)元素依據(jù)某種邏輯聯(lián)系組織起來的。對數(shù)據(jù)元素間邏輯關(guān)系的描述稱為數(shù)據(jù)的邏輯結(jié)構(gòu);數(shù)據(jù)必須在計算機內(nèi)存儲,數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)形式,是其在計算機內(nèi)的表示;此外討論一個數(shù)據(jù)結(jié)構(gòu)必須同時討論在該類數(shù)據(jù)上執(zhí)行的運算才有意義。在許多類型的程序的設(shè)計中,數(shù)據(jù)結(jié)構(gòu)的選擇是一個基本的設(shè)計考慮因素。許多大型

10、系統(tǒng)的構(gòu)造經(jīng)驗表明,系統(tǒng)實現(xiàn)的困難程度和系統(tǒng)構(gòu)造的質(zhì)量都嚴重的依賴于是否選擇了最優(yōu)的數(shù)據(jù)結(jié)構(gòu)。許多時候,確定了數(shù)據(jù)結(jié)構(gòu)后,算法就容易得到了。有些時候事情也會反過來,我們根據(jù)特定算法來選擇數(shù)據(jù)結(jié)構(gòu)與之適應(yīng)。不論哪種情況,選擇合適的數(shù)據(jù)結(jié)構(gòu)都是非常重要的。排序算法是數(shù)據(jù)結(jié)構(gòu)學科經(jīng)典的內(nèi)容,其中內(nèi)部排序現(xiàn)有的算法有很多種,其中包含冒泡排序,直接插入排序,簡單選擇排序,希爾排序,快速排序,堆排序等,各有其特點。對排序算法比較的分析可以遵循若干種

11、不同的準則,通常以排序過程所需要的算法步數(shù)作為度量,有時也以排序過程中所作的鍵比較次數(shù)作為度量。特別是當作一次鍵比較需要較長時間,例如,當鍵是較長的字符串時,常以鍵比較次數(shù)作為排序算法計算時間復(fù)雜性的度量。當排序時需要移動記錄,且記錄都很大時,還</p><p>  關(guān)鍵詞: 數(shù)據(jù)結(jié)構(gòu),算法比較,比較次數(shù),時間復(fù)雜度</p><p>  1《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計的目的、意義和任務(wù)</

12、p><p>  1.1《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計的目的和意義</p><p>  1.1.1 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計的目的</p><p>  數(shù)據(jù)結(jié)構(gòu)與算法課程主要是研究非數(shù)值計算的程序設(shè)計問題中所出現(xiàn)的計算機操作對象以及它們之間的關(guān)系和操作的學科。數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學、計算機軟件和計算機硬件之間的一門計算機專業(yè)的核心課程,它是計算機程序設(shè)計、數(shù)據(jù)庫、操作系統(tǒng)、編譯原理及人工智

13、能等的重要基礎(chǔ),廣泛的應(yīng)用于信息學、系統(tǒng)工程等各種領(lǐng)域。學習數(shù)據(jù)結(jié)構(gòu)與算法是為了將實際問題中涉及的對象在計算機中表示出來并對它們進行處理。通過課程設(shè)計可以提高學生的思維能力,促進學生的綜合應(yīng)用能力和專業(yè)素質(zhì)的提高。</p><p>  1)本演示程序?qū)σ韵?種常用的內(nèi)部排序算法進行實測比較:冒泡排序,插入排序,選擇排序,快速排序,希爾排序;</p><p>  2)演示程序以以用戶和計算機

14、的對話方式執(zhí)行,在計算機終端上顯示提示信息,對隨機數(shù)組進行排序,并輸出比較指標值;</p><p>  3)最后對結(jié)果作出簡單分析。</p><p>  1.1.2 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計的意義</p><p>  按要求輸入不同的操作。輸入后,根據(jù)不同的輸入進行不同的操作,最終達到對各算法進行比較的目的。通過此次課程設(shè)計主要達到以下目的了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計

15、方法,具備初步的獨立分析和設(shè)計能力;初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計、程序編碼、測試等基本方法和技能;提高綜合運用所學的理論知識和方法獨立分析和解決問題的能力;訓練用系統(tǒng)的觀點和軟件開發(fā)一般規(guī)范進行軟件開發(fā),培養(yǎng)軟件工作者所應(yīng)具備的科學的工作方法和作風。</p><p>  1.2 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計的主要任務(wù)</p><p> ?。?)、至少采用三種方法實現(xiàn)上述問題求解(提示,

16、可采用的方法有插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序)。并把排序后的結(jié)果保存在不同的文件中。</p><p> ?。?)、統(tǒng)計每一種排序方法的性能(以上機運行程序所花費的時間為準進行對比),找出其中兩種較快的方法。</p><p>  2 綜合排序的主要功能分析</p><p>  2.1 數(shù)據(jù)對象分析</p><p&

17、gt;  (1)排序方式:冒泡排序,希爾排序,快速排序,插入排序,選擇排序</p><p> ?。?)顯示后的數(shù)據(jù)以及時間效率</p><p><b>  2.2 功能分析</b></p><p>  分析設(shè)計課題的要求,采用順序存儲結(jié)構(gòu),編程實現(xiàn)功能如下:</p><p> ?。?)顯示隨機數(shù):調(diào)用random隨機函數(shù)

18、自動生成數(shù)據(jù),用數(shù)組保存生成的隨機數(shù)。</p><p> ?。?)當輸入的數(shù)的個數(shù)小于100時,在運行界面上顯示隨機生成的數(shù)組,否則將生成數(shù)據(jù)存入文件。</p><p> ?。?)采用冒泡排序、希爾排序、快速排序、插入排序和選擇排序5種排序方法來對隨機產(chǎn)生的數(shù)進行排序以及時間比較。</p><p> ?。?)運用結(jié)構(gòu)體數(shù)組存儲數(shù)據(jù),判斷各種排序的穩(wěn)定性。</p

19、><p> ?。?)顯示各排序算法排序后的數(shù)據(jù)、時間效率以及穩(wěn)定性。</p><p>  3 綜合排序的結(jié)構(gòu)、基本操作及算法設(shè)計</p><p>  3.1 綜合排序的結(jié)構(gòu)設(shè)計</p><p>  3.1.1綜合排序的邏輯結(jié)構(gòu)設(shè)計</p><p>  采用順序存儲結(jié)構(gòu):順序存儲結(jié)構(gòu)是存儲結(jié)構(gòu)類型中的一種,該結(jié)構(gòu)是把邏輯上相

20、鄰的節(jié)點存儲在物理位置上相鄰的存儲單元中,結(jié)點之間的邏輯關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)。由此得到的存儲結(jié)構(gòu)為順序存儲結(jié)構(gòu),通常順序存儲結(jié)構(gòu)是借助于計算機程序設(shè)計語言的數(shù)組來描述的。</p><p>  3.1.2 綜合排序的物理結(jié)構(gòu)設(shè)計</p><p>  struct Type{</p><p><b>  int num;</b></

21、p><p>  int index;</p><p><b>  };</b></p><p>  3.2綜合排序算法設(shè)計 </p><p>  3.2.1 冒泡排序算法的基本思想和算法描述 </p><p>  冒泡排序:如果有n個數(shù),則進行n-1趟比較。在第1趟比較中要進行n-1次兩兩

22、比較,在第j趟比較中進行n-j次兩兩比較。</p><p>  void maopao(Type a[])//冒泡排序</p><p><b>  {</b></p><p><b>  int i,j;</b></p><p>  Type temp;</p><p>  

23、int flag=1;</p><p>  for(i=1;flag&&i<NUM;i++)</p><p>  for(flag=0,j=0;j<NUM-i;j++)</p><p>  if(a[j].num>a[j+1].num)</p><p><b>  {</b></p

24、><p><b>  flag=1;</b></p><p>  temp=a[j];</p><p>  a[j]=a[j+1];</p><p>  a[j+1]=temp;</p><p><b>  }</b></p><p><b&

25、gt;  }</b></p><p>  3.2.2 希爾排序算法的基本思想和算法描述</p><p>  希爾排序:先將整個待排記錄序列分割成為若干子序列分別進行直接插入排序,待整個序列中的記錄“基本有序”時,再對全體記錄進行一次直接插入排序。</p><p>  void shell_sort(Type a[], int n)//希爾排序</

26、p><p><b>  {</b></p><p><b>  int gap;</b></p><p>  for(gap = 3; gap >0; gap--)//gap控制增量由3-1</p><p><b>  {</b></p><p> 

27、 for(int i=0; i<gap; i++)</p><p><b>  {</b></p><p>  for(int j = i+gap; j<n; j=j+gap)//子序列排序</p><p><b>  {</b></p><p>  if(a[j].num<a[j

28、-gap].num)</p><p><b>  {</b></p><p>  Type temp = a[j];</p><p>  int k = j-gap;</p><p>  while(k>=0&&a[k].num>temp.num)</p><p>&l

29、t;b>  {</b></p><p>  a[k+gap] = a[k];</p><p>  k = k-gap;</p><p><b>  }</b></p><p>  a[k+gap] = temp;</p><p><b>  }</b><

30、;/p><p><b>  }</b></p><p><b>  }</b></p><p><b>  }</b></p><p><b>  }</b></p><p>  3.2.3快速排序算法的基本思想和算法描述</p&

31、gt;<p>  快速排序:首先檢查數(shù)據(jù)列表中的數(shù)據(jù)數(shù),如果小于兩個,則直接退出程序。如果有超過兩個以上的數(shù)據(jù),就選擇一個分割點將數(shù)據(jù)分成兩個部分,小于分割點的數(shù)據(jù)放在一組,其余的放在另一組,然后分別對兩組數(shù)據(jù)排序。</p><p>  void qsort(Type a[],int low,int high)//快速排序</p><p><b>  {</

32、b></p><p>  int pivotloc;</p><p>  if(low<high)</p><p><b>  {</b></p><p>  pivotloc=partition(a,low,high);</p><p>  qsort(a,low,pivotloc-

33、1);//遞歸調(diào)用軸心前面元素</p><p>  qsort(a,pivotloc+1,high);//遞歸調(diào)用軸心后面</p><p><b>  }</b></p><p><b>  }</b></p><p>  3.2.4插入排序算法的基本思想和算法描述</p><

34、p>  插入排序:將一個記錄插入到已排好序的有序表中,從而得到一個新的、記錄數(shù)增1的有序表。</p><p>  void charu (Type a[])//插入排序</p><p><b>  {</b></p><p><b>  int i,j;</b></p><p>  Type

35、temp;</p><p>  for(i=1;i<NUM;i++)</p><p><b>  {</b></p><p>  temp=a[i];//設(shè)置監(jiān)視哨</p><p>  for(j=i;j>0&&a[j-1].num>temp.num;j--)//尋找位置插入</p

36、><p>  a[j]=a[j-1];//交換</p><p>  a[j]=temp;</p><p><b>  }</b></p><p><b>  }</b></p><p>  3.2.5選擇排序算法的基本思想和算法描述</p><p>  選

37、擇排序:通過n-1次關(guān)鍵字間的比較,從n-i+1個記錄中選出關(guān)鍵字最小的記錄,并和第i個記錄交換。</p><p>  void xz(Type a[])//選擇排序</p><p><b>  {</b></p><p>  int i,j,k;</p><p>  for(i=0;i<NUM-1;i++)<

38、;/p><p><b>  {</b></p><p><b>  k=i;</b></p><p>  for(j=i+1;j<NUM;j++)//尋找最小的記錄序號</p><p>  if(a[j].num <a[k].num )</p><p><b&g

39、t;  k=j;//記錄</b></p><p><b>  if(k!=i)</b></p><p><b>  {</b></p><p>  Type temp;</p><p>  temp=a[k];</p><p>  a[k]=a[i];</p

40、><p>  a[i]=temp;</p><p><b>  }//交換</b></p><p><b>  }</b></p><p><b>  }</b></p><p>  4 綜合排序的代碼設(shè)計及編程實現(xiàn)</p><p>

41、<b>  程序結(jié)構(gòu)設(shè)計</b></p><p>  采用順序存儲結(jié)構(gòu),如圖:</p><p>  4.1.1流程圖及詳細算法</p><p>  函數(shù)的調(diào)用關(guān)系圖反映了演示程序的層次結(jié)構(gòu):</p><p>  圖4.1 .1 程序流程圖</p><p>  4.1.2流程圖模塊說明</p&

42、gt;<p>  1)Main為主函數(shù)模塊</p><p>  2)maopao,charu,xz,qsort,shell-sort分別對應(yīng)冒泡排序,插入排序,選擇排序,快速排序,希爾排序的各函數(shù)模塊</p><p>  3)在初始化數(shù)據(jù)之后,選擇對應(yīng)的排序模塊進行排序,并對排序做出比較</p><p><b>  4.2代碼設(shè)計</b

43、></p><p><b>  4.2.1函數(shù)聲明</b></p><p>  #include <iostream> </p><p>  #include <fstream></p><p>  #include <ctime> //時間函數(shù)頭文件</p>

44、<p>  #include <cstdlib>//隨機函數(shù)頭文件</p><p>  #include <iomanip>//格式頭文件</p><p>  using namespace std;</p><p><b>  int NUM;</b></p><p>  st

45、ruct Type</p><p><b>  {</b></p><p><b>  int num;</b></p><p>  int index;</p><p><b>  };</b></p><p>  4.2.2源程序代碼</p&g

46、t;<p>  #include <iostream> </p><p>  #include <fstream></p><p>  #include <ctime> //時間函數(shù)頭文件</p><p>  #include <cstdlib>//隨機函數(shù)頭文件</p><p

47、>  #include <iomanip>//格式頭文件</p><p>  using namespace std;</p><p><b>  int NUM;</b></p><p>  struct Type</p><p><b>  {</b></p>

48、<p><b>  int num;</b></p><p>  int index;</p><p><b>  };</b></p><p>  void wending(Type a[])// 穩(wěn)定性判斷</p><p><b>  {</b></p&g

49、t;<p>  bool flag=false;</p><p>  for(int i=0;i<NUM-1;i++)</p><p><b>  {</b></p><p>  if(a[i].num==a[i+1].num &&a[i].index>a[i+1].index)</p>

50、<p><b>  {</b></p><p>  flag=true;</p><p><b>  break;</b></p><p><b>  }</b></p><p><b>  }</b></p><p>&

51、lt;b>  if(flag)</b></p><p>  cout<<endl<<"該算法不是穩(wěn)定的!"<<endl;</p><p><b>  else</b></p><p>  cout<<endl<<"該算法是穩(wěn)定的!&quo

52、t;<<endl;</p><p><b>  }</b></p><p>  void xz(Type a[])//選擇排序</p><p><b>  {</b></p><p>  int i,j,k;</p><p>  for(i=0;i<NUM-

53、1;i++)</p><p><b>  {</b></p><p><b>  k=i;</b></p><p>  for(j=i+1;j<NUM;j++)//尋找最小的記錄序號</p><p>  if(a[j].num <a[k].num )</p><p&g

54、t;<b>  k=j;//記錄</b></p><p><b>  if(k!=i)</b></p><p><b>  {</b></p><p>  Type temp;</p><p>  temp=a[k];</p><p>  a[k]=a[

55、i];</p><p>  a[i]=temp;</p><p><b>  }//交換</b></p><p><b>  }</b></p><p><b>  }</b></p><p>  void charu (Type a[])//插入排序&

56、lt;/p><p><b>  {</b></p><p><b>  int i,j;</b></p><p>  Type temp;</p><p>  for(i=1;i<NUM;i++)</p><p><b>  {</b></p&g

57、t;<p>  temp=a[i];//設(shè)置監(jiān)視哨</p><p>  for(j=i;j>0&&a[j-1].num>temp.num;j--)//尋找位置插入</p><p>  a[j]=a[j-1];//交換</p><p>  a[j]=temp;</p><p><b>  }&

58、lt;/b></p><p><b>  }</b></p><p>  int partition(Type a[],int low,int high)//快排一趟</p><p><b>  {</b></p><p>  int pivotkey;</p><p>

59、;  Type temp;</p><p>  temp=a[low];//不使用a[0]空間存儲軸心元素便于其它排序操作</p><p>  pivotkey=a[low].num;</p><p>  while(low<high)</p><p><b>  {</b></p><p&

60、gt;  while(low<high&&a[high].num>=pivotkey)--high;</p><p>  a[low]=a[high];</p><p>  while(low<high&&a[low].num<=pivotkey)++low;</p><p>  a[high]=a[low];

61、</p><p><b>  }</b></p><p>  a[low]=temp;</p><p>  return low;</p><p><b>  }</b></p><p>  void qsort(Type a[],int low,int high)//快速排

62、序</p><p><b>  {</b></p><p>  int pivotloc;</p><p>  if(low<high)</p><p><b>  {</b></p><p>  pivotloc=partition(a,low,high);<

63、/p><p>  qsort(a,low,pivotloc-1);//遞歸調(diào)用軸心前面元素</p><p>  qsort(a,pivotloc+1,high);//遞歸調(diào)用軸心后面</p><p><b>  }</b></p><p><b>  }</b></p><p>

64、;  void shell_sort(Type a[], int n)//希爾排序</p><p><b>  {</b></p><p><b>  int gap;</b></p><p>  for(gap = 3; gap >0; gap--)//gap控制增量由3-1</p><p&

65、gt;<b>  {</b></p><p>  for(int i=0; i<gap; i++)</p><p><b>  {</b></p><p>  for(int j = i+gap; j<n; j=j+gap)//子序列排序</p><p><b>  {<

66、/b></p><p>  if(a[j].num<a[j-gap].num)</p><p><b>  {</b></p><p>  Type temp = a[j];</p><p>  int k = j-gap;</p><p>  while(k>=0&&a

67、mp;a[k].num>temp.num)</p><p><b>  {</b></p><p>  a[k+gap] = a[k];</p><p>  k = k-gap;</p><p><b>  }</b></p><p>  a[k+gap] = temp

68、;</p><p><b>  }</b></p><p><b>  }</b></p><p><b>  }</b></p><p><b>  }</b></p><p><b>  }</b><

69、/p><p>  void maopao(Type a[])//冒泡排序</p><p><b>  {</b></p><p><b>  int i,j;</b></p><p>  Type temp;</p><p>  int flag=1;</p>&l

70、t;p>  for(i=1;flag&&i<NUM;i++)</p><p>  for(flag=0,j=0;j<NUM-i;j++)</p><p>  if(a[j].num>a[j+1].num)</p><p><b>  {</b></p><p><b> 

71、 flag=1;</b></p><p>  temp=a[j];</p><p>  a[j]=a[j+1];</p><p>  a[j+1]=temp;</p><p><b>  }</b></p><p><b>  }</b></p>

72、;<p>  void suchu(Type a[],const char * filename)//輸出</p><p><b>  {</b></p><p>  if(NUM>100)//輸出到文件</p><p><b>  {</b></p><p>  ofstrea

73、m fout;</p><p>  int file_h_geshu=20;</p><p>  int file_i=0,file_j=0,file_cishu=1;</p><p>  fout.open(filename);</p><p>  fout<<setiosflags(ios::left);//格式</p&

74、gt;<p>  while(file_j!=NUM)</p><p><b>  {</b></p><p>  fout<<setiosflags(ios::left);</p><p>  fout<<"數(shù)字:";</p><p>  for(;fi

75、le_i<file_cishu*file_h_geshu&&file_i<NUM;file_i++)</p><p><b>  {</b></p><p>  fout<<setw(6)<<a[file_i].num;</p><p>  if((file_i+1)%file_h_geshu

76、==0)</p><p>  fout<<endl;</p><p><b>  }</b></p><p>  if(file_cishu*file_h_geshu>NUM)</p><p>  fout<<endl;</p><p>  fout<<&

77、quot;下標:";</p><p>  for(;file_j<file_cishu*file_h_geshu && file_j<NUM;file_j++)</p><p><b>  {</b></p><p>  fout<<setw(6)<<a[file_j].index;

78、</p><p>  if((file_j+1)%file_h_geshu==0)</p><p>  fout<<endl;</p><p><b>  }</b></p><p>  fout<<endl;</p><p>  file_cishu++;<

79、;/p><p><b>  }</b></p><p><b>  }</b></p><p>  else//輸出到顯示器</p><p><b>  {</b></p><p>  int i=0,j=0,cishu=1;</p><

80、;p>  const int xh_geshu=10;</p><p>  cout<<setiosflags(ios::left);</p><p>  while(j!=NUM)</p><p><b>  {</b></p><p>  if(NUM<=100)//當排序元素少于100時輸出

81、</p><p><b>  {</b></p><p>  cout<<"數(shù)字:";</p><p>  for(;i<cishu*xh_geshu &&i<NUM;i++)</p><p><b>  {</b></p>

82、<p>  cout<<setw(6)<<a[i].num;</p><p>  if((i+1)%xh_geshu==0)</p><p>  cout<<endl;</p><p><b>  }</b></p><p>  if(cishu*xh_geshu>NU

83、M)</p><p>  cout<<endl;</p><p>  cout<<"下標:";</p><p>  for(;j<cishu*xh_geshu &&j<NUM;j++)</p><p><b>  {</b></p>&

84、lt;p>  cout<<setw(6)<<a[j].index;</p><p>  if((j+1)%xh_geshu==0)</p><p>  cout<<endl;</p><p><b>  }</b></p><p>  cout<<endl;</

85、p><p><b>  }</b></p><p>  cishu++;</p><p><b>  }</b></p><p><b>  }</b></p><p><b>  }</b></p><p&g

86、t;  double random(double start, double end) </p><p><b>  { </b></p><p>  return start+(end-start)*rand()/(RAND_MAX+ 1.0);</p><p><b>  } </b></p><p

87、>  int main() </p><p><b>  { </b></p><p>  srand(unsigned(time(0))); </p><p>  int i;//i為下標</p><p>  cout<<"請輸入初始元素個數(shù):";</p&

88、gt;<p><b>  cin>>NUM;</b></p><p>  cout<<"當輸入元素個數(shù)大于100時將元素保存在文件中"<<endl<<endl;</p><p>  Type *num=new Type[NUM];</p><p>  Type *

89、temp=new Type[NUM];</p><p>  for(i = 0; i !=NUM; ++i) //產(chǎn)生數(shù)組</p><p><b>  {</b></p><p>  num[i].num=int(random(0,NUM));</p><p>  num[i].index=i;</p>

90、<p><b>  }</b></p><p>  suchu(num,"num.txt");//輸出源數(shù)據(jù)</p><p>  cout<<endl</p><p>  <<"∷∷∷∷∷∷∷∷∷"<<endl</p><p>  

91、<<"∷ 菜單 ∷"<<endl</p><p>  <<"∷ 1.冒泡排序 ∷"<<endl</p><p>  <<"∷ 2.希爾排序 ∷"<<endl</p><p>  <<&qu

92、ot;∷ 3.快速排序 ∷"<<endl</p><p>  <<"∷ 4.插入排序 ∷"<<endl</p><p>  <<"∷ 5.選擇排序 ∷"<<endl</p><p>  <<"∷ 6.退出

93、 ∷"<<endl</p><p>  <<"∷∷∷∷∷∷∷∷∷"<<endl;</p><p>  int select=0;</p><p>  clock_t start_time,end_time;</p><p>  while(select!=6)&

94、lt;/p><p><b>  {</b></p><p>  cin>>select;</p><p>  memcpy(temp,num,NUM*sizeof(Type));</p><p>  switch(select)</p><p><b>  {</b>

95、</p><p><b>  case 1:</b></p><p>  start_time=clock();</p><p>  maopao(temp);</p><p>  end_time=clock();</p><p>  suchu(temp,"maopao.txt&qu

96、ot;);</p><p>  cout<< "冒泡排序時間: "<<static_cast<double>(end_time-start_time)/CLOCKS_PER_SEC*1000<<"ms"<<endl;</p><p>  wending(temp);</p>&

97、lt;p><b>  break;</b></p><p><b>  case 2:</b></p><p>  start_time=clock();</p><p>  shell_sort(temp,NUM);</p><p>  end_time=clock();</p>

98、<p>  suchu(temp,"shell_sort.txt");</p><p>  cout<< "希爾排序時間: "<<static_cast<double>(end_time-start_time)/CLOCKS_PER_SEC*1000<<"ms"<<endl;<

99、;/p><p>  wending(temp);</p><p><b>  break;</b></p><p><b>  case 3:</b></p><p>  start_time=clock();</p><p>  qsort(temp,0,NUM-1);<

100、/p><p>  end_time=clock();</p><p>  suchu(temp,"Qsort.txt");</p><p>  cout<< "快速排序時間: "<<static_cast<double>(end_time-start_time)/CLOCKS_PER_SEC*1

101、000<<"ms"<<endl;</p><p>  wending(temp);</p><p><b>  break;</b></p><p><b>  case 4:</b></p><p>  start_time=clock();</p

102、><p>  charu(temp);</p><p>  end_time=clock();</p><p>  suchu(temp,"charu.txt");</p><p>  cout<< "插入排序時間: "<<static_cast<double>(end_

103、time-start_time)/CLOCKS_PER_SEC*1000<<"ms"<<endl;</p><p>  wending(temp);</p><p><b>  break;</b></p><p><b>  case 5:</b></p><

104、;p>  start_time=clock();</p><p><b>  xz(temp);</b></p><p>  end_time=clock();</p><p>  suchu(temp,"xz.txt");</p><p>  cout<< "選擇排序時間

105、: "<<static_cast<double>(end_time-start_time)/CLOCKS_PER_SEC*1000<<"ms"<<endl;</p><p>  wending(temp);</p><p><b>  break;</b></p><p&

106、gt;<b>  case 6:</b></p><p>  cout<<"退出!"<<endl;</p><p>  if(NUM>100)</p><p>  cout<<"請到當前文件目錄查看排序結(jié)果進而對穩(wěn)定性進行分析"<<endl;</

107、p><p><b>  break;</b></p><p><b>  default:</b></p><p>  cout<<"選擇錯誤!"<<endl</p><p>  <<"請從新選擇"<<endl;&l

108、t;/p><p><b>  break;</b></p><p><b>  }</b></p><p><b>  }</b></p><p><b>  return 0;</b></p><p><b>  }<

109、/b></p><p>  4.3系統(tǒng)運行及分析</p><p>  4.3.1系統(tǒng)運行結(jié)果</p><p>  1.進入程序后即顯示文本方式的用戶界面:</p><p>  圖4.1 進入程序后的界面</p><p>  2.開始運行時的用戶界面:</p><p>  1)輸入1回車,即

110、得冒泡排序的排序結(jié)果、時間及穩(wěn)定性。如圖4.2:</p><p>  圖4.2 輸入1后的運行結(jié)果</p><p>  2)輸入2回車,即得希爾排序的排序結(jié)果、時間及穩(wěn)定性,如圖4.3:</p><p>  圖4.3 輸入2后的運行結(jié)果</p><p>  3)輸入3回車,即得快速排序的排序結(jié)果、時間及穩(wěn)定性,如圖4.4:</p&g

111、t;<p>  圖4.4 輸入3后的運行結(jié)果</p><p>  4)輸入4回車,即得插入排序的排序結(jié)果、時間及穩(wěn)定性,如圖4.5:</p><p>  圖4.5 輸入4后的運行結(jié)果</p><p>  5)輸入5回車,即得選擇排序的排序結(jié)果、時間及穩(wěn)定性,如圖4.6:</p><p>  圖4.6 輸入5后的運行結(jié)果&l

112、t;/p><p>  6)輸入6回車,即退出該程序。</p><p>  圖4.7 輸入6后的運行結(jié)果</p><p>  4.3.2排序算法的分析</p><p>  分析實測得到的數(shù)值,5種排序算法(快速排序采用“比中法”)的特點小結(jié)如下:</p><p>  (1)若n較小(如n≤50),可采用直接插入或直接選擇排

113、序。</p><p>  當記錄規(guī)模較小時,直接插入排序較好;否則因為直接選擇移動的記錄數(shù)少于直接插人,應(yīng)選直接選擇排序為宜。</p><p>  (2)若文件初始狀態(tài)基本有序(指正序),則應(yīng)選用直接插人、冒泡或隨機的快速排序為宜;</p><p>  (3)若n較大,則應(yīng)采用時間復(fù)雜度為O(nlgn)的排序方法:快速排序、堆排序或歸并排序。</p>

114、<p><b>  5 結(jié)束語</b></p><p>  在一個學期后的基礎(chǔ)理論知識的學習后進入實踐的操作雖然仍就有些困難但也是另一種進步的好途徑。這次的課程設(shè)計主要是對基礎(chǔ)知識的靈活使用,這就讓我進一步提高了對數(shù)據(jù)結(jié)構(gòu)知識的鞏固。這次設(shè)計的完成,困難是少不了的,還有許多其他的難題讓我都曾不知所措,但通過努力最終解決它們讓我體會到成就感,更重要的是我的能力在無形中得到了提升和優(yōu)化

115、。這次課程設(shè)計的心得體會通過實習我的收獲如下1、鞏固和加深了對數(shù)據(jù)結(jié)構(gòu)的理解,提高綜合運用本課程所學知識的能力。2、培養(yǎng)了我選用參考書,查閱手冊及文獻資料的能力。培養(yǎng)獨立思考,深入研究,分析問題、解決問題的能力。3、通過實際編譯系統(tǒng)的分析設(shè)計、編程調(diào)試,掌握應(yīng)用軟件的分析方法和工程設(shè)計方法。4、通過課程設(shè)計,培養(yǎng)了我嚴肅認真的工作作風,逐步建立正確的生產(chǎn)觀念、經(jīng)濟觀念和全局觀念。根據(jù)我在實習中遇到得問題,我將在以后的學習過程中注意以下幾

116、點:1、認真上好專業(yè)實驗課,多在實踐中鍛煉自己。2、寫程序的過程中要考慮周到,嚴密。3、在做設(shè)計的時候要有信心,有耐心,切勿浮躁。4、認真的學習課本知識,掌握課本中的知識點,并在此基礎(chǔ)上學會靈活運用。5、在課余時間里多寫程序,熟練掌握在</p><p><b>  參考文獻</b></p><p>  [1] 寧正元,王秀麗.算法與數(shù)據(jù)的結(jié)構(gòu),2006:29~32&l

117、t;/p><p>  [2] 楊輝.楊輝的縱橫圖論,2003:12~14</p><p>  [3] 唐王希.太乙金鏡式經(jīng),2000:35~37</p><p>  [4] 王力柱。c/c++與數(shù)據(jù)結(jié)構(gòu)。2003(8):142~152</p><p>  [5] 徐孝凱,賀桂英。數(shù)據(jù)結(jié)構(gòu)。2004(10):76~92</p><

118、;p>  [6] 吳乃陵,李海文。c++程序設(shè)計。2003(8):80~87 ,263~270</p><p>  [7] 陳媛,何波,涂曉江,涂飛。算法與數(shù)據(jù)結(jié)構(gòu)。2005(4)</p><p>  [8] 張勇,劉君儀。數(shù)據(jù)結(jié)構(gòu)。2006(8):96~107</p><p>  [9] 王挺,周會平。c++程序設(shè)計。2005(1):30~38

溫馨提示

  • 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)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
  • 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論