大學(xué)教程(零起點(diǎn))數(shù)據(jù)結(jié)構(gòu)-查找

第九章查找9.1基本概念9.2線性表的查找9.3樹(shù)上的查找9.4散列技術(shù)1基本概念集合：是一種邏輯結(jié)構(gòu)，其特點(diǎn)是元素之間沒(méi)有邏輯關(guān)系，元素只是共處于一個(gè)集合當(dāng)中。集合的操作：插入刪除查找2查找：是指在數(shù)據(jù)元素集合中查找滿(mǎn)足某種條件的數(shù)據(jù)元素。查找表：稱(chēng)用于查找的數(shù)據(jù)集合為查找表。查找表由同一類(lèi)型的數(shù)據(jù)元素所構(gòu)成，在查找表的結(jié)構(gòu)中每一個(gè)數(shù)據(jù)元素稱(chēng)為查找對(duì)象。關(guān)鍵字：其中應(yīng)當(dāng)有一個(gè)屬性，其值可以唯一地標(biāo)識(shí)這個(gè)數(shù)據(jù)元素基本概念3僅作查詢(xún)和檢索操作的查找表。靜態(tài)查找表有時(shí)在查詢(xún)之后，還需要將“查詢(xún)”結(jié)果為“不在查找表中”的數(shù)據(jù)元素插入到查找表中；或者，從查找表中刪除其“查詢(xún)”結(jié)果為“在查找表中”的數(shù)據(jù)元素。動(dòng)態(tài)查找表查找表可分為兩類(lèi):內(nèi)查找外查找4根據(jù)給定的某個(gè)值，在查找表中確定一個(gè)其關(guān)鍵字等于給定值的數(shù)據(jù)元素或（記錄）

若查找表中存在這樣一個(gè)記錄，則稱(chēng)“查找成功”，給出整個(gè)記錄的信息，或指示該記錄在查找表中的位置；否則稱(chēng)“查找不成功”，給出“空記錄”或“空指針”。查找平均查找長(zhǎng)度59.2線性表的查找1順序查找2有序表上的二分查找3索引順序表上的分塊查找61順序表上的查找順序查找是一種最簡(jiǎn)單的查找方法基本思想是：從表的一端開(kāi)始，順序掃描線性表，依次將掃描到的結(jié)點(diǎn)關(guān)鍵字和待找的值Ｋ相比較，若相等，則查找成功，若整個(gè)表掃描完畢，仍末找到關(guān)鍵字等于Ｋ的元素，則查找失敗。71順序表上的查找利用一段連續(xù)內(nèi)存存儲(chǔ)待查找數(shù)據(jù)key其他信息N個(gè)數(shù)據(jù)Maxsize個(gè)100位置不存數(shù)據(jù)8順序表的類(lèi)型定義typedefstruct{KeyTypekey;//key為關(guān)鍵字InfoTypeotherinfo；//其他信息}NodeType;typedefNodeTypeSeqList[n+1];

SeqListR;//問(wèn)：R的內(nèi)存中有什么信息？9key其他信息N個(gè)數(shù)據(jù)n個(gè)1查找時(shí)，假設(shè)要查找數(shù)據(jù)為K，則將K存入0位置即：R[0].key=K;從i=n位置開(kāi)始，當(dāng)R[i].key<>K,i--向前找查找結(jié)束后i即為要找的位置問(wèn)題：若找到了，i值為？未找到，i值為？？R10key其他信息N個(gè)數(shù)據(jù)n個(gè)1查找時(shí)，假設(shè)要查找數(shù)據(jù)為K，則將K存入0位置即：R[0].key=K;從i=n位置開(kāi)始，當(dāng)R[i].key<>K,i--向前找查找結(jié)束后i即為要找的位置R11順序查找的平均查找長(zhǎng)度：Ｐi為查找第i個(gè)元素的概率Ｃi為查找第i個(gè)元素所用到的比較次數(shù)。順序查找的時(shí)間復(fù)雜度：O（n）122,有序表上的查找策略：選中間點(diǎn)比較，縮小查找范圍二分查找，也稱(chēng)折半查找，是一種高效率的查找方法。但要求表中元素必須按關(guān)鍵字有序(升序或降序，現(xiàn)設(shè)表中元素為升序排列)。13查找key=16的過(guò)程[3101623263853]lowhighmid1234567]14二分查找的基本思想是：將待查元素K與有序表中點(diǎn)上的元素R[mid].key進(jìn)行比較，若相等，則查找成功；若k>R[mid].key，則在大于的區(qū)間繼續(xù)查找；若k<R[mid].key，則在小于的區(qū)間繼續(xù)查找。通過(guò)每比較一次，查找區(qū)間的長(zhǎng)度就縮小一半，如此不斷進(jìn)行下去，直到查找成功或失敗。15key其他信息highn個(gè)lowRmid16二分查找的算法intbinsearch(R,K){low=1;high=n;while(low<=high){mid=(low+high)/2;if(K==R[mid].key)returnmid;if(K<R[mid].key)high=mid-1;if(K>R[mid].key)low=mid+1；}return0；}17二分查找的判定樹(shù)6391425781011判定樹(shù)12233334444二分查找判定樹(shù)的深度與

n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)深度一樣18二分查找的平均查找長(zhǎng)度：

