演示文稿數(shù)據(jù)結(jié)構(gòu)第九章查找

（優(yōu)選）數(shù)據(jù)結(jié)構(gòu)第九章查找目前一頁\總數(shù)八十四頁\編于十六點第九章查找

查找表:由同一類型的數(shù)據(jù)元素（記錄）組成的集合。記作：ST={a1,a2,...,an}學號姓名性別數(shù)學外語200041劉大海

男8075200042王偉

男9083200046吳曉英

女8288200048王偉女8090.....................序號1234n●關(guān)鍵字:可以標識一個記錄的數(shù)據(jù)項●

主關(guān)鍵字:可以唯一地標識一個記錄的數(shù)據(jù)項●

次關(guān)鍵字:可以識別若干記錄的數(shù)據(jù)項學生成績表數(shù)據(jù)項1(主關(guān)鍵字)數(shù)據(jù)項2數(shù)據(jù)項5目前二頁\總數(shù)八十四頁\編于十六點查找表的操作:

生成查找表

查找元素(記錄)x在是否在表ST中

查找元素(記錄)x的屬性

插入新元素(記錄)x

刪除元素(記錄)x......目前三頁\總數(shù)八十四頁\編于十六點查找----根據(jù)給定的某個關(guān)鍵字值，在查找表中確定一個其關(guān)鍵字等于給定值的記錄或數(shù)據(jù)元素。

設k為給定的一個關(guān)鍵字值，R[1..n]為n個記錄的表,若存在R[i].key=k,1≤i≤n,稱查找成功；否則稱查找失敗。靜態(tài)查找:查詢某個特定的元素，檢查某個特定的數(shù)據(jù)元素的屬性,不插入新元素或刪除元素(記錄)

。動態(tài)查找:在查找過程中，同時插入查找表中不存在的數(shù)據(jù)元素(記錄)。目前四頁\總數(shù)八十四頁\編于十六點查找表的類型及其查找方法(1)靜態(tài)查找表

●

順序表，用順序查找法

●

線性鏈表，用順序查找法●有序的順序表，用：折半查找法；**斐班那契查找法；插值查找法；●

索引順序表/分塊表，用分塊查找法。(2)動態(tài)查找表

●

