數(shù)據(jù)結(jié)構(gòu)與算法分析：檢索順序查找

檢索（查找）數(shù)據(jù)結(jié)構(gòu)與算法1何謂查找表？查找表是由同一類型的數(shù)據(jù)元素(或記錄)構(gòu)成的集合。

由于“集合”中的數(shù)據(jù)元素之間存在著松散的關(guān)系，因此查找表是一種應(yīng)用靈便的結(jié)構(gòu)。2對查找表經(jīng)常進行的操作1）查詢某個“特定的”數(shù)據(jù)元素是否在查找表中；2）檢索某個“特定的”數(shù)據(jù)元素的各種屬性；3）在查找表中插入一個數(shù)據(jù)元素；4）從查找表中刪去某個數(shù)據(jù)元素。3僅作查詢和檢索操作的查找表。靜態(tài)查找表有時在查詢之后，還需要將“查詢”結(jié)果為“不在查找表中”的數(shù)據(jù)元素插入到查找表中；或者，從查找表中刪除其“查詢”結(jié)果為“在查找表中”的數(shù)據(jù)元素。動態(tài)查找表查找表可分為兩類4是數(shù)據(jù)元素（或記錄）中某個數(shù)據(jù)項的值，用以標(biāo)識（識別）一個數(shù)據(jù)元素（或記錄）。關(guān)鍵字若此關(guān)鍵字可以識別唯一的一個記錄，則稱之謂“主關(guān)鍵字”。若此關(guān)鍵字能識別若干記錄，則稱之謂“次關(guān)鍵字”。5檢索的方式精確匹配查詢（exact-matchquery）模糊匹配查詢（fuzzy-matchquery）范圍查詢（rangequery）6根據(jù)給定的某個值，在查找表中確定一個其關(guān)鍵字等于給定值的數(shù)據(jù)元素或（記錄）。

精確匹配查找若查找表中存在這樣一個記錄，則稱“查找成功”。查找結(jié)果給出整個記錄的信息，或指示該記錄在查找表中的位置；否則稱“查找不成功”。查找結(jié)果給出“空記錄”或“空指針”。7檢索的方法1.順序表和線性表方法(lists,tables,arrays).2.根據(jù)關(guān)鍵碼值直接訪問方法(hashing)3.樹索引方法.8

由于查找表中的數(shù)據(jù)元素之間不存在明顯的組織規(guī)律，因此不便于查找。為了提高查找的效率，需要在查找表中的元素之間人為地附加某種確定的關(guān)系，換句話說，

用另外一種結(jié)構(gòu)來表示查找表。如何進行查找？查找的方法取決于查找表的結(jié)構(gòu)。9查找方法目錄基于順序（線性）結(jié)構(gòu)的查找基于有序順序（線性）結(jié)構(gòu)的查找10基于線性結(jié)構(gòu)的檢索11順序檢索問45是否已經(jīng)保存？11132050323360459053477123456789101112位置值12ListFindFunction//ReturntrueiffKisinlistboolfind(List<int>&L,intK){

intit;for(L.setStart();L.getValue(it); L.next())if(K==it)returntrue;//Founditreturnfalse;//Notfound}Cost：對一個未排序的線性表進行順序檢索，在平均情況和最差情況下需要(n)13順序檢索（2）問保存的值中最大值是多少？11132050323360459053477123456789101112位置值11132050505060609090909014在數(shù)組中找最大值//Findlargestvalueint