假設(shè)結(jié)點(diǎn)數(shù)為n，則其判定樹(shù)深度為k=log2n+1

則深度為1的1個(gè)結(jié)點(diǎn)

深度為2的2個(gè)

深度為3的4個(gè)

深度為k的2k-1個(gè)

假設(shè)為等概率情況，則二分查找的平均查找長(zhǎng)度：log2n193索引順序表上的查找分塊查找22488606122212138920334244382448605874498653順序表索引表分塊：將一個(gè)主表分成n個(gè)子表，分塊有序：要求子表之間按關(guān)鍵字有序，塊內(nèi)無(wú)序：子表中元素可以無(wú)序的，建立索引表：用每個(gè)子表最大關(guān)鍵字和指示塊中第一個(gè)記錄在表中位置建立索引表。20分塊查找的查找過(guò)程22488606122212138920334244382448605874498653順序表索引表21分塊查找的效率分析b是索引表長(zhǎng)度（塊數(shù)），s是塊長(zhǎng)度分塊查找的時(shí)間復(fù)雜度：O（索引表查找+塊內(nèi)查找）索引表內(nèi)查找：可以利用順序、折半查找塊內(nèi)查找：順序查找221.若查找每個(gè)記錄的概率均等，則在具有n個(gè)記錄的連續(xù)順序文件中采用順序查找法查找一個(gè)記錄，其平均查找長(zhǎng)度ASL為()。A.(n-1)/2B.n/2C.(n+1)/2D.n習(xí)題C232.對(duì)線性表進(jìn)行二分查找時(shí)，要求線性表必須（）A.以順序方式存儲(chǔ)B.以順序方式存儲(chǔ),且數(shù)據(jù)元素有序C.以鏈接方式存儲(chǔ)D.以鏈接方式存儲(chǔ),且數(shù)據(jù)元素有序B243.當(dāng)在一個(gè)有序的順序存儲(chǔ)表上查找一個(gè)數(shù)據(jù)時(shí)，即可用折半查找，也可用順序查找，但前者比后者的查找速度()A.必定快B.不一定C.在大部分情況下要快D.取決于表遞增還是遞減D254.分塊檢索中，若索引表和各塊內(nèi)均用順序查找，則有900個(gè)元素的線性表分成_________塊最好：若分成25塊，其平均查找長(zhǎng)度為_(kāi)________。即要計(jì)算x=n/s的值即當(dāng)平均查找長(zhǎng)度最小時(shí)，計(jì)算得到s的值，即可即對(duì)其求導(dǎo)數(shù)f’（s）=0時(shí)即可求得s值=30269.3樹(shù)上的查找屬于動(dòng)態(tài)查找，查找過(guò)程改變了原查找表二叉排序樹(shù)，定義如下：或者是一棵空樹(shù)，或者是具有如下特征的非空二叉樹(shù)：1)若其左子樹(shù)非空，則左子樹(shù)上所有結(jié)點(diǎn)的關(guān)鍵字均小于根結(jié)點(diǎn)的關(guān)鍵字；

