數(shù)據(jù)結構課件：查找

查找10.1查找的基本概念10.2靜態(tài)查找表10.3動態(tài)查找表10.4哈希表10.5本章小結查找是對數(shù)據(jù)進行操作或處理時經(jīng)常使用的操作。查找就是在一個數(shù)據(jù)元素集合中查找關鍵字等于某個給定關鍵字的數(shù)據(jù)元素。在一個數(shù)據(jù)元素集合中進行查找的方法很多，主要有順序表查找、索引表查找、樹表查找和哈希表查找。查找算法的優(yōu)劣對計算機應用系統(tǒng)的效率影響很大。

查找是在數(shù)據(jù)元素集合中查找是否存在關鍵字等于某個給定關鍵字數(shù)據(jù)元素的過程。查找也稱作檢索。

在計算機應用系統(tǒng)中使用查找的地方有許多，如在高考學生錄取系統(tǒng)中的高考學生成績表中查找考生號碼等于某個值的考生成績，或查找、統(tǒng)計總分超過某個數(shù)值的考生人數(shù)等。10.1查找的基本概念在第9章我們討論過，關鍵字有主關鍵字和次關鍵字。主關鍵字是能夠惟一區(qū)分各個不同數(shù)據(jù)元素的關鍵字，次關鍵字通常不能惟一區(qū)分各個不同數(shù)據(jù)元素。以主關鍵字進行的查找是最經(jīng)常、也是最主要的查找。

在一個數(shù)據(jù)元素集合中查找關鍵字等于某個給定關鍵字的過程有兩種結果：查找成功和查找不成功。查找成功是指在數(shù)據(jù)元素集合中找到了要查找的數(shù)據(jù)元素。查找不成功是指在數(shù)據(jù)元素集合中沒有找到要查找的數(shù)據(jù)元素。查找有靜態(tài)查找和動態(tài)查找兩種。靜態(tài)查找是指只在數(shù)據(jù)元素集合中查找是否存在關鍵字等于某個給定關鍵字的數(shù)據(jù)元素。動態(tài)查找是指在查找過程中同時插入數(shù)據(jù)元素集合中不存在的數(shù)據(jù)元素，或者從數(shù)據(jù)元素集合中刪除已存在的某個數(shù)據(jù)元素。

我們把靜態(tài)查找時構造的存儲結構稱作靜態(tài)查找表，把動態(tài)查找時構造的存儲結構稱作動態(tài)查找表。此外，哈希表是一種既適用于靜態(tài)查找問題也適用于動態(tài)查找問題的查找表。

和第9章討論的排序問題類同，在各種具體的查找問題中，雖然不同數(shù)據(jù)元素的數(shù)據(jù)域差別很大，但查找算法只與數(shù)據(jù)元素的關鍵字有關，與其他域無關。不失一般性，我們定義查找算法的數(shù)據(jù)元素中只包含關鍵字域，其數(shù)據(jù)類型為抽象數(shù)據(jù)類型KeyType。因此，我們定義查找算法中數(shù)據(jù)元素的抽象數(shù)據(jù)類型DataType為如下結構體：typedefstruct

{

KeyTypekey;

}DataType;在本章的例子中，我們都定義KeyType為int類型。衡量查找算法效率的最主要標準是平均查找長度。平均查找長度是指查找過程所需進行的關鍵字比較次數(shù)的平均值。平均查找長度通常記做ASL，其數(shù)學定義為

其中，Pi是要查找數(shù)據(jù)元素的出現(xiàn)概率，Ci是查找相應數(shù)據(jù)元素需進行的關鍵字比較次數(shù)。

查找成功和查找失敗的平均查找長度通常不同。查找成功時的平均查找長度用ASL成功表示，查找失敗時的平均查找長度用ASL失敗表示。

靜態(tài)查找表主要有順序表、有序順序表和索引順序表三種結構。10.2靜態(tài)查找表10.2.1順序表

在順序表上查找的基本思想是：從順序表的一端開始，用給定數(shù)據(jù)元素的關鍵字逐個和順序表中各數(shù)據(jù)元素的關鍵字比較，若在順序表中查找到要查找的數(shù)據(jù)元素則查找成功，函數(shù)返回該數(shù)據(jù)元素在順序表中的位置；否則查找失敗，函數(shù)返回-1。順序表上的查找算法如下：＃include"SeqList.h"

intSeqSearch(SeqListS，DataTypex)

{

inti＝0;

while(i<S.size&&S.list［i］.key!＝x.key)i＋＋;

if(S.list［i］.key＝＝x.key)returni;

elsereturn-1;

}設要查找的數(shù)據(jù)元素在數(shù)據(jù)元素集合中出現(xiàn)的概率均相等，則順序表查找算法查找成功時的平均查找長度ASL成功為

順序表查找算法查找失敗時的平均查找長度ASL失敗為

一個完整的測試主函數(shù)設計如下：＃include<stdio.h>

typedefintKeyType;

typedefstruct

{

KeyTypekey;

}DataType;

＃defineMaxSize100

＃include"SeqList.h"

intSeqSearch(SeqListS，DataTypex)

{

inti＝0;

while(i<S.size&&S.list［i］.key!＝x.key)i＋＋;

if(S.list［i］.key＝＝x.key)returni;

elsereturn-1;

}

voidmain(void)

{

SeqListmyS＝{{710，342，45，686，6，841，429，134，68，264}，10};

DataTypex＝{686};

inti;

if((i＝SeqSearch(myS，x))!＝-1)

printf("該數(shù)據(jù)元素位置為%d"，i);

else

printf("查找失敗");

}該程序的運行結果為：

該數(shù)據(jù)元素位置為310.2.2有序順序表

有序順序表上的查找算法主要有順序查找和二分查找兩種方法。

1.順序查找

有序順序表上的順序查找算法和10.2.1節(jié)討論的順序表上的查找算法方法類同，但不需要比較完所有數(shù)據(jù)元素就可判斷出要查找的數(shù)據(jù)元素是否不在數(shù)據(jù)元素集合中。例如設有序順序表的數(shù)據(jù)元素集合為{2，4，6，8，10}，要查找的數(shù)據(jù)元素為5，當順序和值為6的數(shù)據(jù)元素比較完后就可判定數(shù)據(jù)元素集合中不存在要查找的數(shù)據(jù)元素5。有序順序表上的順序查找算法如下：intOrderSeqSearch(SeqListS，DataTypex)

