1、第七章第七章 查查 找找數據結構與數據結構與STL第七章第七章 查找查找學習內容：學習內容：1. 概述概述 2. 線性表的查找技術線性表的查找技術 3. 樹表的查找技術樹表的查找技術 4. 散列表的查找技術散列表的查找技術5. 查找的應用查找的應用6. STL中的相關模版類中的相關模版類2數據結構與數據結構與STL1. 概述概述2021-7-81.概述概述 基本概念基本概念關鍵碼關鍵碼 用以標識一個記錄的某個數據項。如果該用以標識一個記錄的某個數據項。如果該關鍵碼可以唯一的標識一條記錄，稱為主關鍵關鍵碼可以唯一的標識一條記錄，稱為主關鍵碼；反之為次關鍵碼。碼；反之為次關鍵碼。 2021-7-8

2、3數據結構與數據結構與STL1.概述概述 查找查找 在具有相同類型的記錄集中找出滿足給定條件在具有相同類型的記錄集中找出滿足給定條件的記錄。的記錄。 查找結果查找結果 在查找集中找到匹配的記錄，稱為查找成功；在查找集中找到匹配的記錄，稱為查找成功；否則，稱為查找不成功。否則，稱為查找不成功。一般情況下，查找需要返回記錄的位置。一般情況下，查找需要返回記錄的位置。2021-7-84數據結構與數據結構與STL1.概述概述 靜態查找靜態查找 不涉及插入和刪除操作的查找不涉及插入和刪除操作的查找 動態查找動態查找 有時在查詢之后，還需要將有時在查詢之后，還需要將“查詢查詢”結果為結果為“不在查找表中不

3、在查找表中”的數據元素插入到查找表中；的數據元素插入到查找表中；或者，從查找表中刪除其或者，從查找表中刪除其“查詢查詢”結果為結果為“在在查找表中查找表中”的數據元素。的數據元素。 查找結構查找結構 為了提高查找效率，專門為查找操作設置的數為了提高查找效率，專門為查找操作設置的數據結構。據結構。2021-7-85數據結構與數據結構與STL1.概述概述 本章討論的查找結構本章討論的查找結構 ： 線性表：適用于靜態查找，主要采用順序查線性表：適用于靜態查找，主要采用順序查找技術、折半查找技術；找技術、折半查找技術； 樹表：適用于動態查找，主要采用二叉排序樹表：適用于動態查找，主要采用二叉排序樹的查

4、找技術；樹的查找技術； 散列表：靜態查找和動態查找均適用，主要散列表：靜態查找和動態查找均適用，主要采用散列技術。采用散列技術。2021-7-86數據結構與數據結構與STL2 查找算法的性能查找算法的性能 如何評價一個查找算法的優劣？如何評價一個查找算法的優劣？ 查找算法中最基本的操作是：關鍵碼和給定值查找算法中最基本的操作是：關鍵碼和給定值的比較；的比較； 比較次數越少則算法的性能越好；比較次數越少則算法的性能越好； 使用平均查找長度（使用平均查找長度（ASL）評價一個算法。）評價一個算法。2021-7-87數據結構與數據結構與STL2 查找算法的性能查找算法的性能niiiCPASL1202

5、1-7-88 其中其中: n 為表長，為表長， Pi 為查找表中第為查找表中第i個記錄的概率個記錄的概率 Ci 為找到該記錄時，曾和給定值比為找到該記錄時，曾和給定值比較過的關鍵字的個數較過的關鍵字的個數數據結構與數據結構與STL第七章第七章 查找查找學習內容：學習內容：1. 概述概述 2. 線性表的查找技術線性表的查找技術 3. 樹表的查找技術樹表的查找技術 4. 散列表的查找技術散列表的查找技術5. 查找的應用查找的應用6. STL中的相關模版類中的相關模版類9數據結構與數據結構與STL2. 線性表的查找技術線性表的查找技術順序查找順序查找 已知有已知有n個整數的序列，查找指定數值個整數的

