數(shù)據(jù)結(jié)構(gòu)電子科技-第六章查找

現(xiàn)實生活中，有許多查找的例子：如到某學校找某個同學，郵遞員按信件收信人地址確定收信人的位置；在字典中查詢某個單詞；從海量信息中找到自己需要的信息等等。要查詢這些信息，涉及到兩個主要問題：一是數(shù)據(jù)如何組織——查找表，二是在查找表上如何查找——查找方法

。第六章查找

查找表是由同類型的數(shù)據(jù)元素(或記錄)構(gòu)成的集合?！靖拍睢獙Σ檎冶砘静僮?）查詢某個數(shù)據(jù)元素是否在查找表中；2）檢索某個數(shù)據(jù)元素的各種屬性；3）在查找表中插入一個數(shù)據(jù)元素；4）從查找表中刪去某個數(shù)據(jù)元素。僅作查詢和檢索操作的查找表。靜態(tài)查找表有時在查詢之后，將“查詢”結(jié)果“不在查找表中”的數(shù)據(jù)元素插入到查找表中；或者，從查找表中刪除其“查詢”結(jié)果為“在查找表中”的數(shù)據(jù)元素。動態(tài)查找表查找表分類關(guān)鍵字：是數(shù)據(jù)元素中某個數(shù)據(jù)項的值，用以標識一個數(shù)據(jù)元素。查找過程中，往往是依據(jù)數(shù)據(jù)元素的某個數(shù)據(jù)項進行查找，這個數(shù)據(jù)項通常是數(shù)據(jù)的關(guān)鍵字。

若關(guān)鍵字能標識唯一的一個數(shù)據(jù)元素，則稱謂主關(guān)鍵字。

若關(guān)鍵字能標識若干個數(shù)據(jù)元素，則稱謂次關(guān)鍵字。

根據(jù)給定的某個值，在查找表中確定一個其關(guān)鍵字等于給定值的數(shù)據(jù)元素。

查找

若查找表中存在這樣一個記錄，則稱“查找成功”。查找結(jié)果給出整個數(shù)據(jù)元素的信息，或指示該數(shù)據(jù)元素在查找表中的位置；否則稱“查找不成功”。查找方法評價查找速度占用存儲空間多少算法本身復雜程度平均查找長度ASL(AverageSearchLength)：為確定記錄在表中的位置，需和給定值進行比較的關(guān)鍵字的個數(shù)的期望值叫查找算法的~6.1順序表的查找6.1.1順序查找基本思想從表中指定位置（一般為最后一個，第0個位置設(shè)為崗哨）的記錄開始，沿某個方向?qū)⒂涗浀年P(guān)鍵字與給定值相比較，若某個記錄的關(guān)鍵字和給定值相等，則查找成功；反之，若找完整個順序表，都沒有與給定關(guān)鍵字值相等的記錄，則此順序表中沒有滿足查找條件的記錄，查找失敗。算法描述Ch7_1.ci例01234567891011513192137566475808892找6464監(jiān)視哨iiii比較次數(shù)=5比較次數(shù)：查找第n個元素：1查找第n-1個元素：2……….查找第1個元素：n查找第i個元素：n+1-i查找失?。簄+16.1.1順序查找3.性能分析空間復雜度：需要一個輔助存儲單元空間R[0]，因此，順序查找的空間復雜度為O(1)時間復雜度：查找算法的基本運算是給定值與順序表中記錄關(guān)鍵字值的比較。

最好情況：第一次比較就成功找到所需數(shù)據(jù)，這時，時間復雜度為O(1)。最壞情況：所查找的記錄不在順序表中，這時，需要和整個順序表的記錄進行比較，比較的次數(shù)為n，時間復雜度為O(n)。平均情況：需要和順序表中大約一半的記錄進行比較，即比較次數(shù)為n/2，因而，時間復雜度為O(n)。6.1.1順序查找4.順序表上順序查找的平均查找長度平均查找長度（ASL）：給定值與關(guān)鍵字比較次數(shù)的期望值。對于具有n個記錄的順序表，查找成功時的平均查找長度為：Pi——查找第i個記錄的概率Ci——找到第i個記錄數(shù)據(jù)需要比較的次數(shù)，對于順序表，Ci=n-i+16.1.1順序查找等概率情況不等概率ASL在Pn≥Pn-1≥···≥P2≥P1時取極小值若查找概率無法事先測定，可采取改進辦法：在每次查找之后，將查找到的記錄直接移至表尾。優(yōu)點：算法簡單，適用面廣缺點：平均查找長度較大。6.1.2折半查找查找過程：每次將待查記錄所在區(qū)間縮小一半適用條件：采用順序存儲結(jié)構(gòu)的有序表算法實現(xiàn)設(shè)表長為n，low、high和mid分別指向待查元素所在區(qū)間的上界、下界和中點,k為給定值初始時，令low=1,high=n,mid=(low+high)/2讓k與mid指向的記錄比較若k==r[mid].key，查找成功若k<r[mid].key，則high=mid-1若k>r[mid].key，則low=mid+1重復上述操作，直至low>high時，查找失敗算法描述lowhighmid例1234567891011513192137566475808892找211234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmidCh7_2.c例1234567891011513192137566475808892lowhighmid找701234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhigh6.1.2折半查找性能分析判定樹122333344443914257810116算法評價判定樹：描述查找過程的二叉樹叫~有n個結(jié)點的判定樹的深度為log2n+1折半查找法在查找過程中進行的比較次數(shù)最多不超過其判定樹的深度折半查找的ASL當n值較大時（n>50)，有次近似結(jié)果）4.折半查找特點

