《數(shù)據(jù)結(jié)構(C／C描述)》-第8章查找課件

1、第8章查找第8章查找8.1 基本概念 8.2 靜態(tài)查找8.3 動態(tài)查找8.4 哈希查找 8.1 基本概念 一、 何謂查找表 ？ 查找表是由同一類型的數(shù)據(jù)元素（或記錄）構成的集合。 由于“集合”中的數(shù)據(jù)元素之間存在著松散的關系，因此查找表是一種應用靈便的結(jié)構。8.1 基 本 概 念一、 何謂查找表 ？ 查找表是由同一類型的數(shù)據(jù)元二、 對查找表經(jīng)常進行的操作1. 查詢某個“特定的”數(shù)據(jù)元素是否在查找表中；2. 檢索某個“特定的”數(shù)據(jù)元素的各種屬性；3. 在查找表中插入一個數(shù)據(jù)元素；4. 從查找表中刪去某個數(shù)據(jù)元素。二、 對查找表經(jīng)常進行的操作1. 查詢某個“特定的”數(shù)據(jù)元素僅作查詢和檢索操作的查找

2、表。1. 靜態(tài)查找表有時在查詢之后，還需要將不在查找表中的數(shù)據(jù)元素插入到查找表中；或者，從查找表中刪除指定的數(shù)據(jù)元素。2. 動態(tài)查找表三、查找表的分類僅作查詢和檢索操作的查找表。1. 靜態(tài)查找表有時在查詢之是數(shù)據(jù)元素（或記錄）中某個數(shù)據(jù)項的值，用以標識（識別）一個數(shù)據(jù)元素（或記錄）。四、關鍵字 若此關鍵字可以識別惟一的一個記錄，則稱之謂“主關鍵字”。 若此關鍵字能識別若干記錄，則稱之謂“次關鍵字”。是數(shù)據(jù)元素（或記錄）中某個數(shù)據(jù)項的值，用以標識（識別）一例如：學生管理系統(tǒng)中，可將姓名作為關鍵字，也可將學號作為關鍵字。學號 姓名 專業(yè) 年齡 01 王洪 計算機 17 02 孫文 計算機 18 0

3、3 謝軍 計算機 18 04 李輝 計算機 20 05 沈福 計算機 25 06 余斌 計算機 19 07 鞏力 數(shù)學 17 08 王輝 數(shù)學 18例如：學生管理系統(tǒng)中，可將姓名作為關學號 姓名 根據(jù)給定的某個值，在查找表中確定一個其關鍵字等于給定值的數(shù)據(jù)元素（或記錄）的過程。五、查找 若查找表中存在這樣一個記錄，則稱查找成功，返回整個記錄的信息，或返回該記錄在查找表中的位置；否則稱查找不成功，返回空記錄或空指針。 根據(jù)給定的某個值，在查找表中確定一個其關鍵字等于給定值由于查找表中的數(shù)據(jù)元素之間不存在明顯的組織規(guī)律，因此不便于查找。 為了提高查找的效率， 需要在查找表的元素之間人為地 附加某種

4、確定的關系，即： 用另外一種結(jié)構來表示查找表。六、如何進行查找查找的方法取決于查找表的結(jié)構。由于查找表中的數(shù)據(jù)元素之間不存在明顯的組織規(guī)律，因此不便8.2靜 態(tài) 查 找 8.2靜 態(tài) 查 找 數(shù)據(jù)元素類型的定義為:typedef struct keyType key; / 關鍵字域 / 其它屬性域 ElemType ;數(shù)據(jù)元素類型的定義為:typedef struct 以順序表或線性鏈表表示靜態(tài)查找表的查找。8.2.1 順序查找順序表 以順序表或線性鏈表表示靜態(tài)查找表的查找。8.2.se_listii查找成功！查找失??！key = 64642137881992056456807513 0 1

5、2 3 4 5 6 7 8 9 10 11 se_listi60key = 64i2137881992056456807513 0 1 2 3 4 5 6 7 8 9 10 11 se_listii查找成功！查找失?。ey = 64642分析順序查找的時間性能。 定義： 查找算法的平均查找長度ASL 為確定記錄在查找表中的位置，需和給定值 進行比較的關鍵字個數(shù)的期望值 其中: n 為表長，Pi 為查找表中第 i 個記錄的概率 且 Ci為找到該記錄時，曾和給定值 比較過的關鍵字的個數(shù)分析順序查找的時間性能。 定義： 查找算法的平均查找順序表查找的平均查找長度為：對順序表而言，Ci = n-i+

