(完整word版)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告(實(shí)驗(yàn)十七)(word文檔良心出品)0001

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

2、 第二行輸入n，表示第一個(gè)示例有 n個(gè)數(shù)據(jù) 第三行輸入n個(gè)數(shù)據(jù)，都是正整數(shù)，數(shù)據(jù)之間用空格隔開 以此類推 輸出 每行輸出每個(gè)示例排序后，從小到大的結(jié)果 樣例輸入 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 三、實(shí)驗(yàn)步驟與過(guò)程: 希爾排序是一種按照增量排序的方法。其中增量值是小于n的正整數(shù)。 shell排序的基本思想是： 先取一個(gè)小于n的整數(shù)d1作為第一個(gè)增量，把文件的全部記錄分成d1個(gè)組。所有 距離為dl的倍數(shù)的記錄放在同一個(gè)

3、組中。 先在各組內(nèi)進(jìn)行直接插人排序； 然后，取第二 個(gè)增量d2d1重復(fù)上述的分組和排序，直至所取的增量dt=1(dtdt- 1 -d2d1)，即所 有記錄放在同一組中進(jìn)行直接插入排序?yàn)橹埂?源代碼： 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í)驗(yàn)結(jié)果及數(shù)據(jù)處理分析: A : 實(shí)驗(yàn)基本達(dá)到實(shí)驗(yàn)要求 五、實(shí)驗(yàn)結(jié)論與體會(huì)： 從這個(gè)實(shí)驗(yàn)中我學(xué)會(huì)使用哈希算法進(jìn)行排序，雖然實(shí)現(xiàn)起來(lái)沒(méi)有冒泡和 插入排序簡(jiǎn)單。但實(shí)驗(yàn)數(shù)據(jù)比較多時(shí)，比前兩者時(shí)間復(fù)雜度要小。因此能熟 練使用各種排序方法失衡重要的。 指導(dǎo)教師批閱意見(jiàn): 成績(jī)?cè)u(píng)定: 指導(dǎo)教師簽字： 年 月 日 備注