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

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

2、據(jù)結(jié)構(gòu)課程主要是研究非數(shù)值計算的程序設(shè)計問題中所出現(xiàn)的計算機操作對象以及它們之間的關(guān)系和操作的學科。數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學、計算機軟件和計算機硬件之間的一門計算機專業(yè)的核心課程，它是計算機程序設(shè)計、數(shù)據(jù)庫、操作系統(tǒng)、編譯原理及人工智能等的重要基礎(chǔ)，廣泛的應(yīng)用于信息學、系統(tǒng)工程等各種領(lǐng)域。學習數(shù)據(jù)結(jié)構(gòu)是為了將實際問題中所涉及的對象在計算機中表示出來并對它們進行處理。通過課程設(shè)計可以提高學生的思維能力，促進學生的綜合應(yīng)用能力和專業(yè)素質(zhì)的提高。通過此次課程設(shè)計主要達到以下目的：n 了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計方法，掌握數(shù)組、鏈表、隊列、堆棧、樹等基本數(shù)據(jù)結(jié)構(gòu)，具備初步的獨立分析和設(shè)計能力；n 初步掌握

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

4、找出其中兩種較快的方法。3) 如果采用4種或4種以上的方法者，可適當加分。2 概要設(shè)計2.1 存儲結(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;聲明的類對象d;(2) :int a5,b5,c5, 分別記錄比較次數(shù)，交換次數(shù)，移動次數(shù);(3) :long int a15; /記錄排序所用的時間(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(); 簡單選擇排序3 詳細設(shè)計3.1 流程圖開始主流程圖：定義對象，變量輸入要比較的數(shù)的個數(shù)n進入菜單，輸入功能選項序號p判斷輸入的p P= =0P=1p=2p=3p=4 p=5P=6插入排序合并排序選擇排序時間效率比較排序快速排序冒泡排序執(zhí)行完相應(yīng)操作并輸出結(jié)果后，按任意鍵返回菜單結(jié)束流程圖-1子流程圖：（1）：插入排序：開始判斷i<n 否 是將待插入元素存入temp判斷j>0&&temp<Ij-1 是 否比較次數(shù)a0加1；Ij=Ij-1;j- -;移動次數(shù)c0加1;比較次數(shù)

7、a0加1；找到插入位置j，Ij=temp；結(jié)束流程圖-2 開始（2）：選擇排序： 判斷i<n-1假定待排序列第一個元素最小，s=i; 是 j=i+1 否判斷j<n 是 否比較次數(shù)a1加1；判斷Sj<Sss=j, 記下每次比較的較小元素的下標最小元素與待排序序列的第一個交換,Swap(Si,Ss);交換次數(shù)b1加1;移動次數(shù)c1加3;結(jié)束流程圖-3開始（3）：冒泡排序：判斷i>0進入循環(huán)就將last置為0 , last=0;是判斷j<i判 斷Bj+1<Bj是 否否是交換Bj,Bj+1, Swap(Bj,Bj+1);交換次數(shù)b2加1;移動次數(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)， 對低端序列快速排序遞歸調(diào)用函數(shù)QuickSort(j+1,right)， 對高端序列快速排序結(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)，合并相鄰的兩個子序列；left=right2+1， 確定下次合并的子序列的下界元素個數(shù)擴大一倍，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ù)，移動次數(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ù)字的個數(shù):n");scanf("%d",&n);I=new intn; /創(chuàng)建一個指向整型數(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、();/將隨機生成的資料寫入文件ofstream infile;infile.open("data.txt");/將對象與文件關(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()/簡單選擇排序int s;for(int i=0;i<n-1;i+) s=i; /假定待排序序列中的第一個元素最小 for(int j=i+1;j<n;j+)/每趟掃描n-i-1次 a1+; if(Sj<Ss) s=j;/記下每次比較的較小元素的下標 Swap(Si,Ss);/最小元素與待排序序列的第一個交換 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); /對低端序列快速排序 QuickSort(j+1,right); /對高端序列快速排序void SortableSList:BubbleSort()/冒泡排序int i,j,last; i=n-1; while(i>0) /最多進行n-1趟 last=0; /進入循環(huán)就將last置為0 for(j=0;j<

16、i;j+)/從上往下進行比較 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分別為兩個子序列的上界int*temp=new intright2-left+1; /創(chuàng)建存放兩個子序列的臨時數(shù)組int i=left,j=right1+1,k=0; /i,j是兩個子序列的游動指針，k是temp的游動指針while(i&l

17、t;=right1)&&(j<=right2)/若兩個子序都不空，則循環(huán) a4+; if(Mi<=Mj) /將Mi,Mj中較小的存入tempk tempk+=Mi+,b4+; else tempk+=Mj+,c4+,b4+;while(i<=right1) /若第一個子序列還有剩余的就存入temp tempk+=Mi+,c4+,b4+;while(j<=right2) /若第二個子序列還有剩余的就存入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; /初始化子序列中元素的個數(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); /合并相鄰的兩個子序列l(wèi)eft=right2+1; /確定下次合并的子序

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

20、ot;);printf( " 現(xiàn)在請您做出以下選擇 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:時間效率比較 *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; /排序所用的時間int a25; /排名long int start,finish;printf( " *尊敬的用戶您好* n");printf( " nn");printf( &qu

22、ot; *歡迎使用由計科1班 喻思遠 2011508025 編輯的綜合排序系統(tǒng)!* nnn");printf( " 首先請您輸出要比較數(shù)的個數(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");/將對象與文件關(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ù)|移動次數(shù)|時 間|時間復雜度n");printf("|插入排序|%8d|%10d|%8d|%ld毫秒|n*nn",a0

24、,b0,c0,a10);printf("n請按任意鍵繼續(xù).");getchar();getchar();break; case 2: outfile.open("data.txt");/將對象與文件關(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ù)|移動次數(shù)|時 間|時間復雜度n"

25、;);printf("|選擇排序|%8d|%10d|%8d|%ld毫秒|n*nn",a1,b1,c1,a11);printf("n請按任意鍵繼續(xù).");getchar();getchar();break; case 3: outfile.open("data.txt");/將對象與文件關(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ù)|移動次數(shù)|時 間|時間復雜度n");printf("|冒泡排序|%8d|%10d|%8d|%ld毫秒|n*nn",a2,b2,c2,a12);printf("n請按任意鍵繼續(xù).");getchar();getchar();break; case 4: outfile.open("data.txt");/將對象與文件關(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ù)|移動次數(shù)|時 間|時間復雜度n");printf("|快速排序|%8d|%10d|%8d|%ld毫秒|n*log2nn",a3,b3,c3,a13);printf("n請按任意鍵繼續(xù).");getchar();getchar();break; case 5: outfile.open("data.txt");/將對象與文件關(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ù)|移動次數(shù)|時 間|時間復雜度n");printf("|合并排序|%8d|%10d|%8d|%ld毫秒|n*log2nn",a4,b4,c4,a14);printf("n請按任意鍵繼續(xù).");getchar();getchar();break; case 6: s

29、ystem("cls");outfile.open("data.txt");/將對象與文件關(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)啟動到現(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