靜態(tài)表的查找操作實驗

1、精選文檔實驗B06: 靜態(tài)表的查找操作實驗一、實驗名稱和性質(zhì)所屬課程數(shù)據(jù)結(jié)構(gòu)實驗名稱靜態(tài)表的查找操作實驗學時2實驗性質(zhì)驗證 綜合 設(shè)計必做/選做必做 選做二、實驗?zāi)康?掌握順序查找操作的算法實現(xiàn)。2掌握二分查找操作的算法實現(xiàn)及實現(xiàn)該查找的前提。3掌握索引查找操作的算法實現(xiàn)。三、實驗內(nèi)容1建立順序查找表，并在此查找表上實現(xiàn)順序查找操作（驗證性內(nèi)容）。2建立有序順序查找表，并在此查找表上實現(xiàn)二分查找操作（驗證性內(nèi)容）。3建立索引查找表，并在此查找表上實現(xiàn)索引查找操作（設(shè)計性內(nèi)容）。四、實驗的軟硬件環(huán)境要求硬件環(huán)境要求：PC機（單機）使用的軟件名稱、版本號以及模塊：Windows環(huán)境下的TurboC

2、2.0以上或VC+ 五、知識準備前期要求掌握查找的含義和順序查找、二分查找及索引查找操作的方法。六、驗證性實驗1實驗要求編程實現(xiàn)如下功能：（1）根據(jù)輸入的查找表的表長n和n個關(guān)鍵字值，建立順序查找表，并在此查找表中用順序查找方法查找給定關(guān)鍵值的記錄，最后輸出查找結(jié)果。（2）根據(jù)輸入的查找表的表長n和n個按升排列的關(guān)鍵字值，建立有序順序查找表，并在此查找表中用二分查找方法查找給定關(guān)鍵值的記錄，最后輸出查找結(jié)果。（3）主程序中要求設(shè)計一個菜單，允許用戶通過菜單來多次選擇執(zhí)行哪一種查找操作。2. 實驗相關(guān)原理：查找表分別靜態(tài)查找表和動態(tài)查找表兩種，其中只能做引用操作的查找表稱為靜態(tài)查找表。靜態(tài)查找表

3、采用順序存儲結(jié)構(gòu)的數(shù)據(jù)描述為：#define MAXSIZE 100 /*順序查找表的最大長度*/typedef int keytype;typedef structkeytype key;redtype;typedef struct redtype elemMAXSIZE; int length;Sstable;【核心算法提示】查找操作是根據(jù)給定的某個值，在查找表中確定一個其關(guān)鍵字等于給定值的數(shù)據(jù)元素 或記錄的過程。若查找表中存在這樣一個記錄，則稱“查找成功”。查找結(jié)果給出整個記錄的信息，或指示該記錄在查找表中的位置；若在查找表中不存在這樣的記錄，則稱“查找不成功”。查找結(jié)果給出“空記錄”或

4、“空指針”。（1）順序查找操作的基本步驟：從表中最后一個記錄開始，逆序掃描查找表，依次將掃描到的結(jié)點關(guān)鍵字值與給定值key進行比較，若當前掃描到的結(jié)點關(guān)鍵字值與key相等，則查找成功；若掃描到第一個記錄，仍未找到關(guān)鍵字值等于key的記錄，則查找失敗。在程序設(shè)計中為了減少執(zhí)行的循環(huán)次數(shù)使用了監(jiān)視哨。監(jiān)視哨可設(shè)置在表頭，也可設(shè)置在表尾。在此設(shè)置在表頭。（2）二分查找也叫折半查找，這種查找要求查找表必須是有序順序表。其查找操作的基本步驟：首先取出表中的中間元素，若其關(guān)鍵字值等于給定值key，則查找成功，操作結(jié)束；否則以中間元素為分界點，將查找表分成兩個子表，并判斷所查的key值所在的子表是前部分，還

5、是后部分，再重復上述步驟直到找到關(guān)鍵字值為key的元素或子表長度為0?！竞诵乃惴枋觥縤nt sxsearch(Sstable ST, keytype key)/*在順序查找表ST中，用順序查找的方法查找其關(guān)鍵字等于key的數(shù)據(jù)元素。若找到，則函數(shù)返回該元素在表中的位置，否則返回0 */ ST.elem0.key=key; /*在表頭設(shè)置監(jiān)視哨*/for(i=ST.length;ST.elemi.key!=key;-i); /*從后往前順序查找*/return i;int binsearch(Sstable ST,keytype key)/*在按關(guān)鍵字從小到大的有序順序表ST中，用二分查找的方

6、法查找其關(guān)鍵字等于key的數(shù)據(jù)元素。若找到，則函數(shù)返回該元素在表中的位置，否則返回0 */ low=1;high=ST.length; /*置查找區(qū)間的初值*/ while(low<=high) mid=(low+high)/2;if (key=ST.elemmid.key) return mid;/*找到匹配記錄*/else if (key<ST.elemmid.key) high=mid-1;/*繼續(xù)對左半部分進行二分查找*/ else low=mid+1；/*繼續(xù)對右半部分進行二分查找*/return 0; /*找不到匹配記錄*/3源程序代碼參考#define MAXSIZE

7、 100typedef int keytype;typedef struct keytype key; redtype;typedef struct redtype elemMAXSIZE; int length; Sstable;int sxsearch(Sstable ST,keytype Key)/*順序查找函數(shù)*/ int i; ST.elem0.key=Key; for(i=ST.length;ST.elemi.key!=Key;-i); return i; int binsearch(Sstable ST,keytype Key)/*二分法查找函數(shù)*/ int low,mid,hi

8、gh; low=1;high=ST.length; while(low<=high) mid=(low+high)/2; if (Key=ST.elemmid.key) return mid; else if (Key<ST.elemmid.key) high=mid-1; else low=mid+1; return 0; main()/*主函數(shù)*/Sstable ST; int i,pos,x,key; pos=0; while(1) printf("n 1-Sxserachn"); printf(" 2-Binserachn"); pr

9、intf(" 3-Exitn"); printf("please input choose(1-3):"); scanf("%d",&x); switch(x) case 1: printf("please input table length n:");/*請求輸入順序表表長*/ scanf("%d",&ST.length); printf("please input n data:n");/*請求輸入n個關(guān)鍵字值*/ for(i=1;i<=ST.le

10、ngth;i+) scanf("%d",&ST.elemi.key); printf("please input key:");/*請求輸入待查找的記錄關(guān)鍵字值*/ scanf("%d",&key); pos=sxsearch(ST,key); /*調(diào)用順序查找函數(shù)*/ break; case 2: printf("please input table length n:");/*請求輸入順序表表長*/ scanf("%d",&ST.length); printf(&qu

11、ot;please input n data(sort):n");/*請求輸入n個關(guān)鍵字值（必須升序排列）*/ for(i=1;i<=ST.length;i+) scanf("%d",&ST.elemi.key); printf("please input key:");/*請求輸入待查找的記錄關(guān)鍵字值*/ scanf("%d",&key); pos=binsearch(ST,key);/*調(diào)用二分法查找函數(shù)*/ break; case 3: return; default: printf("

12、choose errorn"); if(pos=0) printf("nthe data is not found.n"); /*若找不到，提示信息*/ else printf("nthe data is at position %dn",pos); /*若找到，輸出位置*/4運行結(jié)果參考如圖6-1所示 圖6-1 驗證性實驗運行結(jié)果七、設(shè)計性實驗1實驗要求編程實現(xiàn)如下功能：（1）建立索引查找表（2）利用索引查找確定給定記錄在索引查找表中的塊號和在塊中的位置。2核心算法分析 索引查找表有索引表和塊表兩部分所構(gòu)成，其中索引表存儲的是各塊記錄中的最大

13、關(guān)鍵字值和各塊的起始存儲地址，用順序存儲結(jié)構(gòu)，各塊的起始存儲地址的初始值置為空指針；而塊表中存儲的是查找表中的所有記錄并且按塊有序，用鏈式存儲或順序存儲結(jié)構(gòu)，在此用鏈式存儲結(jié)構(gòu)。則索引查找表的存儲結(jié)構(gòu)圖如6-2所示： 塊鏈頭指針最大關(guān)鍵字大工業(yè)大工業(yè) 12 23 47 3ST361294152314211331453747ST. LengthST. rr0 r1 r2 r3圖6-2 索引查找表的存儲結(jié)構(gòu)示意圖 將如圖6-2所示的存儲結(jié)構(gòu)描述為： #define MAXSIZE 100typedef int keytype;typedef struct bnode /*塊鏈中的結(jié)點類型*/ ke

14、ytype key; /*存儲塊中記錄的關(guān)鍵字值*/ struct bnode *next; /*指向塊鏈中下一記錄結(jié)點的指針*/ Bnode;typedef struct snode /*索引表中元素的類型*/ keytype Maxkey; /*存儲各塊記錄中的最大關(guān)鍵字值*/ Bnode *head; /*塊鏈的頭指針*/Snode;typedef struct /*索引查找表的結(jié)構(gòu)類型*/ Snode rMAXSIZE; /*索引順序表*/ int length; /*索引順序表中存儲數(shù)據(jù)的個數(shù)*/ Stable;由于在索引查找表中，索引表是按關(guān)鍵字從小到大排列的有序順序表，塊鏈是一個

15、無序鏈表，所有索引表的查找過程可歸納為：（1）在索引表中用二分查找確定待查找的記錄所在的塊號；（2）沿著塊鏈指針用順序查找的方法確定待查找的記錄在塊鏈中的存儲位置。如果查找成功，則輸出待查找記錄在索引表中的塊號和在塊鏈中的存儲地址；如果查找失敗，則輸出“沒有找到”的信息。3核心算法描述int findblock(Stable ST, keytype key) /*用二分查找法在索引查找表ST的索引表中確定關(guān)鍵字值為key的待查找記錄所在的塊號,函數(shù)并返回值其塊號值*/ int low,high,mid; low=1;high=ST.length; while(low<=high) mid=(low+high)/2; if (key<ST.rmid.Maxkey) high=mid-1; else low=mid+1; return high+1; Blink findrec(Stable ST,keytype key) /*