分塊查找課程設(shè)計講解

1、目錄1 實踐的目的與要求 . 11.1 實踐目的 . 11.2 課程設(shè)計要求 . 12 分塊查找概述 . 12.1 分塊查找簡介 . 12.2 基本思想 . 12.3 分塊查找的優(yōu)點 . 23 分塊查找的步驟 . 23.1 方法描述 . 23.2 假設(shè) . 34 流程圖 . 45 編碼 . 46 測試結(jié)果及運行結(jié)果 . 57 總結(jié) . 78 系統(tǒng)開發(fā)所用到的技術(shù) . 7參考文獻 . 9附錄 全部代碼 .1.0.1實踐的目的與要求1.1實踐目的采用分塊查找的方法查找指定的關(guān)鍵碼1.2課程設(shè)計要求1） 可以循環(huán)查找，可以選擇退出；2） 分別采用順序存儲和鏈式存儲完成分塊查找，其中在順序存儲結(jié)果下，

2、索引表的查找采用二分查找；3） 分別用函數(shù)完成索引表查找和塊中查找；4） 每一個函數(shù)要有必要的注釋，在課程設(shè)計論文中有流程圖。2分塊查找概述2.1分塊查找簡介分塊查找是折半查找和順序查找的一種改進方法，折半查找雖然具有很好的性能， 但其前提條件時線性表順序存儲而且按照關(guān)鍵碼排序，這一前提條件在結(jié)點樹很大且表 元素動態(tài)變化時是難以滿足的。而順序查找可以解決表元素動態(tài)變化的要求，但查找效 率很低。如果既要保持對線性表的查找具有較快的速度，又要能夠滿足表元素動態(tài)變化 的要求，則可采用分塊查找的方法。分塊查找的速度雖然不如折半查找算法，但比順序 查找算法快得多，同時又不需要對全部節(jié)點進行排序。當(dāng)節(jié)點很

3、多且塊數(shù)很大時，對索 引表可以采用折半查找，這樣能夠進一步提高查找的速度。分塊查找由于只要求索引表是有序的，對塊內(nèi)節(jié)點沒有排序要求，因此特別適合于 節(jié)點動態(tài)變化的情況。當(dāng)增加或減少節(jié)以及節(jié)點的關(guān)鍵碼改變時，只需將該節(jié)點調(diào)整到 所在的塊即可。在空間復(fù)雜性上，分塊查找的主要代價是增加了一個輔助數(shù)組。需要注意的是，當(dāng)節(jié)點變化很頻繁時，可能會導(dǎo)致塊與塊之間的節(jié)點數(shù)相差很大， 沒寫快具有很多節(jié)點，而另一些塊則可能只有很少節(jié)點，這將會導(dǎo)致查找效率的下降。2.2基本思想1）分塊查找要求把一個大的線性表分解成若干塊，每塊中的節(jié)點可以任意存放， 但塊與塊之間必須排序。假設(shè)是按關(guān)鍵碼值非遞減的，那么這種塊與塊之間

4、必 須滿足已排序要求，實際上就是對于任意的i，第i塊中的所有節(jié)點的關(guān)鍵碼值 都必須小于第i+1塊中的所有節(jié)點的關(guān)鍵碼值。2） 建立一個索引表，把每塊中的最大關(guān)鍵碼值作為索引表的關(guān)鍵碼值，按塊的順序存放到一個輔助數(shù)組中，顯然這個輔助數(shù)組是按關(guān)鍵碼值費遞減排序的3）查找時，首先在索引表中進行查找，確定要找的節(jié)點所在的塊。由于索引表是 排序的，因此，對索引表的查找可以采用順序查找或折半查找。然后，在相應(yīng) 的塊中采用順序查找，即可找到對應(yīng)的節(jié)點。2.3分塊查找的優(yōu)點在線性表中插入或刪除一個元素時，只要找到相應(yīng)的塊，然后在該塊內(nèi)進行插入或 刪除即可。由于塊內(nèi)元素個數(shù)相對較少，而且是任意存放的，所以插入或

