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

2023/9/22福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院1第9章符號(hào)表9.1實(shí)現(xiàn)符號(hào)表的簡(jiǎn)單方法

9.2用散列表實(shí)現(xiàn)符號(hào)表

9.3符號(hào)表的應(yīng)用吳英杰2023/9/22福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院2第9章符號(hào)表

學(xué)習(xí)要點(diǎn)：

理解抽象數(shù)據(jù)類型符號(hào)表的概念。

掌握數(shù)組實(shí)現(xiàn)符號(hào)表的方法。

理解開(kāi)散列和閉散列的概念。

掌握用開(kāi)散列表實(shí)現(xiàn)符號(hào)表的方法。

掌握除余法、數(shù)乘法、平方取中法、基數(shù)轉(zhuǎn)換法和隨機(jī)數(shù)法等散列函數(shù)構(gòu)造方法。

掌握采用線性重新散列技術(shù)的閉散列表實(shí)現(xiàn)符號(hào)表的方法。返回章目錄2023/9/22福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院39.1

實(shí)現(xiàn)符號(hào)表的簡(jiǎn)單方法9.1.0引言ADT符號(hào)表的概念以集合為基礎(chǔ)，并支持Member、Insert和Delete三種運(yùn)算的抽象數(shù)據(jù)類型叫做符號(hào)表。ADT符號(hào)表的應(yīng)用公司的客戶符號(hào)表一個(gè)地區(qū)的固定/移動(dòng)電話號(hào)碼符號(hào)表軟件開(kāi)發(fā)中的數(shù)據(jù)符號(hào)表網(wǎng)上的在線符號(hào)表互聯(lián)網(wǎng)/企業(yè)網(wǎng)/局域網(wǎng)網(wǎng)管中的IP地址符號(hào)表等等

2023/9/22福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院49.1實(shí)現(xiàn)符號(hào)表的簡(jiǎn)單方法9.1.2用固定數(shù)組實(shí)現(xiàn)符號(hào)表9.1.2.1數(shù)組實(shí)現(xiàn)符號(hào)表類Adictionary的定義typedefstructatab*Table;Typedefstructatab{intarraysize;intlast;setitem*data;}Atab;

2023/9/22福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院59.1實(shí)現(xiàn)符號(hào)表的簡(jiǎn)單方法9.1.2用固定數(shù)組實(shí)現(xiàn)符號(hào)表9.1.2.2優(yōu)缺點(diǎn)優(yōu)點(diǎn)：結(jié)構(gòu)簡(jiǎn)單，實(shí)現(xiàn)操作的邏輯簡(jiǎn)單。缺點(diǎn)：所表示的集合的大小受到數(shù)組大小的限制。三個(gè)基本操作在最壞情況下都需要O(n)。通常集合元素并不占滿整個(gè)數(shù)組，空間沒(méi)有得到充分利用。返回章目錄2023/9/22福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院69.2用散列表實(shí)現(xiàn)符號(hào)表9.2.1實(shí)現(xiàn)符號(hào)表的簡(jiǎn)單方法——開(kāi)散列基本設(shè)想：把符號(hào)表中的所有元素散列(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í)間。這里的問(wèn)題是如何散列即如何構(gòu)造散列(映射)函數(shù)去達(dá)到設(shè)想的期望？2023/9/22福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院7例一組關(guān)鍵字為（21，14，19，58，65，32，72）

H(K)=K%11216532∧19∧72∧1458∧∧

∧

∧∧∧∧∧0123456789102023/9/22福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院89.2用散列表實(shí)現(xiàn)符號(hào)表9.2.2用閉散列實(shí)現(xiàn)符號(hào)表9.2.2.1與開(kāi)散列的相同點(diǎn)和區(qū)別相同點(diǎn)：把符號(hào)表中的所有元素散列(hashing)即映射到一個(gè)桶數(shù)組(散列表)的桶中。區(qū)別：桶數(shù)組(散列表)的桶直接用來(lái)存放符號(hào)表元素，而且一個(gè)桶只存放一個(gè)元素。出現(xiàn)多個(gè)元素散列到同一個(gè)桶時(shí)(這叫沖突)，需要按照確定的規(guī)則在桶數(shù)組中進(jìn)行探測(cè)，找還有沒(méi)有存放元素的桶(這叫空桶)，然后將發(fā)生沖突的元素放入空桶，解決沖突，實(shí)現(xiàn)散列。

2023/9/22福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院9例一組關(guān)鍵字為（20，30，70，15，8，12，18，63，19

）

H(K)=K%111912

7015

183020863下標(biāo)：01234567891011用線性探測(cè)法處理沖突！2023/9/22福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院109.2.2.2散列方法需要解決的問(wèn)題：1、構(gòu)造好的散列函數(shù)（1）所選函數(shù)盡可能簡(jiǎn)單，以便提高轉(zhuǎn)換速度。（2）所選函數(shù)對(duì)關(guān)鍵字計(jì)算出的地址，應(yīng)在散列地址集中大致均勻分布，以減少空間浪費(fèi)。

2、制定解決沖突的方案。9.2用散列表實(shí)現(xiàn)符號(hào)表3、需要對(duì)ht[]的每一個(gè)桶的狀態(tài)加以標(biāo)記：

state[k]=0表示ht[k]桶存放著元素。

state[k]=1表示ht[k]桶一直是空桶。

state[k]=2表示ht[k]桶現(xiàn)在是空桶但曾經(jīng)存放過(guò)元素2023/9/22福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院119.2.2.3散列函數(shù)的構(gòu)造方法

1、直接定址法：取關(guān)鍵字的某個(gè)線性函數(shù)值作為散列地址?！^直觀的方法

H(key)=a*key+b;//a、b為常數(shù)

