數(shù)據(jù)結(jié)構(gòu)第九章查找數(shù)據(jù)結(jié)構(gòu)第九章查找1第九章查找

查找表:由同一類型的數(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ù)學外語200041劉大海2查找表的操作:

生成查找表

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

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

插入新元素(記錄)x

刪除元素(記錄)x......查找表的操作:3查找----根據(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ù)元素(記錄)。查找----根據(jù)給定的某個關(guān)鍵字值，在查找表中確定一個其關(guān)鍵4查找表的類型及其查找方法(1)靜態(tài)查找表

●

順序表，用順序查找法

●

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

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

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

鍵樹(3)哈希(Hash)表查找表的類型及其查找方法5平均查找長度----查找一個記錄時比較關(guān)鍵字次數(shù)的平均值。

n

ASL=∑PiCii=1Pi---查找r[i]的概率Ci---查找r[i]所需比較關(guān)鍵字的次數(shù)平均查找長度----查找一個記錄時比較關(guān)鍵字次數(shù)的平均值。62041劉大海...2042王偉...2046吳曉英..............................0123maxsizeelemkeyname...監(jiān)視哨9.1靜態(tài)查找表順序表與順序查找法1.順序表的描述

length2041劉大海...2042王偉...2046吳曉英..7例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;例1元素類型為記錄(結(jié)構(gòu))8

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

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

intlength;}SSTable;SSTableST1,ST2;121030202515//////601292.順序查找法(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。2.順序查找法(sequentialsearch)算法設10輸入：查找表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}輸入：查找表ST，查找條件（關(guān)鍵字）k11算法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,則查找成功；否則,查找失敗。算法2：假定使用監(jiān)視哨elem[0]12輸入：查找表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}輸入：查找表ST，查找條件（關(guān)鍵字）k13因5S做得不好而引發(fā)的設備故障，在作業(yè)現(xiàn)場是舉不勝舉，如潤滑的堵塞、因灰塵導致馬達燒壞、光電管臟污產(chǎn)生錯誤動作。5．塑造企業(yè)文化24.2招標代理機構(gòu)可以根據(jù)本須知第9條規(guī)定，通過修改招標文件適當推遲投標截止時間。在這種情況下，招標代理機構(gòu)和投標人受投標截止時間約束的所有權(quán)利和義務將延長至新的截止期。2.9對容器的檢驗（查）人員、操作人員進行安全技術(shù)教育和技術(shù)考核工作。五、壓力容器、壓力管道使用管理及定期檢驗制度2、增加下級：如果您準備增加某個級別的下級資料，應先在左邊樹狀窗口中選擇該級，然后再單擊【+】；20.5本合同終止時雙方未了的債權(quán)和債務不受合同中止的影響,債務人應繼續(xù)償還未了的債務。22.6未按照規(guī)定簽署及密封的投標文件將被視為非實質(zhì)性響應投標而予以拒絕。【自檢】3查找算法性能分析：對n個記錄的表,所需比較關(guān)鍵字的次數(shù)

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

P2=...

=

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

