數據結構第九部分查找ppt課件

1、中國科大C+程序設計實習 數據結構課程本章內容9.1 查找的根本概念9.2 靜態(tài)查找表9.3 動態(tài)查找表9.4 哈希表中國科大數據結構9.1 查找的根本概念中國科大數據結構9.1 查找的根本概念中國科大數據結構9.1 查找的根本概念中國科大數據結構9.2 靜態(tài)查找表中國科大數據結構9.2 靜態(tài)查找表中國科大數據結構9.2 靜態(tài)查找表監(jiān)視哨兵監(jiān)視哨兵i=11i=7,找到找到i=8i=9i=10比較次數比較次數=5比較次數分析：比較次數分析：查找第查找第n n個元素：個元素： 1 1次次查找第查找第n-1n-1個元素：個元素： 2 2次次.查找第查找第1 1個元素：個元素： n n次次查找第查找第

2、i i個元素：個元素： n+1-i n+1-i次次查找失?。翰檎沂。?n+1 n+1次次 0 1 2 3 4 5 6 7 8 9 10 1162513192137566275808892中國科大數據結構9.2 靜態(tài)查找表中國科大數據結構9.2 靜態(tài)查找表中國科大數據結構9.2 靜態(tài)查找表中國科大數據結構9.2 靜態(tài)查找表1 2 3 4 5 6 7 8 9 10 11513192137566275808892low=1mid=6high=11第一步：第一步：low=1, high=11, mid=6 STmid=ST6=5662, 那么改動那么改動high；第三步：第三步：high=mid-1

3、=8, mid=7 high=8mid=7STmid=ST7=62=62, 找到！找到！62中國科大數據結構9.2 靜態(tài)查找表1 2 3 4 5 6 7 8 9 10 11513192137566275808892high=6low=7找找61u 當下界當下界lowlow大于上界大于上界highhigh時，闡明有序時，闡明有序u 表中沒有關鍵字等于表中沒有關鍵字等于K K的元素，查找失敗的元素，查找失敗中國科大數據結構9.2 靜態(tài)查找表3941756102118斷定樹斷定樹中國科大數據結構9.2 靜態(tài)查找表中國科大數據結構9.2 靜態(tài)查找表中國科大數據結構9.2 靜態(tài)查找表 1 2 3 4 5

4、 6 7 8 9 10 11519132175566237888092211755929主表主表索引表索引表中國科大數據結構9.2 靜態(tài)查找表1 2 3 4 5 6 7 8 9 10 11519132175566237888092211755929主表主表索引表索引表找找62中國科大數據結構9.2 靜態(tài)查找表中國科大數據結構9.3 動態(tài)查找表中國科大數據結構9.3 動態(tài)查找表21二叉排序樹二叉排序樹非二叉排序樹非二叉排序樹56645923788198021137560566459237881980211375中國科大數據結構9.3 動態(tài)查找表566459237881980211375例例1：在

5、右圖二叉排序樹中查找關鍵字值等于：在右圖二叉排序樹中查找關鍵字值等于3737找到找到例例2：在右圖二叉排序樹中查找關鍵字值等于：在右圖二叉排序樹中查找關鍵字值等于88找到找到例例3：在右圖二叉排序樹中查找關鍵字值等于：在右圖二叉排序樹中查找關鍵字值等于94無此數無此數中國科大數據結構9.3 動態(tài)查找表56645923788198021137594中國科大數據結構9.3 動態(tài)查找表566492888075中國科大數據結構9.3 動態(tài)查找表566459237881980211375中國科大數據結構9.3 動態(tài)查找表中國科大數據結構9.3 動態(tài)查找表566459237881980211375中國科大

6、數據結構9.3 動態(tài)查找表566453719211392888075中國科大數據結構9.3 動態(tài)查找表566459237888019211375中國科大數據結構9.3 動態(tài)查找表808892647521191356375中國科大數據結構9.3 動態(tài)查找表808892647521191356375中國科大數據結構9.3 動態(tài)查找表56645923788198021137560565641913753780928821AVLAVL樹樹非非AVLAVL樹樹中國科大數據結構9.3 動態(tài)查找表56564191375378092882100-10-1000100中國科大數據結構9.3 動態(tài)查找表中國科大數

7、據結構9.3 動態(tài)查找表CBA210CBA000中國科大數據結構9.3 動態(tài)查找表CBA210CBA000CBA2-10中國科大數據結構9.3 動態(tài)查找表CBA-2-10CBA000中國科大數據結構9.3 動態(tài)查找表CBA-2-10CBA000ACB-210中國科大數據結構9.3 動態(tài)查找表40插入插入4，平衡，平衡4-1b) 插入插入5，平衡，平衡50c) 插入插入7，不平衡，要處置，不平衡，要處置4-25-170405070RR型處置型處置中國科大數據結構9.3 動態(tài)查找表405170d) 插入插入7，平衡，平衡2141527022e) 插入插入1，不平衡，要處置，不平衡，要處置10405