5、刪除比較容易, 不需要移動大量的元素。由于分塊查找的過程是分兩步進行的， 所以在查找表中查找一個待查找記錄的 ASL為：ASL bs=ASL b+ASL w其中：ASLb是在索引表中查找記錄所在塊的平均查找長度；ASLw是在塊中查找待查找記錄的平均查找長度。假設(shè)將長度為n的查找表均勻地分為b塊，每塊含有s個記錄，即n/s，再假設(shè) 查找表中查找每一個記錄的概率相等，則查找索引表的概率為 1/b，在塊中查找待查找 記錄的概率為1/s。1）若采用順序查找確定待查找記錄所在塊，那么，分塊查找的平均查找長度為：b 1s 1b 亠1 s 亠11 nASLbs=ASLb+ASLw= - i j 二一-（ s

6、） 1i bjjS222 s所以分塊查找的平均查找長度不僅與查找表的 n有關(guān)，而且和每一塊中的記錄個數(shù) s有關(guān)。所以在給定了長度為n的查找表的前提下，每塊中的記錄個數(shù) d是可變的。容 易證明，當(dāng)s= n時，ASLbs =】n+1，值最小。2）若采用折半查找確定待查找記錄所在塊，那么，分塊查找的平均查找長度為：s +1nsASLbs=ASLb+ASLw=log 2（b+1）+= log2（ +1）+2s2由此可見，分塊查找的效率是介于順序查找和折半查找之間的。它比順序查找的執(zhí) 行速度更要快，比折半查找的執(zhí)行速度要慢。3分塊查找的步驟3.1方法描述在查找表中的18個記錄分成三個子表（R1, R2,

7、，R6） ,（R7, R8, .,R12）,（R13, R14,R18）,每個子表為一塊。首先用待查給定值 K在索引表查找，然后再已確定的塊中進行順序查找，當(dāng)查找表示有序表時，在塊中也可用二分查找。3.2假設(shè)假設(shè)，如圖3.1中，如果給定值K=36，貝U先用K和索引表各關(guān)鍵字進行比較，因 為22K48，則關(guān)鍵字為36的記錄若果存在，必定在第二個子表塊中，然后從第二個 字表塊的第一個記錄的位置序號 7開始，按記錄順序查找，知道確定第 10個記錄是要 找的記錄為止，查找成功。又如當(dāng) K=26時，則仍在第二個字表中查找，自第 7個記錄 起按記錄順序查找至第12個記錄，每個記錄的關(guān)鍵字和K比較都不想等，

8、則查找失敗。關(guān)鍵字值224886塊起始地址1713圖3.1分塊查找表結(jié)構(gòu)示意圖22111281020304244362548605574498655123456789101112131415161718第一子表快第二子表塊第三子表塊查找表4流程圖5編碼函數(shù)流程：struct searchtable/索引表結(jié)構(gòu)體 創(chuàng)建索引表（程序開始）一 輸入關(guān)鍵字數(shù)據(jù)一 自動生成索引表一賦值并輸出索引表一 循環(huán)尋找下一個反之跳出循環(huán)一 找到元素反之越界找不到元素（程序結(jié)束）#i nclude#i nclude#in cludeinttable=22,11,12,8,10,20,30,42,44,36,25,4

9、8,60,55,74,49,86,55;list_1.hint stelem;/關(guān)鍵字數(shù)據(jù)in t locati on;/關(guān)鍵字位置6測試結(jié)果及運行結(jié)果如圖6.1，運行程序后的界面，按待查找的線性表給定的數(shù)字，任意輸出其中數(shù)字 和Enter鍵進入下一頁面，或者退出。唏苣我的線性表為22 11 12 g 10 20 30 42 44 3& 25 4S 60 55 74 対 B6 5& 王在生成靜査査找表22 1 48 7 86 13Input 自 nwrbr you want to starch：圖6.1 分塊查找的運行界面圖6.4繼續(xù)給待查給定值查詢結(jié)果fl待童拱的線性表為22 11 12 R

