數(shù)據(jù)結(jié)構(gòu)-查找算法

1、第第1010章章 查找查找查找的基本概念查找的基本概念靜態(tài)查找表靜態(tài)查找表動態(tài)查找表動態(tài)查找表哈希表哈希表主要知識點主要知識點10.1 10.1 查找的基本概念查找的基本概念 查找查找: :查詢查詢關(guān)鍵字關(guān)鍵字是否在是否在( (數(shù)據(jù)元素集合）表中的過程。也稱作數(shù)據(jù)元素集合）表中的過程。也稱作檢索檢索。主關(guān)鍵字主關(guān)鍵字: :能夠惟一區(qū)分各個不同數(shù)據(jù)元素的關(guān)鍵字能夠惟一區(qū)分各個不同數(shù)據(jù)元素的關(guān)鍵字次關(guān)鍵字次關(guān)鍵字: :通常不能惟一區(qū)分各個不同數(shù)據(jù)元素的關(guān)鍵字通常不能惟一區(qū)分各個不同數(shù)據(jù)元素的關(guān)鍵字查找成功查找成功: :在數(shù)據(jù)元素集合中找到了要查找的數(shù)據(jù)元素在數(shù)據(jù)元素集合中找到了要查找的數(shù)據(jù)元素查找

2、不成功查找不成功: :在數(shù)據(jù)元素集合中沒有找到要查找的數(shù)據(jù)元素在數(shù)據(jù)元素集合中沒有找到要查找的數(shù)據(jù)元素靜態(tài)查找靜態(tài)查找: :只查找，不改變數(shù)據(jù)元素集合內(nèi)的數(shù)據(jù)元素只查找，不改變數(shù)據(jù)元素集合內(nèi)的數(shù)據(jù)元素動態(tài)查找動態(tài)查找: :既查找，又改變（增減）集合內(nèi)的數(shù)據(jù)元素既查找，又改變（增減）集合內(nèi)的數(shù)據(jù)元素靜態(tài)查找表靜態(tài)查找表: :靜態(tài)查找時構(gòu)造的存儲結(jié)構(gòu)靜態(tài)查找時構(gòu)造的存儲結(jié)構(gòu)動態(tài)查找表動態(tài)查找表: :動態(tài)查找時構(gòu)造的存儲結(jié)構(gòu)動態(tài)查找時構(gòu)造的存儲結(jié)構(gòu)平均查找長度平均查找長度: :查找過程所需進行的關(guān)鍵字比較次數(shù)的平均值查找過程所需進行的關(guān)鍵字比較次數(shù)的平均值, ,是衡量查找算是衡量查找算法效率的最主要

3、標(biāo)準(zhǔn)法效率的最主要標(biāo)準(zhǔn), ,其數(shù)學(xué)定義為：其數(shù)學(xué)定義為：1niiiASLPC10.2 10.2 靜態(tài)查找表靜態(tài)查找表 靜態(tài)查找表主要有三種結(jié)構(gòu)：靜態(tài)查找表主要有三種結(jié)構(gòu)： 順序表順序表 有序順序表有序順序表 索引順序表索引順序表1.1.順序表順序表 在順序表上查找的在順序表上查找的基本思想是：基本思想是：從順序表的一端開始，用給從順序表的一端開始，用給定數(shù)據(jù)元素的關(guān)鍵字逐個和順序表中各數(shù)據(jù)元素的關(guān)鍵字比較，定數(shù)據(jù)元素的關(guān)鍵字逐個和順序表中各數(shù)據(jù)元素的關(guān)鍵字比較，若在順序表中查找到要查找的數(shù)據(jù)元素，則查找成功，函數(shù)返回若在順序表中查找到要查找的數(shù)據(jù)元素，則查找成功，函數(shù)返回該數(shù)據(jù)元素在順序表中的

4、位置；否則查找失敗，函數(shù)返回該數(shù)據(jù)元素在順序表中的位置；否則查找失敗，函數(shù)返回-1-1。 查找函數(shù)設(shè)計如下：查找函數(shù)設(shè)計如下：#includeSeqList.hint SeqSearch(SeqList S, DataType x)/在在a0-an-1中順序查找關(guān)鍵碼為中順序查找關(guān)鍵碼為key的數(shù)據(jù)元素的數(shù)據(jù)元素/查找成功時返回該元素的下標(biāo)序號；失敗時返回查找成功時返回該元素的下標(biāo)序號；失敗時返回-1int i = 0;while(i n & ai.key != key) i+; if(ai.key = key) return i;else return -1;算法分析算法分析查找成功時的平均

5、查找長度查找成功時的平均查找長度ASLASL成功成功為：為： niiniininCPASL112/)1(1成功查找失敗時的平均查找長度查找失敗時的平均查找長度ASLASL失敗失敗為為 2/)1(111ninCPASLniinii失敗時間效率為時間效率為 O(n)2.2.有序順序表有序順序表 有序順序表上的查找算法主要有有序順序表上的查找算法主要有順序查找順序查找和和折半查找折半查找兩種方法。兩種方法。一、順序查找一、順序查找有序順序表上的順序查找算法和順序表上的查找算法方法類同有序順序表上的順序查找算法和順序表上的查找算法方法類同 二、二分查找（二、二分查找（又稱又稱折半查找）折半查找）算法的

6、基本思想：算法的基本思想：先給數(shù)據(jù)排序先給數(shù)據(jù)排序（例如按升序排好），形成（例如按升序排好），形成有有序表，序表，然后再將然后再將keykey與與正中正中元素相比，若元素相比，若keykey小，則縮小至前半小，則縮小至前半部內(nèi)查找；再取其部內(nèi)查找；再取其中值中值比較，每次縮小比較，每次縮小1/21/2的范圍，直到查找的范圍，直到查找成功或失敗為止。反之，如果成功或失敗為止。反之，如果keykey大，則縮小至后半部內(nèi)查找。大，則縮小至后半部內(nèi)查找。二分查找算法如下：二分查找算法如下：int BiSearch(DataType a, int n, KeyType key)/在有序表在有序表a0-a

7、n-1中二分查找關(guān)鍵碼為中二分查找關(guān)鍵碼為key的數(shù)據(jù)元素的數(shù)據(jù)元素/查找成功時返回該元素的下標(biāo)序號；失敗時返回查找成功時返回該元素的下標(biāo)序號；失敗時返回-1int low = 0, high = n - 1;/確定初始查找區(qū)間上下界確定初始查找區(qū)間上下界int mid; while(low = high)mid = (low + high)/2;/確定查找區(qū)間中心下標(biāo)確定查找區(qū)間中心下標(biāo) if(amid.key = key) return mid;/查找成功查找成功else if(amid.key data.key = item.key) return 1; /查找成功查找成功 if(ite

8、m.key p - data.key) p = p - rightChild; /在右子樹繼續(xù)在右子樹繼續(xù)else p = p - leftChild; /在左子樹繼續(xù)在左子樹繼續(xù)return 0; /查找失敗查找失敗三、插入算法三、插入算法 插入操作要求首先查找數(shù)據(jù)元素是否在二叉排序樹中存插入操作要求首先查找數(shù)據(jù)元素是否在二叉排序樹中存在，若在，若存在則返回存在則返回；若不存在，；若不存在，插入查找失敗時結(jié)點的左指插入查找失敗時結(jié)點的左指針或右指針上。針或右指針上。 插入算法設(shè)計如下插入算法設(shè)計如下:int Insert(BiTreeNode *root, DataType item)/在二

9、叉排序樹在二叉排序樹root中查找數(shù)據(jù)元素中查找數(shù)據(jù)元素item是否存在，若存在返回是否存在，若存在返回0，/否則把否則把item結(jié)點插入到當(dāng)前結(jié)點的左指針或右指針上并返回結(jié)點插入到當(dāng)前結(jié)點的左指針或右指針上并返回1 BiTreeNode *current, *parent = NULL, *p; current = *root; while(current != NULL) if(current - data.key = item.key)return0; parent = current; if(current -data.key rightChild; else current = cu

10、rrent -leftChild; P = (BiTreeNode *)malloc(sizeof(BiTreeNode);if(p = NULL) printf(空間不夠！空間不夠！) exit(1);/生成新結(jié)點生成新結(jié)點P - data = item;P - leftChild = NULL;P - rightChild = NULL;if(parent = NULL) *root = p; /新結(jié)點成為根結(jié)點新結(jié)點成為根結(jié)點else if(item.key data.key) parent - leftChild = p; /新結(jié)點為該結(jié)點的左孩子結(jié)點新結(jié)點為該結(jié)點的左孩子結(jié)點else

11、 parent - rightChild = p; /新結(jié)點為該結(jié)點的右孩子結(jié)點新結(jié)點為該結(jié)點的右孩子結(jié)點return 1;下圖是調(diào)用上述插入函數(shù)依次插入數(shù)據(jù)元素下圖是調(diào)用上述插入函數(shù)依次插入數(shù)據(jù)元素 4,5,7,2,1,9,8,11,34,5,7,2,1,9,8,11,3的過程。的過程。41152791384115279184527918452791452714527457454(d)(c)(b)(a)(g)(f)(e)(i)(h)五、刪除算法五、刪除算法 刪除操作要求首先查找數(shù)據(jù)元素是否在二叉排序樹中存在，刪除操作要求首先查找數(shù)據(jù)元素是否在二叉排序樹中存在，若不存在則結(jié)束；若不存在則結(jié)束；

12、存在的情況及相應(yīng)的刪除方法有如下四種：存在的情況及相應(yīng)的刪除方法有如下四種：(1)(1)要刪除結(jié)點要刪除結(jié)點無孩子結(jié)點無孩子結(jié)點，直接刪除該結(jié)點。，直接刪除該結(jié)點。(2)(2)要刪除結(jié)點要刪除結(jié)點只有左孩子結(jié)點只有左孩子結(jié)點，刪除該結(jié)點且使被刪除結(jié)點，刪除該結(jié)點且使被刪除結(jié)點的雙親結(jié)點指向被刪除結(jié)點的左孩子結(jié)點。的雙親結(jié)點指向被刪除結(jié)點的左孩子結(jié)點。(3)(3)要刪除結(jié)點要刪除結(jié)點只有右孩子結(jié)點只有右孩子結(jié)點，刪除該結(jié)點且使被刪除結(jié)點，刪除該結(jié)點且使被刪除結(jié)點的雙親結(jié)點指向被刪除結(jié)點的右孩子結(jié)點。的雙親結(jié)點指向被刪除結(jié)點的右孩子結(jié)點。(4)(4)要刪除結(jié)點要刪除結(jié)點有左右孩子結(jié)點有左右孩子結(jié)點

13、，分如下三步完成：首先尋找，分如下三步完成：首先尋找數(shù)據(jù)元素的關(guān)鍵字值大于要刪除結(jié)點數(shù)據(jù)元素關(guān)鍵字的最小值數(shù)據(jù)元素的關(guān)鍵字值大于要刪除結(jié)點數(shù)據(jù)元素關(guān)鍵字的最小值，即尋找要刪除結(jié)點右子樹的最左結(jié)點；然后把右子樹的最左，即尋找要刪除結(jié)點右子樹的最左結(jié)點；然后把右子樹的最左結(jié)點的數(shù)據(jù)元素值拷貝到要刪除的結(jié)點上；最后刪除右子樹的結(jié)點的數(shù)據(jù)元素值拷貝到要刪除的結(jié)點上；最后刪除右子樹的最左結(jié)點。最左結(jié)點。刪除過程分別如圖所示刪除過程分別如圖所示1814245162038710303518142451620387303518142451620387103035181424516203071035ptrptr

14、(a)無孩子結(jié)點無孩子結(jié)點(b)有左孩子結(jié)點有左孩子結(jié)點18142451620387103035181424716203810303518142451620387103035181430516207103835ptrptr(c)有右孩子結(jié)點有右孩子結(jié)點(d)有左右孩子結(jié)點有左右孩子結(jié)點六、二叉排序樹的性能分析六、二叉排序樹的性能分析 一棵二叉排序樹的平均查找長度為：一棵二叉排序樹的平均查找長度為：其中：其中：ni 是每層結(jié)點個數(shù)；是每層結(jié)點個數(shù)； Ci 是結(jié)點所在層次數(shù)；是結(jié)點所在層次數(shù)；m 為樹深。為樹深。當(dāng)二叉排序樹是一棵單分支退化樹時，查找成功的平均查找長當(dāng)二叉排序樹是一棵單分支退化樹時

15、，查找成功的平均查找長度和有序順序表的平均查找長度相同，即為：度和有序順序表的平均查找長度相同，即為：nininASL12/ ) 1(1成功若每個數(shù)據(jù)元素的查找概率相等，則二叉排序樹查找成功的平若每個數(shù)據(jù)元素的查找概率相等，則二叉排序樹查找成功的平均查找長度為：均查找長度為： ) 1(log)2(1211ninASLkii成功11miiiASLn Cn3456781064835710(a)(b)（a）滿二叉排序樹時，滿二叉排序樹時，k =log2(7+1)=3，所以查找成功的平均查找長度為：所以查找成功的平均查找長度為： 717) 34221 (71)2(111inASLiki成功（b）左分支

16、退化二叉排序樹時，左分支退化二叉排序樹時，k = n=7，所以查找成功的平均查找長度所以查找成功的平均查找長度為：為： 42/ ) 17(2/ ) 1(11nininASL成功在最壞情況下，二叉排序樹的平均查找長度為在最壞情況下，二叉排序樹的平均查找長度為O(n)。在一般情在一般情況下，二叉排序樹的平均查找長度為況下，二叉排序樹的平均查找長度為O(log2n)。 2.B_樹樹 B_ B_樹是一種平衡多叉排序樹。樹是一種平衡多叉排序樹。平衡是指所有葉結(jié)點都在同一平衡是指所有葉結(jié)點都在同一層上層上，從而可避免出現(xiàn)像二叉排序樹那樣的分支退化現(xiàn)象。因，從而可避免出現(xiàn)像二叉排序樹那樣的分支退化現(xiàn)象。因此

17、此B_B_樹的動態(tài)查找效率更高樹的動態(tài)查找效率更高。B_B_樹中所有結(jié)點的孩子結(jié)點的最大值稱為樹中所有結(jié)點的孩子結(jié)點的最大值稱為B_B_樹的階樹的階，一棵一棵m階階的的B_樹或者是一棵空樹，或者是滿足下列要求的樹或者是一棵空樹，或者是滿足下列要求的m叉樹：叉樹：(1)樹中每個結(jié)點至多有樹中每個結(jié)點至多有m個孩子結(jié)點。個孩子結(jié)點。(2)除根結(jié)點外，其他結(jié)點至少有除根結(jié)點外，其他結(jié)點至少有 m/2 個孩子結(jié)點（符號個孩子結(jié)點（符號“ ”表示上取整）。表示上取整）。(3)若根結(jié)點不是葉結(jié)點，則根結(jié)點至少有兩個孩子結(jié)點；若根結(jié)點不是葉結(jié)點，則根結(jié)點至少有兩個孩子結(jié)點；(4)每個結(jié)點的結(jié)構(gòu)為：每個結(jié)點的

18、結(jié)構(gòu)為：nP0K1P1K2P2KnPn(5)(5)所有葉結(jié)點都在同一層上。所有葉結(jié)點都在同一層上。 1502041172214432330351151603778088 root一棵一棵4階階B_樹樹1. 查找算法查找算法 在在B_樹上查找數(shù)據(jù)元素樹上查找數(shù)據(jù)元素x的方法為：將的方法為：將 x.key與根結(jié)點的與根結(jié)點的Ki逐個進逐個進行比較：行比較：（1）若）若x.key=Ki則查找成功。則查找成功。（2）若）若keyK1則沿著指針則沿著指針P0所指的子樹繼續(xù)查找。所指的子樹繼續(xù)查找。（3）若）若KikeyKn則沿著指針則沿著指針Pn所指的子樹繼續(xù)查找。所指的子樹繼續(xù)查找。2. 插入算法插入

19、算法 插入過程分兩步完成：插入過程分兩步完成：（1 1）利用查找算法找出該關(guān)鍵字的插入結(jié)點（）利用查找算法找出該關(guān)鍵字的插入結(jié)點（B_B_樹的插入結(jié)點一樹的插入結(jié)點一定是葉結(jié)點定是葉結(jié)點）。）。（2 2）判斷該結(jié)點是否還有空位置，即判斷該結(jié)點是否滿足）判斷該結(jié)點是否還有空位置，即判斷該結(jié)點是否滿足nm-1nm-1，若該結(jié)點滿足若該結(jié)點滿足nm-1n tableSize = mSize;hash - ht = (HashItem *)malloc(sizeof(HashItem)*mSize)if(hash - ht = NULL) return 0; else hash - currentSi

20、ze = 0; return 1; int Find(HashTable *hash, DataType x)/查找查找int i = x.key % hash - tableSize;int j = i;while(hash - = Active & hash - htj.data != x.key) /說明存在沖突說明存在沖突j = (j + 1) % hash - tableSize; /用哈希沖突方法繼續(xù)查找用哈希沖突方法繼續(xù)查找 if(j = i) /說明已遍歷整個哈希表未找到且表已滿說明已遍歷整個哈希表未找到且表已滿 return - hash - tableSize;if(hash - = Activ