數(shù)據(jù)結(jié)構(gòu)講義

2023/1/191柳青Email:SchoolofSoftware,YunnanUniversity數(shù)據(jù)結(jié)構(gòu)(DataStructure)2023/1/1929.1靜態(tài)查找表9.2動(dòng)態(tài)查找表9.3哈希表

第九章查找2023/1/193查找(Search)的概念

所謂查找，就是在數(shù)據(jù)集合中尋找滿足某種條件的數(shù)據(jù)元素。查找的結(jié)果通常有兩種可能：

查找成功，即找到滿足條件的數(shù)據(jù)元素。查找結(jié)果可為該元素在結(jié)構(gòu)中的位置，還可進(jìn)一步給出該元素中的具體信息。

查找不成功，或查找失敗。查找結(jié)果為一些指示信息，如失敗標(biāo)志、失敗位置等。第九章查找2023/1/194第九章查找在每一個(gè)元素中有若干屬性，其中應(yīng)當(dāng)有一個(gè)屬性，其值可唯一地標(biāo)識(shí)這個(gè)元素。它稱為關(guān)鍵字(Key)。使用基于關(guān)鍵字的查找，查找結(jié)果應(yīng)是唯一的。實(shí)施查找時(shí)有兩種不同的環(huán)境。靜態(tài)查找表，數(shù)據(jù)結(jié)構(gòu)在執(zhí)行查找操作的前后不發(fā)生改變。（SST）動(dòng)態(tài)查找表，為保持較高的查找效率，數(shù)據(jù)結(jié)構(gòu)在執(zhí)行查找操作時(shí)，可同時(shí)進(jìn)行插入和刪除等操作，結(jié)構(gòu)可能發(fā)生變化。（DST）2023/1/1959.1靜態(tài)查找表typedefstruct{ElemType*elem;intlength;}SSTable;在靜態(tài)查找表中，數(shù)據(jù)元素存放于數(shù)組中。查找算法根據(jù)給定值x，在數(shù)組中進(jìn)行查找，直到找到x在數(shù)組中的存放位置或可確定在數(shù)組中找不到x為止。2023/1/1969.1靜態(tài)查找表所謂順序查找，又稱線性查找，主要用于在線性結(jié)構(gòu)中進(jìn)行查找。設(shè)若表中有n個(gè)元素，則順序查找從表的一端開始，順序用各元素的關(guān)鍵字與給定值x進(jìn)行比較，直到找到與其值相等的元素，則查找成功，給出該元素在表中的位置。若整個(gè)表都已檢測(cè)完仍未找到關(guān)鍵字與x相等的元素，則查找失敗。給出失敗信息。9.1.1順序表的查找2023/1/197intSearch_Seq(SSTableST,KeyTypekey)//查找成功，返回非0；否則返回0。{ST.elem[0].key=key;//0號(hào)單元為監(jiān)視哨

for(i=ST.length;!EQ(ST.elem[i].key,key);i--);returni;}

順序查找算法：9.1靜態(tài)查找表2023/1/1989.1靜態(tài)查找表衡量一個(gè)查找算法的時(shí)間效率的標(biāo)準(zhǔn)是：在查找過(guò)程中關(guān)鍵字的平均比較次數(shù)，這個(gè)標(biāo)準(zhǔn)也稱為平均查找長(zhǎng)度ASL(AverageSearchLength)。通常它是查找元素總數(shù)n的函數(shù)。另外衡量一個(gè)查找算法還要考慮算法所需要的存儲(chǔ)量和算法的復(fù)雜性等問(wèn)題。2023/1/199

順序查找的平均查找長(zhǎng)度

設(shè)查找第

i

個(gè)元素的概率為pi，查找到第

i

個(gè)元素所需比較次數(shù)為

ci，則查找成功的平均查找長(zhǎng)度:

在順序查找情形，ci=n-i+1,i=1,2,,n，因此

在等概率情形，pi=1/n,

i=1,2,,n。

9.1靜態(tài)查找表2023/1/19109.1.2

有序表的查找（折半查找）設(shè)n個(gè)元素存放在一個(gè)有序順序表中，并按其關(guān)鍵字從小到大排好了序。采用折半查找時(shí)，先求位于查找區(qū)間正中的元素的下標(biāo)mid，mid=|(low+high)/2」,用其關(guān)鍵字與給定值x比較:elem[mid].key=x，查找成功；elem[mid].key>x，把查找區(qū)間縮小到表的前半部分，再繼續(xù)進(jìn)行折半查找；elem[mid].key<x，把查找區(qū)間縮小到表的后半部分，再繼續(xù)進(jìn)行折半查找。每比較一次，查找區(qū)間縮小一半。如果查找區(qū)間已縮小到一個(gè)元素，仍未找到想要查找的元素，則查找失敗。9.1靜態(tài)查找表2023/1/19110513192137566475808892lowmidhigh例Key=21的查找過(guò)程：midlowhigh0513192137566475808892midlowhigh05131921375664758088929.1靜態(tài)查找表12345678910112023/1/19120513192137566475808892lowmidhigh例Key=85的查找過(guò)程：midlowhigh0513192137566475808892lowhigh05131921375664758088929.1靜態(tài)查找表1234567891011midlowhigh05131921375664758088922023/1/19139.1靜態(tài)查找表折半查找的算法：intSearch_Bin(SSTableST,KeyTypekey){low=1;high=ST.length;while(low<=high){mid=(low+high)/2;ifEQ(ST.elem[mid].key,key) returnmid;elseifLT(key,ST.elem[mid].key) high=mid-1;elselow=mid+1;}return0;}演示2023/1/1914

從有序表構(gòu)造出的二叉查找樹(判定樹)

若設(shè)n=2h-1，則描述折半查找的二叉查找樹是深度為h

的滿二叉樹。2h=n+1,h=log2(n+1)。第1層結(jié)點(diǎn)有1個(gè)，查找第1層結(jié)點(diǎn)要比較1次；第2層結(jié)點(diǎn)有2個(gè)，查找第2層結(jié)點(diǎn)要比較2次；…。63124597810119.1靜態(tài)查找表2023/1/1915第i(1

i

h)層結(jié)點(diǎn)有2i-1個(gè)，查找第i層結(jié)點(diǎn)要比較i次，…。假定每個(gè)結(jié)點(diǎn)的查找概率相等，即pi

=1/n，則查找成功的平均查找長(zhǎng)度為：9.1靜態(tài)查找表2023/1/1916稠密索引：一個(gè)索引項(xiàng)對(duì)應(yīng)數(shù)據(jù)表中一個(gè)元素的索引結(jié)構(gòu)。當(dāng)元素在外存中按加入順序存放而不是按關(guān)鍵字有序存放時(shí)必須采用稠密索引結(jié)構(gòu)，這時(shí)的索引結(jié)構(gòu)叫做索引非順序結(jié)構(gòu)。示例：有一個(gè)存放職工信息的數(shù)據(jù)表，每一個(gè)職工對(duì)象有近1k字節(jié)的信息。

當(dāng)數(shù)據(jù)元素個(gè)數(shù)n很大時(shí)，如果用無(wú)序表形式的靜態(tài)查找結(jié)構(gòu)存儲(chǔ)，采用順序查找，則查找效率較低。如果采用有序表存儲(chǔ)形式的靜態(tài)查找結(jié)構(gòu)，則插入新記錄進(jìn)行排序，時(shí)間開銷也很可觀。這時(shí)可采用索引方法來(lái)實(shí)現(xiàn)存儲(chǔ)和查找。9.1.3索引順序表的查找9.1靜態(tài)查找表2023/1/19172023/1/1918假設(shè)內(nèi)存工作區(qū)僅能容納64k

