數(shù)據(jù)結構課程設計---希爾排序，冒泡排序，快速排序

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數(shù)：18 大?。?31.50KB 人氣指數(shù)：12 舉報 版權申訴

已閱讀1頁，還剩17頁未讀，繼續(xù)免費閱讀

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

1、　　數(shù)據(jù)結構課程設計　　設計說明書　　希爾排序，冒泡排序，快速排序　　學生姓名：***** 　　學生學號：2009070142**

2、;　　指導教師：***** 　　所在班級：09級電信2班　　成績打分： 　　信息與工程學院　　2011年6月25日　　課程設計任務書<

3、/b>　　2010—2011學年第二學期　　專業(yè)：電子信息工程 　　學號： 　　姓名： 　　課程設計名稱：數(shù)據(jù)結構課程設計&

4、lt;/p>　　設計題目：簡單數(shù)據(jù)的排序 　　設計依據(jù)、要求及主要內容（可另加附頁）：　　要求：　　要有較好的界面，能夠進行三種算法的選擇。　　每一種算法要求有實現(xiàn)的過程，即能看到運行的步驟。<

5、/p>　　對于同一組數(shù)據(jù)進行三種算排序后，應給出相應的效率評估，確定最適合的算法。　　要求有良好的編程風格和注釋。　　指導教師（簽字）： 　　批準日期：年月日　　摘

6、要　　本設計采用VC作為開發(fā)工具，通過希爾排序、冒泡排序與快速排序方法來實現(xiàn)一系列數(shù)據(jù)結構的排序工作。三種方法思路不同，方法各異，體現(xiàn)了排序的多樣性。通過這次課程設計，使我們了解更多的排序知識，了解課設的有關程序過程，以掌握更多的排序方法。　　關鍵詞：C語言;排序　　目

7、錄　　1課題描述……………………………………………………………………………。。。1　　2 邏輯設計……………………………………………………………………………2　　3 詳細設計………………………………………………………………………………4　　4 程序代

8、碼……………………………………………………………………………6　　5程序調試與測試………………………………………………………………………12　　6總結……………………………………………………………………………………14　　參考文獻………………………………………………………………………………15

9、　　1 課題描述　　1.1 課題的現(xiàn)實意義　　現(xiàn)實學習生活中，常會遇到一些數(shù)目較大數(shù)據(jù)繁雜的數(shù)值進行排序，徒手進行排序很困難，這時候我們就希望有一個小軟件來幫忙，所以便著手開發(fā)了這個對數(shù)據(jù)進行有序排序的程序，以便用于自己的學習工作。這些大大方便了我們的生活給我們更多的選擇和實現(xiàn)方式。</p

10、>　　這個程序可以直接輸入多個數(shù)據(jù)，不需要任何轉換，就可以直接輸出這些數(shù)據(jù)排序后的結果并輸出移動的次數(shù)。并且從操作簡單、界面清晰、靈活、實用、方便等要求出發(fā)，它所能完成的主要計算功能有以下幾個方面：冒泡排序，快速排序，希爾排序。計算器的設計使我們所學到的c語言知識在現(xiàn)實中得到檢驗！　　信息時代是科技和經(jīng)濟發(fā)展的產(chǎn)物，軟件產(chǎn)業(yè)是信息時代的產(chǎn)物，它在我們的生活工作中發(fā)揮著

11、越來越大的作用，這個排序程序的設計對我們知識的掌握有很大的作用，更能方便他人，可行性很強！　　1.2 軟件環(huán)境　　開發(fā)環(huán)境: visual c++ 6.0+Windows XP 操作系統(tǒng)　　2邏輯設計<p&g

12、t;　　2.1總設計步驟　　總的設計過程不是很難，但是由于在編程過程中有的粗心大意，或是外部客觀條件，造成了調試很多次。但最終在老師的幫助下完成了設計。　　第一、在紙上列出提綱，把具體大概的設計思路用偽代碼寫出。　　第二、編寫代碼，把各個函數(shù)分別編寫出來，快速排序，冒泡排序，

13、希爾排序……。　　第三、程序上機運行，查找錯誤。　　第四、錯誤代碼的分析。查找原因。　　第五、調試。對于運行成功的代碼進行測試，看是否符合題目要求。使用多組數(shù)據(jù)進行測試。直至不存在著偶然性。　　第五、總結。過程當中有許多庫函數(shù)的調用，使用過程中讓我們對C語言函數(shù)的深刻了解

