《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計報告

1、.課程設(shè)計報告-數(shù)據(jù)結(jié)構(gòu)學(xué)院:軟件學(xué)院班級:11級二班學(xué)號:54110211姓名：劉海鯨輔導(dǎo)老師：劉亞波老師數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告姓名：劉海鯨學(xué)號：54110211實驗室：座位號:提交日期：2013.3.13成績：指導(dǎo)教師：劉亞波問題解析（對問題的分析、解題思路與解題方法）：實驗?zāi)康臑槭刮覀儗W(xué)習(xí)完數(shù)據(jù)結(jié)構(gòu)課程后，全面深入理解數(shù)據(jù)結(jié)構(gòu)知識，掌握應(yīng)用技巧，提高應(yīng)用與分析能力，并培養(yǎng)學(xué)生綜合運用所學(xué)理論知識求解問題的能力和協(xié)作精神。解題思路(分析)：題目要求獨立編寫程序，完成對起泡排序，直接插入排序，簡單選擇排序，快速排序，希爾排序，堆排序6種內(nèi)排序算法的比較，并且使用至少5組不同的輸入數(shù)據(jù)（記錄個數(shù)

2、不小于1000個，其中包括完全正序，完全逆序和無序情況）進行排序，比較各組記錄與各種排序方法在關(guān)鍵字比較次數(shù)和關(guān)鍵字移動次數(shù)這兩個指標上的差異。因此只需對文件進行排序并計算出兩項指標針對某一組特定數(shù)據(jù)在不同排序方法中的值，既可以完成題目要求。編寫正確的排序算法，使用程序讀取不同文件，并定義變量，記錄排序過程中兩項指標的值，就是本題的解題思路。解題方法：使用Code:blocks作為本次實驗的開發(fā)工具，使用C+完成程序。首先使用數(shù)據(jù)產(chǎn)生程序來產(chǎn)生所需的5個數(shù)據(jù)文件，使用了C+中cstdlib文件中的rand（）函數(shù)和srand（）函數(shù)共同產(chǎn)生3組偽隨機數(shù)；在另一個工程中創(chuàng)建了data.h與con

3、trol.h兩個頭文件和main.cpp源文件，其中data.h定義了數(shù)據(jù)類型（模板類），包括主要的排序函數(shù)和數(shù)據(jù)成員，control.h定義了控制類，來完成界面控制，數(shù)據(jù)文件讀取和排序功能的實現(xiàn)，main.cpp是對控制類對象的控制函數(shù)conmian（）的調(diào)用來完成整個程序。最后運行程序來完成對比較指標的統(tǒng)計并進行分析，對得出結(jié)果進行解釋。任務(wù)分工：本實驗由本人獨立完成。進度安排：為第一次實驗課將6個內(nèi)排序算法完成并調(diào)試成功，周末之前完成界面控制并對排序結(jié)果進行分析，第二次實驗之前完成課程設(shè)計報告，第二次試驗對程序結(jié)果進行最后檢查并提交實驗報告。數(shù)據(jù)結(jié)構(gòu)選擇（包括改進或給出）：使用數(shù)組作為本

4、實驗基本的數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)類中包含有數(shù)組的頭指針head，在初始化時動態(tài)申請數(shù)組空間，此外還有count（整型）用于記錄數(shù)組個數(shù),同時可以對數(shù)組進行6種內(nèi)排序及顯示數(shù)組元素的操作。算法設(shè)計：借助課本與網(wǎng)絡(luò)，使用C+編寫算法，詳細請看后面程序清單。編程與程序清單：1./頭文件data.h2./文件數(shù)據(jù)類Data定義3. /起泡排序（升序）4. /直接插入排序（升序）5. /簡單選擇排序（升序）6. /快速排序(升序)7./快速排序的遞歸函數(shù)8./希爾排序 （升序）9./插入排序（升序）10. /堆排序（升序）11./控制類12. /功能選擇13./主函數(shù)1./頭文件data.h 1./頭文件dat

