分塊查找課程設(shè)計(jì)

1、目 錄1實(shí)踐的目的與要求11.1 實(shí)踐目的11.2 課程設(shè)計(jì)要求12 分塊查找概述12.1 分塊查找簡(jiǎn)介12.2 基本思想12.3 分塊查找的優(yōu)點(diǎn)23分塊查找的步驟23.1 方法描述23.2 假設(shè)34流程圖45編碼46測(cè)試結(jié)果及運(yùn)行結(jié)果57總結(jié)78系統(tǒng)開發(fā)所用到的技術(shù)7參考文獻(xiàn)9附錄 全部代碼101實(shí)踐的目的與要求1.1 實(shí)踐目的采用分塊查找的方法查找指定的關(guān)鍵碼1.2 課程設(shè)計(jì)要求1） 可以循環(huán)查找，可以選擇退出；2） 分別采用順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)完成分塊查找，其中在順序存儲(chǔ)結(jié)果下，索引表的查找采用二分查找；3） 分別用函數(shù)完成索引表查找和塊中查找；4） 每一個(gè)函數(shù)要有必要的注釋，在課程設(shè)計(jì)論

2、文中有流程圖。2 分塊查找概述2.1 分塊查找簡(jiǎn)介分塊查找是折半查找和順序查找的一種改進(jìn)方法，折半查找雖然具有很好的性能，但其前提條件時(shí)線性表順序存儲(chǔ)而且按照關(guān)鍵碼排序，這一前提條件在結(jié)點(diǎn)樹很大且表元素動(dòng)態(tài)變化時(shí)是難以滿足的。而順序查找可以解決表元素動(dòng)態(tài)變化的要求，但查找效率很低。如果既要保持對(duì)線性表的查找具有較快的速度，又要能夠滿足表元素動(dòng)態(tài)變化的要求，則可采用分塊查找的方法。分塊查找的速度雖然不如折半查找算法，但比順序查找算法快得多，同時(shí)又不需要對(duì)全部節(jié)點(diǎn)進(jìn)行排序。當(dāng)節(jié)點(diǎn)很多且塊數(shù)很大時(shí)，對(duì)索引表可以采用折半查找，這樣能夠進(jìn)一步提高查找的速度。分塊查找由于只要求索引表是有序的，對(duì)塊內(nèi)節(jié)點(diǎn)沒(méi)

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

4、立一個(gè)索引表，把每塊中的最大關(guān)鍵碼值作為索引表的關(guān)鍵碼值，按塊的順序存放到一個(gè)輔助數(shù)組中，顯然這個(gè)輔助數(shù)組是按關(guān)鍵碼值費(fèi)遞減排序的。3） 查找時(shí)，首先在索引表中進(jìn)行查找，確定要找的節(jié)點(diǎn)所在的塊。由于索引表是排序的，因此，對(duì)索引表的查找可以采用順序查找或折半查找。然后，在相應(yīng)的塊中采用順序查找，即可找到對(duì)應(yīng)的節(jié)點(diǎn)。2.3 分塊查找的優(yōu)點(diǎn)在線性表中插入或刪除一個(gè)元素時(shí)，只要找到相應(yīng)的塊，然后在該塊內(nèi)進(jìn)行插入或刪除即可。由于塊內(nèi)元素個(gè)數(shù)相對(duì)較少，而且是任意存放的，所以插入或刪除比較容易，不需要移動(dòng)大量的元素。由于分塊查找的過(guò)程是分兩步進(jìn)行的，所以在查找表中查找一個(gè)待查找記錄的asl為：aslbs=a

5、slb+aslw其中：aslb是在索引表中查找記錄所在塊的平均查找長(zhǎng)度；aslw是在塊中查找待查找記錄的平均查找長(zhǎng)度。假設(shè)將長(zhǎng)度為n的查找表均勻地分為b塊，每塊含有s個(gè)記錄，即n/s，再假設(shè)查找表中查找每一個(gè)記錄的概率相等，則查找索引表的概率為1/b，在塊中查找待查找記錄的概率為1/s。1) 若采用順序查找確定待查找記錄所在塊，那么，分塊查找的平均查找長(zhǎng)度為：aslbs=aslb+aslw=所以分塊查找的平均查找長(zhǎng)度不僅與查找表的n有關(guān)，而且和每一塊中的記錄個(gè)數(shù)s有關(guān)。所以在給定了長(zhǎng)度為n的查找表的前提下，每塊中的記錄個(gè)數(shù)d是可變的。容易證明，當(dāng)s=時(shí)，aslbs =+1，值最小。2) 若采用

6、折半查找確定待查找記錄所在塊，那么，分塊查找的平均查找長(zhǎng)度為：aslbs=aslb+aslw=log2(b+1)+ = log2(+1)+由此可見，分塊查找的效率是介于順序查找和折半查找之間的。它比順序查找的執(zhí)行速度更要快，比折半查找的執(zhí)行速度要慢。3 分塊查找的步驟3.1 方法描述在查找表中的18個(gè)記錄分成三個(gè)子表（r1，r2，r6）,(r7，r8，.,r12),(r13，r14，,r18)，每個(gè)子表為一塊。首先用待查給定值k在索引表查找，然后再已確定的塊中進(jìn)行順序查找，當(dāng)查找表示有序表時(shí)，在塊中也可用二分查找。3.2 假設(shè)假設(shè)，如圖3.1中，如果給定值k=36，則先用k和索引表各關(guān)鍵字進(jìn)行

