武漢理工數(shù)據(jù)結(jié)構(gòu)課設(shè)

1、1問題描述 2設(shè)計(jì)2. 1存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)2. 2主要算法設(shè)計(jì)2. 3測(cè)試用例設(shè)計(jì) 3調(diào)試報(bào)告3. 1調(diào)試過程中遇到的問題的解決3. 2對(duì)設(shè)計(jì)和編碼的討論和分析 4經(jīng)驗(yàn)和體會(huì)4.1收獲4. 2對(duì)算法改進(jìn)的設(shè)想 5附源程序清單和運(yùn)行結(jié)果5. 1源程序代碼125. 2運(yùn)行結(jié)果與分析參考文獻(xiàn)索引順序查找1問題描述這個(gè)課程設(shè)計(jì)的題目是“索引順序查找”，其實(shí)就是分塊查找是介于順序查 找和折半查找之間的查找方法。將數(shù)據(jù)分別放入幾個(gè)塊中，其中塊之間是有序的，即前邊的最大數(shù)小于后邊的最小數(shù)，塊內(nèi)數(shù)據(jù)可以是無(wú)序的。編寫出一個(gè) 能進(jìn)行索引順序查找的程序，要求能自動(dòng)建立索引表；對(duì)任意待查找的關(guān)鍵字, 若查找成功，給出其

2、關(guān)鍵字比較次數(shù)；測(cè)試用例自己設(shè)計(jì)。我的設(shè)計(jì)思想是建立一個(gè)數(shù)組用來(lái)存放數(shù)據(jù)，所存放的數(shù)據(jù)之間是按塊有 序的，所以設(shè)計(jì)之前要想好自己怎樣分塊。每個(gè)數(shù)據(jù)都只有自己的地址address,每塊內(nèi)都有一個(gè)最大值max。比較關(guān)鍵字key時(shí)先比較最大值，符合條件后再 進(jìn)入塊內(nèi)比較。不管所比較的關(guān)鍵字在比較關(guān)鍵字時(shí)是不是恰好和最大值相等, 都要進(jìn)入塊再重新比較，并且從相應(yīng)塊的首地址開始比較，然后向后依次比較。 從比較一開始，就會(huì)有一個(gè)計(jì)數(shù)關(guān)鍵字count開始計(jì)數(shù)。因此，分塊查找過程需分兩步進(jìn)行。先確定待查記錄所在的塊（子表），然后在塊 中順序查找。假設(shè)給定值key=38,則先將key依次和索引表中各最大關(guān)鍵字進(jìn)

3、行 比較，因?yàn)?2<key<48,則關(guān)鍵字為38的記錄若存在，必定在第二個(gè)子表中， 由于同一索引項(xiàng)中的指針指示第二個(gè)子表中的第一個(gè)記錄是表中第7個(gè)記錄，則 自第7個(gè)記錄起進(jìn)行順序查找，直到l.data10=key為止。假如此子表中沒有關(guān)鍵 字等于key的記錄（例如：key=29時(shí)自第7個(gè)記錄起至第12個(gè)記錄的關(guān)鍵字和key 比較都不等），則查找不成功。索引順序查找的性能分析：分塊查找的平均查找長(zhǎng)度為:其中，d為查找索引表確定所在塊的平均查找長(zhǎng)度zir為在塊中查找元素的平均查找長(zhǎng)度。若用順序查找的方法確定所在的塊，貝!hv jsbi o ihi£a & o若用折半查

4、找確定所在的塊，貝!has%= £»+ =+丄辦=扇叫a些罟s u2£2設(shè)計(jì)2.1存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)這個(gè)程序首先用到了2個(gè)結(jié)構(gòu)體，typedef struct datatype datamaxsize; int length; list;> typedef structf datatype max;int address;index> 分另u表 示定義索引表、定義塊表。其中key表示待查找的索引值；max表示塊內(nèi)索引的 最大值，即為最大關(guān)鍵字，address為塊內(nèi)第一個(gè)索引的地址；datasize表示數(shù)組所能容納的最多元素，length表示表內(nèi)元素的個(gè)數(shù)。在

