基本概念與術語

8.1

基本概念與術語

8.2靜態(tài)查找表8.3動態(tài)查找表8.4哈希表查找8.5小結與習題第八章查找1本章主要內容本章主要學習靜態(tài)查找和動態(tài)查找方法。靜態(tài)查找包括順序查找、二分查找和分塊索引查找等，動態(tài)查找包括二叉排序樹、B樹等。作為重點內容本章還介紹了哈希查找及相關知識。查找是數(shù)據(jù)結構中的重要操作，好的查找方法會大大提高執(zhí)行效率。通過本章學習，應掌握以下內容：

查找的有關概念；

靜態(tài)查找；

動態(tài)查找；

哈希查找。

2查找就是指在給定的一組數(shù)據(jù)中對某個數(shù)值進行查詢的過程。關鍵字是數(shù)據(jù)元素（或記錄）中某個項或組合項的數(shù)值，它可以標識一個數(shù)據(jù)元素或記錄。主關鍵字將能唯一確定一個數(shù)據(jù)元素（或記錄）的關鍵字。查找表是由具有相同類型的數(shù)據(jù)元素（或記錄）組成的集合。分為靜態(tài)查找表和動態(tài)查找表兩大類。如果查找表中能夠找到滿足條件的記錄，稱為查找成功，否則稱為查找不成功。8.1基本概念與術語3

靜態(tài)查找表：在對查找表進行操作時，不改變表的結構，只進行查找操作；

動態(tài)查找表：在對查找表進行操作時，可以改變該查找表的結構，既可以進行查找操作，又可以進行插入、刪除等操作。8.2靜態(tài)查找表8.2.1靜態(tài)查找表結構靜態(tài)查找表是由數(shù)據(jù)元素組成的線性表。其存儲結構分為順序存儲和鏈式存儲兩種。可以用順序表或線性鏈表來表示靜態(tài)查找表。48.2.1靜態(tài)查找表結構

typedefintKeyType;typedefstruct{KeyTypekey;………}ElemType;typedefstruct{ElemTypeelem[MAXSIZE+1]；intlength；}SST；

typedefstructNODE{ElemTypedata；/*結點的數(shù)據(jù)域*/

structNODE*next；/*指針域*/

}NodeType；靜態(tài)查找表的順序存儲結構定義靜態(tài)查找表的鏈式存儲結構定義58.2.2順序查找

順序查找又稱線性查找，它思路簡單、容易實現(xiàn)，是一種最基本的查找方法。其查找過程為：從查找表的一端開始，逐個進行關鍵字與查找值的比較，若某個記錄的關鍵字值與給定值相等，則查找成功，給出數(shù)據(jù)元素在查找表中的位置；若將整個表查找完，仍未找到與給定值相同的關鍵字，則查找失敗，給出提示信息。6【算法8.1】順序查找intSearch_Seq(SSTST，KeyTypex){

ST.elem[0].key=x;/*設置監(jiān)護哨*/

i=ST.length;while(ST.elem[i].key!=x)i--;/*返回找到記錄的下標或者0(查找不成功)*/

returni;}/*Search_Seq*/將查找過程中給定值和關鍵字比較的次數(shù)稱為查找長度。通常用平均查找長度ASL來衡量查找算法的優(yōu)劣。算法分析：7

平均查找長度：在查找成功時，平均查找長度ASL是指為確定數(shù)據(jù)元素在表中位置所進行關鍵字比較次數(shù)的期望值。對一個含n個數(shù)據(jù)元素的表，查找成功時

ASL=Pi*Ci

n∑i=1

Pi為表中第i個數(shù)據(jù)元素的查找概率，Ci為表中第i個數(shù)據(jù)元素的關鍵字與給定值x相等時，需要比較的次數(shù)。設查找表長度為n，查找元素x和表中第i個元素關鍵字相等時，需要比較的次數(shù)為n-i+1，則平均查找長度為：ASL=Pi*（n-i+1）n∑i=18