8、0702010LL型處置型處置4052702-111f) 插入插入3，不平衡，要處置，不平衡，要處置30LR型處置型處置30405-1201070中國科大數據結構9.3 動態(tài)查找表304-15-2201071f) 插入插入6，不平衡，要處置，不平衡，要處置06RL型處置型處置30406020107050中國科大數據結構9.3 動態(tài)查找表中國科大數據結構9.3 動態(tài)查找表3462175平衡二叉樹平衡二叉樹3452176二叉排序樹二叉排序樹從右圖的二叉排序樹可知，查找從右圖的二叉排序樹可知，查找6 6需需4 4次，平均查找長度次，平均查找長度ASL=(1+2+2+3+3+3+4)/7=18/72.

9、57ASL=(1+2+2+3+3+3+4)/7=18/72.57從左圖的平衡二叉樹可知，查找從左圖的平衡二叉樹可知，查找6 6需需2 2次，平均查找長度次，平均查找長度ASL=(1+2+2+3+3+3+3)=17/72.43ASL=(1+2+2+3+3+3+3)=17/72.43從結果可知，平衡二叉樹的查找性能優(yōu)于二叉排序樹。從結果可知，平衡二叉樹的查找性能優(yōu)于二叉排序樹。中國科大數據結構9.4 哈希表中國科大數據結構9.4 哈希表中國科大數據結構9.4 哈希表中國科大數據結構9.4 哈希表中國科大數據結構9.4 哈希表中國科大數據結構9.4 哈希表中國科大數據結構9.4 哈希表中國科大數據結

10、構9.4 哈希表8 1 3 4 6 5 3 28 1 3 4 6 5 3 28 1 3 7 2 2 4 28 1 3 7 2 2 4 28 1 3 8 7 4 2 28 1 3 8 7 4 2 28 1 3 0 1 3 6 78 1 3 0 1 3 6 78 1 3 2 2 8 1 7 8 1 3 2 2 8 1 7 8 1 3 3 8 9 6 78 1 3 3 8 9 6 78 1 3 6 8 5 3 78 1 3 6 8 5 3 78 1 4 1 9 3 5 58 1 4 1 9 3 5 5 分析：分析：只取只取8 8 只取只取1 1 只取只取3 3、4 4 只取只取2 2、7 7、5 5

11、 數字分布近乎隨機數字分布近乎隨機所以：取所以：取恣意兩位或兩位恣意兩位或兩位與另兩位的疊加作哈希地址與另兩位的疊加作哈希地址中國科大數據結構9.4 哈希表中國科大數據結構9.4 哈希表中國科大數據結構9.4 哈希表中國科大數據結構9.4 哈希表中國科大數據結構9.4 哈希表中國科大數據結構9.4 哈希表5 8 6 44 2 2 00 41 0 0 8 8H(key)=0088移位疊加移位疊加5 8 6 40 2 2 40 4 6 0 9 2H(key)=6092間界疊加間界疊加中國科大數據結構9.4 哈希表中國科大數據結構9.4 哈希表中國科大數據結構9.4 哈希表中國科大數據結構9.4 哈

12、希表中國科大數據結構9.4 哈希表0 1 2 3 4 5 6 7 8 9 60 17 29 (a)插入前 60 17 29 38(b) 線性探測再散列線性探測再散列 38 60 17 29 (c) 二次探測再散列二次探測再散列60 17 29 38 (d) 偽隨機探測再散列 用開放定址處置沖突時，關鍵字為用開放定址處置沖突時，關鍵字為3838的記錄插入前后的哈希表的記錄插入前后的哈希表 中國科大數據結構9.4 哈希表中國科大數據結構9.4 哈希表012345678910190114556811823623中國科大數據結構9.4 哈希表012345678910192336116855821401

13、中國科大數據結構9.4 哈希表#define LEN 31/ 表長表長LEN最好為質數最好為質數typedef struct node int data; struct node *next; node;struct node HashTabLEN;中國科大數據結構9.4 哈希表int hash(int key) retAddr = key MOD LEN; return(retAddr);給定給定k值值計算計算hash(key)此地址為空此地址為空關鍵字關鍵字=key查找失敗前往查找失敗前往或插入新結點或插入新結點查找勝利查找勝利按處置沖突方法按處置沖突方法計算下一地址計算下一地址YNYN中國科大數據結構9.4 哈希表node *search(int key) i = hash(key);p = Has