數(shù)據(jù)結(jié)構(gòu)查找課件

1、第11章 查找查找的基本概念靜態(tài)查找表動(dòng)態(tài)查找表哈希表主要知識(shí)點(diǎn)11.1 查找的基本概念 查找:查詢某個(gè)關(guān)鍵字是否在(數(shù)據(jù)元素集合）表中的過程。也 稱作檢索。主關(guān)鍵字:能夠惟一區(qū)分各個(gè)不同數(shù)據(jù)元素的關(guān)鍵字次關(guān)鍵字:通常不能惟一區(qū)分各個(gè)不同數(shù)據(jù)元素的關(guān)鍵字查找成功:在數(shù)據(jù)元素集合中找到了要查找的數(shù)據(jù)元素查找不成功:在數(shù)據(jù)元素集合中沒有找到要查找的數(shù)據(jù)元素=niiiCPASL1靜態(tài)查找:只查找，不改變數(shù)據(jù)元素集合內(nèi)的數(shù)據(jù)元素動(dòng)態(tài)查找:既查找，又改變（增減）集合內(nèi)的數(shù)據(jù)元素靜態(tài)查找表:靜態(tài)查找時(shí)構(gòu)造的存儲(chǔ)結(jié)構(gòu)動(dòng)態(tài)查找表:動(dòng)態(tài)查找時(shí)構(gòu)造的存儲(chǔ)結(jié)構(gòu)平均查找長度:查找過程所需進(jìn)行的關(guān)鍵字比較次數(shù)的平均值，

2、是衡量查找算法效率的最主要標(biāo)準(zhǔn)，其數(shù)學(xué)定義為： 其中，Pi是要查找數(shù)據(jù)元素出現(xiàn)的概率，Ci是查找相應(yīng)數(shù)據(jù)元素的比較次數(shù)。定義要查找數(shù)據(jù)元素的結(jié)構(gòu)體為：typedef struct KeyType key; DataType;11.2 靜態(tài)查找表 靜態(tài)查找表主要有三種結(jié)構(gòu)： 順序表 有序順序表 索引順序表1.順序表 在順序表上查找的基本思想是：從順序表的一端開始，用給定數(shù)據(jù)元素的關(guān)鍵字逐個(gè)和順序表中各數(shù)據(jù)元素的關(guān)鍵字比較，若在順序表中查找到要查找的數(shù)據(jù)元素，則查找成功，函數(shù)返回該數(shù)據(jù)元素在順序表中的位置；否則查找失敗，函數(shù)返回-1。 查找函數(shù)設(shè)計(jì)如下：int SeqSearch(DataType

3、 a, int n, KeyType key) int i = 0; while(i n & ai.key != key) i+; if(ai.key = key) return i; else return -1; 查找成功時(shí)的平均查找長度ASL為： 2.有序順序表 有序順序表上的查找算法主要有順序查找和折半查找兩種方法。一、順序查找 有序順序表上的順序查找算法和順序表上的查找算法方法類同 二、二分查找（又稱折半查找） 算法的基本思想：先給數(shù)據(jù)排序（例如按升序排好），形成有序表，然后再將key與正中元素值相比，若key小，則縮小至前半部內(nèi)查找；再取其中值比較，每次縮小1/2的范圍，直到查找成

4、功或失敗為止。反之，如果key大，則縮小至后半部內(nèi)查找。二分查找算法如下：int BiSearch(DataType a, int n, KeyType key) int low = 0, high = n - 1;/確定初始查找區(qū)間上下界 int mid; while(low = high) mid = (low + high)/2;/確定查找區(qū)間中心下標(biāo) if(amid.key = key) return mid;/查找成功 else if(amid.key data.key = item.key) return 1; if(item.key p-data.key) p = p-right

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

6、= current; if(current-data.key rightChild; else current = current-leftChild; /*生成新結(jié)點(diǎn)*/ p = (BiTreeNode *)malloc(sizeof(BiTreeNode); p-data = item; p-leftChild = NULL; p-rightChild = NULL; if(parent = NULL) *root = p; else if(item.key data.key) parent-leftChild = p; else parent-rightChild = p; return

7、 1; 下圖是調(diào)用上述插入函數(shù)依次插入數(shù)據(jù)元素4,5,7,2,1,9,8,11,3的過程。41152791384115279184527918452791452714527457454(d)(c)(b)(a)(g)(f)(e)(i)(h)五、刪除算法 刪除操作要求首先查找數(shù)據(jù)元素是否在二叉排序樹中存在，若不存在則結(jié)束；存在的情況及相應(yīng)的刪除方法有如下四種：(1)要?jiǎng)h除結(jié)點(diǎn)無孩子結(jié)點(diǎn)，直接刪除該結(jié)點(diǎn)。(2)要?jiǎng)h除結(jié)點(diǎn)只有左孩子結(jié)點(diǎn)，刪除該結(jié)點(diǎn)且使被刪除結(jié)點(diǎn)的雙親結(jié)點(diǎn)指向被刪除結(jié)點(diǎn)的左孩子結(jié)點(diǎn)。(3)要?jiǎng)h除結(jié)點(diǎn)只有右孩子結(jié)點(diǎn)，刪除該結(jié)點(diǎn)且使被刪除結(jié)點(diǎn)的雙親結(jié)點(diǎn)指向被刪除結(jié)點(diǎn)的右孩子結(jié)點(diǎn)。(4)要?jiǎng)h

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