設查找表中各元素的查找概率相等，即Pi=1/n，則上面的式子表示為：

n∑i=1ASL=（n-i+1）=１─ｎｎ＋１───

２當查找成功時，順序查找的時間復雜度就是O(n)。

當查找失敗時，關鍵字與給定值的比較次數(shù)總是n+1次。8.2.3二分查找

二分查找，也稱為折半查找，是對有序表進行的一種高效率的線性查找。有序表是指數(shù)據(jù)元素按給定的關鍵字已經是升序（或者是降序）的查找表。9

假設各記錄的關鍵字是由小到大排序的，算法的實現(xiàn)過程為：在待查找的有序表中，將中間元素首先與給定值進行比較，若相等，則表示查找成功；若給定值小于中間元素的關鍵字，則在左邊的區(qū)域中繼續(xù)查找；若給定值大于中間元素的關鍵字，則在右邊的區(qū)域中繼續(xù)查找。重復上述過程，直到查找成功或者查找失敗，查找的過程隨之結束。例在給定的序列A={6，13，17，20，24，28，30，36，39，44，48，51，55}中查找給定值13和52這兩個數(shù)據(jù)。⑴查找關鍵字為13的過程10

6131720242830363944485155第一次

low=1

mid=7high=13因x<30，下一步繼續(xù)在左半?yún)^(qū)查找，即：

012345678910111213第二次

low=1mid=3high=6因x<17，下一步繼續(xù)在左半?yún)^(qū)查找，即：

012345678910111213

6131720242830363944485155

613172024283036394448515511因x>6，下一步繼續(xù)在右半?yún)^(qū)查找。此時，low=2,high=2,mid=(2+2)/2=2。由于x=13,查找成功，所找到的記錄序號為2。

⑵查找關鍵字為52的過程第一次

low=1

mid=7high=13因x>30，下一步繼續(xù)在右半?yún)^(qū)查找，即：

012345678910111213第二次

low=8

mid=10high=13因x>44，下一步繼續(xù)在右半?yún)^(qū)查找，即：

012345678910111213

6131720242830363944485155

613172024283036394448515512第三次

low=11high=13mid=12因x>51，下一步繼續(xù)在右半?yún)^(qū)查找，即：

012345678910111213

第四次

low=mid=high=13因x<55，下一步繼續(xù)在左半?yún)^(qū)查找，此時，low=13,high=12，因為low>high，所以查找失敗。

012345678910111213

6131720242830363944485155

613172024283036394448515513【算法8.2】二分查找intSearch_Bin(SSTST，KeyTypex){low=1；high=ST.length；while(low<=high)/*區(qū)間條件判斷*/{/*當區(qū)間下限不高于上限時，進行比較測試*/

mid=(low+high)/2；/*取中點*/

if(x<ST.elem[mid].key)

high=mid-1；/*查找區(qū)間縮小到左邊區(qū)域*/

elseif(x>ST.elem[mid].key)

low=mid+1；/*查找區(qū)間縮小到右邊區(qū)域*/

elsereturnmid;}returnERROR;}14算法分析：對于有序查找表，可采用建立二叉樹的方法：將表的中間元素作為二叉樹的根結點，比中間值小的所有結點全部在二叉樹的左子樹中，比中間值大的所有結點全部在二叉樹的右子樹中。按照這種思路建立的二叉樹稱為判定二叉樹。如圖所示。513928176445530244836132015時間復雜度：該算法的時間復雜度取決于該二叉樹中從根結點到該查找元素所在的結點的路徑上與中間結點的比較次數(shù)，即該元素結點在樹中的所在的層數(shù)。對于n個結點的判定樹，樹高為h，則有2h-1-1<n≤2h-1，即h-1<log2(n+1)≤h，所以h=int(log2(n+1))(int為取整函數(shù))。二分查找的平均查找長度（ASL）為：ASL=Pi*Ci

n∑i=1

