數(shù)據(jù)結(jié)構(gòu)參與命題課件第9章符號(hào)表

1、第9章 符號(hào)表實(shí)現(xiàn)符號(hào)表的簡單方法用散列表實(shí)現(xiàn)符號(hào)表開散列閉散列散列函數(shù)及其效率閉散列的重新散列技術(shù)應(yīng)用舉例12011/11/15第9章 符號(hào)表在算法設(shè)計(jì)中用到的集合，往往不做集合的并、交、差運(yùn)算，而常要判定某個(gè)元素是否在給定的集合中，并且要不斷地對(duì)這個(gè)集合進(jìn)行元素的和刪除操作。以集合為基礎(chǔ)，并支持SetMember、SetInsert和SetDelete三種運(yùn)算的抽象數(shù)據(jù)類型叫做符號(hào)表。ADT符號(hào)表的應(yīng)用公司的客戶字典一個(gè)地區(qū)的固定/移動(dòng)號(hào)碼字典開發(fā)中的數(shù)據(jù)字典網(wǎng)上的字典互聯(lián)網(wǎng)/企業(yè)網(wǎng)/局域網(wǎng)中的IP地址字典等等22011/11/159.1 實(shí)現(xiàn)符號(hào)表的簡單方法用固定數(shù)組用數(shù)組實(shí)現(xiàn)符號(hào)表的結(jié)

