《數(shù)據(jù)結(jié)構(gòu)與算法》第10章.ppt

1、南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2006年9月,數(shù)據(jù)結(jié)構(gòu)與算法,Data Structures in C,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2006年9月,第二部分 數(shù)據(jù)結(jié)構(gòu),南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2006年9月,第10章 跳表和散列表,10.1 字典 10.2 跳表 10.3 散列表,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2006年9月,10.1 字典,10.1 字典 10.2 跳表 10.3 散列表,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2006年9月,字典（dictionary）是記錄的集合。字典的每個(gè)詞條是一個(gè)記錄，有關(guān)單詞是該記錄的關(guān)鍵字（key），詞條中還包含其它信息，不同記錄的關(guān)鍵字值各不相同。對(duì)字典的存取通過關(guān)鍵字進(jìn)行。

2、可以認(rèn)為字典是一種特殊的集合。字典上的基本運(yùn)算與ADT 8-1的集合抽象數(shù)據(jù)類型所定義的相同，主要包括搜索、插入和刪除。 可以擴(kuò)充字典的定義使之允許包括重復(fù)記錄。有重復(fù)記錄的字典(dictionary with duplicates)，允許字典中有多個(gè)相同關(guān)鍵字值的記錄，在實(shí)現(xiàn)搜索、插入和刪除操作時(shí)需要一個(gè)規(guī)則來消除歧義。也就是說，如果要搜索（或刪除）關(guān)鍵字值為k的記錄，在多個(gè)具有相同關(guān)鍵字值的記錄中究竟返回哪一個(gè),南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2006年9月,10.3 散 列 表,10.1 字典 10.2 跳表 10.3 散列表,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2006年9月,10.3.1 散列技術(shù),散列

3、表是表示集合和字典的另一種有效方法。它提供了一種完全不同的存儲(chǔ)和搜索方式：通過將關(guān)鍵字值映射到表中某個(gè)位置上來存儲(chǔ)元素，而后根據(jù)關(guān)鍵字值直接訪問。 Loc(key)=h(key) 其中，Loc(key)表示關(guān)鍵字值為key的元素的存儲(chǔ)位置。 （1）這個(gè)把關(guān)鍵字值映射到位置的函數(shù)h稱為散列函數(shù)； （2）這樣建立的表稱為散列表,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2006年9月,沖突和同義詞 建立全國省、市、自治區(qū)的人口統(tǒng)計(jì)簡表。 h(Hebei)=h(Henan)=h(Hubei)=h(Hunan)=8 h(Shandong)= h(Shanxi)= h(Shanghai)= h(Sichuan)=19 所

4、謂沖突，是指對(duì)于關(guān)鍵字集合中的兩個(gè)關(guān)鍵字值Ki和Kj，當(dāng)KiKj時(shí)，有h(Ki)=h(Kj)，h是散列函數(shù)。具有相同散列函數(shù)值的關(guān)鍵字值，對(duì)該散列函數(shù)而言稱為同義詞,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2006年9月,沖突是不可避免的。 例一：關(guān)鍵字值集合有31個(gè)元素，如果我們選擇一個(gè)有40個(gè)元素的記錄數(shù)組的散列表，也就是說散列地址的范圍從0到39。 C4031.31！=40！/9！1042 40314*1049,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2006年9月,10.3.2 散列函數(shù),構(gòu)造一個(gè)散列函數(shù)的方法很多，但究竟什么是“好”的散列函數(shù)？一個(gè)理想的散列函數(shù)h應(yīng)當(dāng)滿足下列條件：（1）能快速計(jì)算；（2）具有均勻性

5、。 假定散列表長度為M，那么，散列函數(shù)h將關(guān)鍵字值轉(zhuǎn)換成0,M-1中的整數(shù)，即0h(key)M。一個(gè)均勻的散列函數(shù)應(yīng)當(dāng)是：如果key是從關(guān)鍵字值集合中隨機(jī)選取的一個(gè)值，則h(key)以同等概率取區(qū)間0，M-1中的每一個(gè)值,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2006年9月,目前比較通用的散列函數(shù)有下列幾種： 除留余數(shù)法（Division） 除留余數(shù)法的散列函數(shù)的形式如下： h(key)=key mod M 其中，key是關(guān)鍵字，M是散列表的大小。 M的選擇十分重要，如果M選擇不當(dāng)，在某些選擇關(guān)鍵字值的方式下，會(huì)造成嚴(yán)重沖突。例如，若M=2k，則h(key)=key mod M 的值僅依賴于最后k個(gè)比特。如