折半查找的查找效率高；平均查找性能和最壞性能相當接近；折半查找要求查找表為有序表；并且，折半查找只適用于順序存儲結(jié)構(gòu)。6.2索引表查找6.2.1索引表的基本概念索引書的目錄就是一種索引，使用索引能夠快速地定位查找范圍。

計算機中對數(shù)據(jù)的存儲和處理也可以采用索引。當數(shù)據(jù)量太大，以至內(nèi)存裝不下，可以對數(shù)據(jù)建立“索引”，根據(jù)索引將所需要的數(shù)據(jù)塊讀入內(nèi)存，這樣只需對讀入的部分數(shù)據(jù)進行查詢，提高查找效率。2.索引表的構(gòu)建分塊：按查找表中數(shù)據(jù)按關(guān)鍵字分成若干塊：R1,R2,…,RL，使得“分塊有序”，即第Rk

塊中所有關(guān)鍵字<Rk+1塊中所有關(guān)鍵字，k=1,2,…,L-1，2)建立索引項：對每一個塊建立一個索引項，每個索引項包含兩項內(nèi)容：關(guān)鍵字項：記載該塊中最大關(guān)鍵字值；指針項：記載該塊第一個記錄在表中位置。3)所有索引項組成索引表。3.索引表的查找索引表的查找分兩步進行：索引表上查找：由索引表確定記錄所在區(qū)間查找表上查找：在查找表的某個區(qū)間內(nèi)進行查找由于索引表有序，對索引表上的查找可用順序查找、二分查找或樹組織查找等方法。查找過程：將表分成幾塊，塊內(nèi)無序，塊間有序；先確定待查記錄所在塊，再在塊內(nèi)查找適用條件：分塊有序表算法實現(xiàn)用數(shù)組存放待查記錄,每個數(shù)據(jù)元素至少含有關(guān)鍵字域建立索引表，每個索引表結(jié)點含有最大關(guān)鍵字域和指向本塊第一個結(jié)點的指針算法描述Ch7_3.c12345678910111213141516171822121389203342443824486058745786532248861713索引表查38最大關(guān)鍵字起始地址分塊查找方法評價ASL（平均查找長度）

最大最小兩者之間表結(jié)構(gòu)有序表、無序表有序表分塊有序表存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)線性鏈表順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)線性鏈表查找方法比較順序查找折半查找分塊查找6.3哈希表的查找問題引入前面介紹的查找方法，都有一個共同特點：都是通過一系列比較來確定關(guān)鍵字為key的記錄在查找表中的地址。這些方法的平均查找長度都不為零。差別僅在于：關(guān)鍵字和給定值進行比較的順序不同。

