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

1、wordword教育資料實驗靜態(tài)表的查找操作實驗、實驗名稱和性質(zhì)所屬課程數(shù)據(jù)結(jié)構(gòu)實驗名稱靜態(tài)表的查找操作實驗學時實驗性質(zhì)驗證口綜合燈設(shè)計必做選做必做口選做二、實驗目的1掌握順序查找操作的算法實現(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)境要求：機（單機）使用的軟件名稱、版本號以及模塊：環(huán)境下的以上或五、知識準備前期要求掌握

2、查找的含義和順序查找、二分查找及索引查找操作的方法。六、驗證性實驗1實驗要求編程實現(xiàn)如下功能：（）根據(jù)輸入的查找表的表長和個關(guān)鍵字值，建立順序查找表，并在此查找表中用順序查找方法查找給定關(guān)鍵值的記錄，最后輸出查找結(jié)果。（）根據(jù)輸入的查找表的表長和個按升排列的關(guān)鍵字值，建立有序順序查找表，并在此查找表中用二分查找方法查找給定關(guān)鍵值的記錄，最后輸出查找結(jié)果。（3）主程序中要求設(shè)計一個菜單，允許用戶通過菜單來多次選擇執(zhí)行哪一種查找操作。2.實驗相關(guān)原理：查找表分別靜態(tài)查找表和動態(tài)查找表兩種，其中只能做引用操作的查找表稱為靜態(tài)查找表。靜態(tài)查找表采用順序存儲結(jié)構(gòu)的數(shù)據(jù)描述為：順序查找表的最大長度【核心算

3、法提示】查找操作是根據(jù)給定的某個值，在查找表中確定一個其關(guān)鍵字等于給定值的數(shù)據(jù)元素或記錄的過程。若查找表中存在這樣一個記錄，則稱“查找成功”。查找結(jié)果給出整個記錄的信息，或指示該記錄在查找表中的位置；若在查找表中不存在這樣的記錄，則稱“查找不成功”。查找結(jié)果給出“空記錄”或“空指針”。（1）順序查找操作的基本步驟：從表中最后一個記錄開始，逆序掃描查找表，依次將掃描到的結(jié)點關(guān)鍵字值與給定值進行比較，若當前掃描到的結(jié)點關(guān)鍵字值與相等，則查找成功；若掃描到第一個記錄，仍未找到關(guān)鍵字值等于的記錄，則查找失敗。在程序設(shè)計中為了減少執(zhí)行的循環(huán)次數(shù)使用了監(jiān)視哨。監(jiān)視哨可設(shè)置在表頭，也可設(shè)置在表尾。在此設(shè)置在

4、表頭。（2）二分查找也叫折半查找，這種查找要求查找表必須是有序順序表。其查找操作的基本步驟：首先取出表中的中間元素，若其關(guān)鍵字值等于給定值，則查找成功，操作結(jié)束；否則以中間元素為分界點，將查找表分成兩個子表，并判斷所查的值所在的子表是前部分，還是后部分，再重復上述步驟直到找到關(guān)鍵字值為的元素或子表長度為0【核心算法描述】intsxsearch（SstableST,keytypekey）在順序查找表中，用順序查找的方法查找其關(guān)鍵字等于的數(shù)據(jù)元素。若找到，則函數(shù)返回該元素在表中的位置，否則返回0*/在表頭設(shè)置監(jiān)視哨從后往前順序查找在按關(guān)鍵字從小到大的有序順序表中，用二分查找的方法查找其關(guān)鍵字等于的

5、數(shù)據(jù)元素。若找到，則函數(shù)返回該元素在表中的位置，否則返回0*/置查找區(qū)間的初值找到匹配記錄繼續(xù)對左半部分進行二分查找繼續(xù)對右半部分進行二分查找找不0到;匹配/記在錄源程序代碼參考順序查找函數(shù)二分法查找函數(shù)（主函）/數(shù)請求輸入順序表表長請求輸入個關(guān)鍵字值請求輸入待查找的記錄關(guān)鍵字值,&key);調(diào)用順序查找函數(shù)請求輸入順序表表長請求輸入個關(guān)鍵字值(必須升序排列)請求輸入待查找的記錄關(guān)鍵字值,&key);調(diào)用二分法查找函數(shù)n;tf(chooseerrorn);若找不到，提示信息若找到，輸出位置運行結(jié)果參考如圖6-所1示圖6-驗1證性實驗運行結(jié)果InpLit：chooseCl3:1Input：tab

6、lelengthn：6Input：ndataInpLit：chooseCl3:1Input：tablelengthn：6Input：ndata：147&4G98Input：key=981Sxseiach2Binselach3ExitpleaseInput：chooseCl3:3thedcktckis：atposition2ZEJeeeessS3saa2aeeee1-1-1-31-plpP4pe&tsniXiXSBE-123thedcktckis：atpositionG七、設(shè)計性實驗1實驗要求編程實現(xiàn)如下功能：（1）建立索引查找表（2）利用索引查找確定給定記錄在索引查找表中的塊號和在塊中的位置。

7、2核心算法分析索引查找表有索引表和塊表兩部分所構(gòu)成，其中索引表存儲的是各塊記錄中的最大關(guān)鍵字值和各塊的起始存儲地址，用順序存儲結(jié)構(gòu)，各塊的起始存儲地址的初始值置為空指針；而塊表中存儲的是查找表中的所有記錄并且按塊有序，用鏈式存儲或順序存儲結(jié)構(gòu)，在此用鏈式存儲結(jié)構(gòu)。則索引查找表的存儲結(jié)構(gòu)圖如6-所2示：r0r1r2r3最大關(guān)鍵字塊鏈頭指針圖r0r1r2r3最大關(guān)鍵字塊鏈頭指針圖6-2索引查找表的存儲結(jié)構(gòu)示意圖將如圖6-所2示的存儲結(jié)構(gòu)描述為：塊鏈中的結(jié)點類型存儲塊中記錄的關(guān)鍵字值指向塊鏈中下一記錄結(jié)點的指針Bnode;索引表中元素的類型存儲各塊記錄中的最大關(guān)鍵字值塊鏈的頭指針Snode;索引查找表的結(jié)構(gòu)類型索引順序表索引順序表中存儲數(shù)據(jù)的個數(shù)Stable;由于在索引查找表中，索引表是按關(guān)鍵字從小到大排列的有序順序表，塊鏈是一個無序鏈表，所有索引表的查找過程可歸納為：（1）在索引表中用二分查找確定待查找的記錄所在的塊號；（2）沿著塊鏈指針用順序查找的方法確定待查找的記錄在塊鏈中的存儲位置。如果查找成功，則輸出待查找記錄在索引表中的塊號和在塊鏈中的存儲地址；如果查找失敗，則輸出“沒有找到”的信息。3核心算法描述intfindblock(StableST,keytypekey)用二分查找法在索引查找表的索引表中確定關(guān)鍵字值為的待