9、r(c)有右孩子結(jié)點(diǎn)(d)有左右孩子結(jié)點(diǎn)例11-2 設(shè)計(jì)一個(gè)測(cè)試二叉排序樹的主函數(shù)。 #include #include #include typedef int KeyType;typedef struct KeyType key;DataType;typedef struct node DataType data; struct node *leftChild; struct node *rightChild; BiTreeNode;#include “BiSortTree.h” void InTraverse(BiTreeNode *root)/*中序遍歷顯示二叉排序樹結(jié)點(diǎn)信息函數(shù)*/

10、if(root = NULL) return; if(root-leftChild != NULL) InTraverse(root-leftChild); printf(%d , root-data.key); if(root-rightChild != NULL) InTraverse(root-rightChild);void main(void) DataType test = 4,5,7,2,1,9,8,11,3, x = 9; int n = 9, i, s; BiTreeNode *root = NULL; for(i = 0; i n; i+) Insert(&root, te

11、sti); InTraverse(root); s = Search(root, x); if(s = 1) printf(n數(shù)據(jù)元素%d存在！, x.key); else printf(n數(shù)據(jù)元素不存在！); 程序運(yùn)行建立的二叉排序樹如圖11-5（i）所示。程序運(yùn)行結(jié)果如下： 1 2 3 4 5 7 8 9 11 數(shù)據(jù)元素9存在！ 六、二叉排序樹的性能分析 一棵二叉排序樹的平均查找長度為：其中： C(i)為查找第i個(gè)數(shù)據(jù)元素時(shí)的關(guān)鍵字比較次數(shù) 當(dāng)二叉排序樹是一棵完全二叉樹時(shí)，二叉排序樹的平均查找長度為 ： 當(dāng)二叉排序樹是一棵單分支退化樹時(shí)，則平均查找長度就和有序順序表的平均查找長度相同，即為

12、 ：3456781064835710(a)(b)（a）滿二叉排序樹時(shí)，k = log2(7+1)=3，所以查找成功的平均查找長度為： （b）左分支退化二叉排序樹時(shí)，k = n=7，所以查找成功的平均查找長度為： 在最壞情況下，二叉排序樹的平均查找長度為O(n)。在一般情況下，二叉排序樹的平均查找長度為O(log2n)。 為了防止二叉排序樹的最壞情況出現(xiàn)，可以把二叉排序樹改造成平衡二叉樹。 平衡二叉樹或者是一棵空樹，或者是具有這樣性質(zhì)的二叉排序樹：它的左子樹和右子樹都是二叉排序樹，并且左子樹和右子樹的深度之差的絕對(duì)值不超過1。 基本方法：就是在構(gòu)造二叉排序樹的基礎(chǔ)上，每當(dāng)如果插入了一個(gè)新結(jié)點(diǎn)后，

