【正文】 課程設計報告數(shù)據(jù)結構學院:軟件學院班級:11級二班學號:54110211姓名：劉海鯨輔導老師：劉亞波老師《數(shù)據(jù)結構》課程設計報告姓名：劉海鯨學號：54110211實驗室：座位號:提交日期：成績：指導教師：劉亞波問題解析（對問題的分析、解題思路與解題方法）：實驗目的為使我們學習完數(shù)據(jù)結構課程后，全面深入理解數(shù)據(jù)結構知識，掌握應用技巧，提高應用與分析能力，并培養(yǎng)學生綜合運用所學理論知識求解問題的能力和協(xié)作精神。解題思路(分析)：題目要求獨立編寫程序，完成對起泡排序，直接插入排序，簡單選擇排序，快速排序，希爾排序，堆排序6種內排序算法的比較，并且使用至少5組不同的輸入數(shù)據(jù)（記錄個數(shù)不小于1000個，其中包括完全正序，完全逆序和無序情況）進行排序，比較各組記錄與各種排序方法在關鍵字比較次數(shù)和關鍵字移動次數(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ù)；，（模板類），包括主要的排序函數(shù)和數(shù)據(jù)成員，來完成界面控制，數(shù)據(jù)文件讀取和排序功能的實現(xiàn)，（）的調用來完成整個程序。最后運行程序來完成對比較指標的統(tǒng)計并進行分析，對得出結果進行解釋。任務分工：本實驗由本人獨立完成。進度安排：為第一次實驗課將6個內排序算法完成并調試成功，周末之前完成界面控制并對排序結果進行分析，第二次實驗之前完成課程設計報告，第二次試驗對程序結果進行最后檢查并提交實驗報告。數(shù)據(jù)結構選擇（包括改進或給出）：使用數(shù)組作為本實驗基本的數(shù)據(jù)結構，數(shù)據(jù)類中包含有數(shù)組的頭指針head，在初始化時動態(tài)申請數(shù)組空間，此外還有count（整型）用于記錄數(shù)組個數(shù),同時可以對數(shù)組進行6種內排序及顯示數(shù)組元素的操作。算法設計：借助課本與網(wǎng)絡，使用C++編寫算法，詳細請看后面程序清單。編程與程序清單：1.//2.//文件數(shù)據(jù)類Data定義3. //起泡排序（升序）4. //直接插入排序（升序）5. //簡單選擇排序（升序）6. //快速排序(升序)7.//快速排序的遞歸函數(shù)8.//希爾排序 （升序）9.//插入排序（升序）10. //堆排序（升序）11.//控制類12. //功能選擇13.//主函數(shù)1.// 1.//ifndef DATA_H_INCLUDEDdefine DATA_H_INCLUDEDincludectimeincludeiostreamusing namespace std。2.//文件數(shù)據(jù)類Data定義templateclass Tclass Data{ private: T *head。 //數(shù)據(jù)數(shù)組指針，用于動態(tài)申請數(shù)組空間 int count。 //數(shù)組大小 public: //構造函數(shù)，使指針為空 Data(){head=NULL。} //用已有數(shù)組構造數(shù)組元素，當前程序使用該函數(shù)來構造數(shù)據(jù)元素 void copy(T *h,int c=1000) { if(head!=NULL) delete[] head。 head=h。count=c。 head=new T[count]。 for(int i=0。icount。i++) { head[i]=h[i]。 } } //手動輸入各元素，當前程序未使用，調試程序時使用！ void set() { if(head!=NULL) delete[] head。 cout請輸入數(shù)據(jù)個數(shù)：endl。 cincount。 head=new T[count]。 cout請輸入數(shù)據(jù)：endl。 for(int i=0。icount。i++) { cinhead[i]。 } } //析構函數(shù)，回收空間 ~Data(){delete[] head。}3. //起泡排序（升序） void bSort() { if(isEmpty()){cout 文件中無記錄，無法排序！endl。return。} int pareTime=0。 //關鍵詞比較次數(shù) int moveTime=0。 //關鍵詞移動次數(shù) int bound=count。 int start,finish。 //記錄程序運行時間 T temp。 cout 正在排序...endl。 start=clock()。 //記錄初始時間 //算法主體 while(bound!=0) { int t=0。 for(int i=0。ibound1。i++) { pareTime++。 if(head[i]head[i+1]) { temp=head[i]。 head[i]=head[i+1]。 head[i+1]=temp。 t=i+1。 moveTime+=3。 //記錄交換一次移動次數(shù)加3 } } bound=t。 } finish=clock()。 cout 排序后結果為：endl。 display()。 //輸出排序后序列 coutendl *endl *關鍵詞比較次數(shù)：pareTimeendl *記錄移動次數(shù)：moveTimeendl *排序執(zhí)行時間：finishstartms