課程設(shè)計報告----內(nèi)排序算法比較

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

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

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

文檔簡介

1、　　《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計報告　　程序清單：　提交日期： 8月20日成績：指導(dǎo)老師：　實驗題目：內(nèi)排序算法比較　問題解析（對問題的分析、理解和解題方法）：

2、偽隨機數(shù)的產(chǎn)生是由 time. h 頭文件,以rand(time(0))為隨機種子的函數(shù)rand()產(chǎn)生，可以保持?jǐn)?shù)據(jù)的無序性。生成三種文件，分別保存正序.逆序.和隨機產(chǎn)生的數(shù)據(jù)，并在程序執(zhí)行過程中可選擇用某一文件中的數(shù)據(jù)。用類涵蓋六種排序算法的內(nèi)部操作，并定義數(shù)組元素類。輸入以文件的方式來進(jìn)行，必須保證對六種排序算法的輸入數(shù)據(jù)是一樣且連續(xù)的。對于比較次數(shù)的統(tǒng)計加在比較判斷的前邊，在判斷失敗時也能統(tǒng)計到比較次數(shù)。對于存在遞歸的快速排序和

3、存在子函數(shù)的堆排序的比較次數(shù).移動次數(shù)統(tǒng)計采用以引用做函數(shù)參數(shù)。　數(shù)據(jù)結(jié)構(gòu)選擇：選用動態(tài)數(shù)組為內(nèi)部基本運算結(jié)構(gòu)，外部數(shù)據(jù)選用文件。算法設(shè)計：構(gòu)建動態(tài)數(shù)組元素類，六種排序操作.輸出操作為該類的函數(shù)，輸入操作包含在構(gòu)造函數(shù)中。需求分析：外部數(shù)據(jù)只可以手動輸入隨機數(shù)的個數(shù)。程序運行中可選擇采用多種文件用各種算法測試多次。程序主線：產(chǎn)生正序文件f1.txt，倒序文件f2.txt，并生成三個隨機文件f3.

4、txt f4.txt f5.txt。選擇將某一文件導(dǎo)入程序，進(jìn)行排序，并測試各種算法的移動和比較次數(shù)。最后對結(jié)果進(jìn)行分析。　任務(wù)分工、進(jìn)度計劃：周一：六種排序算法嵌入各主程序，并進(jìn)行初步測算。周二：主要解決程序文件輸入，輸出問題和各函數(shù)的接口問題。周三：對程序進(jìn)行調(diào)整，解決部分錯誤輸出。　用戶手冊：用戶需要選擇是否生成新的文件，還需要外部輸入待排序

5、數(shù)組元素個數(shù)即可，程序運行中用戶可選擇用某一文件進(jìn)行排序。　測試結(jié)果：請輸入排序元素個數(shù):10000請輸入讀入何種待排序文件:(0：正序 1：逆序 2：隨機文件1 3：隨機文件2 4：隨機文件3)0Bubble:比較次數(shù)=9999 移動次數(shù)：=0InsertSort:比較次數(shù)=9999 移動次數(shù)：=19998SSort:比較次數(shù)=49995000 移動次數(shù)：=29997QSort:比較次

6、數(shù)=19998 移動次數(shù)：=39996ShellSort:比較次數(shù)=120009 移動次數(shù)：=240018HeapSort:比較次數(shù)=264502 移動次數(shù)：=394251是否繼續(xù)測試:(按任意鍵繼續(xù)，按0退出:)1請輸入排序元素個數(shù):10000請輸入讀入何種待排序文件:(0：正序 1：逆序 2：隨機文件1 3：隨機文件2 4：隨機文件3)1Bubble:比較次數(shù)=49995000 移動次數(shù)：=149985000InsertSo

7、rt:比較次數(shù)=9999 移動次數(shù)：=19998SSort:比較次數(shù)=49995000 移動次數(shù)：=29997QSort:比較次數(shù)=19998 移動次數(shù)：=39996ShellSort:比較次數(shù)=120009 移動次數(shù)：=　總結(jié)（對所做程序進(jìn)行分析、評價運行結(jié)果、總結(jié)遇到的問題及解決辦法）：總結(jié)：能輸出各種算法對同一數(shù)組的比較.交換次數(shù)，能較直觀的比較各種算法在不同情況下的優(yōu)劣。遇到如下問題：問