6、序列，查找指定數值key是否在是否在該序列中，如果存在，找出該數值在序列中的位該序列中，如果存在，找出該數值在序列中的位置。置。2021-7-810數據結構與數據結構與STL算法實現算法實現int search(int a, int n, int key) for (int i=0; inext; j+;p = first-next; j=1;p數據結構與數據結構與STL順序查找（單鏈表）順序查找（單鏈表）template int SeqSearch(LinkList A, T key) Node *p=A.first-next; int j=1; while (p!=NULL & p-dat

7、a!=key) p= p-next; j+; if (p=NULL) return 0; else return j;2021-7-818數據結構與數據結構與STL2. 折半查找算法折半查找算法 折半查找適用于有序表。折半查找適用于有序表。 基本思想：基本思想：先確定待查記錄所在的范圍（區間），然后逐步先確定待查記錄所在的范圍（區間），然后逐步縮小范圍直到找到或找不到該記錄為止。縮小范圍直到找到或找不到該記錄為止。2021-7-819數據結構與數據結構與STL2. 折半查找算法折半查找算法例如例如: key = 64 的查找過程如下的查找過程如下2021-7-82005 13 19 21 37

8、 56 64 75 80 88 92 0 1 2 3 4 5 6 7 8 9 10 11 anlowhighmidlow mid high midlow 指示查找區間的下界指示查找區間的下界; ;high 指示查找區間的上界指示查找區間的上界; ;mid = (low+high)/2數據結構與數據結構與STL2. 折半查找算法折半查找算法int Search_Bin(int a, int n, int key) int low=1; int high=n; while(low=high) mid = (low+high)/2; if(key=amid) return mid; else if

9、(key50 時，可得近似結果時，可得近似結果1) 1(log2nASLbs假設假設 n=2h-1 并且查找概率相等并且查找概率相等, 則則數據結構與數據結構與STL性能分析：性能分析：1. 查找不成功查找不成功 假設假設 n=2h-1 并且查找概率相等并且查找概率相等, 則則 ASL = h+1 = log2n+12021-7-824數據結構與數據結構與STL2 折半查找的遞歸算法折半查找的遞歸算法int BinSearch (int r, int low, int high, int k) if(lowhigh) int mid = (low+high)/2; if(rmin=k) ret

10、urn mid; else if(rmink) return BinSearch(r, low, mid-1,k); else return BinSearch(r, mid+1, high,k); 2021-7-825數據結構與數據結構與STL3.分塊查找分塊查找分塊查找又稱索引查找，它是一種性能介于順序分塊查找又稱索引查找，它是一種性能介于順序查找和折半查找之間的查找方法。它要求在建立查找和折半查找之間的查找方法。它要求在建立順序表的同時，建立一個索引表。順序表的同時，建立一個索引表。2021-7-82617 08 21 19 14 31 33 22 25 40 52 61 78 4621

11、 040 578 10012345678910 11 12 13基本表基本表索引表索引表數據結構與數據結構與STL3.分塊查找分塊查找基本思想基本思想首先根據索引表確定待查記錄的區間；首先根據索引表確定待查記錄的區間；然后在確定的主表區間內采用順序查找。然后在確定的主表區間內采用順序查找。2021-7-827數據結構與數據結構與STL3.分塊查找分塊查找性能分析性能分析一般情況下，將長度為一般情況下，將長度為n的主表分成的主表分成b塊，每塊含有塊，每塊含有s條條記錄，即記錄，即bn/s;假設查找概率相等，則每塊查找的概率假設查找概率相等，則每塊查找的概率為為1/b,塊中每條記錄查找的概率為塊中

12、每條記錄查找的概率為1/s。索引表采用順序查找索引表采用順序查找索引采用折半查找索引采用折半查找2021-7-828數據結構與數據結構與STL3.分塊查找分塊查找優點優點插入或刪除比較容易插入或刪除比較容易缺點缺點輔助數組輔助數組初始表分塊排序初始表分塊排序2021-7-829數據結構與數據結構與STL第七章第七章 查找查找學習內容：學習內容：1. 概述概述 2. 線性表的查找技術線性表的查找技術 3. 樹表的查找技術樹表的查找技術 4. 散列表的查找技術散列表的查找技術5. 查找的應用查找的應用6. STL中的相關模版類中的相關模版類30數據結構與數據結構與STL3. 樹表的查找技術樹表的查

13、找技術樹表的查找技術樹表的查找技術主要內容主要內容二叉排序樹二叉排序樹平衡二叉樹平衡二叉樹2021-7-831二叉排序樹二叉排序樹主要內容主要內容 1二叉排序樹的定義二叉排序樹的定義 2二叉排序樹的建立二叉排序樹的建立 3二叉排序樹的查找二叉排序樹的查找 4二叉排序樹的刪除二叉排序樹的刪除2021-7-832數據結構與數據結構與STL1二叉排序樹的定義二叉排序樹的定義 定義：定義： 二叉排序樹或者是一棵空樹；或者是具有如下特二叉排序樹或者是一棵空樹；或者是具有如下特性的二叉樹：性的二叉樹： 1. 若它的左子樹不空，則左子樹上所有結點的若它的左子樹不空，則左子樹上所有結點的值均小于根結點的值；值

14、均小于根結點的值； 2. 若它的右子樹不空，則右子樹上所有結點的若它的右子樹不空，則右子樹上所有結點的值均大于根結點的值；值均大于根結點的值； 3. 它的左它的左. 右子樹也都分別是二叉排序樹。右子樹也都分別是二叉排序樹。2021-7-833數據結構與數據結構與STL二叉排序樹二叉排序樹2021-7-83450308020901085403525238866是二叉排序樹是二叉排序樹不不數據結構與數據結構與STL 建立二叉排序樹建立二叉排序樹 例：例： 63, 90, 70, 55, 67, 42, 982021-7-835639063709063557090636755709063426755

15、70906398426755709063數據結構與數據結構與STL2二叉排序樹的建立二叉排序樹的建立采用二叉鏈表作為二叉排序樹的存儲結構采用二叉鏈表作為二叉排序樹的存儲結構template class Nodepublic: T data;Node *lch;Node *rch;Node(): lch(NULL), rch(NULL) ;2021-7-836數據結構與數據結構與STL2二叉排序樹的插入二叉排序樹的插入2021-7-837PKey = 48RRPRKey = 22RPRPRPRPR30201040352523數據結構與數據結構與STL2二叉排序樹的插入二叉排序樹的插入如何構造一棵

16、二叉排序樹？如何構造一棵二叉排序樹？ 若當前結點若當前結點=NULL，則直接插入；，則直接插入； 否則將給定值與當前結點進行比較否則將給定值與當前結點進行比較 若若當前結點，與其左孩子比較當前結點，與其左孩子比較 否則，與其右孩子比較否則，與其右孩子比較 反復執行，直到插入。反復執行，直到插入。2021-7-838數據結構與數據結構與STL2二叉排序樹的插入二叉排序樹的插入void InsertBST(BiNode *r, BiNode*s) if ( r = NULL) r = s; else if (s-datadata ) InsertBST(r-lchild, s); else Ins

17、ertBST(r-rchild, s);2021-7-839數據結構與數據結構與STL2二叉排序樹的建立二叉排序樹的建立void Create(BiNode *R, int r, int n) for (int i=0; in; i+) BiNode * s=new BiNode ; s-data=ri; s-lch=s-rch=NULL; InsertBST(R, s); 2021-7-840數據結構與數據結構與STL3二叉排序樹的查找二叉排序樹的查找template Node* Search(Node *R, T key) if(R=NULL) return NULL; if(key =R

18、-data) return R; else if (keydata) return Search(R-lch,key); else return Search(R-rch,key);2021-7-841數據結構與數據結構與STL4二叉排序樹的刪除二叉排序樹的刪除 刪除在查找成功之后進行，并且要求在刪除二叉刪除在查找成功之后進行，并且要求在刪除二叉排序樹上某個結點之后，仍然保持二叉排序樹的排序樹上某個結點之后，仍然保持二叉排序樹的特性。特性。可分三種情況討論：可分三種情況討論：a. 被刪除的結點是葉子；被刪除的結點是葉子；b. 被刪除的結點只有左子樹或者只有右子樹；被刪除的結點只有左子樹或者只有

19、右子樹；c. 被刪除的結點既有左子樹，也有右子樹。被刪除的結點既有左子樹，也有右子樹。2021-7-842數據結構與數據結構與STLa. 被刪除的結點是葉子被刪除的結點是葉子2021-7-84350308020908540358832被刪關鍵字被刪關鍵字 = 20 88數據結構與數據結構與STLb. 被刪除的結點只有左子樹或右子樹被刪除的結點只有左子樹或右子樹2021-7-84450308020908540358832被刪關鍵字被刪關鍵字 = 40 80數據結構與數據結構與STLc.被刪除的結點有左子樹，也有右子樹被刪除的結點有左子樹，也有右子樹算法分析：算法分析： 1. 中序遍歷得到被刪除結

20、點中序遍歷得到被刪除結點p的前驅結點的前驅結點q是是p的的左子樹的最右下結點，則左子樹的最右下結點，則q必為單分支結點，或葉必為單分支結點，或葉結點結點(其右指針為空其右指針為空) 2. 將將q的值賦給的值賦給p的值域，的值域， 3. 將刪除將刪除p的操作轉換為刪除的操作轉換為刪除q的操作的操作2021-7-845數據結構與數據結構與STLc.被刪除的結點有左子樹，也有右子樹被刪除的結點有左子樹，也有右子樹2021-7-846503080209085403588324040被刪結點被刪結點前驅結點前驅結點被刪關鍵字被刪關鍵字 = 50數據結構與數據結構與STL例子：分別刪除例子：分別刪除20.

21、 302021-7-847503080209010854035252388數據結構與數據結構與STL5二叉排序樹的刪除二叉排序樹的刪除 template bool DeleteBST(Node *&R,T key) if(R=NULL) return false;elseif(key = R-data) Delete(R);else if (keydata) DeleteBST(R-lch,key); else DeleteBST(R-rch,key);return true; 2021-7-848數據結構與數據結構與STL5二叉排序樹的刪除二叉排序樹的刪除 template void Del

22、ete(Node *&R) Node *q,*s; if(R-lch=NULL) q=R; R=R-rch; delete q; else if (R-rch=NULL) q=R; R=R-lch; delete q; else /s是是R的前驅，的前驅， q是是s的雙親的雙親q = R; s = R-lch;while(s-rch!=NULL) q = s; s = s-rch;R-data = s-data;if(q!=R) q-rch=s-lch;else R-lch=s-lch; /q=R表示表示s為為R的左孩子的左孩子delete s; 2021-7-849數據結構與數據結構與STL

23、二叉排序樹性能分析二叉排序樹性能分析 對于每一棵特定的二叉排序樹，均可按對于每一棵特定的二叉排序樹，均可按照平均查找長度的定義來求它的照平均查找長度的定義來求它的 ASL 值，顯值，顯然，由值相同的然，由值相同的 n 個關鍵字，構造所得的不個關鍵字，構造所得的不同形態的各棵二叉排序樹的平均查找長同形態的各棵二叉排序樹的平均查找長 度的度的值不同，甚至可能差別很大。值不同，甚至可能差別很大。 2021-7-850數據結構與數據結構與STL二叉排序樹性能分析二叉排序樹性能分析2021-7-85121345 由關鍵字序列由關鍵字序列 1，2，3，4，535412由關鍵字序列由關鍵字序列 3，1，2，

24、5，4ASL =（1+2+3+4+5）/ 5 = 3ASL =（1+2+3+2+3）/ 5 = 2.2數據結構與數據結構與STL二叉排序樹性能分析二叉排序樹性能分析最壞的情況最壞的情況 排序二叉樹退化成單支順序查找排序二叉樹退化成單支順序查找ASL = (n+1)/2最優化情況最優化情況 排序二叉樹近似為為折半查找的判定樹排序二叉樹近似為為折半查找的判定樹ASL = log2(n+1)-12021-7-852數據結構與數據結構與STL平衡二叉樹平衡二叉樹主要內容主要內容 1. 定義定義 2. 構造平衡二叉樹構造平衡二叉樹 3. 性能分析性能分析53數據結構與數據結構與STL平衡二叉樹平衡二叉樹

25、定義定義二叉平衡樹或者是一棵空樹；或者是具有如下二叉平衡樹或者是一棵空樹；或者是具有如下特性的二叉樹：特性的二叉樹： 1. 它的左它的左. 右子樹都是平衡二叉樹；右子樹都是平衡二叉樹；2. 它的左它的左. 右子樹的高度之差的絕對值小于右子樹的高度之差的絕對值小于1。注意注意 本章討論的平衡二叉樹是指平衡的二叉排本章討論的平衡二叉樹是指平衡的二叉排序樹。序樹。54數據結構與數據結構與STL1. 平衡二叉樹平衡二叉樹556482648215是平衡樹是平衡樹不是平衡樹不是平衡樹數據結構與數據結構與STL2021-7-8平衡二叉樹平衡二叉樹平衡因子平衡因子結點的平衡因子結點的平衡因子=左子樹高度左子樹

26、高度-右子樹高度右子樹高度平衡二叉樹的平衡因子為平衡二叉樹的平衡因子為-1. 0. 1。 如果在建立排序二叉樹的同時，保證其為平衡二如果在建立排序二叉樹的同時，保證其為平衡二叉樹，則可避免查找的時間復雜度由叉樹，則可避免查找的時間復雜度由O(logn)退化退化成成O(n)。 56 數據結構與數據結構與STL2021-7-8第七章第七章 查找查找學習內容：學習內容：1. 概述概述 2. 線性表的查找技術線性表的查找技術 3. 樹表的查找技術樹表的查找技術 4. 散列表的查找技術散列表的查找技術5. 查找的應用查找的應用6. STL中的相關模版類中的相關模版類57數據結構與數據結構與STL4. 散

27、列表的查找技術散列表的查找技術2021-7-8散列的查找技術散列的查找技術主要內容主要內容 1什么是散列技術？什么是散列技術？ 2散列函數的設計散列函數的設計2021-7-858數據結構與數據結構與STL1什么是散列技術？什么是散列技術？什么是查找？什么是查找？確定關鍵碼確定關鍵碼=給定值的記錄在集合中的查找集合中給定值的記錄在集合中的查找集合中的存儲位置。的存儲位置。由于存儲位置與關鍵碼之間不存在確定的對應關由于存儲位置與關鍵碼之間不存在確定的對應關系，因此，查找時必須通過一系列與關鍵碼的比系，因此，查找時必須通過一系列與關鍵碼的比較。較。順序查找、二分查找、二叉排序樹、順序查找、二分查找、

28、二叉排序樹、B-B-樹查找。樹查找。散列技術，改善時間復雜度，散列技術，改善時間復雜度，由由O(O(loglog2 2(n)(n) )+ +O O(1)(1)O O(1)(1)2021-7-859 不通過比較，直接定不通過比較，直接定位待查記錄的存儲位置？位待查記錄的存儲位置？數據結構與數據結構與STL2021-7-860使用散列技術，使結點在表中的位置和使用散列技術，使結點在表中的位置和該結點的關鍵字存在確定關系。該結點的關鍵字存在確定關系。 ( (理想情況理想情況) )不進行比較。不進行比較。影碟出租商店的例子影碟出租商店的例子: :1 1萬張影碟，用萬張影碟，用7 7位電話號碼做關鍵字。

29、位電話號碼做關鍵字。 7 7位表示位表示1 1千萬個編碼。千萬個編碼。最多的情況最多的情況1 1萬個記錄位置足夠。萬個記錄位置足夠。如何將如何將7 7位號碼影射到位號碼影射到1 1萬個地址萬個地址1什么是散列技術？什么是散列技術？理想情況理想情況 在記錄的存儲位置和其關鍵碼之間建立一個確在記錄的存儲位置和其關鍵碼之間建立一個確定的對應關系定的對應關系H，使得每個關鍵碼，使得每個關鍵碼key和唯一的一和唯一的一個存儲位置個存儲位置H(key)對應。對應。 key 關鍵碼關鍵碼 H(key) 存儲位置存儲位置 這就是散列技術，采用散列技術將記錄存儲在這就是散列技術，采用散列技術將記錄存儲在一塊連續

30、的存儲空間中，就是散列表。一塊連續的存儲空間中，就是散列表。2021-7-861數據結構與數據結構與STL1什么是散列技術？什么是散列技術？散列過程散列過程 1）存儲記錄）存儲記錄通過通過H(key)計算記錄的散列地址，并按此地址存計算記錄的散列地址，并按此地址存儲記錄儲記錄 2）查找記錄）查找記錄通過同樣的通過同樣的H(key)計算記錄的散列地址，按此地計算記錄的散列地址，按此地址訪問該記錄。址訪問該記錄。 散列不能表達記錄之間的邏輯關系，所以是散列不能表達記錄之間的邏輯關系，所以是不完整的存儲結構，主要面向查找的存儲結構不完整的存儲結構，主要面向查找的存儲結構2021-7-862數據結構與

31、數據結構與STL1什么是散列技術？什么是散列技術？ 1).散列函數的設計散列函數的設計 理想情況：理想情況： key 關鍵碼關鍵碼 H(key) 存儲位置存儲位置 實際情況：實際情況： key1 != key2 但但 H(key1) = H(key2) 2).沖突處理沖突處理2021-7-863數據結構與數據結構與STL1). 散列函數的設計散列函數的設計常用的五種方法：常用的五種方法：(1) 直接定址法直接定址法(2) 除留余數法除留余數法(3) 數字分析法數字分析法(4) 平方取中法平方取中法(5) 折疊法折疊法2021-7-864數據結構與數據結構與STL(1) 直接定址法直接定址法散列