14、。　　第六、編寫報告書。編寫報告書的過程有些復雜，由于在實踐過程當中的每一步都要用再次的實現(xiàn)，并用書面報告提交。但是這個充分的是我們對這個編程的理解。　　2.2 三個主要函數(shù)的設計原理：　　（1）快速排序　　基本思路：通過一次分割，將無序序列分成兩部分，其中一部分的

15、元素值均不大于后一部分的元素值。然后用同樣的方法對每一部分進行分割，一直到每一個子序列的長度小于或等于1為止。　　具體過程：設序列P進行分割。首先，從第一個、中間一個、最后一個元素中選出中項，設為P[k]，并將P[k]賦給t，再將序列中的第一個元素移到P[k]的位置上。然后，再設兩個指針i、j分別指向起始和最后位置上：（1）將i逐漸增大，與此同時比較P[i]與t的大小，直到發(fā)現(xiàn)P[i]>t

16、，將P[i]移到P[j]的位置上；（2）將j逐漸減小，與此同時比較P[j]與t的大小，直到發(fā)現(xiàn)P[j]<t，將P[j]移到P[i]的位置上；直到i=j為止，這時將t移到P[i]的位置上。最后就得到了排序結果。　?。?）冒泡排序　　目的：按要求從大到小或從小到大排序。　　基本思路：對尚未排序的各元素從頭

17、到尾依次依次比較相鄰的兩個元素是否逆序（與欲排順序相反），若逆序就交換這兩元素，經(jīng)過第一輪比較排序后便可把最大（或最小）的元素排好，然后再用同樣的方法把剩下的元素逐個進行比較，就得到了你所要的順序?？梢钥闯鋈绻蠳個元素，那么一共要進行n-1輪比較，第I輪要進行j=n-i次比較。（如：有5個元素，則要進行5-1輪比較。第3輪則要進行5-3次比較）　　（3）希爾排序&

18、lt;p>　　基本思想：將整個無序序列分割成若干小的子序列分別進行插入排序。　　序列分割方法：將相隔某個增量h的元素構成一個子序列。在排序過程中，逐次減小這個增量，最后當h減到1時，進行一次插入排序，排序就完成。增量序列一般采用：ht=2t-1,1≤t≤[log2n]，其中n為待排序序列的長度。　　3詳細設計&

19、lt;/p>　　3.1希爾排序函數(shù)的設計　　int Shell(int num[],int n,int d)　　{　　int i,j,t,k=0;　　for(i=0;i<d;i++)

20、;　　{　　for(j=i;j<n;j+=d)　　{　　for(t=j+d;t<n;t+=n)　　{

21、　　if(num[j]>num[t])　　{　　num[t]=num[t]+num[j];　　num[j]=num[t]-num[j];　　num[t]=num[t]-num[j];&l

22、t;p>　　k=k+3;　　}　　}　　}　　}&l

23、t;p>　　return k;　　}　　int sort5(int num[],int n)　　{　　int i,j,k=0;&

24、lt;p>　　for(i=2;n/i;i++)　　{　　j=n/i;　　k+=Shell(num,n,j);　　}<p&g

25、t;　　return k;　　}}　　3.2快速排序函數(shù)的設計　　int Quick(int num[],int low,int high)　　{</p

26、>　　int low1=low,high1=high;　　int pivotkey=num[low];　　int k=0;　　while(low<high)　　{

27、　　while(low<high&&pivotkey<=num[high])high--;　　num[low]=num[high];k++;　　while(low<high&&pivotkey>=num[low])low++;<

28、p>　　num[high]=num[low];k++;　　}　　num[low]=pivotkey;k++;　　if(low-low1>1&&low<=high1)k+=Quick(num,low1,low-1);&l

29、t;p>　　if(high1-high>1&&high>=low1)k+=Quick(num,high+1,high1);　　return k;　　}　　int sort6(int num[],int n

30、)　　{　　int k,low=0,high=n-1;　　k=Quick(num,low,high);　　return k;　　}<