{

inti＝0;

while(i<S.size&&S.list［i］.key<x.key)i＋＋;

if(S.list［i］.key＝＝x.key)returni;

elsereturn-1;

}設要查找的數(shù)據(jù)元素在數(shù)據(jù)元素集合中出現(xiàn)的概率均相等，則有序順序表上順序查找算法查找成功時的平均查找長度ASL成功為

有序順序表上的順序查找算法查找失敗時的平均查找長度ASL失敗為

可見，當查找成功時，有序順序表上順序查找算法的平均查找長度和順序表上查找算法的平均查找長度相同；但當查找不成功時，有序順序表上順序查找算法的平均查找長度約是順序表上查找算法平均查找長度的1/2。

2.二分查找

有序順序表上二分查找算法的基本思想是：在一個查找區(qū)間，確定出查找區(qū)間的中心位置，用待查找數(shù)據(jù)元素的關鍵字和中心位置上數(shù)據(jù)元素的關鍵字比較，若兩者相等則查找成功；否則若前者小于后者，則把查找區(qū)間定為原查找區(qū)間的前半段繼續(xù)循環(huán)；否則若前者大于后者，則把查找區(qū)間定為原查找區(qū)間的后半段繼續(xù)循環(huán)。這樣的循環(huán)過程一直進行到查找區(qū)間的上界小于查找區(qū)間的下界為止。由于二分查找算法每次比較后都把查找區(qū)間折半，所以該算法也稱作折半查找算法。有序順序表上二分查找算法如下：＃include"SeqList.h"

intBinarySearch(SeqListS，DataTypex)

{

intlow＝0，high＝S.size-1;/*確定初始查找區(qū)間上下界*/

intmid;

while(low<＝high)

{

mid＝(low＋high)/2;/*確定初始查找區(qū)間中心位置*/

if(S.list［mid］.key＝＝x.key)returnmid;/*查找成功*/

elseif(S.list［mid］.key<x.key)low＝mid＋1;

elseif(S.list［mid］.key>x.key)high＝mid-1;

}

return-1;/*查找失敗*/

}對于一個有n個數(shù)據(jù)元素的有序順序表，顯然，二分查找算法對應了一棵完全二叉樹，其根結點數(shù)值為n，對應了初始的查找區(qū)間；每一個二叉分支結點數(shù)值為雙親結點數(shù)值除2，對應了每次比較后查找區(qū)間都會折半；所有葉結點是數(shù)值為1的結點，對應了最后一次比較時的查找區(qū)間。假設有序表中的數(shù)據(jù)元素個數(shù)n恰好是滿二叉樹時的結點個數(shù)，即有

則相應的二叉樹深度為

k＝lb(n＋1)

在滿二叉樹的第i層上總共有2

i-1個結點，查找該層上的每個結點需要進行的比較次數(shù)和該結點所在層的深度相同。因此，當有序順序表中每個數(shù)據(jù)元素的查找概率相等時，查找成功的平均查找長度為

當有序順序表中每個數(shù)據(jù)元素的查找概率相等時，查找失敗的平均查找長度為10.2.3索引順序表

當順序表中的數(shù)據(jù)元素個數(shù)非常大時，無論使用前述的哪種查找算法都需要很長的時間。此時提高查找速度的一個常用方法是再在順序表上建立索引表。索引表和我們通常使用的教科書前面的索引在用途和構造方法上類同。我們把要在其上建立索引表的順序表稱作主表。主表中存放著數(shù)據(jù)元素的全部信息，索引表中只存放主表中要查找數(shù)據(jù)元素的主關鍵字和索引信息。圖10-1是一個主表和一個按關鍵字key建立的索引表的結構圖。作為示意，我們只給出了主表中的key域值，其他的域名和域值均未給出。索引表中的數(shù)據(jù)元素由兩個域構成，key域為被索引的若干個數(shù)據(jù)元素中關鍵字的最大值，link域為被索引的若干個數(shù)據(jù)元素中第一個數(shù)據(jù)元素的下標序號。

圖10-1索引表結構圖要使索引表的查找效率高，索引表必須有序。但主表中的數(shù)據(jù)元素不一定也要按關鍵字有序。這是因為有些問題中，主表中的數(shù)據(jù)元素按關鍵字有序是一個實現(xiàn)起來需要花費較多時間的要求。此時可以將此要求放寬為，主表中的數(shù)據(jù)元素按關鍵字分段有序。此時索引表中的key域為被索引的若干個數(shù)據(jù)元素中關鍵字的最大值。圖10-1的索引表結構就是一個主表中的數(shù)據(jù)元素按關鍵字分段有序的例子。此時雖然主表只是分段有序，但索引表卻是有序表，對索引表上的索引項的查找可使用有序順序表的查找算法。

當只在主表上建立一個索引表時，滿足上述建立索引表要求的主表關鍵字有序或分段有序是很容易的。但是，當要在主表上再建立若干個次關鍵字的索引表時，要按所有索引表的要求對主表排序或部分排序就是不可能的，因為不同的關鍵字排序結果會完全不相同。此時，建立索引表的一般方法是先在主表上建立一個和主表項完全相同，但只包含索引關鍵字和該數(shù)據(jù)元素在主表中位置信息的稱作完全索引表的索引表，再在完全索引表上建立索引表。圖10-2給出了這種帶完全索引表的索引表結構圖。圖中完全索引表link域到主表位置的索引關系只象征性地畫出了一條，其余的未畫出。

圖10-2帶完全索引表的索引表結構圖當主表中的數(shù)據(jù)元素個數(shù)非常龐大時，索引表本身可能也很龐大，此時可按照建立索引表的同樣方法對索引表再建立索引表，這樣的索引表稱作二級索引表。同樣的方法還可以對二級索引表再建立三級索引表等。二級以上的索引結構稱作多級索引結構。