字節(jié)的數(shù)據(jù)，在某一時(shí)刻內(nèi)存最多可容納64個(gè)元素以供查找。如果元素總數(shù)有1024個(gè),不可能把所有元素的數(shù)據(jù)一次都讀入內(nèi)存。無(wú)論是順序查找或?qū)Ψ植檎?，都需要多次讀取外存記錄。如果在索引表中每一個(gè)索引項(xiàng)占4個(gè)字節(jié),每個(gè)索引項(xiàng)索引一個(gè)職工對(duì)象，則1024個(gè)索引項(xiàng)需要4k字節(jié),在內(nèi)存中可以容納所有的索引項(xiàng)。這樣只需從外存中把索引表讀入內(nèi)存，經(jīng)過(guò)查找索引后確定了職工對(duì)象的存儲(chǔ)地址，再經(jīng)過(guò)1次讀取元素操作就可以完成查找。9.1靜態(tài)查找表2023/1/1919稀疏索引：把所有n個(gè)元素分為b個(gè)子表(塊)存放，一個(gè)索引項(xiàng)對(duì)應(yīng)數(shù)據(jù)表中一組元素(一個(gè)子表)。在子表中,所有元素可能按關(guān)鍵字有序地存放,也可能無(wú)序地存放。但所有這些子表必須分塊有序，后一個(gè)子表中所有元素的關(guān)鍵字均大于前一個(gè)子表中所有元素的關(guān)鍵字。它們都存放在數(shù)據(jù)區(qū)中。另外建立一個(gè)索引表。索引表由b個(gè)索引項(xiàng)組成，第i個(gè)索引項(xiàng)記錄了子表i中最大關(guān)鍵字max_key以及該子表在數(shù)據(jù)區(qū)中的起始位置obj_addr。各個(gè)索引項(xiàng)在索引表中的序號(hào)與各個(gè)子表的塊號(hào)有一一對(duì)應(yīng)的關(guān)系（第i個(gè)索引項(xiàng)是第i個(gè)子表的索引項(xiàng),i=0,1,…,n-1），這樣的索引結(jié)構(gòu)叫做索引順序結(jié)構(gòu)。9.1靜態(tài)查找表2023/1/19209.1靜態(tài)查找表2023/1/1921對(duì)索引順序結(jié)構(gòu)進(jìn)行查找時(shí)，一般分為兩級(jí)查找。

先在索引表ID

中查找給定值K，確定滿足

ID[i-1].max_key<K

ID[i].max_key

的i值，即待查元素可能在的子表的序號(hào)。然后再在第i個(gè)子表中按給定值查找要求的元素。索引表是按max_key有序的，且長(zhǎng)度也不大，可以對(duì)分查找，也可以順序查找。9.1靜態(tài)查找表2023/1/19229.1靜態(tài)查找表各子表內(nèi)各個(gè)元素如果也按元素關(guān)鍵字有序，可以采用對(duì)分查找或順序查找；如果不是按元素關(guān)鍵字有序，只能順序查找。索引順序查找的查找成功時(shí)的平均查找長(zhǎng)度

ASLIndexSeq=ASLIndex

+ASLSubList其中，ASLIndex

是在索引表中查找子表位置的平均查找長(zhǎng)度，ASLSubList是在子表內(nèi)查找元素位置的查找成功的平均查找長(zhǎng)度。2023/1/1923設(shè)把長(zhǎng)度為n的表分成均等的b個(gè)子表，每個(gè)子表s個(gè)元素，則b=n/s。又設(shè)表中每個(gè)元素的查找概率相等，則每個(gè)子表的查找概率為1/b，子表內(nèi)各元素的查找概率為1/s。若對(duì)索引表和子表都用順序查找，則索引順序查找的查找成功時(shí)的平均查找長(zhǎng)度為

ASLIndexSeq=(b+1)/2+(s+1)/2=(b+s)/2+1索引查找的平均查找長(zhǎng)度不僅與表中的元素個(gè)數(shù)n有關(guān)，而且與每個(gè)子表中的元素個(gè)數(shù)s有關(guān)。在給定n的情況下，s應(yīng)選擇多大？9.1靜態(tài)查找表2023/1/19249.1靜態(tài)查找表利用數(shù)學(xué)方法可以導(dǎo)出，當(dāng)s=

時(shí)，ASLIndexSeq取極小值+1。這個(gè)值比順序查找強(qiáng)，但比折半查找差。若采用折半查找確定元素所在的子表，則查找成功時(shí)的平均查找長(zhǎng)度為

ASLIndexSeq=ASLIndex

+ASLSubList

log2(b+1)-1+(s+1)/2

log2(1+n/s)+s/22023/1/1925定義：

二叉排序樹或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：左子樹(如果存在)上所有結(jié)點(diǎn)的關(guān)鍵字都小于根結(jié)點(diǎn)的關(guān)鍵字。

右子樹(如果存在)上所有結(jié)點(diǎn)的關(guān)鍵字都大于根結(jié)點(diǎn)的關(guān)鍵字。

左子樹和右子樹也是二叉排序樹。特點(diǎn)：

如果對(duì)一棵二叉排序樹進(jìn)行中序遍歷，可以按從小到大的順序，將各結(jié)點(diǎn)關(guān)鍵字排列起來(lái)，所以稱為二叉排序樹。9.2.1

二叉排序樹和平衡二叉樹9.2動(dòng)態(tài)查找表一、二叉排序樹及其查找過(guò)程2023/1/1926二叉排序樹上的查找：在二叉排序樹上進(jìn)行查找，是一個(gè)從根結(jié)點(diǎn)開始，沿某一個(gè)分支逐層向下進(jìn)行比較判等的過(guò)程。它可以是一個(gè)遞歸的過(guò)程，也可以是一個(gè)非遞歸的過(guò)程。假設(shè)想要在二叉排序樹中查找關(guān)鍵字為x的元素，查找過(guò)程從根結(jié)點(diǎn)開始。如果根指針為NULL，則查找不成功；否則用給定值x與根結(jié)點(diǎn)的關(guān)鍵字進(jìn)行比較：如果給定值等于根結(jié)點(diǎn)的關(guān)鍵字，則查找成功。如果給定值小于根結(jié)點(diǎn)的關(guān)鍵字，則繼續(xù)遞歸查找根結(jié)點(diǎn)的左子樹；否則,遞歸查找根結(jié)點(diǎn)的右子樹。9.2動(dòng)態(tài)查找表2023/1/1927BiTreeSearchBST(BiTreeT,KeyTypekey){if(!T)||EQ(key,T->data.key)return(T);elseif(LT(key,T->data.key))return(SearchBST(T->lchild,key));elsereturn(SearchBST(T->rchild,key));}BiTreeSearchBST(BiTreeT,KeyTypekey){p=T;//查找成功，返回指向該結(jié)點(diǎn)的指針，否則返回NULL。

while(p&&!EQ(key,p->data.key))if(LT(key,p->data.key))p=p->lchild;elsep=p->rchild;return(p);}遞歸查找算法非遞歸查找算法9.2動(dòng)態(tài)查找表2023/1/1928二叉排序樹的查找分析：BST的平均查找長(zhǎng)度與它的形態(tài)有關(guān)，最好情況下與折半查找的平均查找長(zhǎng)度一致，最壞情況下與順序查找一致。9.2動(dòng)態(tài)查找表2023/1/1929二、二叉排序樹的插入為了向二叉排序樹中插入一個(gè)新元素，必須先使用查找算法檢查這個(gè)元素是否在樹中已經(jīng)存在。查找成功:

