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

（優(yōu)選）數(shù)據(jù)結(jié)構(gòu)第九章查找現(xiàn)在是1頁\一共有84頁\編輯于星期五第九章查找

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

男8075200042王偉

男9083200046吳曉英

女8288200048王偉女8090.....................序號(hào)1234n●關(guān)鍵字:可以標(biāo)識(shí)一個(gè)記錄的數(shù)據(jù)項(xiàng)●

主關(guān)鍵字:可以唯一地標(biāo)識(shí)一個(gè)記錄的數(shù)據(jù)項(xiàng)●

次關(guān)鍵字:可以識(shí)別若干記錄的數(shù)據(jù)項(xiàng)學(xué)生成績(jī)表數(shù)據(jù)項(xiàng)1(主關(guān)鍵字)數(shù)據(jù)項(xiàng)2數(shù)據(jù)項(xiàng)5現(xiàn)在是2頁\一共有84頁\編輯于星期五查找表的操作:

生成查找表

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

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

插入新元素(記錄)x

刪除元素(記錄)x......現(xiàn)在是3頁\一共有84頁\編輯于星期五查找----根據(jù)給定的某個(gè)關(guān)鍵字值，在查找表中確定一個(gè)其關(guān)鍵字等于給定值的記錄或數(shù)據(jù)元素。

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

。動(dòng)態(tài)查找:在查找過程中，同時(shí)插入查找表中不存在的數(shù)據(jù)元素(記錄)?，F(xiàn)在是4頁\一共有84頁\編輯于星期五查找表的類型及其查找方法(1)靜態(tài)查找表

●

順序表，用順序查找法

●

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

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

●

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

B樹,B+樹,

鍵樹(3)哈希(Hash)表現(xiàn)在是5頁\一共有84頁\編輯于星期五平均查找長(zhǎng)度----查找一個(gè)記錄時(shí)比較關(guān)鍵字次數(shù)的平均值。

n

ASL=∑PiCii=1Pi---查找r[i]的概率Ci---查找r[i]所需比較關(guān)鍵字的次數(shù)現(xiàn)在是6頁\一共有84頁\編輯于星期五2041劉大海...2042王偉...2046吳曉英..............................0123maxsizeelemkeyname...監(jiān)視哨9.1靜態(tài)查找表9.1.1順序表與順序查找法1.順序表的描述

length現(xiàn)在是7頁\一共有84頁\編輯于星期五例1元素類型為記錄(結(jié)構(gòu))#definemaxsize100//表長(zhǎng)100

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

typedefstruct

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

intlength;}SSTable;SSTableST1,ST2;現(xiàn)在是8頁\一共有84頁\編輯于星期五

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

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

intlength;}SSTable;SSTableST1,ST2;現(xiàn)在是9頁\一共有84頁\編輯于星期五2.順序查找法(sequentialsearch)算法設(shè)計(jì)算法1：假定不使用監(jiān)視哨elem[0]基本思想：將關(guān)鍵字k依次與記錄的關(guān)鍵字:elem[n].key,elem[n-1].key，...,elem[1].key比較。