因5S做得不好而引發(fā)的設備故障，在作業(yè)現(xiàn)場是舉不勝舉，如潤滑14●考慮查找失敗:使用監(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●考慮查找失敗:使用監(jiān)視哨elem[0],為n+1151.有序表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=2510121820253040123416

假定k=4051012182025304012345678↑↑↑lowmidhiglow=1,hig=8mid=(low+hig)/2=451012182025304012345678↑↑↑lowmidhiglow=5,hig=8mid=(low+hig)/2=6假定k=40510121820253040121751012182025304012345678↑↑lowmidhig

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

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

lowmidhig

low=8,hig=8mid=(low+hig)/2=8↑↑↑51012182025304012341851012182025304012345678↑↑↑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↑↑↑510121820253040123419

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

midhiglow

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

midhiglow

mid=5low=6,hig=5↑↑↑hig<low,查找失敗假定k=22（續(xù)）5101218202530401203折半查找算法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；//查右子表｝3折半查找算法121if(ST.elem[mid].key==k){printf("success\n”)；//查找成功returnmid；}else{printf("fail\n”)；//查找失敗return0；}}if(ST.elem[mid].key==k)22折半查找算法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}折半查找算法2234.判定樹（描述折半查找過程的二叉樹）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)鍵字比較。4.判定樹（描述折半查找過程的二叉樹）639147112124●若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●若n=2k-1,則判定樹為滿二叉樹,其深度為k25第七條各企業(yè)黨組織要堅持黨建帶團建原則，作好本單位團干部競爭上崗的指導工作。各級團組織要本著對組織、對團員負責的態(tài)度，加強宣傳、廣泛發(fā)動，認真組織開展好競爭上崗工作。上海有一家在淮海中路的巴黎婚紗店。他們在拍結(jié)婚照的時候，會問客戶拍外景的嗎？拍外景要在哪一種別墅？要不要白馬陪伴新人呢？他們的攝影組合分為Ａ套，Ｂ套，Ｃ套，都有很好聽的名稱，例如百年好合，萬年富貴等。這樣按照一定的規(guī)格，滿足顧客追求的不同目標。31.2資格性檢查是依據(jù)法律法規(guī)和招標文件的規(guī)定，對投標文件中資格證明、投標保證金等進行審查，以確定投標人是否具備投標資格。1、任何對地面、天花的改動和分隔的改變，均應報管理處審批，裝修面積超過50平方米的還需報公安局消防處審批。（4）保證交貨期的措施（必要時提供生產(chǎn)計劃周期表）。（2）有良好的執(zhí)行合同能力和售后服務承諾;三、評標方法（12）不同投標人的投標文件出現(xiàn)了評標委員會認為不應當雷同的情況。5S活動沒有輕松安逸的方法，一定要付出努力才能真正認識5S。。通過全員行動形成行為意識的改變，直至養(yǎng)成好習慣到人的行為素質(zhì)的改變。11、成交通知書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，判定樹第七條各企業(yè)黨組織要堅持黨建帶團建原則，作好本單位團干部2620...15...30...10...35...33...40...45...50...60...58...52.........key其它數(shù)據(jù)..首地址最大key123456789101112131234分塊表索引表k=40k=55k=38第一塊第二塊第三塊第四塊20...15...30...10...327●

條件(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)●條件289.2動態(tài)查找表1.二叉排序樹(二叉查找樹）(1)二叉排序樹的定義如果二叉樹的任一結(jié)點大于其非空左子樹的所有結(jié)點，而小于其非空右子樹的所有結(jié)點，則這棵二叉樹稱為二叉排序樹。對一棵二叉排序樹進行中序遍歷，所得的結(jié)點序列一定是遞增有序的。8514103585401080353LDR：5,8,10,14,35LDR：3,5,8,10,35,40,809.2動態(tài)查找表8514103585401080353LD29下列二叉樹是否為二叉排序樹？30111815196410556026803010281522T1T230T3下列二叉樹是否為二叉排序樹？301118151964105530（2）二叉排序樹的生成

設輸入序列為：30,11,18,4,55,19,15,70,58303011183011184193011301118419301118455193011184551570193011184551570583011184555515插入30插入11插入18插入4插入55插入19插入15插入70插入58（2）二叉排序樹的生成303011183011184193031課堂練習：

設輸入關(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課堂練習：55581519460188070113032(3)二叉排序樹的存儲結(jié)構(gòu)lchilddatarchildkey.....左子樹右子樹結(jié)點類型定義：structnode{struct{intkey；//關(guān)鍵字.....//其它數(shù)據(jù)項}data；structnode*lchild,*rchild；//左右子樹的指針}*root,*t；結(jié)點形式：(3)二叉排序樹的存儲結(jié)構(gòu)lchilddatarch33(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;}(4)插入1個元素到二叉排序樹的算法34(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)；//查右子樹}(5)二叉排序樹的查找算法35b)非遞歸算法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；//查找失敗}b)非遞歸算法36(6)二叉排序樹的刪除在二叉排序樹中刪除一個結(jié)點時，必須將因刪除結(jié)點而斷開的二叉鏈表重新鏈接起來，同時確保二叉排序樹的性質(zhì)不會失去。為保證在刪除節(jié)點后二叉排序樹的性質(zhì)不會丟失:刪除葉結(jié)點，只需將其雙親結(jié)點指向它的指針置空，再釋放它即可。被刪結(jié)點缺左子樹（或右子樹），可以用被刪節(jié)點的右子樹（或左子樹）頂替它的位置，再釋放它。(6)二叉排序樹的刪除在二叉排序樹中刪除一個結(jié)點時，必須將因37被刪結(jié)點左、右子樹都存在，可以在它的右子樹中尋找中序下的第一個結(jié)點(關(guān)鍵值最小),用它的值填補到被刪結(jié)點中，再來處理這個結(jié)點的刪除問題。5378651787092345刪除45缺右子樹,用左子樹頂替537865178709235378651787092345刪除45缺右子樹,用左子樹38____________________________________________________________站在顧客的立場，一切以人為本，以誠待客，為顧客排憂解難，提供各類專項、特約服務；超越顧客期望，給顧客意外的驚喜。(15) 在本合同期限內(nèi)，指定并保持一名業(yè)主代表，全權(quán)負責與承包方的聯(lián)絡。C、鄉(xiāng)鎮(zhèn)利用中心藥店，包裝、宣傳（宣傳、包裝由中心藥店人員完成布貨，收款由OTC代表負責）。4．人事政策中國有句古詩“寶劍鋒從磨礪出，梅花香自苦寒來”。因此，企業(yè)利用海豚理論來對員工進行恰當?shù)募?，用象征性的方式鼓勵員工向上發(fā)展。發(fā)展并不是口頭的表達，而需要好好研究，下苦功夫?qū)W習。服務也是一樣，只有不斷地演練與學習，才能更成熟、更精致。1、團(總)支部每年向企業(yè)團委推薦名額不少于兩名，但不超過青年人數(shù)的5%。（1）使用偽造、變造的許可證件；35.3接受最終審查的中標候選人，必須如實回答和受理有關(guān)詢問或考察，并提供所需的有關(guān)資料。26.2根據(jù)現(xiàn)行稅法規(guī)定向賣方征收的與本合同有關(guān)的一切稅費均由賣方負責。2、優(yōu)秀團干部的推薦，由上級團委召開團委委員會議，擬出推薦入選，在征得團干部所在企業(yè)黨組織的同意后，填寫《重慶機電控股（集團）公司優(yōu)秀青年人才上崗工作推薦表》；8853788817940923刪除78缺左子樹,用右子樹頂替53948817092353788117940945刪除78在右子樹上找中序下第一個結(jié)點填補2365538188179409452365______________________________39(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(7)查找性能分析582849304558151910181402.平衡二叉樹(高度平衡二叉樹）

AVL樹：由和提出。結(jié)點的平衡因子：結(jié)點的左右子樹的深度之差。平衡二叉樹：任意結(jié)點的平衡因子的絕對值小于等于1的二叉樹。T1T2T3T4T50102-1000-112100-2（1）AVL樹的定義2.平衡二叉樹(高度平衡二叉樹）T1T241（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樹（2）AVL樹的存儲結(jié)構(gòu)：typedefintData42如果在一棵平衡的二叉搜索樹中插入一個新結(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)如果在一棵平衡的二叉搜索樹中插入一個新結(jié)點，造成了不平衡。此43如果在某一結(jié)點發(fā)現(xiàn)高度不平衡，停止回溯。從發(fā)生不平衡的結(jié)點起，沿剛才回溯的路徑取直接下兩層的結(jié)點。如果這三個結(jié)點處于一條直線上，則采用單旋轉(zhuǎn)進行平衡化。單旋轉(zhuǎn)可按其方向分為左單旋轉(zhuǎn)和右單旋轉(zhuǎn),其中一個是另一個的鏡像，其方向與不平衡的形狀相關(guān)。如果這三個結(jié)點處于一條折線上，則采用雙旋轉(zhuǎn)進行平衡化。雙旋轉(zhuǎn)分為先左后右和先右后左兩類。如果在某一結(jié)點發(fā)現(xiàn)高度不平衡，停止回溯。從發(fā)生不平衡的結(jié)點起44右單旋轉(zhuǎn)左單旋轉(zhuǎn)左右雙旋轉(zhuǎn)右左雙旋轉(zhuǎn)右單旋轉(zhuǎn)左單旋轉(zhuǎn)左右雙旋轉(zhuǎn)右左雙旋轉(zhuǎn)45在子樹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在子樹E中插入新結(jié)點，該子樹高度增1導致結(jié)點A的平衡因子變成46在子樹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在子樹D中插入新結(jié)點，該子樹高度增1導致結(jié)點A的平衡因子變成47在子樹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在子樹F或G中插入新結(jié)點，該子樹的高度增1。結(jié)點A的平衡因子48插入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插入00+1+2-1+1hhACEDhhhAhBCEDB左單4900+200-1hhACED+2hhhAhBCEDB右單旋轉(zhuǎn)FGFGh-1h-1再以結(jié)點E為旋轉(zhuǎn)軸，將結(jié)點A順時針旋轉(zhuǎn)。00+200-1hhACED+2hhhAhBCEDB右單FG50右左雙旋轉(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右左雙旋轉(zhuǎn)是左右雙旋轉(zhuǎn)的鏡像（d）先右后左雙旋轉(zhuǎn)(Rota51從結(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從結(jié)點A起沿插入路徑選取3個結(jié)點A、C和D，它們位于一條形如52再以結(jié)點D為旋轉(zhuǎn)軸，將結(jié)點A逆時針旋轉(zhuǎn)。00-20+10hhACE-2hhhAhBCEDB左單旋轉(zhuǎn)FGFGDh-1h-100-20+10hhACE-2hhhAhBCEDB左單FGF53在向一棵本來是高度平衡的AVL樹中插入一個新結(jié)點時，如果樹中某個結(jié)點的平衡因子的絕對值|balance|>1，則出現(xiàn)了不平衡，需要做平衡化處理。算法從一棵空樹開始，通過輸入一系列對象關(guān)鍵碼，逐步建立AVL樹。在插入新結(jié)點時使用平衡旋轉(zhuǎn)方法進行平衡化處理。（3）AVL樹的插入在向一棵本來是高度平衡的AVL樹中插入一個新結(jié)點時，如果樹中541616例，輸入關(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-21616例，輸入關(guān)鍵碼序列為{16,3,7,11,55181803163+10160-2右左雙旋739000182611+1732616119+1左單旋97161400-171126269-1-111181803163+10160-2右左雙旋739000182561518-231816+2左右雙旋73000117149+116150-111262614-1+29從空樹開始的建樹過程1518-231816+2左右雙旋73000117149+157平衡二叉樹、二叉排序樹、平衡二叉排序樹的區(qū)別：4850351020414560平衡二叉排序樹6870651020414580平衡二叉樹68807510414585二叉排序樹-2-1-101-1-11-110000000000000平衡二叉樹、二叉排序樹、平衡二叉排序樹的區(qū)別：48503558靜態(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ù)元素可能在的位置。靜態(tài)和動態(tài)查找表查找方法599.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ù)計算出的地址稱為哈希地址或散列地址。9.3哈希(Hash)表和哈希法60

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ù)據(jù)結(jié)構(gòu)第九章查找培訓課件61采用哈希表進行存儲和查找需要著重考慮兩個問題：（a）選擇一個好的哈希（散列）函數(shù)；（b）選擇一種解決沖突（碰撞）的方法。數(shù)據(jù)結(jié)構(gòu)第九章查找培訓課件62例1人口統(tǒng)計表110.5212.6311.0420.8......150...序號(地址)年齡人數(shù)(萬)

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

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

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

H(key)=keyH(key)=a.key+b例1人口統(tǒng)計表110.5212.6363例2學生成績表200041劉大海

男8075200042王偉

男9083200043吳曉英

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

例2學生成績表200041劉大海男80752000464例3標識符表ABCCADDAT

FOXYABZOO1234562526序號標識符(key)H(key)=key的第一個字母在字母表中的序號key=ABCCADDATFOXYABZOOH(key)=13462526例3標識符表ABCCADDATFOXYAB652.除留余數(shù)法設哈希表HT[0..m-1]的表長為m，哈希地址為key除以p所的的余數(shù)：

H(key)=keyMODp//PASCAL語言

H(key)=key%p//C語言其中：MOD,%為“取模”或“求余”

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

或不包含小于20的質(zhì)因子的合數(shù)，如：713(=23*31)2.除留余數(shù)法66例1設m=130,取p=127,

H(key)=key%127

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

H(key)=key%251012.....255例1設m=130,取p=127,01267例設哈希表的地址范圍為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例設哈希表的地址范圍為0～20,哈希函數(shù)為6838392122195536371756再輸入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]key3839212219553637175693.平方取中法----取關(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

162944455299key3.平方取中法----取關(guān)鍵字平方后的中間某幾位為哈希地址,704.折疊法將關(guān)鍵字分割成位數(shù)相同的幾部分,然后取這幾部分的疊加和作為哈希地址。(1)邊界折疊法

設表地址范圍為0～999●

k1=056439527650+439+725=1814H(k1)=814●k2=123486790321+486+097=907H(k2)=907●k3=300600007003+600+700=1303H(k2)=30330060000705643952712348679001

303814907999HT[0..999]4.折疊法(1)邊界折疊法30060000705643952714.折疊法將關(guān)鍵字分割成位數(shù)相同的幾部分,然后取這幾部分的疊加和作為哈希地址。(2)移位折疊法(移位法)

設表地址范圍為0～999●

k1=056439527056+439+527=1022H(k1)=022●k2=123486790123+486+790=1399H(k2)=399●k3=300600007300+600+007=907H(k2)=90705643952712348679030060000701

22399907999HT[0..999]4.折疊法(2)移位折疊法(移位法)056439527123725.數(shù)字分析法設哈希表中可能出現(xiàn)的關(guān)鍵字都是事先知道的,則可取關(guān)鍵字的若干分布均勻的位組成哈希地址。kH(k)902006720690443134319013456145904432643290532435249061791679901345690200679044313904432690532439061791145206431432524679HT[0..999]5.數(shù)字分析法kH(k)901345690736.隨機數(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

61718213740key6.隨機數(shù)法例.設哈希表為HT[0..40],哈希函數(shù)為：741.開放地址法(開式尋址法)假定記錄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-1RiRXKi...HT[0..m-1]0RiRX75課堂練習：設H(k)=k的首字母在字母表中的序號,用線性探測再散列法解決沖突，依次用下列關(guān)鍵字，構(gòu)造哈希表HT[0..28]。kH(k)

A1DEC4ZMN26DAB4ZE26ANT1YY25ZOO26CAD3YES25ZY26LL12DE401234567

121325262728HT[0..28]

12345678910111213課堂練習：設H(k)=k的首字母在字母表中的序號,用線性探76例設H(k)=k的首字母在字母表中的序號，用線性探測再散列法解決沖突，依次用下列關(guān)鍵字，構(gòu)造哈希表HT[0..28]。YESAANTCADDECDABZYDELLYYZMNZEZ00kH(k)

1A12DEC43ZMN264DAB45ZE266ANT17YY258ZOO269CAD310YES2511ZY2612LL1213DE401234567

1225262728HT[0..28]例設H(k)=k的首字母在字母表中的序號，用線性探測再77(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(2)二次探測再散列HT[0..99]GECABDF0782.鏈地址法將關(guān)鍵字為同義詞的所有記錄存入同一鏈表中。（表頭插入）例設H(k)=k的首字母在字母表中的序號,用下列關(guān)鍵字造哈希表HT[1..26]kH(k)

A1DEC4ZMN26DAB4ZE26ANT1YY25ZOO26CAD3YES25ZY26LL12DE4

12345678910111213∧∧∧∧HT[1..26]ZEZOOZYZMN∧DEYESYY∧CAD∧ANTA∧DABDEC∧LL∧12341225262.鏈地址法kH(k)1∧∧∧∧HT[1..2792.鏈地址法將關(guān)鍵字為同義詞的所有記錄存入同一鏈表中。(表尾插入)例設H(k)=k的首字母在字母表中的序號,用下列關(guān)鍵字造哈希表HT[1..26]kH(k)

A1DEC4ZMN26DAB4ZE26ANT1YY25ZOO26CAD3YES25ZY26LL12DE4

12345678910111213HT[1..26]ZOOZEZMNZY∧DECYYYES∧CAD∧AANT∧DABDE∧LL∧∧∧∧∧12341225262.鏈地址法kH(k)1HT[1..26]ZO803.建立公共溢出區(qū)將發(fā)生沖突的所有記錄存入一個公共溢出表OT[0..v]中。例設H(k)=k的首字母在字母表中的序號,用下列關(guān)鍵字生成基本表HT[1..26]和溢出表OT[0..50]kH(k)1A12DEC43ZMN264DAB45ZE266ANT17YY258ZOO269CAD310YES2511ZY2612LL1213DE4ACADDECLLYYZMNHT[1..26]1234122526DABZEANTZOOYESZYDEOT[0..50]1234567503.建立公共溢出區(qū)kH(k)ACADDEC814.再哈希法

發(fā)生沖突時，使用下一個哈希函數(shù)計算哈希地址：

j1=H1(K)；j2=H2(K)；j3=H3(K)；......哈希表的查找及其分析∧∧∧∧ZEZOOZYZMN∧DEYESYY∧CAD∧ANTA∧DABDEC∧LL∧例1(鏈地址法)假定每個記錄的查找概率相等，查找成功時的平均查找長度：

ASL=(1+2+1+1+2+3+1+1+2+1+2+3+4)/13=24/13≈1.854.再哈希法∧∧∧∧ZEZOOZYZMN∧DEYESYY∧C82例2（給定線性探測再散列得到的哈希表如右所示)假定每個記錄的查找概率相等，查找成功時的平均查找長度.

關(guān)鍵字KH(K)比較次數(shù)

YES255

A11ANT12

CAD31DEC41DAB42ZY2610DE44LL121YY251ZMN261ZE262Z00263合計34

YESAANTCADDECDABZYDELLYYZMNZEZ00HT[0..28]01234567

121325262728ASLsucc=34/13≈2.62例2（給定線性探測再散列得到的哈希表如右所示)假定每個記錄83YESAANTCADDECDABZYDELLYYZMNZEZ00HT[0..28]01234567

121325262728ASLunsucc=108/28≈

3.857例2(續(xù))(線性探測再散列)查找不成功時的平均查找長度.需統(tǒng)計不成功時比較次數(shù)H(K)比較次數(shù)H(K)比較次數(shù)0 9 18 15127 16136 17145 18154 19163 20172 21181 22191 231101 241111 2513122 26121 27111 28 10YESAANTCADDECDABZYDEL84數(shù)據(jù)結(jié)構(gòu)第九章查找數(shù)據(jù)結(jié)構(gòu)第九章查找85第九章查找

查找表:由同一類型的數(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ù)學外語200041劉大海86查找表的操作:

生成查找表

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

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

插入新元素(記錄)x

刪除元素(記錄)x......查找表的操作:87查找----根據(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ù)元素(記錄)。查找----根據(jù)給定的某個關(guān)鍵字值，在查找表中確定一個其關(guān)鍵88查找表的類型及其查找方法(1)靜態(tài)查找表

●

順序表，用順序查找法

●

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

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

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

鍵樹(3)哈希(Hash)表查找表的類型及其查找方法89平均查找長度----查找一個記錄時比較關(guān)鍵字次數(shù)的平均值。

n

ASL=∑PiCii=1Pi---查找r[i]的概率Ci---查找r[i]所需比較關(guān)鍵字的次數(shù)平均查找長度----查找一個記錄時比較關(guān)鍵字次數(shù)的平均值。902041劉大海...2042王偉...2046吳曉英..............................0123maxsizeelemkeyname...監(jiān)視哨9.1靜態(tài)查找表順序表與順序查找法1.順序表的描述

length2041劉大海...2042王偉...2046吳曉英..91例1元素類型為記錄(結(jié)構(gòu))#definemaxsize100//表長100

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

typedefstruct

{El