樹中已有這個(gè)元素，不再插入。查找不成功:

樹中原來(lái)沒(méi)有關(guān)鍵字等于給定值的結(jié)點(diǎn)，把新元素加到查找操作停止的地方。9.2動(dòng)態(tài)查找表2023/1/1930BiTreeSearchBST(BiTreeT,KeyTypekey,BiTree&pre){//查找成功，返回指向要找的結(jié)點(diǎn)的指針，pre指向該結(jié)點(diǎn)的父結(jié)點(diǎn)；

//否則返回NULL，pre指向查找路徑上的最后一個(gè)結(jié)點(diǎn)。

p=T;pre=NULL;while(p&&!EQ(key,p->data.key){pre=p;if(LT(key,p->data.key))p=p->lchild;elsep=p->rchild;}return(p);}9.2動(dòng)態(tài)查找表修改后的非遞歸查找算法2023/1/1931StatusInsertBST(BiTree&T,ElemTypee){BiTreepre;if(!SearchBST(T,e.key,pre))//查找不成功

{s=(BiTNpde*)malloc(sizeof(BiTNode));//構(gòu)造新結(jié)點(diǎn)

s->data=e;s->lchild=s->rchild=NULL;if(!pre)T=s;//原樹為空時(shí)，新結(jié)點(diǎn)為根

elseif(LT(e.key,pre->data.key))pre->lchild=s;//新結(jié)點(diǎn)為左子結(jié)點(diǎn)

elsepre->rchild=s;//新結(jié)點(diǎn)為右子結(jié)點(diǎn)

return(OK);}return(FALSE);}9.2動(dòng)態(tài)查找表二叉排序樹的插入算法2023/1/1932

輸入數(shù)據(jù)序列

{53,78,65,17,87,09,81,45,23}，建立二叉排序樹的過(guò)程9.2動(dòng)態(tài)查找表2023/1/1933

同樣3個(gè)數(shù)據(jù){1,2,3

}，輸入順序不同，建立起來(lái)的二叉排序樹的形態(tài)也不同。這直接影響到二叉排序樹的查找性能。如果輸入序列選得不好，會(huì)建立起一棵單支樹，使得二叉排序樹的深度達(dá)到最大，這樣必然會(huì)降低查找性能。

{2,1,3}{1,2,3}{1,3,2}{2,3,1}{3,1,2}{3,2,1}

1231111322233239.2動(dòng)態(tài)查找表2023/1/1934三、二叉排序樹的刪除

在二叉排序樹中刪除一個(gè)結(jié)點(diǎn)時(shí)，必須將因刪除結(jié)點(diǎn)而斷開的二叉鏈表重新鏈接起來(lái)，同時(shí)確保二叉排序樹的性質(zhì)不會(huì)失去。刪除葉結(jié)點(diǎn)，只需將其雙親結(jié)點(diǎn)指向它的指針清零，再釋放它即可。被刪結(jié)點(diǎn)缺右子樹，可以拿它的左子女結(jié)點(diǎn)頂替它的位置，再釋放它。被刪結(jié)點(diǎn)缺左子樹，可以拿它的右子女結(jié)點(diǎn)頂替它的位置，再釋放它。被刪結(jié)點(diǎn)左、右子樹都存在，可以在它的右子樹中尋找中序下的第一個(gè)結(jié)點(diǎn)(關(guān)鍵字最小),用它的值填補(bǔ)到被刪結(jié)點(diǎn)中，再來(lái)處理這個(gè)結(jié)點(diǎn)的刪除問(wèn)題。9.2動(dòng)態(tài)查找表2023/1/19352023/1/1936StatusDeleteBST(BiTree&T,KeyTypekey){BiTreep,f,s,q;p=SearchBST(T,key,f);if(!p)return(FALSE);//不存在待刪除結(jié)點(diǎn)

if(!p->lchild||!p->rhcild)//待刪除結(jié)點(diǎn)無(wú)左子樹或右子樹

{q=(p->lchild)?p->lchild:p->rchild;if(!f)T=q;//為根結(jié)點(diǎn)

elseif(p==f->lchild)f->lchild=q;elsef->rchild=q;free(p);}9.2動(dòng)態(tài)查找表二叉排序樹的刪除算法2023/1/1937else//待刪除結(jié)點(diǎn)存在左、右子樹

{q=p;s=p->rchild;//找尋*p右子樹中的最左結(jié)點(diǎn)*swhile(s->lchild){q=s;//*q為*s的父結(jié)點(diǎn)

s=s->lchild;}p->data=s->data;//用*s代替*pif(q==p)p->rchild=s->rchild;elseq->lchild=s->rchild;//*s的右子樹為*q的左子樹

free(s);}return(TRUE);}9.2動(dòng)態(tài)查找表2023/1/1938四、平衡二叉樹（AVL）

1AVL樹的定義：一棵AVL（1962年由Adelson,Velskli和Landis提出）樹或者是空樹，或者是具有下列性質(zhì)的二叉排序樹：它的左子樹和右子樹都是AVL樹，且左子樹和右子樹的深度之差的絕對(duì)值不超過(guò)1。

深度不平衡的二叉排序樹深度平衡的二叉排序樹9.2動(dòng)態(tài)查找表2023/1/1939

2結(jié)點(diǎn)的平衡因子

(balancefactor)：每個(gè)結(jié)點(diǎn)附加一個(gè)數(shù)字，給出該結(jié)點(diǎn)右子樹的深度減去左子樹的深度（或左子樹的深度減去右子樹的深度）所得的深度差。這個(gè)數(shù)字即為結(jié)點(diǎn)的平衡因子balancefactor。根據(jù)AVL樹的定義，任一結(jié)點(diǎn)的平衡因子只能取-1，0和1。如果一個(gè)結(jié)點(diǎn)的平衡因子的絕對(duì)值大于1，則這棵二叉排序樹就失去了平衡，不再是AVL樹。如果一棵二叉排序樹是深度平衡的，它就成為AVL樹。如果它有n個(gè)結(jié)點(diǎn)，其深度可保持在O(log2n)，平均查找長(zhǎng)度也可保持在O(log2n)。9.2動(dòng)態(tài)查找表2023/1/19403平衡化旋轉(zhuǎn)：如果在一棵平衡的二叉排序樹中插入一個(gè)新結(jié)點(diǎn)，造成了不平衡。此時(shí)必須調(diào)整樹的結(jié)構(gòu)，使之平衡化。必須保證平衡化后的二叉樹依然是一棵二叉排序樹。每插入一個(gè)新結(jié)點(diǎn)時(shí)，AVL樹中相關(guān)結(jié)點(diǎn)的平衡狀態(tài)會(huì)發(fā)生改變。因此，在插入一個(gè)新結(jié)點(diǎn)后，需要從插入位置沿通向根的路徑回溯，檢查各結(jié)點(diǎn)的平衡因子(左、右子樹的深度差)。如果在某一結(jié)點(diǎn)發(fā)現(xiàn)深度不平衡，停止回溯。從發(fā)生不平衡的結(jié)點(diǎn)起，沿剛才回溯的路徑取直接下兩層的結(jié)點(diǎn)。9.2動(dòng)態(tài)查找表2023/1/1941如果這三個(gè)結(jié)點(diǎn)處于一條直線上，則采用單旋轉(zhuǎn)進(jìn)行平衡化。單旋轉(zhuǎn)可按其方向分為左單旋轉(zhuǎn)和右單旋轉(zhuǎn)，其中一個(gè)是另一個(gè)的鏡像，其方向與不平衡的形狀相關(guān)。如果這三個(gè)結(jié)點(diǎn)處于一條折線上，則采用雙旋轉(zhuǎn)進(jìn)行平衡化。雙旋轉(zhuǎn)分為先左后右和先右后左兩類。右單旋轉(zhuǎn)左單旋轉(zhuǎn)

