《數據結構與算法》第6章查找課件

數據結構課程的內容6.1線性查找表6.2二叉搜索樹的查找性能6.3AVL樹6.4哈希表6.8模式匹配第6章查找6.1基本概念——若表中存在特定元素，稱查找成功，應輸出該記錄；——否則，稱查找不成功（也應輸出失敗標志或失敗位置）——由同一類型的數據元素（或記錄）構成的集合?！樵?Searching)特定元素是否在表中?！徊檎?，不改變集合內的數據元素。——既查找，又改變（增減）集合內的數據元素?！刂心硞€數據項的值，可用來識別一個記錄(預先確定的記錄的某種標志)

——可以唯一標識一個元素的關鍵字例如“學號”例如“女”——識別若干元素的關鍵字查找表查找查找成功查找不成功靜態(tài)查找動態(tài)查找關鍵字主關鍵字次關鍵字明確：查找的過程就是將給定的K值與文件中各元素的關鍵字項進行比較的過程。所以用比較次數的平均值來評估算法的優(yōu)劣。稱為平均查找長度（ASL：averagesearchlength）。其中：n是文件記錄個數；Pi是查找第i個記錄的查找概率（通常取等概率,即Pi=1/n）;Ci是找到第i個記錄時所經歷的比較次數。統(tǒng)計意義上的數學期望值物理意義：假設每一元素被查找的概率相同，則查找每一元素所需的比較次數之總和再取平均，即為ASL。如何評估查找方法的優(yōu)劣？一、順序查找（Linearsearch，又稱線性查找）（1）順序表的機內存儲結構：StructNodetype{Keytypekey;elemtypedata;}typedefstruct{

structNodetypelist[Maxsize];

intlength;

}Seqlist;順序查找：即用逐一比較的辦法順序查找關鍵字，這顯然是最直接的辦法。