二叉排序樹,平衡二叉樹(AVL樹）**●

B樹,B+樹,

鍵樹(3)哈希(Hash)表目前五頁\總數(shù)八十四頁\編于十六點平均查找長度----查找一個記錄時比較關(guān)鍵字次數(shù)的平均值。

n

ASL=∑PiCii=1Pi---查找r[i]的概率Ci---查找r[i]所需比較關(guān)鍵字的次數(shù)目前六頁\總數(shù)八十四頁\編于十六點2041劉大海...2042王偉...2046吳曉英..............................0123maxsizeelemkeyname...監(jiān)視哨9.1靜態(tài)查找表9.1.1順序表與順序查找法1.順序表的描述

length目前七頁\總數(shù)八十四頁\編于十六點例1元素類型為記錄(結(jié)構(gòu))#definemaxsize100//表長100

typedefstructnode{keytypekey；//關(guān)鍵字類型charname[6]；//姓名......//其它}ElemType；

typedefstruct

{ElemTypeelem[maxsize+1]；//maxsize+1個記錄,//elem[0]為監(jiān)視哨

intlength;}SSTable;SSTableST1,ST2;目前八頁\總數(shù)八十四頁\編于十六點

121030202515//////60123456maxsizelength監(jiān)視哨例2元素類型為整型#definemaxsize100//表長100typedefintElemType；typedefstruct

{ElemTypeelem[maxsize+1]；//maxsize+1個記錄,//elem[0]為監(jiān)視哨

intlength;}SSTable;SSTableST1,ST2;目前九頁\總數(shù)八十四頁\編于十六點2.順序查找法(sequentialsearch)算法設計算法1：假定不使用監(jiān)視哨elem[0]基本思想：將關(guān)鍵字k依次與記錄的關(guān)鍵字:elem[n].key,elem[n-1].key，...,elem[1].key比較。

如果找到一個記錄elem[i],有:elem[i].key＝k(1≤i≤n)，則查找成功，停止比較,返回記錄的下標i；否則,查找失敗,返回0。目前十頁\總數(shù)八十四頁\編于十六點輸入：查找表ST，查找條件（關(guān)鍵字）k輸出：成功時：記錄序號，失敗時：0intsequsearch(SSTableST,keytypek){inti=ST.length；//從第n個記錄開始查找

while(i>=1&&k!=ST.elem[i].key)i--；//繼續(xù)掃描

if(i)printf(”success\n”)；//查找成功

elseprintf(”fail\n”)；//查找失敗returni；//返回記錄的下標i}目前十一頁\總數(shù)八十四頁\編于十六點算法2：假定使用監(jiān)視哨elem[0]基本思想：先將關(guān)鍵字k存入elem[0].key,再將k依次與elem[n].key,...,elem[1].key,elem[0].key進行比較。如果找到一個記錄,有：k=elem[i].key,(0≤i≤n)，則停止比較。如果i>0,則查找成功；否則,查找失敗。目前十二頁\總數(shù)八十四頁\編于十六點輸入：查找表ST，查找條件（關(guān)鍵字）k輸出：成功時：記錄序號，失敗時：0intsequsearch(SSTableST,keytypek){inti=ST.length；//從第n個記錄開始查找ST.elem[0].key=k；//k填入ST.elem[0].key

while(k!=ST.elem[i].key)i--；//繼續(xù)掃描returni；//返回記錄的下標i}目前十三頁\總數(shù)八十四頁\編于十六點3查找算法性能分析：對n個記錄的表,所需比較關(guān)鍵字的次數(shù)

●只考慮查找成功:最少為1,最多為n假定每個記錄的查找概率相等，即P1=

P2=...

=

Pn=1/nASL====(n+1)/2

目前十四頁\總數(shù)八十四頁\編于十六點●考慮查找失敗:使用監(jiān)視哨elem[0],為n+1

不使用監(jiān)視哨elem[0],為

n假定查找成功和失敗的機會相同，對每個記錄的查找概率相等，Pi=1/(2*n),則

1nn+1n+1n+1

ASL=--∑Ci+---=---+---=3(n+1)/42ni=1242目前十五頁\總數(shù)八十四頁\編于十六點9.1.2有序的順序表的查找與折半查找法1.有序表elem[1].key≤elem[2].key≤...≤elem[n].key2.折半查找(binarysearch,對半查找，二分查找)

假定k=1051012182025304012345678↑↑↑lowmidhiglow=1,hig=8mid=(low+hig)/2=451012182025304012345678↑↑↑lowmidhig

low=1,hig=3mid=(low+hig)/2=2目前十六頁\總數(shù)八十四頁\編于十六點

假定k=4051012182025304012345678↑↑↑lowmidhiglow=1,hig=8mid=(low+hig)/2=451012182025304012345678↑↑↑lowmidhiglow=5,hig=8mid=(low+hig)/2=6目前十七頁\總數(shù)八十四頁\編于十六點51012182025304012345678↑↑lowmidhig

low=7,hig=8mid=(low+hig)/2=7↑

假定k=40（續(xù)）51012182025304012345678

lowmidhig

low=8,hig=8mid=(low+hig)/2=8↑↑↑目前十八頁\總數(shù)八十四頁\編于十六點51012182025304012345678↑↑↑lowmidhig

low=1,hig=8mid=(low+hig)/2=451012182025304012345678

↑↑↑lowmidhig

low=5,hig=8mid=(low+hig)/2=6假定k=2251012182025304012345678

lowmidhig

low=5,hig=5mid=(low+hig)/2=5↑↑↑目前十九頁\總數(shù)八十四頁\編于十六點

假定k=22（續(xù)）51012182025304012345678

midhiglow

mid=5low=6,hig=5↑↑↑51012182025304012345678

midhiglow

mid=5low=6,hig=5↑↑↑hig<low,查找失敗目前二十頁\總數(shù)八十四頁\編于十六點3折半查找算法1intbinsrch(SSTableST,keytypek){intlow,mid,hig；low=1；hig=ST.length；while(low<=hig){mid=(low+hig)/2；//計算中間記錄的地址if(k<ST.elem[mid].key)hig=mid-1；//查左子表

elseif(k==ST.elem[mid].key)break；//查找成功,退出循環(huán)

elselow=mid+1；//查右子表｝目前二十一頁\總數(shù)八十四頁\編于十六點if(ST.elem[mid].key==k){printf("success\n”)；//查找成功returnmid；}else{printf("fail\n”)；//查找失敗return0；}}目前二十二頁\總數(shù)八十四頁\編于十六點折半查找算法2intbinsrch(SSTableST,keytypek){intlow,mid,hig；low=1；hig=ST.length；while(low<=high){mid=(low+high)/2；if(k<ST.elem[mid].key)hig=mid-1；//查左子表

elseif(k==ST.elem[mid].key)returnmid；//查找成功，返回midelselow=mid+1；//查右子表｝return0；//查找失敗，返回0}目前二十三頁\總數(shù)八十四頁\編于十六點4.判定樹（描述折半查找過程的二叉樹）639147112101258n=12,非滿二叉樹784625311512141013119n=15,滿二叉樹結(jié)點內(nèi)的數(shù)據(jù)表示數(shù)據(jù)元素的序號（如例中表示有15個元素組成的有序表的判定樹）根結(jié)點表示首先要和關(guān)鍵字k進行比較的數(shù)據(jù)元素的序號（如8），比較相等時，查找成功，否則，當k小于根結(jié)點對應元素的關(guān)鍵字時，下步就和左子結(jié)點（如序號4）對應元素的關(guān)鍵字比較，否則，下步就和右子結(jié)點（如序號12）對應元素的關(guān)鍵字比較。目前二十四頁\總數(shù)八十四頁\編于十六點●若n=2k-1,則判定樹為滿二叉樹,其深度為k=log2(n+1)假定Pi=1/n(i=1,2,...,n),比較關(guān)鍵字的次數(shù)：

●最少Cmin=1

●最多Cmax=log2(n+1)

n+1

●ASL=----log2(n+1)-1n15+116設n=15ASL=------log2(15+1)-1=----*4-1≈3.31515目前二十五頁\總數(shù)八十四頁\編于十六點n=11，加外部結(jié)點的判定樹63914710211585-64-53-42-31-27-88-910-116-79-10-111-對任意的nn+1

ASL≈----log2(n+1)-1=O(log2n)n1+2+2+3+3+3+3+4+4+4+4+437設n=12,ASL=-----------------------=--≈3.11212639147112101258n=12，判定樹目前二十六頁\總數(shù)八十四頁\編于十六點9.1.3索引順序表(分塊表)與分塊查找法20...15...30...10...35...33...40...45...50...60...58...52.........key其它數(shù)據(jù)..首地址最大key123456789101112131234分塊表索引表k=40k=55k=38第一塊第二塊第三塊第四塊目前二十七頁\總數(shù)八十四頁\編于十六點●

條件(1)分塊表"按塊有序",索引表"按key有序"(2)設n個記錄分為b個塊，每塊的記錄數(shù)s=n/b●

查找方法與ASL(1)順序查找(或折半查找)索引表確定k值所在的塊號或塊的首地址

b+1

ASL(1)=Lb=---2(2)在某一塊中順序查找

s+1

ASL(2)=Lw=---2

b+1s+111n●ASL=Lb+Lw=---+---=--(b+s)+1=--(--+s)+12222s●最佳分塊s=√nb=√n

ASLmin=√n+1=O(√n)目前二十八頁\總數(shù)八十四頁\編于十六點9.2動態(tài)查找表1.二叉排序樹(二叉查找樹）(1)二叉排序樹的定義如果二叉樹的任一結(jié)點大于其非空左子樹的所有結(jié)點，而小于其非空右子樹的所有結(jié)點，則這棵二叉樹稱為二叉排序樹。對一棵二叉排序樹進行中序遍歷，所得的結(jié)點序列一定是遞增有序的。8514103585401080353LDR：5,8,10,14,35LDR：3,5,8,10,35,40,80目前二十九頁\總數(shù)八十四頁\編于十六點下列二叉樹是否為二叉排序樹？30111815196410556026803010281522T1T230T3目前三十頁\總數(shù)八十四頁\編于十六點（2）二叉排序樹的生成

設輸入序列為：30,11,18,4,55,19,15,70,58303011183011184193011301118419301118455193011184551570193011184551570583011184555515插入30插入11插入18插入4插入55插入19插入15插入70插入58目前三十一頁\總數(shù)八十四頁\編于十六點課堂練習：

設輸入關(guān)鍵字序列為:58,60,15,80,19,55,4,18,70,11,30,生成二叉排序樹,試畫出二叉排序樹；假定查找每個結(jié)點(關(guān)鍵字)的概率相同，計算查找成功時的平均查找長度ASL。5558151946018807011301+2+2+3+3+3+4+4+4+4+535ASL=---------------------=--≈3.181111目前三十二頁\總數(shù)八十四頁\編于十六點(3)二叉排序樹的存儲結(jié)構(gòu)lchilddatarchildkey.....左子樹右子樹結(jié)點類型定義：structnode{struct{intkey；//關(guān)鍵字.....//其它數(shù)據(jù)項}data；structnode*lchild,*rchild；//左右子樹的指針}*root,*t；結(jié)點形式：目前三十三頁\總數(shù)八十四頁\編于十六點(4)插入1個元素到二叉排序樹的算法structnode*intree(structnode*t,ElemTypex){if(t==NULL)//t是指向二叉樹根的指針{t=(structnode*)malloc(sizeof(structnode))；t->data=x；//生成并插入結(jié)點xt->lchild=t->rchild=NULL；//為葉子結(jié)點}elseif(x.key<t->data.key)t->lchild=intree(t->lchild,x)；//插入左子樹elset->rchild=intree(t->rchild,x)；//插入右子樹returnt;}目前三十四頁\總數(shù)八十四頁\編于十六點(5)二叉排序樹的查找算法(返回值失?。篘ULL成功：非NULL，結(jié)點指針）a)遞歸算法

structnode*search_tr(structnode*t,keytypek){if(t==NULL)returnNULL；//查找失敗elseif(k==t->data.key)returnt；//查找成功elseif(k<t->data.key)returnsearch_tr(t->lchild,k)；//查左子樹

elsereturnsearch_tr(t->rchild,k)；//查右子樹}目前三十五頁\總數(shù)八十四頁\編于十六點b)非遞歸算法structnode*search_tree(structnode*t,keytypek){while(t!=NULL)if(k==t->data.key)returnt；//查找成功elseif(k<t->data.key)t=t->lchild；//查左子樹elset=t->rchild；//查右子樹returnt；//查找失敗}目前三十六頁\總數(shù)八十四頁\編于十六點(6)二叉排序樹的刪除在二叉排序樹中刪除一個結(jié)點時，必須將因刪除結(jié)點而斷開的二叉鏈表重新鏈接起來，同時確保二叉排序樹的性質(zhì)不會失去。為保證在刪除節(jié)點后二叉排序樹的性質(zhì)不會丟失:刪除葉結(jié)點，只需將其雙親結(jié)點指向它的指針置空，再釋放它即可。被刪結(jié)點缺左子樹（或右子樹），可以用被刪節(jié)點的右子樹（或左子樹）頂替它的位置，再釋放它。目前三十七頁\總數(shù)八十四頁\編于十六點被刪結(jié)點左、右子樹都存在，可以在它的右子樹中尋找中序下的第一個結(jié)點(關(guān)鍵值最小),用它的值填補到被刪結(jié)點中，再來處理這個結(jié)點的刪除問題。5378651787092345刪除45缺右子樹,用左子樹頂替53786517870923目前三十八頁\總數(shù)八十四頁\編于十六點8853788817940923刪除78缺左子樹,用右子樹頂替53948817092353788117940945刪除78在右子樹上找中序下第一個結(jié)點填補2365538188179409452365目前三十九頁\總數(shù)八十四頁\編于十六點(7)查找性能分析

最好情況(為滿二叉樹）n+1ASL=---log2(n+1)-1=O(log2n)n

最壞情況(為單枝樹):ASL=(1+2+...+n)/n=(n+1)/2平均值:

ASL≈O(log2n)5828493045581519101811488697964756560滿二叉樹單枝樹ASL=(15+1)/15*log2(15+1)-1≈3.3ASL=(1+2+3+4)/4=2.5目前四十頁\總數(shù)八十四頁\編于十六點2.平衡二叉樹(高度平衡二叉樹）

AVL樹：由和提出。結(jié)點的平衡因子：結(jié)點的左右子樹的深度之差。平衡二叉樹：任意結(jié)點的平衡因子的絕對值小于等于1的二叉樹。T1T2T3T4T50102-1000-112100-2（1）AVL樹的定義目前四十一頁\總數(shù)八十四頁\編于十六點（2）AVL樹的存儲結(jié)構(gòu)：typedefintDataType;//結(jié)點數(shù)據(jù)類型typedefstructnode{//AVL樹結(jié)點定義

DataTypedata;//結(jié)點數(shù)據(jù)域

intbalance;//結(jié)點平衡因子域

structnode*leftChild,*rightChild;//結(jié)點左、右子樹指針域}AVLNode;typedefAVLNode*AVLTree;//AVL樹目前四十二頁\總數(shù)八十四頁\編于十六點如果在一棵平衡的二叉搜索樹中插入一個新結(jié)點，造成了不平衡。此時必須調(diào)整樹的結(jié)構(gòu)，使之平衡化。平衡化旋轉(zhuǎn)有兩類：單旋轉(zhuǎn)(左旋和右旋)

雙旋轉(zhuǎn)(左平衡和右平衡)每插入一個新結(jié)點時,AVL樹中相關(guān)結(jié)點的平衡狀態(tài)會發(fā)生改變。因此,在插入一個新結(jié)點后，需要從插入位置沿通向根的路徑回溯，檢查各結(jié)點的平衡因子。（3）平衡化旋轉(zhuǎn)目前四十三頁\總數(shù)八十四頁\編于十六點如果在某一結(jié)點發(fā)現(xiàn)高度不平衡，停止回溯。從發(fā)生不平衡的結(jié)點起，沿剛才回溯的路徑取直接下兩層的結(jié)點。如果這三個結(jié)點處于一條直線上，則采用單旋轉(zhuǎn)進行平衡化。單旋轉(zhuǎn)可按其方向分為左單旋轉(zhuǎn)和右單旋轉(zhuǎn),其中一個是另一個的鏡像，其方向與不平衡的形狀相關(guān)。如果這三個結(jié)點處于一條折線上，則采用雙旋轉(zhuǎn)進行平衡化。雙旋轉(zhuǎn)分為先左后右和先右后左兩類。目前四十四頁\總數(shù)八十四頁\編于十六點右單旋轉(zhuǎn)左單旋轉(zhuǎn)左右雙旋轉(zhuǎn)右左雙旋轉(zhuǎn)目前四十五頁\總數(shù)八十四頁\編于十六點在子樹E中插入新結(jié)點，該子樹高度增1導致結(jié)點A的平衡因子變成-2，出現(xiàn)不平衡。沿插入路徑檢查三個結(jié)點A、C和E。它們處于方向為“\”的直線上，需做左單旋轉(zhuǎn)。以結(jié)點C為旋轉(zhuǎn)軸，讓結(jié)點A逆時針旋轉(zhuǎn)。（a）左單旋轉(zhuǎn)(RotateLeft)hhhACEBDhhh+1BACEDhhh+1CEABD-1-20-100目前四十六頁\總數(shù)八十四頁\編于十六點在子樹D中插入新結(jié)點，該子樹高度增1導致結(jié)點A的平衡因子變成+2，出現(xiàn)不平衡。沿插入路徑檢查三個結(jié)點A、B和D。它們處于方向為“/”的直線上，需做右單旋轉(zhuǎn)。以結(jié)點B為旋轉(zhuǎn)軸，讓結(jié)點A順時針旋轉(zhuǎn)。（b）右單旋轉(zhuǎn)(RotateRight)hhhACEBDhh+1BACEDhhh+1CEABDh000+1+1+2目前四十七頁\總數(shù)八十四頁\編于十六點在子樹F或G中插入新結(jié)點，該子樹的高度增1。結(jié)點A的平衡因子變?yōu)?2，發(fā)生了不平衡。（c）先左后右雙旋轉(zhuǎn)(RotationLeftRight)插入00+1+2-1+1hhACEDh-1hhAhBCEDB左單旋轉(zhuǎn)FGFGh-1h-1目前四十八頁\總數(shù)八十四頁\編于十六點插入00+1+2-1+1hhACEDh-1hhAhBCEDB左單旋轉(zhuǎn)FGFG從結(jié)點A起沿插入路徑選取3個結(jié)點A、B和E，它們位于一條形如“”的折線上，因此需要進行先左后右的雙旋轉(zhuǎn)。以結(jié)點E為旋轉(zhuǎn)軸，將結(jié)點B逆時針旋轉(zhuǎn)。h-1h-1目前四十九頁\總數(shù)八十四頁\編于十六點00+200-1hhACED+2hhhAhBCEDB右單旋轉(zhuǎn)FGFGh-1h-1再以結(jié)點E為旋轉(zhuǎn)軸，將結(jié)點A順時針旋轉(zhuǎn)。目前五十頁\總數(shù)八十四頁\編于十六點右左雙旋轉(zhuǎn)是左右雙旋轉(zhuǎn)的鏡像在子樹F或G中插入新結(jié)點，該子樹高度增1，A的平衡因子變?yōu)?2，發(fā)生了不平衡。（d）先右后左雙旋轉(zhuǎn)(RotationRightLeft)插入右單旋轉(zhuǎn)-1000+10hhACEDBFG-2000hhACEhBFGDh-1h-1h-1目前五十一頁\總數(shù)八十四頁\編于十六點從結(jié)點A起沿插入路徑選取3個結(jié)點A、C和D，它們位于一條形如“”的折線上，因此需要進行先右后左的雙旋轉(zhuǎn)。以結(jié)點D為旋轉(zhuǎn)軸，將結(jié)點C順時針旋轉(zhuǎn)。插入右單旋轉(zhuǎn)-1000+10hhACEDBFG-2000hhACEhBFGDh-1h-1h-1目前五十二頁\總數(shù)八十四頁\編于十六點再以結(jié)點D為旋轉(zhuǎn)軸，將結(jié)點A逆時針旋轉(zhuǎn)。00-20+10hhACE-2hhhAhBCEDB左單旋轉(zhuǎn)FGFGDh-1h-1目前五十三頁\總數(shù)八十四頁\編于十六點在向一棵本來是高度平衡的AVL樹中插入一個新結(jié)點時，如果樹中某個結(jié)點的平衡因子的絕對值|balance|>1，則出現(xiàn)了不平衡，需要做平衡化處理。算法從一棵空樹開始，通過輸入一系列對象關(guān)鍵碼，逐步建立AVL樹。在插入新結(jié)點時使用平衡旋轉(zhuǎn)方法進行平衡化處理。（3）AVL樹的插入目前五十四頁\總數(shù)八十四頁\編于十六點1616例，輸入關(guān)鍵碼序列為{16,3,7,11,9,26,18,14,15}，插入和調(diào)整過程如下。03163+1070-1+2左右雙旋731600073110+11+2右單旋37169000-1371126916110-1-1-2-2目前五十五頁\總數(shù)八十四頁\編于十六點181803163+10160-2右左雙旋739000182611+1732616119+1左單旋97161400-171126269-1-111目前五十六頁\總數(shù)八十四頁\編于十六點1518-231816+2左右雙旋73000117149+116150-111262614-1+29從空樹開始的建樹過程目前五十七頁\總數(shù)八十四頁\編于十六點平衡二叉樹、二叉排序樹、平衡二叉排序樹的區(qū)別：4850351020414560平衡二叉排序樹6870651020414580平衡二叉樹68807510414585二叉排序樹-2-1-101-1-11-110000000000000目前五十八頁\總數(shù)八十四頁\編于十六點靜態(tài)和動態(tài)查找表查找方法靜態(tài)查找表和動態(tài)查找表通過比較關(guān)鍵字進行查找：（1）順序表，對數(shù)據(jù)元素的存儲一般有兩種形式：(a)是按到來次序連續(xù)存放，查找時順序比較查找；(b)按關(guān)鍵字的相對關(guān)系整理后以遞增或遞減形式連續(xù)存放，則查找時使用順序法或二分法比較查找。（2）二叉排序樹，從根開始進行比較查找。不足：查找時無法根據(jù)關(guān)鍵字的值估計數(shù)據(jù)元素可能在的位置。目前五十九頁\總數(shù)八十四頁\編于十六點9.3哈希(Hash)表和哈希法存儲數(shù)據(jù)元素時，利用一個Hash函數(shù)根據(jù)數(shù)據(jù)元素的關(guān)鍵字計算出該數(shù)據(jù)元素的存儲位置，查找時，也是根據(jù)給定的數(shù)據(jù)元素的關(guān)鍵字計算出該數(shù)據(jù)元素可能存儲位置，這樣一來，存儲和查找的效率相當高，哈希表也稱為散列表，其數(shù)據(jù)元素的存儲一般是不連續(xù)的。通過Hash函數(shù)計算出的地址稱為哈希地址或散列地址。目前六十頁\總數(shù)八十四頁\編于十六點9.3.1哈希表相關(guān)術(shù)語

Hash函數(shù)實現(xiàn)的是將一組關(guān)鍵字映象到一個有限的地址區(qū)間上，理想的情況是不同的關(guān)鍵字得到不同的地址。設K1和K2為關(guān)鍵字,若K1≠K2,H(K1)=H(K2),則稱K1,K2為同義詞,K2與K1發(fā)生了沖突例設H(k)=k%17k1=5k2=22∵H(5)=5%17=5H(22)=22%17=5

H(5)=H(22)=5

∴5和22是同義詞,5和22發(fā)生沖突目前六十一頁\總數(shù)八十四頁\編于十六點9.3.1哈希表相關(guān)術(shù)語采用哈希表進行存儲和查找需要著重考慮兩個問題：（a）選擇一個好的哈希（散列）函數(shù)；（b）選擇一種解決沖突（碰撞）的方法。目前六十二頁\總數(shù)八十四頁\編于十六點例1人口統(tǒng)計表110.5212.6311.0420.8......150...序號(地址)年齡人數(shù)(萬)

1234150H(key)=key=地址H(年齡）=年齡

key9.3.2構(gòu)造哈希函數(shù)的方法

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

H(key)=keyH(key)=a.key+b目前六十三頁\總數(shù)八十四頁\編于十六點例2學生成績表200041劉大海

男8075200042王偉

男9083200043吳曉英

女8288200044王偉女8090....................................1234nkey序號(地址)學號姓名性別數(shù)學外語H(key)=key-200040=地址H(學號)=學號-200040

目前六十四頁\總數(shù)八十四頁\編于十六點例3標識符表ABCCADDAT

FOXYABZOO1234562526序號標識符(key)H(key)=key的第一個字母在字母表中的序號key=ABCCADDATFOXYABZOOH(key)=13462526目前六十五頁\總數(shù)八十四頁\編于十六點2.除留余數(shù)法設哈希表HT[0..m-1]的表長為m，哈希地址為key除以p所的的余數(shù)：

H(key)=keyMODp//PASCAL語言

H(key)=key%p//C語言其中：MOD,%為“取?！被颉扒笥唷?/p>

p<=m，p為接近m的質(zhì)數(shù)(素數(shù)),如：3,5,7,11,13,17,19,23,29,31,37......

或不包含小于20的質(zhì)因子的合數(shù)，如：713(=23*31)目前六十六頁\總數(shù)八十四頁\編于十六點例1設m=130,取p=127,

H(key)=key%127

012.....129例2設m=256取p=251

H(key)=key%251012.....255目前六十七頁\總數(shù)八十四頁\編于十六點例設哈希表的地址范圍為0～20,哈希函數(shù)為H(K)=K%19輸入關(guān)鍵字序列：39,22,21,37,36,38,19,解決沖突的方法為線性探測再散列(哈希),構(gòu)造哈希表HT[0..20]。

關(guān)鍵字KH(K)=K%193939%19=12222%19=32121%19=23737%19=183636%19=173838%19=01919%19=019與38沖突,再與39,21,22沖突,存入HT[4]012345

17181920HT[0..20]39222137383619目前六十八頁\總數(shù)八十四頁\編于十六點38392122195536371756再輸入17,56,5517%19=1717與36沖突,再與37沖突,存入HT[19]。56%19=1856與37沖突,再與17沖突,存入HT[20]。55%19=1755與36沖突,再與37,17,56沖突,再與38,39,21,22,19沖突,存入HT[5]。對于H(k)=k%19，所有的19a+b為同義詞,0<b<19如：5,24,43,62,81,.....01234517181920HT[0..20]key目前六十九頁\總數(shù)八十四頁\編于十六點3.平方取中法----取關(guān)鍵字平方后的中間某幾位為哈希地址,即：

H(k)=取k2的中間某幾位數(shù)字例.設哈希表為HT[0..99],哈希函數(shù)為：H(K)=取k2的中間2位數(shù),輸入關(guān)鍵字序列：39,21,6,36,38,13,用線性探測再散列法解決沖突,構(gòu)造HT[0..99]。Kk2

H(K)39152152210441446003603361296293814444413016916613362138390

3

162944455299key目前七十頁\總數(shù)八十四頁\編于十六點4.折疊法將關(guān)鍵字分割成位數(shù)相同的幾部分,然后取這幾部分的疊加和作為哈希地址。(1)邊界折疊法

設表地址范圍為0～999●

k1=056439527650+439+

725=1814

H(k1)=814●k2=123486790321+486+097=907

H(k2)=907●

k3=300600007003+600+700=1303

H(k2)=30330060000705643952712348679001

303814907999HT[0..999]目前七十一頁\總數(shù)八十四頁\編于十六點4.折疊法將關(guān)鍵字分割成位數(shù)相同的幾部分,然后取這幾部分的疊加和作為哈希地址。(2)移位折疊法(移位法)

設表地址范圍為0～999●

k1=056439527056+439+

527=1022

H(k1)=022●k2=123486790123+486+790=1399

H(k2)=399●

k3=300600007300+600+007=907

H(k2)=90705643952712348679030060000701

22399907999HT[0..999]目前七十二頁\總數(shù)八十四頁\編于十六點5.數(shù)字分析法設哈希表中可能出現(xiàn)的關(guān)鍵字都是事先知道的,則可取關(guān)鍵字的若干分布均勻的位組成哈希地址。kH(k)902006720690443134319013456145904432643290532435249061791679901345690200679044313904432690532439061791145206431432524679HT[0..999]目前七十三頁\總數(shù)八十四頁\編于十六點6.隨機數(shù)法

H(key)=random(key)random(key)為產(chǎn)生偽隨機數(shù)的函數(shù)7.靈活構(gòu)造哈希函數(shù)例.設哈希表為HT[0..40],哈希函數(shù)為：

H(K)=取k2的中間2位數(shù)*40/99其中40/99將其00～99壓縮到00～40之內(nèi)，輸入關(guān)鍵字序列：39,21,6,36,38,13,用線性探測再散列法解決沖突。Kk2

H(K)39152152*40/99=2121044144*40/99=176003603*40/99=177592992*40/99=3738144444*40/99=1713016916*40/99=66

132138

3977

013

61718213740key目前七十四頁\總數(shù)八十四頁\編于十六點9.3.3如何解決沖突1.開放地址法(開式尋址法)假定記錄Ri,RX的關(guān)鍵字Ki,KX為同義詞，散列地址為q,Ri已存入HT[0..m-1]中的HT[q]中，則RX存入HT中的某個空位上。依次在地址:

q+1,q+2,...,m-1,0,1,...,q-1

中尋找一個空位，叫做線性探測再散列。

(1)線性探測再散列Ki...HT[0..m-1]01

q-1qq+1m-1RiRX目前七十五頁\總數(shù)八十四頁\編于十六點課堂練習：設H(k)=k的首字母在字母表中的序號,用線性探測再散列法解決沖突，依次用下列關(guān)鍵字，構(gòu)造哈希表HT[0..28]。kH(k)

A1DEC4ZMN26DAB4ZE26ANT1YY25ZOO26CAD3YES25ZY26LL12DE401234567

121325262728HT[0..28]

12345678910111213目前七十六頁\總數(shù)八十四頁\編于十六點例設H(k)=k的首字母在字母表中的序號，用線性探測再散列法解決沖突，依次用下列關(guān)鍵字，構(gòu)造哈希表HT[0..28]。YESAANTCADDECDABZYDELLYYZMNZEZ00kH(k)

1A12DEC43ZMN264DAB45ZE266ANT17YY258ZOO269CAD310YES2511ZY2612LL1213DE401234567

1225262728HT[0..28]目前七十七頁\總數(shù)八十四頁\編于十六點(2)二次探測再散列

假定記錄Ri和Rj的關(guān)鍵字Ki和Kj為同義詞，散列地址為q,Ri已存入HT[0..m-1]中的HT[q]中。若依次在地址q+12,q-12,q+22,q-22,...,q+i2,q-i2,...中尋找一個空位，叫做二次探測再散列。例:

設記錄X和A為同義詞，散列地址為50,二次探測再散列的地址序列為：51,49,54,46,59,41,66,34,75,......HT[0..99]GECABDF03441464950515459667599XXXXXXXXGECABDFX03441464950515459667599目前七十八頁\總數(shù)八十四頁\編于十六點2.鏈地址法將關(guān)鍵字為同義詞的所有記錄存入同一鏈表中。（表頭插入）例設H(k)=k的首字母在字母表中的序號,用下列關(guān)鍵字造哈希表HT[1..26]kH(k)

A1DEC4ZMN26DAB4ZE26ANT1YY25ZOO26CAD3YES25ZY26LL12DE4

12345678910111213∧∧∧∧HT[1..26]ZEZOOZYZMN∧DEYESYY∧CAD∧ANTA∧DABDEC∧LL∧1234122526目前七十九頁\總數(shù)八十四頁\編于十六點