左右雙旋轉(zhuǎn)右左雙旋轉(zhuǎn)9.2動(dòng)態(tài)查找表2023/1/1942hhhACEBD(a)(b)(c)hhh+1BACEDhhh+1CEABD（1）左單旋轉(zhuǎn)(RR型)：如果在子樹E中插入一個(gè)新結(jié)點(diǎn)，該子樹深度增1導(dǎo)致結(jié)點(diǎn)A的平衡因子變成+2，出現(xiàn)不平衡。沿插入路徑檢查三個(gè)結(jié)點(diǎn)A、C和E。它們處于一條方向?yàn)椤癨”的直線上，需要做左單旋轉(zhuǎn)。以結(jié)點(diǎn)C為旋轉(zhuǎn)軸，讓結(jié)點(diǎn)A反時(shí)針旋轉(zhuǎn)。+1+20+1009.2動(dòng)態(tài)查找表2023/1/1943hhhACEBD(a)(b)(c)hh+1BACEDhhh+1CEABD（2）右單旋轉(zhuǎn)(LL型)：在左子樹D上插入新結(jié)點(diǎn)使其深度增1，導(dǎo)致結(jié)點(diǎn)A的平衡因子增到-2，造成了不平衡。為使樹恢復(fù)平衡，從A沿插入路徑連續(xù)取3個(gè)結(jié)點(diǎn)A、B和D，它們處于一條方向?yàn)椤?”的直線上，需要做右單旋轉(zhuǎn)。以結(jié)點(diǎn)B為旋轉(zhuǎn)軸，將結(jié)點(diǎn)A順時(shí)針旋轉(zhuǎn)。h000-1-1-29.2動(dòng)態(tài)查找表2023/1/1944（3）先左后右雙旋轉(zhuǎn)(LR型)：在下圖中子樹F或G中插入新結(jié)點(diǎn)，該子樹的深度增1。結(jié)點(diǎn)A的平衡因子變?yōu)?2，發(fā)生了不平衡。從結(jié)點(diǎn)A起沿插入路徑選取3個(gè)結(jié)點(diǎn)A、B和E，它們位于一條形如“”的折線上，因此需要進(jìn)行先左后右的雙旋轉(zhuǎn)。首先以結(jié)點(diǎn)E為旋轉(zhuǎn)軸，將結(jié)點(diǎn)B反時(shí)針旋轉(zhuǎn)，以E代替原來(lái)B的位置，做左單旋轉(zhuǎn)。再以結(jié)點(diǎn)E為旋轉(zhuǎn)軸，將結(jié)點(diǎn)A順時(shí)針旋轉(zhuǎn)，做右單旋轉(zhuǎn)。使之平衡化。9.2動(dòng)態(tài)查找表2023/1/1945插入左單旋轉(zhuǎn)右單旋轉(zhuǎn)00-1-2+1-100+12023/1/1946

（4）先右后左雙旋轉(zhuǎn)(RL型)：右左雙旋轉(zhuǎn)是左右雙旋轉(zhuǎn)的鏡像。在下圖中子樹F或G中插入新結(jié)點(diǎn)，該子樹深度增1。結(jié)點(diǎn)A的平衡因子變?yōu)?，發(fā)生了不平衡。從結(jié)點(diǎn)A起沿插入路徑選取3個(gè)結(jié)點(diǎn)A、C和D，它們位于一條形如“”的折線上，需要進(jìn)行先右后左的雙旋轉(zhuǎn)。首先做右單旋轉(zhuǎn)：以結(jié)點(diǎn)D為旋轉(zhuǎn)軸，將結(jié)點(diǎn)C順時(shí)針旋轉(zhuǎn)，以D代替原來(lái)C的位置。再做左單旋轉(zhuǎn)：以結(jié)點(diǎn)D為旋轉(zhuǎn)軸，將結(jié)點(diǎn)A反時(shí)針旋轉(zhuǎn)，恢復(fù)樹的平衡。9.2動(dòng)態(tài)查找表2023/1/1947左單旋轉(zhuǎn)插入右單旋轉(zhuǎn)+10000-1-1+1+22023/1/1948161603163-10701-2左右雙旋731600073110-117316161190-1-2右單旋3716900013711269161101122例：輸入關(guān)鍵字序列{16,3,7,11,9,26,18,14,15}，

建立一棵AVL樹。2023/1/1949181803163-101602右左雙旋739000182611-1732616119-1左單旋9716140017112626911119.2動(dòng)態(tài)查找表2023/1/19501518231816-2左右雙旋73000117149-1161501112626141-29從空樹開始的建樹過(guò)程9.2動(dòng)態(tài)查找表2023/1/1951如右圖:用二叉樹組織文件，當(dāng)文件的記錄個(gè)數(shù)為100，000時(shí)，要找到給定關(guān)鍵字的記錄，需訪問(wèn)外存17次（log2100,000）,太長(zhǎng)了！502510751535609020304055708095索引文件數(shù)據(jù)文件文件頭，可常駐內(nèi)存文件訪問(wèn)示意圖：索引文件、數(shù)據(jù)文件存在盤上

為什么采用B-樹和B+樹：大量數(shù)據(jù)存放在外存中，通常存放在硬盤中，要多次訪問(wèn)外存。但硬盤的驅(qū)動(dòng)受機(jī)械運(yùn)動(dòng)的制約，速度慢。所以，主要矛盾變?yōu)闇p少訪外次數(shù)。用B-樹作為索引組織文件，可提高訪問(wèn)速度、減少時(shí)間。9.2動(dòng)態(tài)查找表9.2.2B-樹和B+樹2023/1/1952一、B-樹一棵m階B-樹是一棵m路查找樹，它或者是空樹，或者是滿足下列性質(zhì)的m叉樹：根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)時(shí)至少有2棵子樹。樹中每個(gè)結(jié)點(diǎn)至多有m棵子樹。除根結(jié)點(diǎn)以外的所有非葉子結(jié)點(diǎn)至少有m/2棵子樹。所有非葉子結(jié)點(diǎn)的組成為(n,A0,K1,A1,K2,A2,…,Kn,An)，n為關(guān)鍵字個(gè)數(shù)，Ki為關(guān)鍵字，Ai為指向子樹的指針。

Ai-1指向子樹的結(jié)點(diǎn)的關(guān)鍵字<Ki<Ai指向子樹的結(jié)點(diǎn)的關(guān)鍵字。所有的葉子結(jié)點(diǎn)都位于同一層（可看作是查找失敗的結(jié)點(diǎn)或外部結(jié)點(diǎn)，實(shí)際上為空）。一棵m階B-樹是一棵m叉有序平衡樹?！狟-樹及其查找9.2動(dòng)態(tài)查找2023/1/1953