2)若其右子樹(shù)非空，則右子樹(shù)上所有結(jié)點(diǎn)的關(guān)鍵字均大于等于根結(jié)點(diǎn)的關(guān)鍵字；

3)左、右子樹(shù)本身又都是一棵二叉排序樹(shù)。27二叉排序樹(shù)中序遍歷的結(jié)果是一個(gè)遞增的序列。20

40815

530

101020119

5306否是28圖中二叉排序樹(shù)的各結(jié)點(diǎn)的值為1～9，標(biāo)出各結(jié)點(diǎn)的值29已知二叉排序樹(shù)10個(gè)結(jié)點(diǎn)值依次為1-10，其結(jié)構(gòu)如圖所示，試標(biāo)出該二叉樹(shù)各結(jié)點(diǎn)所對(duì)應(yīng)得具體值。3050308020908540358832查找關(guān)鍵字==50,505035,503040355090,5080909531二叉排序樹(shù)上的查找思想

若二叉排樹(shù)為非空，先拿根結(jié)點(diǎn)值與待查值進(jìn)行比較，①若相等，則查找成功；②若根結(jié)點(diǎn)值大于待查值，則進(jìn)入左子樹(shù)繼續(xù)查找，③否則，進(jìn)入右子樹(shù)繼續(xù)查找；若在查找過(guò)程中遇到二叉排序樹(shù)的葉子結(jié)點(diǎn)時(shí)，還沒(méi)有找到待找結(jié)點(diǎn)，則查找失敗。32構(gòu)造二叉排序樹(shù)二叉排序樹(shù)的插入二叉排序樹(shù)的形態(tài)與結(jié)點(diǎn)插入順序有關(guān)根據(jù)動(dòng)態(tài)查找表的定義，“插入”操作在查找不成功時(shí)才進(jìn)行；33構(gòu)造二叉排序樹(shù)二叉排序樹(shù)的插入基本思想為：new為待插入結(jié)點(diǎn)若二叉排序樹(shù)為空，將new結(jié)點(diǎn)作為根結(jié)點(diǎn)；非空時(shí)，若樹(shù)中已有此結(jié)點(diǎn)，無(wú)須插入若new關(guān)鍵字小于樹(shù)根關(guān)鍵字，左子樹(shù)中，否則將new插到右子樹(shù)中34將33插入到如下的二叉排序樹(shù)中36125282640661829361226293335將56插入到如下的二叉排序樹(shù)中39331750925621628563350623632.給定表（39，14，22，8，65，28，88，29，67，13，10），試按元素在表中的順序?qū)⑺鼈円来尾迦胍豢贸跏紩r(shí)為空的二叉排序樹(shù)，畫(huà)出插入完成后的二叉排序樹(shù)。新插入的結(jié)點(diǎn)必為一個(gè)新的葉子結(jié)點(diǎn)，其插入位置由查找過(guò)程得到。39142286528882967131037二叉排序樹(shù)的刪除被刪除的結(jié)點(diǎn)是葉子結(jié)點(diǎn)被刪除的結(jié)點(diǎn)只有左子樹(shù)或者只有右子樹(shù)被刪除的結(jié)點(diǎn)既有左子樹(shù)，也有右子樹(shù)38（1）被刪除的結(jié)點(diǎn)是葉子結(jié)點(diǎn)50308020908540358832被刪關(guān)鍵字=8820其雙親結(jié)點(diǎn)中相應(yīng)指針域的值改為“空”3950302040809085883532（2）被刪除的結(jié)點(diǎn)只有左子樹(shù)或者只有右子樹(shù)其雙親結(jié)點(diǎn)的相應(yīng)指針域的值改為“指向被刪除結(jié)點(diǎn)的左子樹(shù)或右子樹(shù)”。被刪關(guān)鍵字=804040503080209085883532（3）被刪除的結(jié)點(diǎn)既有左子樹(shù)，也有右子樹(shù)40方式1：以其中序前驅(qū)替代被刪除結(jié)點(diǎn)，然后再刪除該前驅(qū)結(jié)點(diǎn)被刪關(guān)鍵字=5041503080209085883532（3）被刪除的結(jié)點(diǎn)既有左子樹(shù)，也有右子樹(shù)40方式1：以其中序前驅(qū)替代被刪除結(jié)點(diǎn)，然后再刪除該前驅(qū)結(jié)點(diǎn)被刪關(guān)鍵字=504236425080908588（3）被刪除的結(jié)點(diǎn)既有左子樹(shù)，也有右子樹(shù)3020353240被刪關(guān)鍵字=50方式2：p為被刪除結(jié)點(diǎn)P的左孩子代替p，p原來(lái)的右孩子做原來(lái)左孩子的最右側(cè)孩子43平衡二叉樹(shù)(AVL樹(shù))若一棵二叉樹(shù)中每個(gè)結(jié)點(diǎn)的左、右子樹(shù)的深度之差的絕對(duì)值不超過(guò)1，則稱(chēng)這樣的二叉樹(shù)為平衡二叉樹(shù)。平衡因子：結(jié)點(diǎn)的左、右子樹(shù)高度差-1,0,1548254821是平衡樹(shù)不是平衡樹(shù)4445構(gòu)造二叉平衡（查找）樹(shù)的方法是：按照構(gòu)造二叉排序樹(shù)的方法進(jìn)行構(gòu)造，出現(xiàn)不平衡時(shí)，進(jìn)行旋轉(zhuǎn)調(diào)整321231LL型RR型312321LR型RL型四種不平衡形態(tài)465020有數(shù)據(jù)序列：{20，50，35，80，90，32，85，40，88，30}請(qǐng)按順序構(gòu)造一棵二叉平衡樹(shù)3547設(shè)結(jié)點(diǎn)A為不平衡的最小子樹(shù)根結(jié)點(diǎn)，設(shè)結(jié)點(diǎn)B為插入結(jié)點(diǎn)，對(duì)該子樹(shù)進(jìn)行平衡化調(diào)整的規(guī)則如下：1）從A開(kāi)始，在A到B的路徑上連續(xù)選取三個(gè)結(jié)點(diǎn)作為調(diào)整對(duì)象；2）將三個(gè)結(jié)點(diǎn)按關(guān)鍵字值由小到大排序，取中間結(jié)點(diǎn)作為新根結(jié)點(diǎn)，較小結(jié)點(diǎn)作為其左孩子，較大結(jié)點(diǎn)作為其右孩子；3）若根結(jié)點(diǎn)在調(diào)整前有左孩子，調(diào)整后將其作為現(xiàn)有左孩子的右孩子；若根結(jié)點(diǎn)在調(diào)整前有右孩子，調(diào)整后將其作為現(xiàn)有右孩子的左孩子。48有數(shù)據(jù)序列：{20，50，35，80，90，32，85，40，88，30}請(qǐng)按順序構(gòu)造一棵二叉平衡樹(shù)502035502035809049有數(shù)據(jù)序列：{20，50，35，80，90，32，85，40，88，30}請(qǐng)按順序構(gòu)造一棵二叉平衡樹(shù)802035509050203580903285408850有數(shù)據(jù)序列：{20，50，35，80，90，32，85，40，88，30}請(qǐng)按順序構(gòu)造一棵二叉平衡樹(shù)8020355090328540888020355085328840903051有數(shù)據(jù)序列：{20，50，35，80，90，32，85，40，88，30}請(qǐng)按順序構(gòu)造一棵二叉平衡樹(shù)802035508532884090308030355085328840902052有數(shù)據(jù)序列：{20，50，35，80，90，32，85，40，88，30}請(qǐng)按順序構(gòu)造一棵二叉平衡樹(shù)8030355085328840902053有數(shù)據(jù)序列：{15，20，11，8，14，13}請(qǐng)按順序構(gòu)造一棵二叉平衡樹(shù)2011151413815111454設(shè)結(jié)點(diǎn)A為不平衡的最小子樹(shù)根結(jié)點(diǎn)，設(shè)結(jié)點(diǎn)B為插入結(jié)點(diǎn)，對(duì)該子樹(shù)進(jìn)行平衡化調(diào)整的規(guī)則如下：1）從A開(kāi)始，在A到B的路徑上連續(xù)選取三個(gè)結(jié)點(diǎn)作為調(diào)整對(duì)象；2）將三個(gè)結(jié)點(diǎn)按關(guān)鍵字值由小到大排序，取中間結(jié)點(diǎn)作為新根結(jié)點(diǎn)，較小結(jié)點(diǎn)作為其左孩子，較大結(jié)點(diǎn)作為其右孩子；3）若新根結(jié)點(diǎn)在調(diào)整前有左孩子，調(diào)整后將其作為現(xiàn)有左孩子的右孩子；若根結(jié)點(diǎn)在調(diào)整前有右孩子，調(diào)整后將其作為現(xiàn)有右孩子的左孩子。55有數(shù)據(jù)序列：{15，20，11，8，14，13}請(qǐng)按順序構(gòu)造一棵二叉平衡樹(shù)1420151181313平衡調(diào)整過(guò)程56有數(shù)據(jù)序列：{15，20，11，8，13，14}請(qǐng)按順序構(gòu)造一棵二叉平衡樹(shù)2011151314815111357有數(shù)據(jù)序列：{15，20，11，8，14，13}請(qǐng)按順序構(gòu)造一棵二叉平衡樹(shù)1320151181414平衡調(diào)整過(guò)程58設(shè)結(jié)點(diǎn)A為不平衡的最小子樹(shù)根結(jié)點(diǎn)，設(shè)結(jié)點(diǎn)B為插入結(jié)點(diǎn)，對(duì)該子樹(shù)進(jìn)行平衡化調(diào)整的規(guī)則如下：1）從A開(kāi)始，在A到B的路徑上連續(xù)選取三個(gè)結(jié)點(diǎn)作為調(diào)整對(duì)象；2）將三個(gè)結(jié)點(diǎn)按關(guān)鍵字值由小到大排序，取中間結(jié)點(diǎn)作為新根結(jié)點(diǎn)，較小結(jié)點(diǎn)作為其左孩子，較大結(jié)點(diǎn)作為其右孩子；3）若新根結(jié)點(diǎn)在調(diào)整前有左孩子，調(diào)整后將其作為現(xiàn)有左孩子的右孩子；若根結(jié)點(diǎn)在調(diào)整前有右孩子，調(diào)整后將其作為現(xiàn)有右孩子的左孩子。59B樹(shù)分為B-樹(shù)和B+樹(shù)1．B-樹(shù)的定義m階B-樹(shù)，或?yàn)榭諛?shù)，或?yàn)閙叉樹(shù)滿(mǎn)足：1）樹(shù)中每個(gè)結(jié)點(diǎn)至多有m棵子樹(shù)；2）若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，則至少有兩棵子樹(shù)；3）除根結(jié)點(diǎn)之外的所有非終端結(jié)點(diǎn)至少有m/2棵子樹(shù)；B-樹(shù)60B樹(shù)分為B-樹(shù)和B+樹(shù)1．B-樹(shù)的定義m階B-樹(shù)，或?yàn)榭諛?shù)，或?yàn)閙叉樹(shù)滿(mǎn)足：4）所有的非終端結(jié)點(diǎn)中包含以下信息數(shù)據(jù)：（n，P0，K1，P1，K2，…，Kn，Pn）n為關(guān)鍵字的個(gè)數(shù)Pi為指向子樹(shù)根結(jié)點(diǎn)的指針Ki為關(guān)鍵字，且Ki<Ki+1，，Pi-1所指子樹(shù)中所有結(jié)點(diǎn)的關(guān)鍵字均小于KiPn所指子樹(shù)中所有結(jié)點(diǎn)的關(guān)鍵字均大于Knm/2-1<=n<=m-161B樹(shù)分為B-樹(shù)和B+樹(shù)，這里主要介紹B_樹(shù)的查找和插入。1．B-樹(shù)的定義m階的B-樹(shù)，或?yàn)榭諛?shù)，或?yàn)閙叉樹(shù)滿(mǎn)足：5）所有的葉子結(jié)點(diǎn)都出現(xiàn)在同一層次上，并且不帶信息（實(shí)際上這些結(jié)點(diǎn)不存在）622．B-樹(shù)的運(yùn)算1)B-樹(shù)的查找B-樹(shù)的查找和二叉排序樹(shù)的查找相類(lèi)似B-樹(shù)每個(gè)結(jié)點(diǎn)上是多關(guān)鍵字的有序表，首先把根結(jié)點(diǎn)取出，在根結(jié)點(diǎn)所包含的關(guān)鍵字K1,…Kn中查找給定的關(guān)鍵字(順序查找\折半查找)，若找到，則查找成功；否則，到子樹(shù)中去查找，到達(dá)葉子結(jié)點(diǎn)時(shí)，查找失敗。632．B-樹(shù)的運(yùn)算2)B-樹(shù)的插入首先要經(jīng)過(guò)查找過(guò)程，查找出K的插入位置，然后再進(jìn)行插入。