6、1ASL = nP1 +(n-1)P2 + +2Pn-1+Pn在等概率查找的情況下，順序表查找的平均查找長度為：對順序表而言，Ci = n-i+ 上述順序查找表的查找算法簡單，但平均查找長度較大，特別不適用于表長較大的查找表。8.2.2 折半查找順序表 若以有序表表示靜態(tài)查找表，則查找過程可以折半進行。 上述順序查找表的查找算法簡單，bi_list 長度n例如， key = 64 的查找過程如下：lowhighmidlow mid high midlow 指示查找區(qū)間的下界;high 指示查找區(qū)間的上界;mid = (low+high)/2。bi_list 長度n例如， key = 64 的查

7、找過程如int binarysearch(elemtype bi_list,keytype key,int n)/在有序表bi_list1bi_listn中查找關鍵字為key的記錄int low,high,mid;low=1;high=n;while(low=high) mid=(low+high)/2;if(bi_listmid.key=key) break;/找到記錄else if(bi_listmid.keykey)low=mid+1;/在右半繼續(xù)查找 else high=mid-1;/在左半繼續(xù)查找if(low50 時，可得近似結(jié)果 假設 n=2h-1 并且查找概率相等 一般情況下8.

8、2.3 分塊查找（索引順序查找）在建立順序表的同時，建立一個索引。012345678910111213170821191431332225405261784621 040 578 10例如：索引順序表 = 索引表 + 順序表順序表索引8.2.3 分塊查找（索引順序查找）在建立順序表的同時，建索引順序表的查找過程： 1. 由索引確定記錄所在區(qū)間；2. 在順序表的某個區(qū)間內(nèi)進行查找?？梢?，索引順序查找的過程也是一個“縮小區(qū)間”的查找過程。索引順序表的查找過程： 1. 由索引確定記錄所在區(qū)間；2. 索引表最大關鍵字起始地址2212138920334244382448605874498653第1塊第2

9、塊第3塊224886例：2248861713特點：塊間有序 塊內(nèi)無序順序表索引表最大關鍵字起始地址2212138920334244388.3 動 態(tài) 查 找8.3 動 態(tài) 查 找8.3.1 二叉排序樹（二叉查找樹）1定義2查找算法3插入算法4刪除算法5查找性能的分析8.3.1 二叉排序樹（二叉查找樹）1定義2查找算法3（1）若它的左子樹不空，則左子樹上所有結(jié)點 的值均小于根結(jié)點的值；1定義： 二叉排序樹或者是一棵空樹；或者是具有如下特性的二叉樹：（3）它的左、右子樹也都分別是二叉排序樹。（2）若它的右子樹不空，則右子樹上所有結(jié)點 的值均大于根結(jié)點的值；（1）若它的左子樹不空，則左子樹上所有結(jié)點

10、1定義： 503080209010854035252388例如:是二叉排序樹。66不503080209010854035252388例如:是二叉 通常，取二叉鏈表作為二叉排序樹的存儲結(jié)構。typedef struct bsnode /定義二叉排序樹中的結(jié)點類型 keytype key;struct bsnode *lchild;struct bsnode *rchild;bsnodetype; 通常，取二叉鏈表作為二叉排序樹的存儲結(jié)構。2二叉排序樹的查找算法1. 若給定值等于根結(jié)點的關鍵字, 則查找成功；2. 若給定值小于根結(jié)點的關鍵字，則繼續(xù)在左子樹上進行查找；3. 若給定值大于根結(jié)點的關鍵

11、字，則繼續(xù)在右子樹上進行查找。否則:若二叉排序樹為空，則查找不成功；2二叉排序樹的查找算法1. 若給定值等于根結(jié)點的關鍵字, 50308020908540358832例如:二叉排序樹查找關鍵字= 50 ,505035 ,503040355090 ,50809095 ,50308020908540358832例如:二叉排序樹查找從上述查找過程可見，在查找過程中，生成了一條查找路徑: 從根結(jié)點出發(fā)，沿著左分支或右分支逐層向下直至關鍵字等于給定值的結(jié)點;或者 從根結(jié)點出發(fā)，沿著左分支或右分支逐層向下直至指針指向空樹為止。 查找成功 查找不成功從上述查找過程可見，在查找過程中，生成了一條查找路徑: 算

12、法8.5 用非遞歸算法描述二叉排序樹的查找 ：bsnodetype *bs_search(bsnodetype *bt,keytype key) bsnodetype *p=bt; /指針p指向根結(jié)點，搜索從根結(jié)點開始while (p!=NULL&p-key!=key) if(keykey) p=p-lchild; else p=p-rchild; return (p);算法8.5 用非遞歸算法描述二叉排序樹的查找 ：3二叉排序樹的插入算法若二叉排序樹為空樹，則新插入的結(jié)點為新的根結(jié)點；否則，新插入的結(jié)點必為一個新的葉子結(jié)點。其插入位置由查找過程得到。3二叉排序樹的插入算法若二叉排序樹為空樹，

13、則新插入的結(jié)點為二叉排序樹的插入算法（算法8.6）如下：void bs_insert (bsnodetype *bt , bsnodetype *pn) if(*bt=NULL) *bt=pn; /如果根結(jié)點為空，就把待插結(jié)點作為根結(jié)點 else if(*bt)-keypn-key) bs_insert(&(*bt)- lchild,pn) ; /如果待插結(jié)點的值小于根結(jié)點，就插入到左子樹中 else if(*bt)-keykey) bs_insert(&(*bt)- rchild,pn) ; /如果待插結(jié)點的值大于根結(jié)點，就插入到右子樹中二叉排序樹的插入算法（算法8.6）如下：（1）被刪除的