10、 10 20 3D 42 44 36 25 4 60 55 74 45 86 S& 正在生成蘇態(tài)蠻找表.一.22 1 4S 7 36 L2Input- a numtier yciu want to search： 36箱在表中的怕胃為：1?？⒌囊聰?shù)為6Input nujrfcer you wint tu sear ch-：圖6.2待查給定值查詢結(jié)果如圖6.2，測試輸入給定值“ 36 “頁面正常顯示，程序自動顯示出給定值所在位置 及其比較次數(shù)，以繼續(xù)對頁面進行操作，繼續(xù)測試代碼，邏輯GKUtersVAdminisJlxateFfXDfl-s-lctopDebuVafiKE-sw*待查找的線性表為

11、22 11 13 3 10 20 30 42 44 跖 25 48 60 55 74 49 貓 55正在生成靜態(tài)査找表.22 1 4S 7 S6 13Input a iicunbEF 孑口口 am to search：36 仍在表中的檢置為：10 比較的祝數(shù)為* 6Iqput ayciii want to saarch：26查找失敗！Input a nijinter you wanl to search：圖6.3 查找失敗的顯示框如圖6.3，測試輸入“ 26”頁面正常顯示，顯示查找失敗，說明邏輯設(shè)計正確?？?以繼續(xù)對頁面進行操作，繼續(xù)測試代碼，邏輯。H3 *CAUisiPn.Administr

12、afcorD,ktopDefcugr|fct.eMe X待査找的線性表為亠22 11 12 8 10 20 30 42 44 36 25 48 60 55 74 49 86 55 正在生成靜態(tài)查找表22 1 4S 7 S6 13Input 電 nurabsr you want to表申的檢為:10比轉(zhuǎn)的初:數(shù)為，6Input a nciiiir yciii want to search：26 查找失??！Input 3 number you want to ssnrch;444表中的:9比轉(zhuǎn)的衣數(shù)為5Input a nunflzer yciti want to search：如圖 6.4 ，測試

13、輸入“ 44”頁面正常顯示，程序自動顯示出給定值所在位置及其比較次數(shù)，說明邏輯設(shè)計正確。還可以繼續(xù)對頁面進行操作并繼續(xù)對其測試代碼，邏輯。 調(diào)試階段最重要的還是耐性和細心。要有足夠的耐性去對待令人煩躁的錯誤，一步 步細心的調(diào)試，就會查出錯誤的所在。我們進行調(diào)試、測試是為了讓我們的代碼、程序 更加健壯，質(zhì)量更高。所以，我們不要畏懼報錯，這是個學(xué)習(xí)進步的過程。我們應(yīng)在錯 誤中，認識到自己的不足與薄弱的知識點， 提高自己的編寫代碼能力和改正錯誤的能力。7 總結(jié)經(jīng)過這次課程設(shè)計，得到的收獲還是特別多的。它不僅讓我了解到做代碼的整個流 程，還讓我在這個過程中學(xué)到了，很多過去不知道的東西，以及課本上所沒有

14、講述的東 西，同時也讓我深刻的認識到我對知識的理解以及掌握程度還是極其有限的。通過這次課程設(shè)計，讓我了解到以下幾點：1、能力有待提高。2、態(tài)度不太端正。3、知識欠缺，課下盡可能地進行知識積累4、整體意識不足，努力培養(yǎng)自身的整體意識個人的力量是薄弱的，我學(xué)會了咨詢別人，不再膽怯，不再保守。 在過程中 和同學(xué)相互討論，詢問老師，不斷進步。也許，我們可以說，編一個程僅僅是開始，調(diào)試和運行相比之下更難。實踐中收獲 的遠比想象的多?？吹阶约和瓿闪怂蟮娜蝿?wù)，有一種無法用言語來形容的欣慰之感，這也是無法 從學(xué)習(xí)書本知識中得到的。8 系統(tǒng)開發(fā)所用到的技術(shù)操作系統(tǒng)：Windows7以上的操作系統(tǒng)開發(fā)軟件 :