6、果key是十進(jìn)制數(shù)，則M應(yīng)避免取10的冪次。多數(shù)情況下，選擇一個(gè)不超過M的素?cái)?shù)P，令散列函數(shù)為h(key)=key mod P，會(huì)收到好的效果,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2006年9月,平方取中法 設(shè)關(guān)鍵字用內(nèi)部碼表示，w=18，k=9。內(nèi)碼采用八進(jìn)制表示。 關(guān)鍵字值內(nèi)碼 內(nèi)碼的平方散列地址 0100 0010000 010 1100 1210000 210 1200 1440000 440,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2006年9月,折疊法 key=12320324111220 若散列地址取3位，則key被劃分為5段： 123 203 241 112 20 a)移位法 b)分界法,南京郵電大學(xué)計(jì)算

7、機(jī)學(xué)院 2006年9月,數(shù)字分析法,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2006年9月,10.3.3 拉鏈法,解決沖突也稱為“溢出”處理技術(shù)。有兩種常用的解決沖突的方法：拉鏈的方法和開地址法。拉鏈的方法也稱開散列法，而開地址法又稱閉散列法。 采用拉鏈的方法建立散列表，在極端情況下，散列表中全部為同義詞，所以，最壞情況下，為了搜索一個(gè)關(guān)鍵字值，需檢查全部n個(gè)元素。一般情況下有n個(gè)元素的散列表的鏈表的平均長度為n/M,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2006年9月,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2006年9月,10.3.4 開地址法,地址h(key)被稱為基位置 探查表中空閑位置的探查序列形如： h(key),(h(key

8、)+p(1)mod M, (h(key)+p(i)mod M, 根據(jù)生成探查序列的規(guī)則不同，可以有線性探查法、偽隨機(jī)探查法、二次探查法和雙散列法,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2006年9月,10.3.5 線性探查法,線性探查法是一種最簡單的開地址法。它使用下列循環(huán)探查序列： h(key),h(key)+1,M-1,0,h(key)-1 從基位置h(key)開始，探查該位置是否被占用，即是否為空位置，如果被占用，則繼續(xù)檢查位置h(key）+1，若該位置也已占用，再檢查由探查序列規(guī)定的下一個(gè)位置，。 可以將線性探查法的探查序列記為： hi=(h(key)+i) mod M 對(duì)i=0,1,2,M-1,南

9、京郵電大學(xué)計(jì)算機(jī)學(xué)院 2006年9月,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2006年9月,程序107】 散列表類 template class HashTable:public DynamicSet public: HashTable(int divisor=11); HashTable()deleteht;delete empty; ResultCode Search(T,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2006年9月,private: ResultCode Find(T 后置條件： 若散列表中存在與x的關(guān)鍵字值相同的元素，則將其值賦給x，pos指示該位置，函數(shù)返回Success；否則函數(shù)返回NotPresen

10、t,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2006年9月,template HashTable:HashTable(int divitor) M=divitor; ht=new TM; empty=new boolM; for (int i=0;iM;i+) emptyi=true; for (i=0;iM;i+) hti=NeverUsed;,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2006年9月,程序108】線性探查散列表的搜索 template ResultCode HashTable:Find(T /基地址,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2006年9月,do if(emptypos) return NotPresent;

11、 if (htpos=x) x=htpos; return Success; pos=(pos+1) % M; while (pos!=i); return NotPresent;,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2006年9月,template ResultCode HashTable: Search(T,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2006年9月,程序109】線性探查散列表的插入 template ResultCode HashTable: Insert(T,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2006年9月,do if (htpos=x) x=htpos;return Duplicate; if (htpos=

12、NeverUsed) htpos=x;emptypos=false; return Success; pos=(pos+1) % M; while(pos!=i); return Overflow;,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2006年9月,程序1010】線性探查散列表的刪除 template ResultCode HashTable: Remove(T,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2006年9月,10.3.6 其它開地址法,基本聚集：許多元素在散列表中連成一片， 理想的探查序列應(yīng)當(dāng)是散列表位置的一個(gè)隨機(jī)排列。以后搜索關(guān)鍵字時(shí)，須再生同樣的探查序列,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2006年9月,偽隨機(jī)探查

13、法 探查序列： 一個(gè)簡單的偽隨機(jī)發(fā)生器，其計(jì)算公式如下： y0h(key) yi+1(yi+p) mod M (i=0,1,2,) 式中，y0為偽隨機(jī)數(shù)發(fā)生器的初值，M為散列表的長度，p為與M接近的素?cái)?shù),南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2006年9月,二次探查法 探查序列： h(key),h1(key),h2(key),h2i-1(key),h2i(key), h2i-1(key)=(h(key)+i2)mod M，i=1,2,3,(M-1)/2 h2i(key)=(h(key)-i2)mod M，i=1,2,3,(M-1)/2 式中，M是表的大小，它是一個(gè)值為4k+3的素?cái)?shù)，k是整數(shù)，如503,1019等,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2006年9月,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2