9￥-nine(天津科技大學(xué))

第九章查找

9.1靜態(tài)查找表

9.2動(dòng)態(tài)查找表

9.3哈希表內(nèi)容包括：查找的基本概念、三種基本查找方法的基本思想和算法、二叉排序樹查找的基本思想和算法、散列法基本思想、散列函數(shù)的常用構(gòu)造方法及解決沖突方法。1/18/20251查找的基本概念查找又稱為查詢或檢索，是在一批記錄中依照某個(gè)域的指定域值，找出相應(yīng)的記錄的操作。在計(jì)算機(jī)中，被查找的數(shù)據(jù)對象是由同一類型的記錄構(gòu)成的集合，可稱之為查找表（searchtable）。在實(shí)際應(yīng)用問題中，每個(gè)記錄一般包含有多個(gè)數(shù)據(jù)域，查找是根據(jù)其中某一個(gè)指定的域進(jìn)行的，這個(gè)作為查找依據(jù)的域稱為關(guān)鍵字（key）。1/18/20252對于給定的關(guān)鍵字的值，如果在表中經(jīng)過查找能找到相應(yīng)的記錄，則稱查找成功，一般可輸出該記錄的有關(guān)信息或指示該記錄在查找表中的位置。若表中不存在相應(yīng)的記錄，則稱查找不成功，此時(shí)應(yīng)該給出不成功的信息。查找算法中的基本運(yùn)算是記錄的關(guān)鍵字與給定值所進(jìn)行的比較，其執(zhí)行時(shí)間通常取決于比較的次數(shù)。因此，通常以關(guān)鍵字與給定值進(jìn)行比較的記錄個(gè)數(shù)的平均值，作為衡量查找算法好壞的依據(jù)。1/18/20253查找的應(yīng)用日常生活中：在電話號碼簿中查閱“某單位”或“某人”的電話號碼；在字典中查閱“某個(gè)詞”的讀音和含義等等。這里“電話號碼簿”和“字典”都可看作一張查找表。各種系統(tǒng)軟件和應(yīng)用軟件中：編譯程序中的符號表、信息處理系統(tǒng)中信息表等等。1/18/20254查找表操作及分類操作：(1)查詢某個(gè)“特定的”數(shù)據(jù)元素是否在查找表中；(2)某個(gè)“特定的”數(shù)據(jù)元素的各種屬性；(3)在查找表中插入一個(gè)數(shù)據(jù)元素；(4)從查找表中刪去某個(gè)數(shù)據(jù)元素。分類：若對查找表只作(1)和(2)兩種操作，則稱此類查找表為靜態(tài)查找表。若在查找過程中同時(shí)插入查找表中簿存在的數(shù)據(jù)元素，或者從查找表中刪除已存在的某個(gè)數(shù)據(jù)元素，則稱此類查找表為動(dòng)態(tài)查找表。1/18/202559.1靜態(tài)查找表抽象數(shù)據(jù)類型靜態(tài)查找表的定義：

ADTStaticSearchTable{

數(shù)據(jù)對象D:D是具有相同屬性的數(shù)據(jù)元素的集合。數(shù)據(jù)關(guān)系R:數(shù)據(jù)元素同屬一個(gè)集合?；静僮鱌:Create(&ST,n);Destroy(&ST);Search(ST,key);Traverse(ST,Visit());}ADTStaticSearchTable1/18/20256順序表的查找順序查找(Sequentialsearch)也稱為線性查找，是采用線性表作為數(shù)據(jù)的存儲結(jié)構(gòu)，對數(shù)據(jù)在表中存放的先后次序沒有任何要求。順序查找是最簡單的查找方法，它的基本思想是：查找從線性表的一端開始，順序?qū)⒏鲉卧年P(guān)鍵字與給定值k進(jìn)行比較，直至找到與k相等的關(guān)鍵字，則查找成功，返回該單元的位置序號；如果進(jìn)行到表的另一端，仍未找到與k相等的關(guān)鍵字，則查找不成功，返回0作為查找失敗的信息。1/18/20257順序查找的線性表定義如下：#defineMAXITEM100/*最多項(xiàng)數(shù)*/structelement{

keytypekey;

Elemtypedata;};typedef

struct

sqlist[MAXITEM];

這里keytype和ElemType可以是任何相應(yīng)的數(shù)據(jù)類型，如int、float或char等，在算法中我們規(guī)定它們?nèi)笔∈莍nt類型。1/18/20258順序查找算法int

