數(shù)據(jù)結(jié)構(gòu)-查找課件

第11章查找查找（Searching）又稱檢索，就是從一個(gè)數(shù)據(jù)元素集合中找出某個(gè)特定的數(shù)據(jù)元素。它是數(shù)據(jù)處理中經(jīng)常使用的一種重要操作，尤其是當(dāng)所涉及的數(shù)據(jù)量較大時(shí)，查找算法的優(yōu)劣對整個(gè)軟件系統(tǒng)的效率影響是很大的。11.1查找表查找表（SearchTable）是由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成的集合。由于表中數(shù)據(jù)元素之間存在著完全松散的關(guān)系，因此查找表是一種非常靈便的數(shù)據(jù)結(jié)構(gòu)。對查找表進(jìn)行的操作有以下4種：（1）查詢某個(gè)特定的數(shù)據(jù)元素是否在查找表中；（2）檢索某個(gè)特定的數(shù)據(jù)元素的各種屬性；（3）在查找表中插入一個(gè)數(shù)據(jù)元素；（4）從查找表中刪除某個(gè)數(shù)據(jù)元素。11.2靜態(tài)查找表靜態(tài)查找表是數(shù)據(jù)元素的線性表，可以是基于數(shù)組的順序存儲(chǔ)或以線性鏈表存儲(chǔ)。在C語言中可描述如下：typedef

struct

{

ElemType

elem[];

intlength; }SSTBL;typedef

