第10章 查找電子課件

第10章查找本章講解查找。理解查找基本概念；掌握各種靜態(tài)表查找算法；掌握二叉排序樹查找算法；了解平衡二叉樹查找算法；理解哈希表查找算法；靈活應(yīng)用查找。過年啦！照年俗，正月初一起床就去包大湯圓煮，在有些大湯圓里面包上小硬幣，誰吃到寓意來年發(fā)財(cái)發(fā)大財(cái)！難了，擺在我面前的那么多碗，我到底選哪一碗？那一碗里又是哪一個(gè)湯圓包了發(fā)財(cái)硬幣的？查找吧！提綱10.1查找基本概念10.2靜態(tài)表查找10.3動(dòng)態(tài)表查找10.4哈希表查找10.5查找應(yīng)用10.6查找學(xué)習(xí)總結(jié)10.1查找基本概念定義查找表：被查找的對(duì)象。主關(guān)鍵字可以唯一識(shí)別。舉例：公司每天產(chǎn)生的郵件很多，小王出差辦事忙，已經(jīng)有3天沒有時(shí)間看郵件了?；貋砗螅赂嬖V他公司整體調(diào)薪了，具體數(shù)據(jù)每個(gè)人私郵了的。興奮之余，小王打開郵箱，密密麻麻信件太難找了！還好，有個(gè)搜索查找功能，輸入時(shí)間范圍3天前到現(xiàn)在，輸入關(guān)鍵字“薪”/“工資”，回車見到了！這個(gè)例子說明，查找在我們生活中幾乎天天在、無處不在。10.1查找基本概念2.分類按照操作方式分為靜態(tài)查找表和動(dòng)態(tài)查找表。按照查找是否在內(nèi)存完成分為內(nèi)查找和外查找。按照查找是否按照地址查找分為哈希表和非哈希表。10.1查找基本概念3.性能查找的性能主要是由關(guān)鍵字比較次數(shù)決定的。關(guān)鍵字平均比較次數(shù)也就是平均查找長(zhǎng)度（ASL，AverageSearchLength）是作為查找算法效率優(yōu)劣的依據(jù)。10.1查找基本概念求ASL舉例，如表10.1所示的查找表和找到關(guān)鍵字時(shí)比較的次數(shù)。10.2靜態(tài)表查找靜態(tài)表在查找時(shí)不做插入、刪除操作，所以順序表適合做靜態(tài)表查找。順序表查找類SqListSearch描述10.2.1順序查找舉例：大小英語四級(jí)考試的考場(chǎng)里，考生就位之后監(jiān)考老師從座位號(hào)1開始逐一檢查考試證件，與手上的名單對(duì)照，若正確則到下一個(gè)，若不正確就找到了問題考生。在這個(gè)例子中，按座位號(hào)逐一查找是否有問題考生便是順序查找。10.2.1順序查找【算法10.1】設(shè)計(jì)1個(gè)算法，對(duì)R[0..n-1]進(jìn)行順序查找，若找到返回序號(hào)，否則返回-1。思路：（1）從順序表的一端開始依次遍歷，將遍歷的元素關(guān)鍵字和給定值k相比較，（2）若兩者相等，則查找成功，返回該元素的序號(hào)。（3）若遍歷結(jié)束后，仍未找到關(guān)鍵字等于k的元素，則查找失敗，返回-1。代碼見算法10.110.2.2二分查找在關(guān)鍵字有序序列（2，4，7，9，10，14，18，26，32，40）中采用二分查找方法查找關(guān)鍵字為7的元素。10.2.2二分查找二分查找的性能可以用判定樹描述。顯然，二分查找的平均性能與判定樹的高度h=log2(n+1)有關(guān)10.2.2二分查找

10.2.3分塊查找舉例：每場(chǎng)期末考試考前要在黑板上畫出座位號(hào)。學(xué)生如果從1數(shù)到自己座位號(hào)找到自己座位，有點(diǎn)糟糕！何不，先確定自己的座位號(hào)落在哪一列（區(qū)間），再到那一列去找，效率高多了嘛！10.2.3分塊查找設(shè)查找表為（8，14，6，9，10，22，34，18，19，31，40，38，54，66，46，71，78，68，80，85，100，94，88，96，87），查找關(guān)鍵字為80的元素。10.2.3分塊查找

