數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---排序綜合

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

2023年全國(guó)碩士研究生考試考研英語(yǔ)一試題真題（含答案詳解+作文范文）_第1頁(yè)

已閱讀1頁(yè)，還剩26頁(yè)未讀，繼續(xù)免費(fèi)閱讀

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

文檔簡(jiǎn)介

1、　　信息科學(xué)與技術(shù)學(xué)院　　《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)報(bào)告　　完成日期：1111　　目錄　　1 課程設(shè)計(jì)的目的4　　1.1

2、課程設(shè)計(jì)的目的4　　1.2 課程設(shè)計(jì)的題目4　　1.3 題目要求4　　2 概要設(shè)計(jì)5　　2.1 存儲(chǔ)結(jié)構(gòu)5　　2.2 基本操作5

3、;　　3 詳細(xì)設(shè)計(jì)6　　3.1 流程圖6　　3.2 源程序12　　4 測(cè)試22　　4. 1 主菜單22　　4. 2 插入排序功能22&

4、lt;/p>　　4.3 選擇排序功能23　　4.4 冒泡排序功能23　　4.5 快速排序功能24　　4.6 合并排序功能24　　4.7 5種排序方法比較25　　5 課程設(shè)計(jì)總結(jié)26<

5、;/p>　　6參考書目：26　　1 課程設(shè)計(jì)的目的　　1.1 課程設(shè)計(jì)的目的　　數(shù)據(jù)結(jié)構(gòu)課程主要是研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中所出現(xiàn)的計(jì)算機(jī)操作對(duì)象以及它們之間的關(guān)系和操作的學(xué)科。數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學(xué)、計(jì)算機(jī)軟件和計(jì)算機(jī)硬件之間的一門計(jì)算機(jī)專

6、業(yè)的核心課程，它是計(jì)算機(jī)程序設(shè)計(jì)、數(shù)據(jù)庫(kù)、操作系統(tǒng)、編譯原理及人工智能等的重要基礎(chǔ)，廣泛的應(yīng)用于信息學(xué)、系統(tǒng)工程等各種領(lǐng)域。　　學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)是為了將實(shí)際問題中所涉及的對(duì)象在計(jì)算機(jī)中表示出來(lái)并對(duì)它們進(jìn)行處理。通過課程設(shè)計(jì)可以提高學(xué)生的思維能力，促進(jìn)學(xué)生的綜合應(yīng)用能力和專業(yè)素質(zhì)的提高。通過此次課程設(shè)計(jì)主要達(dá)到以下目的：　　了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)方法，

7、掌握數(shù)組、鏈表、隊(duì)列、堆棧、樹等基本數(shù)據(jù)結(jié)構(gòu)，具備初步的獨(dú)立分析和設(shè)計(jì)能力；　　初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計(jì)、程序編碼、測(cè)試等基本方法和技能；　　提高綜合運(yùn)用所學(xué)的理論知識(shí)和方法獨(dú)立分析和解決問題的能力；　　訓(xùn)練用系統(tǒng)的觀點(diǎn)和軟件開發(fā)一般規(guī)范進(jìn)行軟件開發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng)。

8、　　1.2 課程設(shè)計(jì)的題目　　排序綜合，利用隨機(jī)函數(shù)產(chǎn)生N個(gè)隨機(jī)整數(shù)（20000以上），對(duì)這些數(shù)進(jìn)行多種方法進(jìn)行排序。 　　1.3 題目要求　　要求：

9、　　至少采用三種方法實(shí)現(xiàn)上述問題求解（提示，可采用的方法有插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序）。并把排序后的結(jié)果保存在不同的文件中。　　統(tǒng)計(jì)每一種排序方法的性能（以上機(jī)運(yùn)行程序所花費(fèi)的時(shí)間為準(zhǔn)進(jìn)行對(duì)比），找出其中兩種較快的方法。　　如果采用4種或4種以上的方法者，可適當(dāng)加分。<

10、;b>　　2 概要設(shè)計(jì)　　2.1 存儲(chǔ)結(jié)構(gòu)　　定義的主要的數(shù)據(jù)：　　(1):class SortableSList　　{<

11、/p>　　public:　　SortableSList();　　void InsertSort();　　void SelectSort();　　void BubbleSort();&

12、lt;p>　　void QuickSort();　　void MergeSort();　　void QuickSort(int left,int right);　　int QSort(int left,int right);　　void Merge(int lef

13、t,int right1,int right2);　　int *I,*S,*Q,*B,*M;　　int n;　　};聲明的類對(duì)象d;　　:int a[5],b[5],c[5], 分別記錄比較次數(shù)，交換次數(shù)，移動(dòng)次數(shù);</p&g