5、創(chuàng)建塊表時(shí)，int intput (list *l, index *index),定義了l為list的引用， index為index的數(shù)據(jù)成員。先將表的長(zhǎng)度l-length定義為0,每輸入一個(gè)數(shù)，表長(zhǎng) 度隨之加1,然后輸入要建的塊數(shù)，并且輸入每個(gè)塊的首地址。指明每個(gè)塊的最大 值，以便在下一個(gè)函數(shù)indexsearch中直接將key與最大值進(jìn)行比較。在查找時(shí)，我定義了 函數(shù)int indexsearch(list ljndex index9int lendatatypekey),現(xiàn)將關(guān)鍵字key與每一塊的最大<indexi.key進(jìn)行比較，從第一塊開始，依次向 后比較，當(dāng)計(jì)數(shù)器i超過塊的個(gè)

6、數(shù)時(shí)，返回1;當(dāng)符合條件ivlen&&key>indeximax時(shí), 進(jìn)入塊進(jìn)行比較。從當(dāng)前塊的首地址元素開始依次向后比較。無(wú)論是比較最大值還是比 較塊中元素，比較次數(shù)計(jì)數(shù)器count直在計(jì)數(shù)。當(dāng)存在塊中元素與關(guān)鍵字相等時(shí)，輸 出關(guān)鍵字的比較次數(shù)conn併且返回當(dāng)前元素的地址addresso若當(dāng)前塊中沒有元素與關(guān) 鍵字相等，返回12.2主要算法設(shè)計(jì)為了體現(xiàn)程序的簡(jiǎn)單與高效，我將程序最終到造成了只用兩個(gè)函數(shù)就完成了 主要功能的實(shí)現(xiàn)，在函數(shù)index中輸入所有數(shù)據(jù)元素與地址和要分的塊數(shù)，以及 每一塊的最大值。在函數(shù)indexsearch中實(shí)現(xiàn)了關(guān)鍵字的比較，其中包括關(guān)鍵字 與

7、最大元素的比較和響應(yīng)塊中每個(gè)元素的比較，直到找到相應(yīng)元素為止。而且 比較次數(shù)與相應(yīng)元素的地址也在這個(gè)函數(shù)中體現(xiàn)出來(lái)。根據(jù)索引順序査找的原理，得知分塊查找需兩步進(jìn)行，要先確定待查所在的 塊(子表)，然后在塊中順序查找，所以至少需要兩個(gè)查找函數(shù)。查找塊函數(shù)可 用折半查找或者順序查找。一般情況下進(jìn)行分塊查找，可以將長(zhǎng)度為n的表均勻地分成b塊，每塊含有 s個(gè)記錄，即b= rn/s ；假定表中每個(gè)記錄的查找概率相等，則每塊查找的概率 為1/b,塊中每個(gè)記錄的查找概率為1/so若用順序查找確定所在塊，則分塊查找的平均查找長(zhǎng)度為aslbs=l/2(n/s+s)+lo可見，此時(shí)的平均查找長(zhǎng)度不僅和表 長(zhǎng)n有關(guān)

8、，而且和每一塊中的記錄個(gè)數(shù)s有關(guān)。在給定n的前提下，s是可以選擇的。容易證明，當(dāng)s取徧時(shí)，ass取小值奶+ 1。這個(gè)值比順序查找有了很大改進(jìn)，但遠(yuǎn)不及折半查找。若用折半查找確定所在塊，則分塊查找的平均 查找長(zhǎng)度 aslbs 約為 log2(n/s+l)+s/2o雖然通過平均查找長(zhǎng)度的比較，對(duì)塊的查找用折半查找較先進(jìn)，但我這里的 int indexsearch()函數(shù)還是用的一般人較易理解的順序查找。這里用到的是順序 查找，若key值小于或等于第一塊的最大關(guān)鍵字indexl.max,則key值可能在 第一塊中；若key值大于最后一塊的最大關(guān)鍵字indexlen.max,則key值必定 不在任何一