structNODE {

ElemType

elem;

structNODE*next; }NodeType;11.2.1順序查找順序查找又稱線性查找，是最基本的查找方法之一。其查找過程為：從表的一端開始，向另一端逐個(gè)按給定值kx與數(shù)據(jù)元素的關(guān)鍵字key進(jìn)行比較。若找到，查找成功，并返回?cái)?shù)據(jù)元素在表中的位置；若整個(gè)表查找完，仍未找到與kx相同的關(guān)鍵字，則查找失敗，給出失敗信息。以順序存儲(chǔ)為例，0號(hào)單元留空，數(shù)據(jù)元素從下標(biāo)為1的數(shù)組單元開始存放。11.2.2有序表的折半查找有序表即是表中數(shù)據(jù)元素按關(guān)鍵字升序或降序排列。折半查找的思想為：在有序表中，取中間元素作為比較對象，若給定值與中間元素的關(guān)鍵字相等，則查找成功；若給定值小于中間元素的關(guān)鍵字，則在中間元素的左半?yún)^(qū)繼續(xù)查找；若給定值大于中間元素的關(guān)鍵字，則在中間元素的右半?yún)^(qū)繼續(xù)查找。不斷重復(fù)上述查找過程，直到查找成功，或所查找的區(qū)間無數(shù)據(jù)元素，查找失敗。1．算法分析2．算法實(shí)現(xiàn)3．性能分析11.2.3分塊查找分塊查找又稱索引順序查找，是對順序查找的一種改進(jìn)。分塊查找要求將查找表分成若干個(gè)子表，并對子表建立索引表，每一個(gè)子表由索引表中的索引項(xiàng)確定。索引項(xiàng)包括兩個(gè)字段：關(guān)鍵字字段（存放對應(yīng)子表中的最大關(guān)鍵字值）；指針字段（存放指向?qū)?yīng)子表的指針），并且要求索引項(xiàng)按關(guān)鍵字字段有序。查找過程：將表分成幾塊，塊內(nèi)無序，塊間有序；先確定待查記錄所在塊，再在塊內(nèi)查找。查找時(shí)，先用給定值kx在索引表中檢測索引項(xiàng)，以確定所要進(jìn)行的查找在查找表中的查找分塊（由于索引項(xiàng)按關(guān)鍵字字段有序，可用順序查找或折半查找），然后，再對該分塊進(jìn)行順序查找。11.3動(dòng)態(tài)查找表——二叉排序樹動(dòng)態(tài)查找表的特點(diǎn)是表結(jié)構(gòu)本身在查找過程中動(dòng)態(tài)生成，即對給定的關(guān)鍵字key，若表中存在其關(guān)鍵字等于key的記錄，則查找成功返回，否則插入關(guān)鍵字等于key的記錄。二叉排序樹（BinarySortTree）可以是一棵空二叉樹；當(dāng)它非空時(shí)，是滿足下列性質(zhì)的二叉樹：（1）若左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；若右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值。（2）左右子樹也都是二叉排序樹。11.3.1二叉排序樹查找過程:從其定義可見，二叉排序樹的查找過程如下。（1）若查找樹為空，查找失敗。（2）查找樹非空，將給定值kx與查找樹的根結(jié)點(diǎn)關(guān)鍵字比較。（3）若相等，查找成功，結(jié)束查找過程。11.3.2二叉排序樹插入操作設(shè)待插入結(jié)點(diǎn)的關(guān)鍵字為kx，為將其插入，先要在二叉排序樹中進(jìn)行查找。若查找成功，按二叉排序樹定義，不用插入；查找不成功時(shí)，則插入之。因此，新插入結(jié)點(diǎn)一定是作為葉子結(jié)點(diǎn)添加上去的。構(gòu)造一棵二叉排序樹則是逐個(gè)插入結(jié)點(diǎn)的過程。11.3.3二叉排序樹刪除操作和插入相反，刪除在查找成功之后進(jìn)行，而且要求在刪除二叉排序樹上某個(gè)結(jié)點(diǎn)之后，仍然保持二叉排序樹的特性。設(shè)待刪結(jié)點(diǎn)為*p（p為指向待刪結(jié)點(diǎn)的指針），其雙親結(jié)點(diǎn)為*f，分三種情況進(jìn)行討論。*p結(jié)點(diǎn)為葉結(jié)點(diǎn)，只需將被刪結(jié)點(diǎn)的雙親結(jié)點(diǎn)相應(yīng)指針域改為空指針。*p結(jié)點(diǎn)只有左子樹pl或右子樹pr。此時(shí)，只需用pl或pr替換*p結(jié)點(diǎn)即可。*p結(jié)點(diǎn)既有左子樹又有右子樹，可按中序遍歷保持有序進(jìn)行調(diào)整。11.3.4二叉排序樹的查找分析對于每一棵特定的二叉排序樹，均可按照平均查找長度的定義來求它的ASL值，顯然，由值相同的n個(gè)關(guān)鍵字，構(gòu)造所得的不同形態(tài)的各棵二叉排序樹的平均查找長度的值不同，甚至可能差別很大。例如，由關(guān)鍵字序列1，2，3，4，5構(gòu)造而得的二叉排序樹，ASL=（1+2+3+4+5）/5=3。由關(guān)鍵字序列3，1，2，5，4構(gòu)造而得的二叉排序樹，ASL=（1+2+3+2+3）/5=2.2對給定序列建立二叉排序樹，若左右子樹均勻分布，則其查找過程類似于有序表的折半查找。若給定序列有序，則建立的二叉排序樹就蛻化為單鏈表，其查找效率同順序查找一樣。因此對均勻的二叉排序樹進(jìn)行插入或刪除結(jié)點(diǎn)后，應(yīng)對其調(diào)整，使其依然保持均勻。11.4動(dòng)態(tài)查找表——平衡二叉樹平衡二叉樹或者是一棵空樹，或者是具有下列性質(zhì)的二叉排序樹：它的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹高度之差的絕對值不超過1。11.4.1左單旋轉(zhuǎn)調(diào)整策略：調(diào)整后的子樹除了各結(jié)點(diǎn)的平衡因子絕對值不超過1，還必須是二叉排序樹。由于結(jié)點(diǎn)c的左子樹D可作為結(jié)點(diǎn)a的右子樹，將結(jié)點(diǎn)a為根的子樹調(diào)整為左子樹是B，右子樹是D，再將結(jié)點(diǎn)a為根的子樹調(diào)整為結(jié)點(diǎn)c的左子樹，結(jié)點(diǎn)c為新的根結(jié)點(diǎn)。平衡化調(diào)整操作判定：沿插入路徑檢查三個(gè)點(diǎn)a、c、E，若它們處于“\”直線上的同一個(gè)方向，則要作左單旋轉(zhuǎn)，即以結(jié)點(diǎn)c為軸逆時(shí)針旋轉(zhuǎn)。11.4.2右單旋轉(zhuǎn)右單旋轉(zhuǎn)與左單旋轉(zhuǎn)類似，沿插入路徑檢查三個(gè)點(diǎn)a、c、E，若它們處于“/”直線上的同一個(gè)方向，則要作右單旋轉(zhuǎn)，即以結(jié)點(diǎn)c為軸順時(shí)針旋轉(zhuǎn)。11.4.3先左后右雙向旋轉(zhuǎn)下圖為插入前的子樹，根結(jié)點(diǎn)a的左子樹比右子樹高度高1，待插入結(jié)點(diǎn)x將插入到結(jié)點(diǎn)b的右子樹上，并使結(jié)點(diǎn)b的右子樹高度增1，從而使結(jié)點(diǎn)a的平衡因子的絕對值大于1，導(dǎo)致結(jié)點(diǎn)a為根的子樹平衡被破壞。11.4.3先左后右雙向旋轉(zhuǎn)11.4.4先右后左雙向旋轉(zhuǎn)先右后左雙向旋轉(zhuǎn)和先左后右雙向旋轉(zhuǎn)對稱。在平衡的二叉排序樹T上插入一個(gè)關(guān)鍵字為kx的新元素，遞歸算法可描述如下。（1）若T為空樹，則插入一個(gè)數(shù)據(jù)元素為kx的新結(jié)點(diǎn)作為T的根結(jié)點(diǎn)，樹的深度增1；（2）若kx和T的根結(jié)點(diǎn)關(guān)鍵字相等，則不進(jìn)行插入；（3）若kx小于T的根結(jié)點(diǎn)關(guān)鍵字，而且在T的左子樹中不存在與kx有相同關(guān)鍵字的結(jié)點(diǎn)，則將新元素插入在T的左子樹上，并且當(dāng)插入之后的左子樹深度增加1時(shí)，分別就下列情況進(jìn)行處理。11.5動(dòng)態(tài)查找表——B-樹和B+樹B-樹是一種平衡的多路查找樹，它在文件系統(tǒng)中很有用。B+樹是應(yīng)文件系統(tǒng)所需而產(chǎn)生的一種B-樹的變形樹。11.5.1B-樹的定義一棵m階的B-樹，可以為空樹，非空時(shí)是滿足下列特性的m叉樹：1）樹中每個(gè)結(jié)點(diǎn)至多有m棵子樹；2）若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，則至少有兩棵子樹；3）除根結(jié)點(diǎn)之外的所有非終端結(jié)點(diǎn)至少有m/2棵子樹；4）所有的非終端結(jié)點(diǎn)中包含以下信息數(shù)據(jù)：（n，A0，K1，A1，K2，…，Kn，An）11.5.2B-樹的查找類似二叉排序樹的查找，所不同的是B-樹每個(gè)結(jié)點(diǎn)上是多關(guān)鍵字的有序表，在到達(dá)某個(gè)結(jié)點(diǎn)時(shí)，先在有序表中查找，若找到，則查找成功；否則，到按照對應(yīng)的指針信息指向的子樹中去查找，當(dāng)?shù)竭_(dá)葉子結(jié)點(diǎn)時(shí)，則說明樹中沒有對應(yīng)的關(guān)鍵字，查找失敗。即在B-樹上的查找過程是一個(gè)順指針查找結(jié)點(diǎn)和在結(jié)點(diǎn)中查找關(guān)鍵字交叉進(jìn)行的過程。11.5.3B-樹上插入結(jié)點(diǎn)在B-樹上插入關(guān)鍵字與在二叉排序樹上插入結(jié)點(diǎn)不同，關(guān)鍵字的插入不是在葉結(jié)點(diǎn)上進(jìn)行的，而是在最底層的某個(gè)非終端結(jié)點(diǎn)中添加一個(gè)關(guān)鍵字，若該結(jié)點(diǎn)上關(guān)鍵字個(gè)數(shù)不超過m-1個(gè)，則可直接插入到該結(jié)點(diǎn)上；否則，該結(jié)點(diǎn)上關(guān)鍵字個(gè)數(shù)至少達(dá)到m個(gè)，因而使該結(jié)點(diǎn)的子樹超過了m棵，這與B-樹定義不符。所以要進(jìn)行調(diào)整，即結(jié)點(diǎn)的“分裂”。方法為：關(guān)鍵字加入結(jié)點(diǎn)后，將結(jié)點(diǎn)中的關(guān)鍵字分成三部分，使得前后兩部分關(guān)鍵字個(gè)數(shù)均大于等于，而中間部分只有一個(gè)結(jié)點(diǎn)。前后兩部分成為兩個(gè)結(jié)點(diǎn)，中間的一個(gè)結(jié)點(diǎn)將其插入到父結(jié)點(diǎn)中。若插入父結(jié)點(diǎn)而使父結(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù)超過m-1，則父結(jié)點(diǎn)繼續(xù)分裂，直到插入某個(gè)父結(jié)點(diǎn)，其關(guān)鍵字個(gè)數(shù)小于m。可見，B-樹是從底向上生長的。11.5.4B-樹上刪除結(jié)點(diǎn)分兩種情況：（1）刪除最底層結(jié)點(diǎn)中關(guān)鍵字（2）刪除為非底層結(jié)點(diǎn)中關(guān)鍵字11.5.5B+樹一棵m階的B+樹和m階的B-樹的差異在于：（1）有n棵子樹的結(jié)點(diǎn)中含有n個(gè)關(guān)鍵字；（2）所有的葉子結(jié)點(diǎn)中包含了全部關(guān)鍵字的信息，及指向含有這些關(guān)鍵字記錄的指針，且葉子結(jié)點(diǎn)本身依關(guān)鍵字的大小自小而大的順序鏈接；（3）所有的非終端結(jié)點(diǎn)可以看成是索引部分，結(jié)點(diǎn)中僅含有其子樹根結(jié)點(diǎn)中最大（或最小）關(guān)鍵字。11.5.5B+樹11.6哈希表前面討論的查找方法，由于數(shù)據(jù)元素的存儲(chǔ)位置與關(guān)鍵字之間不存在確定的關(guān)系，因此查找時(shí)，需要進(jìn)行一系列對關(guān)鍵字的查找比較，即“查找算法”是建立在比較的基礎(chǔ)上的，查找效率由比較一次縮小的查找范圍決定。理想的情況是不經(jīng)過任何比較，一次存取便能得到所查記錄，即要求關(guān)鍵字與數(shù)據(jù)元素間存在一一對應(yīng)關(guān)系，通過這個(gè)關(guān)系，能很快地由關(guān)鍵字得到對應(yīng)的數(shù)據(jù)元素位置。11.6.1哈希表與哈希方法選取某個(gè)函數(shù)，依該函數(shù)按關(guān)鍵字計(jì)算元素的存儲(chǔ)位置，并按此存放；查找時(shí)，由同一個(gè)函數(shù)對給定值kx計(jì)算地址，將kx與地址單元中元素關(guān)鍵字進(jìn)行比，確定查找是否成功，這就是哈希方法(雜湊法)；哈希方法中使用的轉(zhuǎn)換函數(shù)稱為哈希函數(shù)(雜湊函數(shù))；按這個(gè)思想構(gòu)造的表稱為哈希表(雜湊表)。對于n個(gè)數(shù)據(jù)元素的集合，總能找到關(guān)鍵字與存放地址一一對應(yīng)的函數(shù)。若最大關(guān)鍵為m，可以分配m個(gè)數(shù)據(jù)元素存放單元，選取函數(shù)f(key)=key即可，但這樣會(huì)造成存儲(chǔ)空間的很大浪費(fèi)，甚至不可能分配這么大的存儲(chǔ)空間。通常關(guān)鍵字的集合比哈希地址集合大得多，因而經(jīng)過哈希函數(shù)變換后，可能將不同的關(guān)鍵字映射到同一個(gè)哈希地址上，這種現(xiàn)象稱為沖突（Collision），映射到同一哈希地址上的關(guān)鍵字稱為同義詞。可以說，沖突不可能避免，只能盡可能減少。11.6.2常用的哈希函數(shù)下面介紹幾種構(gòu)造哈希函數(shù)常用的方法，重點(diǎn)掌握直接定址法和除留余數(shù)法。1．直接定址法2．除留余數(shù)法3．?dāng)?shù)字分析法4．平方取中法5．折疊法（Folding）11.6.3處理沖突的方法在哈希函數(shù)中，當(dāng)取不同的key值時(shí)，卻得到相同的函數(shù)值，沖突就產(chǎn)生了，那么如何處理這種沖突呢？最基本的處理沖突的方法是：開放定址法、再哈稀法和拉鏈法。前者是將所有結(jié)點(diǎn)均存放在散列表T[0..m-1]中；后者通常是將互為同義詞的結(jié)點(diǎn)鏈成一個(gè)單鏈表，而將此鏈表的頭指針放在散列表T[0..m-1]中。1．開放定址法2．再哈希法3．拉鏈法11.6.4哈希表的查找分析哈希表的查找過程基本上和造表過程相同。一些關(guān)鍵字可通過哈希函數(shù)轉(zhuǎn)換的地址直接找到，另一些關(guān)鍵字在哈希函數(shù)得到的地址上產(chǎn)生了沖突，需要按處理沖突的方法進(jìn)行查找。在介紹的三種處理沖突的方法中，產(chǎn)生沖突后的查找仍然是給定值與關(guān)鍵字進(jìn)行比較的過程。所以，對哈希表查找效率的量度，依然用平均查找長度來衡量。查找過程中，關(guān)鍵字的比較次數(shù)，取決于產(chǎn)生沖突的多少，產(chǎn)生的沖突少，查找效率就高，產(chǎn)生的沖突多，查找效率就低。因此，影響產(chǎn)生沖突多少的因素，也就是影響查找效率的因素。影響產(chǎn)生沖突多少有以下三個(gè)因素：哈希函數(shù)是否均勻、處理沖突的方法及哈希表的裝填因子。11.7算法設(shè)計(jì)舉例下面給出二叉排序樹、哈希表應(yīng)用的算法設(shè)計(jì)，提高利用計(jì)算機(jī)分析解決綜合性實(shí)際問題的基本能力；鍛煉個(gè)人動(dòng)手能力，歷練自身素質(zhì)。11.7.1構(gòu)造二叉排序樹實(shí)現(xiàn)以二叉排序樹為例，設(shè)計(jì)一個(gè)有關(guān)動(dòng)態(tài)查找表的建立、查找、插入和刪除