(完整word版)數(shù)據(jù)結構實驗報告(實驗十七)(word文檔良心出品)0001

1、深圳 大學實 驗報告 課程名稱： 數(shù)據(jù)結構實驗與課程設計 實驗項目名稱： 希爾排序 學院： 計算機與軟件學院 專業(yè)： 指導教師： 蔡平 報告人：文成 學號：2011150259班級： 5 實驗時間： 2012-12-17 實驗報告提交時間： 2012-12-24 教務部制 一、實驗目的與要求： 目的： 1掌握哈希排序算法原理 2掌握哈希排序算法的實現(xiàn)方法 要求： 1.熟悉C+語言編程 2熟練編程實現(xiàn)哈希算法 、實驗內(nèi)容: 問題A:數(shù)據(jù)結構實驗-希爾排序 題目描述 給出一個數(shù)據(jù)序列，使用希爾排序算法進行從小到大的排序 間隔gap使用序列長度循環(huán)除 2直到1 輸入 第一行輸入t，表示有t個測試示例

2、 第二行輸入n，表示第一個示例有 n個數(shù)據(jù) 第三行輸入n個數(shù)據(jù)，都是正整數(shù)，數(shù)據(jù)之間用空格隔開 以此類推 輸出 每行輸出每個示例排序后，從小到大的結果 樣例輸入 2 6 111 22 6 444 333 55 8 77 555 33 1 444 77 666 2222 樣例輸出 6 22 55 111 333 444 1 33 77 77 444 555 666 2222 三、實驗步驟與過程: 希爾排序是一種按照增量排序的方法。其中增量值是小于n的正整數(shù)。 shell排序的基本思想是： 先取一個小于n的整數(shù)d1作為第一個增量，把文件的全部記錄分成d1個組。所有 距離為dl的倍數(shù)的記錄放在同一個

3、組中。 先在各組內(nèi)進行直接插人排序； 然后，取第二 個增量d2d1重復上述的分組和排序，直至所取的增量dt=1(dtdt- 1 -d2d1)，即所 有記錄放在同一組中進行直接插入排序為止。 源代碼： A : #in clude using n amespace std; int ShellSort(i nt array,i nt n) int gap,i,i; for(gap=n /2;gap=1;gap-) for(i=0;igap; i+) for(j = i+gap; jn; j=j+gap) if(arrayj=0 k = k-gap; arrayk+gap = temp; retur

4、n 0; int mai n() int test nu m,i,j; cin test num; for(i=0;itest nu m;i+) int num; cinnum; int *array=new intnu m; for(j=0;j arrayj; ShellSort(arra y,nu m); for(j=0;j nu m;j+) coutarrayj; coute ndl; return 0; 四、實驗結果及數(shù)據(jù)處理分析: A : 實驗基本達到實驗要求 五、實驗結論與體會： 從這個實驗中我學會使用哈希算法進行排序，雖然實現(xiàn)起來沒有冒泡和 插入排序簡單。但實驗數(shù)據(jù)比較多時，比前兩者時間復雜度要小。因此能熟 練使用各種排序方法失衡重要的。 指導教師批閱意見: 成績評定: 指導教師簽字： 年 月 日 備注