=[1×20+2×21+…＋h×2h-1]=(n+1)n*log2(n+1)-1≈log2(n+1)-1所以，二分查找的時間復雜度為O(log2n)。168.2.4分塊查找二分查找適用于順序存儲的有序表查找，但并不是所有的查找表都是有序的。分塊查找又稱索引順序查找，其思想是先將查找表中的數(shù)據(jù)分成若干個塊，并為這若干個塊建立相應的索引表，查找時通過將表分塊操作而提高效率。索引表的值包括兩個部分：關鍵字和指針，其中關鍵字部分存放的是某子表中的最大關鍵字值，指針部分存放的是對應子表的起始位置，索引表中的表項必須以關鍵字字段有序排列。查找過程：首先查找索引表，確定關鍵字記錄所在的塊，然后在塊中順序查找。17【例8-2】設關鍵字集合為：96，40，12，33，81，4，58，45，39，64，18，85，17，57按關鍵字值33，58，96分為三個塊建立的查找表及其索引表。查找表索引表關鍵字字段

指針字段1335896611123341817405845395796816485說明：在分塊查找算法中，索引表中關鍵字的選取將對算法的優(yōu)劣度起到相當大的作用，若能夠使各子表中紀錄個數(shù)基本項等，則可以提高算法效率。188.3動態(tài)查找表動態(tài)查找表將在查找的過程中對記錄的關鍵字進行了插入或刪除等修改操作。8.3.1二叉排序樹

二叉排序樹屬動態(tài)查找方法?？筛鶕?jù)相應的二叉排序樹，實現(xiàn)對結點的查找。1．二叉排序樹定義二叉排序樹又稱為二叉查找樹，其定義是一個遞歸過程：它或者是一棵空樹；或者是具有下列性質定義的二叉樹：59409975986049578861919⑴若左子樹不空，則左子樹上所有結點的值均小于根結點的值；若右子樹不空，則右子樹上所有結點的值均大于或等于根結點的值。⑵左右子樹都分別是一棵二叉排序樹。5940997598604957886198.3.2二叉排序樹的建立1.二叉排序樹的建立：由空集為初始狀態(tài)，將結點按關鍵字依次插入到排序二叉樹中去。先將第一個結點作為二叉樹的根結點，插入其它結點時，若結點的值小于根結點的值，則插入左子樹，否則插入右子樹，該過程依次進行，直到整個過程結束。202.二叉排序樹的操作二叉排序樹的主要操作包括插入、查找、刪除等。(1)插入結點二叉排序樹插入結點的過程和二叉樹的建立過程中各結點的插入相似，即將一個元素插入到二叉排序樹中。(2)查找結點根據(jù)前面的定義可知，二叉排序樹的查找是一個遞歸的過程，具體如下：①若二叉排序樹為空，則查找失敗，輸出相關信息。②若二叉查找樹不為空，將給定值x與查找樹的根結點關鍵字進行比較。21否則，完成下面的判斷：(i)若給定的值x小于根結點關鍵字的值，查找將按照遞歸的方式在左子樹上進行。(ii)若給定的值x大于根結點關鍵字的值，查找將按照遞歸的方式在右子樹上進行。(iii)重復以上過程，直到查找結束（成功或者失敗）。③若比較結果為相等，則查找成功，整個查找結束。22(3)刪除結點：當刪除一個結點之后，原二叉樹的結構可能發(fā)生變化，需要將其進行相應的調整。使其保持二叉排序樹的性質。設準備刪除的結點為p，其雙親結點為f，以下分三種情況進行討論。(1)若結點p為葉子結點，刪去葉子結點后不影響整棵樹的特性，所以，只需將被刪除結點的雙親結點相應指針域改為空指針。fpf刪除的結點為葉子結點的情況23(2)若結點p為非葉子結點，假設只有右子樹pr或只有左子樹pl，此時，只需將pr或pl替換f結點的p結點即可。如圖8-5所示。fpfpl刪除的結點p只有左子樹plfpfpr刪除的結點p只有右子樹pr24(3)若結點p既有左子樹pl又有右子樹pr，可按中序遍歷保持有序的原則進行調整。調整方法有：①直接令pl為*r相應的子樹，以pr為pl中序遍歷的最后一個結點pk的右子樹；②令p結點的直接前驅pr或直接后繼（對pl子樹中序遍歷的最后一個結點pk）替換p結點，再按②的方法刪去pr或pk。

