算數(shù)提高課件字典

1第六章字典與檢索數(shù)據(jù)結(jié)構(gòu)與算法張路

2字典與檢索教學(xué)目的：介紹字典的線性表表示、散列表表示和樹型表示。教學(xué)重點(diǎn)：重點(diǎn)掌握順序查找、二分查找，二叉排序樹查找以及散列表查找的基本思想和算法實(shí)現(xiàn)。教學(xué)難點(diǎn)：二叉排序樹的刪除算法。3內(nèi)容提要基本概念根據(jù)字典（檢索的對象）的不同組織方式，定義不同的檢索策略已排序的順序表=>順序檢索和二分檢索散列表示=>散列函數(shù)樹型表示=>二叉排序樹、B樹、B+樹4字典字典(Dictionary)是一種特殊的集合，其主要的操作為字典中元素的檢索。字典是元素的有窮集合，其中每個元素由兩部分組成，分別稱為元素的“關(guān)鍵碼”(key)和“屬性”(attribute)。例：英漢字典中，每個詞條是一個元素，詞條中的英文單詞可看作是該元素的關(guān)鍵碼，詞條中對該英文單詞的解釋可看作是元素的屬性。字典中的兩個元素能夠根據(jù)其關(guān)鍵碼進(jìn)行比較，對字典元素的存取、檢索也是以關(guān)鍵碼為依據(jù)進(jìn)行的。稱關(guān)鍵碼和屬性存在關(guān)聯(lián)(Association)。5檢索檢索：給定一個值key，在字典中找出關(guān)鍵碼等于key的元素如果找到，則檢索成功否則檢索失敗為了便于字典的維護(hù)，有時(shí)也要考慮在字典中插入和刪除元素的操作6字典的種類靜態(tài)(static)字典：字典一經(jīng)建立就基本固定不變，主要的操作就是字典元素的檢索為靜態(tài)字典選擇存儲方法主要需考慮檢索效率、檢索運(yùn)算的簡單性動態(tài)(dynamic)字典：經(jīng)常需要改動的字典對于動態(tài)字典，存儲方法的選擇不僅要考慮檢索效率，還要考慮字典元素的插入、刪除運(yùn)算是否簡便。7檢索算法的效率衡量一個檢索算法效率的主要標(biāo)準(zhǔn)是檢索過程中和關(guān)鍵碼的平均比較次數(shù)，即平均檢索長度ASL(AverageSearchLength)，定義為：n是字典中元素的個數(shù)。pi是查找第i個元素的概率。若不特別聲明，一般認(rèn)為每個元素的檢索概率相等，即pi=1/nci是找到第i個元素的比較次數(shù)。算法的空間開銷，以及算法是否易于理解等因素。8本章中的假定在本章的討論中，假設(shè)字典元素類型相同，且關(guān)鍵碼為數(shù)值類型（例如正整數(shù)），因此，可以將字典元素按關(guān)鍵碼排序9內(nèi)容提要基本概念字典的順序表表示順序檢索二分檢索字典的散列表示=>散列函數(shù)字典的樹型表示=>二叉排序樹、B樹、B+樹10字典的順序表示定義//為了描述簡單，將KeyType和DataType定義為int類型typedefint KeyType;typedefint DataType;typedefstruct{ KeyTypekey; /*字典元素的關(guān)鍵碼字段*/ DataTypeother; /*字典元素的屬性字段*/}DicElement;typedefstruct{ DicElementelement[MAXNUM]; intn; /*n<MAXNUM，為字典中元素的個數(shù)*/}SeqDictionary;11順序檢索算法算法結(jié)束時(shí)返回檢索成功或失敗信息若檢索成功，則參數(shù)position指向找到的元素位置否則，position指向應(yīng)插入元素的位置intSeqSearch(SeqDictionary*pdic,KeyTypekey,int*pos)/*在字典中順序檢索關(guān)鍵碼為key的元素*/{inti;for(i=0;i<pdic->n;i++)/*從頭開始*/{if(pdic->element[i].key==key)/*成功*/{*pos=i; returnTRUE;}}*pos=i;returnFALSE;/*失敗*/}12順序檢索的插入intSeqInsert(SeqDictionary*pdic,KeyTypekey,intpos)/*在字典中順序檢索關(guān)鍵碼為key的元素*/{ if(pdic->n==MAXNUM) returnFALSE;

/*溢出*/