32、散列函數：函數：h(key) = a*key + b特點：特點： 計算簡單，沒有沖突；適合于關鍵碼分布比較連計算簡單，沒有沖突；適合于關鍵碼分布比較連續的情況；否則空間浪費較多。續的情況；否則空間浪費較多。2021-7-865人口統計表：人口統計表：數據結構與數據結構與STL(2) 除留余數法除留余數法散列函數：散列函數：h(key) = key % p (pm)m為散列表的長度，為散列表的長度，p最好為素數或不包含小于最好為素數或不包含小于20的質因數的合數。的質因數的合數。特點：特點： 計算簡單，使用范圍廣計算簡單，使用范圍廣。2021-7-866數據結構與數據結構與STL(2) 除留余數

33、法除留余數法關鍵碼關鍵碼 25, 18, 23, 4, 57, 89, 19, 37, 60選擇選擇P值值 2021-7-867哈希函數：哈希函數： h(key) = key % 13數據結構與數據結構與STL(3) 數字分析法數字分析法假設關鍵碼集合中的每個關鍵碼都是由假設關鍵碼集合中的每個關鍵碼都是由 s 位數字位數字組成組成 (u1, u2, , us)，分析每位數字的分布情況，分析每位數字的分布情況，從中提取分布均勻的若干位或它們的組合作為地從中提取分布均勻的若干位或它們的組合作為地址。址。特點特點適合于所有關鍵碼已知，并對每一位的取值分布適合于所有關鍵碼已知，并對每一位的取值分布有所