13、使二叉樹中某個(gè)結(jié)點(diǎn)的左子樹和右子樹的深度之差的絕對(duì)值超過1，則調(diào)整相應(yīng)的二叉樹，使二叉樹中該結(jié)點(diǎn)的左子樹和右子樹的深度之差的絕對(duì)值不超過1。 特點(diǎn)：平衡二叉樹一定不會(huì)出現(xiàn)單分支退化二叉排序樹那樣的情況，因此，平衡二叉樹的平均查找長度為O(lbn)。但相對(duì)二叉排序樹來說，構(gòu)造平衡二叉樹需要花費(fèi)較多的時(shí)間，而且刪除平衡二叉樹中某個(gè)結(jié)點(diǎn)時(shí)，也要考慮刪除某個(gè)結(jié)點(diǎn)后，平衡二叉樹中某個(gè)結(jié)點(diǎn)的左子樹和右子樹的深度之差的絕對(duì)值不能超過1。 七、平衡二叉樹1 B_樹 B_樹是一種平衡多叉排序樹。平衡是指所有葉結(jié)點(diǎn)都在同一層上，從而可避免出現(xiàn)像二叉排序樹那樣的分支退化現(xiàn)象。因此B_樹的動(dòng)態(tài)查找效率更高。 B_樹中

14、所有結(jié)點(diǎn)的孩子結(jié)點(diǎn)的最大值稱為B_樹的階，一棵m階的B_樹或者是一棵空樹，或者是滿足下列要求的m叉樹：11.3.2 B_樹和B+樹(1)樹中每個(gè)結(jié)點(diǎn)至多有m個(gè)孩子結(jié)點(diǎn)。(2)除根結(jié)點(diǎn)外，其他結(jié)點(diǎn)至少有m/2個(gè)孩子結(jié)點(diǎn) （符號(hào)“ ”表示上取整）。(3)若根結(jié)點(diǎn)不是葉結(jié)點(diǎn)，則根結(jié)點(diǎn)至少有兩個(gè)孩子結(jié)點(diǎn)；(4)每個(gè)結(jié)點(diǎn)的結(jié)構(gòu)為：nP0K1P1K2P2KnPn(5)所有葉結(jié)點(diǎn)都在同一層上。 1502041172214432330351151603778088 root一棵4階B_樹 B_樹的查找算法 在B_樹上查找數(shù)據(jù)元素x的方法為：將 x.key與根結(jié)點(diǎn)的Ki逐個(gè)進(jìn)行比較：（1）若x.key=Ki則查

15、找成功。（2）若keyK1則沿著指針P0所指的子樹繼續(xù)查找。（3）若KikeyKn則沿著指針Pn所指的子樹繼續(xù)查找。（5）若相應(yīng)Pi指針為空，則查找失敗。插入過程分兩步完成：（1）利用查找算法找出該關(guān)鍵字的插入結(jié)點(diǎn)（B_樹的插入結(jié)點(diǎn)一定是葉結(jié)點(diǎn)）。（2）判斷該結(jié)點(diǎn)是否還有空位置，即判斷該結(jié)點(diǎn)是否滿足nm-1，若該結(jié)點(diǎn)滿足ntableSize = mSize; hash-ht = (HashItem *)malloc(sizeof(HashItem)*mSize); if(hash-ht = NULL) return 0; else hash-currentSize = 0; return 1;

16、 int Find(HashTable *hash, DataType x) int i = x.key % hash-tableSize; int j = i; while( = Active & hash-htj.data.key != x.key) j = (j + 1) % hash-tableSize; if(j = i) return -hash-tableSize; if( = Active) return j;/成功返回j else return -j;/失敗返回- jinto Insert(HashTable *hash, DataType x) int i = Find(hash, x); if(i 0) return 0; else if(i != -hash-tableSize) hash-ht-i.data = x; = Active; hash-currentSize+; return 1; else return 0;int Delete(HashTa