我們總希望ASL=0，比較次數(shù)為0。如果記錄在表中的存放位置和其關(guān)鍵字之間存在著某種確定的關(guān)系，將會怎樣？我們有何計可施?6.3.1基本概念若將學號為xx000~xx999的學生記錄分別存放在查找表下標為000~999中，例如：為每年招收的1000名新生建立一張查找表，其關(guān)鍵字為學號，其值的范圍為xx000~xx999(前兩位為年份)。則查找過程為：取給定學號的后三位，不需要經(jīng)過比較，便可直接從查找表中找到給定學生的記錄。哈希查找基本思想：在記錄的存儲地址和它的關(guān)鍵字之間建立一個確定的對應(yīng)關(guān)系；這樣，不經(jīng)過比較，一次存取就能得到所查元素的查找方法定義哈希函數(shù)——在記錄的關(guān)鍵字與記錄的存儲地址之間建立的一種對應(yīng)關(guān)系叫~哈希函數(shù)是一種映象，是從關(guān)鍵字空間到存儲地址空間的一種映象哈希函數(shù)可寫成：addr(ai)=H(ki)ai是表中的一個元素addr(ai)是ai的存儲地址ki是ai的關(guān)鍵字關(guān)鍵字集合存儲地址集合hash哈希表——應(yīng)用哈希函數(shù)，由記錄的關(guān)鍵字確定記錄在表中的地址，并將記錄放入此地址，這樣構(gòu)成的表叫~哈希查找——又叫散列查找，利用哈希函數(shù)進行查找的過程叫~例30個地區(qū)的各民族人口統(tǒng)計表編號地區(qū)別總?cè)丝跐h族回族…...1北京2上海…...…...以編號作關(guān)鍵字，構(gòu)造哈希函數(shù)：H(key)=keyH(1)=1H(2)=2以地區(qū)別作關(guān)鍵字，取地區(qū)名稱第一個拼音字母的序號作哈希函數(shù)：H(Beijing)=2H(Shanghai)=19H(Shenyang)=19從例子可見：哈希函數(shù)只是一種映象，所以哈希函數(shù)的設(shè)定很靈活，只要使任何關(guān)鍵字的哈希函數(shù)值都落在表長允許的范圍之內(nèi)即可沖突：key1key2，但H(key1)=H(key2)的現(xiàn)象叫~同義詞：具有相同函數(shù)值的兩個關(guān)鍵字，叫該哈希函數(shù)的~哈希函數(shù)通常是一種壓縮映象，所以沖突不可避免，只能盡量減少；同時，沖突發(fā)生后，應(yīng)該有處理沖突的方法哈希函數(shù)的構(gòu)造方法直接哈希函數(shù)法構(gòu)造：取關(guān)鍵字或關(guān)鍵字的某個線性函數(shù)作哈希地址，即H(key)=key或H(key)=a·key+b例如：有一個解放后出生人口調(diào)查表，每個記錄包含年份、人數(shù)等數(shù)據(jù)項，其中年分為關(guān)鍵字，則哈希函數(shù)可取為:H（key）=key+（-1948）這樣就可以方便地存儲和查找1948年后任一年的記錄。地址01……22……年份1949……1970……人數(shù)……特點直接定址法所得地址集合與關(guān)鍵字集合大小相等，不會發(fā)生沖突實際中能用這種哈希函數(shù)的情況很少數(shù)字分析法構(gòu)造：對關(guān)鍵字進行分析，取關(guān)鍵字的若干位或其組合作哈希地址適于關(guān)鍵字位數(shù)比哈希地址位數(shù)大，且可能出現(xiàn)的關(guān)鍵字事先知道的情況例有80個記錄，關(guān)鍵字為8位十進制數(shù)，哈希地址為2位十進制數(shù)8134653281372242813874228130136781322817813389678136853781419355…..…..分析：只取8只取1只取3、4只取2、7、5數(shù)字分布近乎隨機所以：取任意兩位或兩位與另兩位的疊加作哈希地址6.3.2哈希函數(shù)3.平方取中法取關(guān)鍵字平方后的中間幾位作為哈希地址，即哈希函數(shù)為：

H（key）=“key2的中間幾位”，其中，所取的位數(shù)由哈希表的大小確定數(shù)據(jù)關(guān)鍵字(關(guān)鍵字)2哈希地址(217~29)A01000010000010I11001210000210J12001440000440I011601370400370P120614310541310P220624314704314Q121614734741734Q221624741304741Q321634745651745

以關(guān)鍵字的平方值的中間幾位作為存儲地址。求“關(guān)鍵字的平方值”的目的是“擴大差別”和“貢獻均衡”。即：關(guān)鍵字的各位都在平方值的中間幾位有所貢獻，Hash值中應(yīng)該有各位影子。適于不知道全部關(guān)鍵字情況平方取中法思想折疊法構(gòu)造：將關(guān)鍵字分割成位數(shù)相同的幾部分，然后取這幾部分的疊加和（舍去進位）做哈希地址種類移位疊加：將分割后的幾部分低位對齊相加間界疊加：從一端沿分割界來回折送，然后對齊相加適于關(guān)鍵字位數(shù)很多，且每一位上數(shù)字分布大致均勻情況例關(guān)鍵字為：，哈希地址位數(shù)為4586442200410088H(key)=0088移位疊加5864022404

