查找的基本概念(2).ppt課件

1、第八章 查找1查找的基本概念備注2概念查找表查找操作針對的數(shù)據(jù)集，由同一類型的數(shù)據(jù)元素組成關(guān)鍵字(key)數(shù)據(jù)元素中某個(gè)數(shù)據(jù)項(xiàng)的值，可唯一標(biāo)識該數(shù)據(jù)元素關(guān)鍵字和數(shù)據(jù)元素的類型說明，如typedef float KeyType; /實(shí)型typedef int KeyType; /整型typedef char *KeyType; /字符串型typedef struct KeyType key; /關(guān)鍵字域 /其它域ElemType;3概念查找在查找表中根據(jù)關(guān)鍵字找出特定的數(shù)據(jù)元素的操作查找成功關(guān)鍵字找到，返回對應(yīng)數(shù)據(jù)元素在查詢表中的位置查找失敗關(guān)鍵字沒有找到，返回空記錄或空指針關(guān)鍵字比較的宏定義/

2、對數(shù)值類型關(guān)鍵字#define EQ(a,b) (a) = (b)#define LT(a,b) (a) (b)#define LQ(a,b) (a) = (b)/對字符串類型關(guān)鍵字#define EQ(a,b) (!strcmp(a), (b)#define LT(a,b) (strcmp(a), (b) 0)#define LQ(a,b) (strcmp(a), (b) = 0)4概念查找算法取決于查找表的數(shù)據(jù)結(jié)構(gòu)靜態(tài)查找表查找表事先已確定對查詢表除了創(chuàng)建和銷毀操作外，只有查找或遍歷操作動態(tài)查找表查找表本身在查找過程中動態(tài)生成，即若沒有找到，則插入該元素對查詢表除了創(chuàng)建、銷毀、查找、遍歷操

3、作外，還能進(jìn)行插入和刪除操作5一些約定典型的關(guān)鍵字類型說明：typedef float KeyType;/實(shí)型typedef int KeyType;/整型typedef char *KeyType;/字符串型數(shù)據(jù)元素類型定義為：typedef structKeyType key; / 關(guān)鍵字域.ElemType; 6對兩個(gè)關(guān)鍵字的比較約定為如下的宏定義：對數(shù)值型關(guān)鍵字#define EQ(a,b) (a)=(b)#define LT(a,b) (a)(b)#define LQ(a,b) (a)=(b)對字符串型關(guān)鍵字#define EQ(a,b) (!strcmp(a),(b)#define

4、 LT(a,b) (strcmp(a),(b)0)#define LQ(a,b) (strcmp(a),(b)=0)79.1靜態(tài)表查找順序表的查找有序表的查找索引順序表的查找8靜態(tài)查找表的類型定義：ADT StaticSearchTable數(shù)據(jù)對象D：D是具有相同特性的數(shù)據(jù)元素的集合。各個(gè)數(shù)據(jù)元素均含有類型相同，可唯一標(biāo)識數(shù)據(jù)元素的關(guān)鍵字。數(shù)據(jù)關(guān)系R：數(shù)據(jù)元素同屬一個(gè)集合?；静僮鱌：9Create(&ST,n);操作結(jié)果：構(gòu)造一個(gè)含n個(gè)數(shù)據(jù)元素的靜態(tài)查找表ST。Destroy(&ST);初始條件：靜態(tài)查找表ST存在。操作結(jié)果：銷毀表ST。Search(ST,key);初始條件：靜態(tài)查找表ST

5、存在，key為和關(guān)鍵字類型相同的給定值。操作結(jié)果：若ST中在在其關(guān)鍵字等于key的數(shù)據(jù)元素，則函數(shù)值為該元素的值或在表中的位置，否則為“空”。Traverse(ST,Visit();初始條件：靜態(tài)查找表ST存在，Visit是對元素操作的應(yīng)用函數(shù)。操作結(jié)果：按某種次序?qū)T的每個(gè)元素調(diào)用函數(shù)visit()一次且僅一次。一旦visit()失敗，則操作失敗。ADT StaticSearchTable109.1.1順序表的查找順序查找：從表中最后一個(gè)記錄開始，逐個(gè)進(jìn)行記錄的關(guān)鍵字和給定值的比較，若某個(gè)記錄的關(guān)鍵字和給定值比較相等，則查找成功，找到所查記錄；反之，查找不成功。11靜態(tài)查找表的順序存儲結(jié)構(gòu)