31、;/b>　　3.3冒泡排序函數(shù)的設計　　int sort15(int num[],int n)　　{　　int k=0,i=0,j;　　while(i<n-1)

32、　　{　　j=0;　　while(j<n-i-1)　　{　　if(num[j]>num[j+1])&

33、lt;p>　　{　　num[j]=num[j]+num[j+1];　　num[j+1]=num[j]-num[j+1];　　num[j]=num[j]-num[j+1];　　k+=3;<

34、;/p>　　}　　j++;　　}　　i++;　　}&l

35、t;/p>　　return k;　　4程序原代碼　　#include<iostream>　　#include<conio.h>　　#includ

36、e<stdlib.h>　　#include<cmath>　　#define max 20　　using namespace std;　　typedef struct　　{

37、;　　int num[max+1];　　int n;　　}str;　　typedef struct str12　　{

38、　　int num;　　struct str12 *next;　　}str12;　　//希爾排序　　int Shel

39、l(int num[],int n,int d)　　{　　int i,j,t,k=0;　　for(i=0;i<d;i++)　　{　　for(j=i;

40、j<n;j+=d)　　{　　for(t=j+d;t<n;t+=n)　　{　　if(num[j]>num[t])　　{&

41、lt;/b>　　num[t]=num[t]+num[j];　　num[j]=num[t]-num[j];　　num[t]=num[t]-num[j];　　k=k+3;

42、　}　　}　　}　　}　　return k;<b&g

43、t;　　}　　int sort5(int num[],int n)　　{　　int i,j,k=0;　　for(i=2;n/i;i++)　　{</b

44、>　　j=n/i;　　k+=Shell(num,n,j);　　}　　return k;　　}

45、　　//快速排序　　int Quick(int num[],int low,int high)　　{　　int low1=low,high1=high;

46、　　int pivotkey=num[low];　　int k=0;　　while(low<high)　　{　　while(low<high&&piv

47、otkey<=num[high])high--;　　num[low]=num[high];k++;　　while(low<high&&pivotkey>=num[low])low++;　　num[high]=num[low];k++;&l

48、t;b>　　}　　num[low]=pivotkey;k++;　　if(low-low1>1&&low<=high1)k+=Quick(num,low1,low-1);　　if(high1-high>1&&high>=low1)k+

49、=Quick(num,high+1,high1);　　return k;　　}　　int sort6(int num[],int n)　　{

50、;　　int k,low=0,high=n-1;　　k=Quick(num,low,high);　　return k;　　}　　//冒泡排序</b&g

51、t;　　int sort15(int num[],int n)　　{　　int k=0,i=0,j;　　while(i<n-1)　　{</p&

52、gt;　　j=0;　　while(j<n-i-1)　　{　　if(num[j]>num[j+1])　　{

53、　　num[j]=num[j]+num[j+1];　　num[j+1]=num[j]-num[j+1];　　num[j]=num[j]-num[j+1];　　k+=3;　　}

54、　　j++;　　}　　i++;　　}　　return k;&

55、lt;/b>　　}　　int Begin()　　{　　cout<<"\t\t#============================================#

56、"<<endl;　　cout<<"\t\t| 本軟件使用說明 |"<<endl;　　cout<<"\t\t#============================================#"&

57、lt;<endl;　　cout<<"\t\t| 為了方便測試，本軟件自帶了三組數(shù)據(jù)，按 |"<<endl;　　cout<<"\t\t| 'o'或'O'以外的任意鍵即自行調用默認的測試數(shù) |"<<endl;

58、;　　cout<<"\t\t| 據(jù)，而不需要用戶輸入數(shù)據(jù)。如果對默認的數(shù)據(jù) |"<<endl;　　cout<<"\t\t| 持有質疑，你可以按'O'或'o'鍵，然后輸入你的 |"<<endl;　　cout<&

60、ot;<<endl;　　cout<<"\t\t| 過多的輸入就會被打斷，或者整數(shù)位數(shù)超過八位 |"<<endl;　　cout<<"\t\t| 本軟件就會認為此數(shù)輸入結束，并輸出空格，并 |"<<endl;　　cou

61、t<<"\t\t| 將接下來的輸入計為下一個數(shù)。請按任意鍵… |"<<endl;　　cout<<"\t\t| 2009年 |"<<endl;　　cout<<"\t\t#=

62、===========================================#"<<endl;　　cout<<"\t\t#============================================#"<<endl;　　int choice=getch();syste

63、m("cls");　　if(79==choice||111==choice)return 1;　　else return 0;　　}　　void main()<b&g