以上給出的索引表例子都是等長索引表的例子，即索引表中的每個索引項對應主表中的數(shù)據(jù)元素個數(shù)是相等的，如圖10-2中的每個索引項對應主表中的5個數(shù)據(jù)元素。索引表中的索引項對應主表中的數(shù)據(jù)元素個數(shù)也可以是不相等的，這種索引表稱作不等長索引表。圖10-3是一個不等長索引表結構圖。不等長索引表要增加一個數(shù)據(jù)域存放各個索引項的長度值。

不等長索引表不僅適用于靜態(tài)查找問題，而且適用于動態(tài)查找問題。這是因為不等長索引表中的索引長度可隨著動態(tài)插入和刪除改變。

索引順序表上的查找過程包括了索引表上的查找和主表上的查找兩部分。由于索引表是有序順序表，所以各種有序順序表上的查找算法都適用于索引表上的查找。主表上的查找算法可以根據(jù)關鍵字有序或部分有序選用前面所述的相應算法。

圖10-3不等長索引表結構圖索引順序表上查找算法的比較次數(shù)等于索引表上查找的比較次數(shù)加上主表中某個子表上查找的比較次數(shù)。假設索引表的長度為m，主表中每個子表的長度為s，并假設在索引表上和在主表上均采用順序查找算法，則索引順序表上查找算法的平均查找長度為

動態(tài)查找表主要有二叉樹結構和樹結構兩種類型。二叉樹結構有二叉排序樹、平衡二叉樹等。樹結構有B-樹、B

＋樹等。本節(jié)我們討論二叉排序樹和B-樹。10.3動態(tài)查找表10.3.1二叉排序樹

1.二叉排序樹的基本概念

二叉排序樹或者是一棵空樹，或者是具有下列性質的二叉樹：

(1)若左子樹不空，則左子樹上所有結點的值均小于根結點的值；

(2)若右子樹不空，則右子樹上所有結點的值均大于等于根結點的值；

(3)每個左右子樹也分別為二叉排序樹。

圖10-4所示就是一棵二叉排序樹。

圖10-4二叉排序樹由定義和例子都可知，一棵二叉排序樹一定是一棵二叉樹。二叉排序樹通常采用二叉鏈存儲結構，其結點的結構體定義如下：typedefstructnode

{

DataTypedata;

structnode*leftChild;

structnode*rightChild;

}

BiTreeNode;二叉排序樹上的操作主要有查找、插入和刪除操作。

2.二叉排序樹上的查找算法

查找就是遍歷二叉排序樹并在遍歷過程中尋找要查找的數(shù)據(jù)元素是否存在的過程。在二叉排序樹上查找某個數(shù)據(jù)元素是否存在的過程和在有序順序表中查找某個數(shù)據(jù)元素是否存在的過程非常相似。相應的，在二叉排序樹上查找某個數(shù)據(jù)元素是否存在的算法也有循環(huán)結構算法和遞歸結構算法兩種。這里我們給出循環(huán)結構的查找算法。intSearch(BiTreeNode*root，DataTypeitem)

{

BiTreeNode*p;

if(root!＝NULL)

{

p＝root;

while(p!＝NULL)

{

if(p->data.key＝＝item.key)return1;/*查找成功*/

if(item.key>p->data.key)p＝p->rightChild;

elsep＝p->leftChild;

}

}

return0;/*查找失敗*/

}3.二叉排序樹上的插入算法

二叉排序樹上的插入操作要求首先查找數(shù)據(jù)元素是否已在二叉排序樹中存在，若已存在則不插入，若不存在則把該數(shù)據(jù)元素插入到在二叉排序樹上查找失敗時結點的左指針或右指針上。因此，二叉排序樹上的插入過程首先是一個遍歷查找過程。這個查找過程和前面討論的查找算法的不同之處是：這里的查找過程要求同時記住當前結點的位置，因為當查找不到該數(shù)據(jù)元素時，插入的過程即是把該數(shù)據(jù)元素結點地址賦值給查找失敗時當前結點的左指針或右指針。這里給出插入算法。

intInsert(BiTreeNode**root，DataTypeitem)

/*在二叉排序樹root中查找數(shù)據(jù)元素item是否存在，若存在則返回0，否則把*/

/*item結點插入到當前結點的左指針或右指針上并返回1*/

{

BiTreeNode*current，*parent＝NULL，*p;

current＝*root;

while(current!＝NULL)

{

if(current->data.key＝＝item.key)return0;/*數(shù)據(jù)元素已存在*/

parent＝current;

if(current->data.key<item.key)current＝current->rightChild;

elsecurrent＝current->leftChild;

}

p＝(BiTreeNode*)malloc(sizeof(BiTreeNode));

if(p＝＝NULL)

{

printf("空間不夠!");

exit(1);

}

/*生成新結點*/

p->data＝item;

p->leftChild＝NULL;

p->rightChild＝NULL;

if(parent＝＝NULL)*root＝p;/*新結點成為根結點*/

elseif(item.key<parent->data.key)

parent->leftChild＝p;/*新結點為該結點的左孩子結點*/

else

parent->rightChild＝p;/*新結點為該結點的右孩子結點*/

return1;

}

調(diào)用二叉排序樹上的插入算法就可以構造出一棵二叉排序樹。圖10-5(a)~(i)是調(diào)用上述插入算法依次插入數(shù)據(jù)元素4，5，7，2，1，9，8，11，3的過程。

圖10-5二叉排序樹的插入

4.二叉排序樹上的刪除算法

刪除操作的要求是首先查找數(shù)據(jù)元素是否在二叉排序樹中存在，若不存在則返回；若存在再按如下四種不同情況分別進行不同的刪除操作。

(1)要刪除結點無孩子結點。

(2)要刪除結點只有左孩子結點。

(3)要刪除結點只有右孩子結點。

(4)要刪除結點有左右孩子結點。對應于上述四種不同情況，相應的刪除方法是：

(1)要刪除結點無孩子結點時直接刪除該結點。

(2)要刪除結點只有左孩子結點時刪除該結點且使被刪除結點的雙親結點指向被刪除結點的左孩子結點。

(3)要刪除結點只有右孩子結點時刪除該結點且使被刪除結點的雙親結點指向被刪除結點的右孩子結點。