對給定序列建立二叉排序樹時，若左右子樹分布均勻，則能提高查找效率。因此，對均勻的二叉排序樹進行插入或刪除結點后，應對其進行調整，使其依然保持均勻。25(a)fpplprclslqlsrfclplslqlprsr（3）若結點p既有左子樹pl又有右子樹pr，如圖（a）所示，可按照中序遍歷保持有序的原則進行調整。調整方法有以下兩種：1）

直接使左子樹pl為f的左子樹，再使pr為子樹pl中序遍歷最后一個結點的右子樹，如圖（b）所示。2）

26將p結點的直接前驅（或直接后繼）替換結點p，然后再從二叉排序樹中刪除它的直接前驅（或直接后繼），如圖（c）所示。fsrprclplslql(c)27【例8-3】記錄的關鍵字序列為：60，94，74，57，69，41，99，85，13，48，59，則構造一棵二叉排序樹的過程如圖所示。6060947494607494605774946057697494605769417494605769419974946035769859941749460576985991341419974946048578569135941997494604857856913φ28【算法8.3】二叉排序樹的查找BTNode*BST_search(BTNode*t,intx)/*二叉排序樹的查找*/{BTNode*p=t;/*t為根結點*/

f=NULL;while(p!=NULL){if(x==p->key)returnp;/*查找結束*/

elseif(x<p->key){f=p;p=p->lchild;}/*在左子樹上查找*/

else{f=p;p=p->rchild;}

}/*在右子樹上查找*/

returnNULL;}29【算法8.4】二叉排序樹的建立BTNode*BST_Insert(BTNode*t,intx)/*在二叉排序樹上執(zhí)行插入操作*/{BTNode*s,*p=BST_search(t,x);if(p==NULL){s=(BTNode*)malloc(sizeof(BTNode));s->key=x;s->lchild=s->rchild=NULL;if(t==NULL)t=s;elseif(x<f->key)

f->lchild=s;/*生成左孩子*/

elsef->rchild=s;/*生成右孩子*/

}

returnt;}308.3.3平衡二叉樹（AVL樹）平衡二叉樹(BalancedBinaryTree)指的是形態(tài)勻稱的二叉樹，其定義是一個遞歸過程：它或是一棵空樹，或者是具有下列性質的二叉排序樹：它的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹高度之差的絕對值不超過1220054854960770100031對于非平衡二叉排序樹，希望通過適當調整，使其成為平衡二叉樹，設A結點為失去平衡的最小子樹根結點，對該子樹進行平衡化調整歸納起來有以下四種情況：1.LL型平衡旋轉當在A的左子樹上插入結點，使A的平衡因子由1增至2而失去平衡，因此需要進行一次順時針旋轉操作。如圖8-9(a)所示。AB1插入前，平衡AB2C插入結點，失去平衡AB0C順時針旋轉后，平衡322.RR型平衡旋轉由于在A的右子樹上插入結點，使A的平衡因子由-1增至-2而失去平衡，因此需要進行一次逆時針旋轉操作。如圖所示。AB-1插入前平衡AB-2C插入結點失去平衡CB0A逆時針旋轉后平衡333.LR型平衡旋轉由于在A的左子樹的右子樹上插入結點，使A的平衡因子由1增至2而失去平衡，因此需要進行兩次旋轉（先逆時針旋轉，再順時針旋轉）操作。如圖8-9(c)所示。AB1插入前平衡AC0B順時針旋轉使其平衡AB2C插入結點失去平衡AC2以C為軸逆時針旋轉B344.RL型平衡旋轉由于在A的右子樹的左子樹上插入結點，使A的平衡因子由-1增至-2而失去平衡，因此需要進行兩次旋轉（先順時針旋轉，再逆時針旋轉）操作。如圖8-9(d)所示。-1插入前平衡ABAB-2CBC0A插入結點失去平衡逆時針旋轉使平衡AC-2以C為軸順時針旋轉B35【例8-4】設有數(shù)據(jù)序列{63，90，70，55，67，42，98}，試用這組數(shù)建立平衡二叉排序樹，如圖8-10所示。636390639070709063709063557090635567709063556742(e)