14、t;　　:long int a1[5]; //記錄排序所用的時(shí)間　　int a2[5]; //記錄排名　　2.2 基本操作　　(1):void SortableSList::BubbleSort(); 冒泡排序:<

15、;p>　　(2):void SortableSList::InsertSort(); 直接插入排序　　(3):void SortableSList::MergeSort(); 合并排序 　　(4):void SortableSList::QuickSort(); 快速排序　　(5):void S

16、ortableSList::SelectSort(); 簡(jiǎn)單選擇排序　　3 詳細(xì)設(shè)計(jì)　　3.1 流程圖　　主流程圖：　　P= =0&

17、lt;/b>　　P==1 p==2 p==3 p==4 p==5 P==6 　　流程圖-1　　子流程圖：<

18、b>　　（1）：插入排序：　　否　　是　　是否　　流程圖-2

19、　（2）：選擇排序： 　　是　　否　　是

20、否　　流程圖-3　　（3）：冒泡排序：　　是　　是

21、否　　否　　是　　流程圖-4　　：快速排序：　　是&l

22、t;/b>　　否　　流程圖-5　　:合并排序: 　　是　　否

23、否　　是 　　否 　　是否　　流程圖-6<p&

24、gt;　　3.2 源程序　　#include<iostream>　　#include <stdio.h>　　#include<fstream>　　#include<stdlib.h>&

25、lt;/p>　　#include<windows.h>　　#include<iomanip>//包含列表的函數(shù)　　using namespace std;　　int a[5],b[5],c[5];//a[],b[],c[]分別記錄比較次數(shù)，交換次數(shù)，移動(dòng)次數(shù)&l

26、t;/p>　　ifstream outfile;　　class SortableSList　　{　　public:　　SortableSList();

27、;　　void InsertSort();　　void SelectSort();　　void BubbleSort();　　void QuickSort();　　void MergeSort();　　voi

28、d QuickSort(int left,int right);　　int QSort(int left,int right);　　void Merge(int left,int right1,int right2);　　int *I,*S,*Q,*B,*M;<

29、b>　　int n;　　};　　SortableSList::SortableSList()　　{　　printf( " 輸入排序數(shù)字的個(gè)數(shù):\n")

30、;　　scanf("%d",&n);　　I=new int[n]; //創(chuàng)建一個(gè)指向整型數(shù)據(jù)的數(shù)組,并將地址賦給指向整型數(shù)據(jù)的指針　　S=new int[n];　　Q=new int[n];　　B=

31、new int[n];　　M=new int[n];　　for(int i=0;i<n;i++)　　I[i]=S[i]=Q[i]=B[i]=M[i]=rand();　　//將隨機(jī)生成的資料寫入文件　　ofstream inf

32、ile;　　infile.open("data.txt");//將對(duì)象與文件關(guān)聯(lián)　　for(i=0;i<n;i++)　　{　　double w=I[i];　　infi

33、le<<w<<" "; }　　infile.close();　　}　　void Swap(int&a,int&b)//交換函數(shù)　　{&

34、lt;/p>　　int T=a;a=b;b=T;　　}　　void SortableSList::InsertSort()//直接插入排序　　{ 　　for(int i