2、除留余數(shù)法：取關(guān)鍵字的某個(gè)不大于表長(zhǎng)m的數(shù)p除后所得的余數(shù)作為散列地址。——較簡(jiǎn)單、常用的方法

H(key)=key%p;//p<=m

3、平方取中法：取關(guān)鍵字平方后的中間幾位作為散列地址(若超出范圍時(shí)，可再取模)。9.2用散列表實(shí)現(xiàn)符號(hào)表2023/9/22福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院129.2.2.3散列函數(shù)的構(gòu)造方法

4、折疊法：將關(guān)鍵字分成幾個(gè)部分，再將這幾個(gè)部分結(jié)合(作某一運(yùn)算)起來(lái)的值作為散列地址?！Ｓ糜陉P(guān)鍵字的位數(shù)較多的情況

5、數(shù)值分析法：如果事先知道所有可能的關(guān)鍵字的取值時(shí)，可通過(guò)對(duì)這些關(guān)鍵字分析，發(fā)現(xiàn)其變化規(guī)律，構(gòu)造出相應(yīng)的函數(shù)。9.2用散列表實(shí)現(xiàn)符號(hào)表2023/9/22福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院139.2.2.4處理沖突的方法

1、線性探測(cè)法：當(dāng)由H(k)算出的位置不空時(shí)，依次用下面函數(shù)以找出一個(gè)新的空位置。

Hi(k)=(H(k)+di)modm,其中i=1,2,…k(k≤m-1)

其中：m為散列表長(zhǎng)度，di的取值常用如下形式：di=i，即di為增量序列，依次取值1，2，……，m-19.2用散列表實(shí)現(xiàn)符號(hào)表2023/9/22福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院14

例：已知散列表的地址區(qū)間為0～11，散列函數(shù)為H(k)=k%11,采用線性探測(cè)法處理沖突，試將以下關(guān)鍵字序列依次存儲(chǔ)到散列表中，構(gòu)造出該散列表，并求出在等概論情況下的平均查找長(zhǎng)度。

20，30，70，15，8，12，18，63，19H(20)=9,可直接存放到A[9]中(搜索時(shí)次數(shù)為1)；

……H(19)=8，因?yàn)橄聵?biāo)為8~11的元素均已被占用，故往后搜索并繞回到A[0]存放(搜索時(shí)次數(shù)為5)。9.2用散列表實(shí)現(xiàn)符號(hào)表9.2.2.4處理沖突的方法2023/9/22福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院151912

7015

183020863下標(biāo)：01234567891011搜索次數(shù)：511211134

在等概率情況下，該表成功的平均查找長(zhǎng)度如下：（1×5＋2×1＋3×1＋4×1＋5×1）/9＝19/99.2用散列表實(shí)現(xiàn)符號(hào)表9.2.2.4處理沖突的方法2023/9/22福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院169.2用散列表實(shí)現(xiàn)符號(hào)表9.2.2.4處理沖突的方法2、二次重新散列技術(shù)它選取的探查桶序列為：h(x),h1(x),h2(x),…,h2i(x),h2i+1(x),

其中，，。

3、隨機(jī)重新散列技術(shù)

它選取的探查桶序列為：

,i=1，2，…，B-1。其中，是1，2，…，B-1的一個(gè)隨機(jī)排列。

4、雙重散列技術(shù)

這種方法使用2個(gè)散列函數(shù)h和h’來(lái)產(chǎn)生探索序列：

其中

i=1，2，…，B-1。要求h’(x)的值和B互素。2023/9/22福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院179.2用散列表實(shí)現(xiàn)符號(hào)表9.2.3改進(jìn)Delete(x)的基本思想：動(dòng)機(jī)是希望騰出的空桶(記為ht[i])不僅僅可供新元素插入，而且能為提高還在桶數(shù)組中的元素(比如y=ht[j])的查找速度作出貢獻(xiàn)：減少查找y的探測(cè)次數(shù)。容易理解，如果不作任何改進(jìn)，查找y的探測(cè)次數(shù)會(huì)等于插入y時(shí)的探測(cè)次數(shù)。如果插入y時(shí)x已在桶ht[i]中且與x發(fā)生沖突而增加了插入的探測(cè)次數(shù)，那么，現(xiàn)在x不存在了，只要將x騰出的桶ht[i]讓y頂替，就可以使得將來(lái)查找y時(shí)減少探測(cè)次數(shù)。因此改進(jìn)Delete(x)的途徑是在當(dāng)前的桶數(shù)組中找能頂替x的y。如果找不到，就按Delete(x)的原版處理；如果找得到，在用y頂替x之后還可以引起連鎖反應(yīng)。2023/9/22福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院189.2用散列表實(shí)現(xiàn)符號(hào)表改進(jìn)Delete(x)的細(xì)節(jié)——找能頂替x的y

假設(shè)被刪除元素x位于桶單元ht[i]?，F(xiàn)考察一個(gè)非空單元ht[j]中的元素y，其散列函數(shù)值設(shè)為h=hf(y)，則按從h出發(fā)的線性探測(cè)，只要i比j離h近即可使得在頂替后找y的探測(cè)次數(shù)減少。①當(dāng)i<j時(shí)，若i<h

j，則不可用元素ht[j]頂替ht[i]；若h

i<j或i<j<h，則可用元素ht[j]頂替ht[i]。如下圖(a)。②當(dāng)j<i時(shí)，若j<h

I，則可用元素ht[j]頂替ht[i]，如下圖

(b)；否則不可。這里以線性探測(cè)為前題，以頂替后減少探測(cè)次數(shù)為目標(biāo)。2023/9/22福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院199.2用散列表實(shí)現(xiàn)符號(hào)表9.2.4