(f)

(g)失去平衡36(h)調整平衡(i)結束67906355704267906355704298平衡二叉樹的查找分析：在查找過程中將給定值進行比較的關鍵字個數(shù)不超過樹的深度。因此，在平衡樹上進行查找的時間復雜度為O(log2n)。(等概率的提前下進行的)378.3.4B樹如果查找需要在外存儲器上進行，需要使用外部查找方法。1.B樹的定義一棵m階的B樹，或者為空樹，或為滿足下列特性的m叉樹：⑴樹中每個結點至多有m棵子樹；⑵除非根結點為葉子結點，否則至少有兩棵子樹；⑶除根結點之外的所有非終端結點至少有m/2

棵子樹；⑷所有的非終端結點中包含以下信息數(shù)據(jù)：（n，A0，K1，A1，K2，…，Kn，An）38

其中：Ki（i=1,2,…,n）為關鍵字，且Ki<Ki+1，Ai為指向子樹根結點的指針(i=0,1,…,n)，且指針Ai-1所指子樹中所有結點的關鍵字均小于Ki(i=1,2,…,n)，An所指子樹中所有結點的關鍵字均大于Kn，m/2

1≤n≤m1，n為關鍵字的個數(shù)。⑸所有的葉子結點都出現(xiàn)在同一層次上，并且不帶信息。1L2DG3OSW3∧A∧B∧C∧2∧E∧F∧2∧H∧K∧2∧M∧N∧3∧P∧Q∧R∧3∧T∧U∧V∧3∧X∧Y∧Z∧圖8-11一棵5階的B-樹392．B樹基本操作

B樹的基本操作也是查找、插入和刪除等操作。現(xiàn)以B樹查找為例做簡單介紹。B樹的查找類似二叉排序樹的查找，所不同的是B樹每個結點上是多關鍵字的有序表，在到達某個結點時，先在有序表中查找，若找到，則查找成功；否則，按照對應的指針信息指向的子樹中去查找，當?shù)竭_葉子結點時，則說明樹中沒有對應的關鍵字，查找失敗?？梢姡珺樹上進行查找的過程是一個順指針查找結點和在結點的關鍵字中進行查找交叉進行的過程。408.4哈希表查找8.4.1哈希表與哈希方法前面介紹的查找算法基本上都是建立在“比較”的基礎上。而數(shù)據(jù)元素的存儲位置與關鍵字之間不存在確定的關系，查找效率由每次比較縮小的查找范圍決定。哈希表（Hash）是由哈希函數(shù)生成的表示關鍵字與存儲位置之間關系的表。哈希函數(shù)是一個以關鍵字值為自變量，在關鍵字值與記錄存儲位置之間建立確定關系的函數(shù)。哈希函數(shù)的值，就是指定關鍵字對應的存儲地址。41【例8-5】設有11個記錄的關鍵字，其值分別為6，37，12，21，69，31，16，33，41，13，51。選取關鍵字與記錄位置間的函數(shù)為Hash(key)=key%11建立的哈希查找表如下：331213693716651413121對于n個數(shù)據(jù)元素的集合，總能找到關鍵字與存放地址一一對應的函數(shù)。但當key1≠key2，而Hash(key1)=Hash(key2)時，即將不同的關鍵字映射到同一個哈希地址上，這種現(xiàn)象稱為沖突，映射到同一哈希地址上的關鍵字稱為同義詞?？梢哉f，沖突是不可能避免的，只能盡可能減少。因此選取適當?shù)墓：瘮?shù)很關鍵。428.4.2常用的哈希函數(shù)1.直接定址法