8、題1：快速排序的遞歸中和堆排序的子函數(shù)中比較次數(shù)和移動次數(shù)無法同時返回解決辦法:引用比較次數(shù)compare和移動次數(shù)move作為函數(shù)的參數(shù)。問題2：在數(shù)組很大>10000，正序或逆序時，快速排序堆棧溢出解決辦法：在編譯器中修改了堆棧上限。　　#include<iostream>　　#include<ctime></p&

9、gt;　　#include<fstream>　　using namespace std;　　class lists{　　public:　　int n;</p

10、>　　void savefile();　　lists();　　int getlist(int n){return list[n];}　　void output();　　void Bubble();</

11、p>　　void InsertSort();　　void SSort();　　void QQSort(int m,int n,int &,int &);　　void QSort();　　void ShellSort();<

12、/p>　　void Restore(int *tree,const int root,const int n,int &,int &);　　void HeapSort();　　private:　　int *list;</p&g

13、t;　　};　　lists::lists(){　　int s0;　　savefile();　　cout<<"請輸入讀入何種待排序文件:(0：正序 1：

14、逆序 2：隨機文件1 3：隨機文件2 4：隨機文件3)"<<endl;　　cin>>s0;　　list=new int[n];　　switch(s0){　　case 0:{ifstream in

15、file("f1.txt",ios::in);　　for(int i=0;i<n;i++)infile>>list[i];　　infile.close();break;}　　case 1:{ifstream infile("f2.txt",ios::in)

16、;　　for(int i=0;i<n;i++)infile>>list[i];　　infile.close();break;}　　case 2:{ifstream infile("f3.txt",ios::in);　　for(int

17、i=0;i<n;i++)infile>>list[i];　　infile.close();break;}　　case 3:{ifstream infile("f4.txt",ios::in);　　for(int i=0;i<n;i++)infile>>lis

18、t[i];　　infile.close();break;}　　case 4:{ifstream infile("f5.txt",ios::in);　　for(int i=0;i<n;i++)infile>>list[i];　　infi

19、le.close();break;}　　}　　}　　void lists::output(){　　for(int i=0;i<n;i++)　　cou

20、t<<list[i]<<endl;　　}　　//冒泡排序　　void lists::Bubble(){　　int bound,j,t;<p&g

21、t;　　int e;　　int compare=0,move=0;　　bound=n-1;　　while(bound){　　t=0;　　for(j=0;j

22、<bound;j++){　　compare++;　　if(list[j]>list[j+1]){　　move+=3;　　e=list[j];　　list[j]=list[j+1];

23、　　list[j+1]=e;　　t=j;　　}　　}　　bound=t;<

24、;/p>　　}　　cout<<"Bubble:比較次數(shù)="<<compare<<" 移動次數(shù)：="<<move<<endl;　　}

25、　　//直接插入排序　　void lists::InsertSort(){　　int e,i;　　int compare=0,move=0;　　//list[-1]=0;&l

26、t;/p>　　for(int j=1;j<n;j++){　　e=list[j];　　move++;　　i=j-1;　　compare++;

27、　　while(e<list[i]){　　list[i+1]=list[i];　　move++;　　i--;　　}

28、　　list[i+1]=e;　　move++;　　}　　cout<<"InsertSort:比較次數(shù)="<<compare<<" 移動次數(shù)：=&quo

29、t;<<move<<endl;　　}　　//直接選擇排序　　void lists::SSort(){　　int t;

30、;　　int e;　　int compare=0,move=0;　　for(int j=n-1;j>=1;j--){　　t=0;　　for(int i=1;i<=

31、j;i++){　　compare++;　　if(list[t]<list[i])　　t=i;　　}　　e=list[t];&

32、lt;p>　　list[t]=list[j];　　list[j]=e;　　move+=3;　　}　　cout<<"SSort:比較次數(shù)="<<co

33、mpare<<" 移動次數(shù)：="<<move<<endl;　　}　　//快速排序　　void lists::QQSort(int m,int n,int &a,int &am

34、p;b){　　int i,j,k,temp;　　if(m<n){　　i=m;　　j=n+1;　　k=list[

35、m];　　b++;　　while(i<j){　　i++;　　a++;　　while(list[i]<k)

36、i++;　　j--;　　a++;　　while(list[j]>k)j--;　　if(i<j){　　te

37、mp=list[i];　　list[i]=list[j];　　list[j]=temp;　　b+=3;　　}　　}&

38、lt;/p>　　temp=list[m];　　list[m]=list[j];　　list[j]=temp;　　b+=3;　　QQSort(m,j-1,a,b);

39、　QQSort(j+1,n,a,b);　　}　　}　　//快速排序　　void lists::QSort(){　　i