10.2.3分塊查找【算法10.4】設(shè)計(jì)1個(gè)算法，在順序表R[0..n-1]和索引表I[0..b-1]中進(jìn)行分塊查找，若找到返回序號(hào)，否則返回-1。思路：（1）根據(jù)查找表長(zhǎng)度進(jìn)行分塊，由每1塊的最大值/最小值構(gòu)造索引表。（2）對(duì)索引表進(jìn)行順序/二分查找，找到對(duì)應(yīng)查找表中的分塊。（3）對(duì)查找表對(duì)應(yīng)的分塊中進(jìn)行順序查找。代碼見算法10.410.3動(dòng)態(tài)表查找動(dòng)態(tài)表在查找時(shí)要做插入或刪除操作，所以鏈表樹表適合做動(dòng)態(tài)表查找。10.3.1二叉排序樹查找左孩子小于根，右孩子大于根顯然，對(duì)二叉排序樹進(jìn)行中序遍歷，序列為有序序列。10.3.1二叉排序樹查找二叉排序樹節(jié)點(diǎn)類BSTNode描述二叉排序樹類BST描述10.3.1二叉排序樹查找已知1組關(guān)鍵字為（25,18,46,2,53,39,32,4,74,67,60,11），按表中的元素順序依次插入到1棵初始為空的二叉排序樹中，畫出該二叉排序樹，并求等概率情況下的ASL成功和ASL不成功。10.3.2平衡二叉樹查找它首先是棵二叉排序樹，然后保持樹的高度較?。ㄗ笥移胶夤实妹?。有時(shí)又叫做AVL樹。10.3.2平衡二叉樹查找更新AVL樹時(shí)會(huì)打破“平衡”，需要調(diào)整為AVL樹，有4種調(diào)整方式：（1)LL型調(diào)整（右旋）（2)RR型調(diào)整（左旋）（3)LR型調(diào)整（先左旋后右旋）（4)RL型調(diào)整（先右旋后左旋）10.3.2平衡二叉樹查找（1)LL型調(diào)整（右旋）10.3.2平衡二叉樹查找（2)RR型調(diào)整（左旋）10.3.2平衡二叉樹查找（3)LR型調(diào)整（先左旋后右旋）10.3.2平衡二叉樹查找（4)RL型調(diào)整（先右旋后左旋）*10.3.3B-樹*10.3.4B+樹10.4哈希表查找問題的提出：比較的方式查找，往往與問題規(guī)模和元素位置相關(guān)，效率低。解決方案：通過元素關(guān)鍵字值進(jìn)行存儲(chǔ)和查找，從而查找效率可以提高。哈希函數(shù)可以實(shí)現(xiàn)。10.4.1哈希函數(shù)哈希函數(shù)存儲(chǔ)是把關(guān)鍵字映射為內(nèi)存地址。10.4.1哈希函數(shù)舉例：上體育課排隊(duì)，女生前2排男生后2排，從左到右依次由矮到高排。在身高沒有變化的情況下，每個(gè)同學(xué)每次上體育課排隊(duì)時(shí)都能迅速找到自己的位置列隊(duì)。在這個(gè)例子中，身高是關(guān)鍵字值，通過這個(gè)值計(jì)算出列隊(duì)位置，也可以查找到該位置的同學(xué)。類似的例子還有看電影時(shí)通過電影票對(duì)號(hào)入座。10.4.1哈希函數(shù)查找學(xué)號(hào)為2018007的學(xué)生分?jǐn)?shù)：先計(jì)算h(2018007)=2018007-2018001=6。再取ha[6]元素的分?jǐn)?shù)76即可。顯然利用哈希函數(shù)的查找時(shí)間復(fù)雜度為O(1)。10.4.1哈希函數(shù)

10.4.1哈希函數(shù)

10.4.1哈希函數(shù)（3）數(shù)字分析法提取關(guān)鍵字中有差異的那些位作為哈希地址的方法。10.4.2解決沖突方法對(duì)于2個(gè)不同的關(guān)鍵字ki和kj（i≠j）出現(xiàn)h(ki)=h(kj)，稱為哈希沖突（同義詞沖突）。發(fā)生哈希沖突的概率與裝填因子（α=n/m）有關(guān)。開放定址法（1）線性探測(cè)法迭代公式為：d0=h(k)，di=(di-1+1)modm(1≤i≤m-1)舉例：校車上的座位基本坐滿，1個(gè)老師上車后從車頭向車尾方向走，直到找到空位置坐下。在這個(gè)例子中，老師找空位置類似線性探測(cè)。10.4.2解決沖突方法

10.4.2解決沖突方法

10.4.2解決沖突方法

10.4.2解決沖突方法2.拉鏈法拉鏈法是把所有的同義詞用單鏈表鏈接起來的方法。10.4.2解決沖突的方法

10.4.3哈希表查找性能分析開放定址法性能分析10.4.3哈希表查找性能分析2.拉鏈法性能分析如圖10.28所示，拉鏈法的ASL成功和ASL不成功計(jì)算如下：10.5查找應(yīng)用【例10.1】設(shè)計(jì)1個(gè)算法，統(tǒng)計(jì)1個(gè)整數(shù)序列中每個(gè)整數(shù)出現(xiàn)的次數(shù)。思路：（1）將整數(shù)序列存入1個(gè)數(shù)組，設(shè)置1個(gè)TreeMap集合；（2）遍歷數(shù)組，每次將當(dāng)前元素添加到集合中，鍵存儲(chǔ)元素值，值存儲(chǔ)其出現(xiàn)的次數(shù)；（3）若當(dāng)前元素已經(jīng)在集合的鍵中，則將其值加1，否則將其值置1；（4）遍歷完成后，輸出集合所有“鍵-值”對(duì)元素。代碼見應(yīng)用10.110.5查找應(yīng)用【例10.2】設(shè)計(jì)1個(gè)算法，按學(xué)號(hào)遞增順序輸出學(xué)生的學(xué)號(hào)和姓名信息。思路：（1）創(chuàng)建1個(gè)含學(xué)號(hào)和姓名屬性的學(xué)生類Student；（2）Student去實(shí)現(xiàn)Comparable接口，重寫compareTo()方法，按學(xué)號(hào)升序排序；（3）構(gòu)造若干個(gè)學(xué)生實(shí)例對(duì)象，將他們添加到1個(gè)TreeSet集合中；（4）遍歷輸出該集合。代碼見應(yīng)用10.210.6查找學(xué)習(xí)總結(jié)順序查找算法簡(jiǎn)單，對(duì)查找表的存儲(chǔ)結(jié)構(gòu)無關(guān)，但不適合n很大情形。二分查找之前，需對(duì)關(guān)鍵字排序。分塊查找中，對(duì)索