例如：m=4階B-樹。除根結(jié)點(diǎn)和葉子結(jié)點(diǎn)之外，每個(gè)結(jié)點(diǎn)的孩子個(gè)數(shù) 至少為

個(gè)；結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)至少為1。該B-樹的深度為4。 葉子結(jié)點(diǎn)都在第4層上。1，993，47，58，641，391，271，112，43，781，181，35FFFFFFFFFFFF第1層第2層第3層(L層)第4層(L＋1層)9.2動(dòng)態(tài)查找表—B-樹2023/1/1954非B-樹（至少應(yīng)有2棵子樹）

B-樹

非B-樹和B-樹示例：9.2動(dòng)態(tài)查找表—B-樹2023/1/1955#definem3typedefstructBTNode{ //結(jié)點(diǎn)定義

int keynum;//結(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù)

structBTNode*parent; //雙親指針

KeyType key[m+1];//關(guān)鍵字?jǐn)?shù)組1m-1structBTNode*ptr[m+1]; //子樹指針數(shù)組0m};typedefstruct{BTNode *pt; //指向找到的結(jié)點(diǎn)

int i; //1..m,在結(jié)點(diǎn)中的關(guān)鍵字序號(hào)

int tag; //1:查找成功;0:查找失敗}Result; //B-樹的查找結(jié)果類型--B-樹的結(jié)點(diǎn)類型說(shuō)明9.2動(dòng)態(tài)查找表2023/1/1956ResultSearchBTree(BtreeT,KeyTypeK){//返回(pt,i,tag)。查找成功，tag=1，pt所指結(jié)點(diǎn)中第i個(gè)關(guān)鍵字等于K。

//查找失敗，則tag=0，K應(yīng)插到pt所指結(jié)點(diǎn)中第i和第i+1個(gè)關(guān)鍵字之間。

p=T;q=NULL;found=FALSE;while(p&&!found){for(i=p->keynum,p->key[0]=K;K<p->key[i];i--);//查找i,使p->key[i]<=K<p->key[i+1]if(i>0&&p->key[i]==K)found=TRUE; else{q=p;p=p->ptr[i];}}if(found)return(p,i,1);//查找成功

elsereturn(q,i,0);//查找不成功,返回插入位置}9.2動(dòng)態(tài)查找表–

B-樹的查找算法

2023/1/1957

B-樹的查找過(guò)程是一個(gè)在結(jié)點(diǎn)內(nèi)查找和循某一條路徑向下一層查找交替進(jìn)行的過(guò)程。在B-樹上進(jìn)行查找，查找成功所需的時(shí)間取決于關(guān)鍵字所在的層次，查找不成功所需的時(shí)間取決于樹的深度。從B-樹的定義知,每層關(guān)鍵字個(gè)數(shù)N最少有：第1層1個(gè)結(jié)點(diǎn)第2層至少2個(gè)結(jié)點(diǎn)第3層至少2m/2

個(gè)結(jié)點(diǎn)第4層至少2m/2

2個(gè)結(jié)點(diǎn)如此類推，第h

層至少有2m/2

h-2個(gè)結(jié)點(diǎn)。所有這些結(jié)點(diǎn)都不是失敗結(jié)點(diǎn)。----B-樹查找分析9.2動(dòng)態(tài)查找表2023/1/1958若樹中關(guān)鍵字有N個(gè),則失敗結(jié)點(diǎn)數(shù)為N+1。這是因?yàn)槭∫话惆l(fā)生在Ki<x<Ki+1,0i

N，設(shè)K0=-，KN+1=+。因此有

N+1=失敗結(jié)點(diǎn)數(shù)=位于第h+1層的結(jié)點(diǎn)數(shù)

2m/2

h-1

N

2m/2

h-1-1

反之，h

log

m/2

((N+1)/2)+1示例：若B-樹的階數(shù)m=199，關(guān)鍵字總數(shù)N=1999999，則B-樹的深度h不超過(guò)

log1001000000+1=4若B-樹的階數(shù)m=3，深度h=4，則關(guān)鍵字總數(shù)至少為N=23/2

4-1-1=159.2動(dòng)態(tài)查找表2023/1/1959---B-樹的插入B-樹是從空樹起，逐個(gè)插入關(guān)鍵字而生成的。插入從某個(gè)葉子結(jié)點(diǎn)開始。如果在關(guān)鍵字插入后結(jié)點(diǎn)中的關(guān)鍵字個(gè)數(shù)超出了上界m-1，則結(jié)點(diǎn)需要“分裂”，否則可以直接插入。實(shí)現(xiàn)結(jié)點(diǎn)“分裂”的原則是：設(shè)結(jié)點(diǎn)p中已經(jīng)有m-1個(gè)關(guān)鍵字，當(dāng)再插入一個(gè)關(guān)鍵字后結(jié)點(diǎn)中的狀態(tài)為(m,P0,K1,P1,K2,P2,……,Km,Pm)

其中Ki<Ki+1,1

i<m把結(jié)點(diǎn)p分裂成兩個(gè)結(jié)點(diǎn)p和q，它們包含的信息分別為：結(jié)點(diǎn)p：(m/2

-1,P0,K1,P1,……,Km/2

-1,Pm/2

-1)結(jié)點(diǎn)q：(m

-

m/2,Pm/2,Km/2+1,Pm/2+1,……,Km,Pm)位于中間的關(guān)鍵字Km/2

與指向新結(jié)點(diǎn)q的指針形成一個(gè)二元組(Km/2,q)，插入到這兩個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)中去。9.2動(dòng)態(tài)查找表2023/1/1960結(jié)點(diǎn)“分裂”的示例9.2動(dòng)態(tài)查找表2023/1/1961示例：從空樹開始逐個(gè)加入關(guān)鍵字建立3階B-樹2023/1/1962在插入新關(guān)鍵字時(shí)，需要自底向上分裂結(jié)點(diǎn)，最壞情況下從被插關(guān)鍵字所在葉結(jié)點(diǎn)到根的路徑上的所有結(jié)點(diǎn)都要分裂。9.2動(dòng)態(tài)查找表2023/1/1963---B-樹的刪除在B-樹上刪除一個(gè)關(guān)鍵字時(shí)，首先需要找到這個(gè)關(guān)鍵字所在的結(jié)點(diǎn)，從中刪去這個(gè)關(guān)鍵字。若該結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，且被刪關(guān)鍵字為Ki，1

i

n，則在刪去該關(guān)鍵字之后，應(yīng)以該結(jié)點(diǎn)Pi所指示子樹中的最小關(guān)鍵字x來(lái)代替被刪關(guān)鍵字Ki所在的位置，然后在x

所在的葉子結(jié)點(diǎn)中刪除x。9.2動(dòng)態(tài)查找表2023/1/1964在葉子結(jié)點(diǎn)上的刪除有以下4種情況：

1）被刪關(guān)鍵字所在葉子結(jié)點(diǎn)同時(shí)又是根結(jié)點(diǎn)且刪除前該結(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù)n

2，則直接刪去該關(guān)鍵字。

2）被刪關(guān)鍵字所在葉子結(jié)點(diǎn)不是根結(jié)點(diǎn)且刪除前該結(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù)n