35、=1;i<n;i++)　　{　　int j=i;　　int temp=I[i];//將待插入元素存入temp　　c[0]++;&

36、lt;p>　　while(j>0&&temp<I[j-1]){//從后往前查找插入位置　　a[0]++;　　I[j]=I[j-1];j--;　　c[0]++;&l

37、t;b>　　}　　a[0]++;　　I[j]=temp;//將待插入的元素存入找到的插入位置　　}　　}&l

38、t;p>　　void SortableSList::SelectSort()//簡(jiǎn)單選擇排序　　{　　int s;　　for(int i=0;i<n-1;i++){　　s=i;

39、 //假定待排序序列中的第一個(gè)元素最小　　for(int j=i+1;j<n;j++)//每趟掃描n-i-1次　　a[1]++;　　if(S[j]<S[s]) s=j;//記下每次比較的較小元素的下標(biāo)

40、;　　Swap(S[i],S[s]);//最小元素與待排序序列的第一個(gè)交換　　c[1]=c[1]+3,b[1]++;　　}　　}　　void SortableSList::QuickSort()/

41、/快速排序　　{ 　　QuickSort(0,n-1); //以初始序列為待排序序列開始快速排序　　}　　int SortableSList::QSort(int left,

42、int right)　　{　　int i=left,j=right+1;　　do{ //開始一趟快速排序，Q[left]作為分割元素　　do

43、　　{　　i++;　　a[3]++;　　}while(Q[i]<Q[left]);　　do&

44、lt;/b>　　{　　j--;　　a[3]++;　　}while(Q[j]>Q[left]);<b

45、>　　if(i<j)　　Swap(Q[i],Q[j]),b[3]++;　　}while(i<j);　　Swap(Q[left],Q[j]); //交換分割元素Q[left]和Q[j]的位置　　c[3]=c[3]+3,b[

46、3]++;　　return j;　　}　　void SortableSList::QuickSort(int left,int right)　　{</p

47、>　　if(left<right){　　int j=QSort(left,right);　　QuickSort(left,j-1); //對(duì)低端序列快速排序　　QuickSort(j+1,right); //對(duì)高端序列快速排序

48、　　}　　}　　void SortableSList::BubbleSort()//冒泡排序　　{　　int i,j,last;<

49、;p>　　i=n-1;　　while(i>0)　　{ //最多進(jìn)行n-1趟　　last=0; //進(jìn)入循環(huán)就將last置為0 　　for(j=0;j<i;j++)//從上往下進(jìn)行比較</p&g

50、t;　　{　　if(B[j+1]<B[j])　　{　　Swap(B[j],B[j+1]);　　c[2]=c[2]+3;<

51、b>　　b[2]++;　　last=j;　　}　　a[2]++;　　}

52、　　i=last; //如果沒有交換元素，則last=0,退出循環(huán)　　}　　}　　//兩路合并排序　　void Sortable

53、SList::Merge(int left,int right1,int right2)//兩路合并　　{　　//right1,right2分別為兩個(gè)子序列的上界　　int*temp=new int[right2-left+1]; //創(chuàng)建存放兩個(gè)子序列的臨時(shí)數(shù)組</p

54、>　　int i=left,j=right1+1,k=0; //i,j是兩個(gè)子序列的游動(dòng)指針，k是temp的游動(dòng)指針　　while((i<=right1)&&(j<=right2))//若兩個(gè)子序都不空，則循環(huán)　　{<p&

55、gt;　　a[4]++;　　if(M[i]<=M[j]) //將M[i],M[j]中較小的存入temp[k]　　temp[k++]=M[i++],b[4]++;　　else<

56、;p>　　temp[k++]=M[j++],c[4]++,b[4]++;　　}　　while(i<=right1) //若第一個(gè)子序列還有剩余的就存入temp　　temp[k++]=M[i++],c[4]++,b[4]++;</

57、p>　　while(j<=right2) //若第二個(gè)子序列還有剩余的就存入temp　　temp[k++]=M[j++],c[4]++,b[4]++;　　for(i=0,k=left;k<=right2;) //將temp中的元素放回　　M[k

58、++]=temp[i++],c[4]++,b[4]++;　　}　　void SortableSList::MergeSort()//合并排序　　{　　int left,right2,right1;

59、　　int size=1; //初始化子序列中元素的個(gè)數(shù)為1　　while(size<n){　　left=0;　　while(left+size<n) //若成立，則需兩兩合并