(4)要刪除結點有左右孩子結點時分如下三步完成：首先尋找data域值大于要刪除結點的最小值，即尋找右子樹的最左結點；然后把右子樹的最左結點的值拷貝到要刪除結點上；最后刪除右子樹的最左結點。對于情況(1)、(2)、(3)、(4)的二叉排序樹的刪除見圖10-6，其中圖10-6(a)是要刪除結點無孩子結點，圖10-6(b)是要刪除結點只有左孩子結點，圖106(c)是要刪除結點只有右孩子結點，圖10-6(d)是要刪除結點有左右孩子結點。圖中虛線箭頭ptr指針所指結點是當前要刪除的結點。

圖10-6二叉排序樹的刪除

(a)無孩子結點；(b)只有左孩子結點；(c)只有右孩子結點；(d)有左右孩子結點

5.測試程序

上述插入算法和查找算法的一個測試程序設計如下：＃include<stdio.h>

＃include<stdlib.h>

＃include<malloc.h>

typedefintKeyType;

typedefstruct

{

KeyTypekey;

}DataType;

typedefstructnode

{

DataTypedata;

structnode*leftChild;

structnode*rightChild;

}BiTreeNode;

(查找和插入算法如前所示，此處省略)

voidInTraverse(BiTreeNode*root)/*中序遍歷顯示二叉排序樹結點信息函數(shù)*/

{

if(root＝＝NULL)return;

if(root->leftChild!＝NULL)

InTraverse(root->leftChild);

printf("%d"，root->data.key);

if(root->rightChild!＝NULL)

InTraverse(root->rightChild);

}

voidmain(void)

{

DataTypetest［］＝{4，5，7，2，1，9，8，11，3}，x＝{9};

intn＝9，i，s;

BiTreeNode*root＝NULL;

for(i＝0;i<n;i＋＋)/*依次插入建立二叉排序樹*/

{

Insert(&root，test［i］);

}

InTraverse(root);/*調(diào)用中序遍歷函數(shù)*/

s＝Search(root，x);/*調(diào)用查找函數(shù)*/

if(s＝＝1)

printf(""＼n數(shù)據(jù)元素%d存在！"，x.key");

else

printf("＼n數(shù)據(jù)元素不存在！");

}程序運行建立的二叉排序樹如圖10-5(i)所示。程序運行輸出結果如下：

1234578911

數(shù)據(jù)元素9存在！

6.二叉排序樹的性能分析

從前面的討論可知，插入和刪除算法的主體部分是查找，因此二叉排序樹上的查找效率也就表示了二叉排序樹上各個操作的性能。對有n個結點的二叉排序樹來說，若每個數(shù)據(jù)元素的查找概率相等，則二叉排序樹平均查找長度是結點深度的函數(shù)，即

若每個數(shù)據(jù)元素的查找概率相等，則二叉排序樹查找成功的平均查找長度為

但是，當二叉排序樹是一棵單分支退化樹時，查找成功的平均查找長度和有序順序表的平均查找長度相同，即為

圖10-7是共有7個數(shù)據(jù)元素的數(shù)據(jù)元素集合相同但形態(tài)不同的兩棵二叉排序樹，其中，圖10-7(a)是一棵滿二叉排序樹，圖10-7(b)是一棵右分支退化二叉排序樹。

對于圖10-7(a)所示的滿二叉排序樹，k＝lb(7＋1)＝3，所以查找成功的平均查找長度為

圖10-7數(shù)據(jù)元素集合相同但形態(tài)不同的兩棵二叉排序樹

(a)滿二叉排序樹；(b)右分支退化二叉排序樹

對于圖10-7(b)所示的右分支退化二叉排序樹，k＝n＝7，所以查找成功的平均查找長度為

造成二叉排序樹形態(tài)不同的主要因素是構造二叉排序樹時數(shù)據(jù)元素的輸入次序。例如，若測試程序數(shù)據(jù)元素的輸入次序為

test［］＝{6，4，8，3，5，7，10}

時，將構造出圖10-7(a)所示的完全二叉排序樹；若測試程序數(shù)據(jù)元素的輸入次序為

test［］＝{3，4，5，6，7，8，10}

時，將構造出圖10-7(b)所示的右分支退化二叉排序樹。

因此，在最壞情況下，二叉排序樹的平均查找長度為O(n)。在隨機情況下，二叉排序樹的平均查找長度為O(lbn)。10.3.2B-樹

和二叉排序樹相比，B-樹是一種平衡多叉排序樹。這里說的平衡是指所有葉結點都在同一層上，從而可避免出現(xiàn)像二叉排序樹那樣的分支退化現(xiàn)象；多叉是指多于二叉。因此，B-樹是一種動態(tài)查找效率較二叉排序樹更高的樹型存儲結構。

B-樹中所有結點的孩子結點的最大值稱為B-樹的階，B-樹的階通常用m表示，從查找效率考慮，要求m≥3。一棵m階的B-樹或者是一棵空樹，或者是滿足下列要求的m叉樹：

(1)樹中每個結點至多有m個孩子結點。

(2)除根結點外，其他結點至少有［m/2］個孩子結點(符號“［］”表示上取整)。

(3)若根結點不是葉結點，則根結點至少有兩個孩子結點。

(4)每個結點的結構為：

其中，n為該結點中的關鍵字個數(shù)，除根結點外。其他所有結點的n大于等于［m/2］＋1且小于等于m-1；Ki(1≤i≤n)為該結點的關鍵字且滿足Ki<Ki＋1；Pi(0≤i≤n)為該結點的孩子結點指針且滿足Pi(0≤i≤n-1)指針所指結點的關鍵字均大于等于Ki且小于Ki＋1，Pn指針所指結點的關鍵字大于等于Kn。

(5)所有葉結點都在同一層上。

圖10-8一棵4階B-樹由于B-樹是平衡的，因此可避免出現(xiàn)像二叉排序樹那樣的分支退化現(xiàn)象；另外，B-樹的多叉樹型結構也較二叉樹結構有更高的查找效率。因此B-樹是一種較二叉排序樹動態(tài)查找效率更高的樹型結構。

1.B-樹上的查找算法