m/2，則直接刪去該關(guān)鍵字。9.2動(dòng)態(tài)查找表---B-樹的刪除2023/1/1965刪除55簡(jiǎn)單刪除2023/1/19663）被刪關(guān)鍵字所在葉子結(jié)點(diǎn)刪除前關(guān)鍵字個(gè)數(shù)n=m/2

-1，若這時(shí)與該結(jié)點(diǎn)相鄰的右兄弟(或左兄弟)

結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)n

>m/2，則可按以下步驟調(diào)整該結(jié)點(diǎn)、右兄弟(或左兄弟)

結(jié)點(diǎn)以及其雙親結(jié)點(diǎn)，以達(dá)到新的平衡。將雙親結(jié)點(diǎn)中剛剛大于(或小于)

該被刪關(guān)鍵字的關(guān)鍵字Ki(1i

n)下移到被刪除的關(guān)鍵字位置；9.2動(dòng)態(tài)查找表2023/1/1967將右兄弟(或左兄弟)

結(jié)點(diǎn)中的最小(或最大)關(guān)鍵字上移到雙親結(jié)點(diǎn)的Ki位置；將右兄弟(或左兄弟)

結(jié)點(diǎn)中的最左(或最右)

子樹指針平移到被刪關(guān)鍵字所在結(jié)點(diǎn)中最后(或最前)

子樹指針位置；在右兄弟(或左兄弟)

結(jié)點(diǎn)中，將被移走的關(guān)鍵字和指針位置用剩余的關(guān)鍵字和指針填補(bǔ)、調(diào)整。再將結(jié)點(diǎn)中的關(guān)鍵字個(gè)數(shù)減1。9.2動(dòng)態(tài)查找表2023/1/1968刪除65結(jié)點(diǎn)聯(lián)合調(diào)整2023/1/1969刪除702023/1/19704）被刪關(guān)鍵字所在葉子結(jié)點(diǎn)刪除前關(guān)鍵字個(gè)數(shù)n=m/2

-1，若這時(shí)與該結(jié)點(diǎn)相鄰的右兄弟(或左兄弟)

結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)n=m/2

-1，則必須按以下步驟合并這兩個(gè)結(jié)點(diǎn)。將雙親結(jié)點(diǎn)p中相應(yīng)關(guān)鍵字下移到選定保留的結(jié)點(diǎn)中。若要合并p中的子樹指針Pi與Pi+1所指的結(jié)點(diǎn)，且保留Pi所指結(jié)點(diǎn)，則把p中的關(guān)鍵字Ki+1下移到Pi所指的結(jié)點(diǎn)中。9.2動(dòng)態(tài)查找表2023/1/1971把p中子樹指針Pi+1所指結(jié)點(diǎn)中的全部指針和關(guān)鍵字都照搬到Pi所指結(jié)點(diǎn)的后面。刪去Pi+1所指的結(jié)點(diǎn)。在結(jié)點(diǎn)p中用后面剩余的關(guān)鍵字和指針填補(bǔ)關(guān)鍵字Ki+1和指針Pi+1。修改結(jié)點(diǎn)

p

和選定保留結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)。9.2動(dòng)態(tài)查找表2023/1/1972刪除55結(jié)點(diǎn)合并2023/1/1973刪除80結(jié)點(diǎn)合并2023/1/1974非葉結(jié)點(diǎn)刪除刪除50刪除552023/1/1975結(jié)點(diǎn)合并與調(diào)整刪除702023/1/1976刪除752023/1/1977在合并結(jié)點(diǎn)的過(guò)程中，雙親結(jié)點(diǎn)中的關(guān)鍵字個(gè)數(shù)減少了。若雙親結(jié)點(diǎn)是根結(jié)點(diǎn)且結(jié)點(diǎn)關(guān)鍵字個(gè)數(shù)減到0，則該雙親結(jié)點(diǎn)應(yīng)從樹上刪去，合并后保留的結(jié)點(diǎn)成為新的根結(jié)點(diǎn)；否則將雙親結(jié)點(diǎn)與合并后保留的結(jié)點(diǎn)都寫回磁盤，刪除處理結(jié)束。若雙親結(jié)點(diǎn)不是根結(jié)點(diǎn)，且關(guān)鍵字個(gè)數(shù)減到m/2

-2，又要與它自己的兄弟結(jié)點(diǎn)合并，重復(fù)上面的合并步驟。最壞情況下這種結(jié)點(diǎn)合并處理要自下向上直到根結(jié)點(diǎn)。9.2動(dòng)態(tài)查找表2023/1/1978---B+樹B+樹可以看作是B-樹的一種變形，在實(shí)現(xiàn)文件索引結(jié)構(gòu)方面比B-樹使用得更普遍。一棵m階B+樹與m階B-樹的主要差別如下：有n棵子樹的結(jié)點(diǎn)含有n個(gè)關(guān)鍵字；所有的葉子結(jié)點(diǎn)都處于同一層次上，包含了全部關(guān)鍵字及指向相應(yīng)數(shù)據(jù)元素存放地址的指針，且葉子結(jié)點(diǎn)本身按關(guān)鍵字從小到大順序鏈接；所有的非葉子結(jié)點(diǎn)可以看成是索引部分，結(jié)點(diǎn)中關(guān)鍵字Ki與指向子樹的指針Pi構(gòu)成其子樹(即下一層索引塊)的索引項(xiàng)(Ki,Pi

)，Ki是子樹中最大的關(guān)鍵字。9.2動(dòng)態(tài)查找表2023/1/1979在B+樹中有兩個(gè)頭指針：一個(gè)指向B+樹的根結(jié)點(diǎn)，一個(gè)指向關(guān)鍵字最小的葉子結(jié)點(diǎn)?？蓪?duì)B+樹進(jìn)行兩種查找運(yùn)算：一種是循葉子結(jié)點(diǎn)鏈的順序查找，另一種是從根結(jié)點(diǎn)開始的隨機(jī)查找。在B+樹上進(jìn)行隨機(jī)查找、插入和刪除的過(guò)程基本上與B-樹類似。只是在查找過(guò)程中，如果非葉子結(jié)點(diǎn)上的關(guān)鍵字等于給定值，查找并不停止，而是繼續(xù)沿右指針向下，一直查到葉子結(jié)點(diǎn)上的這個(gè)關(guān)鍵字。B+樹的查找分析類似于B_樹。9.2動(dòng)態(tài)查找表2023/1/1980本節(jié)課后作業(yè)

“數(shù)據(jù)結(jié)構(gòu)題集（C語(yǔ)言版）”

P559.3、P569.11P569.132023/1/1981哈希方法在數(shù)據(jù)元素的存儲(chǔ)位置與它的關(guān)鍵字之間建立一個(gè)確定的對(duì)應(yīng)函數(shù)關(guān)系Hash()，使每個(gè)關(guān)鍵字與結(jié)構(gòu)中一個(gè)存儲(chǔ)位置相對(duì)應(yīng)：

Address

