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

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

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

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

n個結(jié)點的完全二叉樹深度一樣18二分查找的平均查找長度：

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

則深度為1的1個結(jié)點

深度為2的2個

深度為3的4個

深度為k的2k-1個

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

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

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

40815

530

101020119

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

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

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

d+1，d+2，…m-1，0，1，2，…d-1如此探測可能出現(xiàn)非同義詞爭奪同一個地址的現(xiàn)象，稱為“堆積”，又稱“二次聚集”線性探測法8101234563047523634設(shè)閉散列表容量為7（散列地址空間0..6），給定表（30，36，47，52，34），散列函數(shù)H（k）=kmod6，采用線性探測法解決沖突，要求：（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時，首先計算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時，首先計算H（68）=68mod6=5比較散列空間5位置比較散列空間6位置比較散列空間0位置查找成功共比較3次已知散列函數(shù)為H(key)=key%7，散列表長度為7(散列地址空間為0..6)，待散列序列為：(25，48，32，50，68)。要求：(1)構(gòu)造一散列表，用線性探測法解決有關(guān)地址沖突；(2)若要用該散列表查找元素68，給出所需的比較次數(shù)。83對K鍵值計算d0

=

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

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

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

3沖突的處理方法：2）開散列（鏈地址、拉鏈法）86地址向量和同義詞子表，此法也稱“拉鏈法”012345678910111213141914230168208427551110798701234567891011121314191423已知一組關(guān)鍵字為{19,14,23,01,68,20,84,27,55,11,10,79}按哈希函數(shù)H（key）=key%13和開散列法處理沖突構(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和開散列法處理沖突構(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和開散列法處理沖突構(gòu)造所得的哈希表