34、分析。有所分析。2021-7-868數據結構與數據結構與STL(4) 平方取中法平方取中法將關鍵碼平方后，取中間幾位作為存儲地址。求將關鍵碼平方后，取中間幾位作為存儲地址。求“關鍵字的平方值關鍵字的平方值” 的目的是的目的是“擴大差別擴大差別” ，同，同時平方值的中間各位又能受到整個關鍵字中各位時平方值的中間各位又能受到整個關鍵字中各位的影響。的影響。特點特點事先不知道關鍵碼的分布且關鍵碼的位數不是很事先不知道關鍵碼的分布且關鍵碼的位數不是很大。大。2021-7-869數據結構與數據結構與STL(5) 折疊法折疊法 將關鍵碼從左到右分割成位數相等的若干部分，將關鍵碼從左到右分割成位數相等的若干

35、部分，然后取它們的疊加和為哈希地址。有兩種疊加然后取它們的疊加和為哈希地址。有兩種疊加處理的方法：處理的方法：移位疊加：將各部分的最后一位對齊相加移位疊加：將各部分的最后一位對齊相加間界疊加：從一端到另一端沿各部分分界來回折間界疊加：從一端到另一端沿各部分分界來回折疊后，最后一位對齊相加疊后，最后一位對齊相加特點特點適用于關鍵字的數字位數特別多。適用于關鍵字的數字位數特別多。2021-7-870數據結構與數據結構與STL例：例： 設關鍵碼設關鍵碼 key= 25346358705，散列表表長為，散列表表長為3位，則可對關鍵碼進行三位一分割，將關鍵位，則可對關鍵碼進行三位一分割，將關鍵碼分割如下