＝Hash(key)在查找時(shí)，首先對(duì)數(shù)據(jù)元素的關(guān)鍵字進(jìn)行函數(shù)計(jì)算，把函數(shù)值當(dāng)做數(shù)據(jù)元素的存儲(chǔ)位置，在結(jié)構(gòu)中按此位置取數(shù)據(jù)元素比較。若關(guān)鍵字相等，則查找成功。在存放數(shù)據(jù)元素時(shí)，依相同函數(shù)計(jì)算存儲(chǔ)位置，并按此位置存放。這種方法就是哈希方法。在哈希方法中使用的轉(zhuǎn)換函數(shù)叫做哈希函數(shù)。而按此種想法構(gòu)造出來(lái)的表或結(jié)構(gòu)就叫做哈希表。使用哈希方法進(jìn)行查找不必進(jìn)行多次關(guān)鍵字的比較，查找速度比較快，可以直接到達(dá)或逼近具有此關(guān)鍵字的數(shù)據(jù)元素的實(shí)際存放地址。E.g.

電話區(qū)號(hào)=Hash(城市名)9.3哈希表9.3.1什么是哈希表2023/1/1982哈希函數(shù)是一個(gè)壓縮映象函數(shù)。關(guān)鍵字集合比哈希表地址集合大得多。因此有可能經(jīng)過(guò)哈希函數(shù)的計(jì)算，把不同的關(guān)鍵字映射到同一個(gè)哈希地址上，這就產(chǎn)生了沖突

(Collision)。例：有一組數(shù)據(jù)元素，其關(guān)鍵字分別是12361,07251,03309,30976

采用的哈希函數(shù)是hash(x)=x%73+13420

其中，“%”是除法取余操作。則有：hash(12361)=hash(07251)=hash(03309)=hash(30976)=13444。就是說(shuō)，對(duì)不同的關(guān)鍵字，通過(guò)哈希函數(shù)的計(jì)算，得到了同一哈希地址。這些產(chǎn)生沖突的哈希地址相同的不同關(guān)鍵字稱為同義詞。見P252表9.1由于關(guān)鍵字集合比地址集合大得多，沖突很難避免。所以對(duì)于哈希方法，需要討論以下兩個(gè)問(wèn)題：對(duì)于給定的一個(gè)關(guān)鍵字集合，選擇一個(gè)計(jì)算簡(jiǎn)單且地址分布比較均勻的哈希函數(shù)，避免或盡量減少?zèng)_突；擬訂解決沖突的方案。9.3哈希表2023/1/1983構(gòu)造哈希函數(shù)時(shí)的幾點(diǎn)要求：哈希函數(shù)的定義域必須包括需要存儲(chǔ)的全部關(guān)鍵字，如果哈希表允許有m個(gè)地址時(shí),其值域必須在0到m-1之間。哈希函數(shù)計(jì)算出來(lái)的地址應(yīng)能均勻分布在整個(gè)地址空間中：若key

是從關(guān)鍵字集合中隨機(jī)抽取的一個(gè)關(guān)鍵字，哈希函數(shù)應(yīng)能以同等概率取0到m-1中的每一個(gè)值。哈希函數(shù)應(yīng)是簡(jiǎn)單的，能在較短的時(shí)間內(nèi)計(jì)算出結(jié)果。9.3.2

哈希函數(shù)的構(gòu)造方法9.3哈希表

1.直接定址法此類函數(shù)取關(guān)鍵字的某個(gè)線性函數(shù)值作為哈希地址：

Hash(key)＝a*key+b{a,b為常數(shù)}

這類哈希函數(shù)是一對(duì)一的映射，不會(huì)產(chǎn)生沖突。但是，它要求哈希地址空間的大小與關(guān)鍵字集合的大小相同。2023/1/1984

示例：有一組關(guān)鍵字如下：{942148,941269,940527,941630,941805,941558,942047,940001}。哈希函數(shù)為

Hash(key)=key

-940000

則有

Hash(942148)=2148Hash(941269)=1269 Hash(940527)=527Hash(941630)=1630 Hash(941805)=1805Hash(941558)=1558 Hash(942047)=2047Hash(940001)=1

可以按計(jì)算出的地址存放記錄。

2.數(shù)字分析法設(shè)有n個(gè)d位數(shù)，每一位可能有r種不同的符號(hào)。這r種不同的符號(hào)在各位上出現(xiàn)的頻率不一定相同，可能在某些位上分布均勻些；在某些位上分布不均勻，只有某幾種符號(hào)經(jīng)常出現(xiàn)。可根據(jù)哈希表的大小，選取其中各種符號(hào)分布均勻的若干位作為哈希地址。9.3哈希表2023/1/1985示例：若哈希表地址范圍有3位數(shù)字,取各關(guān)鍵字的④⑤⑥位做為記錄的哈希地址。也可以把第①，②，③和第⑤位相加，舍去進(jìn)位位，變成一位數(shù)，與第④，⑥位合起來(lái)作為哈希地址。還有其它方法。 ①②③④⑤⑥

942148 941269 940527 941630 941805 941558 942047 940001 數(shù)字分析法僅適用于事先明確知道表中所有關(guān)鍵字每一位數(shù)值的分布情況，它完全依賴于關(guān)鍵字集合。如果換一個(gè)關(guān)鍵字集合，選擇哪幾位要重新決定。9.3哈希表2023/1/1986

3.除留余數(shù)法設(shè)哈希表的地址范圍是0到m-1,取一個(gè)不大于m，但最接近于或等于m的質(zhì)數(shù)p,利用以下公式把關(guān)鍵字轉(zhuǎn)換成哈希地址。哈希函數(shù)為：

hash(key)=key%p p

m示例：有一個(gè)關(guān)鍵字key=962148，哈希表大小m=25，即HT[25]。取質(zhì)數(shù)p=23。哈希函數(shù)hash(key)=key%p。則哈希地址為

hash(962148)=962148%23=12?？梢园从?jì)算出的地址存放記錄。需要注意的是，使用上面的哈希函數(shù)計(jì)算出來(lái)的地址范圍是0到22，因此，從23到24這幾個(gè)哈希地址實(shí)際上在一開始是不可能用哈希函數(shù)計(jì)算出來(lái)的，只可能在處理溢出時(shí)達(dá)到這些地址。9.3哈希表2023/1/1987

4.乘余取整法使用此方法時(shí)，先讓關(guān)鍵字key乘上一個(gè)常數(shù)A(0<A<1)，提取乘積的小數(shù)部分。然后，再用整數(shù)m乘以這個(gè)值，對(duì)結(jié)果向下取整，把它做為哈希的地址。哈希函數(shù)為：

hash(key)=

m*(A*key

-

A*key

)

其中,“A*key

-

A*key

”表示取A*key的小數(shù)部分。示例：設(shè)關(guān)鍵字key=123456，m=10000，且A=0.6180339，則

hash(123456)==10000*(0.6180339*123456-0.6180339*123456)=10000*(76300.0041151-76300)=10000*0.0041151

=41.151=41哈希表的地址范圍是0到m-1。9.3哈希表2023/1/19885.平方取中法先計(jì)算構(gòu)成關(guān)鍵字的標(biāo)識(shí)符的內(nèi)碼的平方，然后按照哈希表的大小取中間的若干位作為哈希地址。設(shè)標(biāo)識(shí)符可以用一個(gè)計(jì)算機(jī)字長(zhǎng)的內(nèi)碼表示。因?yàn)閮?nèi)碼平方數(shù)的中間幾位一般是由標(biāo)識(shí)符所有字符決定，所以對(duì)不同的標(biāo)識(shí)符計(jì)算出的哈希地址大多不相同，例標(biāo)識(shí)符的八進(jìn)制內(nèi)碼表示及其平方值。 標(biāo)識(shí)符內(nèi)碼 內(nèi)碼的平方哈希地址 A 01 01 001 A1 0134 20420 042 A9 0144 23420 342 B 02 04 004 DMAX04150130 21526443617100 443 DMAX1 5264473522151420 352 AMAX01150130 135423617100 236 AMAX1 3454246522151420 6529.3哈希表2023/1/19896.折疊法此方法把關(guān)鍵字自左到右分成位數(shù)相等的幾部分，每一部分的位數(shù)應(yīng)與哈希表地址位數(shù)相同，只有最后一部分的位數(shù)可以短一些。把這些部分的數(shù)據(jù)疊加起來(lái)，就可以得到具有該關(guān)鍵字的記錄的哈希地址。有兩種疊加方法：