9、個(gè)塊中，查找失??；若key值大于前一塊的最大關(guān)鍵字，小于或等 于后一塊的最大關(guān)鍵字，則key值肯能在后一塊中。這樣就能確定key值所在 的塊了。通過我的思考，我覺得順序查找較簡(jiǎn)單些，所以在程序中就用了順序 查找。再者是在塊中查找關(guān)鍵字用到的int indexsearch ()函數(shù)，由于塊中的元素是 無(wú)序排列，所以只能用順序查找。l->data是通過所查到的塊中的元素建立的 數(shù)組，再通過把每個(gè)塊中的元素依次和key值做比較，就可查到是否存在key 這個(gè)元素。若從該塊的第一個(gè)元素查到最后一個(gè)元素都沒有找到與key相等的 值，則查找失敗，這個(gè)是根據(jù)該塊的長(zhǎng)度(塊中元素的個(gè)數(shù))控制的。若找到 與

10、kty相等的值，就返回該元素所在的位置。2.3測(cè)試用例設(shè)計(jì)1 對(duì)創(chuàng)建表的函數(shù)int input(),通過手動(dòng)輸入所有元素(按塊有序進(jìn)行輸入，以0 為結(jié)束輸入的標(biāo)志)和塊數(shù)，如輸入一些簡(jiǎn)單易操作的數(shù)32 16549870 2然后輸入每塊的首地址以及每塊的最大值，這樣就將塊確定了下來(lái)。如：輸入要建立的3個(gè)塊表，每個(gè)塊表的最大關(guān)鍵字和首地址分別是：3, 0； 6, 3； 9, 6。得到的結(jié)果為:index0.max=3 indexleinax=6 index2<max=9index o.address=o index l.address=3 index 2>address=63 對(duì)查找關(guān)

11、字所在的塊以及對(duì)比找到確切位置的函數(shù)int indexsearch()通過對(duì)要查找的key值分別與每一塊的最大關(guān)鍵字進(jìn)行比較，得出key值可 能位于哪一塊中。如i：當(dāng)key=5時(shí)，先與第一塊最大關(guān)鍵字進(jìn)行比較，key>index0.max=3, 再與第二塊最頭關(guān)鍵字進(jìn)行比較，key<index2.max=6,所以5可能在第二塊中, 返回第二塊的首地址；然后比較key<l.datao,所以再與下一個(gè)元素比較，有 key=l.datal,所以可以確定在第二塊第二個(gè)位置，比較次數(shù)為4次。當(dāng)key=12時(shí)，先與第一塊最大關(guān)鍵字進(jìn)行比較，key>index0.max=3；再 進(jìn)行

12、比較，key>index2.max=9,所以12不可能位于這些塊表中，查找失敗, 則不再需要進(jìn)入塊中進(jìn)行比較。與第二塊最大關(guān)鍵字進(jìn)行比較,key>indexl.max=6；再與第三塊最大關(guān)鍵字3調(diào)試報(bào)告3.1調(diào)試過程中遇到的問題的解決1 對(duì)存放元素的數(shù)組的大小定義一開始過小，導(dǎo)致我后來(lái)存放的元素超出了數(shù)組 空間，產(chǎn)生溢出，于是我將數(shù)組大小改為100,問題得以解決2對(duì)創(chuàng)建索引順序表的函數(shù)int input()這個(gè)函數(shù)還算簡(jiǎn)單，在此函數(shù)中我同時(shí)實(shí)現(xiàn)了表中元素的輸入，每塊的首地 址以及塊內(nèi)最大值，當(dāng)時(shí)設(shè)計(jì)的時(shí)候沒有使表的首地址和塊的首地址做到統(tǒng)一, 在建立完函數(shù)時(shí)我將它們的首地址統(tǒng)一設(shè)置