14、結(jié)點是葉子；（2）被刪除的結(jié)點只有左子樹或者只有右子樹（3）被刪除的結(jié)點既有左子樹，也有右子樹。4二叉排序樹的刪除算法可分 3 種情況討論： 和插入相反，刪除在查找成功之后進行，并且要求在刪除二叉排序樹上某個結(jié)點之后，仍然保持二叉排序樹的特性。（1）被刪除的結(jié)點是葉子；4二叉排序樹的刪除算法可分 3 （1）被刪除的結(jié)點是葉子結(jié)點其雙親結(jié)點中相應指針域的值改為“空”（2）被刪除的結(jié)點只有左子樹或者 只有右子樹 其雙親結(jié)點的相應指針域的值改為 “指向被刪除結(jié)點的左子樹或右子樹”。（3）被刪除的結(jié)點既有左子樹，也有右子樹以其前驅(qū)替代之，然后再刪除該前驅(qū)結(jié)點（1）被刪除的結(jié)點是葉子結(jié)點其雙親結(jié)點中相應

15、指針域的值改為“void bs_delete ( bsnodetype *bt, keytype key)bsnodetype *p,*q,*r,*s;p=NULL;q=*bt;while(q&(q-key!=key)p=q;if(keykey)q=q-lchild;elseq=q-rchild; /在二叉樹中查找關鍵字等于key的結(jié)點刪除算法描述如下： void bs_delete ( bsnodetype *if(q=NULL) return;/如果二叉樹中沒有該結(jié)點，則不進行刪除，直接返回if(q-lchild=NULL) s=q-rchild;else s=q-lchild;r=s;w

16、hile(r-rchild)r=r-rchild;r-rchild=q-rchild;/若被刪結(jié)點有左子樹，則在其左子樹中找到中序遍歷下的最后一個結(jié)點r if(q=NULL) return; if(p=NULL)*bt=s; /如果要刪除的結(jié)點是根結(jié)點，就令s為根結(jié)點else if(q=p-lchild)p-lchild=s;elsep-rchild=s;free(q); if(p=NULL) 若被刪結(jié)點沒有左子樹，則用其右孩子代替它（注意，右孩子可以為空）若被刪結(jié)點有左子樹，則在其左子樹中找到中序遍歷的最后一個結(jié)點r，把被刪結(jié)點的右子樹作為結(jié)點r的右子樹，并用被刪結(jié)點的左孩子代替被刪結(jié)點。若

17、被刪結(jié)點沒有左子樹，則用其右孩子代替它（注意，右孩子可以為注意：如果被刪結(jié)點是根結(jié)點，同樣適用上述方法，只不過要對根結(jié)點做調(diào)整，因為原根結(jié)點要被刪除，所以把取代根結(jié)點的結(jié)點作為新的根結(jié)點。注意：如果被刪結(jié)點是根結(jié)點，同樣適用上述方法，只不過要對根結(jié)5二叉排序樹的查找性能分析 對于每一棵特定的二叉排序樹，均可按照平均查找長度的定義來求它的 ASL 值，顯然，由值相同的 n 個關鍵字，構造所得的不同形態(tài)的各棵二叉排序樹的平均查找長 度的值不同，甚至可能差別很大。5二叉排序樹的查找性能分析 對于由關鍵字序列 3，1，2，5，4構造而得的二叉排序樹由關鍵字序列 1，2，3，4，5構造而得的二叉排序樹，

18、例如：2134535412ASL =（1+2+3+4+5）/ 5 = 3ASL =（1+2+3+2+3）/ 5= 2.2含n個結(jié)點的平均查找長度為：由關鍵字序列 3，1，2，5，4構造而得的二叉排序樹由關鍵字8.3.2 平衡二叉樹什么是平衡二叉樹(Balanced Binary Tree) ?平衡二叉樹是空樹,或者是具有以下性質(zhì)的二叉樹:它的左子樹和右子樹也都是平衡二叉樹并且左子樹和右子樹的深度之差的絕對值不超過1結(jié)點的平衡因子BF(Balance Factor)是左子樹的深度減去右子樹的深度,它只可能是-1,0,1平衡二叉樹(也稱AVL樹)的深度為O(log N)(其中N為結(jié)點個數(shù))它的平均

19、查找長度也是O(log N)8.3.2 平衡二叉樹什么是平衡二叉樹(Balanced 平衡二叉樹及平衡因子舉例-1100-110平衡的二叉樹1100平衡二叉樹及平衡因子舉例-1100-110平衡的二叉樹110不平衡的二叉樹-1000-210 2-101 00不平衡二叉樹及平衡因子舉例不平衡的二叉樹-1000-210 2-101 00不平衡二叉二叉排序樹轉(zhuǎn)成平衡樹示例設關鍵字序列為(13,24,37,90,53) 013-113 024 037 013-213-124 024 037 053 013 013 037 090 053-124 190-237-224(a)(b)(c)(d)(e)(f

20、)(g)(h)2413375390二叉排序樹轉(zhuǎn)成平衡樹示例設關鍵字序列為(13,24,37二叉排序樹轉(zhuǎn)成平衡樹失去平衡后進行調(diào)整的4種情況(1)單向右旋平衡處理當在左子樹上插入左結(jié)點,使平衡因子由1增至2時(2)單向左旋平衡處理(上例從圖(d)到圖(e)當在右子樹上插入右結(jié)點,使平衡因子由-1增至-2時(3)雙向旋轉(zhuǎn)(先左后右)平衡處理當在左子樹上插入右結(jié)點,使平衡因子由1增至2時(4)雙向旋轉(zhuǎn)(先右后左)平衡處理當在右子樹上插入左結(jié)點,使平衡因子由-1增至-2時(例如上例從圖(f)右旋到圖(g)再左旋到圖(h)二叉排序樹轉(zhuǎn)成平衡樹失去平衡后進行調(diào)整的4種情況(1)單向 B-樹是一種多路平衡查

21、找樹。它適合在磁盤等直接存取設備上組織動態(tài)的查找表。 一棵m階的B_樹，或為空樹，或為滿足下列特性的m叉樹：（1）所有的非終端結(jié)點的結(jié)構如下：8.3.3 B_ 樹和B樹nP0K1P1K2P2KiPiKnPn一、 B_ 樹 B-樹是一種多路平衡查找樹。它適合在磁盤等直接存取設其中： K1，K2，Kn為n個按從小到大順序排列的關鍵字； P0，P1，P2，Pn為（n+1）個指針，用于指向該結(jié)點的（n+l）棵子樹，P0所指向的子樹中的所有關鍵字的值均小于K1；Pn所指向的子樹中的所有關鍵字的值均大于Kn；Pi（1in-1）所指向的子樹中的所有關鍵字的值均大于Ki且小于Ki+1； n（nm-1）為結(jié)點中

22、關鍵字的個數(shù)，所以子樹個數(shù)為（n+1）。數(shù)據(jù)結(jié)構(CC描述)-第8章查找課件（2）樹中每個結(jié)點至多有m棵子樹。（3）若根結(jié)點不為葉子結(jié)點，則它至少有兩棵子樹。（4）除根之外的所有非終端結(jié)點至少有棵子樹。 （5）所有葉子結(jié)點在同一個層次上，且不含有任何信息（可以看作外部結(jié)點或查找失敗的結(jié)點，實際上這些結(jié)點不存在，指向這些結(jié)點的指針為空）。（2）樹中每個結(jié)點至多有m棵子樹。15013027090125235401553758085195abcdefghB_樹示例150130270901252354015537580851 B+樹是B-樹的一種變形樹。一棵m階的B+樹滿足下列條件：（1）每個結(jié)點至多

23、有m棵子樹。（2）根結(jié)點或者沒有子樹或者至少有兩棵子樹。（3）除了根結(jié)點以外，每個分支結(jié)點至少有 棵子樹。（4）樹葉都在最底層，包含了所有的關鍵字以及指向相應記錄的指針，而且按關鍵字的大小順序鏈接。二、B樹二、B樹（5）有n棵子樹的分支結(jié)點中含有n個關鍵字，而且每個關鍵字都不小于對應子樹中最大的關鍵字。B+樹與B-樹的差異在于：（1）B+樹中，有n棵子樹的結(jié)點中含有n個關鍵字；而B-樹中有n+1棵子樹的結(jié)點中含有n個關鍵字。（2）B+樹中所有的葉子結(jié)點包含了全部關鍵字的信息，以及指向含這些關鍵字記錄的指針，且葉子結(jié)點本身依關鍵字的大小從小到大順序鏈接（3）所有的非終端結(jié)點可以看成是索引部分，結(jié)

24、點中僅含有其子樹中最大（或最?。┑年P鍵字。（5）有n棵子樹的分支結(jié)點中含有n個關鍵字，而且每個關鍵字都a30 38 4065 75 8025 304055 6570 75bdcefg80hroot38i40 65sqtB+樹示例a30 38 4065 75 8025 30405 一、什么是哈希表？二、哈希函數(shù)的構造方法三、處理沖突的方法 四、哈希表的查找8.4 哈 希 表 一、什么是哈希表？二、哈希函數(shù)的構造方法三、處理沖突的方法 以上兩節(jié)討論的表示查找表的各種結(jié)構的共同特點：記錄在表中的位置和它的關鍵字之間不存在一個確定的關系，一、什么是哈希表？ 查找的過程為給定值依次和關鍵字集合中各個關鍵

25、字進行比較， 查找的效率取決于和給定值進行比較的關鍵字個數(shù)。 以上兩節(jié)討論的表示查找表的各種結(jié)構的共同特點 用這類方法表示的查找表，其平均查找長度ASL都不為零。 不同的表示方法，其差別僅在于關鍵字和給定值進行比較的順序不同。 用這類方法表示的查找表，其平均查找長度ASL 只有一個辦法：預先知道所查關鍵字在表中的位置。 對于頻繁使用的查找表，希望 ASL = 0。 即，要求：記錄在表中位置和其關鍵字之間存在一種確定的關系。 只有一個辦法：預先知道所查關鍵字在表中的位置但是，對于動態(tài)查找表而言， 因此在一般情況下，需在關鍵字與記錄在表中的存儲位置之間建立一個函數(shù)關系，以 H(key) 作為關鍵字

26、為 key 的記錄在表中的位置，通常稱這個函數(shù) H (key) 為哈希函數(shù)。(1) 表長不確定；(2) 在設計查找表時，只知道關鍵字所 屬范圍，而不知道確切的關鍵字。但是，對于動態(tài)查找表而言， 因此在一般情況下，哈希表的定義: 根據(jù)設定的哈希函數(shù) H(key) 和所選中的處理沖突的方法，將一組關鍵字映象到一個有限的、地址連續(xù)的地址集 (區(qū)間) 上，并以關鍵字在地址集中的“象”作為相應記錄在表中的存儲位置，如此構造所得的查找表稱之為“哈希表”。哈希表的定義: 根據(jù)設定的哈希函數(shù) H(key二、構造哈希函數(shù)的方法 對數(shù)字的關鍵字可有下列構造方法:1. 直接定址法3. 平方取中法5. 除留余數(shù)法4.

27、 折疊法6. 隨機數(shù)法2. 數(shù)字分析法二、構造哈希函數(shù)的方法 對數(shù)字的關鍵字可有下列構造方法:哈希函數(shù)為關鍵字的線性函數(shù) H(key) = key 或者 H(key) = a key + b1. 直接定址法此法僅適合于：地址集合的大小 = = 關鍵字集合的大小哈希函數(shù)為關鍵字的線性函數(shù)1. 直接定址法此法僅適合于：5. 除留余數(shù)法 設定哈希函數(shù)為: H(key) = key MOD p 其中： pm (表長) 并且 p 應為不大于 m 的素數(shù) 5. 除留余數(shù)法 設定哈希函數(shù)為: 實際造表時，采用何種構造哈希函數(shù)的方法取決于建表的關鍵字集合的情況(包括關鍵字的范圍和形態(tài))，總的原則是使產(chǎn)生沖突的可能性降到盡可能地小。 實際造表