B-樹的查找算法和二叉排序樹上的查找算法類同。在B-樹上查找數(shù)據(jù)元素x的方法為將x.key與根結點的Ki逐個進行比較：

(1)若x.key＝Ki，則查找成功。

(2)若key<K1，則沿著指針P0所指的子樹繼續(xù)查找。

(3)若Ki<key<Ki＋1，則沿著指針Pi所指的子樹繼續(xù)查找。

(4)若key>Kn，則沿著指針Pn所指的子樹繼續(xù)查找。

2.B-樹的插入算法

將數(shù)據(jù)元素x的關鍵字x.key插入到B-樹的過程分兩步完成：

(1)利用前述的B-樹的查找算法找出該關鍵字的插入結點。(注意，B-樹的插入結點一定是葉結點。)

(2)判斷該結點是否還有空位置，即判斷該結點是否滿足n<m-1，若該結點滿足n<m-1，

說明該結點還有空位置，直接把關鍵字x.key插入到該結點的合適位置上(即滿足插入后結點上的關鍵字序列仍保持有序)；若該結點滿足n＝m-1，說明該結點已沒有空位置，要插入就要分裂該結點。結點分裂的方法是：以中間關鍵字為界把結點分為兩個結點，并把中間關鍵字向上插入到雙親結點上，若雙親結點未滿則把它插入到雙親結點的合適位置上，若雙親結點已滿則按同樣的方法繼續(xù)向上分裂。這個向上的分裂過程可一直進行到根結點的分裂，此時B-樹的高度將增1。由于B-樹的插入過程或者是直接在葉結點上插入，或者是從葉結點向上的分裂過程，所以新結點插入后仍將保持所有葉結點都在同一層上的特點。

圖10-93階B-樹上的插入

(a)初始狀態(tài)；(b)插入90后的狀態(tài)；

(c)插入195后結點分裂前的狀態(tài)；(d)插入195后結點的分裂過程

3.B-樹的刪除算法

在B-樹上刪除數(shù)據(jù)元素x的關鍵字x.key的過程分兩步完成：

(1)利用前述的B-樹的查找算法找出該關鍵字所在的結點。

(2)在結點上刪除關鍵字x.key分兩種情況：一種是在葉結點上刪除關鍵字；另一種是在非葉結點上刪除關鍵字。在非葉結點上刪除關鍵字時，假設要刪除關鍵字Ki(1≤i≤n)，在刪去該關鍵字后，以該結點Pi所指子樹中的最小關鍵字Kmin來代替被刪關鍵字Ki所在的位置(注意，Pi所指子樹中的最小關鍵字Kmin一定是在葉結點上)，然后再以指針Pi所指結點為根結點查找并刪除Kmin

(即再以Pi所指結點為B-樹的根結點，

以Kmin為要刪除關鍵字再次調(diào)用B-樹上的刪除算法)，這樣也就把非葉結點上的刪除問題轉化成了葉結點上的刪除問題。在B-樹的葉結點上刪除關鍵字共有以下三種情況：

①假如要刪除關鍵字結點的關鍵字個數(shù)n大于m/2＋1，說明刪去該關鍵字后該結點仍滿足B-樹的定義，則可直接刪去該關鍵字。

②假如要刪除關鍵字結點的關鍵字個數(shù)n等于m/2＋1，說明刪去該關鍵字后該結點將不滿足B-樹的定義，此時若該結點的左(或右)兄弟結點中關鍵字個數(shù)n大于m/2＋1，則把該結點的左(或右)兄弟結點中最大(或最小)的關鍵字上移到雙親結點中，同時把雙親結點中大于(或小于)上移關鍵字的關鍵字下移到要刪除關鍵字的結點中，這樣刪去關鍵字后該結點以及它的左(或右)兄弟結點都仍舊滿足B-樹的定義。

③假如要刪除關鍵字結點的關鍵字個數(shù)n等于m/2＋1并且該結點的左和右兄弟結點(如果存在的話)中關鍵字個數(shù)n均等于m/2＋1，這時需把要刪除關鍵字的結點與其左(或右)兄弟結點以及雙親結點中分割二者的關鍵字合并成一個結點。圖10-10是在3階B-樹上進行刪除操作的示例，其中圖10-10(b)是在葉結點上刪除關鍵字的第一種情況；圖10-10(c)是在葉結點上刪除關鍵字的第二種情況；圖10-10(d)是在葉結點上刪除關鍵字的第三種情況；圖10-10(e)是在非葉結點上刪除關鍵字的情況。

圖10-103階B-樹上的刪除

(a)初始狀態(tài)；(b)刪去110后的狀態(tài)；(c)刪去80后的狀態(tài)；(d)刪去116后的狀態(tài)；(e)刪去180后的狀態(tài)

在前面討論的靜態(tài)查找表和動態(tài)查找表中，數(shù)據(jù)元素的存放位置和數(shù)據(jù)元素的關鍵字之間沒有關系，因此查找過程是一系列比較的過程。如果我們構造一個查找表，使數(shù)據(jù)元素的存放位置和數(shù)據(jù)元素的關鍵字之間存在某種對應關系，則我們可以直接由數(shù)據(jù)元素的關鍵字得到該數(shù)據(jù)元素的存放位置。這樣的查找表就是哈希表，數(shù)據(jù)元素的關鍵字和該數(shù)據(jù)元素的存放位置之間的映射函數(shù)稱為哈希函數(shù)。因此我們說，哈希表是通過哈希函數(shù)來確定數(shù)據(jù)元素存放位置的一種表結構。10.4哈希表10.4.1哈希表的基本概念

構造哈希表的方法是：設要存儲的數(shù)據(jù)元素個數(shù)為n，設置一個長度為m(m≥n)的連續(xù)內(nèi)存單元，分別以每個數(shù)據(jù)元素的關鍵字Ki為(0≤i≤n-1)為自變量，通過一個稱為哈希函數(shù)的函數(shù)h(Ki)，把Ki映射為內(nèi)存單元的地址h(Ki)，并把該數(shù)據(jù)元素存儲在這個內(nèi)存單元中。從數(shù)學的觀點看，哈希函數(shù)h(Ki)實際上是關鍵字Ki到內(nèi)存單元的映射，因此，h(Ki)也稱為哈希地址。哈希表也稱作散列表。從哈希表的構造方法可以推知，構造哈希表時一定要使用主關鍵字，不能使用次關鍵字。