對順序結構如何線性查找？對單鏈表結構如何線性查找？函數雖未給出，但也很容易編寫；只要知道頭指針head就可以“順藤摸瓜”；對非線性樹結構如何順序查找?可借助各種遍歷操作?。?）算法的實現：技巧：把待查關鍵字key存入表頭或表尾（俗稱“哨兵”），這樣可以加快執(zhí)行速度。例：若將待查找的特定值key存入順序表的首部（如0號單元），則順序查找的實現方案為：從后向前逐個比較！intSearch_Seq(SeqlistST,KeyTypekey){

//在順序表ST中，查找關鍵字與key相同的元素；若成功，返回其位置信息，否則返回0

ST.list[0].key=key;

//設立哨兵，可免去查找過程中每一步都要檢測是否查找完畢。當n>1000時，查找時間將減少一半。

for(i=ST.length;ST.list[i].key!=key;--i);

//不要用for(i=n;i>0;--i)或for(i=1;i<=n;i++)

returni;

//若到達0號單元才結束循環(huán)，說明不成功，返回0值(i=0)。成功時則返回找到的那個元素的位置i。}

——返回特殊標志，例如返回空記錄或空指針。前例中設立了“哨兵”，就是將關鍵字送入末地址ST.list[0].key使之結束并返回i=0。討論②

查找效率怎樣計算？——用平均查找長度ASL衡量。討論①

查不到怎么辦？討論③如何計算ASL？分析：查找第1個元素所需的比較次數為n；查找第2個元素所需的比較次數為n-1；……查找第n個元素所需的比較次數為1；總計全部比較次數為：1＋2＋…＋n=(1+n)n/2未考慮查找不成功的情況：查找哨兵所需的比較次數為n+1這是查找成功的情況若求某一個元素的平均查找次數，還應當除以n（等概率），即：ASL＝（1＋n）/2，時間效率為O(n)二、折半查找（又稱二分查找或對分查找）優(yōu)點：算法簡單，且對順序結構或鏈表結構均適用。缺點：

ASL太長，時間效率太低。這是一種容易想到的查找方法。先給數據排序（例如按升序排好），形成有序表，然后再將key與正中元素相比，若key小，則縮小至左半部內查找；再取其中值比較，每次縮小1/2的范圍，直到查找成功或失敗為止。對順序表結構如何編程實現折半查找算法？

——見下頁之例

對單鏈表結構如何折半查找？

——無法實現！因全部元素的定位只能從頭指針head開始對非線性(樹)結構如何折半查找？

——可借助二叉排序樹來查找（屬動態(tài)查找表形式）。

如何改進？討論④順序查找的特點：②運算步驟：(1)low=1,high=11,mid=6，待查范圍是[1,11]；(2)若ST.list[mid].key<key，說明key[mid+1,high]，則令：low=mid+1;重算mid＝(low+high)/2；.(3)若ST.list[mid].key>

key，說明key[low,mid-1]，則令：high=mid–1;重算mid；(4)若ST.list[mid].key=key，說明查找成功，元素序號=mid;結束條件：（1）查找成功：ST.list[mid].key=key（2）查找不成功：high≤low

（意即區(qū)間長度小于0）解：①先設定3個輔助標志:

low,high,mid，折半查找舉例：Low指向待查元素所在區(qū)間的下界high指向待查元素所在區(qū)間的上界mid指向待查元素所在區(qū)間的中間位置已知如下11個元素的有序表：

（0513192137566475808892）,請查找關鍵字為21

和85的數據元素。顯然有：mid=(low+high)/2討論①若關鍵字不在表中，怎樣得知和停止？——典型標志是：當查找范圍的上界≤下界時停止查找。討論②二分查找的效率（ASL）1次比較就查找成功的元素有1個（20），即中間值；2次比較就查找成功的元素有2個（21），即1/4處（或3/4）處；3次比較就查找成功的元素有4個（22），即1/8處（或3/8）處…4次比較就查找成功的元素有8個（23），即1/16處（或3/16）處………則第m次比較時查找成功的元素會有（2m-1）個；為方便起見，假設表中全部n個元素＝2m-1個，此時就不討論第m次比較后還有剩余元素的情況了。全部比較總次數為1×20＋2×21＋3×22＋4×23…＋m×2m—1

＝推導過程平均每個數據的查找時間還要除以n，所以：課堂練習（多項選擇）：Ａ．采用鏈式存貯結構 Ｂ．記錄的長度≤128Ｃ．采用順序存貯結構Ｄ．記錄按關鍵字遞增有序√√使用折半查找算法時，要求被查文件：查找過程可用二叉樹描述：每個記錄用一個結點表示；結點中值為該記錄在表中位置，這個描述查找過程的二叉樹稱為判定樹。n個元素的表的折半查找的判定樹是唯一的，即：判定樹由表中元素個數決定。

找到有序表中任一記錄的過程就是：走了一條從根結點到與該記錄相應的結點的路徑。

比較的關鍵字個數：為該結點在判定樹上的層次數。

查找成功時比較的關鍵字個數最多不超過樹的深度d:d=log2n+1

若所有結點的空指針域設置為一個指向一個方形結點的指針，稱方形結點為判定樹的外部結點；對應的，圓形結點為內部結點。

查找不成功的過程就是走了一條從根結點到外部結點的路徑。折半查找效率分析法三、分塊查找（索引順序查找）這是一種順序查找的另一種改進方法。先讓數據分塊有序，即分成若干子表，要求每個子表中的數值（用關鍵字更準確）都比后一塊中數值?。ǖ颖韮炔课幢赜行颍?。然后將各子表中的最大關鍵字構成一個索引表，表中還要包含每個子表的起始地址（即頭指針）。索引表最大關鍵字起始地址2212138920334244382448605874498653第1塊第2塊第3塊224886例：2248861713特點：塊間有序，塊內無序查找步驟分兩步進行：①對索引表使用折半查找法（因為索引表是有序表）；②確定了待查關鍵字所在的子表后，在子表內采用順序查找法（因為各子表內部是無序表）；查找效率：ASL=Lb+Lw對索引表查找的ASL對塊內查找的ASLS為每塊內部的記錄個數，n/s即塊的數目例如當n=9，s=3時，ASLbs=3.5,而折半法為3.1,順序法為55.實現程序下面函數以二分法查找塊,以順序法查找分塊內的方法,實現了線性表的分塊查找。其中參數a為順序存儲的線性表,idx為索引表,v為要查找的給定值,m為總塊數。

typedefstruct{intkey;intstart;intlen;}IDX;

intblk_search(a,idx,v,m)IDXidx[];inta[],v,m;{intlow=0,high=m-1,mid,i,h;while(low<=high){mid=(low+high)/2;if(v<idx[mid].key)high=mid-1;elseif(v>idx[mid].keylow=mid+1;

else

{low=mid;break;}}

if(low>=m)return(-1);i=idx[low].start;h=i+idx[low].len;while(i<h&&a[i]!=v)i++;if(a[i]!=v)i=-l;return(i);}

特點：一、二叉排序樹的定義二、二叉排序樹的插入與刪除三、二叉排序樹的查找分析6.2二叉搜索樹的查找性能表結構在查找過程中動態(tài)生成。要求：對于給定值key,若表中存在其關鍵字等于key的記錄，則查找成功返回；否則插入關鍵字等于key的記錄。典型的動態(tài)表———二叉排序樹二叉排序樹查找的算法實現遞歸函數

intBSTsearch(BitreeT,elemtypex){Bitnode*p;if(!T)return0;

else

{if(T->data==x)return1;elseif(x<(T->data))

BSTsearch(T->lchild,x);

else

BSTsearch(T->rchild,x);

}}二叉排序樹插入的算法實現遞歸函數

voidBSTinsert(BitreeT,elemtypex){Bitnode*p;p=(Bitnode*)malloc(sizeof(Bitnode));p->data=x;p->lchild=p->rchild=NULL;if(!T)T=p;elseif(x<T->data)BSTinsert(T->lchild,x);elseBSTinsert(T->rchild,x);

}1)二叉排序樹上查找某關鍵字等于給定值的結點過程，其實就是走了一條從根到該結點的路徑。

比較的關鍵字次數＝此結點的層次數;

最多的比較次數＝樹的深度（或高度），即log2n+12)一棵二叉排序樹的平均查找長度為：二叉排序樹的查找分析其中：ni是每層結點個數；