6092H(key)=6092間界疊加除留余數(shù)法構(gòu)造：取關(guān)鍵字被某個不大于哈希表表長m的數(shù)p除后所得余數(shù)作哈希地址，即H(key)=keyMODp，pm特點簡單、常用，可與上述幾種方法結(jié)合使用p的選取很重要；p選的不好，容易產(chǎn)生同義詞隨機數(shù)法構(gòu)造：取關(guān)鍵字的隨機函數(shù)值作哈希地址，即H(key)=random(key)適于關(guān)鍵字長度不等的情況選取哈希函數(shù)，考慮以下因素：計算哈希函數(shù)所需時間關(guān)鍵字長度哈希表長度（哈希地址范圍）關(guān)鍵字分布情況記錄的查找頻率6.3哈希表的查找6.3.3沖突處理沖突：是指由關(guān)鍵字得到的Hash地址上已有其他記錄。沖突處理：為出現(xiàn)哈希地址沖突的關(guān)鍵字尋找下一個哈希地址。好的哈希函數(shù)可以減少沖突，但很難避免沖突。常見的沖突處理方法有：開放地址法再哈希法鏈地址法公共溢出區(qū)法處理沖突的方法開放定址法方法：當沖突發(fā)生時，形成一個探查序列；沿此序列逐個地址探查，直到找到一個空位置（開放的地址），將發(fā)生沖突的記錄放到該地址中，即Hi=(H(key)+di)MODm，i=1,2,……k(km-1)其中：H(key)——哈希函數(shù)

m——哈希表表長

di——增量序列分類線性探測再散列：di=1,2,3,……m-1平方探測再散列：di=12,-12,22,-22,32,……±k2(km/2)偽隨機探測再散列：di=偽隨機數(shù)序列例表長為11的哈希表中已填有關(guān)鍵字為17，60，29的記錄，

H(key)=keyMOD11,現(xiàn)有第4個記錄，其關(guān)鍵字為38，按三種處理沖突的方法，將它填入表中012345678910601729(1)H(38)=38MOD11=5沖突

H1=(5+1)MOD11=6沖突

H2=(5+2)MOD11=7沖突

H3=(5+3)MOD11=8不沖突38(2)H(38)=38MOD11=5沖突

H1=(5+12)MOD11=6沖突

H2=(5-12)MOD11=4不沖突38(3)H(38)=38MOD11=5沖突設(shè)偽隨機數(shù)序列為9，則：

H1=(5+9)MOD11=3不沖突38再哈希法方法：構(gòu)造若干個哈希函數(shù)，當發(fā)生沖突時，計算下一個哈希地址，即：Hi=Rhi(key)i=1,2,……k其中：Rhi——不同的哈希函數(shù)特點：計算時間增加鏈地址法方法：將所有關(guān)鍵字為同義詞的記錄存儲在一個單鏈表中，并用一維數(shù)組存放頭指針例已知一組關(guān)鍵字(19,14,23,1,68,20,84,27,55,11,10,79)

哈希函數(shù)為：H(key)=keyMOD13,

用鏈地址法處理沖突0123456789101112

14^127796855198420231011^^^^^^^^^^^^6.3.3沖突處理4.公共溢出區(qū)法假設(shè)某哈希函數(shù)的值域[0,m-1]，向量HashTable[0,m-1]為基本表，每個分量存放一個記錄，另設(shè)一個向量OverTable[0,v]為溢出表。將與基本表中的關(guān)鍵字發(fā)生沖突的所有記錄都填入溢出表中。如一組關(guān)鍵字序列為{19，14，23，01，68，20，84，27，55，11，10，79}，哈希函數(shù)為H（key）=keymod13，采用公共溢出區(qū)法得到的結(jié)果為：哈希查找過程及分析哈希查找過程給定k值計算H(k)此地址為空關(guān)鍵字==k查找失敗查找成功按處理沖突方法計算HiYNYN例已知一組關(guān)鍵字(19,14,23,1,68,20,84,27,55,11,10,79)

哈希函數(shù)為：H(key)=keyMOD13,哈希表長為m=16，

設(shè)每個記錄的查找概率相等(1)用線性探測再散列處理沖突，即Hi=(H(key)+di)MODmH(55)=3沖突，H1=(3+1)MOD16=4

沖突，H2=(3+2)MOD16=5H(79)=1沖突，H1=(1+1)MOD16=2

沖突，H2=(1+2)MOD16=3

沖突，H3=(1+3)MOD16=4

沖突，H4=(1+4)MOD16=5

沖突，H5=(1+5)MOD16=6

沖突，H6=(1+6)MOD16=7

沖突，H7=(1+7)MOD16=8

沖突，H8=(1+8)MOD16=90123456789101112131415ASL=(1*6+2+3*3+4+9)/12=2.514168275519208479231110H(19)=6H(14)=1H(23)=10H(1)=1沖突，H1=(1+1)MOD16=2H(68)=3H(20)=7H(84)=6沖突，H1=(6+1)MOD16=7

沖突，H2=(6+2)MOD16=8H(27)=1沖突，H1=(1+1)MOD16=2

沖突，H2=(1+2)MOD16=3

沖突，H3=(1+3)MOD16=4H(11)=