6、typedef struct ElemType *elem;int length;SSTable;int Search_Seq(SSTable ST,KeyType key)ST.elme0.key=key;for(i=ST.length; !EQ(ST.elemi.key,key); -i);return i;查找算法12查找操作的性能分析：查找算法中的基本操作是將記錄的關(guān)鍵字和給定值進(jìn)行比較，通常以“其關(guān)鍵字和給定值進(jìn)行過比較的記錄個(gè)數(shù)的平均值”作為衡量依據(jù)。平均查找長度 Average Search Length：為確定記錄在查找表中的位置，需用和給定值進(jìn)行比較的關(guān)鍵字個(gè)數(shù)的期望值稱為查

7、找算法在查找成功時(shí)的平均查找長度。13 其中：Pi為查找表中第i個(gè)記錄的概率，且 ；Ci為找到表中其關(guān)鍵字與給定值相等的第i個(gè)記錄時(shí)，和給定值已進(jìn)行過比較的關(guān)鍵字個(gè)數(shù)。 等概率條件下有： 假設(shè)查找成功與不成功的概率相同： 149.1.2靜態(tài)查找表（二）有序表的查找折半查找的查找過程以有序表表示靜態(tài)查找表時(shí)，Search函數(shù)可用折半查找來實(shí)現(xiàn)。先確定待查記錄所在的范圍（區(qū)間），然后逐步縮小范圍直到找到或找不到該記錄為止。 15折半查找的查找實(shí)現(xiàn)int Search_Bin(SSTable ST,KeyType key)low=1;high=ST.length;while(lowdata.key)