15、 Devc+技術(shù)：功能模塊（函數(shù)） ；結(jié)構(gòu)；查找；文件保存及讀取。模塊與函數(shù) : 功能模塊：求解較小問題的算法與程序稱作“功能模塊”，各功能模 塊可以先單獨設(shè)計，然后將求解所有的子問題的模塊組合成求解原問題的程序。將一個 大問題分解成多個解決小問題的模塊的設(shè)計思想。由功能模塊組成程序的結(jié)構(gòu)：主控模 塊和模塊組成。模塊還可細分。自頂向下，逐步分解的設(shè)計思想函數(shù)：完成相對獨立功能和程序。模塊獨立： 功能獨立的子功能模塊之間的關(guān)系簡單， 使用獨立變量， 模塊規(guī)模適當(dāng)： 分解模塊要注意層次：(1)對問題抽象化(2)設(shè)計時細化 設(shè)計原則：高內(nèi)聚，低耦合 查找是生活中經(jīng)常用到的一個操作，如在英漢字典中查找

16、某個英文單詞的中文解 釋；在新華字典中查找某個漢字的讀音、含義；在對數(shù)表、平方根表中查找某個數(shù)的對 數(shù)、平方根；郵遞員送信件要按收件人的地址確定位置等?？梢哉f查找是為了得到某個 信息而常進行的工作。查找在計算機科學(xué)中定義為：在一些(有序的 / 無序的)數(shù)據(jù)元素中，通過一定的 方法找出與給定關(guān)鍵字相同的數(shù)據(jù)元素的過程叫做查找。也就是根據(jù)給定的某個值，在 查找表中確定一個關(guān)鍵字等于給定值的記錄或數(shù)據(jù)元素。參考文獻1劉覺夫，王更生等編著.C+程序設(shè)計北京：北京郵電大學(xué)出版社，20032李素若,陳萬華,游明坤編著 . 北京：中國水利水電出版社， 2014.3譚浩強.C+面向?qū)ο蟪绦蛟O(shè)計北京：清華大學(xué)出

17、版社，2006.4劉玉英，張怡芳等.C+實驗指導(dǎo)與課程設(shè)計人民郵電出版社，2007.附錄 全部代碼#include#include#includeint table=22,11,12,8,10,20,30,42,44,36,25,48,60,55,74,49,86,55;/書本8.2分塊查找表結(jié)構(gòu)示意圖struct searchtable/索引表結(jié)構(gòu)體int stelem;/關(guān)鍵字數(shù)據(jù)int location;/關(guān)鍵字位置;int main()cout待查找的線性表為 endl;int i;for(i=0;i18;i+)couttablei ;coutendl;coutvv正在生成靜態(tài)查找表e

18、ndl;/自動生成索引表searchtable stable3;/索引表分為 3個部分，表示分為 3塊stable0.location=1;/第一個子表序列由位置 1開始stable1.location=7;/第二個子表序列由位置 7開始stable2.location=13;/第三個子表序列由位置 13開始int max=table0;/將第一個元素值賦給 max for(int j=0;jmax) max=tablej; stable0.stelem=max; /用循環(huán)使第一個子表的最大關(guān)鍵字的值賦給索引表第一個元素值max=table6;/將第七個元素的值賦給 max for(j=6;jmax) max=tablej; stable1.stelem=max; /用循環(huán)使第二個子表的最大關(guān)鍵字的值賦給索引表第二個元素值max=table12;/將第十三個元素的值賦給 max for(j=12;jmax) max=tablej; stable2.stelem=max; /利用循環(huán)將第三個子表的最大關(guān)鍵字的值賦給索引表第三個元素值 for(j=0;j3;j+)coutstablej.stelem stablej.location ;/輸出索引表 couta;/接受輸入的值賦給 aint count=0;/計數(shù)器清零/在素引表中先查找for(in