關(guān)鍵字的插入是在最底層的某個(gè)非終端結(jié)點(diǎn)中添加一個(gè)關(guān)鍵字，若該結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)不超過(guò)m-1，則插入完成；否則，若該結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)已達(dá)到m個(gè)，這與B-樹(shù)定義不符，將引起結(jié)點(diǎn)的“分裂”。642．B-樹(shù)的運(yùn)算2)B-樹(shù)的插入若插入新數(shù)據(jù)后，結(jié)點(diǎn)關(guān)鍵字個(gè)數(shù)已達(dá)到m個(gè)，這與B-樹(shù)定義不符，將引起結(jié)點(diǎn)的“分裂”。分裂方法為：將結(jié)點(diǎn)中的關(guān)鍵字分成三部分，使得前后兩部分關(guān)鍵字個(gè)數(shù)均大于等于m/2-1，而中間部分只有一個(gè)關(guān)鍵字。前后兩部分成為兩個(gè)結(jié)點(diǎn)，中間部分的關(guān)鍵字將插入到父結(jié)點(diǎn)中。若中間部分關(guān)鍵字插入父結(jié)點(diǎn)后，父結(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù)超過(guò)m-1，則父結(jié)點(diǎn)繼續(xù)分裂，直到插入某個(gè)父結(jié)點(diǎn)，其關(guān)鍵字個(gè)數(shù)小于m。65在e結(jié)點(diǎn)中插入40，插入后e結(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù)為1<=2<=4，仍然符合B-樹(shù)定義。m/2-1<=n<=m-1此處m=466679.4散列技術(shù)1散列表的概念2散列函數(shù)的構(gòu)造3沖突解決方法4散列表上的計(jì)算5開(kāi)散列表和閉散列表的比較68靜態(tài)查找表和動(dòng)態(tài)查找表的特點(diǎn)是：要經(jīng)過(guò)一系列的關(guān)鍵字比較查找所需時(shí)間總是與比較次數(shù)有關(guān)。如果將記錄的存儲(chǔ)位置與它的關(guān)鍵字之間建立一個(gè)確定的關(guān)系H，使每個(gè)關(guān)鍵字和一個(gè)唯一的存儲(chǔ)位置對(duì)應(yīng)，在查找時(shí)，只需要根據(jù)對(duì)應(yīng)關(guān)系計(jì)算出給定的關(guān)鍵字值k對(duì)應(yīng)的值H(k)，就可以得到記錄的存儲(chǔ)位置這就是哈希表查找方法的基本思想。69若以下標(biāo)為000-999的順序表表示之。例如：為每年招收的1000名新生建立一張查找表，其關(guān)鍵字為學(xué)號(hào)，其值的范圍為xx000~xx999(前兩位為年份)。則查找過(guò)程可以簡(jiǎn)單進(jìn)行：取給定值（學(xué)號(hào)）的后三位，不需要經(jīng)過(guò)比較便可直接從順序表中找到待查關(guān)鍵字。70散列表的基本概念散列又稱(chēng)哈希（Hash）以結(jié)點(diǎn)的關(guān)鍵字k為自變量，通過(guò)一個(gè)確定的函數(shù)H，計(jì)算出對(duì)應(yīng)的函數(shù)值H(k)，作為結(jié)點(diǎn)的存儲(chǔ)位置，將結(jié)點(diǎn)存入H(k)所指的存儲(chǔ)位置上。將關(guān)鍵字值轉(zhuǎn)換成存儲(chǔ)地址的函數(shù):關(guān)鍵字為K的記錄所在位置為＝H(K)給定一個(gè)關(guān)鍵字K即可計(jì)算得到一個(gè)記錄位置71散列表的基本概念將關(guān)鍵字值轉(zhuǎn)換成存儲(chǔ)地址的函數(shù):關(guān)鍵字為K的記錄所在位置為＝H(K)給定一個(gè)關(guān)鍵字K即可計(jì)算得到一個(gè)記錄位置用哈希法存儲(chǔ)的線性表叫做哈希表。上述的H函數(shù)稱(chēng)為哈希函數(shù)。H(k)稱(chēng)為哈希地址。基于這種存儲(chǔ)結(jié)構(gòu)的查找稱(chēng)為哈希查找。72{Zhao,Qian,Sun,Li,Wu,Chen,Han}設(shè)哈希函數(shù)H(key)=首字母序/2例如：對(duì)于如下7個(gè)關(guān)鍵字261719122338ZhaoQianSunLiWuChenHan12345678910111213進(jìn)行查找時(shí)，只要根據(jù)給定關(guān)鍵字，然后利用H函數(shù)，即可計(jì)算得到關(guān)鍵字所在位置查找方便73{Zhao,Qian,Sun,Li,Wu,Chen,Han,zhou}設(shè)哈希函數(shù)H(key)=首字母序/2例如：對(duì)于如下7個(gè)關(guān)鍵字261719122338ZhaoQianSunLiWuChenHan12345678910111213同義詞:若H(k1)==H(k2),則K1，K2對(duì)于H稱(chēng)為同義詞此時(shí)H(k1)==H(k2),說(shuō)明K1和K2應(yīng)存入相同位置，此情況稱(chēng)為沖突74散列表的兩個(gè)問(wèn)題：1，如何構(gòu)造均勻的散列函數(shù)2，如何解決沖突75相乘取整法除余法平方取中法隨機(jī)數(shù)法2散列函數(shù)的構(gòu)造762.除余法構(gòu)造：取關(guān)鍵字被某個(gè)不大于哈希表表長(zhǎng)m的數(shù)p除后所得余數(shù)作哈希地址，即H(key)=key%p，pm772.除余法已知一組關(guān)鍵字為{19,14,23,01,68,20,84,27,55,11,10,79}則按哈希函數(shù)H（key）=key%13構(gòu)造所得的哈希表HT[0..14]。0123456789101112131419142301682084275511107978當(dāng)發(fā)生沖突時(shí)，在散列表中按某地址序列進(jìn)行探查，直到遇到開(kāi)放的地址為止（即該內(nèi)存單元未被占用）3沖突的處理方法：1）開(kāi)放定址法探查未被占用單元79閉散列表（開(kāi)放定址）基本思想所有元素存儲(chǔ)在散列表數(shù)組中經(jīng)散列函數(shù)計(jì)算出來(lái)的地址稱(chēng)為基地址每個(gè)鍵值K生成一個(gè)散列地址序列d0，d1…dm-1d0=H（K）,之后地址為后繼散列地址若插入K時(shí)，d0已占用則在按該序列探測(cè)找到第一個(gè)未被占用的地址存入，若全部地址被占用則散列表溢出探測(cè)下一存儲(chǔ)位置的策略：線性探測(cè)法二次探測(cè)法80對(duì)K鍵值計(jì)算H（K）=d設(shè)散列表容量為m，則后繼散列地址為：