36、碼分割如下 253 463 587 05 2021-7-871 2 5 3 4 6 3 5 8 7+ 0 5 1 3 0 8移位疊加移位疊加 2 5 3 3 6 4 5 8 7 + 5 0 1 2 5 4間界疊加間界疊加數據結構與數據結構與STL2).處理沖突的方法處理沖突的方法“處理沖突處理沖突”的實際含義是：的實際含義是：為產生沖突的地址尋找下一個哈希地址為產生沖突的地址尋找下一個哈希地址三種方法三種方法(1)開放定址法開放定址法(2) 鏈地址法鏈地址法(3) 建立公共溢出區建立公共溢出區2021-7-872數據結構與數據結構與STL(1)開放定址法開放定址法為產生沖突的地址為產生沖突的地

37、址 H(key) ，按照某種規則產生按照某種規則產生另一個地址的方法：另一個地址的方法： 線性探測法線性探測法 平方探測法平方探測法 隨機探測法隨機探測法2021-7-873數據結構與數據結構與STL(1)開放定址法開放定址法 線性探測法線性探測法 Hi = ( H(key) + di ) MOD m di = c i 最簡單的情況最簡單的情況 c=1 2021-7-874數據結構與數據結構與STL2021-7-875例子例子25, 18, 23, 3, 56, 87, 19, 37, 59哈希函數哈希函數 h(key) = key % 11h(key) = key % 11251823356

38、87193759哈希表哈希表：ASL1 = (5*1+3*2+3)/9 = 1.56數據結構與數據結構與STL(1)開放定址法開放定址法 平方探測法平方探測法 Hi = ( H(key) + di ) MOD m di = 12, -12, 22, -22, ,2021-7-876數據結構與數據結構與STL2021-7-877例子例子25, 18, 23, 3, 56, 87, 19, 37, 59哈希函數哈希函數 h(key) = key % 11h(key) = key % 1125182335687193759哈希表哈希表：ASL2= (5*1+ 3*2+5)/9 = 1.78數據結構與