sequsearch(sqlistr,intk,n){/*n為線性表r中元素個(gè)數(shù)*/i=1while(r[i].key!=k&&i<=n)i++;if(i>n)i=0;return(i);}1/18/20259順序查找算法分析此函數(shù)的主要運(yùn)算時(shí)間是用于循環(huán)語句逐單元進(jìn)行比較判斷r[i].key是否等于k，因此順序查找的速度較慢，最壞的情況查找成功需比較n次，最好的情況是比較1次，如果對每個(gè)關(guān)鍵字進(jìn)行查找的概率相等，則查找成功所需的平均比較次數(shù)為(n+1)/2，而查找失敗則需比較(n+1)次，時(shí)間復(fù)雜度為O（n）。為確定記錄在查找表中的位置，需和給定值進(jìn)行比較的關(guān)鍵字個(gè)數(shù)的期望值稱為查找算法在查找成功時(shí)的平均查找長度(AverageSearchLength)。1/18/202510順序查找算法分析順序查找的平均查找長度

ASLSS=(n+1)/2(假設(shè)每個(gè)記錄的查找概率相等）查找概率不等時(shí),應(yīng)對查找表作特殊處理.嚴(yán)格說來，查找算法的平均查找長度應(yīng)是查找成功時(shí)的平均查找長度與查找不成功時(shí)的平均查找長度之和。順序查找的優(yōu)點(diǎn)是算法簡單、適應(yīng)面廣，且不要求表中數(shù)據(jù)有序。缺點(diǎn)是平均查找長度較大，特別是當(dāng)n較大時(shí)，查找效率較低，不宜采用。1/18/202511有序表的查找(二分查找)二分查找(Birarysearch)也稱為折半查找，它的查找速度比順序查找快，但它要求數(shù)據(jù)在線性表中按查找的關(guān)鍵字域有序排列。設(shè)n個(gè)數(shù)據(jù)存放于數(shù)組r中，且已經(jīng)過排序，按由小到大遞增的順序排列。采用二分查找，首先用要查找的給定值k與表正中間元素的關(guān)鍵值相比較，此元素的下標(biāo)。1/18/202512比較結(jié)果有三種可能：⑴如果r[m].key>k，說明如果存在欲查找的元素，該元素一定在數(shù)組的前半部分，查找范圍縮小了一半，修改查找范圍的的上界high=m-1，繼續(xù)對數(shù)組的前半部分進(jìn)行二分查找；⑵如果r[m].key<k，說明如果存在欲查找的元素，該元素一定在數(shù)組的后半部分，查找范圍縮小了一半，修改查找范圍的的下界low=m+1，繼續(xù)對數(shù)組的后半部分進(jìn)行二分查找；⑶如果r[m].key=k，查找成功，m所指的記錄就是查找到的數(shù)據(jù)。1/18/202513重復(fù)上述過程，查找范圍每次縮小1/2，當(dāng)范圍不斷縮小，出現(xiàn)查找范圍的下界大于上界時(shí)，則查找失敗，確定關(guān)鍵字為key的記錄不存在。二分查找是一種效率較高的算法，最好的情況是第一次比較即找到所查元素，即使一次比較沒有找到，也把進(jìn)一步查找的范圍縮小一半。與此類似，每比較一次均使查找范圍減半，故最壞的情況所需比較次數(shù)為O(logn)，對于較大的n顯然較順序查找速度快得多。1/18/202514二分查找算法int

binsearch(sqlist

r,intk,n){

inti,low=1,high=n,m,find=0;/*low和high分別表示查找范圍的起始單元下標(biāo)和終止單元下標(biāo)，find為查找成功的標(biāo)志變量*/while(low<=high&&!find){m=(low+high)/2;if(k<r[m].key)high=m-1;elseif(k>r[m].key)1/18/202515二分查找算法續(xù)low=m+1;else{i=m;find=1;}}if(!find)i=0;return(i);}1/18/202516二分查找的性能分析具體例子(11個(gè)元素)查找過程可用判定樹描述查找成功時(shí)進(jìn)行比較的關(guān)鍵字個(gè)數(shù)最多不超過樹的深度

log2n+1

當(dāng)n較大時(shí)，平均查找長度為

ASLbs=log2(

n+1)–163194710258111/18/202517靜態(tài)樹表的查找有序表中各記錄的查找概率不等時(shí)，二分查找性能不一定最優(yōu)?？捎删唧w例子說明。靜態(tài)最優(yōu)查找樹和次優(yōu)查找樹方法可解決這一問題。1/18/202518分塊查找分塊查找又稱為索引順序查找，是順序查找方法的另一種改進(jìn)，其性能介于順序查找和二分查找之間。分塊查找把線性表分成若干塊，每一塊中的元素存儲順序是任意的，但塊與塊之間必須按關(guān)鍵字大小有序排列，即前一塊中的最大關(guān)鍵字值小于后一塊中的最小關(guān)鍵字值。還需要建立一個(gè)索引表，索引表中的一項(xiàng)對應(yīng)于線性表中的一塊，索引項(xiàng)由鍵域和鏈域組成，鍵域存放相應(yīng)塊的最大關(guān)鍵字，鏈域存放指向本塊第一個(gè)結(jié)點(diǎn)和最末一個(gè)結(jié)點(diǎn)的指針。索引表按關(guān)鍵字值的遞增順序排列。1/18/202519分塊查找的算法分兩步進(jìn)行，首先確所查找的結(jié)點(diǎn)屬于哪一塊，即在索引表中查找其所在的塊，然后在塊內(nèi)查找待查的數(shù)據(jù)。由于索引表是遞增有序的，可采用二分查找，而塊內(nèi)元素是無序的，只能采用順序查找。如果塊內(nèi)元素個(gè)數(shù)較少，則不會對執(zhí)行速度有太大的影響。例如線性表中關(guān)鍵字為:9,22,12,14,35,42,44,38,48,60,58,47,78,80,77,82其索引如圖8.1所示。1/18/202520圖8.1

線性表與索引表1/18/202521索引表的定義struct

indexterm{

keytypekey;

intlow,high;};typedef

struct

indextermindex[MAXITEM];

這里的keytype可以是任何相應(yīng)的數(shù)據(jù)類型，如int、float、或char等，在算法中，我們規(guī)定keytype缺省是int類型。1/18/202522分塊查找算法int

blksearch(sqlistr,indexidx,int

k,bn)/*bn為塊的個(gè)數(shù)*/{

inti,high=bn,low=1,mid,j,find=0;while(low<=high&&!find){/*二分查找索引表*/mid=(low+high)/2;if(k<idx[mid].key)high=mid-1;elseif(k>idx[mid].key)low=mid+1;1/18/202523分塊查找算法續(xù)

elsefind=1;}if(find==1){i=idx[mid].low;j=idx[mid].high;}elseif(low<bn)/*k小于索引表內(nèi)最大值*/1/18/202524分塊查找算法續(xù)

{i=idx[low].low;j=idx[low].high;}while(i<=j&&r[i].key!=k)i++;if(i>j)i=0;return(i);}返回1/18/202525分塊查找性能分析分塊查找的平均查找長度為

ASL=Lb+Lw

其中Lb為查找索引表確定所在塊的平均查找長度，Lw為在塊中查找元素的平均查找長度。若將長度為n的表均勻地分成b塊，每塊含有s個(gè)記錄，即b=n/s;又假定表中每個(gè)記錄的查找概率相等，則每塊查找的概率為1/b,塊中每個(gè)記錄的查找概率為1/s.1/18/202526分塊查找性能分析順序查找確定所在塊，平均查找長度為

ASL=Lb+Lw=(b+1)/2+(s+1)/2=((n/s+s)+1)/2

與n和s有關(guān)。當(dāng)s=sqrt(n)時(shí)，取最小值sqrt(n)+1.折半查找確定所在塊，平均查找長度為

ASL’log2(n/s+1)+s/21/18/2025279.2動(dòng)態(tài)查找表

特點(diǎn)：表結(jié)構(gòu)本身是在查找過程中動(dòng)態(tài)生成的。抽象數(shù)據(jù)類型動(dòng)態(tài)查找表的定義

ADTDynamicSearchTable{

數(shù)據(jù)對象D:D是具有相同特性的數(shù)據(jù)元素的集合。數(shù)據(jù)關(guān)系R:數(shù)據(jù)元素同屬一個(gè)集合?；静僮鱌:InitDSTable;DestroyDSTable;

SearchDSTable;InsertDSTable;DeletdDSTable;

TraverseDSTable1/18/202528二叉排序樹定義：二叉排序樹(BinarySortTree)或者是一棵空樹；或者是具有下列性質(zhì)的二叉樹：(1)若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；(2)若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；(3)它的左、右子樹也分別為二叉排序樹。1/18/202529二叉排序樹舉例

4512353375098843160CAODINGZHAOCHENWANGMA1/18/202530二叉排序樹查找將原始數(shù)據(jù)表示成二叉排序樹，樹的每個(gè)結(jié)點(diǎn)對應(yīng)一個(gè)記錄，則可利用此二叉排序樹進(jìn)行類似于二分查找思想的數(shù)據(jù)查找，這也是一個(gè)逐步縮小查找范圍的過程。這種查找方法稱為樹型查找?；舅枷耄翰檎疫^程從根結(jié)點(diǎn)開始，首先將它的關(guān)鍵字與給定值k進(jìn)行比較，如果相等，則查找成功，輸出有關(guān)的信息；如果不等，若根結(jié)點(diǎn)關(guān)鍵字大于給定值k，向左子樹繼續(xù)查找，否則向右子樹繼續(xù)查找。向子樹查找又是樹型查找，先以子樹的根結(jié)點(diǎn)數(shù)據(jù)與k進(jìn)行比較，如果不相等又轉(zhuǎn)向它的左或右子樹繼續(xù)查找。1/18/202531樹型查找是一種遞歸的查找過程。在二叉排序樹上查找關(guān)鍵字為k的結(jié)點(diǎn)，成功時(shí)返回該結(jié)點(diǎn)位置，否則返回NULL，遞歸函數(shù)如下：btree*search(btree*b,intk){if(b==NULL)return(NULL);else{if(b->data==k)return(b);1/18/202532二叉排序樹查找遞歸算法if(k<b->data)return(search(b->left,k));elsereturn(search(b->right,k));}}1/18/202533非遞歸算法btree*treesearch(btree*b,intk){btree*p;p=b;while(p!=NULL);{if(p->data==k)return(p);elseif(k<p->data)p=p->left;elsep=p->right;}return(NULL);}1/18/202534二叉排序樹的插入二叉排序樹是一種動(dòng)態(tài)樹表。特點(diǎn)是樹的結(jié)構(gòu)不是一次生成，而是在查找過程中，當(dāng)樹中不存在關(guān)鍵字等于給定值的結(jié)點(diǎn)時(shí)再進(jìn)行插入。新插入的結(jié)點(diǎn)一定是一個(gè)新添加的葉子結(jié)點(diǎn)，并且是查找不成功時(shí)查找路徑上訪問的最后一個(gè)結(jié)點(diǎn)的左孩子或右孩子結(jié)點(diǎn)。1/18/202535二叉排序樹的插入(續(xù))從空樹出發(fā)，經(jīng)過一系列的查找插入操作之后，可生成一棵二叉排序樹。設(shè)查找的關(guān)鍵字序列為{45,12,53,3,37,50,98,1,8,43,60}，則生成的二叉排序樹如下中序遍歷二叉排序樹可得到一個(gè)關(guān)鍵字的有序序列。插入時(shí)，不必移動(dòng)結(jié)點(diǎn)。45123533750988431601/18/202536二叉排序樹的刪除一般二叉樹刪除存在的問題。如何在二叉排序樹上刪除結(jié)點(diǎn)？設(shè)在二叉排序樹上被刪結(jié)點(diǎn)為*p,其雙親結(jié)點(diǎn)為*f，又*p是*f的左孩子。若*p為葉子結(jié)點(diǎn)，其左右子樹為空。此時(shí)只需修改*f的指針。若*p只有左子樹PL或只有右子樹PR，此時(shí)只要令PL或PR直接成為其雙親結(jié)點(diǎn)*f的左子樹即可。1/18/202537二叉排序樹的刪除(續(xù))若*p的左子樹PL和右子樹PR均不空。根據(jù)圖示可知，在刪去*p之前，中序遍歷該二叉樹得到的序列為{…CLC…QLQSLSPPRF…},在刪去*p之后，仍應(yīng)保持其它元素的相對位置不變，方法一是令*p的左子樹為*f的左子樹，而*p的右子樹為*s的右子樹；方法二是令*p的直接前驅(qū)（或直接后繼）替代*p，然后再從二叉排序樹中刪去它的直接前驅(qū)（或直接后繼）。1/18/202538二叉排序樹的刪除圖示

FPfpPLPRFPfpCLPRfCQSQLSLFCfcCLPRfQSQLSLc1/18/202539在二叉排序樹上進(jìn)行查找，若查找成功，則是從根結(jié)點(diǎn)出發(fā)走了一條從根結(jié)點(diǎn)到所查找結(jié)點(diǎn)的路徑；若查找不成功，則是從根結(jié)點(diǎn)出發(fā)走了一條從根結(jié)點(diǎn)到某個(gè)終端葉子結(jié)點(diǎn)的路徑。與二分查找類似，和關(guān)鍵字比較的次數(shù)不超過二叉排序樹的深度。但是，含有n個(gè)結(jié)點(diǎn)的二叉樹不是唯一的，由于對其結(jié)點(diǎn)插入的先后次序不同，所構(gòu)成的二叉樹的形態(tài)和深度也可能不同。例如，下頁圖是按不同插入次序得到的兩個(gè)二叉排序樹。二叉排序樹查找分析1/18/202540兩個(gè)二叉排序樹在查找失敗的情況下，在這二個(gè)樹上所進(jìn)行的關(guān)鍵字比較次數(shù)分別為3和6次。1/18/202541二叉排序樹查找分析(續(xù))樹型查找最壞情況時(shí)，需要的查找時(shí)間取決于樹的高度，當(dāng)二叉排序樹接近滿二叉樹時(shí)，其高度為log2n，最壞情況下查找時(shí)間為O(logn)，與二分查找是同樣數(shù)量級的；當(dāng)二叉排序樹為只有一個(gè)端結(jié)點(diǎn)的所謂“退化樹”時(shí)，其高度等于n，最壞情況下查找時(shí)間為O(n)，與順序查找屬于同一數(shù)量級。為了保證樹型查找有較高的查找速度，我們希望該二叉樹接近滿二叉樹，也就是希望二叉樹的每一個(gè)結(jié)點(diǎn)的左、右子樹高度盡量接近平衡，即使按任意次序不斷地插入結(jié)點(diǎn)，也不要使此樹成為退化樹。1/18/202542平衡樹平衡樹(Balancedtree)也稱為AVL樹，是由阿德爾森—維爾斯基和蘭迪斯(Adelson-velskiiandlandis)于1962年首先提出的。這是一種附加了一定限制條件的二叉樹。我們定義二叉樹中每一結(jié)點(diǎn)的左子樹高度減右子樹高度為該結(jié)點(diǎn)的平衡因子（Balancefactor），所謂平衡樹，是指一個(gè)二叉樹其任一結(jié)點(diǎn)的平衡因子值只能是+1，0或-1，即任一結(jié)點(diǎn)的左、右子樹高度之差不超過1。如下頁圖所示，圖中數(shù)字為該結(jié)點(diǎn)的平衡因子。1/18/202543平衡樹平衡二叉樹不平衡二叉樹1/18/202544假設(shè)給平衡樹某個(gè)結(jié)點(diǎn)的左子樹插入一個(gè)新結(jié)點(diǎn)，且此新結(jié)點(diǎn)使左子樹的高度加1，我們可能會遇到以下三種情況：(1)如果原來其左子樹高度hl與右子樹高度hr相等，即原來此結(jié)點(diǎn)的平衡因子等于0,插入新結(jié)點(diǎn)后將使平衡因子變成+1，但仍符合平衡樹的條件，不必對其加以調(diào)整；⑵如果原來hl>hr，即原來此結(jié)點(diǎn)的平衡因子等于+1,插入新結(jié)點(diǎn)后將使平衡因子變成+2，破壞了平衡樹的限制條件，需對其加以調(diào)整；⑶如果原來hl<hr，即原來此結(jié)點(diǎn)的平衡因子等于-1，插入新結(jié)點(diǎn)后將使平衡因子變成0，平衡更加改善，不必加以調(diào)整。1/18/202545如果給平衡樹某結(jié)點(diǎn)的右子樹插入一個(gè)結(jié)點(diǎn)，且設(shè)此新結(jié)點(diǎn)使右子樹的高度增加1，則也會遇到與之相對應(yīng)的三種情況。以下頁圖所示的樹為例，設(shè)原已有關(guān)鍵字為51，29，72，11和46這五個(gè)結(jié)點(diǎn)，原樹符合平衡樹條件，圖中各結(jié)點(diǎn)旁所標(biāo)數(shù)字為該結(jié)點(diǎn)的平衡因子。1/18/202546平衡樹插入結(jié)點(diǎn)1/18/202547插入新結(jié)點(diǎn)破壞了平衡樹條件的情況分為兩類，仍以向左子樹插入新結(jié)點(diǎn)為例，這兩類情況分別如下頁圖（a）和(c)所示。圖中矩形表示子樹，矩形的高度表示子樹的高度，帶陰影線的方形則表示插入新結(jié)點(diǎn)后造成的子樹高度加1，各結(jié)點(diǎn)旁所標(biāo)數(shù)字為該結(jié)點(diǎn)的平衡因子。1/18/202548平衡樹的調(diào)整圖1/18/2025491/18/202550平衡樹以二叉鏈表作為存儲結(jié)構(gòu),每個(gè)結(jié)點(diǎn)還要增加一個(gè)平衡因子域。平衡樹的查找運(yùn)算與普通樹型查找完全相同，由于平衡樹附加了平衡條件，其高度與結(jié)點(diǎn)數(shù)相同的完全樹屬于同一數(shù)量級，所以有較快的查找速度。在插入新結(jié)點(diǎn)時(shí)，當(dāng)確定了新結(jié)點(diǎn)應(yīng)插入的位置后，需向回尋找有關(guān)平衡因子變?yōu)?2或-2的祖先，如有這種結(jié)點(diǎn)，則取其中層數(shù)居最低者，根據(jù)不同的情況進(jìn)行單旋轉(zhuǎn)或雙旋轉(zhuǎn)，使整個(gè)樹仍然符合平衡樹的條件，每次插入結(jié)點(diǎn)后，還需對有關(guān)祖先的平衡因子加以修改。1/18/202551B-樹前面介紹的查找方法，均適用于查找存儲在內(nèi)存中的數(shù)據(jù)，統(tǒng)稱為內(nèi)查找方法，它們適用于較小的表，而對較大的、存儲在外存儲器上的文件就不合適了。B-樹是一種多路平衡查找樹，這是一種適用于外查找的方法的數(shù)據(jù)結(jié)構(gòu)。B-樹的定義：

一棵m（m≥3）階的B-樹，或者為空樹，或者是滿足如下條件的m叉樹：1/18/202552(1)樹中每個(gè)非終端結(jié)點(diǎn)至少包含以下數(shù)據(jù)項(xiàng)：

（n,A0,K1,A1,K2,……Kn,An）其中，n為關(guān)鍵字總數(shù)，Ki（1≤i≤n）是關(guān)鍵字，Ai是指向子樹根結(jié)點(diǎn)的指針。關(guān)鍵字是遞增有序的：K1<K2<……Kn，且Ai(0≤i≤n)所指子樹中所有結(jié)點(diǎn)的關(guān)鍵字均小于Ki+1，An所指子樹中所有結(jié)點(diǎn)的關(guān)鍵字均大于Kn。(2)所有的葉子結(jié)點(diǎn)都在同一層上，并且不帶信息（可以看作是外部結(jié)點(diǎn)或查找失敗的結(jié)點(diǎn)，實(shí)際上這些結(jié)點(diǎn)不存在，指向這些結(jié)點(diǎn)的指針為空）。B-樹定義1/18/202553(3)每個(gè)非根結(jié)點(diǎn)中所包含的關(guān)鍵字個(gè)數(shù)n滿足-1≤n≤m-1，即每個(gè)非根結(jié)點(diǎn)至少應(yīng)有個(gè)關(guān)鍵字，至多有m-1個(gè)關(guān)鍵字。因?yàn)槊總€(gè)內(nèi)部結(jié)點(diǎn)的度數(shù)正好是關(guān)鍵字?jǐn)?shù)加1，故每個(gè)非根的內(nèi)部結(jié)點(diǎn)至少有棵子樹，至多有m棵子樹。(4)如果樹非空，則根至少有1個(gè)關(guān)鍵字，所以如果根不是葉結(jié)點(diǎn)，則至少有兩棵子樹。最多有m-1個(gè)關(guān)鍵字，所以最多有m棵子樹。1/18/202554

