數(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動態(tài)查找表9.3哈希表

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

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

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

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

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

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

順序查找的平均查找長度

設(shè)查找第

i

個元素的概率為pi，查找到第

i

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

ci，則查找成功的平均查找長度:

在順序查找情形，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個元素存放在一個有序順序表中，并按其關(guān)鍵字從小到大排好了序。采用折半查找時，先求位于查找區(qū)間正中的元素的下標(biāo)mid，mid=|(low+high)/2」,用其關(guān)鍵字與給定值x比較:elem[mid].key=x，查找成功；elem[mid].key>x，把查找區(qū)間縮小到表的前半部分，再繼續(xù)進行折半查找；elem[mid].key<x，把查找區(qū)間縮小到表的后半部分，再繼續(xù)進行折半查找。每比較一次，查找區(qū)間縮小一半。如果查找區(qū)間已縮小到一個元素，仍未找到想要查找的元素，則查找失敗。9.1靜態(tài)查找表2023/1/19110513192137566475808892lowmidhigh例Key=21的查找過程：midlowhigh0513192137566475808892midlowhigh05131921375664758088929.1靜態(tài)查找表12345678910112023/1/19120513192137566475808892lowmidhigh例Key=85的查找過程：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é)點有1個，查找第1層結(jié)點要比較1次；第2層結(jié)點有2個，查找第2層結(jié)點要比較2次；…。63124597810119.1靜態(tài)查找表2023/1/1915第i(1

i

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

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

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

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

先在索引表ID

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

ID[i-1].max_key<K

ID[i].max_key

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

ASLIndexSeq=ASLIndex

+ASLSubList其中，ASLIndex

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

ASLIndexSeq=(b+1)/2+(s+1)/2=(b+s)/2+1索引查找的平均查找長度不僅與表中的元素個數(shù)n有關(guān)，而且與每個子表中的元素個數(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=

時，ASLIndexSeq取極小值+1。這個值比順序查找強，但比折半查找差。若采用折半查找確定元素所在的子表，則查找成功時的平均查找長度為

ASLIndexSeq=ASLIndex

+ASLSubList

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

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

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

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

左子樹和右子樹也是二叉排序樹。特點：

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

二叉排序樹和平衡二叉樹9.2動態(tài)查找表一、二叉排序樹及其查找過程2023/1/1926二叉排序樹上的查找：在二叉排序樹上進行查找，是一個從根結(jié)點開始，沿某一個分支逐層向下進行比較判等的過程。它可以是一個遞歸的過程，也可以是一個非遞歸的過程。假設(shè)想要在二叉排序樹中查找關(guān)鍵字為x的元素，查找過程從根結(jié)點開始。如果根指針為NULL，則查找不成功；否則用給定值x與根結(jié)點的關(guān)鍵字進行比較：如果給定值等于根結(jié)點的關(guān)鍵字，則查找成功。如果給定值小于根結(jié)點的關(guān)鍵字，則繼續(xù)遞歸查找根結(jié)點的左子樹；否則,遞歸查找根結(jié)點的右子樹。9.2動態(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é)點的指針，否則返回NULL。

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

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

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

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

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動態(tài)查找表修改后的非遞歸查找算法2023/1/1931StatusInsertBST(BiTree&T,ElemTypee){BiTreepre;if(!SearchBST(T,e.key,pre))//查找不成功

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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動態(tài)查找表2023/1/1938四、平衡二叉樹（AVL）

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

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

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

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

左右雙旋轉(zhuǎn)右左雙旋轉(zhuǎn)9.2動態(tài)查找表2023/1/1942hhhACEBD(a)(b)(c)hhh+1BACEDhhh+1CEABD（1）左單旋轉(zhuǎn)(RR型)：如果在子樹E中插入一個新結(jié)點，該子樹深度增1導(dǎo)致結(jié)點A的平衡因子變成+2，出現(xiàn)不平衡。沿插入路徑檢查三個結(jié)點A、C和E。它們處于一條方向為“\”的直線上，需要做左單旋轉(zhuǎn)。以結(jié)點C為旋轉(zhuǎn)軸，讓結(jié)點A反時針旋轉(zhuǎn)。+1+20+1009.2動態(tài)查找表2023/1/1943hhhACEBD(a)(b)(c)hh+1BACEDhhh+1CEABD（2）右單旋轉(zhuǎn)(LL型)：在左子樹D上插入新結(jié)點使其深度增1，導(dǎo)致結(jié)點A的平衡因子增到-2，造成了不平衡。為使樹恢復(fù)平衡，從A沿插入路徑連續(xù)取3個結(jié)點A、B和D，它們處于一條方向為“/”的直線上，需要做右單旋轉(zhuǎn)。以結(jié)點B為旋轉(zhuǎn)軸，將結(jié)點A順時針旋轉(zhuǎn)。h000-1-1-29.2動態(tài)查找表2023/1/1944（3）先左后右雙旋轉(zhuǎn)(LR型)：在下圖中子樹F或G中插入新結(jié)點，該子樹的深度增1。結(jié)點A的平衡因子變?yōu)?2，發(fā)生了不平衡。從結(jié)點A起沿插入路徑選取3個結(jié)點A、B和E，它們位于一條形如“”的折線上，因此需要進行先左后右的雙旋轉(zhuǎn)。首先以結(jié)點E為旋轉(zhuǎn)軸，將結(jié)點B反時針旋轉(zhuǎn)，以E代替原來B的位置，做左單旋轉(zhuǎn)。再以結(jié)點E為旋轉(zhuǎn)軸，將結(jié)點A順時針旋轉(zhuǎn)，做右單旋轉(zhuǎn)。使之平衡化。9.2動態(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é)點，該子樹深度增1。結(jié)點A的平衡因子變?yōu)?，發(fā)生了不平衡。從結(jié)點A起沿插入路徑選取3個結(jié)點A、C和D，它們位于一條形如“”的折線上，需要進行先右后左的雙旋轉(zhuǎn)。首先做右單旋轉(zhuǎn)：以結(jié)點D為旋轉(zhuǎn)軸，將結(jié)點C順時針旋轉(zhuǎn)，以D代替原來C的位置。再做左單旋轉(zhuǎn)：以結(jié)點D為旋轉(zhuǎn)軸，將結(jié)點A反時針旋轉(zhuǎn)，恢復(fù)樹的平衡。9.2動態(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動態(tài)查找表2023/1/19501518231816-2左右雙旋73000117149-1161501112626141-29從空樹開始的建樹過程9.2動態(tài)查找表2023/1/1951如右圖:用二叉樹組織文件，當(dāng)文件的記錄個數(shù)為100，000時，要找到給定關(guān)鍵字的記錄，需訪問外存17次（log2100,000）,太長了！502510751535609020304055708095索引文件數(shù)據(jù)文件文件頭，可常駐內(nèi)存文件訪問示意圖：索引文件、數(shù)據(jù)文件存在盤上

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

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

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

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

B-樹

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

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

structBTNode*parent; //雙親指針

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

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

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

//查找失敗，則tag=0，K應(yīng)插到pt所指結(jié)點中第i和第i+1個關(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動態(tài)查找表–

B-樹的查找算法

2023/1/1957

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

個結(jié)點第4層至少2m/2

2個結(jié)點如此類推，第h

層至少有2m/2

h-2個結(jié)點。所有這些結(jié)點都不是失敗結(jié)點。----B-樹查找分析9.2動態(tài)查找表2023/1/1958若樹中關(guān)鍵字有N個,則失敗結(jié)點數(shù)為N+1。這是因為失敗一般發(fā)生在Ki<x<Ki+1,0i

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

N+1=失敗結(jié)點數(shù)=位于第h+1層的結(jié)點數(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不超過

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

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

其中Ki<Ki+1,1

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

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

-1,Pm/2

-1)結(jié)點q：(m

-

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

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

i

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

p

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

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

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

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

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

Address

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

電話區(qū)號=Hash(城市名)9.3哈希表9.3.1什么是哈希表2023/1/1982哈希函數(shù)是一個壓縮映象函數(shù)。關(guān)鍵字集合比哈希表地址集合大得多。因此有可能經(jīng)過哈希函數(shù)的計算，把不同的關(guān)鍵字映射到同一個哈希地址上，這就產(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。就是說，對不同的關(guān)鍵字，通過哈希函數(shù)的計算，得到了同一哈希地址。這些產(chǎn)生沖突的哈希地址相同的不同關(guān)鍵字稱為同義詞。見P252表9.1由于關(guān)鍵字集合比地址集合大得多，沖突很難避免。所以對于哈希方法，需要討論以下兩個問題：對于給定的一個關(guān)鍵字集合，選擇一個計算簡單且地址分布比較均勻的哈希函數(shù)，避免或盡量減少沖突；擬訂解決沖突的方案。9.3哈希表2023/1/1983構(gòu)造哈希函數(shù)時的幾點要求：哈希函數(shù)的定義域必須包括需要存儲的全部關(guān)鍵字，如果哈希表允許有m個地址時,其值域必須在0到m-1之間。哈希函數(shù)計算出來的地址應(yīng)能均勻分布在整個地址空間中：若key

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

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

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

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

這類哈希函數(shù)是一對一的映射，不會產(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

可以按計算出的地址存放記錄。

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

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

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

hash(key)=key%p p

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

hash(962148)=962148%23=12?？梢园从嬎愠龅牡刂反娣庞涗洝Ｐ枰⒁獾氖?，使用上面的哈希函數(shù)計算出來的地址范圍是0到22，因此，從23到24這幾個哈希地址實際上在一開始是不可能用哈希函數(shù)計算出來的，只可能在處理溢出時達(dá)到這些地址。9.3哈希表2023/1/1987

4.乘余取整法使用此方法時，先讓關(guān)鍵字key乘上一個常數(shù)A(0<A<1)，提取乘積的小數(shù)部分。然后，再用整數(shù)m乘以這個值，對結(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.平方取中法先計算構(gòu)成關(guān)鍵字的標(biāo)識符的內(nèi)碼的平方，然后按照哈希表的大小取中間的若干位作為哈希地址。設(shè)標(biāo)識符可以用一個計算機字長的內(nèi)碼表示。因為內(nèi)碼平方數(shù)的中間幾位一般是由標(biāo)識符所有字符決定，所以對不同的標(biāo)識符計算出的哈希地址大多不相同，例標(biāo)識符的八進制內(nèi)碼表示及其平方值。 標(biāo)識符內(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ù)疊加起來，就可以得到具有該關(guān)鍵字的記錄的哈希地址。有兩種疊加方法：

移位法

—

把各部分的最后一位對齊相加；

分界法

—

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

239

385

878

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

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

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

Hi

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

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

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表長;當(dāng)發(fā)生沖突時,探查下一個位置。當(dāng)循環(huán)m-1次后就會回到開始探查時的位置,說明待查關(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)鍵字在哈希表中的存儲位置如下圖所示，其中HT上面的數(shù)字表示關(guān)鍵字找到空位置所需要的探查次數(shù)，平均查找長度=探查次數(shù)之和/元素個數(shù)，即30/12=2.5HT線性探查方法容易產(chǎn)生“堆積”，即在處理沖突過程中發(fā)生的兩個第一個哈希地址不同的元素爭奪同一個后續(xù)地址的現(xiàn)象，顯然這將會導(dǎo)致查找時間增加。2023/1/1994(2)二次探測法(quadraticprobing)為改善“堆積”問題，減少為完成查找所需的平均探查次數(shù)，可使用二次探查法。令哈希函數(shù)為：

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

Hi=(H0

+di)%m，di

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

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

di)%m的運算時，H0+

di

可能為負(fù)數(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的存儲位置的過程為：

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;······

平均查找長度22/11=22023/1/19962鏈地址法采用鏈地址法解決沖突時，首先對關(guān)鍵字集合用某一個哈希函數(shù)計算它們的存放位置。若設(shè)哈希表地址空間的所有位置是從0到m-1，則關(guān)鍵字集合中的所有關(guān)鍵字被劃分為m個子集，具有相同地址的關(guān)鍵字歸于同一子集。同一子集中的關(guān)鍵字互稱為同義詞。通常關(guān)鍵字互為同義詞的數(shù)據(jù)元素通過一個單鏈表鏈接起來，稱之為同義詞子表。所有關(guān)鍵字互為同義詞的數(shù)據(jù)元素都鏈接在同一個同義詞子表中，各鏈表的表頭結(jié)點組成一個向量。向量的元素個數(shù)與地址空間的位置數(shù)一致。向量中的第i個元素中存放哈希函數(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采用鏈地址法