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

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

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

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

5、a.h#ifndef DATA_H_INCLUDED#define DATA_H_INCLUDED#include<ctime>#include<iostream>using namespace std;2./文件數據類Data定義template<class T>class Data private: T *head; /數據數組指針，用于動態申請數組空間 int count; /數組大小 public: /構造函數，使指針為空 Data()head=NULL; /用已有數組構造數組元素，當前程序使用該函數來構造數據元素 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; /手動輸入各元素，當前程序未使用，調試程序時使用！ void set() if(head!=NULL) delete head; cout<<"請輸入數據個數："<<endl; cin>>count; head=new Tcount; cout<<"請輸入數據："<<endl; fo

7、r(int i=0;i<count;i+) cin>>headi; /析構函數，回收空間 Data()delete head;3. /起泡排序（升序） void bSort() if(isEmpty()cout<<" 文件中無記錄，無法排序！"<<endl;return; int compareTime=0; /關鍵詞比較次數 int moveTime=0; /關鍵詞移動次數 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; /記錄交換一次移動次數加3 bound=t; finish=clock(); cout<<" >>排序后結果為："<<endl; display();

9、 /輸出排序后序列 cout<<endl<<" *-"<<endl <<" *關鍵詞比較次數："<<compareTime<<endl <<" *記錄移動次數："<<moveTime<<endl <<" *排序執行時間："<<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、向輔存中移動，故移動次數加1 while(j>=0&&headj>temp) compareTime+; headj+1=headj; moveTime+; /記錄向后移一位，移動次數加1 j-; compareTime+; /跳出循環后比較次數要再加1 headj+1=temp; moveTime+; finish=clock(); cout<<" >>排序后結果為："<<endl; display(); cout<<endl<<" *-"<<endl

12、<<" *關鍵詞比較次數："<<compareTime<<endl <<" *記錄移動次數："<<moveTime<<endl <<" *排序執行時間："<<(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<<" >>排序后結果為："<<endl; display(); cout<<endl<<" *-"<<endl <<" *關鍵詞比較次數："<<compareTime<<endl <<" *記錄移動次數："<<moveTime<<endl <

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

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

17、數："<<times1<<endl <<" *排序執行時間："<<(finish-start)<<"ms"<<endl <<" *-"<<endl<<endl; 7./快速排序的遞歸函數 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; /依據課本得到希爾排序最優的增量遞減序列 long start,finish; cout<<" 正在排序."<<endl; start=clock(); int n; for(int i=0;i<8;i+) n=seqi; insert(n,times); /調用插入排序算法對同組數據進行排序 finish=clock(); cout<<&quo

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

21、<<" *-"<<endl<<endl; 9./插入排序（被希爾排序shell函數調用） 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() /堆為完全二叉樹，故可用數組構造堆，且不會造成空間的浪費 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<<" >>排序后結果為："<<endl; display(); cout<<endl<<" *-"<<endl <<" *關鍵詞比較次數："<<times0<

24、;<endl <<" *記錄移動次數："<<times1<<endl <<" *排序執行時間："<<(finish-start)<<"ms"<<endl <<" *-"<<endl<<endl; /重建堆算法（被堆排序hSort函數調用） 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的值，跳出循環，退出程序 times0+; /輸出記錄序列（升序） void display() for(int i=0;i<count;i+) cout<<headi&l

26、t;<" " cout<<endl; /判斷數據是否為空 bool isEmpty()constreturn head=NULL; /獲得頭指針，本程序未使用！ T *getHead()return head; /獲得數組元素個數，本程序未使用！ 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./控制類，進行界面管理,記錄文件讀取，調用排序函數等操作class Control public: void conmain() /控制函數 cout<<"#" <<"#【數據結構課程設計（一）：內排序算法比較】#" <<"#" cout<<"#使用說明：運行程序，請輸入數據文

28、件名（a.txt,b.txt,c.txt均為無序數據，d.txt為完#" <<"#全正序數據，e.txt為完全逆序文件，均存放在當前目錄下），之后請按照用戶個人需求 #" <<"#選擇相應功能！ #" <<"#" <<" #"<<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;/數組存儲數據int data1000;/定義Data類對象Data<int> temp;/文件名string file; /讀取文件,從輸入的文件名中讀取數據，a.txt,b.txt,c.txt為隨機數據，e.txt為正序，e.txt為逆序cout<<endl<<" >>請輸入目標數據文件：" cin>>file; ifstream in(file.c_str()

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

32、;temp.bSort();break; /調用直接插入排序函數case 2:temp.copy(data);temp.iSort();break; /調用簡單選擇排序函數case 3:temp.copy(data);temp.sSort();break; /調用快速排序函數 case 4:temp.copy(data);temp.qqSort();break; /調用Shell排序函數 case 5:temp.copy(data);temp.shell();break; /調用堆排序函數 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、;" >>請選擇功能（輸入對應功能的序號）："cin>>opt1;cout<<"#"<<"#"<<"#"<<endl; ;#endif / CONTROL_H_INCLUDED/源文件main.cpp#include"data.h"#include"control.h"#include<iostream>using namespace std;12./主函數int main() Control

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

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

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