7、比較，因?yàn)?2k48，則關(guān)鍵字為36的記錄若果存在，必定在第二個(gè)子表塊中，然后從第二個(gè)字表塊的第一個(gè)記錄的位置序號(hào)7開始，按記錄順序查找，知道確定第10個(gè)記錄是要找的記錄為止，查找成功。又如當(dāng)k=26時(shí)，則仍在第二個(gè)字表中查找，自第7個(gè)記錄起按記錄順序查找至第12個(gè)記錄，每個(gè)記錄的關(guān)鍵字和k比較都不想等，則查找失敗。引索表關(guān)鍵字值224886塊起始地址171322111281020304244362548605574498655查找表123456789101112131415161718第一子表快第二子表塊第三子表塊圖3.1 分塊查找表結(jié)構(gòu)示意圖4 流程圖取索引表有效項(xiàng)數(shù)和索引表首址在索引表中

8、讀取數(shù)據(jù)塊的首址和最大值查找數(shù)據(jù)輸入關(guān)鍵字?jǐn)?shù)據(jù)自動(dòng)生成索引表賦值并輸出索引表循環(huán)尋找下一個(gè)反之跳出循環(huán)找到元素反之越界找不到元素（程序結(jié)束）#include#include #includeint table=22,11,12,8,10,20,30,42,44,36,25,48,60,55,74,49,86,55; /list_1.h int stelem;/關(guān)鍵字?jǐn)?shù)據(jù) int location; /關(guān)鍵字位置6 測(cè)試結(jié)果及運(yùn)行結(jié)果如圖6.1，運(yùn)行程序后的界面，按待查找的線性表給定的數(shù)字，任意輸出其中數(shù)字和enter鍵進(jìn)入下一頁(yè)面，或者退出。圖6.1 分塊查找的運(yùn)行界面圖6.2 待查給定值查詢

9、結(jié)果如圖6.2，測(cè)試輸入給定值“36“頁(yè)面正常顯示，程序自動(dòng)顯示出給定值所在位置及其比較次數(shù)，以繼續(xù)對(duì)頁(yè)面進(jìn)行操作，繼續(xù)測(cè)試代碼，邏輯。圖6.3 查找失敗的顯示框如圖6.3，測(cè)試輸入“26”頁(yè)面正常顯示，顯示查找失敗，說(shuō)明邏輯設(shè)計(jì)正確?？梢岳^續(xù)對(duì)頁(yè)面進(jìn)行操作，繼續(xù)測(cè)試代碼，邏輯。圖6.4 繼續(xù)給待查給定值查詢結(jié)果如圖6.4，測(cè)試輸入“44”頁(yè)面正常顯示，程序自動(dòng)顯示出給定值所在位置及其比較次數(shù)，說(shuō)明邏輯設(shè)計(jì)正確。還可以繼續(xù)對(duì)頁(yè)面進(jìn)行操作并繼續(xù)對(duì)其測(cè)試代碼，邏輯。調(diào)試階段最重要的還是耐性和細(xì)心。要有足夠的耐性去對(duì)待令人煩躁的錯(cuò)誤，一步步細(xì)心的調(diào)試，就會(huì)查出錯(cuò)誤的所在。我們進(jìn)行調(diào)試、測(cè)試是為了讓我

10、們的代碼、程序更加健壯，質(zhì)量更高。所以，我們不要畏懼報(bào)錯(cuò)，這是個(gè)學(xué)習(xí)進(jìn)步的過(guò)程。我們應(yīng)在錯(cuò)誤中，認(rèn)識(shí)到自己的不足與薄弱的知識(shí)點(diǎn)，提高自己的編寫代碼能力和改正錯(cuò)誤的能力。7 總結(jié)經(jīng)過(guò)這次課程設(shè)計(jì)，得到的收獲還是特別多的。它不僅讓我了解到做代碼的整個(gè)流程，還讓我在這個(gè)過(guò)程中學(xué)到了，很多過(guò)去不知道的東西，以及課本上所沒(méi)有講述的東西，同時(shí)也讓我深刻的認(rèn)識(shí)到我對(duì)知識(shí)的理解以及掌握程度還是極其有限的。通過(guò)這次課程設(shè)計(jì)，讓我了解到以下幾點(diǎn)：1、能力有待提高。2、態(tài)度不太端正。3、知識(shí)欠缺，課下盡可能地進(jìn)行知識(shí)積累4、整體意識(shí)不足，努力培養(yǎng)自身的整體意識(shí)個(gè)人的力量是薄弱的，我學(xué)會(huì)了咨詢別人，不再膽怯，不再保守

11、。在過(guò)程中和同學(xué)相互討論，詢問(wèn)老師，不斷進(jìn)步。也許，我們可以說(shuō)，編一個(gè)程僅僅是開始，調(diào)試和運(yùn)行相比之下更難。實(shí)踐中收獲的遠(yuǎn)比想象的多?？吹阶约和瓿闪怂蟮娜蝿?wù)，有一種無(wú)法用言語(yǔ)來(lái)形容的欣慰之感，這也是無(wú)法從學(xué)習(xí)書本知識(shí)中得到的。8 系統(tǒng)開發(fā)所用到的技術(shù)操作系統(tǒng)：windows7以上的操作系統(tǒng)開發(fā)軟件: devc+技術(shù)：功能模塊（函數(shù)）；結(jié)構(gòu)；查找；文件保存及讀取。模塊與函數(shù):功能模塊：求解較小問(wèn)題的算法與程序稱作“功能模塊”，各功能模塊可以先單獨(dú)設(shè)計(jì)，然后將求解所有的子問(wèn)題的模塊組合成求解原問(wèn)題的程序。將一個(gè)大問(wèn)題分解成多個(gè)解決小問(wèn)題的模塊的設(shè)計(jì)思想。由功能模塊組成程序的結(jié)構(gòu)：主控模塊和模塊

12、組成。模塊還可細(xì)分。自頂向下，逐步分解的設(shè)計(jì)思想函數(shù)：完成相對(duì)獨(dú)立功能和程序。模塊獨(dú)立：功能獨(dú)立的子功能模塊之間的關(guān)系簡(jiǎn)單，使用獨(dú)立變量，模塊規(guī)模適當(dāng)：分解模塊要注意層次：(1)對(duì)問(wèn)題抽象化(2)設(shè)計(jì)時(shí)細(xì)化設(shè)計(jì)原則：高內(nèi)聚，低耦合查找是生活中經(jīng)常用到的一個(gè)操作，如在英漢字典中查找某個(gè)英文單詞的中文解釋；在新華字典中查找某個(gè)漢字的讀音、含義；在對(duì)數(shù)表、平方根表中查找某個(gè)數(shù)的對(duì)數(shù)、平方根；郵遞員送信件要按收件人的地址確定位置等?？梢哉f(shuō)查找是為了得到某個(gè)信息而常進(jìn)行的工作。查找在計(jì)算機(jī)科學(xué)中定義為：在一些（有序的/無(wú)序的）數(shù)據(jù)元素中，通過(guò)一定的方法找出與給定關(guān)鍵字相同的數(shù)據(jù)元素的過(guò)程叫做查找。也就是

13、根據(jù)給定的某個(gè)值，在查找表中確定一個(gè)關(guān)鍵字等于給定值的記錄或數(shù)據(jù)元素。參考文獻(xiàn)1 劉覺(jué)夫,王更生等編著.c+程序設(shè)計(jì).北京：北京郵電大學(xué)出版社,2003.2 李素若,陳萬(wàn)華,游明坤編著.北京：中國(guó)水利水電出版社，2014.3 譚浩強(qiáng). c+面向?qū)ο蟪绦蛟O(shè)計(jì).北京：清華大學(xué)出版社，2006.4 劉玉英,張怡芳等.c+實(shí)驗(yàn)指導(dǎo)與課程設(shè)計(jì).人民郵電出版社,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

14、 searchtable/索引表結(jié)構(gòu)體 int stelem;/關(guān)鍵字?jǐn)?shù)據(jù) int location; /關(guān)鍵字位置; int main()cout待查找的線性表為 endl;int i;for(i=0;i18;i+)couttablei ;coutendl;cout正在生成靜態(tài)查找表.endl;/自動(dòng)生成索引表searchtable stable3;/索引表分為3個(gè)部分，表示分為3塊 stable0.location=1;/第一個(gè)子表序列由位置1開始stable1.location=7;/第二個(gè)子表序列由位置7開始stable2.location=13;/第三個(gè)子表序列由位置13開始int

15、max=table0;/將第一個(gè)元素值賦給maxfor(int j=0;jmax)max=tablej;stable0.stelem=max;/用循環(huán)使第一個(gè)子表的最大關(guān)鍵字的值賦給索引表第一個(gè)元素值max=table6;/將第七個(gè)元素的值賦給maxfor(j=6;jmax)max=tablej;stable1.stelem=max;/用循環(huán)使第二個(gè)子表的最大關(guān)鍵字的值賦給索引表第二個(gè)元素值max=table12;/將第十三個(gè)元素的值賦給maxfor(j=12;jmax)max=tablej;stable2.stelem=max;/利用循環(huán)將第三個(gè)子表的最大關(guān)鍵字的值賦給索引表第三個(gè)元素值 for(j=0;j3;j+) coutstablej.stelem stablej.location ; /輸出索引表 couta; /接受輸入的值賦給aint count=0; /計(jì)數(shù)器清零/在素引表中先查找 for(int i=0;istablei.stelem) /如果輸入的值比索引表最大關(guān)鍵字的值大conti