移位法

—

把各部分的最后一位對(duì)齊相加；

分界法

—

各部分不折斷，沿各部分的分界來(lái)回折疊，然后對(duì)齊相加，將相加的結(jié)果當(dāng)做哈希地址示例：設(shè)給定的關(guān)鍵字為key=23938587841，若存儲(chǔ)空間限定3位,則劃分結(jié)果為每段3位.上述關(guān)鍵字可劃分為4段：

239

385

878

419.3哈希表2023/1/1990把超出地址位數(shù)的最高位刪去,僅保留最低的3位，做為可用的哈希地址。一般當(dāng)關(guān)鍵字的位數(shù)很多，而且關(guān)鍵字每一位上數(shù)字的分布大致比較均勻時(shí)，可用這種方法得到哈希地址。9.3哈希表2023/1/19919.3.3處理沖突的方法

解決沖突的方法又稱為溢出處理技術(shù)。因?yàn)榻^大多數(shù)哈希函數(shù)不能避免產(chǎn)生沖突，因此選擇好的解決沖突的方法十分重要。9.3哈希表1開放地址法若設(shè)哈希表中的地址為0到m-1，當(dāng)要加入一個(gè)數(shù)據(jù)元素R2時(shí),用它的關(guān)鍵字R2.key，通過(guò)哈希函數(shù)hash(R2.key)的計(jì)算，得到它的存放位置j，但是在存放時(shí)發(fā)現(xiàn)這個(gè)位置已經(jīng)被另一個(gè)數(shù)據(jù)元素R1占據(jù)了。這時(shí)不但發(fā)生了沖突，還必須處理溢出。為此，必須把R2存放到表中“下一個(gè)”空位置中。如果表未滿，則在允許的范圍內(nèi)必定還有空位置。2023/1/1992(1)線性探測(cè)法(LinearProbing)9.3哈希表需要查找或加入一個(gè)數(shù)據(jù)元素時(shí)，使用哈希函數(shù)計(jì)算位置號(hào)：

H0=hash(key)一旦發(fā)生沖突，在表中順次向后尋找“下一個(gè)”空位置Hi的公式為：

Hi

=(Hi-1+1)%m，i=1,2,…,m-1

即用以下的線性探測(cè)序列在表中尋找“下一個(gè)”空位置：

H0+1,H0+2,…,m-1,0,1,2,…,H0-1

亦可寫成Hi=(H0

+di)%m，di

=1,2,…,m-1

其中H0=hash(key)稱為Hash函數(shù),m稱為Hash表長(zhǎng);當(dāng)發(fā)生沖突時(shí),探查下一個(gè)位置。當(dāng)循環(huán)m-1次后就會(huì)回到開始探查時(shí)的位置,說(shuō)明待查關(guān)鍵字不在表內(nèi),而且表已滿,不能再插入新關(guān)鍵字。2023/1/19939.3哈希表假設(shè)一組數(shù)據(jù)元素的關(guān)鍵字為(19,14,23,01,68,20,84,27,55,11,10,79)。哈希表為HT[16]，哈希函數(shù)為Hash(key)=key%13，采用線性探查法處理沖突，則上述關(guān)鍵字在哈希表中的存儲(chǔ)位置如下圖所示，其中HT上面的數(shù)字表示關(guān)鍵字找到空位置所需要的探查次數(shù)，平均查找長(zhǎng)度=探查次數(shù)之和/元素個(gè)數(shù)，即30/12=2.5HT線性探查方法容易產(chǎn)生“堆積”，即在處理沖突過(guò)程中發(fā)生的兩個(gè)第一個(gè)哈希地址不同的元素爭(zhēng)奪同一個(gè)后續(xù)地址的現(xiàn)象，顯然這將會(huì)導(dǎo)致查找時(shí)間增加。2023/1/1994(2)二次探測(cè)法(quadraticprobing)為改善“堆積”問(wèn)題，減少為完成查找所需的平均探查次數(shù)，可使用二次探查法。令哈希函數(shù)為：

H0=hash(x)二次探查法在表中尋找“下一個(gè)”空位置的公式為：

Hi=(H0

+di)%m，di

=12,-12,22,-22,…,k2,-k2式中的m是表的大小，當(dāng)m是一個(gè)值為4k+3

（k是整數(shù)）的質(zhì)數(shù)時(shí)，采用二次探查法的Hi才能找到哈希表的每一個(gè)位置。在做(H0+

di)%m的運(yùn)算時(shí)，H0+

di

可能為負(fù)數(shù)，因此實(shí)際算式可改為：

if((H0+di)<0)j=(H0

+di+m)%m9.3哈希表2023/1/1995假設(shè)一組數(shù)據(jù)元素的關(guān)鍵字為(19,14,23,01,68,20,84,27,55,11,10)。哈希表為HT[11]，采用的哈希函數(shù)是：

Hash(key)=key%11

采用二次探查法處理溢出，則上述關(guān)鍵字在哈希表中哈希位置如圖所示，HT上面的數(shù)字表示關(guān)鍵字找到空位置所需要的比較次數(shù)。9.3哈希表HT其中，求關(guān)鍵字10的存儲(chǔ)位置的過(guò)程為：

H0=10%11=10; (10+1)%11=0;(10-1)%11=9;(10+4)%11=3; (10-4)%11=6;(10+9)%11=8;(10-9)%11=1;······

平均查找長(zhǎng)度22/11=22023/1/19962鏈地址法采用鏈地址法解決沖突時(shí)，首先對(duì)關(guān)鍵字集合用某一個(gè)哈希函數(shù)計(jì)算它們的存放位置。若設(shè)哈希表地址空間的所有位置是從0到m-1，則關(guān)鍵字集合中的所有關(guān)鍵字被劃分為m個(gè)子集，具有相同地址的關(guān)鍵字歸于同一子集。同一子集中的關(guān)鍵字互稱為同義詞。通常關(guān)鍵字互為同義詞的數(shù)據(jù)元素通過(guò)一個(gè)單鏈表鏈接起來(lái)，稱之為同義詞子表。所有關(guān)鍵字互為同義詞的數(shù)據(jù)元素都鏈接在同一個(gè)同義詞子表中，各鏈表的表頭結(jié)點(diǎn)組成一個(gè)向量。向量的元素個(gè)數(shù)與地址空間的位置數(shù)一致。向量中的第i個(gè)元素中存放哈希函數(shù)為i的同義詞子表的頭指針。9.3哈希表2023/1/19979.3哈希表假設(shè)一組數(shù)據(jù)元素的關(guān)鍵字為(19,14,23,01,68,20,84,27,55,11,10,79)。哈希表為HT[13]，采用的哈希函數(shù)是：

Hash(key)=key%13采用鏈地址法