39、數據結構與STL(1)開放定址法開放定址法 隨機探測法隨機探測法 Hi = ( H(key) + di ) MOD m di 是一組偽隨機數列是一組偽隨機數列 或者或者 di=iH2(key) (又稱雙散列函數探測又稱雙散列函數探測)。比如：。比如：3. 1. 9. 2. 2021-7-878數據結構與數據結構與STL2021-7-879例子例子 25, 18, 23, 3, 56, 87, 19, 37, 59 哈希函數哈希函數 h(key) = key % 11h(key) = key % 11哈希表：哈希表：25182335687193759ASL3= (5*1+ 2*2+3+4)/9

40、=1.78數據結構與數據結構與STL(2) 拉鏈法拉鏈法基本思想基本思想 將所有散列地址相同的記錄都存儲在一個單將所有散列地址相同的記錄都存儲在一個單鏈表中鏈表中稱為同義詞子表，散列表存儲所有稱為同義詞子表，散列表存儲所有同一詞的頭指針。同一詞的頭指針。2021-7-880數據結構與數據結構與STL2021-7-8816 65 54 43 32 21 10 056233738759251819ASL= (5*1+3*2+3)/9 =1.56數據結構與數據結構與STL(3) 公共溢出法公共溢出法基本思想基本思想散列表包含基本表和溢出表兩個部分，將發生沖散列表包含基本表和溢出表兩個部分，將發生沖突

41、的記錄存儲在溢出表中。突的記錄存儲在溢出表中。 查找方法查找方法通過通過H(key)函數計算散列地址，先與基本表中記函數計算散列地址，先與基本表中記錄進行比較，若相等，則查找成功；否則，到溢錄進行比較，若相等，則查找成功；否則，到溢出表順序查找。出表順序查找。2021-7-882數據結構與數據結構與STL散列查找的性能分析散列查找的性能分析性能分析性能分析散列技術中，處理沖突的方法不同，得到的散列散列技術中，處理沖突的方法不同，得到的散列表不同，散列表的查找性能也不同。表不同，散列表的查找性能也不同。決定性能的因素決定性能的因素比較次數取決于產生沖突的概率。產生的沖突越比較次數取決于產生沖突的

42、概率。產生的沖突越多，則查找效率越低。多，則查找效率越低。2021-7-883數據結構與數據結構與STL散列查找的性能分析散列查找的性能分析2021-7-884哈希函數哈希函數 h(key) = key % 11 ASL1 = (5*1+3*2+3)/9 = 1.56 ASL2= (5*1+ 3*2+5)/9 = 1.782518233568719375925182335687193759哈希表：哈希表：數據結構與數據結構與STL散列查找的性能分析散列查找的性能分析影響沖突的因素影響沖突的因素 1）散列函數是否均勻）散列函數是否均勻 2）處理沖突的方法）處理沖突的方法 3）散列函數的裝填因子）

43、散列函數的裝填因子a a越大代表填入表中的記錄越多，則產生沖越大代表填入表中的記錄越多，則產生沖突的可能性就越大。突的可能性就越大。 2021-7-885a=a=填入表中的記錄個數填入表中的記錄個數散列表的長度散列表的長度數據結構與數據結構與STL開散列和閉散列開散列和閉散列開散列開散列采用鏈式方式存儲同義詞，不產生堆積現象。查采用鏈式方式存儲同義詞，不產生堆積現象。查找找. 插入插入. 刪除易于實現，但附加指針增加了存儲刪除易于實現，但附加指針增加了存儲空間。空間。閉散列閉散列采用順序方式，存儲效率高，但容易產生堆積現采用順序方式，存儲效率高，但容易產生堆積現象。象。2021-7-886數據

44、結構與數據結構與STL第七章第七章 查找查找學習內容：學習內容：1. 概述概述 2. 線性表的查找技術線性表的查找技術 3. 樹表的查找技術樹表的查找技術 4. 散列表的查找技術散列表的查找技術5. 查找的應用查找的應用6. STL中的相關模版類中的相關模版類87數據結構與數據結構與STL5. 查找的應用查找的應用2021-7-85. 查找的應用查找的應用主要內容主要內容1. 文件查找文件查找2. 中文分詞技術中的詞搜索算法中文分詞技術中的詞搜索算法2021-7-8881. 文件查找文件查找問題問題一個文件包含至多一個文件包含至多10,000,000條數據，每條數據條數據，每條數據都是一個都是

45、一個7位的整數，每個整數至多出現一次，系位的整數，每個整數至多出現一次，系統只有統只有2MB的內存空間，和無限大的硬盤空間，的內存空間，和無限大的硬盤空間，如何利用利用散列表來實現存儲和查找？如何利用利用散列表來實現存儲和查找？2021-7-8891. 文件查找文件查找基本思想基本思想利用類似位圖的方法來實現散列函數。利用類似位圖的方法來實現散列函數。例如集合例如集合1,2,3,5,8,13人存儲方式可以是這樣的人存儲方式可以是這樣的0 1 1 1 0 1 0 0, 1 0 0 0 0 1 0 0, 0 0 0 0 將代表數字的各個位設置將代表數字的各個位設置1，其他位全部設置，其他位全部設置

46、0。 存儲空間存儲空間=10000000bit(10Mbit = 1.25MB2MB)當且僅當整數當且僅當整數i在該文件中存在，將第在該文件中存在，將第i位置位置1；否；否則置則置0。2021-7-8901. 文件查找文件查找初始化長度為初始化長度為N字符串，全部位置字符串，全部位置0，這里，這里N=(最大整數值最大整數值+1)/一個一個char所占用的所占用的bit數數=10000000/8=1250000讀取文件中一條數據，把相應讀取文件中一條數據，把相應bit置置1，再讀下一條，再讀下一條數據，直到文件結束數據，直到文件結束查找時只需按位檢測查找時只需按位檢測bit是否為是否為1，若待查