如果找到一個(gè)記錄elem[i],有:elem[i].key＝k(1≤i≤n)，則查找成功，停止比較,返回記錄的下標(biāo)i；否則,查找失敗,返回0?，F(xiàn)在是10頁\一共有84頁\編輯于星期五輸入：查找表ST，查找條件（關(guān)鍵字）k輸出：成功時(shí)：記錄序號(hào)，失敗時(shí)：0intsequsearch(SSTableST,keytypek){inti=ST.length；//從第n個(gè)記錄開始查找

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

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

elseprintf(”fail\n”)；//查找失敗returni；//返回記錄的下標(biāo)i}現(xiàn)在是11頁\一共有84頁\編輯于星期五算法2：假定使用監(jiān)視哨elem[0]基本思想：先將關(guān)鍵字k存入elem[0].key,再將k依次與elem[n].key,...,elem[1].key,elem[0].key進(jìn)行比較。如果找到一個(gè)記錄,有：k=elem[i].key,(0≤i≤n)，則停止比較。如果i>0,則查找成功；否則,查找失敗?，F(xiàn)在是12頁\一共有84頁\編輯于星期五輸入：查找表ST，查找條件（關(guān)鍵字）k輸出：成功時(shí)：記錄序號(hào)，失敗時(shí)：0intsequsearch(SSTableST,keytypek){inti=ST.length；//從第n個(gè)記錄開始查找ST.elem[0].key=k；//k填入ST.elem[0].key

while(k!=ST.elem[i].key)i--；//繼續(xù)掃描returni；//返回記錄的下標(biāo)i}現(xiàn)在是13頁\一共有84頁\編輯于星期五3查找算法性能分析：對(duì)n個(gè)記錄的表,所需比較關(guān)鍵字的次數(shù)

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

P2=...

=

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

現(xiàn)在是14頁\一共有84頁\編輯于星期五●考慮查找失敗:使用監(jiān)視哨elem[0],為n+1

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

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

1nn+1n+1n+1

ASL=--∑Ci+---=---+---=3(n+1)/42ni=1242現(xiàn)在是15頁\一共有84頁\編輯于星期五9.1.2有序的順序表的查找與折半查找法1.有序表elem[1].key≤elem[2].key≤...≤elem[n].key2.折半查找(binarysearch,對(duì)半查找，二分查找)

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

low=1,hig=3mid=(low+hig)/2=2現(xiàn)在是16頁\一共有84頁\編輯于星期五

假定k=4051012182025304012345678↑↑↑lowmidhiglow=1,hig=8mid=(low+hig)/2=451012182025304012345678↑↑↑lowmidhiglow=5,hig=8mid=(low+hig)/2=6現(xiàn)在是17頁\一共有84頁\編輯于星期五51012182025304012345678↑↑lowmidhig

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

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

lowmidhig

low=8,hig=8mid=(low+hig)/2=8↑↑↑現(xiàn)在是18頁\一共有84頁\編輯于星期五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↑↑↑現(xiàn)在是19頁\一共有84頁\編輯于星期五

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

midhiglow

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

midhiglow

mid=5low=6,hig=5↑↑↑hig<low,查找失敗現(xiàn)在是20頁\一共有84頁\編輯于星期五3折半查找算法1intbinsrch(SSTableST,keytypek){intlow,mid,hig；low=1；hig=ST.length；

while(low<=hig){mid=(low+hig)/2；//計(jì)算中間記錄的地址if(k<ST.elem[mid].key)hig=mid-1；//查左子表

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

elselow=mid+1；//查右子表｝現(xiàn)在是21頁\一共有84頁\編輯于星期五if(ST.elem[mid].key==k){printf("success\n”)；//查找成功returnmid；}else{printf("fail\n”)；//查找失敗return0；}}現(xiàn)在是22頁\一共有84頁\編輯于星期五折半查找算法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}現(xiàn)在是23頁\一共有84頁\編輯于星期五4.判定樹（描述折半查找過程的二叉樹）639147112101258n=12,非滿二叉樹784625311512141013119n=15,滿二叉樹結(jié)點(diǎn)內(nèi)的數(shù)據(jù)表示數(shù)據(jù)元素的序號(hào)（如例中表示有15個(gè)元素組成的有序表的判定樹）根結(jié)點(diǎn)表示首先要和關(guān)鍵字k進(jìn)行比較的數(shù)據(jù)元素的序號(hào)（如8），比較相等時(shí)，查找成功，否則，當(dāng)k小于根結(jié)點(diǎn)對(duì)應(yīng)元素的關(guān)鍵字時(shí)，下步就和左子結(jié)點(diǎn)（如序號(hào)4）對(duì)應(yīng)元素的關(guān)鍵字比較，否則，下步就和右子結(jié)點(diǎn)（如序號(hào)12）對(duì)應(yīng)元素的關(guān)鍵字比較?，F(xiàn)在是24頁\一共有84頁\編輯于星期五●若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設(shè)n=15ASL=------log2(15+1)-1=----*4-1≈3.31515現(xiàn)在是25頁\一共有84頁\編輯于星期五n=11，加外部結(jié)點(diǎn)的判定樹63914710211585-64-53-42-31-27-88-910-116-79-10-111-對(duì)任意的nn+1

ASL≈----log2(n+1)-1=O(log2n)n1+2+2+3+3+3+3+4+4+4+4+437設(shè)n=12,ASL=-----------------------=--≈3.11212639147112101258n=12，判定樹現(xiàn)在是26頁\一共有84頁\編輯于星期五9.1.3索引順序表(分塊表)與分塊查找法20...15...30...10...35...33...40...45...50...60...58...52.........key其它數(shù)據(jù)..首地址最大key123456789101112131234分塊表索引表k=40k=55k=38第一塊第二塊第三塊第四塊現(xiàn)在是27頁\一共有84頁\編輯于星期五●

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

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

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)現(xiàn)在是28頁\一共有84頁\編輯于星期五9.2動(dòng)態(tài)查找表1.二叉排序樹(二叉查找樹）(1)二叉排序樹的定義如果二叉樹的任一結(jié)點(diǎn)大于其非空左子樹的所有結(jié)點(diǎn)，而小于其非空右子樹的所有結(jié)點(diǎn)，則這棵二叉樹稱為二叉排序樹。對(duì)一棵二叉排序樹進(jìn)行中序遍歷，所得的結(jié)點(diǎn)序列一定是遞增有序的。8514103585401080353LDR：5,8,10,14,35LDR：3,5,8,10,35,40,80現(xiàn)在是29頁\一共有84頁\編輯于星期五下列二叉樹是否為二叉排序樹？30111815196410556026803010281522T1T230T3現(xiàn)在是30頁\一共有84頁\編輯于星期五（2）二叉排序樹的生成

設(shè)輸入序列為：30,11,18,4,55,19,15,70,58303011183011184193011301118419301118455193011184551570193011184551570583011184555515插入30插入11插入18插入4插入55插入19插入15插入70插入58現(xiàn)在是31頁\一共有84頁\編輯于星期五課堂練習(xí)：

設(shè)輸入關(guān)鍵字序列為:58,60,15,80,19,55,4,18,70,11,30,生成二叉排序樹,試畫出二叉排序樹；假定查找每個(gè)結(jié)點(diǎn)(關(guān)鍵字)的概率相同，計(jì)算查找成功時(shí)的平均查找長(zhǎng)度ASL。5558151946018807011301+2+2+3+3+3+4+4+4+4+535ASL=---------------------=--≈3.181111現(xiàn)在是32頁\一共有84頁\編輯于星期五(3)二叉排序樹的存儲(chǔ)結(jié)構(gòu)lchilddatarchildkey.....左子樹右子樹結(jié)點(diǎn)類型定義：structnode{struct{intkey；//關(guān)鍵字.....//其它數(shù)據(jù)項(xiàng)}data；structnode*lchild,*rchild；//左右子樹的指針}*root,*t；結(jié)點(diǎn)形式：現(xiàn)在是33頁\一共有84頁\編輯于星期五(4)插入1個(gè)元素到二叉排序樹的算法structnode*intree(structnode*t,ElemTypex){if(t==NULL)//t是指向二叉樹根的指針{t=(structnode*)malloc(sizeof(structnode))；t->data=x；//生成并插入結(jié)點(diǎn)xt->lchild=t->rchild=NULL；//為葉子結(jié)點(diǎn)}elseif(x.key<t->data.key)t->lchild=intree(t->lchild,x)；//插入左子樹elset->rchild=intree(t->rchild,x)；//插入右子樹returnt;}現(xiàn)在是34頁\一共有84頁\編輯于星期五(5)二叉排序樹的查找算法(返回值失敗：NULL成功：非NULL，結(jié)點(diǎn)指針）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)；//查右子樹}現(xiàn)在是35頁\一共有84頁\編輯于星期五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；//查找失敗}現(xiàn)在是36頁\一共有84頁\編輯于星期五(6)二叉排序樹的刪除在二叉排序樹中刪除一個(gè)結(jié)點(diǎn)時(shí)，必須將因刪除結(jié)點(diǎn)而斷開的二叉鏈表重新鏈接起來，同時(shí)確保二叉排序樹的性質(zhì)不會(huì)失去。為保證在刪除節(jié)點(diǎn)后二叉排序樹的性質(zhì)不會(huì)丟失:刪除葉結(jié)點(diǎn)，只需將其雙親結(jié)點(diǎn)指向它的指針置空，再釋放它即可。被刪結(jié)點(diǎn)缺左子樹（或右子樹），可以用被刪節(jié)點(diǎn)的右子樹（或左子樹）頂替它的位置，再釋放它?，F(xiàn)在是37頁\一共有84頁\編輯于星期五被刪結(jié)點(diǎn)左、右子樹都存在，可以在它的右子樹中尋找中序下的第一個(gè)結(jié)點(diǎn)(關(guān)鍵值最小),用它的值填補(bǔ)到被刪結(jié)點(diǎn)中，再來處理這個(gè)結(jié)點(diǎn)的刪除問題。5378651787092345刪除45缺右子樹,用左子樹頂替53786517870923現(xiàn)在是38頁\一共有84頁\編輯于星期五8853788817940923刪除78缺左子樹,用右子樹頂替53948817092353788117940945刪除78在右子樹上找中序下第一個(gè)結(jié)點(diǎn)填補(bǔ)2365538188179409452365現(xiàn)在是39頁\一共有84頁\編輯于星期五(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現(xiàn)在是40頁\一共有84頁\編輯于星期五2.平衡二叉樹(高度平衡二叉樹）

AVL樹：由和提出。結(jié)點(diǎn)的平衡因子：結(jié)點(diǎn)的左右子樹的深度之差。平衡二叉樹：任意結(jié)點(diǎn)的平衡因子的絕對(duì)值小于等于1的二叉樹。T1T2T3T4T50102-1000-112100-2（1）AVL樹的定義現(xiàn)在是41頁\一共有84頁\編輯于星期五（2）AVL樹的存儲(chǔ)結(jié)構(gòu)：typedefintDataType;//結(jié)點(diǎn)數(shù)據(jù)類型typedefstructnode{//AVL樹結(jié)點(diǎn)定義

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

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

structnode*leftChild,*rightChild;//結(jié)點(diǎn)左、右子樹指針域}AVLNode;typedefAVLNode*AVLTree;//AVL樹現(xiàn)在是42頁\一共有84頁\編輯于星期五如果在一棵平衡的二叉搜索樹中插入一個(gè)新結(jié)點(diǎn)，造成了不平衡。此時(shí)必須調(diào)整樹的結(jié)構(gòu)，使之平衡化。平衡化旋轉(zhuǎn)有兩類：?jiǎn)涡D(zhuǎn)(左旋和右旋)

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

Hash函數(shù)實(shí)現(xiàn)的是將一組關(guān)鍵字映象到一個(gè)有限的地址區(qū)間上，理想的情況是不同的關(guān)鍵字得到不同的地址。設(shè)K1和K2為關(guān)鍵字,若K1≠K2,H(K1)=H(K2),則稱K1,K2為同義詞,K2與K1發(fā)生了沖突例設(shè)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ā)生沖突現(xiàn)在是61頁\一共有84頁\編輯于星期五9.3.1哈希表相關(guān)術(shù)語采用哈希表進(jìn)行存儲(chǔ)和查找需要著重考慮兩個(gè)問題：（a）選擇一個(gè)好的哈希（散列）函數(shù)；（b）選擇一種解決沖突（碰撞）的方法。現(xiàn)在是62頁\一共有84頁\編輯于星期五例1人口統(tǒng)計(jì)表110.5212.6311.0420.8......150...序號(hào)(地址)年齡人數(shù)(萬)

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

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

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

H(key)=keyH(key)=a.key+b現(xiàn)在是63頁\一共有84頁\編輯于星期五例2學(xué)生成績(jī)表200041劉大海

男8075200042王偉

男9083200043吳曉英

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

現(xiàn)在是64頁\一共有84頁\編輯于星期五例3標(biāo)識(shí)符表ABCCADDAT

FOXYABZOO1234562526序號(hào)標(biāo)識(shí)符(key)H(key)=key的第一個(gè)字母在字母表中的序號(hào)key=ABCCADDATFOXYABZOOH(key)=13462526現(xiàn)在是65頁\一共有84頁\編輯于星期五2.除留余數(shù)法設(shè)哈希表HT[0..m-1]的表長(zhǎng)為m，哈希地址為key除以p所的的余數(shù)：

H(key)=keyMODp//PASCAL語言

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

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

或不包含小于20的質(zhì)因子的合數(shù)，如：713(=23*31)現(xiàn)在是66頁\一共有84頁\編輯于星期五例1設(shè)m=130,取p=127,

H(key)=key%127

012.....129例2設(shè)m=256取p=251

H(key)=key%251012.....255現(xiàn)在是67頁\一共有84頁\編輯于星期五例設(shè)哈希表的地址范圍為0～20,哈希函數(shù)為H(K)=K%19輸入關(guān)鍵字序列：39,22,21,37,36,38,19,解決沖突的方法為線性探測(cè)再散列(哈希),構(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現(xiàn)在是68頁\一共有84頁\編輯于星期五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]。對(duì)于H(k)=k%19，所有的19a+b為同義詞,0<b<19如：5,24,43,62,81,.....01234517181920HT[0..20]key現(xiàn)在是69頁\一共有84頁\編輯于星期五3.平方取中法----取關(guān)鍵字平方后的中間某幾位為哈希地址,即：

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

H(K)39152152210441446003603361296293814444413016916613362138390

3

162944455299key現(xiàn)在是70頁\一共有84頁\編輯于星期五4.折疊法將關(guān)鍵字分割成位數(shù)相同的幾部分,然后取這幾部分的疊加和作為哈希地址。(1)邊界折疊法

設(shè)表地址范圍為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]現(xiàn)在是71頁\一共有84頁\編輯于星期五4.折疊法將關(guān)鍵字分割成位數(shù)相同的幾部分,然后取這幾部分的疊加和作為哈希地址。(2)移位折疊法(移位法)

設(shè)表地址范圍為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]現(xiàn)在是72頁\一共有84頁\編輯于星期五5.數(shù)字分析法設(shè)哈希表中可能出現(xiàn)的關(guān)鍵字都是事先知道的,則可取關(guān)鍵字的若干分布均勻的位組成哈希地址。kH(k)902006720690443134319013456145904432643290532435249061791679901345690200679044313904432690532439061791145206431432524679HT[0..999]現(xiàn)在是73頁\一共有84頁\編輯于星期五6.隨機(jī)數(shù)法

H(key)=random(key)random(key)為產(chǎn)生偽隨機(jī)數(shù)的函數(shù)7.靈活構(gòu)造哈希函數(shù)例.設(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,用線性探測(cè)再散列法解決沖突。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現(xiàn)在是74頁\一共有84頁\編輯于星期五9.3.3如何解決沖突1.開放地址法(開式尋址法)假定記錄Ri,RX的關(guān)鍵字Ki,KX為同義詞，散列地址為q,Ri已存入HT[0..m-1]中的HT[q]中，則RX存入HT中的某個(gè)空位上。依次在地址:

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

中尋找一個(gè)空位，叫做線性探測(cè)再散列。

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

q-1qq+1m-1RiRX現(xiàn)在是75頁\一共有84頁\編輯于星期五課堂練習(xí)：設(shè)H(k)=k的首字母在字母表中的序號(hào),用線性探測(cè)再散列法解決沖突，依次用下列關(guān)鍵字，構(gòu)造哈希表HT[0..28]。kH(k)

A1DEC4ZMN26DAB4ZE26ANT1YY25ZOO26CAD3YES25ZY26LL12DE401234567

121325262728HT[0..28]

12345678910111213現(xiàn)在是76頁\一共有84頁\編輯于星期五例設(shè)H(k)=k的首字母在字母表中的序號(hào)，用線性探測(cè)再散列法解決沖突，依次用下列關(guān)鍵字，構(gòu)造哈希表HT[0..28]。YESAANTCADDECDABZYDELLYYZMNZEZ00kH(k)

1A12DEC43ZMN264DAB45ZE266ANT17YY258ZOO269CAD310YES2511ZY2612LL1213DE401234567

1225262728HT[0..28]現(xiàn)在是77頁\一共有84頁\編輯于星期五(2)二次探測(cè)再散列

假定記錄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,...中尋找一個(gè)空位，叫做二次探測(cè)再散列。例:

設(shè)記錄X和A為同義詞，散列地址為50,二次探測(cè)再散列的地址序列為：51,49,54,46,59,41,66,34,75,......HT[0..99]GECABDF03441464950515459667599XXXXXXXXGECABDFX03441464950515459667599現(xiàn)在是78頁\一共有84頁\編輯于星期五2.鏈地址法將關(guān)鍵字為同義詞的所有記錄存入同一鏈表中。（表頭插入）例設(shè)H(k)=k的首字母在字母表中的序號(hào),用下列關(guān)鍵字造哈希表HT[1..26]kH(k)

A1DEC4ZMN26DAB4ZE26ANT1YY25ZOO26CAD3YES25ZY26LL12DE4

12345678910111213∧∧∧∧HT[1..26]ZEZOOZYZMN∧DEYESYY∧CAD∧ANTA∧DABDEC∧LL∧1234122526現(xiàn)在是79頁\一共有84頁\編輯