1、目 錄1實踐的目的與要求11.1 實踐目的11.2 課程設計要求12 分塊查找概述12.1 分塊查找簡介12.2 基本思想12.3 分塊查找的優點23分塊查找的步驟23.1 方法描述23.2 假設34流程圖45編碼46測試結果及運行結果57總結78系統開發所用到的技術7參考文獻9附錄 全部代碼101實踐的目的與要求1.1 實踐目的采用分塊查找的方法查找指定的關鍵碼1.2 課程設計要求1） 可以循環查找，可以選擇退出；2） 分別采用順序存儲和鏈式存儲完成分塊查找，其中在順序存儲結果下，索引表的查找采用二分查找；3） 分別用函數完成索引表查找和塊中查找；4） 每一個函數要有必要的注釋，在課程設計論

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

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

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

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

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

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

8、讀取數據塊的首址和最大值查找數據輸入關鍵字數據自動生成索引表賦值并輸出索引表循環尋找下一個反之跳出循環找到元素反之越界找不到元素（程序結束）#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;/關鍵字數據 int location; /關鍵字位置6 測試結果及運行結果如圖6.1，運行程序后的界面，按待查找的線性表給定的數字，任意輸出其中數字和enter鍵進入下一頁面，或者退出。圖6.1 分塊查找的運行界面圖6.2 待查給定值查詢

9、結果如圖6.2，測試輸入給定值“36“頁面正常顯示，程序自動顯示出給定值所在位置及其比較次數，以繼續對頁面進行操作，繼續測試代碼，邏輯。圖6.3 查找失敗的顯示框如圖6.3，測試輸入“26”頁面正常顯示，顯示查找失敗，說明邏輯設計正確。可以繼續對頁面進行操作，繼續測試代碼，邏輯。圖6.4 繼續給待查給定值查詢結果如圖6.4，測試輸入“44”頁面正常顯示，程序自動顯示出給定值所在位置及其比較次數，說明邏輯設計正確。還可以繼續對頁面進行操作并繼續對其測試代碼，邏輯。調試階段最重要的還是耐性和細心。要有足夠的耐性去對待令人煩躁的錯誤，一步步細心的調試，就會查出錯誤的所在。我們進行調試、測試是為了讓我

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

11、。在過程中和同學相互討論，詢問老師，不斷進步。也許，我們可以說，編一個程僅僅是開始，調試和運行相比之下更難。實踐中收獲的遠比想象的多。看到自己完成了所要求的任務，有一種無法用言語來形容的欣慰之感，這也是無法從學習書本知識中得到的。8 系統開發所用到的技術操作系統：windows7以上的操作系統開發軟件: devc+技術：功能模塊（函數）；結構；查找；文件保存及讀取。模塊與函數:功能模塊：求解較小問題的算法與程序稱作“功能模塊”，各功能模塊可以先單獨設計，然后將求解所有的子問題的模塊組合成求解原問題的程序。將一個大問題分解成多個解決小問題的模塊的設計思想。由功能模塊組成程序的結構：主控模塊和模塊

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

13、根據給定的某個值，在查找表中確定一個關鍵字等于給定值的記錄或數據元素。參考文獻1 劉覺夫,王更生等編著.c+程序設計.北京：北京郵電大學出版社,2003.2 李素若,陳萬華,游明坤編著.北京：中國水利水電出版社，2014.3 譚浩強. c+面向對象程序設計.北京：清華大學出版社，2006.4 劉玉英,張怡芳等.c+實驗指導與課程設計.人民郵電出版社,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分塊查找表結構示意圖struct

14、 searchtable/索引表結構體 int stelem;/關鍵字數據 int location; /關鍵字位置; int main()cout待查找的線性表為 endl;int i;for(i=0;i18;i+)couttablei ;coutendl;cout正在生成靜態查找表.endl;/自動生成索引表searchtable stable3;/索引表分為3個部分，表示分為3塊 stable0.location=1;/第一個子表序列由位置1開始stable1.location=7;/第二個子表序列由位置7開始stable2.location=13;/第三個子表序列由位置13開始int

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