pdic->element[pos].key=key; pdic->n++; returnTRUE;/*成功*/}13順序檢索的平均檢索長度若找到的是第i個元素，則比較次數(shù)為ci=i。因此，ASL=1×P1+2×P2+…+n×Pn假設(shè)每個元素的檢索概率相等，即Pi=1/n，則平均檢索長度為：因此，成功檢索的平均比較次數(shù)約為字典長度的一半；若字典中不存在關(guān)鍵碼為key的元素，則需進(jìn)行n次比較?？傊?，順序檢索的平均檢索時(shí)間為ASL=O(n)14順序檢索的改進(jìn)在不等概率情況下，當(dāng)P1≥P2…≥Pn時(shí)，順序檢索需要使ASL最小，應(yīng)該保持概率最大的元素在最前面，概率最小的元素在最后面。通常，無法預(yù)先知道各個元素的查找概率，解決的辦法是為用檢索成功次數(shù)代替查找概率，當(dāng)檢索元素成功時(shí)，其檢索成功次數(shù)加1，保持檢索成功次數(shù)最大的元素在前面，檢索成功次數(shù)最小的元素在最后面。15順序檢索的特點(diǎn)順序檢索優(yōu)點(diǎn)：

算法簡單且適應(yīng)面廣，無論字典中元素是否有序均可使用。插入效率很高。順序檢索缺點(diǎn)：

平均檢索長度較大，特別是當(dāng)n很大時(shí)，檢索效率較低。16順序表表示基本概念字典的順序表表示順序檢索二分法檢索字典的散列表示字典的索引和樹型表示17二分法檢索二分法檢索(折半檢索)要求字典元素已按關(guān)鍵碼排序?；舅枷耄菏紫葘⒆值渲虚g位置上元素的關(guān)鍵碼和給定值key比較，如果相等，則檢索成功；否則，若大于key，則在字典前半部分中繼續(xù)進(jìn)行二分法檢索；否則，在字典后半部分中繼續(xù)進(jìn)行二分法檢索。折半檢索的實(shí)質(zhì)是逐步縮小查找區(qū)間的查找方法。18有序順序表的插入intBinInsert(SeqDictionary*pdic,KeyTypekey,intpos)/*在字典中順序檢索關(guān)鍵碼為key的元素*/{ if(pdic->n==MAXNUM) returnFALSE;

/*溢出*/

inti; for(i=pdic->n;i>pos;i--) pdic->element[i]=pdic->element[i-1];

pdic->element[pos].key=key; pdic->n++; returnTRUE;/*成功*/}19二分檢索算法的時(shí)間復(fù)雜性分析每比較一次縮小一半的查找區(qū)間。查找過程可用二叉樹來描述。樹中結(jié)點(diǎn)數(shù)字表示結(jié)點(diǎn)在有序表中的位置，通常稱這個描述查找過程的二叉樹為判定樹。01234567891005，10，18，25，27，32，41，51，68，73，99536092810714右圖為11個記錄的判定樹。如要檢索第3、9個記錄需要2次比較；檢索第1、4、7、10個記錄需要3次比較20二分檢索算法的時(shí)間復(fù)雜性分析折半檢索的過程恰好是在判定樹中走了一條從根到檢索結(jié)點(diǎn)的路徑，比較的關(guān)鍵碼個數(shù)恰為該結(jié)點(diǎn)在二叉樹中的層數(shù)。因此，成功折半檢索關(guān)鍵碼比較次數(shù)不會超過樹的深度：那么，折半檢索的ASL等于多少？53609281071421假定記錄數(shù)n=2h-1，即h=log2(n+1)，則描述折半檢索的判定樹是一棵深度為h-1的滿二叉樹。在該滿二叉判定樹中，有：

層數(shù)為0的結(jié)點(diǎn)個數(shù)為20，比較1次；層數(shù)為1的結(jié)點(diǎn)個數(shù)為21，比較2次；

……

層數(shù)為k的結(jié)點(diǎn)個數(shù)為2k，比較k+1次；

……

層數(shù)為h-1的結(jié)點(diǎn)個數(shù)為2h-1，比較h次；等概率檢索下，檢索成功時(shí)二分檢索算法的時(shí)間復(fù)雜性分析22

當(dāng)n很大時(shí)，如n>100，則得到:ASL≈log2(n+1)-123二分法檢索特點(diǎn)二分法檢索的優(yōu)點(diǎn)

折半檢索的效率要高于順序檢索。如n=1000，順序ASL=500，而折半ASL≈9。 比較次數(shù)少，檢索速度快。二分法檢索缺點(diǎn)

