第八章數(shù)據(jù)結(jié)構(gòu)-查找

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

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

3、查找算法效率的最主要標(biāo)準(zhǔn), ,其數(shù)學(xué)定義為：其數(shù)學(xué)定義為：其中，其中，Pi是要查找數(shù)據(jù)元素出現(xiàn)的概率，是要查找數(shù)據(jù)元素出現(xiàn)的概率，Ci是查是查找相應(yīng)數(shù)據(jù)元素的比較次數(shù)。找相應(yīng)數(shù)據(jù)元素的比較次數(shù)。定義要定義要查找數(shù)據(jù)元素的結(jié)構(gòu)體為：查找數(shù)據(jù)元素的結(jié)構(gòu)體為：typedef structtypedef struct KeyType key;KeyType key; DataType; DataType;=niiiCPASL18.2 8.2 靜態(tài)查找表靜態(tài)查找表 靜態(tài)查找表主要有三種結(jié)構(gòu)：靜態(tài)查找表主要有三種結(jié)構(gòu)： 順序表順序表 有序順序表有序順序表 索引順序表索引順序表1.1.順序表順序表 在順序表

4、上查找的在順序表上查找的基本思想是：基本思想是：從順序表的一端開(kāi)始，用給從順序表的一端開(kāi)始，用給定數(shù)據(jù)元素的關(guān)鍵字逐個(gè)和順序表中各數(shù)據(jù)元素的關(guān)鍵字比較，定數(shù)據(jù)元素的關(guān)鍵字逐個(gè)和順序表中各數(shù)據(jù)元素的關(guān)鍵字比較，若在順序表中查找到要查找的數(shù)據(jù)元素，則查找成功，函數(shù)返回若在順序表中查找到要查找的數(shù)據(jù)元素，則查找成功，函數(shù)返回該數(shù)據(jù)元素在順序表中的位置；否則查找失敗，函數(shù)返回該數(shù)據(jù)元素在順序表中的位置；否則查找失敗，函數(shù)返回-1-1。 查找函數(shù)設(shè)計(jì)如下：查找函數(shù)設(shè)計(jì)如下：int SeqSearch(DataType a, int n, KeyType key)/在在a0-an-1中順序查找關(guān)鍵碼為中順

5、序查找關(guān)鍵碼為key的數(shù)據(jù)元素的數(shù)據(jù)元素/查找成功時(shí)返回該元素的下標(biāo)序號(hào)；失敗時(shí)返回查找成功時(shí)返回該元素的下標(biāo)序號(hào)；失敗時(shí)返回-1int i = 0;while(i n & ai.key != key) i+; if(ai.key = key) return i;else return -1;算法分析算法分析查找成功時(shí)的平均查找長(zhǎng)度查找成功時(shí)的平均查找長(zhǎng)度ASLASL成功成功為：為： =niiniininCPASL112/)1(1成功查找失敗時(shí)的平均查找長(zhǎng)度查找失敗時(shí)的平均查找長(zhǎng)度ASLASL失敗失敗為為 2/)1(111=ninCPASLniinii失敗2.2.有序順序表有序順序表 有序順序

6、表上的查找算法主要有有序順序表上的查找算法主要有順序查找順序查找和和折半查找折半查找兩種方法。兩種方法。一、順序查找一、順序查找有序順序表上的順序查找算法和順序表上的查找算法方法類(lèi)同有序順序表上的順序查找算法和順序表上的查找算法方法類(lèi)同 二、二分查找（二、二分查找（又稱(chēng)又稱(chēng)折半查找）折半查找）算法的基本思想：算法的基本思想：先給數(shù)據(jù)排序先給數(shù)據(jù)排序（例如按升序排好），形成（例如按升序排好），形成有有序表，序表，然后再將然后再將keykey與與正中正中元素相比，若元素相比，若keykey小，則縮小至前半小，則縮小至前半部?jī)?nèi)查找；再取其部?jī)?nèi)查找；再取其中值中值比較，每次縮小比較，每次縮小1/21/