但是存在這樣的問題，對于兩個關鍵字Ki和Kj(i≠j)，有Ki≠Kj(i≠j)，但h(Ki)＝h(Kj)。我們把建立哈希表時Ki≠Kj(i≠j)，但h(Ki)＝h(Kj)的現(xiàn)象稱作哈希沖突。通常把這種具有不同關鍵字而具有相同哈希地址的數(shù)據(jù)元素稱作“同義詞”，由同義詞引起的沖突稱作同義詞沖突。在哈希表存儲結構的存儲中，同義詞沖突是很難避免的，除非關鍵字的變化區(qū)間小于等于哈希地址的變化區(qū)間，而這種情況當關鍵字取值不連續(xù)時是非常浪費存儲空間的。通常的實際情況是關鍵字的取值區(qū)間遠遠大于哈希地址的變化區(qū)間。解決哈希沖突方法有許多，其基本思想是當哈希沖突時通過哈希沖突函數(shù)(設為hl(K)

(l＝1，2，…，m-1))產(chǎn)生一個新的哈希地址使hl(Ki)≠hl(Kj)。哈希沖突函數(shù)產(chǎn)生的哈希地址仍可能有哈希沖突問題，此時再用新的哈希沖突函數(shù)得到新的哈希地址，一直到不存在哈希沖突為止。這樣我們就把要存儲的n個數(shù)據(jù)元素通過哈希函數(shù)映射到了m個連續(xù)內(nèi)存單元中，從而完成了哈希表的建立。顯然，一旦哈希表建立，在哈希表中進行查找的方法就是以要查找關鍵字K為映射函數(shù)的自變量、以建立哈希表時使用的同樣的哈希函數(shù)h(K)為映射函數(shù)得到一個哈希地址(設該地址中數(shù)據(jù)元素的關鍵字為Ki)，比較要查找關鍵字K和Ki，如果K＝Ki則查找成功；否則，以建立哈希表時使用的同樣的哈希沖突函數(shù)得到新的哈希地址(設該地址中數(shù)據(jù)元素的關鍵字為Kj)，比較要查找關鍵字K和Kj，如果K＝Kj則查找成功；否則，以建立哈希表時使用的同樣的后續(xù)哈希沖突函數(shù)得到新的哈希地址繼續(xù)查找；直到查找成功或查找完m次未查找到而查找失敗為止?！纠?0-1】建立數(shù)據(jù)元素集合a的哈希表，a＝{180，750，600，430，541，900，460}，并比較m取值不同時的哈希沖突情況。

設計分析：數(shù)據(jù)元素集合a中共有7個數(shù)據(jù)元素，數(shù)據(jù)元素的關鍵字為三位整數(shù)，如果我們?nèi)?nèi)存單元個數(shù)m為1000，即內(nèi)存單元區(qū)間為000～999，則第一，在m個內(nèi)存單元中可以存放下n個數(shù)據(jù)元素，第二，若取h(K)＝K，則當Ki≠Kj(i≠j)時一定有h(Ki)≠h(Kj)。

但是，在1000個內(nèi)存單元中只存儲7個數(shù)據(jù)元素其空間存儲效率太低。我們可適當減少內(nèi)存單元個數(shù)。若取內(nèi)存單元個數(shù)m為13，取哈希函數(shù)h(K)為h(K)＝Kmodm，

即哈希地址h(K)為關鍵字K除m所得的余數(shù)，則有

h(180)＝11h(750)＝9

h(600)＝2h(430)＝1

h(541)＝8h(900)＝3

h(460)＝5

則數(shù)據(jù)元素集合在哈希表中的存儲映像為：若取內(nèi)存單元個數(shù)m為11，仍取哈希函數(shù)h(K)為h(K)＝Kmodm，則有

h(180)＝4h(750)＝2

h(600)＝6h(430)＝1

h(541)＝3h(900)＝9

h(460)＝9

此時h(460)＝h(900)＝9，因此存在哈希沖突。若取第一次哈希沖突函數(shù)h1(K)為關鍵字加1后模m，即h1(K)＝h(K＋1)，則有

h1(460)＝10

則數(shù)據(jù)元素集合在哈希表中的存儲映像為：

從例10-1可知，如何盡量避免沖突和沖突發(fā)生后如何解決沖突(即為發(fā)生沖突的數(shù)據(jù)元素找到一個空閑內(nèi)存單元)就成了建立哈希表的兩個關鍵問題。在構造哈希表時，雖然哈希沖突很難避免，但發(fā)生哈希沖突的可能性卻有大有小。哈希沖突主要與三個因素有關：

(1)裝填因子α。所謂裝填因子是指哈希表中已存入的數(shù)據(jù)元素個數(shù)ｎ與哈希地址空間大?。淼谋戎?，即α＝ｎ/ｍ，當α越小時，沖突的可能性就越小，α越大(最大可取1)時，沖突的可能性就越大。但是，α越小，哈希表中空閑單元的比例就越大，存儲空間的利用率就越低；α越大，哈希表中空閑單元的比例就越小，存儲空間的利用率就越高。為了既兼顧減少哈希沖突的發(fā)生，又兼顧提高存儲空間的利用率這兩個方面，通常使α控制在0.6～0.9的范圍內(nèi)。

(2)所采用的哈希函數(shù)。若哈希函數(shù)選擇得當，就可使哈希地址盡可能均勻地分布在哈希地址空間上，從而減少沖突的發(fā)生；否則，若哈希函數(shù)選擇不當，就可能使哈希地址集中于某些區(qū)域，從而加大哈希沖突發(fā)生的可能性。

(3)解決哈希沖突的哈希沖突函數(shù)。哈希沖突函數(shù)選擇的好壞也將影響發(fā)生哈希沖突的可能性。10.4.2哈希函數(shù)構造方法