47、數據對應，若待查數據對應bit為為1，則查找成功；否則查找失敗；，則查找成功；否則查找失敗；2021-7-8911. 文件查找文件查找模塊化劃分模塊化劃分1）構造一個空的散列表）構造一個空的散列表unsigned char ch1250000 = 0;2）在散列表中插入一個元素）在散列表中插入一個元素void insert_ele (unsigned char ch, int elementary)；3）在散列表中查找一個元素）在散列表中查找一個元素bool search_ele (unsigned char ch, int elementary)4）讀取文件，并調用函數（）讀取文件，并調用函

48、數（2生成散列表生成散列表5）讀取用戶輸入，并調用函數（）讀取用戶輸入，并調用函數（3查找散列表查找散列表2021-7-8922. 中文分詞技術中的詞搜索算法中文分詞技術中的詞搜索算法所謂中文分詞，是指將一個漢字序列切分成一個所謂中文分詞，是指將一個漢字序列切分成一個一個單獨的詞。一個單獨的詞。中文分詞是自然語言處理、文本挖掘等研究領域中文分詞是自然語言處理、文本挖掘等研究領域的基礎。的基礎。2021-7-8932. 中文分詞技術中的詞搜索算法中文分詞技術中的詞搜索算法基于字符串匹配的分詞方法基于字符串匹配的分詞方法它按照一定的策略將待分析的漢字串與一個它按照一定的策略將待分析的漢字串與一個“

49、充分充分大的大的”中文詞典中的詞條進行匹配，若在詞典中找中文詞典中的詞條進行匹配，若在詞典中找到某個字符串，則匹配成功（識別出一個詞）。到某個字符串，則匹配成功（識別出一個詞）。掃描方向：正向匹配掃描方向：正向匹配 / 逆向匹配逆向匹配長度：最大（最長）匹配長度：最大（最長）匹配 / 最小（最短）匹配最小（最短）匹配詞性標注：單純分詞方法詞性標注：單純分詞方法 / 分詞與標注相結合的分詞與標注相結合的一體化方法一體化方法2021-7-8942. 中文分詞技術中的詞搜索算法中文分詞技術中的詞搜索算法問題問題判斷一個漢字串是否詞典中的詞是必須的，如何判斷一個漢字串是否詞典中的詞是必須的，如何快速實

50、現其快速匹配？快速實現其快速匹配？2021-7-8952. 中文分詞技術中的詞搜索算法中文分詞技術中的詞搜索算法基本思想基本思想散列技術進行查找效率是最高的散列技術進行查找效率是最高的，因此，如何將，因此，如何將詞典中的詞放到一個散列表中是關鍵詞典中的詞放到一個散列表中是關鍵假定所有詞典中的所有漢字都在假定所有詞典中的所有漢字都在GB2312-80一級一級字庫內，而一級字庫的漢字共有字庫內，而一級字庫的漢字共有3755個，其編碼個，其編碼具有一定的規則：具有一定的規則：每個漢字占兩個字節；每個漢字占兩個字節；第一個字節（高字節）的值大于等于第一個字節（高字節）的值大于等于176；第二個字節（低

51、字節）的值大于等于第二個字節（低字節）的值大于等于161，但小于，但小于255。因此每個漢字編碼的二進制形式為因此每個漢字編碼的二進制形式為“1xxxxxxx 1xxxxxxx”，每個字節的最高位為，每個字節的最高位為1。2021-7-8962. 中文分詞技術中的詞搜索算法中文分詞技術中的詞搜索算法散列函數：散列函數：H(漢字編碼漢字編碼)=(漢字編碼高字節漢字編碼高字節-176)*94+(漢字編漢字編碼低字節碼低字節161)這樣一級字庫的漢字放到長度為這樣一級字庫的漢字放到長度為3755的散列表中的散列表中剛好地址是唯一的，得到的散列地址從剛好地址是唯一的，得到的散列地址從0到到3754，既

52、不會用沖突，也不會用空余。既不會用沖突，也不會用空余。“啊啊”：編碼編碼0 xB0A1H(“啊啊”)= ( 0 xB0 - 176 ) * 94 + (0 xA1 161 ) = 0； “座座”： 編碼編碼0 xD7F9H(“座座”)= ( 0 xD7 - 176 ) * 94 + (0 xF9 161 ) = 3754。2021-7-8972. 中文分詞技術中的詞搜索算法中文分詞技術中的詞搜索算法每個詞都有第一個漢字，因此可以將其作為散每個詞都有第一個漢字，因此可以將其作為散列函數的關鍵字。以拉鏈法解決沖突。列函數的關鍵字。以拉鏈法解決沖突。2021-7-8982. 中文分詞技術中的詞搜索算

53、法中文分詞技術中的詞搜索算法缺點缺點散列表非常小，而每個鏈表相對較長，在查找鏈散列表非常小，而每個鏈表相對較長，在查找鏈表時只能順序查找，因此查找速度較慢。表時只能順序查找，因此查找速度較慢。改進改進散列表越長，關鍵字在表中的分布越均勻，則沖散列表越長，關鍵字在表中的分布越均勻，則沖突越少、匹配速度越快。突越少、匹配速度越快。一般的中文詞典包含的中文詞有一般的中文詞典包含的中文詞有20萬到萬到60萬不等，萬不等，以以60萬為例，并設裝填因子為萬為例，并設裝填因子為0.6，則散列表長度，則散列表長度設計為設計為100萬。萬。2021-7-8992. 中文分詞技術中的詞搜索算法中文分詞技術中的詞搜