要將字典按關(guān)鍵碼排序，且只適用于順序存儲結(jié)構(gòu)。插入的效率低。24內(nèi)容提要基本概念字典的順序表表示字典的散列表示散列表散列函數(shù)存儲表示與碰撞的處理字典的索引和樹型表示25散列表前面的檢索方法都是通過給定值與關(guān)鍵碼的比較才能確定記錄位置，檢索效率與檢索過程中進(jìn)行的比較次數(shù)有關(guān)。散列法(hashing)/雜湊法/關(guān)鍵碼地址轉(zhuǎn)換法是一種基于盡可能不通過比較操作而直接得到記錄的存儲位置的想法而提出來的存儲和檢索方法。設(shè)一個字典元素，若其關(guān)鍵碼為key，按一個確定的散列函數(shù)h計(jì)算h(key)，并把h(key)作為該元素的存儲地址，即散列地址。檢索時(shí)仍需要根據(jù)h(key)得到關(guān)鍵碼所在元素的存儲地址。散列表/哈希表/Hash表：用散列法表示的字典。26散列相關(guān)概念碰撞：如果兩個不相等的關(guān)鍵碼key1和key2，用散列函數(shù)h得到相同的散列地址h(key1)=h(key2)，這種現(xiàn)象稱為碰撞。發(fā)生碰撞的兩個(或多個)關(guān)鍵碼稱為同義詞.h(key)的值域所對應(yīng)的地址空間稱為基本區(qū)域.發(fā)生碰撞時(shí)，同義詞可以存放在基本區(qū)域中未被占用的單元，也可以放到基本區(qū)域以外另開辟的區(qū)域（稱溢出區(qū)）當(dāng)時(shí)碰撞不可避免。27散列表的構(gòu)造和檢索散列表的構(gòu)造和檢索中，需要解決的主要問題包括：對于任意的散列函數(shù)，都可能出現(xiàn)“碰撞”現(xiàn)象。因此，如何選擇合適的散列函數(shù)減少碰撞發(fā)生是Hash表構(gòu)造中的一個關(guān)鍵問題。碰撞發(fā)生時(shí)如何處理？散列表如何檢索？檢索效率如何？檢索效率與哪些因素有關(guān)？28散列表示散列表散列函數(shù)存儲表示與碰撞的處理29散列函數(shù)的選擇標(biāo)準(zhǔn)散列函數(shù)的選擇在散列表的構(gòu)造和檢索中是非常重要的，合適的散列函數(shù)可以減少碰撞的發(fā)生，提高檢索效率。散列函數(shù)的構(gòu)造很靈活，只要使得任何關(guān)鍵字由此所得到的哈希函數(shù)值落在表長的范圍內(nèi)。散列函數(shù)的選擇標(biāo)準(zhǔn)：對于字典中的任一個關(guān)鍵碼，經(jīng)散列函數(shù)映象到地址集合中任何一個地址的概率是相等的，即關(guān)鍵字的散列地址均勻分布在整個地址空間中，從而減少碰撞；散列函數(shù)盡可能簡單，提高計(jì)算速度。30常用的散列函數(shù)直接定址法數(shù)字分析法平方取中法折疊法除留余數(shù)法基數(shù)轉(zhuǎn)換法31直接定址法取關(guān)鍵字或關(guān)鍵字的某個線性函數(shù)值為散列地址h(key)=a*key+b（a和b為常數(shù)）適用于關(guān)鍵碼分布基本連續(xù)情況。若關(guān)鍵碼分布不連續(xù)，容易造成空單元，存儲空間浪費(fèi)。1~100歲人口數(shù)字統(tǒng)計(jì)表（a=1,b=0,key=年齡）解放后人口調(diào)查地址010203...252627...100年齡123...252627...100人數(shù)300020005000...1050............地址010203...22年份194919501951...1970人數(shù)1500032數(shù)字分析法關(guān)鍵碼數(shù)位比存儲區(qū)的地址碼位數(shù)多，這時(shí)可以對各位進(jìn)行分析，丟掉分布不均勻的位而留下均勻的位作為地址。例如：(395003,395010,395012,395085,395097)，前四位相同，后兩位隨機(jī)分布，故可以取后兩位構(gòu)成散列函數(shù)，得到的散列地址為（03，10，12，85，97）通常用于已知記錄關(guān)鍵碼，并且關(guān)鍵碼各位分布已經(jīng)知道的情況，適合于靜態(tài)的字典。33平方取中法先求出關(guān)鍵碼的平方，然后取中間若干位構(gòu)成散列函數(shù)。例如：key=4731，key2=22382361，如地址碼為3位，則可以取382為散列地址，即h(4731)=382這是一種較常用的構(gòu)造散列函數(shù)的方法，一個數(shù)在平方后的中間幾位數(shù)和每一位都相關(guān)，由此使隨機(jī)分布的關(guān)鍵字得到的散列地址也是隨機(jī)的。取的位數(shù)由表長決定。34折疊法如果關(guān)鍵碼的位數(shù)多于地址位數(shù)，且關(guān)鍵碼中每一位分布均勻時(shí)，此時(shí)可以將關(guān)鍵碼分成若干部分，其中一部分的長度等于地址位數(shù)。各部分相加，舍棄進(jìn)位，最后的和作為散列地址。如：key=，地址位數(shù)為4。

2241224182422428+)05+)05[1]04884674移位相加間界疊加35除留余數(shù)法h(key)=key%pp的選擇非常重要，通常選小于等于散列表長度m的符合一定要求的最大數(shù)（比如要求是素?cái)?shù)）。如：除留余數(shù)法計(jì)算簡單，許多情況下效果較好，是一種常用的散列函數(shù)。m=81632641282565121024p=7133161127251503101936基數(shù)轉(zhuǎn)換法將關(guān)鍵碼首先看作是另一進(jìn)制的表示，然后再轉(zhuǎn)換為原來的進(jìn)制數(shù)，用數(shù)字分析法取若干位作為散列地址。一般轉(zhuǎn)換基數(shù)大于原基數(shù)，且最好二者互素。例如：key=(236075)10,把它看作13進(jìn)制數(shù)(236075)13,再轉(zhuǎn)換為10進(jìn)制，地址位數(shù)為4：

(236075)13=2*135+3*134+6*133+7*131+5=(841547)10

選擇2~5，得到散列地址h(236075)=415437選取散列函數(shù)的因素考慮的因素：計(jì)算散列函數(shù)所需時(shí)間關(guān)鍵字的長度散列表的大小關(guān)鍵字的分布情況記錄的查找頻率無論選擇何種散列函數(shù)，碰撞都可能發(fā)生。換句話講，合適的散列函數(shù)可以減少碰撞發(fā)生的幾率，但不能保證不發(fā)生碰撞。＝>碰撞發(fā)生時(shí)如何處理？38散列表示散列表散列函數(shù)存儲表示與碰撞的處理39存儲表示與碰撞的處理開地址法（探查法）線性探查法雙散列函數(shù)法拉鏈法40開地址法基本思想：當(dāng)碰撞發(fā)生時(shí)，用某種方法在基本區(qū)域內(nèi)形成一個探查序列，沿著探查序列逐個單元查找，直到找到該元素或碰到一個未被占用的地址為止若插入元素，則碰到空的地址單元就存放要插入的同義詞。若檢索元素，則碰到空的地址單元說明表中沒有待查的元素形成探查序列的方法有多種，下面介紹兩種探查方法：線性探查法雙散列函數(shù)法41線性探查法將基本存貯區(qū)看作一個循環(huán)表。若在地址為d(d=h(key))的單元發(fā)生碰撞，則依次探查下述地址單元：d+1,d+2,…,m-1,0,1,…,d-1(m為基本存貯區(qū)的長度)，直到找到一個空單元或查找到關(guān)鍵碼為key的元素為止。如果從單元d開始探查，查找一遍后，又回到地址d，則表示基本存貯區(qū)已經(jīng)溢出。42示例設(shè)散列表用數(shù)組element表示，關(guān)鍵碼集合K={18，73，10，05，68，99，27，41，51，32，25}，用線性探查法解決碰撞：m=13，散列函數(shù)為h(key)=key%13；

h(18)=5, h(73)=8,h(10)=10,h(05)=5,h(68)=3, h(99)=8，h(27)=1,h(41)=2, h(51)=12,h(32)=6, h(25)=12計(jì)算散列地址d=key%13，若地址未被占用，則插入新結(jié)點(diǎn)；否則進(jìn)行線性探查。43示例(續(xù))插入18,73,10時(shí)，地址都未被占用，可以直接存放；插入05時(shí)，其地址與18的地址發(fā)生碰撞，進(jìn)行線性探查，由于element[6]為空單元，可以插入；68的地址為3，element[3]是空單元，直接插入；99的地址為8，與73的地址相沖突，線性探查后放入element[9]；27，41，51的地址都未被占用，可以直接存放；32的地址為6，element[6]已經(jīng)被5占用，線性探查后存入element[7]25的地址為12，與51發(fā)生沖突，線性探查后存入element[0]44散列表的運(yùn)算散列表示的字典定義：typedefstruct{DicElementelement[REGION_LEN];intm;/*m=REGION_LEN,為基本區(qū)域長度*/}HashDictionary;散列表的檢索算法散列表的插入算法45堆積線性探測容易出現(xiàn)不同的關(guān)鍵碼爭奪同一個散列地址問題，這種現(xiàn)象稱為“二次聚集[堆積]”。即不是同義詞的結(jié)點(diǎn)處在同一個探查序列中，增加了探查序列的長度;在上例中，h(32)=6，h(5)=5，32和5不是同義詞，但是在解決05與18的碰撞時(shí)，05已經(jīng)存入element[6]，使得在插入32時(shí)，32與05不沖突的兩個非同義詞之間發(fā)生了碰撞為了減少堆積的產(chǎn)生，可以改進(jìn)線性探查方法，使探查順序跳躍式地散列在表中。46存儲表示與碰撞的處理開地址法（探查法）線性探查法雙散列函數(shù)法拉鏈法47雙散列函數(shù)法雙散列函數(shù)法中選用兩個散列函數(shù)h1和h2h1以關(guān)鍵碼為自變量，產(chǎn)生一個0到m-1之間的數(shù)作為地址。h2以關(guān)鍵碼為自變量，產(chǎn)生一個1到m-1之間的并和m互素的數(shù)作為對地址的補(bǔ)償。例如，h1(key)=key%m，h2(key)=key%(m-2)+1。如果d=h1(key)發(fā)生碰撞，則再計(jì)算h2(key)，取(d+h2(key))%m,(d+2h2(key))%m,…直到找到未被占用的地址插入同義詞為止。48示例已知關(guān)鍵碼集合K={18，73，10，05，68，99，27，41，51，32，25}，用雙散列函數(shù)法解決碰撞m=13，h1、h2函數(shù)分別為：

h1(key)=key%13，

h2(key)=key%(m-2)+1=key%11+1計(jì)算地址d=h1(key)，若地址未被占用，則插入新結(jié)點(diǎn)；否則用h2函數(shù)計(jì)算地址補(bǔ)償，直到找到未被占用的地址。

h1(18)=5, h1(73)=8,h1(10)=10,h1(05)=5, h1(68)=3, h1(99)=8，h1(27)=1,h1(41)=2,h1(51)=12,h1(32)=6, h1(25)=1249示例-續(xù)05與18沖突，用h2函數(shù)對地址進(jìn)行補(bǔ)償，h2(05)=5%11+1=6，得到散列地址為(d+6)%m=(5+6)%13=11，是空地址單元可以直接插入同樣可以得到99的插入地址為9，25的地址為7。存放后的散列表為∶50開地址法特點(diǎn)邏輯刪除處理：用開地址法構(gòu)造散列表，刪除結(jié)點(diǎn)時(shí)，不能簡單地將要刪除的結(jié)點(diǎn)空間置為空，因?yàn)楦鞣N開地址法中，空地址單元是檢索失敗的依據(jù)，刪除一個結(jié)點(diǎn)會影響其它結(jié)點(diǎn)的檢索，因此只能在被刪除結(jié)點(diǎn)上做標(biāo)記，不能真正刪除。這樣，做了許多刪除后，形式上散列表是滿的，但實(shí)際上卻很空，浪費(fèi)了存貯空間。改進(jìn)的方法：在插入結(jié)點(diǎn)時(shí)利用做了標(biāo)記的地址空間。51存儲表示與碰撞的處理開地址法線性探查法雙散列函數(shù)法拉鏈法52拉鏈法設(shè)基本區(qū)域長度為m，碰撞發(fā)生時(shí)建立一個鏈表，若n個關(guān)鍵碼映象到基本區(qū)域的m個存貯單元上，則最多可以建立m個鏈表。例如：已知關(guān)鍵碼集合K={18，73，10，05，68，99，27，41，51，32，25}，用拉鏈法解決碰撞。設(shè)散列函數(shù)為h(key)=key%13，插入新結(jié)點(diǎn)時(shí)，將結(jié)點(diǎn)插入到鏈表中53

h(18)=5, h(73)=8,h(10)=10,h(05)=5,h(68)=3,h(99)=8,h(27)=1, h(41)=2,h(51)=12,h(32)=6,h(25)=12得到的散列表為∶散列表的存儲表示需要另外定義∧41∧6818

5∧327399∧51

12∧100地址關(guān)鍵