一棵4階B-樹1/18/2025559.3哈希表集合結(jié)構(gòu)--查找表是一種非常靈便的數(shù)據(jù)結(jié)構(gòu)，關(guān)系松散，給查找?guī)聿槐恪榇?，需在?shù)據(jù)元素之間人為地加上一些關(guān)系，以便按某種規(guī)則進(jìn)行查找，即以另一種數(shù)據(jù)結(jié)構(gòu)來表示查找表。在線性表、樹表中，記錄在結(jié)構(gòu)中的相對位置是隨機(jī)的，查找時(shí)需進(jìn)行一系列的比較，查找的效率依賴于查找過程中所進(jìn)行的比較次數(shù)。1/18/202556哈希表理想情況是不經(jīng)過任何比較，一次存取便能得到所查記錄，需在記錄的存儲位置和它的關(guān)鍵字之間建立一個(gè)確定的對應(yīng)關(guān)系。從關(guān)鍵字集合到地址集合的對應(yīng)關(guān)系f稱為哈希函數(shù)或散列函數(shù)（HashedFunction）

。按這個(gè)思想建立的表稱為哈希表(hashedtable)

。f(K)的值稱為哈希地址或散列地址。哈希查找(Hashedsearch)為在哈希表上進(jìn)行查找的過程，也稱為散列法或雜湊法。1/18/202557設(shè)有關(guān)鍵字為1，3，7，12，15的五個(gè)記錄，定義一個(gè)散列函數(shù)為：