64、t;　　{　　int i,j=0,k;　　str d[3];　　char data[10];　　int read=1;　　for(i=0;i<15;i+=2)d[0]

65、.num[j++]=15-i;　　for(i=1;i<15;i+=2)d[0].num[j++]=15-i;　　d[0].n=15;　　for(i=0;i<15;i++)d[1].num[i]=15-i;　　d[1].n=15;<

66、p>　　for(i=0;i<15;i++)d[2].num[i]=i+1;　　d[2].n=15;　　str num;　　int t=Begin();　　if(0==t)</p&

67、gt;　　{　　for(j=0;j<3;j++)　　{　　num=d[j];cout<<"\t原始數(shù)據(jù)為：";　　for(i=0;i&l

68、t;num.n;i++)cout<<num.num[i]<<" ";　　cout<<"1、希爾排序：";　　k=sort5(num.num,num.n); 　　for(i=0;i<num.n;i++)cout&

69、lt;<num.num[i]<<" ";　　cout<<"\t數(shù)據(jù)移動次數(shù)為："<<k<<endl;　　num=d[j];　　cout<<"2、快速排序

70、：";　　k=sort6(num.num,num.n); 　　for(i=0;i<num.n;i++)cout<<num.num[i]<<" ";　　cout<<"\t數(shù)據(jù)移動次數(shù)為："<<k&l

71、t;<endl;　　num=d[j];　　cout<<"3、冒泡排序：";　　k=sort15(num.num,num.n); 　　for(i=0;i<num.n;i++

72、)cout<<num.num[i]<<" ";　　cout<<"\t數(shù)據(jù)移動次數(shù)為："<<k<<endl;　　}　　}

73、　　else　　{　　cout<<"請輸入測試數(shù)據(jù)："<<endl;　　for(i=0;i<20&&read;i++)<

74、p>　　{　　for(j=0;data[j]=getch();j++)　　{　　if(data[j]==13)　　{<p&

75、gt;　　if(j&&data[j-1]!=43&&data[j-1]!=45)d[0].num[i]=atoi(data);　　else i--;　　cout<<endl<<endl;　　break;

76、　　}　　else if(data[j]>57||(data[j]<48&&data[j]!=32&&data[j]!=43&&data[j]!=45))　　{

77、;　　read=0;　　break;　　}　　else if(j&&(data[j]==43||data[j]==45))

78、　　{　　read=0;　　break;　　}　　else if(j&&j<

79、8&&data[j]==32)　　{　　d[0].num[i]=atoi(data);　　cout<<" ";　　break;

80、　　}　　else if(j==8)　　{　　d[0].num[i]=atoi(data);　　cout<<data[j]<<" &quo

81、t;;　　break;　　}　　else cout<<data[j];　　}　　if(i==14||da

82、ta[j]==13)break;　　}　　if(read)　　{　　d[0].n=i+1;j=0;system("cls");</p

83、>　　num=d[j];cout<<"\t原始數(shù)據(jù)為：";　　for(i=0;i<num.n;i++)cout<<num.num[i]<<" ";cout<<'\n';　　cout<<"1、希

84、爾排序：";　　k=sort5(num.num,num.n); 　　for(i=0;i<num.n;i++)cout<<num.num[i]<<" ";　　cout<<"\t數(shù)據(jù)移動次數(shù)為："<&l

85、t;k<<endl;　　num=d[j];　　cout<<"2、快速排序：";　　k=sort6(num.num,num.n); 　　for(i=0;i<num.

86、n;i++)cout<<num.num[i]<<" ";　　cout<<"\t數(shù)據(jù)移動次數(shù)為："<<k<<endl;　　num=d[j];　　cout<<"

87、;3、冒泡排序：";　　k=sort15(num.num,num.n); 　　for(i=0;i<num.n;i++)cout<<num.num[i]<<" ";　　cout<<"\t數(shù)據(jù)移動次數(shù)為："

88、<<k<<endl;　　}　　}　　if(read)　　{<p&g

89、t;　　getch();system("cls");　　cout<<endl<<"\t是否繼續(xù)?(y/n)";　　while(read)　　{　　t=getch();&l

90、t;/p>　　if(t==13||t==78||t==89||t==110||t==121)read=0;　　else cout<<endl<<"請輸入回車或 n(N) 或 y(Y) 作選擇… "<<endl;　　}</p&g

91、t;　　if(t==13||t==89||t==121)　　{　　system("cls");　　main();　　}

92、;　　}　　else　　{　　system("cls");　　main();&

93、lt;/b>　　}　　}　　5程序調試與測試　　程序調試是指對程序的查錯和排錯。為了便于查錯、閱讀，在設計該程序的過程中我們采用了結構化程序方法編輯，添