8、 return (T); else if (LT(key, T-data.key) return (SearchBST(T-lchild, key); elsereturn (SearchBST(T-rchild, key);29二叉排序樹二叉排序樹的查找算法二(考慮查找失敗后將插入記錄，插入的記錄將成為一個(gè)新的葉子結(jié)點(diǎn)，故需在查找過程中預(yù)留插入位置)Status SearchBST(BiTree T, KeyType key, BiTree f, BiTree &p) /在根指針T所指二叉排序樹中遞歸地查找某關(guān)鍵字等于key的數(shù)據(jù)元素，/若查找成功則p指向該數(shù)據(jù)元素結(jié)點(diǎn)，并返回TRUE，否則

9、指針p指向查/找路徑上訪問的最后一個(gè)結(jié)點(diǎn)(一定是一個(gè)葉子結(jié)點(diǎn))并返回FALSE，/指針f指向T的雙親，其初始調(diào)用值為NULL if (!T) p = f; return FALSE; else if (EQ(key, T-data.key) p = T; return TRUE; else if (LT(key, T-data.key) SearchBST(T-lchild, key, T, p); else SearchBST(T-rchild, key, T, p);30二叉排序樹的插入(創(chuàng)建)算法Status InsertBST(BiTree &T, ElemType e) /當(dāng)二叉排序

10、樹T中不存在關(guān)鍵字等于e.key的數(shù)據(jù)元素時(shí)，/插入e并返回TRUE，否則返回FALSE if (!SearchBST(T, e.key, NULL, p) /查找不成功 s = (BiTree)malloc(sizeof(BiNode); s-data = e; s-lchild = s-rchild = NULL; /新的葉子結(jié)點(diǎn) if (!p) T = s; else if (LT(e.key, p-data.key) p-lchild = s; else p-rchild = s; return TRUE; else return FALSE; 從空樹開始，經(jīng)過一系列查找插入操作后，可

11、生成一棵二叉排序樹31例一：假設(shè)查找的關(guān)鍵序列為45,24,53,45,12,24,90，則生成二叉排序樹的過程如下圖所示：454524452453452453124524531290abcde32例二：假設(shè)查找的關(guān)鍵序列為27,32,16,27,14,16,27，則生成二叉排序樹的過程如下圖所示：abcd2727322716322716321433二叉排序樹二叉排序樹的特點(diǎn)中序遍歷二叉排序樹可得到一個(gè)關(guān)鍵字的有序序列（即：可以通過輸入一個(gè)無序序列，而通過構(gòu)造二叉排序樹后進(jìn)行遍歷的方法實(shí)現(xiàn)排序）二叉排序樹的插入過程不需要移動其他記錄具有相同n個(gè)結(jié)點(diǎn)的二叉排序樹會因?yàn)闃?gòu)造的時(shí)候關(guān)鍵字插入的順序不

12、同而不同(下頁說明)二叉排序樹的查找算法具有折半查找的特性，同時(shí)又采用了鏈?zhǔn)酱鎯Y(jié)構(gòu)，因此是動態(tài)查找表的適宜表示34如：查找的關(guān)鍵序列分別為27,32,16,14、16,14,27,32和14,16,27, 32, 生成二叉排序樹分別如下：27163214161427321416273235例 找 1004036在二叉排序樹中刪除一個(gè)節(jié)點(diǎn)的算法Status DeleteBST(BiTree &T,KeyType key)if(!T) return FALSE;elseif EQ(key,T-data.key) Delete(T);else if LT(key,T-data.key) Delet

13、eBST(T-lchild,key);else DeleteBST(T-rchild,key);return TRUE;37void Delete(BiTree &p)if(!p-rchild)q=p; p=p-lchild; free(q);else if(!p-lchild)q=p;p=p-rchild; free(q);else/左右子樹都不空/方法一：如圖示q=p;s=p-lchild;while(s-rchild)q=s;s=s-rchild/轉(zhuǎn)左，然后向右到盡頭p-data=s-data; /s指向被刪結(jié)點(diǎn)的前驅(qū)if(q!=p)q-rchild=s-lchild; /重接*q的右子

14、樹else q-lchild=s-lchild;/重接*q的左子樹 （方法一結(jié)束）38q=p;s=p-lchild;while(s-rchild)q=s;s=s-rchild/轉(zhuǎn)左，然后向右到盡頭p-data=s-data; /s指向被刪結(jié)點(diǎn)的前驅(qū)if(q!=p)q-rchild=s-lchild; /重接*q的右子樹else q-lchild=s-lchild;/重接*q的左子樹 （方法一結(jié)束）39/或可用方法二：/q=s=(*p)-lchild; /while(s-rchild) s=s-rchild; /s-rchild=(*p)-rchild; /free(*p); /(*p)=q;

15、40二叉排序樹的查找分析最差情況最好情況平均性能419.3 哈希(Hash)表一般的線性表，樹中，記錄在結(jié)構(gòu)中的相對位置是隨機(jī)的，即和記錄的關(guān)鍵字之間不存在確定的關(guān)系，因此，在結(jié)構(gòu)中查找記錄時(shí)需進(jìn)行一系列和關(guān)鍵字的比較。這一類查找方法建立在“比較“的基礎(chǔ)上，查找的效率依賴于查找過程中所進(jìn)行的比較次數(shù)。 理想的情況是能直接找到需要的記錄，因此必須在記錄的存儲位置和它的關(guān)鍵字之間建立一個(gè)確定的，使每個(gè)關(guān)鍵字和結(jié)構(gòu)中一個(gè)唯一的存儲位置相對應(yīng)。稱對應(yīng)關(guān)系f就是哈希函數(shù)42哈希表最常見的例子是以學(xué)生學(xué)號為關(guān)鍵字的成績表，號學(xué)生的記錄位置在第一條，號學(xué)生的記錄位置在第條.如果我們以學(xué)生姓名為關(guān)鍵字，如何建

16、立查找表，使得根據(jù)姓名可以直接找到相應(yīng)記錄呢？abcdefghijklmnopqrstuvwxyz1234567891011121314151617181920212223242526劉麗劉宏英吳軍吳小艷李秋梅陳偉.姓名中各字拼音首字母lllhywjwxylqmcw.用所有首字母編號值相加求和244633724226.最小值可能為3 最大值可能為78 可放75個(gè)學(xué)生用上述得到的數(shù)值作為對應(yīng)記錄在表中的位置，得到下表：用上述得到的數(shù)值作為對應(yīng)記錄在表中的位置，得到下表：43：成績一成績二.3.24劉麗829525.26陳偉.33吳軍.42李秋梅.46劉宏英.72吳小艷.78.上面這張表即哈希表。

17、如果將來要查李秋梅的成績，可以用上述方法求出該記錄所在位置：李秋梅:lqm 12+17+13=42 取表中第42條記錄即可。問題：如果兩個(gè)同學(xué)分別叫 劉麗 劉蘭 該如何處理這兩條記錄？這個(gè)問題是哈希表不可避免的，即沖突現(xiàn)象：對不同的關(guān)鍵字可能得到同一哈希地址。44Hash表又稱散列表Hash函數(shù)建立關(guān)鍵字值集合到存儲地址集合的映射關(guān)系即：記錄的存儲位置loc = h(key)Hash表所有記錄按Hash思想組成而成的表優(yōu)點(diǎn)：根據(jù)key值，查找時(shí)不必經(jīng)過多次key值比較就可以一次定位，直接找到所查找的記錄問題：hash函數(shù)的選擇非常重要，如果不同的key值可能得到相同的loc，那末就存在存儲位置

18、沖突的問題Hash函數(shù)順序表下標(biāo)值等45哈希(Hash)表如：hash函數(shù)h(key) = key mod 10, 記錄集合為No. Name Class Zhang c1 Liu c2 Wang c1 Li c3則Hash表為10 Li c312 Liu c24 Wang c15 Zhang c301234567lockey46哈希(Hash)表沖突問題不同key值對應(yīng)的hash函數(shù)值(地址值)相同沖突產(chǎn)生的原因通常hash表的大小小于key值集合的大小Hash函數(shù)構(gòu)造不合理建立hash表時(shí)需要重要考慮的是設(shè)定好的hash函數(shù)，使hash值盡可能均勻分布建立相應(yīng)的沖突處理方法(沖突不可避免，

19、力求盡量減少)47二、哈希表的構(gòu)造方法直接定址法 數(shù)字分析法平方取中法折疊法除留余數(shù)法 隨機(jī)數(shù)法 48例如：有一個(gè)從1到100歲的人口數(shù)字統(tǒng)計(jì)表，其中，年齡作為關(guān)鍵字，哈希函數(shù)取關(guān)鍵字自身。地址0102.252627.100年齡12.252627.人數(shù)30002000.1050.、直接定址法49、數(shù)字分析法有學(xué)生的生日數(shù)據(jù)如下：年.月.日75.10.0375.11.2376.03.0276.07.1275.04.2176.02.15.經(jīng)分析,第一位，第二位，第三位重復(fù)的可能性大，取這三位造成沖突的機(jī)會增加，所以盡量不取前三位，取后三位比較好。50、平方取中法取關(guān)鍵字平方后的中間幾位為哈希地址。

20、Fig.9.2351將關(guān)鍵字分割成位數(shù)相同的幾部分（最后一部分的位數(shù)可以不同），然后取這幾部分的疊加和（舍去進(jìn)位）作為哈希地址，這方法稱為折疊法。例如：每一種西文圖書都有一個(gè)國際標(biāo)準(zhǔn)圖書編號，它是一個(gè)10位的十進(jìn)制數(shù)字，若要以它作關(guān)鍵字建立一個(gè)哈希表，當(dāng)館藏書種類不到10,000時(shí)，可采用此法構(gòu)造一個(gè)四位數(shù)的哈希函數(shù)。如果一本書的編號為0-442-20586-4,則：5864586442200224+)04+)04-100886092H(key)=0088H(key)=6092(a)移位疊加(b)間界疊加、折疊法52、除留余數(shù)法取關(guān)鍵字被某個(gè)不大于哈希表表長m的數(shù)p除后所得余數(shù)為哈希地址。H(

21、key)=key MOD p (p=m)53、隨機(jī)數(shù)法選擇一個(gè)隨機(jī)函數(shù)，取關(guān)鍵字的隨機(jī)函數(shù)值為它的哈希地址，即H(key)=random(key) ,其中random為隨機(jī)函數(shù)。通常用于關(guān)鍵字長度不等時(shí)采用此法。54二、處理沖突的方法成績一成績二.3.24劉麗829525.26陳偉.33吳軍.42李秋梅.46劉宏英.72吳小艷.78.如果兩個(gè)同學(xué)分別叫 劉麗 劉蘭，當(dāng)加入劉蘭時(shí)，地址24發(fā)生了沖突，我們可以以某種規(guī)律使用其它的存儲位置，如果選擇的一個(gè)其它位置仍有沖突，則再選下一個(gè)，直到找到?jīng)]有沖突的位置。選擇其它位置的方法有：55選擇其它位置的方法有：開放定址法再哈希法鏈地址法建立一個(gè)公共溢出

22、區(qū)56、開放定址法Hi=(H(key)+di) MOD m i=1,2,.,k(k=m-1)其中m為表長，di為增量序列如果di值可能為1,2,3,.m-1，稱線性探測再散列。如果di取值可能為1,-1,2,-2,4,-4,9,-9,16,-16,.k*k,-k*k(k=m/2)稱二次探測再散列。如果di取值可能為偽隨機(jī)數(shù)列。稱偽隨機(jī)探測再散列。Hi = (H(key)+di)mod m di =偽隨機(jī)數(shù)序列57例：在長度為11的哈希表中已填有關(guān)鍵字分別為17, 60, 29的記錄， H(key) = key MOD 11現(xiàn)有第四個(gè)記錄，其關(guān)鍵字為38，由哈希函數(shù)得到地址為5，若用線性探測再散

23、列，如下：012345678910601729(a)插入前01234567891060172938(b)線性探測再散列58012345678910601729(a)插入前01234567891038601729(c)二次探測再散列01234567891038601729(d)偽隨機(jī)探測再散列偽隨機(jī)數(shù)列為9,5,3,8,1.59、再哈希法當(dāng)發(fā)生沖突時(shí)，使用第二個(gè)、第三個(gè)、哈希函數(shù)計(jì)算地址，直到無沖突時(shí)。缺點(diǎn)：計(jì)算時(shí)間增加。60、鏈地址法將所有關(guān)鍵字為同義詞的記錄存儲在同一線性鏈表中012345678910111201 14 27 79 55 68 19 84 10 23 20 11 已知一組關(guān)鍵

24、字為19,14,23,01,68,20,84,27,55,11,10,79，則按hash函數(shù)H(key) = key mod 13和鏈地址法處理沖突構(gòu)造所得的hash表為：61、建立一個(gè)公共溢出區(qū)假設(shè)哈希函數(shù)的值域?yàn)?,m-1,則設(shè)向量HashTable0.m-1為基本表，另外設(shè)立存儲空間向量OverTable0.v用以存儲發(fā)生沖突的記錄。62三、哈希表的查找/開放定址哈希表的存儲結(jié)構(gòu)int hashsize=997,.;typedef structElemType *elem;int count;int sizeindex;HashTable;63#define SUCCESS 1#defi

25、ne UNSUCCESS 0#define DUPLICATE -1Status SearchHash(HashTable H,KeyType K,int &p,int &c)p=Hash(K);while(H.elemp.key!=NULLKEY & !EQ(K,H.elemp.key)collision(p,+c);if(EQ(K,H.elemp.key)return SUCCESS;else return UNSUCCESS;64Status InsertHash(HashTable &H,EleType e)c=0;if(SearchHash(H,e.key,p,c)return DUPLICATE;else if(chashsizeH.sizeindex/2)H.elemp=e; +H.count; return OK;else RecreateHashTable(H);65Example 9.3Key: