查找的概念順序查找折半查找分塊查找哈希查找,第六章查找,查找也叫檢索，是根據(jù)給定的某個(gè)值，在表中確定一個(gè)關(guān)鍵字等于給定值的記錄或數(shù)據(jù)元素關(guān)鍵字是數(shù)據(jù)元素中某個(gè)數(shù)據(jù)項(xiàng)的值，它可以標(biāo)識(shí)一個(gè)數(shù)據(jù)元素查找方法評(píng)價(jià)查找速度占用存儲(chǔ)空間多少算法本身復(fù)雜程度平均查找長(zhǎng)度ASL(AverageSearchLength)：為確定記錄在表中的位置，需和給定值進(jìn)行比較的關(guān)鍵字的個(gè)數(shù)的期望值叫查找算法的,查找的概念,順序查找查找過(guò)程：從表的一端開(kāi)始逐個(gè)進(jìn)行記錄的關(guān)鍵字和給定值的比較算法描述,64,監(jiān)視哨,比較次數(shù)=5,比較次數(shù)：查找第n個(gè)元素：1查找第n-1個(gè)元素：2.查找第1個(gè)元素：n查找第i個(gè)元素：n+1-i查找失敗：n+1,順序查找#defineMAXITEM100structelementintkey;/關(guān)鍵字intdata;/其他數(shù)據(jù);typedefstructelementsqlistMAXITEM;intseqsrch(sqlistr,intk,intn)/k為給定值，返回i為關(guān)鍵字等于k的記錄在表r中的序號(hào)，/i值為0表示查找不成功r0.key=k;i=n;while(ri.key!=k)i-;return(i);,順序查找方法的ASL,折半查找查找過(guò)程：每次將待查記錄所在區(qū)間縮小一半適用條件：采用順序存儲(chǔ)結(jié)構(gòu)的有序表算法實(shí)現(xiàn)設(shè)表長(zhǎng)為n，low、high和mid分別指向待查元素所在區(qū)間的上界、下界和中點(diǎn),k為給定值初始時(shí)，令low=1,high=n,mid=(low+high)/2讓k與mid指向的記錄比較若k=rmid.key，查找成功若krmid.key，則low=mid+1重復(fù)上述操作，直至lowhigh時(shí)，查找失敗,算法描述,折半查找intbinsrch(sqlistr,intk,intn)/k為給定值，返回i為關(guān)鍵字等于k的記錄在表r中的序號(hào)，/i值為0表示查找不成功inti,low=1,high=n,mid,find=0;while(lowrmid.key)low=mid+1;elsei=mid;find=1;if(!find)i=0;return(i);,算法評(píng)價(jià)判定樹(shù)：描述查找過(guò)程的二叉樹(shù)叫有n個(gè)結(jié)點(diǎn)的判定樹(shù)的深度為log2n+1折半查找法在查找過(guò)程中進(jìn)行的比較次數(shù)最多不超過(guò)其判定樹(shù)的深度折半查找的ASL,分塊查找（索引順序查找）查找過(guò)程：將表分成幾塊，塊內(nèi)無(wú)序，塊間有序；先確定待查記錄所在塊，再在塊內(nèi)查找適用條件：分塊有序表算法實(shí)現(xiàn)用數(shù)組存放待查記錄,每個(gè)數(shù)據(jù)元素至少含有關(guān)鍵字域建立索引表，每個(gè)索引表結(jié)點(diǎn)含有最大關(guān)鍵字域和指向本塊第一個(gè)結(jié)點(diǎn)的指針?biāo)惴枋?分塊查找方法評(píng)價(jià),哈希查找基本思想：在記錄的存儲(chǔ)地址和它的關(guān)鍵字之間建立一個(gè)確定的對(duì)應(yīng)關(guān)系；這樣，不經(jīng)過(guò)比較，一次存取就能得到所查元素的查找方法定義哈希函數(shù)在記錄的關(guān)鍵字與記錄的存儲(chǔ)地址之間建立的一種對(duì)應(yīng)關(guān)系叫哈希函數(shù)是一種映象，是從關(guān)鍵字空間到存儲(chǔ)地址空間的一種映象哈希函數(shù)可寫成：addr(ai)=H(ki)ai是表中的一個(gè)元素addr(ai)是ai的存儲(chǔ)地址ki是ai的關(guān)鍵字,哈希表應(yīng)用哈希函數(shù)，由記錄的關(guān)鍵字確定記錄在表中的地址，并將記錄放入此地址，這樣構(gòu)成的表叫哈希查找又叫散列查找，利用哈希函數(shù)進(jìn)行查找的過(guò)程叫,以編號(hào)作關(guān)鍵字，構(gòu)造哈希函數(shù)：H(key)=keyH(1)=1H(2)=2,以地區(qū)別作關(guān)鍵字，取地區(qū)名稱第一個(gè)拼音字母的序號(hào)作哈希函數(shù)：H(Beijing)=2H(Shanghai)=19H(Shenyang)=19,從例子可見(jiàn)：哈希函數(shù)只是一種映象，所以哈希函數(shù)的設(shè)定很靈活，只要使任何關(guān)鍵字的哈希函數(shù)值都落在表長(zhǎng)允許的范圍之內(nèi)即可沖突：key1key2，但H(key1)=H(key2)的現(xiàn)象叫同義詞：具有相同函數(shù)值的兩個(gè)關(guān)鍵字，叫該哈希函數(shù)的哈希函數(shù)通常是一種壓縮映象，所以沖突不可避免，只能盡量減少；同時(shí)，沖突發(fā)生后，應(yīng)該有處理沖突的方法哈希函數(shù)的構(gòu)造方法直接定址法構(gòu)造：取關(guān)鍵字或關(guān)鍵字的某個(gè)線性函數(shù)作哈希地址，即H(key)=key或H(key)=akey+b特點(diǎn)直接定址法所得地址集合與關(guān)鍵字集合大小相等，不會(huì)發(fā)生沖突實(shí)際中能用這種哈希函數(shù)的情況很少,數(shù)字分析法構(gòu)造：對(duì)關(guān)鍵字進(jìn)行分析，取關(guān)鍵字的若干位或其組合作哈希地址適于關(guān)鍵字位數(shù)比哈希地址位數(shù)大，且可能出現(xiàn)的關(guān)鍵字事先知道的情況,例有80個(gè)記錄，關(guān)鍵字為8位十進(jìn)制數(shù)，哈希地址為2位十進(jìn)制數(shù),分析：只取8只取1只取3、4只取2、7、5數(shù)字分布近乎隨機(jī)所以：取任意兩位或兩位與另兩位的疊加作哈希地址,平方取中法構(gòu)造：取關(guān)鍵字平方后中間幾位作哈希地址適于不知道全部關(guān)鍵字情況折疊法構(gòu)造：將關(guān)鍵字分割成位數(shù)相同的幾部分，然后取這幾部分的疊加和（舍去進(jìn)位）做哈希地址種類移位疊加：將分割后的幾部分低位對(duì)齊相加間界疊加：從一端沿分割界來(lái)回折送，然后對(duì)齊相加適于關(guān)鍵字位數(shù)很多，且每一位上數(shù)字分布大致均勻情況,例關(guān)鍵字為：0442205864，哈希地址位數(shù)為4,除留余數(shù)法構(gòu)造：取關(guān)鍵字被某個(gè)不大于哈希表表長(zhǎng)m的數(shù)p除后所得余數(shù)作哈希地址，即H(key)=keyMODp，pm特點(diǎn)簡(jiǎn)單、常用，可與上述幾種方法結(jié)合使用p的選取很重要；p選的不好，容易產(chǎn)生同義詞隨機(jī)數(shù)法構(gòu)造：取關(guān)鍵字的隨機(jī)函數(shù)值作哈希地址，即H(key)=random(key)適于關(guān)鍵字長(zhǎng)度不等的情況選取哈希函數(shù)，考慮以下因素：計(jì)算哈希函數(shù)所需時(shí)間關(guān)鍵字長(zhǎng)度哈希表長(zhǎng)度（哈希地址范圍）關(guān)鍵字分布情況記錄的查找頻率,處理沖突的方法開(kāi)放定址法方法：當(dāng)沖突發(fā)生時(shí)，形成一個(gè)探查序列；沿此序列逐個(gè)地址探查，直到找到一個(gè)空位置（開(kāi)放的地址），將發(fā)生沖突的記錄放到該地址中，即Hi=(H(key)+di)MODm，i=1,2,k(km-1)其中：H(key)哈希函數(shù)m哈希表表長(zhǎng)di增量序列分類線性探測(cè)再散列：di=1,2,3,m-1二次探測(cè)再散列：di=1,-1,2,-2,3,k(km/2)偽隨機(jī)探測(cè)再散列：di=偽隨機(jī)數(shù)序列,例表長(zhǎng)為11的哈希表中已填有關(guān)鍵字為17，60，29的記錄，H(key)=keyMOD11,現(xiàn)有第4個(gè)記錄，其關(guān)鍵字為38，按三種處理沖突的方法，將它填入表中,(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+1)MOD11=6沖突H2=(5-1)MOD11=4不沖突,38,(3)H(38)=38MOD11=5沖突設(shè)偽隨機(jī)數(shù)序列為9，則：H1=(5+9)MOD11=3不沖突,38,再哈希法方法：構(gòu)造若干個(gè)哈希函數(shù)，當(dāng)發(fā)生沖突時(shí)，計(jì)算下一個(gè)哈希地址，即：Hi=RHi(key)i=1,2,k其中：RHi不同的哈希函數(shù)特點(diǎn)：計(jì)算時(shí)間增加鏈地址法方法：將所有關(guān)鍵字為同義詞的記錄存儲(chǔ)在一個(gè)單鏈表中，并用一維數(shù)組存放頭指針,例已知一組關(guān)鍵字(19,14,23,1,68,20,84,27,55,11,10,79)哈希函數(shù)為：H(key)=keyMOD13,用鏈地址法處理沖突,哈希查找過(guò)程及分析哈希查找過(guò)程,哈希查找分析哈希查找過(guò)程仍是一個(gè)給定值與關(guān)鍵字進(jìn)行比較的過(guò)程評(píng)價(jià)哈希查找效率仍要用ASL哈希查找過(guò)程與給定值進(jìn)行比較的關(guān)鍵字的個(gè)數(shù)取決于：哈希函數(shù)處理沖突的方法哈希表的裝填因子=表中填入的記錄數(shù)/哈希表長(zhǎng)度,例已知一組關(guān)鍵字(19,14,23,1,68,20,84,27,55,11,10,79)哈希函數(shù)為：H(key)=keyMOD13,哈希表長(zhǎng)為m=16，設(shè)每個(gè)記錄的查找概率相等,(1)用線性探測(cè)再散列處理沖突，即Hi=(H(key)+di)MODm,H(55)=3沖突，H1=(3+1)MOD16=4沖突，H2=(3+2)MOD16=5,H(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=9,ASL=(1*6+2+3*3+4+9)/12=2.5,14,1,68,27,55,19,20,84,79,23,11,10,H(19)=6,H(14)=1,H(23)=10,H(1)=1沖突，H1=(1+1)MOD16=2,H(68)=3,H(20)=7,H(84)=6沖突，H1=(6+1)MOD16=7沖突，H2=(6+2)MOD16=8,H(27)=1沖突，H1=(1+1)MOD16=2沖突，H2=(1+2)MOD16=3沖突，H3=(1+3)MOD16=4,H(11)=11,H(10)=10沖突，H1=(10+1