d+1，d+2，…m-1，0，1，2，…d-1如此探測(cè)可能出現(xiàn)非同義詞爭(zhēng)奪同一個(gè)地址的現(xiàn)象，稱(chēng)為“堆積”，又稱(chēng)“二次聚集”線性探測(cè)法8101234563047523634設(shè)閉散列表容量為7（散列地址空間0..6），給定表（30，36，47，52，34），散列函數(shù)H（k）=kmod6，采用線性探測(cè)法解決沖突，要求：（7分）1）構(gòu)造散列表；

2）求查找數(shù)34需要的比較次數(shù)。H（30）=30mod6=0H（36）=36mod6=0H（47）=47mod6=5H（52）=52mod6=4H（34）=34mod6=4查找34時(shí)，首先計(jì)算H（34）=34mod6=4比較散列空間4位置比較散列空間5位置比較散列空間6位置查找成功共比較3次8201234566832255048H（25）=25mod7=4H（48）=48mod7=6H（32）=32mod7=4H（50）=50mod7=1H（68）=68mod7=5查找34時(shí)，首先計(jì)算H（68）=68mod6=5比較散列空間5位置比較散列空間6位置比較散列空間0位置查找成功共比較3次已知散列函數(shù)為H(key)=key%7，散列表長(zhǎng)度為7(散列地址空間為0..6)，待散列序列為：(25，48，32，50，68)。要求：(1)構(gòu)造一散列表，用線性探測(cè)法解決有關(guān)地址沖突；(2)若要用該散列表查找元素68，給出所需的比較次數(shù)。83對(duì)K鍵值計(jì)算d0