7、2的范圍，直到查找的范圍，直到查找成功或失敗為止。反之，如果成功或失敗為止。反之，如果keykey大，則縮小至后半部?jī)?nèi)查找。大，則縮小至后半部?jī)?nèi)查找。二分查找算法如下：二分查找算法如下：int BiSearch(DataType a, int n, KeyType key)/在有序表在有序表a0-an-1中二分查找關(guān)鍵碼為中二分查找關(guān)鍵碼為key的數(shù)據(jù)元素的數(shù)據(jù)元素/查找成功時(shí)返回該元素的下標(biāo)序號(hào)；失敗時(shí)返回查找成功時(shí)返回該元素的下標(biāo)序號(hào)；失敗時(shí)返回-1 int low = 0, high = n - 1;/確定初始查找區(qū)間上下界確定初始查找區(qū)間上下界 int mid; while(low =

8、 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(p-data.key = item.key) return 1; if(item.key p-data.key) p = p-rightChild;if(item.key p-data.key) p = p-rightChild; else p = p-leftChild; else p = p-leftChild;

9、 return 0; return 0; 三、插入算法三、插入算法 插入操作要求首先查找數(shù)據(jù)元素是否在二叉排序樹(shù)中存在，插入操作要求首先查找數(shù)據(jù)元素是否在二叉排序樹(shù)中存在，若若存在則返回存在則返回；若不存在，；若不存在，插入查找失敗時(shí)結(jié)點(diǎn)的左指針或右插入查找失敗時(shí)結(jié)點(diǎn)的左指針或右指針上。所插新結(jié)點(diǎn)一定在葉結(jié)點(diǎn)上。指針上。所插新結(jié)點(diǎn)一定在葉結(jié)點(diǎn)上。插入算法設(shè)計(jì)如下插入算法設(shè)計(jì)如下:int Insert(BiTreeNode int Insert(BiTreeNode * * *root, DataType item)root, DataType item) BiTreeNode BiTreeNo

10、de * *current, current, * *parent = NULL, parent = NULL, * *p;p;current = current = * *root;root;while(current != NULL)while(current != NULL) if(current-data.key = item.key) return 0;if(current-data.key = item.key) return 0;parent = current;parent = current;if(current-data.key data.key rightChild;cu

11、rrent = current-rightChild;else else current = current-leftChild;current = current-leftChild; / /* *生成新結(jié)點(diǎn)生成新結(jié)點(diǎn)* */ /p = (BiTreeNode p = (BiTreeNode * *)malloc(sizeof(BiTreeNode);)malloc(sizeof(BiTreeNode);p-data = item;p-data = item;p-leftChild = NULL;p-leftChild = NULL;p-rightChild = NULL;p-rightCh

12、ild = NULL;if(parent = NULL) if(parent = NULL) * *root = p;root = p;else if(item.key data.key)else if(item.key data.key)parent-leftChild = p;parent-leftChild = p;else else parent-rightChild = p;parent-rightChild = p;return 1;return 1; 下圖是調(diào)用上述插入函數(shù)依次插入數(shù)據(jù)元素下圖是調(diào)用上述插入函數(shù)依次插入數(shù)據(jù)元素 4,5,7,2,1,9,8,11,34,5,7,2,

13、1,9,8,11,3的過(guò)程。的過(guò)程。41152791384115279184527918452791452714527457454(d)(c)(b)(a)(g)(f)(e)(i)(h)五、刪除算法五、刪除算法 刪除操作要求首先查找數(shù)據(jù)元素是否在二叉排序樹(shù)中存在，刪除操作要求首先查找數(shù)據(jù)元素是否在二叉排序樹(shù)中存在，若不存在則結(jié)束；若不存在則結(jié)束；存在的情況及相應(yīng)的刪除方法有如下四種：存在的情況及相應(yīng)的刪除方法有如下四種：(1)(1)要?jiǎng)h除結(jié)點(diǎn)要?jiǎng)h除結(jié)點(diǎn)無(wú)孩子結(jié)點(diǎn)無(wú)孩子結(jié)點(diǎn)，直接刪除該結(jié)點(diǎn)。，直接刪除該結(jié)點(diǎn)。(2)(2)要?jiǎng)h除結(jié)點(diǎn)要?jiǎng)h除結(jié)點(diǎn)只有左孩子結(jié)點(diǎn)只有左孩子結(jié)點(diǎn)，刪除該結(jié)點(diǎn)且使被刪除結(jié)點(diǎn)，刪