構造哈希函數(shù)的目標是使得到的哈希地址盡可能均勻地分布在m個連續(xù)內(nèi)存單元上，同時，使計算過程盡可能簡單以達到盡可能高的時間效率。根據(jù)關鍵字的結構和分布的不同，可構造出許多不同的哈希函數(shù)。這里主要討論幾種常用的整數(shù)類型關鍵字的哈希函數(shù)構造方法。

1.直接定址法

直接定址法是以關鍵字K本身或關鍵字加上某個數(shù)值常量C作為哈希地址的方法。直接定址法的哈希函數(shù)h(K)為

h(K)＝K＋C

這種哈希函數(shù)計算簡單，并且不可能有沖突發(fā)生。但是，此種哈希函數(shù)有可能造成內(nèi)存單元的大量浪費。如例10-1中，若使用直接定址法的哈希函數(shù)，則因關鍵字為3位數(shù)而需要1000個內(nèi)存單元來存放7個數(shù)據(jù)元素。

2.除留余數(shù)法

除留余數(shù)法是用關鍵字K除以哈希表長度m所得的余數(shù)作為哈希地址的方法。除留余數(shù)法的哈希函數(shù)h(K)為

h(K)＝Kmodm

除留余數(shù)法計算比較簡單，適用范圍廣，是最經(jīng)常使用的一種哈希函數(shù)。例10-1中的后兩種方法都是除留余數(shù)法的哈希函數(shù)。這種方法的關鍵是選好哈希表長度m，使得數(shù)據(jù)元素集合中的每一個關鍵字通過該函數(shù)轉換后映射到哈希表的任意地址上的概率相等，從而盡可能地減少發(fā)生哈希沖突的可能性。例如m取奇數(shù)就比m取偶數(shù)好，因為當m取偶數(shù)時，偶數(shù)的關鍵字(除了關鍵字2)將映射到哈希表的偶數(shù)區(qū)間，奇數(shù)的關鍵字將映射到哈希表的奇數(shù)區(qū)間。理論研究表明，哈希表長度m取素數(shù)時效果最好。素數(shù)是除1和該數(shù)自身外，不能被任何數(shù)整除的數(shù)。根據(jù)前邊討論給出的裝填因子α＝n/m的定義和α的取值最好在0.6～0.9的實踐經(jīng)驗，可得出m最好取1.1n～1.7n之間的一個素數(shù)。例如當n＝7時，m最好取11，13等素數(shù)；當n＝100時，m最好取113，127，139，143等素數(shù)。

3.數(shù)字分析法

數(shù)字分析法是取關鍵字中某些取值較均勻的數(shù)字位作為哈希地址的方法。它適合于所有關鍵字值已知的情況。我們可對關鍵字中每一位的取值分布情況做出分析，從而可以把一個很大的關鍵字取值區(qū)間轉化為一個較小的關鍵字取值區(qū)間。例如，要構造一個數(shù)據(jù)元素個數(shù)n＝80，哈希表長度m＝100的哈希表。不失一般性，我們這里只給出其中8個關鍵字進行分析，8個關鍵字值如下所示：

K1＝61317602K2＝61326875K3＝62739628

K4＝61343634K5＝62706816K6＝62774638

K7＝61381262K8＝61394220

分析上述8個關鍵字可知，關鍵字從左到右的第1，2，3，6位取值較集中，不宜作為哈希地址，剩余的第4，5，7，8位取值較均勻，可選取其中的兩位作為哈希地址。設選取最后兩位作為哈希地址，則這8個關鍵字的哈希地址分別為：02，75，28，34，16，38，62，20。10.4.3哈希沖突解決方法

解決哈希沖突的方法主要有開放定址法和鏈表法兩大類。

1.開放定址法

開放定址法是一類以發(fā)生沖突的哈希地址為自變量、通過某種哈希沖突函數(shù)得到一個新的空閑的哈希地址的方法。在開放定址法中，哈希表中的空閑單元(假設其地址為d)不僅允許哈希地址為d的同義詞關鍵字使用，而且也允許發(fā)生沖突的其他關鍵字使用，因為這些關鍵字的哈希地址不為d，所以稱為非同義詞關鍵字。開放定址法的名稱就是來自此方法的哈希表空閑單元既向同義詞關鍵字開放，也向發(fā)生沖突的非同義詞關鍵字開放。至于哈希表的一個地址中存放的是同義詞關鍵字還是非同義詞關鍵字，要看誰先占用它，這和構造哈希表的數(shù)據(jù)元素排列次序有關。

在開放定址法中，以發(fā)生沖突的哈希地址為自變量、通過某種哈希沖突函數(shù)得到一個新的空閑的哈希地址的方法有很多種，下面介紹常用的幾種。

1)線性探查法

線性探查法是從發(fā)生沖突的地址(設為d)開始，依次探查d的下一個地址(當?shù)竭_地址為m-1的哈希表表尾時，下一個探查的地址是表首地址0)，直到找到一個空閑單元為止(當m≥n時一定能找到一個空閑單元)。線性探查法的數(shù)學遞推描述公式為

例10-1中m＝11時產(chǎn)生沖突后所使用的解決沖突的方法就是線性探查法。

線性探查法容易產(chǎn)生堆積問題，這是由于當連續(xù)出現(xiàn)若干個同義詞后(設第一個同義詞占用單元d，這些連續(xù)的若干個同義詞將占用哈希表的d，d＋1，d＋2，…單元)，此時隨后任何d＋1，d＋2，…單元上的哈希映射都會由于前面的同義詞堆積而產(chǎn)生沖突。

2)平方探查法

設發(fā)生沖突的地址為d，則平方探查法的探查序列為d＋20，d＋21，…。平方探查法的數(shù)學遞推描述公式為

由于平方探查法的探查跨步很大，所以可避免出現(xiàn)堆積問題。

2.鏈表法

用鏈表法解決哈希沖突有兩種方法：第一種方法是把所有的同義詞用單鏈表鏈接起來；第二種方法是當哈希表中相應位置為空時直接存放，當哈希表中相應位置非空時用單鏈表鏈接起來?！纠?0-2】建立數(shù)據(jù)元素集合a的哈希表，a＝{16，74，60，43，54，90，46，31，29，88，77，66，55}。要求哈希函數(shù)采用除留余數(shù)法，解決沖突方法采用鏈表法。

設計分析：數(shù)據(jù)元素集合a中共有13個數(shù)據(jù)元素，取哈希表的單元個數(shù)m＝13。除留余數(shù)法的哈希函數(shù)為h(K)＝Kmodm，有：

h(16)＝3h(74)＝9h(60)＝8

h(43)＝4h(54)＝2h(90)＝12

h(46)＝7h(31)＝5h(29)＝3

h(88)＝10h(77)＝12h(66)＝1

h(55)＝3

采用鏈表法的第一種方法建立的哈希表存儲結構如圖10-11(a)所示，采用鏈表法的第二種方法建立的哈希表存儲結構如圖10-11(b)所示。

圖10-11用鏈表法解決沖突的哈希表

(a)采用第一種方法的鏈表法；(b)采用第二種方法的鏈表法

10.4.4哈希表設計舉例

【例10-3】編寫一組包括哈希表初始化、哈希表元素插入、哈希表元素刪除、哈希表查找和哈希表空間撤消操作的函數(shù)。要求哈希函數(shù)采用除留余數(shù)法，解決哈希沖突方法采用開放定址法的線性探查法。并設計一個測試程序進行測試。

設計數(shù)據(jù)結構設計：結構體HashTable由哈希表數(shù)組、數(shù)組個數(shù)和當前表項個數(shù)三部分組成，其中哈希表數(shù)組中每個表項的數(shù)據(jù)類型是結構體HashItem。結構體HashItem由數(shù)據(jù)元素和表項狀態(tài)兩部分組成，其中數(shù)據(jù)元素僅包括一個關鍵字域，表項狀態(tài)的數(shù)據(jù)類型為枚舉類型，表項狀態(tài)域有Empty、Active和Deleted三種狀態(tài)，分別表示表項的空、已占用和被刪除三種狀態(tài)。數(shù)據(jù)結構定義如下：typedefenum

{Empty，Active，Deleted}KindOfItem;/*表項狀態(tài)的枚舉類型*/

typedefintKeyType;

typedefstruct

{

KeyTypekey;

}DataType;

typedefstruct

{

DataTypedata;

KindOfIteminfo;

}HashItem;/*表項結構體*/

typedefstruct

{

HashItem*ht;/*哈希表數(shù)組*/

inttableSize;/*數(shù)組個數(shù)*/

intcurrentSize;/*當前表項個數(shù)*/

}HashTable;/*哈希表結構體*/

函數(shù)設計：哈希表元素插入操作、哈希表元素刪除操作和哈希表查找操作都需要首先定位數(shù)據(jù)元素的位置，因此要設計一個定位數(shù)據(jù)元素位置的函數(shù)。定位數(shù)據(jù)元素位置有兩種情況：一種情況是插入時尋找空閑單元的定位；另一種情況是在查找或刪除操作時尋找是否該數(shù)據(jù)元素在哈希表中存在的定位。這里我們把這兩種情況的數(shù)據(jù)元素位置定位設計成一個函數(shù)。插入時尋找空閑單元定位的特征是哈希表中不存在該數(shù)據(jù)元素，我們設計此種情況時定位函數(shù)返回尋找到的空閑單元地址的負值；查找和刪除操作時尋找該數(shù)據(jù)元素是否在哈希表中存在的特征是info＝＝Active，我們設計此種情況時定位函數(shù)返回尋找到的存放該數(shù)據(jù)元素單元地址的正值。intInitiate(HashTable*hash，intmSize)/*初始化函數(shù)*/

{

hash->tableSize＝mSize;

hash->ht＝(HashItem*)malloc(sizeof(HashItem)*mSize);

if(hash->ht＝＝NULL)return0;

else

{

hash->currentSize＝0;

return1;

}

}

intFindPos(HashTable*hash，DataTypex)/*定位函數(shù)*/

/*數(shù)據(jù)元素x在哈希表hash中不存在時返回哈希地址的負值，否則返回正值*/

{

inti＝x.key%hash->tableSize;/*除留余數(shù)法的哈希函數(shù)*/

intj＝i;

while(hash->ht［j］.info＝＝Active&&hash->ht［j］.data.key!＝x.key)

{

j＝(j＋1)%hash->tableSize;/*線性探查法的哈希沖突方法*/

if(j＝＝i)return-hash->tableSize;/*哈希表已滿*/

}

if(hash->ht［j］.info＝＝Active)returnj;/*x在hash中存在返回正值*/

elsereturn-j;/*x在hash中不存在返回負值*/

}

intInsert(HashTable*hash，DataTypex)/*插入函數(shù)*/

{

inti＝FindPos(hash，x);

if(i>0)return0;

elseif(i!＝-hash->tableSize&&hash->ht［-i］.info!＝Active)

{

hash->ht［-i］.data＝x;

hash->ht［-i］.info＝Active;

hash->currentSize＋＋;

return1;

}

elsereturn0;

}

intDelete(HashTable*hash，DataTypex)/*刪除函數(shù)*/

{

inti＝FindPos(hash，x);

if(i>＝0)

{

hash->ht［i］.info＝Deleted;

hash->currentSize--;

return1;

}

elsereturn0;

}

intFind(HashTable*hash，DataTypex)/*查找函數(shù)*/

/*函數(shù)返回數(shù)據(jù)元素x的哈希地址。查找成功返回值≥0，查找失敗返回值<0*/

{

inti＝FindPos(hash，x)，j＝i;

if(j>＝0)

{

while(hash->ht［j］.info＝＝Active&&hash->ht［j］.data.key!＝x.key)

{

j＝(j＋1)%hash->tableSize;/*按線性探查法繼續(xù)查找*/

if(j＝＝i)return-hash->tableSize;/*查找失敗*/

}

if(hash->ht［j］.info＝＝Active)returnj;/*查找成功*/

elsereturn-j;/*查找失敗*/

}

elsereturnj;/*查找失敗*/

}

voidDestroy(HashTable*hash)/*撤消函數(shù)*/

{

free(hash->ht);

}測試程序設計：

我們以數(shù)據(jù)集合a＝{180，750，600，430，541，900，460}為例子，當設計