60、　　{　　right1=left+size-1; //確定子序列1的下界　　if(right1+size>n-1)　　right2=n-1;　　else</p&g

61、t;　　right2=right1+size;　　Merge(left,right1,right2); //合并相鄰的兩個(gè)子序列　　left=right2+1; //確定下次合并的子序列的下界　　}　　si

62、ze*=2;//元素個(gè)數(shù)擴(kuò)大一倍　　}　　}　　void Wrong()//錯(cuò)誤輸出　　{　　printf(&quo

63、t;\n*****按鍵錯(cuò)誤!請(qǐng)重新輸入*****\n");　　getchar();//從標(biāo)準(zhǔn)輸入獲取字符并返回下一個(gè)字符　　}　　void menu()　　{&l

64、t;p>　　printf( " \n");　　printf( " ***************************尊敬的用戶您好*************************** \n");&

65、lt;/p>　　printf( " \n");　　printf( " ****歡迎使用由計(jì)科1班喻思遠(yuǎn) 2011508025 編輯的綜合排序系統(tǒng)!**** \n");</p

66、>　　printf( " \n");　　printf( "

67、 \n");　　printf( " 現(xiàn)在請(qǐng)您做出以下選擇 \n");　　printf( "

68、 \n");　　printf( " \n");　　printf( " ************************************

69、********************************* \n");　　printf( " \n");　　printf( " ******

70、******** 1:插入排序 ***********\n");　　printf( " ************** 2:選擇排序 ***********\n");　　printf( " ************** 3:冒泡排序

71、***********\n");　　printf( " ************** 4:快速排序 ***********\n");　　printf( " ************** 5:合并排序 ***********\n");&

72、lt;/p>　　printf( " ************** 6:時(shí)間效率比較 ***********\n");　　printf( " ************** 0:退出 ***********\n");

73、printf( " \n");　　printf( " ******************************************************************** \n");<

74、;/p>　　}　　void main()　　{　　int i,p;　　for(i=0;i<5;i++)

75、　　{　　a[i]=b[i]=c[i]=0;　　}　　long int a1[5]; //排序所用的時(shí)間　　int a2[5]; //排名&l

76、t;p>　　long int start,finish;　　printf( " ***************************尊敬的用戶您好*************************** \n");　　printf( "

77、 \n\\n");　　printf( " ****歡迎使用由計(jì)科1班喻思遠(yuǎn) 2011508025 編輯的綜合排序系統(tǒng)!**** \n\n\n");　　printf( " 首先請(qǐng)您輸出要

78、比較數(shù)的個(gè)數(shù) \n\n\n");　　SortableSList d;　　//循環(huán)執(zhí)行,直到按0退出　　while(1)　　{

79、　　system("cls");　　menu();//顯示選擇界面　　scanf("%d",&p); //等待輸入　　//輸入0退出　　if(p

80、==0)　　{　　printf(" ************************謝謝!歡迎下次使用*************************!\n");　　getchar();&

81、lt;b>　　break;　　}　　//判斷輸入值，選擇相應(yīng)的操作　　switch(p)　　{<p&g

82、t;　　case 1:outfile.open("data.txt");//將對(duì)象與文件關(guān)聯(lián)　　for(i=0;i<d.n;i++)　　{　　double w;　　ou

83、tfile>>w;　　d.I[i]=w;　　}　　outfile.close();　　start=GetTickCount();　　d.Ins

85、d|%10d|%8d|%ld毫秒|n*n\n",a[0],b[0],c[0],a1[0]);　　printf("\n請(qǐng)按任意鍵繼續(xù)...");getchar();getchar();break;　　case 2: outfile.open("data.txt");//將對(duì)象與文件關(guān)聯(lián)

86、　　for(i=0;i<d.n;i++)　　{　　double w;　　outfile>>w;　　d.S[i]=w;&

87、lt;/p>　　}　　start=GetTickCount();　　d.SelectSort ();　　finish=GetTickCount();　　a1[1]=finish-start;</p&g

89、);getchar();getchar();break;　　case 3: outfile.open("data.txt");//將對(duì)象與文件關(guān)聯(lián)　　for(i=0;i<d.n;i++)　　{<b&g

90、t;　　double w;　　outfile>>w;　　d.B[i]=w;　　}　　start=GetTickCount();<p&g

92、t;|冒泡排序|%8d|%10d|%8d|%ld毫秒|n*n\n",a[2],b[2],c[2],a1[2]);　　printf("\n請(qǐng)按任意鍵繼續(xù)...");getchar();getchar();break;　　case 4: outfile.open("data.txt");//將對(duì)象與文件關(guān)聯(lián)

93、　　for(i=0;i<d.n;i++)　　{　　double w;　　outfile>>w;　　d.Q[i]=w;&

94、lt;/b>　　}　　start=GetTickCount();　　d.QuickSort();　　finish=GetTickCount();　　a1[3]=finish-start;

96、鍵繼續(xù)...");getchar();getchar();break;　　case 5: outfile.open("data.txt");//將對(duì)象與文件關(guān)聯(lián)　　for(i=0;i<d.n;i++)　　{<

97、p>　　double w;　　outfile>>w;　　d.M[i]=w;　　}　　start=GetTickCount();</p&