14、除該結(jié)點(diǎn)且使被刪除結(jié)點(diǎn)的雙親結(jié)點(diǎn)指向被刪除結(jié)點(diǎn)的左孩子結(jié)點(diǎn)。的雙親結(jié)點(diǎn)指向被刪除結(jié)點(diǎn)的左孩子結(jié)點(diǎn)。(3)(3)要?jiǎng)h除結(jié)點(diǎn)要?jiǎng)h除結(jié)點(diǎn)只有右孩子結(jié)點(diǎn)只有右孩子結(jié)點(diǎn)，刪除該結(jié)點(diǎn)且使被刪除結(jié)點(diǎn)，刪除該結(jié)點(diǎn)且使被刪除結(jié)點(diǎn)的雙親結(jié)點(diǎn)指向被刪除結(jié)點(diǎn)的右孩子結(jié)點(diǎn)。的雙親結(jié)點(diǎn)指向被刪除結(jié)點(diǎn)的右孩子結(jié)點(diǎn)。(4)(4)要?jiǎng)h除結(jié)點(diǎn)要?jiǎng)h除結(jié)點(diǎn)有左右孩子結(jié)點(diǎn)有左右孩子結(jié)點(diǎn)，分如下三步完成：首先尋找，分如下三步完成：首先尋找數(shù)據(jù)元素的關(guān)鍵字值大于要?jiǎng)h除結(jié)點(diǎn)數(shù)據(jù)元素關(guān)鍵字的最小值數(shù)據(jù)元素的關(guān)鍵字值大于要?jiǎng)h除結(jié)點(diǎn)數(shù)據(jù)元素關(guān)鍵字的最小值，即尋找要?jiǎng)h除結(jié)點(diǎn)右子樹(shù)的最左結(jié)點(diǎn)；然后把右子樹(shù)的最左，即尋找要?jiǎng)h除結(jié)點(diǎn)右子樹(shù)的最左結(jié)點(diǎn)；然后

15、把右子樹(shù)的最左結(jié)點(diǎn)的數(shù)據(jù)元素值拷貝到要?jiǎng)h除的結(jié)點(diǎn)上；最后刪除右子樹(shù)的結(jié)點(diǎn)的數(shù)據(jù)元素值拷貝到要?jiǎng)h除的結(jié)點(diǎn)上；最后刪除右子樹(shù)的最左結(jié)點(diǎn)。最左結(jié)點(diǎn)。刪除過(guò)程分別如圖所示刪除過(guò)程分別如圖所示1814245162038710303518142451620387303518142451620387103035181424516203071035ptrptr(a)無(wú)孩子結(jié)點(diǎn)無(wú)孩子結(jié)點(diǎn)(b)有左孩子結(jié)點(diǎn)有左孩子結(jié)點(diǎn)18142451620387103035181424716203810303518142451620387103035181430516207103538ptrptr(c)有右孩子結(jié)點(diǎn)有右孩子結(jié)點(diǎn)(

16、d)有左右孩子結(jié)點(diǎn)有左右孩子結(jié)點(diǎn)測(cè)試程序測(cè)試程序例例10-2 設(shè)計(jì)一個(gè)測(cè)試二叉排序樹(shù)的主函數(shù)。設(shè)計(jì)一個(gè)測(cè)試二叉排序樹(shù)的主函數(shù)。 # #include include #include #include #include #include typedef int KeyType;typedef int KeyType;typedef structtypedef struct KeyType key;KeyType key;DataType;DataType;typedef struct nodetypedef struct node DataType data;DataType data;str

17、uct node struct node * *leftChild;leftChild;struct node struct node * *rightChild;rightChild; BiTreeNode; BiTreeNode;#include “BiSortTree.h” #include “BiSortTree.h” void InTraverse(BiTreeNode void InTraverse(BiTreeNode * *root)root)/ /* *中序遍歷顯示二叉排序樹(shù)結(jié)點(diǎn)信息函數(shù)中序遍歷顯示二叉排序樹(shù)結(jié)點(diǎn)信息函數(shù)* */ / if(root = NULL) retur

18、n;if(root = NULL) return;if(root-leftChild != NULL)if(root-leftChild != NULL)InTraverse(root-leftChild);InTraverse(root-leftChild);printf(%d , root-data.key);printf(%d , root-data.key);if(root-rightChild != NULL)if(root-rightChild != NULL)InTraverse(root-rightChild);InTraverse(root-rightChild); void