Ci是結點所在層次數；m為樹深。最壞情況：即插入的n個元素從一開始就有序，

——變成單支樹的形態(tài)！此時樹的深度為n;ASL=(n+1)/2此時查找效率與順序查找情況相同。最好情況：即：與折半查找中的判定樹相同（形態(tài)比較均衡）3）對有n個關鍵字的二叉排序樹的平均查找長度:設每種樹態(tài)出現概率相同，查找每個關鍵字也是等概率的。則ASL求解過程可推導。

樹的深度為：log2n+1；ASL=log2(n+1)–1；與折半查找相同。結論：二叉排序樹的ASL≤2（1＋1/n）lnn一般情況：（與logn同階）問題：如何提高二叉排序樹的查找效率？

盡量讓二叉樹的形狀均衡平衡二叉樹6.3平衡二叉樹平衡二叉樹又稱AVL樹，它是具有如下性質的二叉樹：為了方便起見，給每個結點附加一個數字，給出該結點左子樹與右子樹的高度差。這個數字稱為結點的平衡因子balance。這樣，可以得到AVL樹的其它性質：即|左子樹深度-右子樹深度|≤1左、右子樹是平衡二叉樹；所有結點的左、右子樹深度之差的絕對值≤1例：判斷下列二叉樹是否AVL樹？任一結點的平衡因子只能取：-1、0或

