由于查找運(yùn)算的使用頻率很高解讀課件

1、第8章 查找第8章 查找概述 由于查找運(yùn)算的使用頻率很高，幾乎在任何一個(gè)計(jì)算機(jī)系統(tǒng)軟件和應(yīng)用軟件中都會(huì)涉及到，所以當(dāng)問(wèn)題所涉及的數(shù)據(jù)量相當(dāng)大時(shí)，查找方法的效率就顯得格外重要。在一些實(shí)時(shí)查詢(xún)系統(tǒng)中尤其如此。因此，本章將系統(tǒng)地討論各種查找方法，并通過(guò)對(duì)它們的效率分析來(lái)比較各種查找方法的優(yōu)劣。概述 由于查找運(yùn)算的使用頻率很高，幾乎在任何一個(gè)8.1查找的基本概念8.1查找的基本概念1、查找表和查找一般，假定被查找的對(duì)象是由一組結(jié)點(diǎn)組成的表(Table)或文件，而每個(gè)結(jié)點(diǎn)則由若干個(gè)數(shù)據(jù)項(xiàng)組成。并假設(shè)每個(gè)結(jié)點(diǎn)都有一個(gè)能惟一標(biāo)識(shí)該結(jié)點(diǎn)的關(guān)鍵字。查找(Searching)的定義是：給定一個(gè)值K，在含有n個(gè)結(jié)點(diǎn)

2、的表中找出關(guān)鍵字等于給定值K的結(jié)點(diǎn)。若找到，則查找成功，返回該結(jié)點(diǎn)的信息或該結(jié)點(diǎn)在表中的位置；否則查找失敗，返回相關(guān)的指示信息。1、查找表和查找一般，假定被查找的對(duì)象是由一組結(jié)點(diǎn)組成的2、查找表的數(shù)據(jù)結(jié)構(gòu)表示1. 動(dòng)態(tài)查找表和靜態(tài)查找表 若在查找的同時(shí)對(duì)表做修改操作(如插入和刪除)，則相應(yīng)的表稱(chēng)之為動(dòng)態(tài)查找表。否則稱(chēng)之為靜態(tài)查找表。2. 內(nèi)查找和外查找和排序類(lèi)似，查找也有內(nèi)查找和外查找之分。若整個(gè)查找過(guò)程都在內(nèi)存進(jìn)行，則稱(chēng)之為內(nèi)查找；反之，若查找過(guò)程中需要訪(fǎng)問(wèn)外存，則稱(chēng)之為外查找。2、查找表的數(shù)據(jù)結(jié)構(gòu)表示1. 動(dòng)態(tài)查找表和靜態(tài)查找表3、平均查找長(zhǎng)度ASL查找運(yùn)算的主要操作是關(guān)鍵字的比較，所以通

3、常把查找過(guò)程中對(duì)關(guān)鍵字需要執(zhí)行的 平均比較次數(shù)(也稱(chēng)為平均查找長(zhǎng)度)作為衡量一個(gè)查找算法效率優(yōu)劣的標(biāo)準(zhǔn)。（ 平均查找長(zhǎng)度 ASL(Average Search Length)定義為： 3、平均查找長(zhǎng)度ASL查找運(yùn)算的主要操作是關(guān)鍵字的比較，所n是結(jié)點(diǎn)的個(gè)數(shù)；Pi是查找第i個(gè)結(jié)點(diǎn)的概率。若不特別聲明，認(rèn)為每個(gè)結(jié)點(diǎn)的查找概率相等，即 pl=p2=pn=1/nci是找到第i個(gè)結(jié)點(diǎn)所需進(jìn)行的比較次數(shù)。n是結(jié)點(diǎn)的個(gè)數(shù)；查找數(shù)據(jù)類(lèi)型 typedef int KeyType； /KeyType應(yīng)由用戶(hù)定義查找數(shù)據(jù)類(lèi)型 typedef int KeyType； /8.3線(xiàn)性表查找8.3線(xiàn)性表查找1、順序查找的