40、nt compare=0,move=0;　　QQSort(0,n-1,compare,move);　　cout<<"QSort:比較次數(shù)="<<compare<<" 移動次數(shù)：="<<move<<endl;<

41、b>　　}　　//希爾排序　　void lists::ShellSort(){　　int gap=n-1;　　int i;　　i

42、nt compare=0,move=0;　　while(gap>=1){　　gap=gap/2;　　for(i=0;i<gap;i++){　　int e;　　in

43、t t;　　for(int j=i+gap;j<n;j=j+gap){　　e=list[j];　　t=j-gap;　　move++;<p&g

44、t;　　compare++;　　while(e<list[t]){　　list[t+gap]=list[t];　　t=t-gap;　　move++;

45、　　if(t<=i)break;　　}　　list[t+gap]=e;　　move++;　　}

46、;　　}　　}　　cout<<"ShellSort:比較次數(shù)="<<compare<<" 移動次數(shù)：="<<move<<endl;　　}&

47、lt;/b>　　//重建堆　　void lists::Restore(int *tree,const int root,const int n,int &a,int &b){　　int m,e;

48、　　int j=root;　　while(j<=n/2-1){　　a++;　　if((2*j<n-1)&&(tree[2*j]<tree[2*j+1]))m=2*j+1;　　els

49、e m=2*j;　　a++;　　if(tree[j]<tree[m]){　　b+=3;　　e=tree[j];　　tree[j]=tree[m];&

50、lt;/p>　　tree[m]=e;　　j=m;　　}　　else j=n-1;　　}&

51、lt;b>　　}　　void lists::HeapSort(){　　int i,e;　　int compare=0,move=0;　　for(i=(n-1)/2;i>=0;i--)

52、　　Restore(list,i,n,compare,move);　　for(i=n-1;i>0;i--){　　e=list[i];　　list[i]=list[0];　　list[0]=e;　　Res

53、tore(list,0,i,compare,move);　　}　　cout<<"HeapSort:比較次數(shù)="<<compare<<" 移動次數(shù)：="<<move<<endl;

54、　　}　　void lists::savefile(){　　int i;　　srand(time(0));　　cout<<"請輸入排序元素個數(shù):"<<e

55、ndl;　　cin>>n;　　list=new int[n];　　ofstream outfile1("f1.txt",ios::out);　　for(i=0;i<n;i++){

56、;　　list[i]=i+1;　　outfile1<<list[i]<<endl;　　}outfile1.close();　　ofstream outfile2("f2.txt",ios::out);　　f

57、or(i=0;i<n;i++){　　list[i]=n-i;　　outfile2<<list[i]<<endl;　　}outfile2.close();　　ofstream outfile3("f3.txt",ios::o

58、ut);　　for(i=0;i<n;i++){　　list[i]=rand()%10000+1;　　outfile3<<list[i]<<endl;　　}outfile3.close();　　ofst

59、ream outfile4("f4.txt",ios::out);　　for(i=0;i<n;i++){　　list[i]=rand()%10000+1;　　outfile4<<list[i]<<endl;　　}outfi

60、le4.close();　　ofstream outfile5("f5.txt",ios::out);　　for(i=0;i<n;i++){　　list[i]=rand()%10000+1;　　outfile5<<list[i]<

61、;<endl;　　}outfile5.close();　　}　　#include<iostream>　　#include"排序.h"　　using nam

62、espace std;　　int sort(){　　class lists a_list;　　//cout<<"排序前:"<<endl;　　//a_list.output();　　a

63、_list.Bubble();　　a_list.InsertSort();　　a_list.SSort();　　a_list.QSort();　　a_list.ShellSort();　　a_list.HeapSort();<

64、;/p>　　//cout<<"排序后:"<<endl;　　//a_list.output();　　return 0;　　}

65、;　　int main(){　　int flag;　　do{　　sort();　　cout<<"是否繼續(xù)測試:(按任意鍵繼續(xù)，按0退出:

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

溫馨提示

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)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

課程設(shè)計報告----內(nèi)排序算法比較

文檔簡介

溫馨提示

最新文檔

評論

課程設(shè)計報告----內(nèi)排序算法比較

文檔簡介

溫馨提示

最新文檔

評論

免費下載