1；如果樹中任意一個結點的平衡因子的絕對值大于1，則這棵二叉樹就失去平衡，不再是AVL樹；對于一棵有n個結點的AVL樹，其高度保持在O(log2n)數量級，ASL也保持在O(log2n)量級。2-100011-10001-1如果在一棵AVL樹中插入一個新結點，就有可能造成失衡，此時必須重新調整樹的結構，使之恢復平衡。我們稱調整平衡過程為平衡旋轉?，F分別介紹這四種平衡旋轉。平衡旋轉可以歸納為四類：

LL平衡旋轉

RR平衡旋轉

LR平衡旋轉

RL平衡旋轉若在A的左子樹的左子樹上插入結點，使A的平衡因子從1增加至2，需要進行一次順時針旋轉。(以B為旋轉軸）ABCABC若在A的右子樹的右子樹上插入結點，使A的平衡因子從-1增加至-2，需要進行一次逆時針旋轉。(以B為旋轉軸）2）RR平衡旋轉：ABCABC1）LL平衡旋轉：若在A的右子樹的左子樹上插入結點，使A的平衡因子從-1增加至-2，需要先進行順時針旋轉，再逆時針旋轉。(以插入的結點C為旋轉軸）4）RL平衡旋轉：ABCABCABC若在A的左子樹的右子樹上插入結點，使A的平衡因子從1增加至2，需要先進行逆時針旋轉，再順時針旋轉。(以插入的結點C為旋轉軸）ABCABCABC3）LR平衡旋轉：這種調整規(guī)則可以保證二叉排序樹的次序不變013037024例：請將下面序列構成一棵平衡二叉排序樹：

（13，24，37，90，53）013037-113024-124-213需要RR平衡旋轉(繞B逆轉,B為根）090-124-137053190-237需要RL平衡旋轉(繞C先順后逆）037090053037090053

練習(1)輸入關鍵字序列為

{16,3,7,11,9,26,18,14,15}試構成一棵平衡二叉排序樹3-1187001111615026149給出序列{5,8,9,2,6,4,7,1,3}呢？6.6哈希查找表一、哈希表的概念二、哈希函數的構造方法三、沖突處理方法四、哈希表的查找及分析前面介紹的所有查找都是基于待查關鍵字與表中元素進行比較而實現的查找方法，查找的效率依賴于查找過程中所進行的比較次數。理想的情況是希望不經過任何比較，一次便能得到所查記錄。哈希表它既是一種查找方法，又是一種存貯方法哈希表：即散列存儲結構。

散列法存儲的基本思想：建立關鍵字值與其存儲位置的對應關系，或者說，由關鍵碼的值決定數據的存儲地址。優(yōu)點：查找速度極快（O(1)）,查找效率與元素個數n無關！例1：若將學生信息按如下方式存入計算機，如：將2001011810201的所有信息存入V[01]單元；將2001011810202的所有信息存入V[02]單元；……將2001011810231的所有信息存入V[31]單元。欲查找學號為2001011810216的信息，便可直接訪問V[16]！一、哈希表的概念

有數據元素序列(14，23，39，9，25，11)，若規(guī)定每個元素k的存儲地址H（k）＝k，請畫出存儲結構圖。（注：H（k）＝k稱為散列函數）例2：解：根據散列函數H（k）＝k，可知元素14應當存入地址為14的單元，元素23應當存入地址為23的單元，……，對應散列存儲表（哈希表）如下：討論：如何進行散列查找？根據存儲時用到的散列函數H(k)表達式，迅即可查到結果！例如，查找key=9,則訪問H(9)=9號地址，若內容為9則成功；若查不到，應當設法返回一個特殊值，例如空指針或空記錄。

地址…9…11…14…232425…39…內點：空間效率低！選取某個函數，依該函數按關鍵字計算元素的存儲位置，并按此存放；查找時，由同一個函數對給定值k計算地址，將k與地址單元中元素關鍵碼進行比較，確定查找是否成功?？赡軐⒉煌年P鍵碼映射到同一個哈希地址上，這種現象稱為沖突。若干術語哈希方法(雜湊法)哈希函數(雜湊函數)哈希表(雜湊表)沖突哈希方法中使用的轉換函數稱為哈希函數(雜湊函數)按上述思想構造的表稱為哈希表(雜湊表)

有6個元素的關鍵碼分別為：（14，23，39，9，25，11）。選取關鍵碼與元素位置間的函數為H(k)=kmod7通過哈希函數對6個元素建立哈希表：253923914沖突現象舉例：6個元素用7個地址應該足夠!H(14)=14%7=011H(25)=25%7=4H(11)=11%7=4有沖突！0123456所以，哈希方法必須解決以下兩個問題：1）構造好的哈希函數（a）所選函數盡可能簡單，以便提高轉換速度；（b）所選函數對關鍵碼計算出的地址，應在哈希地址集中大致均勻分布，以減少空間浪費。2）制定一個好的解決沖突的方案查找時，如果從哈希函數計算出的地址中查不到關鍵碼，則應當依據解決沖突的規(guī)則，有規(guī)律地查詢其它相關單元。在哈希查找方法中，沖突是不可能避免的，只能盡可能減少。二、哈希函數的構造方法常用的哈希函數構造方法有：直接定址法除留余數法乘余取整法數字分析法平方取中法折疊法隨機數法要求一：n個數據原僅占用n個地址，雖然散列查找是以空間換時間，但仍希望散列的地址空間盡量小。要求二：無論用什么方法存儲，目的都是盡量均勻地存放元素，以避免沖突。Hash(key)=a·key+b(a、b為常數)優(yōu)點：以關鍵碼key的某個線性函數值為哈希地址，不會產生沖突.缺點：要占用連續(xù)地址空間，空間效率低。例：關鍵碼集合為{100，300，500，700，800，900}，選取哈希函數為Hash(key)=key/100，則存儲結構（哈希表）如下：01234567899008007005003001001、直接定址法Hash(key)=B*(A*keymod1)

(A、B均為常數，且0<A<1，B為整數)特點：以關鍵碼key乘以A，取其小數部分，然后再放大B倍并取整，作為哈希地址。Hash(key)=keymodp(p是一個整數)特點：以關鍵碼除以p的余數作為哈希地址。關鍵：如何選取合適的p？技巧：若設計的哈希表長為m，則一般取p≤m且為質數（也可以是不包含小于20質因子的合數）。3、乘余取整法2、除留余數法（A*keymod1）就是取A*key的小數部分例：欲以學號最后兩位作為地址，則哈希函數應為：

H(k)=100*(0.01*k%1)其實也可以用法2實現：H(k)=k%100特點：某關鍵字的某幾位組合成哈希地址。所選的位應當是：各種符號在該位上出現的頻率大致相同。34705243491487348269634852703486305349805834796713473919例：有一組（例如80個）關鍵碼，其樣式如下：4、數字分析法討論：①第1、2位均是“3和4”，第3位也只有“7、8、9”，因此，這幾位不能用，余下四位分布較均勻，可作為哈希地址選用。位號：①②③④⑤⑥⑦②若哈希地址取兩位（因元素僅80個），則可取這四位中的任意兩位組合成哈希地址，也可以取其中兩位與其它兩位疊加求和后，取低兩位作哈希地址。特點：對關鍵碼平方后，按哈希表大小，取中間的若干位作為哈希地址。理由：因為中間幾位與數據的每一位都相關。例：2589的平方值為6702921，可以取中間的029為地址。6、折疊法特點：將關鍵碼自左到右分成位數相等的幾部分（最后一部分位數可以短些），然后將這幾部分疊加求和，并按哈希表表長，取后幾位作為哈希地址。適用于：每一位上各符號出現概率大致相同的情況。法1：移位法──將各部分的最后一位對齊相加。法2：間界疊加法──從一端向另一端沿分割界來回折疊后，最后一位對齊相加。例：元素42751896,用法1：427＋518＋96=1041用法2：42751896—>724+518+69=13115、平方取中法7、隨機數法Hash(key)=random(key)(random為偽隨機函數)適用于：關鍵字長度不等的情況。造表和查找都很方便。①執(zhí)行速度（即計算哈希函數所需時間）；②關鍵字的長度；③哈希表的大小；④關鍵字的分布情況；⑤查找頻率。小結：構造哈希函數的原則：三、沖突處理方法常見的沖突處理方法有：開放定址法（開地址法）鏈地址法（拉鏈法）再哈希法（雙哈希函數法）建立一個公共溢出區(qū)1、開放定址法（開地址法）設計思路：有沖突時就去尋找下一個空的哈希地址，只要哈希表足夠大，空的哈希地址總能找到，并將數據元素存入。具體實現：Hi=(Hash(key)+di)modm(1≤i<m)其中：Hash(key)為哈希函數

m為哈希表長度

di

為增量序列1，2，…m-1，且di=i1.線性探測法含義：一旦沖突，就找附近（下一個）空地址存入。關鍵碼集為{47，7，29，11，16，92，22，8，3}，設：哈希表表長為m=11；哈希函數為Hash(key)=keymod11；擬用線性探測法處理沖突。建哈希表如下：解釋：①47、7（以及11、16、92）均是由哈希函數得到的沒有沖突的哈希地址；012345678910477△▲△△例：291116922283②Hash(29)=7，哈希地址有沖突，需尋找下一個空的哈希地址：由H1=(Hash(29)+1)mod11=8，哈希地址8為空，因此將29存入。③另外，22、8、3同樣在哈希地址上有沖突，也是由H1找到空的哈希地址的。其中3還連續(xù)移動了兩次（二次聚集）線性探測法的優(yōu)點：只要哈希表未被填滿，保證能找到一個空地址單元存放有沖突的元素；線性探測法的缺點：可能使第i個哈希地址的同義詞存入第i+1個哈希地址，這樣本應存入第i+1個哈希地址的元素變成了第i+2個哈希地址的同義詞，……，因此，可能出現很多元素在相鄰的哈希地址上“堆積”起來，大大降低了查找效率。解決方案：可采用二次探測法或偽隨機探測法，以改善“堆積”問題。討論：仍舉上例，改用二次探測法處理沖突，建表如下：012345678910112234792167298△▲△△注：只有3這個關鍵碼的沖突處理與上例不同，Hash(3)=3，哈希地址上沖突，由H1=(Hash(3)+12)mod11=4，仍然沖突；H2=(Hash(3)-12)mod11=2，找到空的哈希地址，存入。2.二次探測法Hi=(Hash(key)±di)modm其中：Hash(key)為哈希函數

m為哈希表長度，m要求是某個4k+3的質數；

di為增量序列

12，-12，22，-22，…，q2

3.若di＝偽隨機序列，就稱為偽隨機探測法2、鏈地址法(拉鏈法）基本思想：將具有相同哈希地址的記錄鏈成一個單鏈表，m個哈希地址就設m個單鏈表，然后用一個數組將m個單鏈表的表頭指針存儲起來，形成一個動態(tài)的結構。設{47,7,29,11,16,92,22,8,3,50,37,89}的哈希函數為：Hash(key)=keymod11，用拉鏈法處理沖突，則建表如右圖所示。

例：

01234567891022118934737922971650810注：有沖突的元素可以插在表尾,也可以插在表頭3、再哈希法（雙哈希函數法）Hi=RHi(key)i=1,2,…，kRHi均是不同的哈希函數，當產生沖突時就計算另一個哈希函數，直到沖突不再發(fā)生。優(yōu)點：不易產生聚集；缺點：增加了計算時間。4.建立一個公共溢出區(qū)思路：除設立哈?；颈硗猓碓O立一個溢出向量表。 所有關鍵