Hash(key)=a*key+b(a、b為常數(shù))直接地址法取關鍵字的某個線性函數(shù)值為哈希地址?！纠?-6】

解放后，某農作物年產量(單位：噸)序列為下表：1950年1951年1952年1953年1954年1955年……160萬240萬360萬540萬810萬1006萬……若選取哈希函數(shù)：

Hash(key)=key-1950，其中key取“年份”，則建立的哈希查找表如下：012345……195019511952195319541955……1602403605408101006……432.除留余數(shù)法

Hash(key)=key%p(p是一個整數(shù))即取關鍵字除以p的余數(shù)作為哈希地址。使用除留余數(shù)法，選取合適的p很重要，若哈希表表長為m，一般選取p≤m的質數(shù)。【例8-7】關鍵字集合為{34，21，78，52，16，46，33}，構造哈希函數(shù)。選取哈希函數(shù)為Hash(key)=key%7，則存放如下：21781652463334

0123456443.數(shù)字分析法設關鍵字集合中，每個關鍵字均由m位組成，每位上可能有r種不同的符號。數(shù)字分析法根據(jù)r種不同的符號，在各位上的分布情況，選取某幾位，組合成哈希地址。所選的位應使各種符號在該位上出現(xiàn)的頻率大致相同?！纠?-8】有一組關鍵字如下：

2

7

40364

2

7

61487

2

7

52496

2

7

55470

2

7

57305分析：第1、2位均是“2和7”，第3位也只有“4、5、6”，因此，這幾位不能用，余下四位分布較均勻，可作為哈希地址選用。454.平方取中法對關鍵字平方后，按哈希表大小，取中間的若干位作為哈希地址?！纠?-9】設有如下關鍵字序列{0100，0110，1010，1001，0111}，采用平方取中法建立哈希表。關鍵字平方取值0100001000010001100012100121101010201002011001100200102001110012321123則該關鍵字序列對應的地址值分別為{100，121，201，020，123}。468.4.3處理沖突的方法1.開放定址法：當由關鍵字得到的哈希地址發(fā)生了沖突，即該地址已經存放了某數(shù)據(jù)元素時，就自動尋找下一個空的內存地址，只要哈希表足夠大，總能找到一個位置，將數(shù)據(jù)元素存入。

(1)線性探測法

Hi=(Hash(key)+di)%m(1≤i<m)其中：Hash(key)為哈希函數(shù)，m為哈希表長度，di

為增量序列1，2，……，m-1，且di=i【例8-11】關鍵字集為{47，7，29，11，16，92，22，8，3}，哈希表表長為11，

Hash(key)=key%11，用線性探測法處理沖突，如下所示：0123456789101122

47921637298

47存儲元素47、7后，再存儲29時，Hash(29)=7，哈希地址上沖突，由H1=(Hash(29)+1)%11=8，哈希地址8為空，將29存入；線性探測法可能使第i個哈希地址的同義詞存入第i+1個哈希地址，這樣本應存入第i+1個哈希地址的元素變成了第i+2個哈希地址的同義詞，……，因此，可能出現(xiàn)很多元素在相鄰的哈希地址上“堆積”起來，大大降低了查找效率?？刹捎枚翁綔y法，或雙哈希函數(shù)探測法，以改善“堆積”問題。0123456789101122

47921637298

48

(2)二次探測法

Hi=(Hash(key)±di)modm其中：Hash(key)為哈希函數(shù)，m為哈希表長度，通常取m為4k+3的質數(shù)，di

為增量序列12，-12，22，-22，……，q2，-q2且q≤(m-1)/2

當對例8-11使用二次探測法處理沖突時，如果已經將前8個數(shù)都存入相應的位置，