2、構(gòu)定義如下：typedef structypedef strucab *Table;abarraysize; last;SetItem*data;Atab;32011/11/15創(chuàng)建一個(gè)定長數(shù)組大小為size的空符號(hào)表Table TableInit(size)Table T=malloc(sizeof *T); T-arraysize=size;T-last=0;T-data=malloc(size*sizeof(SetItem); return T;42011/11/15符號(hào)表的成員查詢運(yùn)算TableMember(SetItem x,Table T)I;for(i=0;ilast;i+)if

3、(T-datai=x) return 1;return 0;52011/11/15符號(hào)表的元素運(yùn)算void TableInsert(SetItem x,Table T)if(! TableMember(x,T) & T-lastarraysize)T-da-last+=x;62011/11/15符號(hào)表的元素刪除運(yùn)算void TableDelete(SetItem x,Table T)i=0;if (T-last0)while(T-datai!=x & ilast) if(ilast & T-datai=x)T-datai=T-data-T-last;i+;72011/11/159.1 實(shí)現(xiàn)符號(hào)

4、表的簡單方法用固定數(shù)組優(yōu)點(diǎn)：結(jié)構(gòu)簡單，實(shí)現(xiàn)操作的邏輯簡單。缺點(diǎn)：所表示的集合的大小受到數(shù)組大小的限制。情況下都需要O(n)。三個(gè)基本操作在通常集合元素并不占滿整個(gè)數(shù)組，因此，空間沒有得到充分利用。82011/11/159.2 用散列表實(shí)現(xiàn)符號(hào)表實(shí)現(xiàn)符號(hào)表的另一個(gè)重要技巧是散列技術(shù)。用散列來實(shí)現(xiàn)符號(hào)表可以使符號(hào)表的每個(gè)運(yùn)算所需的平均時(shí)間是一個(gè)常數(shù)值，在正比于集合的大小。散列有兩種形式：情況下每個(gè)運(yùn)算所需的時(shí)間開散列：它將符號(hào)表元素放在一個(gè)潛無窮的空間里，能處理任意大小的集合。閉散列：它使用一個(gè)固定大小的空間，所能處理的集合大小過其空間大小。92011/11/15 9.2.1 開散列基本：把符號(hào)表

5、中的所有元素散列(hashing)，即到一個(gè)桶數(shù)組(散列表)的桶中。當(dāng)有多個(gè)不同元素被散列到同一個(gè)桶時(shí)，這些元素用鏈在一個(gè)表里。期望散列能均勻，使得當(dāng)桶數(shù)組的規(guī)模與符號(hào)表的規(guī)模同階時(shí)，桶數(shù)組的每一個(gè)桶中大致有常數(shù)個(gè)元素，從而對(duì)符號(hào)表的三個(gè)基本操作都只需要常數(shù)時(shí)間。是如何散列即如何構(gòu)造散列()函數(shù)去達(dá)這里到設(shè)想的期望？102011/11/15 9.2.1 開散列開散列的數(shù)據(jù)要素按照設(shè)想，開散列首先需要擁有一個(gè)桶數(shù)組，桶數(shù)組的規(guī)模與符號(hào)表的規(guī)模同階，桶數(shù)組中的每一個(gè)桶有一個(gè)指針各指向一個(gè)鏈表。其次需要擁有一個(gè)散列()函數(shù)，它把符號(hào)表中的元素分別散列(的鏈表中。，分散)到各桶所對(duì)應(yīng)112011/11

6、/15 9.2.1 開散列散列函數(shù)的例子假設(shè)符號(hào)表的元素是字符串x，桶數(shù)組的規(guī)模為101，那么，下面是散列函數(shù)的一個(gè)具體例子：hash1(char* x)len=strlen(x), hashval = 0;for(i=0;isize=nbuckets;H-hf=hashf;H-ht=malloc(H-size*sizeof(List); for(i=0;isize;i+)H-hti=ListInit()return H;142011/11/15開散列表的成員查詢函數(shù)HTMember(x,H)，根據(jù)元素x的散列函數(shù)值確定該元素的桶號(hào)，然后調(diào)用相應(yīng)的表定位函數(shù)返回查詢結(jié)果。HTMember(Se

7、tItem x,OpenHashTable H)i=(*H-hf)(x) % H-size;return (ListLocate(x,H-hti)0);152011/11/15運(yùn)算HTInsert(x,H)，根據(jù)元素x的該元素的桶號(hào)，然后在該桶的表首開散列表的元素散列函數(shù)值確定元素x。void HTInsert(SetItem x,OpenHashTable H)i;if (HTMember(x,H) Error(“Bad Input”); i=(*H-hf)(x) % H-size;ListInsert(0,x,H-hti);162011/11/15開散列表的元素刪除運(yùn)算HTDelete(x

8、,H)，根據(jù)元素x的散列函數(shù)值確定該元素的桶號(hào)，然后調(diào)用相應(yīng)的表元素刪除函數(shù)刪除元素x。void HTDelete(SetItem x,OpenHashTable H)i;i=(*H-hf)(x) % H-size;if (k=ListLocate(x,H-hti) ListDelete(k,H-hti);172011/11/15 9.2.2 閉散列與開散列的相同點(diǎn)和區(qū)別相同點(diǎn)：把符號(hào)表中的所有元素散列(hashing)即到一個(gè)桶數(shù)組(散列表)的桶中。區(qū)別：桶數(shù)組(散列表)的桶直接用來存放符號(hào)表元素，而且一個(gè)桶只存放一個(gè)元素。出現(xiàn)多個(gè)元素散列到同一個(gè)桶時(shí)(這叫)，需要按照確定的規(guī)則在桶數(shù)組中進(jìn)

9、行探測，找還沒有存放元素的桶(這叫空桶)，然后將發(fā)生沖突的后到元素放入空桶，解決，實(shí)現(xiàn)散列。182011/11/15 9.2.2 閉散列閉散列(1) 需要一個(gè)探測函數(shù)c(i)，i=0,1,2,size-1： c(0)=0,而且對(duì)于任意的0jsize-1，(j+c(0)% size, (j+c(1)% size, ,(j+c(size-1)% size是0,1,2,size-1 的重排,保證不會(huì)漏測。(2) 需要對(duì)ht 的每一個(gè)桶的狀態(tài)加以標(biāo)記：sssek=0表示htk桶存放著元素。ek=1表示htk桶一直是空桶。ek=2表示htk桶現(xiàn)在是空桶但曾經(jīng)存放過元素192011/11/15用閉散列實(shí)現(xiàn)

10、的符號(hào)表結(jié)構(gòu)HashTable的定義typedef structypedef strucshtable *HashTable;shtablesize;/桶數(shù)組大小(*hf)(SetItem x);/散列函數(shù)SetItem *ht;/桶數(shù)組*se;/占用狀態(tài)數(shù)組Hashtable;202011/11/15初始化桶數(shù)組ht和s創(chuàng)建一個(gè)空的散列表HashTable HTInit(i;e，將每個(gè)桶都設(shè)置為空桶。divisor,(*hashf)(SetItem x)HashTable H=malloc(sizeof *H); H-size=divisor;H-hf = hashf;H-ht=malloc

11、(H-size*sizeof(SetItem);H-se=malloc(H-size*sizeof();for (i=0;isize;i+)H-sreturn H;ei=1;212011/11/15FindMatch(SetItem x,HashTable H)在散列表H的桶數(shù)組中查找元素x，并返回它在桶數(shù)組中的位置。I,j,k;j=(*H-hf)(x);for (i=0;isize;i+) k=(j+HashProb(i)%H-size;if (H-s if(!H-sek=1) break;ek & H-htk=x) return k;return H-size;HashProb(i)ret

12、urn i;222011/11/15返回散列表H的桶數(shù)組中可位置k。元素x的未占用桶單元Unoccupied(SetItem x,HashTable H)I,j,k;j=(*H-hf)(x);for (i=0;isize;i+) k=(j+HashProb(i) % H-size;if (H-sek)return k;return H-size;232011/11/15閉散列表通過調(diào)用函數(shù)FindMatch實(shí)現(xiàn)成員查詢HTMember(SetItem x,HashTable H)i=FindMatch(x,H);if (isize & H-hti=x) return 1; return 0;2

13、42011/11/15閉散列表的元素運(yùn)算HTInsert(SetItem x,HashTable H)i; if(HTMember(x,H) i=Unoccupied(x,H);if(isize)Error(“Bad Input”);H-sei=0;H-hti=x;else Error(“table full”);252011/11/15閉散列表的元素刪除運(yùn)算HTDelete(SetItem x,HashTable H)i=FindMatch(x,H);if (isize & H-hti=x)H-sei=2;262011/11/15上述刪除算法HTDelete的缺點(diǎn)：在執(zhí)行了大量元素刪除運(yùn)算后

14、，大量的桶的狀態(tài)標(biāo)記為 2，即大量的桶的狀態(tài)標(biāo)記既非 1 也非 0，使得運(yùn)算 FindMatch 中的循環(huán)次數(shù)大大增加，從而導(dǎo)致運(yùn)算 FindMatch的速度大大減慢。因此人們提出HTDelete的一種改進(jìn)版本HTDelete1。272011/11/15改進(jìn)HTDelete的基本：是希望騰出的空桶(記為hti)不僅僅可供新元素，而且能為提高還在桶數(shù)組中的元素(比如y= htj)的查找速度作出貢獻(xiàn)：減少查找y的探測次數(shù)。容易理解，如果不作任何改進(jìn)，查找y的探測次數(shù)會(huì)等于y時(shí)的探測次數(shù)。如果y時(shí)x已在桶hti中且與x發(fā)的探測次數(shù)，那么，現(xiàn)在x不存在了，生而增加了只要將x騰出的桶hti讓y頂替，就可

15、以使得將來查找y時(shí)減少探測次數(shù)。因此，改進(jìn)HTDelete的途徑是在當(dāng)前的桶數(shù)組中找能頂替x的y。如果找不到，就按HTDelete的原版處理；如果找得到，在用y頂替x之后還可以引起。282011/11/15改進(jìn)HTDelete的細(xì)節(jié)找能頂替x的y假設(shè)被刪除元素x位于桶單元hti?，F(xiàn)一個(gè)非空單元htj中的元素y，其散列函數(shù)值設(shè)為h=hf(y)，則按從h出發(fā)的線性探測，只要i比j離h近即可使得在頂替后找y的探測次數(shù)減少。當(dāng)ij時(shí)，若ihj，則不可用元素htj頂替hti；若hij或ijh，則可用元素htj頂替hti。如下圖(a)。當(dāng)ji時(shí)，若jhI，則可用元素htj頂替hti，如下圖 (b)；否則不

16、可。這里以線性探測為前題，以頂替后減少探測次數(shù)為目標(biāo)。292011/11/15Void HTDelete1SetItem x,HashTable H)改進(jìn)HTDelete的函數(shù)HTDelete1i=FindMatch(x);if (isize)for (;) / &H-hti=x可以去掉/找hti的頂替元素H-sj;ei=2;/先按無頂替元素處理/從(i+1)%size開始線性搜索可頂替元素for (j=(i+1)%H-size; !sej; j=(j+1)%H-size)h=(*H-hf) (H-htj);if (h=i&ij)|(ij&jh)|(jh&hsej)break;/跳出外for循

17、環(huán)H- hti=htj; H-sei=sej;/做頂替工作i=j;/為循環(huán)找htj的頂替元素302011/11/15 9.2.3 散列函數(shù)及其效率若能選擇一個(gè)好的散列函數(shù)，將集合中的n個(gè)元素均勻地散列到B個(gè)桶中，那么每個(gè)桶中平均有n/B個(gè)元素。使得在開散列表中，HTInsert，HTDelete和 HTMember運(yùn)算都只要O(n/B)的平均時(shí)間。當(dāng)n/B為一常數(shù)時(shí)，每一個(gè)符號(hào)表運(yùn)算都可在常數(shù)時(shí)間內(nèi)完成。因此：對(duì)于開散列表，關(guān)鍵在于選擇一個(gè)好的散列函數(shù)。312011/11/15 9.2.3 散列函數(shù)及其效率幾種計(jì)算簡單且效果較好的散列函數(shù)構(gòu)造方法：(1)除余法：h(k)=k%m(2)數(shù)乘法：h(k)= Bkaka(3)平方取中法：h(k)= k 2 / c %B(4)基數(shù)轉(zhuǎn)換法(5)隨機(jī)數(shù)法 ：h(k)=random(k)322011/11/15 9.2.4 閉散列的重新散列技術(shù)(1) 二次重新散列技術(shù)它選取的探查桶序列為：h(x),h1(x) ,h2(x) ,h2i(x) ,h2i+1(x) ,其中，h (x) h(x) i2 %Bh(x) h(x) i2 %B2i1