13、成0,這樣元素的名義地址為i,實(shí) 際地址為i+1.3對(duì)于搜索函數(shù)indexsearch出現(xiàn)的錯(cuò)誤雖然不多，但是很嚴(yán)重，而且在當(dāng)時(shí)按 我當(dāng)?shù)某踉O(shè)計(jì)思路來(lái)改很難改。從一開始設(shè)計(jì)搜索函數(shù)時(shí)，我考慮的太多，想 實(shí)現(xiàn)這個(gè)函數(shù)的“智能化”：在比較最大值時(shí)，我考慮了 key是不是恰好是某一 塊的最大值，這樣將不再進(jìn)入塊中進(jìn)行比較，而且考慮到這一點(diǎn)我在塊中搜索 時(shí)，是從后往前搜索的，即搜索的初值我設(shè)計(jì)為j=indexi+l.address-l,h這樣 當(dāng)key在最后一塊時(shí)，上邊的這一公式卻不能再用，只能另外處理。而且在當(dāng) 初計(jì)算比較次數(shù)時(shí)由于這樣設(shè)計(jì)的比較繁瑣，我忘記了對(duì)比較塊最后一個(gè)值時(shí) 對(duì)計(jì)數(shù)器加1。由于

14、對(duì)搜索函數(shù)的數(shù)次盲目改動(dòng)都以失敗告終，我最后用了一種簡(jiǎn)單的思 路進(jìn)行比較，即先比較每塊的最大值，如果沒有直接返回1,不再進(jìn)入塊；若有 符合條件得塊，則直接進(jìn)入此塊，并且不管最大值是否就是key,都從首地址再 次重新進(jìn)行比較。這樣計(jì)數(shù)器在查找塊時(shí)和在塊內(nèi)查找時(shí)都在計(jì)數(shù)。在計(jì)數(shù)時(shí)由于程序自身的缺陷，在比較找到符合條件的塊以及在塊中尋找 都符合條件的元素時(shí)，計(jì)數(shù)器都不會(huì)對(duì)最后一次的比較加1,因?yàn)樵诒容^時(shí)我使 用的是while循環(huán)語(yǔ)句，這樣當(dāng)條件符合時(shí)，就不會(huì)再進(jìn)入下邊的結(jié)構(gòu)對(duì)計(jì)數(shù)器 加1 所以我在當(dāng)每次查找成功后都會(huì)再對(duì)計(jì)數(shù)器加1 這樣就保證了計(jì)數(shù)器的值 就是真正的比較的次數(shù)?，F(xiàn)在想想我當(dāng)初設(shè)計(jì)搜索

15、函數(shù)時(shí)之所以出現(xiàn)那種負(fù)責(zé)的比較，只是因?yàn)槲?在潛意識(shí)里將塊的最大值和塊的最后一個(gè)值給混淆了，這也是為什么我當(dāng)初按 大小順序輸入元素得到的比較次數(shù)并沒有錯(cuò)的原因。而當(dāng)我按照混亂的順序輸 入元素時(shí)就出錯(cuò)了。4對(duì)主函數(shù)main()在最初自己電腦上調(diào)試時(shí)沒有出現(xiàn)錯(cuò)誤，但是到了實(shí)驗(yàn)室里出現(xiàn)了跳屏現(xiàn) 象，即結(jié)果輸出來(lái)的時(shí)候窗口隨之就關(guān)閉了，在老師加入兩個(gè)getcharo后，問 題得到解決。3.2對(duì)設(shè)計(jì)和編碼的討論和分析我覺得我的程序非常簡(jiǎn)便，絕對(duì)體現(xiàn)了程序的高效性和簡(jiǎn)單性，我看過其他 類似的程序但都顯得過分冗雜，程序非常長(zhǎng)，看起來(lái)很復(fù)雜，但是最終實(shí)現(xiàn)的 主要的還是那兩個(gè)函數(shù)，我的函數(shù)之所以只有兩個(gè)，是因?yàn)?/p>