4、基本思想基本思想是：從表的一端開(kāi)始，順序掃描線(xiàn)性表，依次將掃描到的結(jié)點(diǎn)關(guān)鍵字和給定值K相比較。若當(dāng)前掃描到的結(jié)點(diǎn)關(guān)鍵字與K相等，則查找成功；若掃描結(jié)束后，仍未找到關(guān)鍵字等于K的結(jié)點(diǎn)，則查找失敗。1、順序查找的基本思想基本思想是：從表的一端開(kāi)始，順序掃描2、順序查找的存儲(chǔ)結(jié)構(gòu)要求順序查找方法既適用于線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)，也適用于線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（使用單鏈表作存儲(chǔ)結(jié)構(gòu)時(shí)，掃描必須從第一個(gè)結(jié)點(diǎn)開(kāi)始）。2、順序查找的存儲(chǔ)結(jié)構(gòu)要求順序查找方法既適用于線(xiàn)性表的順序存3.基于順序結(jié)構(gòu)的順序查找算法（1）類(lèi)型說(shuō)明 typedef struct KeyType key； InfoType otherinfo

5、； /此類(lèi)型依賴(lài)于應(yīng)用 NodeType； typedef NodeType SeqListn+1； /0號(hào)單元用作哨兵3.基于順序結(jié)構(gòu)的順序查找算法（1）類(lèi)型說(shuō)明 typed（2）具體算法 int SeqSearch(Seqlist R，KeyType K) /在順序表R1.n中順序查找關(guān)鍵字為K的結(jié)點(diǎn)，/成功時(shí)返回找到的結(jié)點(diǎn)位置，失敗時(shí)返回0 int i； R0.key=K; for(i=n；Ri.key!=K;i-)； /從表后往前找 return i； /若i為0，表示查找失敗，否則Ri是要找的結(jié)點(diǎn) /SeqSearch（2）具體算法 int SeqSearch(Seqlist 計(jì)比較

6、的次數(shù)1 2 3 +.+n=(1+n)/2約等于表長(zhǎng)的一半找不到？n+11528329766145iiiiiii計(jì)比較的次數(shù)1 2 3 +.+n=(1+n)/2約等于表（3）算法分析 算法中監(jiān)視哨R0的作用 為了在for循環(huán)中省去判定防止下標(biāo)越界的條件i1，從而節(jié)省比較的時(shí)間。成功時(shí)的順序查找的平均查找長(zhǎng)度： 在等概率情況下，pi=1/n(1in)，故成功的平均查找長(zhǎng)度為 (n+2+1)/n=(n+1)/2 即查找成功時(shí)的平均比較次數(shù)約為表長(zhǎng)的一半。 若K值不在表中，則須進(jìn)行n+1次比較之后才能確定查找失敗。（3）算法分析 算法中監(jiān)視哨R0的作用 為了在算法并不很好？算法簡(jiǎn)單，但效率不高。算法

7、并不很好？算法簡(jiǎn)單，但效率不高。二分查找1、二分查找(Binary Search) 二分查找又稱(chēng)折半查找，它是一種效率較高的查找方法。 二分查找要求：線(xiàn)性表是有序表，即表中結(jié)點(diǎn)按關(guān)鍵字有序，并且要用向量作為表的存儲(chǔ)結(jié)構(gòu)。不妨設(shè)有序表是遞增有序的。二分查找1、二分查找(Binary Search)找到的條件low high mid=(low+high)/2if(amid=k)表示找到121619222533404852657083lmhmlhmh找到的條件low high mid=(low+high)/2、二分查找的基本思想二分查找的基本思想是:(設(shè)Rlow.high是當(dāng)前的查找區(qū)間）（1）首先

8、確定該區(qū)間的中點(diǎn)位置： mid=(high+low)/2; （2）然后將待查的K值與Rmid.key比較：若相等，則查找成功并返回此位置，否則須確定新的查找區(qū)間，繼續(xù)二分查找，具體方法如下： 若Rmid.keyK，則由表的有序性可知Rmid.n.keys均大于K，因此若表中存在關(guān)鍵字等于K的結(jié)點(diǎn)，則該結(jié)點(diǎn)必定是在位置mid左邊的子表R1.mid-1中，故新的查找區(qū)間是左子表R1.mid-1。 類(lèi)似地，若Rmid.keyK，則要查找的K必在mid的右子表Rmid+1.n中，即新的查找區(qū)間是右子表Rmid+1.n。下一次查找是針對(duì)新的查找區(qū)間進(jìn)行的。2、二分查找的基本思想二分查找的基本思想是:3、

9、二分查找算法 int BinSearch(SeqList R，KeyType K) /在有序表R1.n中進(jìn)行二分查找，成功時(shí)返回結(jié)點(diǎn)的位置，失敗時(shí)返回零 int low=1，high=n，mid； /置當(dāng)前查找區(qū)間上、下界的初值 while(lowK) high=mid-1; /繼續(xù)在Rlow.mid-1中查找 else low=mid+1； /繼續(xù)在Rmid+1.high中查找 return 0； /當(dāng)lowhigh時(shí)表示查找區(qū)間為空，查找失敗 /BinSeareh3、二分查找算法 int BinSearch(SeqL時(shí)間復(fù)雜度ASL=log2(n+1)n=10000條記錄;ASL=5000

10、次log210000=15時(shí)間復(fù)雜度ASL=log2(n+1)一個(gè)常考的題目一個(gè)?？嫉念}目512182135455078900123456784323132345121821354550789001234567843234.分塊查找2、分塊查找的基本思想分塊查找的基本思想是：（1）首先查找索引表索引表是有序表，可采用二分查找或順序查找，以確定待查的結(jié)點(diǎn)在哪一塊。（2）然后在已確定的塊中進(jìn)行順序查找由于塊內(nèi)無(wú)序，只能用順序查找。4.分塊查找2、分塊查找的基本思想分塊查找的基本思想是lsl/s(l/s+1)/2+(s+1)/2y=(l/x+x)/2+120 0840 41260 119182820

11、343043475452l20 0840 41260 1191828201313152325333345555560l1313152325333345555560l4、算法分析（1）平均查找長(zhǎng)度ASL分塊查找是兩次查找過(guò)程。整個(gè)查找過(guò)程的平均查找長(zhǎng)度是兩次查找的平均查找長(zhǎng)度之和。以二分查找來(lái)確定塊，分塊查找成功時(shí)的平均查找長(zhǎng)度 ASLblk=ASLbn+ASLsqlg(b+1)-1+(s+1)/2lg(n/s+1)+s/2以順序查找確定塊，分塊查找成功時(shí)的平均查找長(zhǎng)度 ASLblk=(b+1)/2+(s+1)/2=(s2+2s+n)/(2s)4、算法分析（1）平均查找長(zhǎng)度ASL分塊查找是兩次查

12、找8.3 樹(shù)上的查找動(dòng)態(tài)查找8.3 樹(shù)上的查找動(dòng)態(tài)查找1、二叉排序樹(shù)的定義 二叉排序樹(shù)(Binary Sort Tree)又稱(chēng)二叉查找(搜索)樹(shù)(Binary Search Tree)。其定義為：二叉排序樹(shù)或者是空樹(shù)，或者是滿(mǎn)足如下性質(zhì)的二叉樹(shù)：若它的左子樹(shù)非空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；若它的右子樹(shù)非空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值；左、右子樹(shù)本身又各是一棵二叉排序樹(shù)。上述性質(zhì)簡(jiǎn)稱(chēng)二叉排序樹(shù)性質(zhì)(BST性質(zhì))，故二叉排序樹(shù)實(shí)際上是滿(mǎn)足BST性質(zhì)的二叉樹(shù)。1、二叉排序樹(shù)的定義 二叉排序樹(shù)(Binary Sort 2、二叉排序樹(shù)的特點(diǎn)由BST性質(zhì)可得：（1） 二叉排序樹(shù)中

13、任一結(jié)點(diǎn)x，其左(右)子樹(shù)中任一結(jié)點(diǎn)y(若存在)的關(guān)鍵字必小(大)于x的關(guān)鍵字。（2） 二叉排序樹(shù)中，各結(jié)點(diǎn)關(guān)鍵字是惟一的。2、二叉排序樹(shù)的特點(diǎn)由BST性質(zhì)可得：（1） 二叉排二叉排序示例二叉排序示例12346573184232p=NULLf12346573184232p=NULLf3、二叉排序樹(shù)的存儲(chǔ)結(jié)構(gòu)typedef int KeyType； /假定關(guān)鍵字類(lèi)型為整數(shù)typedef struct node /結(jié)點(diǎn)類(lèi)型 KeyType key； /關(guān)鍵字項(xiàng) InfoType otherinfo； /其它數(shù)據(jù)域，InfoType視應(yīng)用情況而定，下面不處理它 struct node *lchild

14、，*rchild； /左右孩子指針 BSTNode；typedef BSTNode *BSTree； /BSTree是二叉排序樹(shù)的類(lèi)型 3、二叉排序樹(shù)的存儲(chǔ)結(jié)構(gòu)typedef int KeyTyp二叉排序樹(shù)插入新結(jié)點(diǎn)的非遞歸算法BSTree InsertBST(BSTree *Tptr，KeyType key) /若二叉排序樹(shù) *Tptr中沒(méi)有關(guān)鍵字為key，則插入，否則直接返回 BSTNode *f，*p=*TPtr； /p的初值指向根結(jié)點(diǎn) while(p) /查找插入位置 if(p-key=key) return p；/樹(shù)中已有key，無(wú)須插入 f=p； /f保存當(dāng)前查找的結(jié)點(diǎn) p=(ke

15、ykey)?p-lchild：p-rchild； /若keykey，則在左子樹(shù)中查找，否則在右子樹(shù)中查找 /endwhile p=(BSTNode *)malloc(sizeof(BSTNode)； p-key=key； p-lchild=p-rchild=NULL； /生成新結(jié)點(diǎn) if(*TPtr=NULL) /原樹(shù)為空 *Tptr=p； /新插入的結(jié)點(diǎn)為新的根 else /原樹(shù)非空時(shí)將新結(jié)點(diǎn)關(guān)p作為關(guān)f的左孩子或右孩子插入 if(keykey) f-lchild=p； else f-rchild=p； return NULL /InsertBST二叉排序樹(shù)插入新結(jié)點(diǎn)的非遞歸算法BSTree

16、 InseBSTree InsertBST(BSTree *root,int key)BSTree q;BSTree studTree;q=InsertBST(&studTree,23);if(q=NULL) printf(“插入成功n”);else printf(“該同學(xué)已經(jīng)存在”); printf(“%d”,p-key, BSTree InsertBST(BSTree *root,34235678289167822328345667788291log2n退化二叉樹(shù)3423567828916782232834566778828.4散列查找Hash(哈希查找）8.4散列查找Hash(哈希查找）

17、散列表的概念1、散列表 設(shè)所有可能出現(xiàn)的關(guān)鍵字集合記為U(簡(jiǎn)稱(chēng)全集)。實(shí)際發(fā)生(即實(shí)際存儲(chǔ))的關(guān)鍵字集合記為K（|K|比|U|小得多）。 散列方法是使用函數(shù)h將U映射到表T0.m-1的下標(biāo)上（m=O(|U|)）。這樣以U中關(guān)鍵字為自變量，以h為函數(shù)的運(yùn)算結(jié)果就是相應(yīng)結(jié)點(diǎn)的存儲(chǔ)地址。從而達(dá)到在O(1)時(shí)間內(nèi)就可完成查找。 其中： h：U0，1，2，m-1 ，通常稱(chēng)h為散列函數(shù)(Hash Function)。散列函數(shù)h的作用是壓縮待處理的下標(biāo)范圍，使待處理的|U|個(gè)值減少到m個(gè)值，從而降低空間開(kāi)銷(xiāo)。 T為散列表(Hash Table)。 h(Ki)(KiU)是關(guān)鍵字為Ki結(jié)點(diǎn)存儲(chǔ)地址(亦稱(chēng)散列值或

18、散列地址)。 將結(jié)點(diǎn)按其關(guān)鍵字的散列地址存儲(chǔ)到散列表中的過(guò)程稱(chēng)為散列(Hashing)散列表的概念1、散列表 設(shè)所有可能出現(xiàn)的關(guān)鍵字集合由于查找運(yùn)算的使用頻率很高解讀課件例子有10個(gè)學(xué)生記錄，他們的學(xué)號(hào)為8780001 87800028780003 87800048780005 87800068780007 87800088780009 8780010要存放在一個(gè)10個(gè)元素的一維數(shù)組里，如何存放，取出來(lái)比較方便例子有10個(gè)學(xué)生記錄，他們的學(xué)號(hào)為01012342656067298942單元序號(hào)=學(xué)號(hào)-8780001878000901012342656067298942單元序號(hào)=學(xué)號(hào)-87例子有1

19、0個(gè)，他們的學(xué)號(hào)為8780001 87800028780003 87800048780005 87800068780007 87800088780009 8780010要存放在一個(gè)一維數(shù)組里，如何存放，取出來(lái)比較方便例子有10個(gè)，他們的學(xué)號(hào)為28暫定：27日（星期日上午）307，303，305，207。28暫定：27日（星期日上午）307，303，305，207例子有10個(gè)，他們的學(xué)號(hào)為01 0613 1726 2940 2060 56 h(k)=19%20要存放在一個(gè)一維數(shù)組里，如何存放，取出來(lái)比較方便例子有10個(gè)，他們的學(xué)號(hào)為一維數(shù)組只有7個(gè)元素怎么辦？一維數(shù)組只有7個(gè)元素怎么辦？3、散列

20、表的沖突現(xiàn)象（1）沖突 兩個(gè)不同的關(guān)鍵字，由于散列函數(shù)值相同，因而被映射到同一表位置上。該現(xiàn)象稱(chēng)為沖突(Collision)或碰撞。發(fā)生沖突的兩個(gè)關(guān)鍵字稱(chēng)為該散列函數(shù)的同義詞(Synonym)。 【例】上圖中的k2k5，但h(k2)=h(k5)，故k2和K5所在的結(jié)點(diǎn)的存儲(chǔ)地址相同。3、散列表的沖突現(xiàn)象（1）沖突 兩個(gè)不同的關(guān)鍵字，討論二個(gè)相關(guān)問(wèn)題找一個(gè)比較好的Hash函數(shù)一個(gè)碰撞機(jī)機(jī)率盡可能少，碰撞肯定會(huì)發(fā)生。盡可能分散如何解決碰撞討論二個(gè)相關(guān)問(wèn)題找一個(gè)比較好的Hash函數(shù)（2）安全避免沖突的條件 最理想的解決沖突的方法是安全避免沖突。要做到這一點(diǎn)必須滿(mǎn)足兩個(gè)條件：其一是|U|m其二是選擇合

21、適的散列函數(shù)。 這只適用于|U|較小，且關(guān)鍵字均事先已知的情況，此時(shí)經(jīng)過(guò)精心設(shè)計(jì)散列函數(shù)h有可能完全避免沖突。（2）安全避免沖突的條件 最理想的解決沖突的方法是安（3）沖突不可能完全避免通常情況下，h是一個(gè)壓縮映像。雖然|K|m，但|U|m，故無(wú)論怎樣設(shè)計(jì)h，也不可能完全避免沖突。因此，只能在設(shè)計(jì)h時(shí)盡可能使沖突最少。同時(shí)還需要確定解決沖突的方法，使發(fā)生沖突的同義詞能夠存儲(chǔ)到表中。（3）沖突不可能完全避免通常情況下，h是一個(gè)壓縮映像。雖然（4）影響沖突的因素 沖突的頻繁程度除了與h相關(guān)外，還與表的填滿(mǎn)程度相關(guān)。 設(shè)m和n分別表示表長(zhǎng)和表中填人的結(jié)點(diǎn)數(shù)，則將=n/m定義為散列表的裝填因子(Loa

22、d Factor)。越大，表越滿(mǎn)，沖突的機(jī)會(huì)也越大。通常取1。（4）影響沖突的因素 沖突的頻繁程度除了與h相關(guān)外，散列函數(shù)的構(gòu)造方法1、散列函數(shù)的選擇有兩條標(biāo)準(zhǔn)：簡(jiǎn)單和均勻。 簡(jiǎn)單指散列函數(shù)的計(jì)算簡(jiǎn)單快速； 均勻指對(duì)于關(guān)鍵字集合中的任一關(guān)鍵字，散列函數(shù)能以等概率將其映射到表空間的任何一個(gè)位置上。也就是說(shuō)，散列函數(shù)能將子集K隨機(jī)均勻地分布在表的地址集0，1，m-1上，以使沖突最小化。散列函數(shù)的構(gòu)造方法1、散列函數(shù)的選擇有兩條標(biāo)準(zhǔn)：簡(jiǎn)單和均勻。2、常用散列函數(shù) 為簡(jiǎn)單起見(jiàn)，假定關(guān)鍵字是定義在自然數(shù)集合上。2、常用散列函數(shù) 為簡(jiǎn)單起見(jiàn)，假定關(guān)鍵字是定義在自（1）平方取中法具體方法：先通過(guò)求關(guān)鍵字的平

23、方值擴(kuò)大相近數(shù)的差別，然后根據(jù)表長(zhǎng)度取中間的幾位數(shù)作為散列函數(shù)值。又因?yàn)橐粋€(gè)乘積的中間幾位數(shù)和乘數(shù)的每一位都相關(guān)，所以由此產(chǎn)生的散列地址較為均勻。1 2 3 4 51 4 9 16 25（1）平方取中法具體方法：先通過(guò)求關(guān)鍵字的平方值擴(kuò)大相近數(shù)的例【例】將一組關(guān)鍵字(0100，0110，1010，1001，0111)平方后得 (0010000，0012100，1020100，1002001，0012321) 若取表長(zhǎng)為1000，則可取中間的三位數(shù)作為散列地址集： (100，121，201，020，123)。相應(yīng)的散列函數(shù)用C實(shí)現(xiàn)很簡(jiǎn)單：int Hash(int key) /假設(shè)key是4位整數(shù)

24、 key*=key； key/=100； /先求平方值，后去掉末尾的兩位數(shù) return key1000； /取中間三位數(shù)作為散列地址返回例【例】將一組關(guān)鍵字(0100，0110，1010，1001（2）除余法該方法是最為簡(jiǎn)單常用的一種方法。它是以表長(zhǎng)m來(lái)除關(guān)鍵字，取其余數(shù)作為散列地址，即 h(key)=keym 該方法的關(guān)鍵是選取m。選取的m應(yīng)使得散列函數(shù)值盡可能與關(guān)鍵字的各位相關(guān)。m最好為素?cái)?shù)取m大于表長(zhǎng)的最小質(zhì)數(shù) 表長(zhǎng)10m=11 m=17（2）除余法該方法是最為簡(jiǎn)單常用的一種方法。它是以表長(zhǎng)m來(lái)例【例】若選m是關(guān)鍵字的基數(shù)的冪次，則就等于是選擇關(guān)鍵字的最后若干位數(shù)字作為地址，而與高位無(wú)關(guān)。于是高位不同而低位相同的關(guān)鍵字均互為同義詞。 【例】若關(guān)鍵字是十進(jìn)制整數(shù)，其基為10，則當(dāng)m=100時(shí)，159，259，359，等均互為同義詞。例【例】若選m是關(guān)鍵字的基數(shù)的冪次，則就等于是選擇關(guān)鍵字的（3）相乘取整法 該方法包