h(k)=(kmodm)+1

式中k為關(guān)鍵字，mod表示除法取余數(shù)的運(yùn)算，m為一項(xiàng)規(guī)定的整數(shù)。假設(shè)在此我們?nèi)=7，則按這五個(gè)關(guān)鍵字計(jì)算出的函數(shù)值為：

h(1)=2,h(3)=4,h(7)=1,h(12)=6,h(15)=2

1/18/202558散列法可能由不同的關(guān)鍵字計(jì)算出相同的散列函數(shù)值來，例如此例中h(1)和h(15)都等于2，也就是遇到了不同記錄占用同一地址單元的情況，這種情況稱為發(fā)生了沖突（collision）。具有相同函數(shù)值的關(guān)鍵字對該哈希函數(shù)來說稱為同義詞(synonym)。1/18/202559散列是一種重要的存儲方法，又是一種查找方法。應(yīng)用散列法存儲記錄的過程是對每個(gè)記錄的關(guān)鍵字進(jìn)行散列函數(shù)的運(yùn)算，計(jì)算出該記錄存儲的地址，并將記錄存入此地址中。查找一個(gè)記錄的過程與存儲記錄的過程一樣，就是對待查找記錄的關(guān)鍵字進(jìn)行計(jì)算，得到地址，并到此地址中查找記錄是否存在。散列存儲的兩個(gè)關(guān)鍵問題：如何盡量避免沖突和如何解決沖突。1/18/202560哈希函數(shù)構(gòu)造方法目標(biāo)是使散列地址盡可能均勻地分布在散列空間上，同時(shí)使計(jì)算盡可能簡單，以節(jié)省計(jì)算時(shí)間。直接定址法：直接取關(guān)鍵字本身或者關(guān)鍵字加上一個(gè)常數(shù)作為散列地址。適用于關(guān)鍵字的分布基本連續(xù)的情況。例子見教材。數(shù)字分析法：又稱為數(shù)字選擇法。適用于所有關(guān)鍵字事先都知道，并且關(guān)鍵字的位數(shù)比散列地址的位數(shù)多的情況，在這種情況下，可將各個(gè)關(guān)鍵字列出，分析它們的每一位數(shù)字，舍去各關(guān)鍵字取值比較集中的位，僅保留取值比較分散的位作為散列地址。1/18/202561數(shù)字分析法例子1/18/202562哈希函數(shù)構(gòu)造方法除留余數(shù)法：用關(guān)鍵字除以不大于哈希表表長m的數(shù)p除后所得余數(shù)為哈希地址。即H(key)=keyMODp,pm這是一種最簡單也最常用的構(gòu)造散列函數(shù)的方法。這種方法關(guān)鍵在于p的選擇，若p選的不好，容易出現(xiàn)沖突。由經(jīng)驗(yàn)知：一般情況下，可以選為質(zhì)數(shù)或不包含小于20的質(zhì)因數(shù)的和數(shù)。1/18/202563哈希函數(shù)構(gòu)造方法平方取中法：取關(guān)鍵字平方后的中間幾位為哈希地址。在不知道關(guān)鍵字全部情況時(shí)常用。折疊法：折疊法是將關(guān)鍵字按要求的長度分成位數(shù)相等的幾段，最后一段如不夠長可以短些，然后把各段重疊在一起相加并去掉進(jìn)位，以所得的和作為地址。隨機(jī)數(shù)法：選擇一個(gè)隨機(jī)函數(shù)，取關(guān)鍵字的隨機(jī)函數(shù)值為它的哈希地址。當(dāng)關(guān)鍵字長度不等時(shí)采用此方法較恰當(dāng)。采用不同的哈希函數(shù)應(yīng)考慮的五個(gè)因素。1/18/202564處理沖突的方法假設(shè)哈希表的地址集為0~n-1,沖突是指由關(guān)鍵字得到的地址為j(0jn-1)的位置上已存有記錄，則處理“沖突”就是為該關(guān)鍵字的記錄找到另一個(gè)“空”的記錄。開放地址法：開放地址就是表中尚未被占用的地址，當(dāng)新插入的記錄所選地址已被占用時(shí)，即轉(zhuǎn)而尋找其它尚開放的地址。形成探查地址序列最簡單的方法是線性探測法，設(shè)散列函數(shù)為H，閉散列表一維數(shù)組的容量為m，對關(guān)鍵字k，計(jì)算出的地址為d=H(k)。1/18/202565處理沖突的方法（續(xù)）線性探測法的基本思想是沿著散列表順序向后探查，直至找到開放地址為止，如到達(dá)表末端仍未找到開放地址，則將表看成是循環(huán)的，返回到表的首端再向后找，只要尚有開放地址最終總可以找到。線性探測法對應(yīng)的探查地址序列為d+1，d+2，……m,1,……,d-1。探查地址序列對應(yīng)的計(jì)算公式為：di=(H(K)+i)modm(1≤i≤m-1)1/18/202566例如，已知一組關(guān)鍵字k1~k5，已計(jì)算出各關(guān)鍵字的散列函數(shù)值為：

H(k1)=3,H(k2)=5,H(k3)=1,H(k4)=3,H(k5)=3，總記錄個(gè)數(shù)為5，開辟的一維數(shù)組長度可以比實(shí)際用的存儲單元多一些，取m=8。1/18/202567開放地址的線性探測1/18/202568二次探測法二次探測法的基本思想是：生成的探查地址序列不是連續(xù)的，而是跳躍式的。二次探測法對應(yīng)的探查地址序列的計(jì)算公式為：

di=(H(k)+i)modm其中i=12，-12，22，-22-,……j2，-j2，(j≤m/2)。隨機(jī)探測法：I為偽隨機(jī)數(shù)序列。1/18/202569開放地址的二次探測1/18/202570鏈地址法：設(shè)散列函數(shù)為H(k)，函數(shù)值范圍為0～m-1，散列表的結(jié)構(gòu)可以設(shè)計(jì)成一個(gè)由m個(gè)指針域構(gòu)成的指針數(shù)組T[m]，初始狀態(tài)都是空指針。其中每一個(gè)分量對應(yīng)一個(gè)單鏈表的頭指針，凡散列地址為i的記錄都插入到頭指針為T[i]的鏈表中。每一個(gè)這樣的單鏈表稱為一個(gè)同義詞表。鏈地址法解決沖突的方式，就是將所有關(guān)鍵字為同義詞的記錄鏈接在同一個(gè)單鏈表中。同義詞要求按關(guān)鍵字有序。其它處理沖突的方法：再哈希法和建立公共溢出區(qū)。例如前面的例子改用鏈地址法如下頁圖所示。1/18/202571鏈地址法1/18/202572散列法的查找運(yùn)算散列表的目的主要是用于快速查找。在建表時(shí)采用何種散列函數(shù)及何種解決沖突的辦法，在查找時(shí)，也采用同樣的散列函數(shù)及解決沖突的辦法。假設(shè)給定的值為k，根據(jù)建表時(shí)設(shè)定的散列函數(shù)H，計(jì)算出散列地址H(k)，如果表中該地址單元為空，則查找失?。环駝t將該地址中的關(guān)鍵字值與給定值k比較，如果相等則查找成功，否則按建表時(shí)設(shè)定的處理沖突的方法找下一個(gè)地址，如此反復(fù)下去，直到某個(gè)地址單元為空（查找失敗）或與關(guān)鍵字值比較相等（查找成功）為止。1/18/202573設(shè)有一批正整數(shù)關(guān)鍵字，采用除留余數(shù)的散列函數(shù)和線性探測開放地址的辦法解決沖突，存放入長度約為該批數(shù)據(jù)總數(shù)1.5倍的一維數(shù)組A中，因?yàn)殛P(guān)鍵字值均大于0，所以規(guī)定數(shù)組元素置0表示開放地址。要求當(dāng)查找成功時(shí)，給出與該關(guān)鍵字相應(yīng)的地址，查找失敗時(shí)則將該關(guān)鍵字插入開放地址單元并輸出此地址。待查找的關(guān)鍵字為k，m值取一個(gè)接近數(shù)組長度的質(zhì)數(shù)，則這種散列法的查找算法如下：1/18/202574查找算法intHashing(intA,m,k){

inti;/*為散列函數(shù)值*/i=(kmodm)+1while(A[i]!=k&&A[i]>0){if(i==m)i=1;elsei++;/*i未到達(dá)表末端則后移一個(gè)單元進(jìn)行線性探測，否則返回到表首端繼續(xù)探測，直至找到待查關(guān)鍵字k或者遇到開放地址為止*/}1/18/202575查找算法續(xù)}if(A[i]==0)A[i]=k;return(i);}1/18/202576例1設(shè)有一組關(guān)鍵字{19,01,23,14,55,20,84,27,68,11,10,77}，采用哈希函數(shù)：H（k）=kmod13。采用開放地址的線性探測法解決沖突，試在0～18的散列地址空間中，對該關(guān)鍵字序列構(gòu)造散列表。解：依題意m=19，得到線性探測法對應(yīng)的探查地址序列計(jì)算公式為：

di=(H(k)+j)mod19;j=1,2,……,18

其計(jì)算函數(shù)如下：

H(19)=19mod13=6H(01)=01mod13=11/18/202577

H(23)=23mod13=10H(14)=14mod13=1(沖突)H(14)=(1