largest(intarray[],intn){int

currlarge=0;//Largestvalueseenfor(inti=1;i<n;i++)//Foreachvalif(array[currlarge]<array[i])

currlarge=i;//Rememberposreturncurrlarge;//Returnlargest}15

定義：

查找算法的平均查找長度

(AverageSearchLength)

為確定記錄在查找表中的位置，需和給定值

進行比較的關(guān)鍵字個數(shù)的期望值

其中:n

為表長，Pi

為查找表中第i個記錄的概率，且，Ci為找到該記錄時，曾和給定 值比較過的關(guān)鍵字的個數(shù)。分析順序查找的時間性能16在等概率查找的情況下，

順序表查找的平均查找長度為：對順序表而言，Ci=n-i+1ASL=nP1+(n-1)P2++2Pn-1+Pn17

若查找概率無法事先測定，則查找過程采取的改進辦法是，在每次查找之后，將剛剛查找到的記錄直接移至表尾的位置上。在不等概率查找的情況下，ASLss

在

Pn≥Pn-1≥···≥P2≥P1時取極小值18順序查找表的查找算法簡單，但平均查找長度較大，特別不適用于表長較大的查找表。19基于有序順序結(jié)構(gòu)的檢索20二分查找法問45是否已經(jīng)保存？41113203233455053607790123456789101112位置值21BinarySearch//Returnpositionofelementinsorted//arrayofsizenwithvalueK.int

binary(intarray[],intn,intK){

intl=-1;

intr=n;//l,rarebeyondarrayboundswhile(l+1!=r){//Stopwhenl,rmeet

inti=(l+r)/2;//Checkmiddleif(K<array[i])r=i;//Lefthalfif(K==array[i])returni;//Founditif(K>array[i])l=i;//Righthalf}returnn;//Searchvaluenotinarray}22假設(shè)n=2h-1并且查找概率相等則

在n>50時，可得近似結(jié)果

一般情況下，表長為n的折半查找的判定樹的深度和含有n個結(jié)點的完全二叉樹的深度相同。23字典檢索檢索一般不從辭典的中間開始。如果要查找的詞以's'開頭，查找者會估計到以's'開頭的條目從詞典的四分之三處開始。這樣，他就會先翻到詞典的四分之三處，然后根據(jù)所看到的內(nèi)容決定接下來向哪里翻。也就是說，人們一般根據(jù)關(guān)鍵碼值預(yù)期分布的知識“計算出”接下來向哪里翻。這種經(jīng)過計算的二分法檢索的形式稱為詞典檢索(dictionarysearch)或者插值檢索(interpolationsearch)24自組織線性表25根據(jù)訪問頻率排列列表根據(jù)估算的訪問頻率排列記錄.執(zhí)行順序檢索訪問第一條記錄的代價:1訪問第二條記錄的代價:2預(yù)期的檢索代價:26例子(1)(1)每一條記錄被訪問的機會都相同.27例子(2)(2)指數(shù)頻率28Zipf

分布應(yīng)用:自然語言(如英語)中單詞使用頻率的分布.城市中的人口規(guī)模的分布,等.80/20規(guī)則:80%的訪問都是對20%的記錄進行的.當(dāng)按照80/20規(guī)則分布時,29自組織線性表自組織線性表根據(jù)實際的記錄訪問模式在線性表中修改記錄順序.自組織線性表使用啟發(fā)式規(guī)則決定如何重新排列線性表.這些啟發(fā)式規(guī)則類似于管理緩沖池的規(guī)則.30啟發(fā)式規(guī)則計數(shù)方法:為每條記錄保存一個訪問計數(shù),而且一直按照這個順序維護記錄.(類似于緩沖池替代策略中的“最不頻繁使用”LFU法.)移至前端法:如果找到一條記錄就把它放到線性表的最前面,而把其他記錄后退一個位置.轉(zhuǎn)置:把找到的記錄與它在線性表中的前一條記錄交換位置.31例子假定有8條記錄，其關(guān)鍵碼值為A到H，而且最初以字母順序排列 訪問序列FDFGEGFAFGE（12次訪問）線性表根據(jù)計數(shù)法組織最后結(jié)果FGDEABCH總代價是45次比較根據(jù)移至前端啟發(fā)式規(guī)則最后結(jié)果EGFDABCH總代價是54次比較根據(jù)轉(zhuǎn)置啟發(fā)式規(guī)則最后結(jié)果ABFDGECH總代價是62次比較32文本壓縮的例子應(yīng)用:文本壓縮.線性表是根據(jù)移至前端規(guī)則自組織的.如果單詞前面已經(jīng)出現(xiàn)，就傳送這個單詞在線性表中的位置.如果單詞是第一次出現(xiàn)，就傳送這個單詞.ThecaronthelefthitthecarIleft.Thecaron3lefthit35I5.這種壓縮方法的思想類似于Ziv-lempel編碼算法.33集合的檢索34集合的檢索Fordensesets(smallrange,highpercentageofelementsinset).可以使用邏輯上的位操作.例子:為了尋找數(shù)字0到15之間奇素數(shù)集合,計算:0011010100010100&010101010101010135分塊和索引（索引順序查找）36分塊查找的存儲結(jié)構(gòu)表分為b塊，每一塊中的關(guān)鍵字不一定有序，但前一塊中的最大關(guān)鍵字必須小于后一塊中的最小關(guān)鍵字，即表是“分塊有序”的。抽取各塊中的最大關(guān)鍵字及其起始位置構(gòu)成一個索引表,由于表R是分塊有序的，所以索引表是一個遞增有序表。

37分塊查找的基本思想1）首先查找索引表

索引表是有序表，可采用二分查找或順序查找，以確定待查的結(jié)點在哪一塊。

2）然后在已確定的塊中進行順序查找

由于塊內(nèi)