16、我的操作都隱含在 這兩個(gè)函數(shù)中了，函數(shù)雖少，功能不少，充分借助了函數(shù)內(nèi)的數(shù)據(jù)，這讓我可 以從一開始的冗雜到現(xiàn)在的簡(jiǎn)單。4經(jīng)驗(yàn)和體會(huì)4.1收獲通過這次課程設(shè)計(jì)，我對(duì)索引順序查找有了更加深入的了解，我基本學(xué)會(huì)了 用索引順序查找來(lái)解決類似的查找問題。雖然在程序的編譯過程中遇到了不少 問題，但是我通過查資料，跟同學(xué)討論等方式，把問題都逐步的解決了。所以, 在這次的實(shí)踐中，我也學(xué)到了不少解決問題的方法，讓我獲益匪淺。我希望以 后老師能多給我們安排一些類似的課程設(shè)計(jì)，我認(rèn)為通過我們的自主設(shè)計(jì)，自 主思考，不僅能提高我們的專業(yè)技能，而且能提高我們自主解決問題的能力， 使我們獲得了更多在平時(shí)學(xué)不到的知識(shí)。這同

17、時(shí)也是一種經(jīng)驗(yàn)，為以后的工作 奠定了一定的基礎(chǔ)。4.2對(duì)算法改進(jìn)的設(shè)想我的搜索函數(shù)indexsearch無(wú)論怎么改都有自身的局限性，這也我我本身的設(shè)計(jì) 思路有關(guān)，而且關(guān)鍵問題在while循環(huán)上，我在查找塊成功進(jìn)入塊內(nèi)查找時(shí)，對(duì) 于前幾個(gè)塊的查找都沒問題只是到了最后一個(gè)，因?yàn)槲业膚hile循環(huán)語(yǔ)句是wh訂e(j<=(indexi+l.address)&&key!=l.data|jj),這樣導(dǎo)致若關(guān)字在最后一塊時(shí)，產(chǎn)生錯(cuò)誤，因?yàn)闆]有indexi+l.addresso這樣我不得不將語(yǔ)改為(j<=(indexi.address+2)&&key!=l.data

18、j),這樣改是因?yàn)槲乙婚_始測(cè)試時(shí)所使用的塊 長(zhǎng)是3,雖然這樣該解決了最后一塊的問題，但是也就產(chǎn)生了局限性，使每塊的個(gè)數(shù)被固定了。這也有解決辦法，就是設(shè)將 indexi.address+2 改為indexi.address+x,這樣每塊的個(gè)數(shù)就可以隨意變動(dòng)了。由于時(shí)間關(guān)系，我并未將其改動(dòng)，但我相信改動(dòng)后一定會(huì)產(chǎn)生期望的效果的。5附源程序清單和運(yùn)行結(jié)果5.1源程序代碼#include nstdio.hn#define maxsize 100 typedef int datatype;typedef structdatatype datafmaxsize; int length;list;typed

19、ef structdatatype max;int address;index;int intpul(list *l,index * index)datatype x,y;int i,j;l->length=o;printf("輸入表，以'o'結(jié)束nnh);scanf(“d”,&x);while(x!=0)l->datal->length=x;l->length+; scanf(h%dh,&x);printf(nn輸入塊的長(zhǎng)度:”);scanf(” d”,&y);printf(nn輸入每一塊的地址：”)； for(i=0

20、;i<y;i+)scanf(”d”,&x); indexij.address=x;printf("n輸入每一塊的最大值:”);for(j=0;j<y;j+)scanf(”d”,&x); indexj.max=x;return y;int indexsearch(list l,index indexjnt len,datatype key) int i=0,count=0,j;while(i<le n&&key>indexi.max) i4-+;count+; if(i>=len)returnelsecount+;while

21、(j<=indexi.address+2&&key!=l.dataj)j+;count+;if(j>indexi.address+2)return -1;else count+; printf(nn 搜索次數(shù)是:%dh,count); return j;int main()list l;index indexmaxsizej;int x,y,m;intlen;len=intput(&l，index); printf(mn輸入關(guān)鍵字:”); scanf(,'n%d",&x);y=indexsearch(l,index jen,x);if(y=-l)printf(,n 沒有 %du,x); else printf("n地址:%d",y+l );printf(nn是否還要繼續(xù)？若是，請(qǐng)按1： h); scanf(,n%d",&m);while(m=l)printf(nn輸入關(guān)鍵字