=

H（K）設(shè)散列表容量為m，則后繼散列地址為：

d1=（d0+12）modmd2=（d0-12）modmd3=（d0-22）modmd4=（d0-22）modm……………二次探測(cè)法84多重散列法公共溢出去法簡(jiǎn)單了解85開(kāi)散列表設(shè)有H（K）計(jì)算得到的地址范圍0..m-1設(shè)置一個(gè)“地址向量”

HP[m]每個(gè)HP[i]指向一個(gè)單鏈表該單鏈表中存放散列地址為i的同義詞，即該單鏈表稱(chēng)為一個(gè)同義詞子表

3沖突的處理方法：2）開(kāi)散列（鏈地址、拉鏈法）86地址向量和同義詞子表，此法也稱(chēng)“拉鏈法”012345678910111213141914230168208427551110798701234567891011121314191423已知一組關(guān)鍵字為{19,14,23,01,68,20,84,27,55,11,10,79}按哈希函數(shù)H（key）=key%13和開(kāi)散列法處理沖突構(gòu)造所得的哈希表HT[0..14]頭插法8801234567891011121314141923已知一組關(guān)鍵字為{19,14,23,01,68,20,84,27,55,11,10,79}按哈希函數(shù)H（key）=key%13和開(kāi)散列法處理沖突構(gòu)造所得的哈希表HT[0..14]016820頭插法89012345678910111213141923已知一組關(guān)鍵字為{19,14,23,01,68,20,84,27,55,11,10,79}按哈希函數(shù)H（key）=key%13和開(kāi)散列法處理沖突構(gòu)造所得的哈希表