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

1、信息科學(xué)與技術(shù)學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告題目名稱：排 序 綜 合專業(yè)班級(jí)：1111學(xué)生姓名：1111學(xué)生學(xué)號(hào)：1111指導(dǎo)教師：111完成日期：1111目 錄1 課程設(shè)計(jì)的目的41.1 課程設(shè)計(jì)的目的41.2 課程設(shè)計(jì)的題目41.3 題目要求42 概要設(shè)計(jì)52.1 存儲(chǔ)結(jié)構(gòu)52.2 基本操作53 詳細(xì)設(shè)計(jì)63.1 流程圖63.2 源程序124 測(cè)試224. 1 主菜單224. 2 插入排序功能224.3 選擇排序功能234.4 冒泡排序功能234.5 快速排序功能244.6 合并排序功能244.7 5種排序方法比較255 課程設(shè)計(jì)總結(jié)266參考書目：261 課程設(shè)計(jì)的目的1.1 課程設(shè)計(jì)的目的數(shù)

2、據(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ī)專業(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ī)中表示出來并對(duì)它們進(jìn)行處理。通過課程設(shè)計(jì)可以提高學(xué)生的思維能力，促進(jìn)學(xué)生的綜合應(yīng)用能力和專業(yè)素質(zhì)的提高。通過此次課程設(shè)計(jì)主要達(dá)到以下目的：n 了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)方法，掌握數(shù)組、鏈表、隊(duì)列、堆棧、樹等基本數(shù)據(jù)結(jié)構(gòu)，具備初步的獨(dú)立分析和設(shè)計(jì)能力；n 初步掌握

3、軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計(jì)、程序編碼、測(cè)試等基本方法和技能；n 提高綜合運(yùn)用所學(xué)的理論知識(shí)和方法獨(dú)立分析和解決問題的能力；n 訓(xùn)練用系統(tǒng)的觀點(diǎn)和軟件開發(fā)一般規(guī)范進(jìn)行軟件開發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng)。1.2 課程設(shè)計(jì)的題目排序綜合，利用隨機(jī)函數(shù)產(chǎn)生N個(gè)隨機(jī)整數(shù)（20000以上），對(duì)這些數(shù)進(jìn)行多種方法進(jìn)行排序。1.3 題目要求 要求：1) 至少采用三種方法實(shí)現(xiàn)上述問題求解（提示，可采用的方法有插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序）。并把排序后的結(jié)果保存在不同的文件中。2) 統(tǒng)計(jì)每一種排序方法的性能（以上機(jī)運(yùn)行程序所花費(fèi)的時(shí)間為準(zhǔn)進(jìn)行對(duì)比），

4、找出其中兩種較快的方法。3) 如果采用4種或4種以上的方法者，可適當(dāng)加分。2 概要設(shè)計(jì)2.1 存儲(chǔ)結(jié)構(gòu)定義的主要的數(shù)據(jù)：(1):class SortableSListpublic: SortableSList(); void InsertSort(); void SelectSort(); void BubbleSort(); void QuickSort(); void MergeSort(); void QuickSort(int left,int right); int QSort(int left,int right); void Merge(int left,int right1,i

5、nt right2); int *I,*S,*Q,*B,*M; int n;聲明的類對(duì)象d;(2) :int a5,b5,c5, 分別記錄比較次數(shù)，交換次數(shù)，移動(dòng)次數(shù);(3) :long int a15; /記錄排序所用的時(shí)間(4) int a25; /記錄排名2.2 基本操作(1):void SortableSList:BubbleSort(); 冒泡排序: (2):void SortableSList:InsertSort(); 直接插入排序 (3):void SortableSList:MergeSort(); 合并排序 (4):void SortableSList:QuickSort(

6、); 快速排序 (5):void SortableSList:SelectSort(); 簡(jiǎn)單選擇排序3 詳細(xì)設(shè)計(jì)3.1 流程圖開始主流程圖：定義對(duì)象，變量輸入要比較的數(shù)的個(gè)數(shù)n進(jìn)入菜單，輸入功能選項(xiàng)序號(hào)p判斷輸入的p P= =0P=1p=2p=3p=4 p=5P=6插入排序合并排序選擇排序時(shí)間效率比較排序快速排序冒泡排序執(zhí)行完相應(yīng)操作并輸出結(jié)果后，按任意鍵返回菜單結(jié)束流程圖-1子流程圖：（1）：插入排序：開始判斷i<n 否 是將待插入元素存入temp判斷j>0&&temp<Ij-1 是 否比較次數(shù)a0加1；Ij=Ij-1;j- -;移動(dòng)次數(shù)c0加1;比較次數(shù)