94、加了盡可能多的注釋，這就為接下來的調試過程帶來了很多方便。　　經(jīng)過仔細檢查之后進行上機調試。進行編譯，如果在編譯和連接過程中發(fā)現(xiàn)錯誤，屏幕上顯示了出錯信息，根據(jù)提示找到出錯的位置，加以改正，再進行編譯……如此反復，直到順利通過編譯和連接為止。在本次實習過程中碰到的編譯、連接的錯誤主要有：缺少變量定義，定義位置不正確、語法錯誤、轉義字符漏用、邏輯錯誤等。&

95、lt;b>　　5.1錯誤原因分析　　出現(xiàn)以下提示：　　圖1　　根據(jù)電腦所給的提示出現(xiàn)語法錯誤，缺少變量的定義大多的語法錯誤在通過書本參考下能夠修改。主要是平時看書不仔細、不太注意而產(chǎn)生的。如沒有注意具體數(shù)據(jù)使用是

96、有一定的范圍限定；過分重視分號的重要性而在for、if、while語句中畫蛇添足加分號。由于此程序需要的結果很多，所以得一一例舉面：　　5.2進入程序主界面如下：　　圖2　　5.3要求輸入數(shù)據(jù)界面如下：　　圖3<

97、;/b>　　5.4輸入數(shù)據(jù)界面如下：　　圖4　　5.5運行結果界面如下：　　圖5　　6 總結

98、;　　這次課程設計使我收獲很大，對我以前學習的知識進行了綜合性的考察，這次課程設計我主要是應用以前學習的C語言、數(shù)據(jù)結構的一些知識才完成了這個數(shù)據(jù)排序的課程設計。　　首先，綜合課程設計讓我把以前學習到的知識得到鞏固和進一步的提高認識，對已有知識有了更進一步的理解和認識，再次，我在課程設計中碰到了很多的問題，我通過查閱相關書籍，資料，通過自己鉆研，特別是得到了高虎老師的諄諄教

99、導，高老師給予了我很大的幫助，不僅給了我思路上的開闊，還讓我認識到了自己對以前所學知識的不足方面。　　隨著社會發(fā)展，以及軟件事業(yè)飛速發(fā)展，人們對各類軟件的要求越來越迫切，這次的課程設計我主要應用所學，通過在visual c++編程環(huán)境下，運用函數(shù)定義與調用的知識，進行基于各種排序函數(shù)的設計，它易于實現(xiàn)對數(shù)據(jù)的排序并且能夠比較出哪種排序的優(yōu)越性，這是它的一大優(yōu)勢。<p

100、>　　當然，通過這次課程設計，我也發(fā)現(xiàn)了自身的很多不足之處，在以后的學習中，我會不斷的完善自我，不斷進取，能使自己在C語言編程這方面有一個大的發(fā)展。　　參考文獻　　[1] 蕭秋水，文娟.網(wǎng)絡編程之vb篇[M].北京.清華出版社。　　[2] 方敏，張彤.網(wǎng)絡應用程序設計[

眾賞文庫> 全部分類> 畢業(yè)設計

溫馨提示

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

數(shù)據(jù)結構課程設計---希爾排序，冒泡排序，快速排序

文檔簡介

溫馨提示

最新文檔

評論

數(shù)據(jù)結構課程設計---希爾排序，冒泡排序，快速排序

文檔簡介

溫馨提示

最新文檔

評論

免費下載

數(shù)據(jù)結構課程設計---希爾排序，冒泡排序，快速排序