19、 main(void)void main(void) DataType test = 4,5,7,2,1,9,8,11,3, x = 9;DataType test = 4,5,7,2,1,9,8,11,3, x = 9;int n = 9, i, s;int n = 9, i, s;BiTreeNode BiTreeNode * *root = NULL;root = NULL;for(i = 0; i n; i+)for(i = 0; i n; i+)Insert(&root, testi);Insert(&root, testi);InTraverse(root);InTraverse(

20、root);s = S e a r c h ( r o o t , x ) ;s = S e a r c h ( r o o t , x ) ;if(s = 1)if(s = 1)printf(nprintf(n數(shù)據(jù)元素?cái)?shù)據(jù)元素% %d d存在！存在！, , x.key);x.key);elseelseprintf(nprintf(n數(shù)據(jù)元素不存在！數(shù)據(jù)元素不存在！);); 程序運(yùn)行建立的二叉排序樹(shù)如圖程序運(yùn)行建立的二叉排序樹(shù)如圖10-510-5（i i）所示。程序運(yùn)行結(jié)果如下：所示。程序運(yùn)行結(jié)果如下：1 2 3 4 5 7 8 9 111 2 3 4 5 7 8 9 11 數(shù)據(jù)元素?cái)?shù)據(jù)元素9

21、存在！存在！ 六、二叉排序樹(shù)的性能分析六、二叉排序樹(shù)的性能分析 一棵二叉排序樹(shù)的平均查找長(zhǎng)度為：一棵二叉排序樹(shù)的平均查找長(zhǎng)度為：其中：其中：ni 是每層結(jié)點(diǎn)個(gè)數(shù)；是每層結(jié)點(diǎn)個(gè)數(shù)； Ci 是結(jié)點(diǎn)所在層次數(shù)；是結(jié)點(diǎn)所在層次數(shù)；m 為樹(shù)深。為樹(shù)深。當(dāng)二叉排序樹(shù)是一棵單分支退化樹(shù)時(shí)，查找成功的平均查找長(zhǎng)當(dāng)二叉排序樹(shù)是一棵單分支退化樹(shù)時(shí)，查找成功的平均查找長(zhǎng)度和有序順序表的平均查找長(zhǎng)度相同，即為：度和有序順序表的平均查找長(zhǎng)度相同，即為：=nininASL12/ ) 1(1成功若每個(gè)數(shù)據(jù)元素的查找概率相等，則二叉排序樹(shù)查找成功的平若每個(gè)數(shù)據(jù)元素的查找概率相等，則二叉排序樹(shù)查找成功的平均查找長(zhǎng)度為：均查找長(zhǎng)

22、度為： ) 1(log)2(1211=ninASLkii成功=miiiCnnASL113456781064835710(a)(b)（a）滿(mǎn)二叉排序樹(shù)時(shí)，滿(mǎn)二叉排序樹(shù)時(shí)，k = log2(7+1)=3，所以查找成功的平均查找長(zhǎng)度為：所以查找成功的平均查找長(zhǎng)度為： 717) 34221 (71)2(111=inASLiki成功（b）左分支退化二叉排序樹(shù)時(shí)，左分支退化二叉排序樹(shù)時(shí)，k = n=7，所以查找成功的平均查找長(zhǎng)度所以查找成功的平均查找長(zhǎng)度為：為： 42/ ) 17(2/ ) 1(11=nininASL成功在最壞情況下，二叉排序樹(shù)的平均查找長(zhǎng)度為在最壞情況下，二叉排序樹(shù)的平均查找長(zhǎng)度為O(n

23、)。在一般情在一般情況下，二叉排序樹(shù)的平均查找長(zhǎng)度為況下，二叉排序樹(shù)的平均查找長(zhǎng)度為O(log2n)。 2.B_樹(shù)樹(shù) B_ B_樹(shù)是一種平衡多叉排序樹(shù)。樹(shù)是一種平衡多叉排序樹(shù)。平衡是指所有葉結(jié)點(diǎn)都在同一平衡是指所有葉結(jié)點(diǎn)都在同一層上層上，從而可避免出現(xiàn)像二叉排序樹(shù)那樣的分支退化現(xiàn)象。因，從而可避免出現(xiàn)像二叉排序樹(shù)那樣的分支退化現(xiàn)象。因此此B_B_樹(shù)的動(dòng)態(tài)查找效率更高樹(shù)的動(dòng)態(tài)查找效率更高。B_B_樹(shù)中所有結(jié)點(diǎn)的孩子結(jié)點(diǎn)的最大值稱(chēng)為樹(shù)中所有結(jié)點(diǎn)的孩子結(jié)點(diǎn)的最大值稱(chēng)為B_B_樹(shù)的階樹(shù)的階，一棵一棵m階階的的B_樹(shù)或者是一棵空樹(shù)，或者是滿(mǎn)足下列要求的樹(shù)或者是一棵空樹(shù)，或者是滿(mǎn)足下列要求的m叉樹(shù)：叉樹(shù)：

24、(1)樹(shù)中每個(gè)結(jié)點(diǎn)至多有樹(shù)中每個(gè)結(jié)點(diǎn)至多有m個(gè)孩子結(jié)點(diǎn)。個(gè)孩子結(jié)點(diǎn)。(2)除根結(jié)點(diǎn)外，其他結(jié)點(diǎn)至少有除根結(jié)點(diǎn)外，其他結(jié)點(diǎn)至少有 m/2 個(gè)孩子結(jié)點(diǎn)（符號(hào)個(gè)孩子結(jié)點(diǎn)（符號(hào)“ ”表示上取整）。表示上取整）。(3)若根結(jié)點(diǎn)不是葉結(jié)點(diǎn)，則根結(jié)點(diǎn)至少有兩個(gè)孩子結(jié)點(diǎn)；若根結(jié)點(diǎn)不是葉結(jié)點(diǎn)，則根結(jié)點(diǎn)至少有兩個(gè)孩子結(jié)點(diǎn)；(4)每個(gè)結(jié)點(diǎn)的結(jié)構(gòu)為：每個(gè)結(jié)點(diǎn)的結(jié)構(gòu)為：nP0K1P1K2P2KnPn(5)(5)所有葉結(jié)點(diǎn)都在同一層上。所有葉結(jié)點(diǎn)都在同一層上。 1502041172214432330351151603778088 root一棵一棵4階階B_樹(shù)樹(shù)1. 查找算法查找算法 在在B_樹(shù)上查找數(shù)據(jù)元素樹(shù)上查找數(shù)據(jù)元

25、素x的方法為：將的方法為：將 x.key與根結(jié)點(diǎn)的與根結(jié)點(diǎn)的Ki逐個(gè)進(jìn)逐個(gè)進(jìn)行比較：行比較：（1）若）若x.key=Ki則查找成功。則查找成功。（2）若）若keyK1則沿著指針則沿著指針P0所指的子樹(shù)繼續(xù)查找。所指的子樹(shù)繼續(xù)查找。（3）若）若KikeyKn則沿著指針則沿著指針Pn所指的子樹(shù)繼續(xù)查找。所指的子樹(shù)繼續(xù)查找。2. 插入算法插入算法 插入過(guò)程分兩步完成：插入過(guò)程分兩步完成：（1 1）利用查找算法找出該關(guān)鍵字的插入結(jié)點(diǎn)（）利用查找算法找出該關(guān)鍵字的插入結(jié)點(diǎn)（B_B_樹(shù)的插入結(jié)點(diǎn)一樹(shù)的插入結(jié)點(diǎn)一定是葉結(jié)點(diǎn)定是葉結(jié)點(diǎn)）。）。（2 2）判斷該結(jié)點(diǎn)是否還有空位置，即判斷該結(jié)點(diǎn)是否滿(mǎn)足）判斷該結(jié)點(diǎn)

26、是否還有空位置，即判斷該結(jié)點(diǎn)是否滿(mǎn)足nm-1nm-1，若該結(jié)點(diǎn)滿(mǎn)足若該結(jié)點(diǎn)滿(mǎn)足nm-1ntableSize = mSize;hash-tableSize = mSize;hash-ht = (HashItem hash-ht = (HashItem * *)malloc(sizeof(HashItem)malloc(sizeof(HashItem)* *mSize);mSize);if(hash-ht = NULL) return 0;if(hash-ht = NULL) return 0;elseelse hash-currentSize = 0;hash-currentSize = 0;r

27、eturn 1;return 1; int Find(HashTable int Find(HashTable * *hash, DataType x)hash, DataType x) int i = x.key % hash-tableSize;int i = x.key % hash-tableSize;int j = i;int j = i;while( = Active & while( = Active & hash-htj.data.key != x.key)hash-htj.data.key != x.key) j = (j + 1) % hash-tableSize;j = (j + 1) % hash-tableSize;if(j = i) return -hash-tableSize;if(j = i) return -hash-tableSize; if( = Active) return j;if( = Active) return j;el