預(yù)備知識(shí)81靜態(tài)查找表82動(dòng)態(tài)查找表83哈希表.ppt

1,預(yù)備知識(shí) 8.1 靜態(tài)查找表 8.2 動(dòng)態(tài)查找表 8.3 哈希表,第8章 查找,2,本章重點(diǎn)難點(diǎn),重點(diǎn)：順序查找、二分查找、二叉排序樹查找以 及散列表查找的基本思想和算法實(shí)現(xiàn)。,難點(diǎn)：二叉排序樹的刪除算法和平衡二叉樹的 構(gòu)造算法。,3,預(yù)備知識(shí) 8.1 靜態(tài)查找表 8.2 動(dòng)態(tài)查找表 8.3 哈希表,第8章 查找,4,(1) 查找表：,(2) 靜態(tài)查找表：,是由同一類型的數(shù)據(jù)元素(或記錄)構(gòu)成的集合。,僅作查詢和檢索操作的查找表。,有關(guān)概念,(3) 動(dòng)態(tài)查找表：,在查找時(shí)包含插入、刪除或修改。,預(yù)備知識(shí),5,(4) 主關(guān)鍵字,(5) 次關(guān)鍵字,可以識(shí)別唯一的一個(gè)記錄的數(shù)據(jù)項(xiàng)（字段）。,關(guān)聯(lián)若干項(xiàng)記錄的數(shù)據(jù)項(xiàng)（字段）。,(6) 查找,根據(jù)給定的某個(gè)值，在查找表中確定一個(gè)其關(guān)鍵字 等于給定值的數(shù)據(jù)元素或（記錄）。,有關(guān)概念,預(yù)備知識(shí),6,(7) 查找成功,(8) 查找不成功,查找表中存在滿足條件的記錄。,查找表中不存在滿足條件的記錄。,有關(guān)概念,預(yù)備知識(shí),7,typedef float Keytype; /Keytype定義為浮點(diǎn)數(shù)據(jù)類型 typedef int Keytype; /Keytype定義為整型數(shù)據(jù)類型 typedef char *Keytype; /Keytype定義為字符指針數(shù)據(jù)類型,類型定義,預(yù)備知識(shí),8,數(shù)據(jù)元素類型定義為： typedef struct Keytype key; /聲明關(guān)鍵字 SElemType; / SElemType結(jié)構(gòu)體數(shù)據(jù)類型,類型定義,預(yù)備知識(shí),9,/數(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),宏定義,預(yù)備知識(shí),10,為什么要針對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行查找？,在程序設(shè)計(jì)中，根據(jù)實(shí)際情況的需要，要將數(shù)據(jù)存儲(chǔ)為一些特定的數(shù)據(jù)結(jié)構(gòu)，例如數(shù)組，隊(duì)列，堆，數(shù)等等。程序的業(yè)務(wù)邏輯有時(shí)候需要確認(rèn)某項(xiàng)數(shù)據(jù)是否存在。因此，要進(jìn)行查找。例如 賓館電梯控制程序，查找Vip樓層是否在隊(duì)列中 國家緝毒部門要查找可疑的毒品走私犯人 等等,預(yù)備知識(shí),11,預(yù)備知識(shí) 8.1 靜態(tài)查找表 8.2 動(dòng)態(tài)查找表 8.3 哈希表,第8章 查找,12,8.1 靜態(tài)查找表,8.1.1 順序表的查找 8.1.2 有序表的查找 *8.1.3 靜態(tài)樹表的查找 /自學(xué) 8.1.4 索引順序表的查找,13,8.1 靜態(tài)查找表,數(shù)據(jù)對(duì)象D：,數(shù)據(jù)關(guān)系R：,D是具有相同特性的數(shù)據(jù)元素的集合。每個(gè)數(shù)據(jù)元素含有類型相同的關(guān)鍵字，可唯一標(biāo)識(shí)數(shù)據(jù)元素。,數(shù)據(jù)元素同屬一個(gè)集合。,ADT StaticSearchTable ,基本操作 P：, ADT StaticSearchTable,見下頁,靜態(tài)查找表的抽象數(shù)據(jù)類型,14,8.1 靜態(tài)查找表,Create( /建立靜態(tài)查找表,Destroy( /銷毀靜態(tài)查找表,Search(ST, key); /按關(guān)鍵字字key查找,Traverse(ST, Visit(); /遍歷查找表,基本操作,15,8.1 靜態(tài)查找表,8.1.1 順序表的查找 8.1.2 有序表的查找 *8.1.3 靜態(tài)樹表的查找 /自學(xué) 8.1.4 索引順序表的查找,16,順序查找,17,typedef struct / 數(shù)據(jù)元素存儲(chǔ)空間基址，建表時(shí) / 按實(shí)際長(zhǎng)度分配，0號(hào)單元留空 int length; / 表的長(zhǎng)度 SSTable;,8.1.1 順序查找表,ElemType *elem;,順序查找表存儲(chǔ)結(jié)構(gòu),18,8.1.1 順序查找表,從查找表的第一個(gè)元素向后（或從最后一個(gè) 元素向前），比較當(dāng)前位置數(shù)據(jù)元素的關(guān)鍵字與查找關(guān)鍵字； 若相等，輸出當(dāng)前位置，查找成功，若不相等，走向下一個(gè)位置； 循環(huán)執(zhí)行a)、b)步，直到查找成功或超出范圍，表示查找失敗。,順序查找表的思想,19,8.1.1 順序查找表,順序查找表示例演示,55,67,78,76,45,33,99,88,越界了，表示沒找到，返回值為0,監(jiān)視哨,從后向前查找55,查找步驟：,20,33,67,78,76,45,33,99,88,監(jiān)視哨,從后向前查找33,查找步驟：,查找成功，返 回當(dāng)前位置5,8.1.1 順序查找表,順序查找表示例演示,21,8.1.1 順序查找表,int Search_Seq(SSTable ST, KeyType key) / 在順序表ST中順序查找其關(guān)鍵字等于 / key的數(shù)據(jù)元素。若找到，則該函數(shù) / 返回該元素在表中的位置，否則返回 / 0。 ST.elem0.key = key; / “哨兵” for (i=ST.length; (i=0) /若返回值i為0，則表示沒有找到 / Search_Seq,順序查找表的算法與實(shí)現(xiàn),22,給定值進(jìn)行比較的關(guān)鍵字個(gè)數(shù)的期望值:,8.1.1 順序查找表,順序查找表算法分析,n 為表長(zhǎng),Pi 為查找表中第i個(gè)記錄的概率,Ci為找到記錄時(shí)，關(guān)鍵字的比較次數(shù),23,在等概率查找的情況下， 順序表查找的平均查找長(zhǎng)度為：,8.1.1 順序查找表,順序查找表算法分析,24,折半查找,25,8.1.2 有序表的查找,想一想：英文字典的特點(diǎn)及英語單詞的查找過程。,折半查找的前提要求,英文字典是有序的，英語單詞的查找用的是折半查找。,折半查找的前提要求是順序存儲(chǔ)并且有序。,26,折半查找表的思想,8.1.2 有序表的查找,1)將要查找關(guān)鍵字與查找表的中間的元素 進(jìn)行比較，若相等，返回當(dāng)前位值； 2)若查找關(guān)鍵字比當(dāng)前位置關(guān)鍵字大，向 前遞歸，否則向后遞歸。,27,low,high,mid= (low+high)/2,查找21,因?yàn)?156，所以21不可能落到右面的區(qū)間，于是我們僅考慮左邊的區(qū)間,8.1.2 有序表的查找,折半查找表示例演示,28,對(duì)于左邊的區(qū)間，繼續(xù)進(jìn)行折半查找，如下,low,high,mid= (low+high)/2,因?yàn)?119，因此，21不可能在左邊的區(qū)間出現(xiàn)，所以考慮在右端區(qū)間查找,8.1.2 有序表的查找,折半查找表示例演示,29,low,high,mid= (low+high)/2,此時(shí)，在mid點(diǎn)的值剛好等于21，所以查找成功,對(duì)右端的區(qū)間繼續(xù)進(jìn)行折半查找，如下,8.1.2 有序表的查找,折半查找表示例演示,查找成功，返 回當(dāng)前位置3,30,位置 0 1 2 3 4 5 6 7 8 9 10 關(guān)鍵字05 13 19 21 37 56 64 75 80 88 90,low,high,mid= (low+high)/2,high=mid-1,mid,low=mid+1,mid,8.1.2 有序表的查找,折半查找表示例演示,查找21,31,int Search_Bin ( SSTable ST, KeyType key ) low = 1; high = ST.length; / 置區(qū)間初值 while (low = high) /語句見下頁 return 0; / 順序表中不存在待查元素 / Search_Bin,8.1.2 有序表的查找,折半查找表算法與實(shí)現(xiàn),32,while (low = high) mid = (low + high) / 2; if （EQ (key , ST.elemmid.key) ) return mid; / 找到待查元素 else if ( LT (key , ST.elemmid.key) ) high = mid - 1; / 繼續(xù)在前半?yún)^(qū)間進(jìn)行查找 else low = mid + 1; / 繼續(xù)在后半?yún)^(qū)間進(jìn)行查找 ,8.1.2 有序表的查找,折半查找表算法與實(shí)現(xiàn),33,0 1 2 3 4 5 6 7 8 9 10 05 13 19 21 37 56 64 75 80 88 90 用判定樹描述折半查找的過程。,設(shè)n=2h-1 ( h=log2(n+1) ),平均查找長(zhǎng)度,折半查找表算法分析,8.1.2 有序表的查找,5,8,9,10,6,7,4,3,2,0,1,查找速度真快！,34,游戲：猜商品價(jià)格,某款I(lǐng)Pad的價(jià)格在2000元到3000元之間，猜出它的價(jià)格。實(shí)際價(jià)格在下頁,折半查找表算法分析,8.1.2 有序表的查找,35,實(shí)際價(jià)格：2888元,游戲：猜商品價(jià)格,折半查找表算法分析,8.1.2 有序表的查找,36,索引順序表查找,37,8.1.4 索引順序表的查找,索引順序表的前提要求,查找表要求順序存儲(chǔ) 要求查找表可以分成n塊，并且當(dāng)ij時(shí)，第i塊中 的最小元素大于第j塊中的最大元素。,0 1 2 3 4 5 6 7 8 9 10,按塊單調(diào)增加,38,8.1.4 索引順序表的查找,索引順序表的查找思想,(1) 首先確定所要查找關(guān)鍵字在哪一塊中。,(2) 在所確定的塊中用順序查找查找關(guān)鍵字。,39,8.1.4 索引順序表的查找,建立索引表,0 1 2 3 4 5 6 7 8 9 10,該塊最大關(guān)鍵字該塊起始位址,線性表,索引順序表的示例演示,第1塊最大值,第2塊最大值,第3塊最大值,第1塊起 始位置,第2塊起 始位置,第3塊起 始位置,40,查找示例：假如要查找42，則根據(jù)索引表：,整個(gè)查找表被分為了三塊，按照塊單調(diào)遞增： 第1塊中的 最大關(guān)鍵字 小于 第2塊的 最小關(guān)鍵字； 第2塊中的 最大關(guān)鍵字 小于 第3塊的 最小關(guān)鍵字。 因?yàn)?2 22，所以42 肯定不在第一塊中， 因?yàn)?2 48，而第三塊的最小值也大于48，所以42肯定不在第三塊中， 所以決定在第二塊中查找。一般情況下使用順序查找法。,8.1.4 索引順序表的查找,41,typedef struct keytype key; int addr; indextype; typedef struct indextype indexmaxblock; int block; INtable; INtable IX;,8.1.4 索引順序表的查找,索引表的存儲(chǔ)結(jié)構(gòu),索引表數(shù)據(jù)類型,索引表結(jié)構(gòu),42,int SEARCH(SSTable ST, INtable IX,KeyType key ) int I = 0, s, e; /s記錄在查找表中的開始位置 /e記錄在查找表中的結(jié)束位置 在索引表中查找，確定s和e的值 根據(jù)s和e的值在線性表中查找 return -1 ,8.1.4 索引順序表的查找,索引順序表的算法與實(shí)現(xiàn),43,while (keyIX.indexi.key) return -1 ,8.1.4 索引順序表的查找,索引順序表的算法與實(shí)現(xiàn),44,思考題：如果索引表長(zhǎng)度為b，每塊平均長(zhǎng)度 為L(zhǎng)，那么平均查找長(zhǎng)度是多少？,8.1.4 索引順序表的查找,索引順序表的算法分析,答案：(b+1)/2+(L+1)/2。,45,問題1：如果實(shí)現(xiàn)知道一個(gè)長(zhǎng)度為1600位的查找表，被分為40塊，按塊單調(diào)增加，每塊中的數(shù)據(jù)都是按照單調(diào)增加排列的，則是否還有必要利用索引順序表進(jìn)行查找？,問題2：如果實(shí)現(xiàn)知道一個(gè)長(zhǎng)度為1600位的查找表，被分為40塊，按塊單調(diào)增加，每塊都是有序的（有的塊為單調(diào)增加的，有的塊為單調(diào)減少的），則是否還有必要利用索引順序表進(jìn)行查找？如果是，則在已經(jīng)確定了的那塊中，使用什么方法繼續(xù)進(jìn)行查找。,索引順序表的算法分析,46,預(yù)備知識(shí) 8.1 靜態(tài)查找表 8.2 動(dòng)態(tài)查找表 8.3 哈希表,第8章 查找,47,8.2 動(dòng)態(tài)查找表,8.2.1 二叉排序樹 (平衡二叉樹，自己學(xué)) 8.2.2 B樹和B+樹 (需要者可自己學(xué)習(xí)),48,ADT DynamicSearchTable ,動(dòng)態(tài)查找表的抽象數(shù)據(jù)類型,數(shù)據(jù)對(duì)象D： 數(shù)據(jù)關(guān)系R：,數(shù)據(jù)元素同屬一個(gè)集合。,D是具有相同特性的數(shù)據(jù)元素的集合，每個(gè)數(shù)據(jù)元素含有類型相同的關(guān)鍵字，可唯一標(biāo)識(shí)數(shù)據(jù)元素。,ADT DynamicSearchTable,基本操作P：,8.2 動(dòng)態(tài)查找表,見下頁,49,InitDSTable(&DT) /初始化表,DestroyDSTable(&DT) /銷毀表,SearchDSTable(DT, key); /按關(guān)鍵字查找,InsertDSTable( /插入數(shù)據(jù)元素,DeleteDSTable( /刪除數(shù)據(jù)元素,TraverseDSTable(DT, Visit(); /遍歷表,8.2 動(dòng)態(tài)查找表,基本操作,50,二叉排序樹的查找,51,二叉排序樹(Binary Sort Tree)或者是一棵空樹；或者是具有下列性質(zhì)的二叉樹： 若它的左子樹不空，則左子樹上所有的結(jié)點(diǎn) 的關(guān)鍵字的值均小于它的根結(jié)點(diǎn)的值； 若它的右子樹不空，則右子樹上所有的結(jié)點(diǎn) 的關(guān)鍵字的值均大于它的根結(jié)點(diǎn)的值； 它的左、右子樹也分別為二叉排序樹。,二叉排序樹的定義,8.2.1 二叉排序樹和平衡二叉樹,52,45,12,53,3,37,100,24,61,90,78,45,12,37,24,二叉排序樹的例子,8.2.1 二叉排序樹和平衡二叉樹,53,typedef struct BiTNode / 結(jié)點(diǎn)結(jié)構(gòu) struct BiTNode *lchild, *rchild; / 左右孩子指針 BiTNode, *BiTree;,TElemType data;,二叉排序樹的存儲(chǔ)結(jié)構(gòu),8.2.1 二叉排序樹和平衡二叉樹,54,當(dāng)二叉排序樹不空時(shí)，先將給定值和根結(jié)點(diǎn) 的關(guān)鍵字比較，若相等，則查找成功；否則： 若給定值小于根結(jié)點(diǎn)的關(guān)鍵字，則在左子樹上繼續(xù)進(jìn)行查找； 若給定值大于根結(jié)點(diǎn)的關(guān)鍵字，則在右子樹上繼續(xù)進(jìn)行查找; 直到找到或查到空結(jié)點(diǎn)時(shí)為止。,二叉排序樹的查找思想,8.2.1 二叉排序樹和平衡二叉樹,55,在下圖中查24,二叉排序樹的查找示例演示,45,12,53,3,37,100,24,61,90,78,45,12,37,24,8.2.1 二叉排序樹和平衡二叉樹,例,查找成功，返回該節(jié)點(diǎn)的指針,56,二叉排序樹的查找示例演示,45,12,53,3,37,100,24,61,90,78,45,53,100,61,90,8.2.1 二叉排序樹和平衡二叉樹,在下圖中查100,例,查找成功，返回 該節(jié)點(diǎn)的指針,57,二叉排序樹的查找示例演示,45,12,53,3,37,100,24,61,90,78,45,53,100,61,90,NULL,8.2.1 二叉排序樹和平衡二叉樹,在下圖中查93,例,查找失敗， 返回null,58,BiTree SearchBST(BiTree T, keytype k) BiTree p=T; while(p!=NULL) if (p-data.key=k) return p; if (kdata.key) p = p-lchild else p=p-rchild return NULL; ,二叉排序樹的查找算法,8.2.1 二叉排序樹和平衡二叉樹,59,45,24,53,12,37,94,12,24,37,45,53,94,樹1平均查找長(zhǎng)度 O(log2n),樹2平均查找長(zhǎng)度 O(n),二叉排序樹的查找算法分析,8.2.1 二叉排序樹和平衡二叉樹,60,二叉排序樹的平均查找長(zhǎng)度最差情況與順序表相 同(關(guān)鍵字有序時(shí)),為O(n); 最好情況與折半查找相同,是O（log2n）數(shù)量級(jí)的; 二叉排序樹的平均查找長(zhǎng)度仍然是O(log2n)。,二叉排序樹的查找算法分析,8.2.1 二叉排序樹和平衡二叉樹,61,若二叉樹為空：則待插入結(jié)點(diǎn)*s作為根結(jié)點(diǎn)； 當(dāng)二叉排序樹非空時(shí)：將待插結(jié)點(diǎn)關(guān)鍵字與根 結(jié)點(diǎn)進(jìn)行比較，若相等，則說明樹中已有此結(jié)點(diǎn)，無須插入； 若小于根結(jié)點(diǎn)，插入左子樹； 若大于根結(jié)點(diǎn)，插入右子樹。,二叉排序樹的插入算法思想,8.2.1 二叉排序樹和平衡二叉樹,62,12,45,3,37,53,100,24,61,在如下二叉排序樹中插入25過程演示,45,25,二叉排序樹的插入過程演示,12,37,24,8.2.1 二叉排序樹和平衡二叉樹,63,二叉排序樹的插入算法,Status InsertBST(BiTree / 樹中已有關(guān)鍵字相同的結(jié)點(diǎn)，不再插入 / Insert BST,8.2.1 二叉排序樹和平衡二叉樹,64,二叉排序樹的插入算法分析,二叉排序樹的插入算法的時(shí)間復(fù)雜性與查找 算法的時(shí)間復(fù)雜性相同; 最好情況是O（log2n）;最壞情況是O(n);平均情況是O(log2n)。,思考題：如何生成二叉排序樹?,答案：從空樹開始循環(huán)調(diào)用插入算法。,8.2.1 二叉排序樹和平衡二叉樹,65,例：從給定的一列數(shù)據(jù)出發(fā)，構(gòu)造二叉排序樹。 給定：56 52 60 43 65 28 80 96 40 39 45,產(chǎn)生了一棵不平衡的二叉排序樹,8.2.1 二叉排序樹和平衡二叉樹,56,66,例：從給定的一列數(shù)據(jù)出發(fā)，構(gòu)造二叉排序樹。 給定： 52 56 60 43 65 28 80 96 40 39 45,產(chǎn)生另外一棵不平衡的二叉排序樹,8.2.1 二叉排序樹和平衡二叉樹,52,67,在二元查找樹上的刪除一個(gè)結(jié)點(diǎn)，要求刪除結(jié)點(diǎn)后，仍保持二叉排序樹的結(jié)構(gòu)特點(diǎn)不變。,二叉排序樹的結(jié)點(diǎn)刪除定義,8.2.1 二叉排序樹和平衡二叉樹,68,(1) p為葉結(jié)點(diǎn),(2) p只有左子樹,(3) p只有右子樹,(4) p左右子樹都有,設(shè)被刪結(jié)點(diǎn)為p,其雙親結(jié)點(diǎn)為f，則p可能有以下4種情況：,二叉排序樹的結(jié)點(diǎn)刪除方法,8.2.1 二叉排序樹和平衡二叉樹,69,(1) p為葉結(jié)點(diǎn),如右圖所示：,刪除方法：釋放結(jié)點(diǎn)p，修改其父結(jié)點(diǎn)f的相應(yīng)指針。,f,p,12,45,3,37,53,100,24,61,51,25,二叉排序樹的結(jié)點(diǎn)刪除方法,8.2.1 二叉排序樹和平衡二叉樹,70,(2) p只有左子樹,如上圖 所示：,刪除方法：釋放結(jié)點(diǎn)p，p的左子樹頂替p點(diǎn)的位置。,p,12,45,3,37,53,100,24,61,51,25,12,45,3,53,100,24,61,51,25,二叉排序樹的結(jié)點(diǎn)刪除方法,8.2.1 二叉排序樹和平衡二叉樹,71,(3) p只有右子樹, 如上圖 所示：,刪除方法：釋放結(jié)點(diǎn)p，p的右子樹頂替p點(diǎn)的位置。,12,45,3,37,53,100,24,61,25,12,45,3,37,100,24,61,25,二叉排序樹的結(jié)點(diǎn)刪除方法,8.2.1 二叉排序樹和平衡二叉樹,72,把左子樹作為右子樹中最小結(jié)點(diǎn)的左子樹。,或者把右子樹作為左子樹中最大結(jié)點(diǎn)的右子樹。,(4) p既有左子樹，也有右子樹， 如上圖 所示：,刪除方法：,缺點(diǎn)：,增加了樹的高度。,12,45,3,37,53,100,24,61,51,25,二叉排序樹的結(jié)點(diǎn)刪除方法,8.2.1 二叉排序樹和平衡二叉樹,73,(4) p既有左子樹，也有右子樹, 如上圖 所示：,12,45,3,37,53,100,24,61,51,25,二叉排序樹的結(jié)點(diǎn)刪除方法,8.2.1 二叉排序樹和平衡二叉樹,改進(jìn)刪除方法：,找一個(gè)結(jié)點(diǎn)頂替它的位置。,能夠頂替它的結(jié)點(diǎn)是左子樹中最大的，右子樹中最小的。 我們用左子樹最大的結(jié)點(diǎn)來頂替。,74,Status DeleteBST(BiTree / DeleteBST,二叉排序樹的結(jié)點(diǎn)刪除算法,8.2.1 二叉排序樹和平衡二叉樹,75,Status Delete(BiTree ,二叉排序樹的結(jié)點(diǎn)刪除算法,8.2.1 二叉排序樹和平衡二叉樹,76,while (s-rchild) q = s; s = s-rchild; p-data = s-data; if (q != p) q-rchild = s-lchild; else q-lchild = s-lchild; free(s); return TRUE; / Delete,二叉排序樹的結(jié)點(diǎn)刪除算法,8.2.1 二叉排序樹和平衡二叉樹,77,二叉排序樹的刪除算法分析,二叉排序樹的刪除算法的時(shí)間復(fù)雜性與查找算法的時(shí)間復(fù)雜性相同; 最好情況是O（log2n）; 最壞情況是O(n); 平均情況是O(log2n),8.2.1 二叉排序樹和平衡二叉樹,78,預(yù)備知識(shí) 8.1 靜態(tài)查找表 8.2 動(dòng)態(tài)查找表 8.3 哈希表,第8章 查找,79,8.3.1 什么是哈希表 8.3.2 哈希函數(shù)的構(gòu)造方法 8.3.3 處理沖突的方法 8.3.4 哈希表的查找及其分析,8.3 哈希表,80,學(xué)生名單的順序存儲(chǔ)與查找方式：,哈希表的引入,030530101 張三 男 030530103 李四 男 030530133 王五 男,030530101 張三 男,030530103 李四 男,030530133 王五 男,0 1 ,8.3.1 什么是哈希表,例,順序存儲(chǔ),81,030530101 張三 男,030530103 李四 男,030530133 王五 男,0 1 2 32 ,H(num)=atoi(substr(num,8,2)-1,num=“030530101” name=“張三” sex=“男”,030530101 張三 男 030530103 李四 男 030530133 王五 男,substr(num,8,2)=“01”,哈希表的引入,8.3.1 什么是哈希表,不是按照順序存儲(chǔ)；按照函數(shù)映射,82,以結(jié)點(diǎn)的關(guān)鍵字K為自變量，通過一個(gè)確定的函數(shù)關(guān)系H，計(jì)算出對(duì)應(yīng)的函數(shù)值H(K),把這個(gè)函數(shù)值作為結(jié)點(diǎn)的存儲(chǔ)地址。 存儲(chǔ)時(shí)：把關(guān)鍵字為K的數(shù)據(jù)元素存儲(chǔ)在地址H(K)中; 查找時(shí)：給定關(guān)鍵字K，直接到地址H(k)中取數(shù)據(jù)元素。,哈希表的思想,8.3.1 什么是哈希表,優(yōu)點(diǎn)：查找的速度快,83,用散列法存儲(chǔ)的線性表叫散列表（Hash table）,又稱雜湊表，哈希表，對(duì)應(yīng)的函數(shù)稱為散列函數(shù)、雜湊函數(shù)或哈希函數(shù)。,哈希表的定義,8.3.1 什么是哈希表,84,(1) 裝填因子： 設(shè)散列表空間大小為n，填入表中的結(jié)點(diǎn)數(shù)為 m,則稱=m/n為散列表的裝填因子。 (2) 散列函數(shù)的選取原則： 運(yùn)算簡(jiǎn)單； 函數(shù)值域不能超過表長(zhǎng)； 盡可能使關(guān)鍵字不同時(shí)，散列函數(shù)值也不同。 (3) 沖突與同義詞 若H(k1) = H(k2), 則稱為沖突， 發(fā)生沖突的兩個(gè)關(guān)鍵字k1和k2稱為同義詞。,哈希表的有關(guān)概念,8.3.1 什么是哈希表,85,直接定址法,8.3.2 哈希函數(shù)的構(gòu)造方法,取關(guān)鍵字的某個(gè)線性函數(shù)值為哈希地址。即: H(key) = a*key + b 其中a、b為常數(shù)。又稱H(key)為自身函數(shù)。 優(yōu)點(diǎn)：沒有沖突； 缺點(diǎn)：若關(guān)鍵字集合很大，浪費(fèi)存儲(chǔ)空間嚴(yán)重。,86,質(zhì)數(shù)除余法,8.3.2 哈希函數(shù)的構(gòu)造方法,如果表長(zhǎng)為n，取小于或等于n的最大質(zhì)數(shù)m作模，關(guān)鍵字通過m取模運(yùn)算，所得值作為散列地址。,例子：針對(duì)以下的數(shù)據(jù)，使用質(zhì)數(shù)除余法，決定存儲(chǔ)地址 56 52 60 43 65 28 80 96 40 39 45 H(a) = a%53 則得存儲(chǔ)地址： 3 52 7 43 12 28 27 43 40 39 45,87,平方取中法,int Hash(int key) /假設(shè)key是4位整數(shù) key*=key； /求平方 key=key/100； /去掉末尾的兩位數(shù) key=key%1000; return key； ,8.3.2 哈希函數(shù)的構(gòu)造方法,在不知道關(guān)鍵字的全部情況時(shí)，可通過求關(guān)鍵字的平方值擴(kuò)大差別，然后取中間幾位作為哈希地址：,88,折疊法（關(guān)鍵字太長(zhǎng)，分成幾塊，相加） 數(shù)字分析法（預(yù)先知道數(shù)據(jù)結(jié)構(gòu)，例如身份證） 基數(shù)轉(zhuǎn)換法（例如，10進(jìn)制轉(zhuǎn)換為8進(jìn)制）,8.3.2 哈希函數(shù)的構(gòu)造方法,89,又叫開放地址，用于順序存儲(chǔ)； 開放地址指地址單元為空，對(duì)于數(shù)組來說，是指還沒存入數(shù)據(jù)的數(shù)組單元，在順序存儲(chǔ)結(jié)構(gòu)中用一定方法進(jìn)行散列存取的方法稱為開放定址法。,開放定址法的定義,8.3.3 處理沖突的方法,90,設(shè)散列表的長(zhǎng)度為13，散列函數(shù)為: H(K)=K%13, 給定的關(guān)鍵字序列為: 19, 14, 23, 1, 68, 20, 84, 27, 54, 11, 10,0 1 2 3 4 5 6 7 8 9 10 11 12,14,23,(1)線性探測(cè)再散列法：若H(key)=d的單元發(fā)生沖 突，則按下述方法進(jìn)行探查： hi(k)=(h(k)+i)%n，n是散列表的長(zhǎng)度，1in-1,1,68,20,19,27,54,H(K) = 6, 1, 10, 1, 3, 7, 6, 1, 2, 11, 10,11,10,84,開放定址法示例演示,8.3.3 處理沖突的方法,例,91,二次聚集的概念,8.3.3 處理沖突的方法,兩個(gè)本來不發(fā)生沖突的非同義詞，也就是散列地址不同的結(jié)點(diǎn)，發(fā)生爭(zhēng)奪同一個(gè)散列地址的現(xiàn)象稱為二次聚集或堆積。,92,查找分析：查11，查40。 1、利用散列函數(shù)計(jì)算出關(guān)鍵字為K的數(shù)據(jù)元素的地址：d=H(K)，如果Fd.key=K,查找成功，返回d; 2、如果Fd.key!=K,依次查找F(d+i)%n.key, 直到找到某個(gè)F(d+j)%n.key=K,返回(d+j)%n, 或者找到一個(gè)開放地址為止，此時(shí)顯示沒找到。,19, 14, 23, 1, 68, 20, 84, 27, 54, 11, 10,0 1 2 3 4 5 6 7 8 9 10 11 12,14,23,1,68,20,19,27,54,H(K)=6, 1, 10, 1, 3, 7, 6, 1, 2, 11, 10,11,10,84,開放定址法查找示例演示,8.3.3 處理沖突的方法,93,刪除分析：如果刪除68，查找27。 刪除結(jié)點(diǎn)時(shí)不能簡(jiǎn)單地將被刪結(jié)點(diǎn)的地址置空（使用一個(gè)特殊標(biāo)記、值占位），否則將截?cái)嗨筇钊肷⒘斜淼耐x詞的查找路徑(如果刪除了68，并且使得地址置空，則將無法查找得到27),19, 14, 23, 1, 68, 20, 84, 27, 54, 11, 10,0 1 2 3 4 5 6 7 8 9 10 11 12,14,23,1,68,20,19,27,54,H(K) = 6, 1, 10, 1, 3, 7, 6, 1, 2, 11, 10,11,10,84,開放定址法刪除示例演示,8.3.3 處理沖突的方法,94,(1) 線性探測(cè)再散列法：若H(key) = d的單元發(fā)生沖突， 則按下述方法進(jìn)行探查： hi(k) = (h(k)+i)%n, n是散列表的長(zhǎng)度，1in-1,(2) 二次探測(cè)再散列法：若H(key)=d的單元發(fā)生沖突， 則按下述方法進(jìn)行探查： hi(k) = (h(k)+di)%n, n是散列表的長(zhǎng)度， di = 12, -12, 22, -22, k2, -k2 (k n/2),(3) 偽隨機(jī)探測(cè)再散列，取di=偽隨機(jī)序列（種子一樣，隨機(jī)一樣，不會(huì)變）,開放定址法處理沖突的方法,8.3.3 處理沖突的方法,95,設(shè)置RHi()，i=1, 2, k 多個(gè)哈希函數(shù)，當(dāng)一個(gè)哈希函數(shù)產(chǎn)生沖突時(shí)，順序用下一個(gè)。,(4) 再哈希法（再散列法）,開放定址法處理沖突的方法,8.3.3 處理沖突的方法,96,鏈地址法（又稱拉鏈法）的示例演示,0 1 2 3 4 ,19, 14, 23, 1, 68, 20, 84, 27, 54, 11, 10, 79,H(K) = 6, 1, 10, 1, 3, 7, 6, 1, 2, 11, 10, 1,8.3.3 處理沖突的方法,先查找指針， 然后按照順序查找,97,拉鏈法（外散列表）平均查找長(zhǎng)度比開放地質(zhì)法（內(nèi)散列法）平均查找長(zhǎng)度短。,14,23,1,68,20,19,27,54,11,10,84,79,0 1 2 3 4 5 6 7 8 9 10 11 12,8.3.3 處理沖突的方法,開放定址法與鏈地址法平均查找長(zhǎng)度比較,例子查找79,使用鏈地址法查找：,98,拉鏈法的查找算法,0 1 2 3 4,8.3.3 處理沖突的方法,根據(jù)關(guān)鍵字K找到關(guān)鍵字為K的結(jié)點(diǎn)所在單鏈表的首地址； 在所找到的單鏈表上進(jìn)行順序查找，若找到則返回地址值，否則返回空值。,99,拉鏈法的插入算法：,8.3.3 處理沖突的方法,根據(jù)關(guān)鍵字K找到關(guān)鍵字為K的結(jié)點(diǎn)所應(yīng)該存在的單鏈表的首地