7、a0加1；找到插入位置j，Ij=temp；結(jié)束流程圖-2 開始（2）：選擇排序： 判斷i<n-1假定待排序列第一個(gè)元素最小，s=i; 是 j=i+1 否判斷j<n 是 否比較次數(shù)a1加1；判斷Sj<Sss=j, 記下每次比較的較小元素的下標(biāo)最小元素與待排序序列的第一個(gè)交換,Swap(Si,Ss);交換次數(shù)b1加1;移動(dòng)次數(shù)c1加3;結(jié)束流程圖-3開始（3）：冒泡排序：判斷i>0進(jìn)入循環(huán)就將last置為0 , last=0;是判斷j<i判 斷Bj+1<Bj是 否否是交換Bj,Bj+1, Swap(Bj,Bj+1);交換次數(shù)b2加1;移動(dòng)次數(shù)c2加3;last=

8、j;比較次數(shù)a2加1如果沒有交換元素，則last=0,退出循環(huán)i=last;結(jié)束流程圖-4（4） ：快速排序：開始調(diào)用函數(shù)QuickSort(0,n-1);判斷l(xiāng)eft<right是調(diào)用QSort(left,right)，開始一趟快速排序，Qleft作為分割元素，并且j=QSort(left,right)； 否遞歸調(diào)用函數(shù)QuickSort(left,j-1)， 對(duì)低端序列快速排序遞歸調(diào)用函數(shù)QuickSort(j+1,right)， 對(duì)高端序列快速排序結(jié)束流程圖-5開始(5) :合并排序: 判斷size<n 是初始化left=0; 否 否 判斷l(xiāng)eft+size<n是確定子

9、序列1的下界， right1=left+size-1; 判斷right1+size>n-1否right2=right1+size;right2=n-1;是 否遞歸調(diào)用Merge(left,right1,right2)，合并相鄰的兩個(gè)子序列；left=right2+1， 確定下次合并的子序列的下界元素個(gè)數(shù)擴(kuò)大一倍，size*=2結(jié)束流程圖-63.2 源程序#include<iostream>#include <stdio.h>#include<fstream>#include<stdlib.h>#include<windows.h>

10、;#include<iomanip>/包含列表的函數(shù)using namespace std;int a5,b5,c5;/a,b,c分別記錄比較次數(shù)，交換次數(shù)，移動(dòng)次數(shù)ifstream outfile;class SortableSListpublic: SortableSList(); void InsertSort(); void SelectSort(); void BubbleSort(); void QuickSort(); void MergeSort(); void QuickSort(int left,int right); int QSort(int left,in

11、t right); void Merge(int left,int right1,int right2); int *I,*S,*Q,*B,*M; int n;SortableSList:SortableSList()printf( " 輸入排序數(shù)字的個(gè)數(shù):n");scanf("%d",&n);I=new intn; /創(chuàng)建一個(gè)指向整型數(shù)據(jù)的數(shù)組,并將地址賦給指向整型數(shù)據(jù)的指針S=new intn;Q=new intn;B=new intn;M=new intn;for(int i=0;i<n;i+) Ii=Si=Qi=Bi=Mi=rand

12、();/將隨機(jī)生成的資料寫入文件ofstream infile;infile.open("data.txt");/將對(duì)象與文件關(guān)聯(lián)for(i=0;i<n;i+)double w=Ii;infile<<w<<" " infile.close();void Swap(int&a,int&b)/交換函數(shù)int T=a;a=b;b=T;void SortableSList:InsertSort()/直接插入排序 for(int i=1;i<n;i+)int j=i;int temp=Ii;/將待插入元素存入te

13、mpc0+;while(j>0&&temp<Ij-1)/從后往前查找插入位置a0+;Ij=Ij-1;j-;c0+;a0+;Ij=temp;/將待插入的元素存入找到的插入位置void SortableSList:SelectSort()/簡(jiǎn)單選擇排序int s;for(int i=0;i<n-1;i+) s=i; /假定待排序序列中的第一個(gè)元素最小 for(int j=i+1;j<n;j+)/每趟掃描n-i-1次 a1+; if(Sj<Ss) s=j;/記下每次比較的較小元素的下標(biāo) Swap(Si,Ss);/最小元素與待排序序列的第一個(gè)交換 c1=c

14、1+3,b1+;void SortableSList:QuickSort()/快速排序 QuickSort(0,n-1); /以初始序列為待排序序列開始快速排序int SortableSList:QSort(int left,int right)int i=left,j=right+1;do /開始一趟快速排序，Qleft作為分割元素 do i+; a3+;while(Qi<Qleft); do j-; a3+; while(Qj>Qleft); if(i<j) Swap(Qi,Qj),b3+;while(i<j);Swap(Qleft,Qj); /交換分割元素Qlef

15、t和Qj的位置c3=c3+3,b3+;return j;void SortableSList:QuickSort(int left,int right)if(left<right) int j=QSort(left,right); QuickSort(left,j-1); /對(duì)低端序列快速排序 QuickSort(j+1,right); /對(duì)高端序列快速排序void SortableSList:BubbleSort()/冒泡排序int i,j,last; i=n-1; while(i>0) /最多進(jìn)行n-1趟 last=0; /進(jìn)入循環(huán)就將last置為0 for(j=0;j<

16、i;j+)/從上往下進(jìn)行比較 if(Bj+1<Bj) Swap(Bj,Bj+1);c2=c2+3;b2+;last=j;a2+; i=last; /如果沒有交換元素，則last=0,退出循環(huán)/兩路合并排序void SortableSList:Merge(int left,int right1,int right2)/兩路合并/right1,right2分別為兩個(gè)子序列的上界int*temp=new intright2-left+1; /創(chuàng)建存放兩個(gè)子序列的臨時(shí)數(shù)組int i=left,j=right1+1,k=0; /i,j是兩個(gè)子序列的游動(dòng)指針，k是temp的游動(dòng)指針while(i&l

17、t;=right1)&&(j<=right2)/若兩個(gè)子序都不空，則循環(huán) a4+; if(Mi<=Mj) /將Mi,Mj中較小的存入tempk tempk+=Mi+,b4+; else tempk+=Mj+,c4+,b4+;while(i<=right1) /若第一個(gè)子序列還有剩余的就存入temp tempk+=Mi+,c4+,b4+;while(j<=right2) /若第二個(gè)子序列還有剩余的就存入temp tempk+=Mj+,c4+,b4+;for(i=0,k=left;k<=right2;) /將temp中的元素放回 Mk+=tempi+,

18、c4+,b4+;void SortableSList:MergeSort()/合并排序int left,right2,right1;int size=1; /初始化子序列中元素的個(gè)數(shù)為1while(size<n) left=0; while(left+size<n) /若成立，則需兩兩合并right1=left+size-1; /確定子序列1的下界if(right1+size>n-1)right2=n-1;elseright2=right1+size;Merge(left,right1,right2); /合并相鄰的兩個(gè)子序列l(wèi)eft=right2+1; /確定下次合并的子序

19、列的下界 size*=2;/元素個(gè)數(shù)擴(kuò)大一倍void Wrong()/錯(cuò)誤輸出printf("n*按鍵錯(cuò)誤!請(qǐng)重新輸入*n");getchar();/從標(biāo)準(zhǔn)輸入獲取字符并返回下一個(gè)字符void menu()printf( " n");printf( " *尊敬的用戶您好* n");printf( " n");printf( " *歡迎使用由計(jì)科1班 喻思遠(yuǎn) 2011508025 編輯的綜合排序系統(tǒng)!* n");printf( " n");printf( " n&qu

20、ot;);printf( " 現(xiàn)在請(qǐng)您做出以下選擇 n");printf( " n");printf( " n");printf( " * n");printf( " n");printf( " * 1:插入排序 *n");printf( " * 2:選擇排序 *n");printf( " * 3:冒泡排序 *n");printf( " * 4:快速排序 *n");printf( " * 5:合并排序 *n

21、");printf( " * 6:時(shí)間效率比較 *n");printf( " * 0:退出 *n");printf( " n");printf( " * n");void main()int i,p;for(i=0;i<5;i+)ai=bi=ci=0;long int a15; /排序所用的時(shí)間int a25; /排名long int start,finish;printf( " *尊敬的用戶您好* n");printf( " nn");printf( &qu

22、ot; *歡迎使用由計(jì)科1班 喻思遠(yuǎn) 2011508025 編輯的綜合排序系統(tǒng)!* nnn");printf( " 首先請(qǐng)您輸出要比較數(shù)的個(gè)數(shù) nnn");SortableSList d;/循環(huán)執(zhí)行,直到按0退出 while(1) system("cls"); menu();/顯示選擇界面 scanf("%d",&p); /等待輸入 /輸入0退出 if(p=0) printf(" *謝謝!歡迎下次使用*!n"); getchar(); break; /判斷輸入值，選擇相應(yīng)的操作 switch(p)

23、 case 1:outfile.open("data.txt");/將對(duì)象與文件關(guān)聯(lián)for(i=0;i<d.n;i+)double w;outfile>>w;d.Ii=w;outfile.close();start=GetTickCount();d.InsertSort();finish=GetTickCount();a10=finish-start;printf("|排序名稱|比較次數(shù)|交換的次數(shù)|移動(dòng)次數(shù)|時(shí) 間|時(shí)間復(fù)雜度n");printf("|插入排序|%8d|%10d|%8d|%ld毫秒|n*nn",a0

24、,b0,c0,a10);printf("n請(qǐng)按任意鍵繼續(xù).");getchar();getchar();break; case 2: outfile.open("data.txt");/將對(duì)象與文件關(guān)聯(lián)for(i=0;i<d.n;i+)double w;outfile>>w;d.Si=w;start=GetTickCount();d.SelectSort ();finish=GetTickCount();a11=finish-start;printf("|排序名稱|比較次數(shù)|交換的次數(shù)|移動(dòng)次數(shù)|時(shí) 間|時(shí)間復(fù)雜度n"

25、;);printf("|選擇排序|%8d|%10d|%8d|%ld毫秒|n*nn",a1,b1,c1,a11);printf("n請(qǐng)按任意鍵繼續(xù).");getchar();getchar();break; case 3: outfile.open("data.txt");/將對(duì)象與文件關(guān)聯(lián)for(i=0;i<d.n;i+)double w;outfile>>w;d.Bi=w; start=GetTickCount();d.BubbleSort ();finish=GetTickCount();a12=finish-s

26、tart;printf("|排序名稱|比較次數(shù)|交換的次數(shù)|移動(dòng)次數(shù)|時(shí) 間|時(shí)間復(fù)雜度n");printf("|冒泡排序|%8d|%10d|%8d|%ld毫秒|n*nn",a2,b2,c2,a12);printf("n請(qǐng)按任意鍵繼續(xù).");getchar();getchar();break; case 4: outfile.open("data.txt");/將對(duì)象與文件關(guān)聯(lián)for(i=0;i<d.n;i+)double w;outfile>>w;d.Qi=w;start=GetTickCoun

27、t();d.QuickSort();finish=GetTickCount();a13=finish-start;printf("|排序名稱|比較次數(shù)|交換的次數(shù)|移動(dòng)次數(shù)|時(shí) 間|時(shí)間復(fù)雜度n");printf("|快速排序|%8d|%10d|%8d|%ld毫秒|n*log2nn",a3,b3,c3,a13);printf("n請(qǐng)按任意鍵繼續(xù).");getchar();getchar();break; case 5: outfile.open("data.txt");/將對(duì)象與文件關(guān)聯(lián)for(i=0;i<d

28、.n;i+)double w;outfile>>w;d.Mi=w; start=GetTickCount();d.MergeSort();finish=GetTickCount();a14=finish-start;printf("|排序名稱|比較次數(shù)|交換的次數(shù)|移動(dòng)次數(shù)|時(shí) 間|時(shí)間復(fù)雜度n");printf("|合并排序|%8d|%10d|%8d|%ld毫秒|n*log2nn",a4,b4,c4,a14);printf("n請(qǐng)按任意鍵繼續(xù).");getchar();getchar();break; case 6: s

29、ystem("cls");outfile.open("data.txt");/將對(duì)象與文件關(guān)聯(lián)for(i=0;i<d.n;i+)double w;outfile>>w;d.Ii=d.Si=d.Qi=d.Bi=d.Mi=w;outfile.close(); for(i=0;i<5;i+) ai=bi=ci=0;long int t1,t2,t3,t4,t5,t6,t7,t8,t9,t10;t1=GetTickCount();/從系統(tǒng)啟動(dòng)到現(xiàn)在所經(jīng)過的毫秒數(shù)d.InsertSort();t2=GetTickCount();t3=Get

30、TickCount();d.SelectSort();t4=GetTickCount();t5=GetTickCount();d.BubbleSort();t6=GetTickCount();t7=GetTickCount();d.QuickSort();t8=GetTickCount();t9=GetTickCount();d.MergeSort();t10=GetTickCount();a10=t2-t1;a11=t4-t3;a12=t6-t5;a13=t8-t7;a14=t10-t9;for(i=0;i<5;i+)int t=1;for(int j=0;j<5;j+)if(i!=j)if(a1i