5、a.h#ifndef DATA_H_INCLUDED#define DATA_H_INCLUDED#include<ctime>#include<iostream>using namespace std;2./文件數(shù)據(jù)類Data定義template<class T>class Data private: T *head; /數(shù)據(jù)數(shù)組指針，用于動態(tài)申請數(shù)組空間 int count; /數(shù)組大小 public: /構(gòu)造函數(shù)，使指針為空 Data()head=NULL; /用已有數(shù)組構(gòu)造數(shù)組元素，當前程序使用該函數(shù)來構(gòu)造數(shù)據(jù)元素 void copy(T *h,in

6、t c=1000) if(head!=NULL) delete head; head=h;count=c; head=new Tcount; for(int i=0;i<count;i+) headi=hi; /手動輸入各元素，當前程序未使用，調(diào)試程序時使用！ void set() if(head!=NULL) delete head; cout<<"請輸入數(shù)據(jù)個數(shù)："<<endl; cin>>count; head=new Tcount; cout<<"請輸入數(shù)據(jù)："<<endl; fo

7、r(int i=0;i<count;i+) cin>>headi; /析構(gòu)函數(shù)，回收空間 Data()delete head;3. /起泡排序（升序） void bSort() if(isEmpty()cout<<" 文件中無記錄，無法排序！"<<endl;return; int compareTime=0; /關(guān)鍵詞比較次數(shù) int moveTime=0; /關(guān)鍵詞移動次數(shù) int bound=count; int start,finish; /記錄程序運行時間 T temp; cout<<" 正在排序.&q

8、uot;<<endl; start=clock(); /記錄初始時間 /算法主體 while(bound!=0) int t=0; for(int i=0;i<bound-1;i+) compareTime+; if(headi>headi+1) temp=headi; headi=headi+1; headi+1=temp; t=i+1; moveTime+=3; /記錄交換一次移動次數(shù)加3 bound=t; finish=clock(); cout<<" >>排序后結(jié)果為："<<endl; display();

9、 /輸出排序后序列 cout<<endl<<" *-"<<endl <<" *關(guān)鍵詞比較次數(shù)："<<compareTime<<endl <<" *記錄移動次數(shù)："<<moveTime<<endl <<" *排序執(zhí)行時間："<<finish-start<<"ms"<<endl <<" *-"<<end

10、l<<endl; 4. /直接插入排序（升序） void iSort() if(isEmpty()cout<<" 文件中無記錄，無法排序！"<<endl; int compareTime=0; int moveTime=0; long start,finish; T temp; cout<<" 正在排序."<<endl; start=clock(); for(int i=1;i<count;i+) int j; j=i-1; temp=headi; moveTime+; /無記錄交換，僅有

11、向輔存中移動，故移動次數(shù)加1 while(j>=0&&headj>temp) compareTime+; headj+1=headj; moveTime+; /記錄向后移一位，移動次數(shù)加1 j-; compareTime+; /跳出循環(huán)后比較次數(shù)要再加1 headj+1=temp; moveTime+; finish=clock(); cout<<" >>排序后結(jié)果為："<<endl; display(); cout<<endl<<" *-"<<endl

12、<<" *關(guān)鍵詞比較次數(shù)："<<compareTime<<endl <<" *記錄移動次數(shù)："<<moveTime<<endl <<" *排序執(zhí)行時間："<<(finish-start)<<"ms"<<endl <<" *-"<<endl<<endl; 5. /簡單選擇排序（升序） void sSort() if(isEmpty()cout&

13、lt;<" 文件中無記錄，無法排序！"<<endl; int compareTime=0; int moveTime=0; long start,finish; T temp; cout<<" 正在排序."<<endl; start=clock(); for(int i=0;i<count-1;i+) int j=i; for(int k=i+1;k<count;k+) compareTime+; if(headj>headk) j=k; /標記當前最大的記錄下標 if(i!=j) temp=h

14、eadi; headi=headj; headj=temp; moveTime+=3; finish=clock(); cout<<" >>排序后結(jié)果為："<<endl; display(); cout<<endl<<" *-"<<endl <<" *關(guān)鍵詞比較次數(shù)："<<compareTime<<endl <<" *記錄移動次數(shù)："<<moveTime<<endl <

15、;<" *排序執(zhí)行時間："<<(finish-start)<<"ms"<<endl <<" *-"<<endl<<endl; 6. /快速排序(升序) void qqSort() if(isEmpty()cout<<" 文件中無記錄，無法排序！"<<endl; long start,finish; int times2=0,0; /要調(diào)用函數(shù)，故使用數(shù)組來記錄關(guān)鍵詞的比較次數(shù)和移動次數(shù)，直接進行計數(shù) start=c

16、lock(); cout<<" 正在排序."<<endl; qSort(head,0,count,times); /一趟快速排序函數(shù) finish=clock(); cout<<" >>排序后結(jié)果為："<<endl; display(); cout<<endl<<" *-"<<endl <<" *關(guān)鍵詞比較次數(shù)："<<times0<<endl <<" *記錄移動次

17、數(shù)："<<times1<<endl <<" *排序執(zhí)行時間："<<(finish-start)<<"ms"<<endl <<" *-"<<endl<<endl; 7./快速排序的遞歸函數(shù) void qSort(T *head,int m,int n,int *times) int i=m,j=n; T temp=headm,t=m; if(m<n) /遞歸出口（m>=n） while(i<j) i=i

18、+1; while(headi<temp&&i!=n)times0+;i+; j=j-1; while(headj>temp&&j!=m)times0+;j-; if(i<j) t=headi; headi=headj; headj=t; times1+=3; if(m!=j) t=headm; headm=headj; headj=t; times1+=3; qSort(head,m,j,times); qSort(head,j+1,n,times); 8./希爾排序 （升序） void shell() if(isEmpty()cout<

19、;<" 文件中無記錄，無法排序！"<<endl; int times2=0,0; int seq8=701,301,132,57,23,10,4,1; /依據(jù)課本得到希爾排序最優(yōu)的增量遞減序列 long start,finish; cout<<" 正在排序."<<endl; start=clock(); int n; for(int i=0;i<8;i+) n=seqi; insert(n,times); /調(diào)用插入排序算法對同組數(shù)據(jù)進行排序 finish=clock(); cout<<&quo

20、t; >>排序后結(jié)果為："<<endl; display(); cout<<endl<<" *-"<<endl <<" *關(guān)鍵詞比較次數(shù)："<<times0<<endl <<" *記錄移動次數(shù)："<<times1<<endl <<" *排序執(zhí)行時間："<<(finish-start)<<"ms"<<endl

21、<<" *-"<<endl<<endl; 9./插入排序（被希爾排序shell函數(shù)調(diào)用） void insert(int n,int * times) /增量為n帶來一系列程序的改動 for(int k=0;k+n<count;k+) T temp; for(int i=k+n;i<count;i+=n) int j; j=i-n; temp=headi; times1+; while(j>=k&&headj>temp) times0+; headj+n=headj; times1+; j-=n;

22、times0+; headj+n=temp; times1+; 10. /堆排序（升序） void hSort() /堆為完全二叉樹，故可用數(shù)組構(gòu)造堆，且不會造成空間的浪費 if(isEmpty()cout<<" 文件中無記錄，無法排序！"<<endl; int times2=0,0; T temp; long start,finish; cout<<" 正在排序."<<endl; start=clock(); /初始建堆 for(int i=count/2;i>0;i-) restore(i,cou

23、nt,times); /排序及重建堆 for(int i=count;i>1;i-) temp=head0; head0=headi-1; headi-1=temp; times1+=3; restore(1,i-1,times); finish=clock(); cout<<" >>排序后結(jié)果為："<<endl; display(); cout<<endl<<" *-"<<endl <<" *關(guān)鍵詞比較次數(shù)："<<times0<

24、;<endl <<" *記錄移動次數(shù)："<<times1<<endl <<" *排序執(zhí)行時間："<<(finish-start)<<"ms"<<endl <<" *-"<<endl<<endl; /重建堆算法（被堆排序hSort函數(shù)調(diào)用） void restore(int a,int b,int * times) int mark,j=a; T temp; while(j<=b/2)

25、if(2*j<b&&head2*j-1<head2*j) mark=2*j; times0+; else mark=2*j-1; times0+; if(headmark>headj-1) temp=headmark; headmark=headj-1; headj-1=temp; j=mark+1; times0+; times1+=3; else j=b; /人為改變j的值，跳出循環(huán)，退出程序 times0+; /輸出記錄序列（升序） void display() for(int i=0;i<count;i+) cout<<headi&l

26、t;<" " cout<<endl; /判斷數(shù)據(jù)是否為空 bool isEmpty()constreturn head=NULL; /獲得頭指針，本程序未使用！ T *getHead()return head; /獲得數(shù)組元素個數(shù)，本程序未使用！ int getCount ()constreturn count;#endif / DATA_H_INCLUDED/頭文件control.h#ifndef CONTROL_H_INCLUDED#define CONTROL_H_INCLUDED#include"data.h"#include&

27、lt;iostream>#include<sstream> /含有istringstream類#include<fstream>using namespace std;11./控制類，進行界面管理,記錄文件讀取，調(diào)用排序函數(shù)等操作class Control public: void conmain() /控制函數(shù) cout<<"#" <<"#【數(shù)據(jù)結(jié)構(gòu)課程設(shè)計（一）：內(nèi)排序算法比較】#" <<"#" cout<<"#使用說明：運行程序，請輸入數(shù)據(jù)文

28、件名（a.txt,b.txt,c.txt均為無序數(shù)據(jù)，d.txt為完#" <<"#全正序數(shù)據(jù)，e.txt為完全逆序文件，均存放在當前目錄下），之后請按照用戶個人需求 #" <<"#選擇相應(yīng)功能！ #" <<"#" <<" #"<<endl <<" #>>功能列表 #"<<endl <<" #"<<endl <<" # 1.起泡

29、排序 （升序） #"<<endl <<" # 2.直接插入排序（升序） #"<<endl <<" # 3.簡單選擇排序 （升序） #"<<endl <<" # 4.快速排序（升序） #"<<endl <<" # 5.希爾排序（升序） #"<<endl <<" # 6.堆排序（升序） #"<<endl <<" # 0.退出 #"

30、;<<endl <<" #"<<endl;/定義選擇變量及輔助變量int opt1,a,i=0;/數(shù)組存儲數(shù)據(jù)int data1000;/定義Data類對象Data<int> temp;/文件名string file; /讀取文件,從輸入的文件名中讀取數(shù)據(jù)，a.txt,b.txt,c.txt為隨機數(shù)據(jù)，e.txt為正序，e.txt為逆序cout<<endl<<" >>請輸入目標數(shù)據(jù)文件：" cin>>file; ifstream in(file.c_str()

31、; /string類轉(zhuǎn)換為字符串且在末尾加'0' for(string s;getline(in,s);) /讀取文件，讀取整行，使用istringstream類讀出數(shù)字（可自動忽略數(shù)字間的空格） for(istringstream sin(s);sin>>a;); datai+=a; 12. /功能選擇cout<<endl<<" >>請選擇功能（輸入對應(yīng)功能的序號）："cin>>opt1;while(opt1)switch(opt1) /調(diào)用起泡排序函數(shù)case 1:temp.copy(data)

32、;temp.bSort();break; /調(diào)用直接插入排序函數(shù)case 2:temp.copy(data);temp.iSort();break; /調(diào)用簡單選擇排序函數(shù)case 3:temp.copy(data);temp.sSort();break; /調(diào)用快速排序函數(shù) case 4:temp.copy(data);temp.qqSort();break; /調(diào)用Shell排序函數(shù) case 5:temp.copy(data);temp.shell();break; /調(diào)用堆排序函數(shù) case 6:temp.copy(data);temp.hSort();break; <<&

33、quot; |<您的輸入有誤，請再次輸入！>|"<<endl <<" -"<<endl; cout<<" #"<<endl <<" #>>功能列表 #"<<endl <<" #"<<endl <<" # 1.起泡排序 （升序） #"<<endl <<" # 2.直接插入排序（升序） #"<<

34、;endl <<" # 3.簡單選擇排序 （升序） #"<<endl <<" # 4.快速排序（升序） #"<<endl <<" # 5.希爾排序（升序） #"<<endl <<" # 6.堆排序（升序） #"<<endl <<" # 0.退出 #"<<endl <<" #"<<endl;cout<<endl<<

35、;" >>請選擇功能（輸入對應(yīng)功能的序號）："cin>>opt1;cout<<"#"<<"#"<<"#"<<endl; ;#endif / CONTROL_H_INCLUDED/源文件main.cpp#include"data.h"#include"control.h"#include<iostream>using namespace std;12./主函數(shù)int main() Control

36、 a; /控制類Control類對象 a.conmain(); /控制函數(shù) return 0;測試方法：使用排序程序前，先使用數(shù)據(jù)產(chǎn)生程序generator產(chǎn)生所需數(shù)據(jù)（整型，1000個記錄），包括3組無序數(shù)據(jù)（用rand（）與srand（）函數(shù)產(chǎn)生），一組完全正序數(shù)據(jù)和一組完全逆序數(shù)據(jù)，并分別存儲于5個不同的文本文件中。在排序程序中依次讀取5個數(shù)據(jù)文件并按照程序的提示對數(shù)據(jù)進行排序，觀測輸出的排序序列并對關(guān)鍵詞比較次數(shù)和關(guān)鍵詞移動次數(shù)進行分析。測試數(shù)據(jù)：由數(shù)據(jù)產(chǎn)生程序generator產(chǎn)生，存儲于文件由數(shù)據(jù)產(chǎn)生程序generator產(chǎn)生，存儲于文件a.txt,b.txt,c.txt,d.tx

37、t,e.txt(前三個為無序記錄文件，第四個為完全正序文件，第五個為完全逆序文件)中，記錄為整型數(shù)據(jù)， 規(guī)模為1000數(shù)量級。測試結(jié)果：起泡排序數(shù)據(jù)組別比較次數(shù)/次移動次數(shù)/次排序時間/ms理論值（最好，最壞，平均）O（n），O(n2)，O(n2)0，O(n2)，O(n2)-a49729676015212b49713975650716c49559674349912d99901e499500149850014直接插入排序數(shù)據(jù)組別比較次數(shù)/次移動次數(shù)/次排序時間/ms理論值（最好，最壞，平均）O（n），O(n2)，O(n2)O（n），O(n2)，O(n2)-a2543832553825b25316

38、82541676c2488322498315d99919981e50049950149811簡單選擇排序數(shù)據(jù)組別比較次數(shù)/次移動次數(shù)/次排序時間/ms理論值（最好，最壞，平均）O(n2)，O(n2)，O(n2)0，O(n)，O(n)-a49950029856b49950029766c49950029736d49950007e49950015009快速排序數(shù)據(jù)組別比較次數(shù)/次移動次數(shù)/次排序時間/ms理論值（最好，最壞，平均）O(n·log2n)，O(n·log2n)，O(n·log2n)0，O(n·log2n)，O(n·log2n)-a834182953b663983764c759382232d49950005e49950015006Shell排序數(shù)據(jù)組別比較次數(shù)/次移動次數(shù)/次排序時間/ms理論值（最好，最壞，平均）O(n·（log2n）2)O(n·（log2n）2)-a714181142199923b714136142195422c714210142202821d707818141563622e710908141872621堆