54、索算法空間復雜度空間復雜度采用拉鏈法建立散列表采用拉鏈法建立散列表結點：漢字個數、所有漢字、下一個同義詞結點結點：漢字個數、所有漢字、下一個同義詞結點地址。地址。地址占地址占4個字節；漢字個數域占個字節；漢字個數域占1個字節；假設每個字節；假設每個詞平均有個詞平均有3個漢字，共個漢字，共6個字節。個字節。整個散列表總共的存儲空間：整個散列表總共的存儲空間：10000004 + 6000001110.1MByte2021-7-81002. 中文分詞技術中的詞搜索算法中文分詞技術中的詞搜索算法存放方法存放方法散列表長度為散列表長度為1M，可用，可用20個比特表示每個地址。個比特表示每個地址。對于二

55、字詞，共有對于二字詞，共有4個字節，考慮到每個字節的最個字節，考慮到每個字節的最高比特均為高比特均為1，實際大小，實際大小4x8-4=28bit抽取抽取20個比特作為散列地址。個比特作為散列地址。對于三字詞或更高字詞，仍然只需抽取對于三字詞或更高字詞，仍然只需抽取20個比特。個比特。2021-7-81012. 中文分詞技術中的詞搜索算法中文分詞技術中的詞搜索算法抽取方法示例抽取方法示例對于含有對于含有n個漢字的詞，共有個漢字的詞，共有2n個字節個字節去掉每個字節的最高位，共有去掉每個字節的最高位，共有14n個比特個比特每每20個分為一組。若不足個分為一組。若不足20，在后面補，在后面補“0”，

56、構成，構成20比特。比特。各組進行異或運算，最后得到的運算結果作為散各組進行異或運算，最后得到的運算結果作為散列地址。列地址。例如對于四字詞，共有例如對于四字詞，共有56個比特，可分為個比特，可分為3組進行組進行異或運算，異或運算，2021-7-8102抽取方法示例抽取方法示例2021-7-81032. 中文分詞技術中的詞搜索算法中文分詞技術中的詞搜索算法性能性能該方法對該方法對31萬個中文詞構造長度為萬個中文詞構造長度為1M的散列表，的散列表，產生了大約產生了大約26萬個不同的散列地址，即萬個不同的散列地址，即5萬個詞在萬個詞在構造散列地址時產生沖突構造散列地址時產生沖突最長的鏈表為最長的鏈

57、表為7個詞，即最壞情況比較個詞，即最壞情況比較7次次平均比較次數僅為平均比較次數僅為1.21次。次。2021-7-8104第七章第七章 查找查找學習內容：學習內容：1. 概述概述 2. 線性表的查找技術線性表的查找技術 3. 樹表的查找技術樹表的查找技術 4. 散列表的查找技術散列表的查找技術5. 查找的應用查找的應用6. STL中的相關模版類中的相關模版類105數據結構與數據結構與STL6. STL中的相關模版類中的相關模版類2021-7-86. STL中的相關模版類中的相關模版類集合集合(Set)一個集合（一個集合（set）是一個容器，它其中所包含的元）是一個容器，它其中所包含的元素的值是

58、唯一的。素的值是唯一的。內部數據結構內部數據結構集合（集合（set）的內部數據組織是一顆紅黑樹）的內部數據組織是一顆紅黑樹(一種非嚴格一種非嚴格意義上的平衡二叉樹意義上的平衡二叉樹)，這顆樹具有對數據自動排序的，這顆樹具有對數據自動排序的功能，因此，功能，因此，set內部所有的數據是有序的。內部所有的數據是有序的。2021-7-8106集合集合(Set)1、set的構造函數的構造函數定義一個元素為整數的集合定義一個元素為整數的集合a，可以用：，可以用： set intSet;2021-7-8107集合集合(Set)數據的基本操作數據的基本操作插入元素：插入元素：intSet.insert(1)

59、;刪除元素（如果存在）：刪除元素（如果存在）：intSet.erase(1);判斷元素是否屬于集合：判斷元素是否屬于集合： if (intSet.find(1) != intSet.end() .返回集合元素的個數：返回集合元素的個數：intSet.size()將集合清為空集：將集合清為空集：intSet.clear()2021-7-8108集合集合(Set)問題：如何判斷一個元素是否在問題：如何判斷一個元素是否在Set中？中？方法一方法一用用count函數來判定關鍵字是否出現，返回值是函數來判定關鍵字是否出現，返回值是1，則關鍵字在則關鍵字在Set中出現的情況，否則返回中出現的情況，否則返回

60、0。比如。比如查找關鍵字查找關鍵字1是否出現：是否出現： int index intSet. count(1);2021-7-8109集合集合(Set)方法二方法二用用find函數來定位數據出現位置，它返回一個迭函數來定位數據出現位置，它返回一個迭代器，當代器，當set中包含該數據，返回數據所在位置的中包含該數據，返回數據所在位置的迭代器，如果不包含，返回的迭代器等于迭代器，如果不包含，返回的迭代器等于end函數函數返回的迭代器。比如查找關鍵字返回的迭代器。比如查找關鍵字1是否出現：是否出現：if (intSet.find(1) = intSet.end() cout”Not Find ”1e