99、rintf("|合并排序|%8d|%10d|%8d|%ld毫秒|n*log2n\n",a[4],b[4],c[4],a1[4]);　　printf("\n請(qǐng)按任意鍵繼續(xù)...");getchar();getchar();break;　　case 6:&l

100、t;p>　　system("cls");　　outfile.open("data.txt");//將對(duì)象與文件關(guān)聯(lián)　　for(i=0;i<d.n;i++)　　{

101、double w;　　outfile>>w;　　d.I[i]=d.S[i]=d.Q[i]=d.B[i]=d.M[i]=w;　　}　　outfile.close();<p&g

102、t;　　for(i=0;i<5;i++)　　{ 　　a[i]=b[i]=c[i]=0;}　　long int t1,t2,t3,t4,t5,t6,t7,t8,t9,t10;　　t1=GetTickCount();//從系統(tǒng)啟動(dòng)到

103、現(xiàn)在所經(jīng)過的毫秒數(shù)　　d.InsertSort();　　t2=GetTickCount();　　t3=GetTickCount();　　d.SelectSort();　　t4=GetTickCount();

104、　　t5=GetTickCount();　　d.BubbleSort();　　t6=GetTickCount();　　t7=GetTickCount();　　d.QuickSort();　　t8=GetTickC

105、ount();　　t9=GetTickCount();　　d.MergeSort();　　t10=GetTickCount();　　a1[0]=t2-t1;　　a1[1]=t4-t3;

106、a1[2]=t6-t5;　　a1[3]=t8-t7;　　a1[4]=t10-t9;　　for(i=0;i<5;i++)　　{　　int t=1;&l

107、t;/p>　　for(int j=0;j<5;j++)　　{　　if(i!=j)　　if(a1[i]>a1[j])　　t++;</b

108、>　　}　　a2[i]=t;　　}　　printf( "各種內(nèi)排序的性能比較\n");

110、d|%10d|%8d|%6ld毫秒|%6d|n*n\n",a[1],b[1],c[1],a1[1],a2[1]);　　printf( "| 冒泡排序 |%8d|%10d|%8d|%6ld毫秒|%6d|n*n\n",a[2],b[2],c[2],a1[2],a2[2]);　　printf( "| 快速排序 |%8d|

111、%10d|%8d|%6ld毫秒|%6d|n*log2n\n",a[3],b[3],c[3],a1[3],a2[3]);　　printf( "| 合并排序 |%8d|%10d|%8d|%6ld毫秒|%6d|n*log2n\n",a[4],b[4],c[4],a1[4],a2[4]);　　printf("\n請(qǐng)按任意鍵

112、繼續(xù)...");getchar();getchar();break;　　default:Wrong();　　getchar();　　break;　　}<p&

113、gt;　　}　　}　　4 測(cè)試　　4. 1主菜單　　圖—4.1

114、;　　4. 2 插入排序功能　　圖—4.2　　4.3選擇排序功能　　圖—4.3　　4.4 冒泡排序功能<

115、p>　　圖—4.4　　4.5快速排序功能:　　圖—4.5　　4.6合并排序功能:　　圖—4.6　　4.7 5

116、種排序方法比較　　圖—4.7 　　5 課程設(shè)計(jì)總結(jié)　　通過這次課程設(shè)計(jì),我收獲到很多, 平時(shí)的在做作業(yè)時(shí),因?yàn)轭}形與結(jié)構(gòu)都是很簡(jiǎn)單的,并且每一章的內(nèi)容都是有相應(yīng)的例題可以參考,所以在做題時(shí)沒有遇到過很麻煩的問題,而這次不同了,一個(gè)課題拿

117、到手時(shí),給我的感覺是較為復(fù)雜的,而且要求很多,使得題目要求更大了.　　本次課程設(shè)計(jì)我是將整個(gè)程序分塊完成的.將整個(gè)大的程序的實(shí)現(xiàn)分6個(gè)功能模塊,每個(gè)功能都通過一個(gè)相應(yīng)的函數(shù)來(lái)實(shí)現(xiàn).在調(diào)試時(shí)分別進(jìn)行調(diào)試,使得調(diào)試更方便些，最后將程序整體進(jìn)行調(diào)試，在修改不妥之處。　　6參考書目：

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

溫馨提示

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

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---排序綜合

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---排序綜合

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

免費(fèi)下載