第6章 集合及字典

1、第六章 集合與字典 從邏輯結(jié)構(gòu)上看，集合和字典都是最簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)，它們的元素之間沒有任何確定的依賴關(guān)系。字典是關(guān)聯(lián)的集合。作為抽象數(shù)據(jù)類型，集合和字典之間的主要區(qū)別，在于它們的操作。集合主要考慮集合之間的并、交和差操作；字典主要關(guān)心其元素的檢索、插入和刪除。 目錄n6.1 集合及其抽象數(shù)據(jù)類型集合及其抽象數(shù)據(jù)類型n 6.1.1基本概念基本概念n 6.1.2主要運(yùn)算主要運(yùn)算n 6.1.3抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型n6.2 集合的實(shí)現(xiàn)集合的實(shí)現(xiàn)n 6.2.1集合的位向量表示集合的位向量表示n 6.2.2集合的單鏈表表示集合的單鏈表表示n6.3 字典及其抽象數(shù)據(jù)類型字典及其抽象數(shù)據(jù)類型n 6.3.1

2、基本概念基本概念n 6.3.2抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型n6.4 字典的順序表示字典的順序表示n 6.4.1存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)n 6.4.2算法的實(shí)現(xiàn)算法的實(shí)現(xiàn)n 6.4.3有序順序表有序順序表n 與二分法檢索與二分法檢索n6.5 字典的散列表示字典的散列表示n 6.5.1基本概念基本概念n 6.5.2散列函數(shù)散列函數(shù)n 6.5.3碰撞的處理碰撞的處理n 6.5.4散列文件散列文件6.1 集合及其抽象數(shù)據(jù)類型6.1.1 基本概念 集合是數(shù)學(xué)中最基本的概念，也是一種基本數(shù)據(jù)結(jié)構(gòu)。在數(shù)學(xué)中，集合集合是一些互不相同元素的無序匯集。這些元素稱為該集合的成員成員。集合中的成員可以是一個(gè)原子（不可再分解）；也

3、可以是一個(gè)結(jié)構(gòu)，甚至又是一個(gè)集合。集合中的各個(gè)元素應(yīng)該是互不相同的。 AxAx ,列舉法: 定義一個(gè)有窮集，可以將成員放在一對(duì)花括號(hào)中，成員之間用逗號(hào)隔開。 例如，2，謂詞描述法:集合的大小大小: 集合中所包含的元素的個(gè)數(shù)個(gè)數(shù)。 空集 子集 超集 數(shù)據(jù)結(jié)構(gòu)中討論的集合，一般有以下限制限制：1）數(shù)據(jù)結(jié)構(gòu)討論的集合總限制為有窮集；2）假定集合中所有元素屬同一類型；并且假設(shè)元素之間存在一個(gè)小于關(guān)系小于關(guān)系“”，也稱為有序集有序集。 Ix Z xx | ( )06.1.2 主要運(yùn)算n集合也可以定義測(cè)試一個(gè)元素是否存在于集合中、增加一個(gè)元素、刪除一個(gè)元素等運(yùn)算，但集合更加關(guān)心下面的一些運(yùn)算。n求并集并集

4、：n求交集交集：n求差集差集：n子集子集： A是B的子集n如果集合A是B的子集，反過來也稱集合B是A的超集超集。n相等相等：n例如例如：若，則有，。另外，不等于，同時(shí)和相互都不是子集關(guān)系。 |BxAxxBA|BxAxxBA|BxAxxBA)(BxAxxA BAB BA 上面集合間的運(yùn)算，都可以通過增加元素、刪除元素和成員測(cè)試等運(yùn)算來實(shí)現(xiàn)。例如：n已知集合A和B，求它們的并集，只要以集合A（或B）為基礎(chǔ)，把集合B（或A）的元素逐個(gè)插入。n如果要求兩個(gè)集合的交集，只要從A（或B）出發(fā)，檢查各元素是否在B（或A）中出現(xiàn)，把那些也在另一個(gè)集合里出現(xiàn)的元素插入（初態(tài)為空集）的集合中即可。n求A與B的差集

5、AB時(shí)，只要以A為基礎(chǔ)，對(duì)每個(gè)B中的元素做刪除運(yùn)算即可。6.1.3 抽象數(shù)據(jù)類型 ADT Set isoperationsSet createEmptySet ( void )創(chuàng)建一個(gè)空集合。int member（Set ，DataType ）當(dāng)時(shí)返回真值，否則取假值。int insert（Set ，DataType ）使作為的一個(gè)成員,如果本來就是的成員，則不變。int delete（Set ，DataType ）將從中刪除，如果本來就不在中，則不改變。int union（Set ，Set ，Set ）求集合和的并集，結(jié)果在集合中。int intersection （Set ，Set ，Se

6、t ）求集合和的交集，結(jié)果在集合中。int difference（Set ，Set ，Set ）求集合和的差集，結(jié)果在集合中。int subset（Set ，Set ）當(dāng)且僅當(dāng)是的子集時(shí)，函數(shù)值才為真。end ADT Set6.2 集合的實(shí)現(xiàn) n位向量表示 n單鏈表表示 6.2.1 位向量表示 位向量位向量是一種每個(gè)元素都是二進(jìn)制位（即0/1值）的數(shù)組。當(dāng)表示的集合存在某個(gè)不太大的公共超集時(shí)，采用位向量的方式來表示這種集合往往十分有效。 假設(shè)需要表示的集合的公共超集中，共有個(gè)不同的元素，為敘述的方便，不妨假設(shè)這些元素就是整數(shù)0，-1等。每個(gè)集合可以采用一個(gè)有位的位向量來表示。若整數(shù)是這個(gè)集合的

7、一個(gè)元素，則位向量中對(duì)應(yīng)的位為（真），否則為0（假）。 存儲(chǔ)結(jié)構(gòu)由于在C語言中無法直接定義位數(shù)組，要定義位向量，需要借助其它方式。一種比較自然的方式，是用長(zhǎng)度為n/8的字符數(shù)組表示長(zhǎng)度為n的字位數(shù)組。一個(gè)字符用8位二進(jìn)制編碼，它實(shí)際上包含了8個(gè)二進(jìn)制位。 位向量表示集合的存儲(chǔ)結(jié)構(gòu)：typedef struct int size;/*字符數(shù)組的長(zhǎng)度*/char * array; /*位向量空間。每一數(shù)組元素保存8位。*/ BitSet; 下圖給出了一個(gè)公共超集是從0到9的整數(shù)集合，采用位向量表示的存儲(chǔ)結(jié)構(gòu)示意圖。從圖中可以看出每個(gè)整數(shù)所對(duì)應(yīng)的二進(jìn)制位的位置。當(dāng)集合S=1,3,5,7,9時(shí),它的實(shí)

8、際存儲(chǔ)狀態(tài)如圖（b）所示(注意其中元素的排列方法)。 用位向量表示集合時(shí)，所占空間的大小與公共超集的大小成正比，而與要表示的集合的大小無關(guān)。 array size 2 （a）位向量表示的存儲(chǔ)結(jié)構(gòu)示意圖 0 7 6 5 4 3 2 1 8 9 array size 2 （b）集合 S=1,3,5,7,9的實(shí)際存儲(chǔ)狀態(tài) 0 1 0 1 0 1 0 1 0 1 算法實(shí)現(xiàn)以位向量表示集合，只有兩個(gè)集合都是某個(gè)公共集合的子集時(shí)，它們互相運(yùn)算才是有效的。由于在位向量定義里并沒有關(guān)于集合元素的實(shí)際信息，只能要求參與運(yùn)算的兩個(gè)位向量長(zhǎng)度相同。 位運(yùn)算n假設(shè)x和y都是8位的字符，其值分別是：X= 0101011

9、1Y= 11011010。對(duì)x和y做各種字位運(yùn)算，得到的結(jié)果如下：nx 10101000nx & y 01010010nx y 10001101nx | y 11011111nx 5 00000110n空集合的創(chuàng)建 與空順序表的的創(chuàng)建類似，不同之處在于這里省略了每個(gè)集合中實(shí)際元素個(gè)數(shù)的變量: BitSet * createEmptySet (int n) n將整數(shù)index的元素插入集合 將值為index的元素插入集合S的過程，通過將位向量中下標(biāo)為index的位置為1來完成： int insert (BitSet * s, int index) n將整數(shù)index的元素從集合中刪除 通過將位向

10、量中下標(biāo)為index的位置為0來完成： int delete(BitSet * s, int index) n判斷整數(shù)index的元素是否屬于集合 通過判斷位向量中下標(biāo)為index的位是否為1來完成： int member(BitSet * s, int index) n集合與集合的并利用按位的“或”運(yùn)算實(shí)現(xiàn): int union (BitSet * s0, BitSet * s1, BitSet * s2) n集合與集合的交 這個(gè)運(yùn)算很容易通過位“與”操作實(shí)現(xiàn)。 int intersection(BitSet * s0, BitSet * s1, BitSet * s2) n集合與集合的差

11、將第一個(gè)集合與第二個(gè)集合的逆做與運(yùn)算，就可以達(dá)到這個(gè)目的。 int difference(BitSet * s0, BitSet * s1, BitSet * s2) 6.2.2 單鏈表表示 鏈接表示方式下，在鏈表中存放的是集合中元素的實(shí)際數(shù)值，而不是元素是否屬于集合的標(biāo)記。 存儲(chǔ)結(jié)構(gòu)n鏈表中的每個(gè)結(jié)點(diǎn)表示集合中的一個(gè)元素，具體方式與第二章單鏈表的結(jié)點(diǎn)struct Node類似。n不同之處在于：線性表的單鏈表中，link字段表示線性表元素之間的邏輯后繼關(guān)系，而在這里僅僅是把屬于同一集合的所有元素鏈接成一個(gè)整體。n因?yàn)槲覀冇懻摰氖怯行蚣?，如果將集合中的所有元素按“”關(guān)系排序構(gòu)造有序鏈表，給集合的

12、某些運(yùn)算會(huì)帶來方便。 struct Node;typedef struct Node *PNode;struct Node DataType info; PNode link;typedef struct Node *LinkSet; 集合0，1，2，n-1采用帶表頭結(jié)點(diǎn)的有序鏈表表示時(shí)，如圖所示：n求單鏈表表示集合的交集 int intersectionLink (LinkSet s0,LinkSet s1,LinkSet s2）在有序鏈表表示的集合中，在在有序鏈表表示的集合中，在s1中找到第一個(gè)與中找到第一個(gè)與s0中中相同元素后，其它共同元素不需要從頭開始比較，只相同元素后，其它共同元素不

13、需要從頭開始比較，只要從剛才比較成功所結(jié)束的位置繼續(xù)向后檢索。要從剛才比較成功所結(jié)束的位置繼續(xù)向后檢索。因此，只要用兩個(gè)指針，沿因此，只要用兩個(gè)指針，沿s0和和s1從頭至尾掃描一遍從頭至尾掃描一遍即可完成。當(dāng)這兩個(gè)表的長(zhǎng)度為即可完成。當(dāng)這兩個(gè)表的長(zhǎng)度為和和時(shí)，算法的時(shí)，算法的時(shí)間總花費(fèi)最多為（時(shí)間總花費(fèi)最多為（）。）。 程序?qū)崿F(xiàn) 算法實(shí)現(xiàn)算法實(shí)現(xiàn)n集合的賦值 int assignLink (LinkSet s0,LinkSet s1) 賦值運(yùn)算將集合s0拷貝成集合s1，注意這一運(yùn)算不能簡(jiǎn)單地將s0的表頭結(jié)點(diǎn)置成s1的表頭結(jié)點(diǎn)，因?yàn)槿暨@樣處理，則對(duì)s1的改變將會(huì)帶來s0的改變。 程序?qū)崿F(xiàn)n插入運(yùn)

14、算 int insertLink (LinkSet s0,DataType x) 插入運(yùn)算首先要找到適當(dāng)?shù)牟迦胛恢?，它有兩個(gè)參數(shù)：一個(gè)是被插入元素的信息x；另一個(gè)則是被插入的集合s0。 程序?qū)崿F(xiàn) 6.3 字典及其抽象數(shù)據(jù)類型 6.3.1基本概念字典字典是一種集合，其中每個(gè)元素由兩部分組成，分別稱為關(guān)鍵碼關(guān)鍵碼和屬性屬性(或稱為值值)。這種包含關(guān)鍵碼和屬性的二元組稱作關(guān)聯(lián)關(guān)聯(lián)(Association)。抽象地看，一個(gè)關(guān)聯(lián)是一個(gè)有序?qū)?，它可以看成是由關(guān)鍵碼值k到屬性(值)v的一個(gè)對(duì)應(yīng)。字典就是由關(guān)鍵碼集合到值集合的二元關(guān)系。字典中的元素之間能夠根據(jù)其關(guān)鍵碼進(jìn)行比較大小，對(duì)字典元素的插入、刪除和檢索

15、等操作一般也以關(guān)鍵碼為依據(jù)進(jìn)行。 Dk vkKvV ,|在實(shí)踐中使用較多的字典里所有的關(guān)鍵碼互不相同，這種關(guān)鍵碼具有唯一性的字典，在數(shù)學(xué)中稱為映射(mapping)，數(shù)據(jù)結(jié)構(gòu)里講的就是這種字典。 字典關(guān)心的最主要的運(yùn)算是檢索檢索。衡量一個(gè)字典檢索算法效率的主要標(biāo)準(zhǔn)是檢索過程中對(duì)關(guān)鍵碼的平均比較次數(shù)：以及算法的空間開銷、算法是否易于理解等因素。n1iiicpASL6.3.2 抽象數(shù)據(jù)類型假設(shè)用假設(shè)用Dictionary表示抽象數(shù)據(jù)類型字典，表示抽象數(shù)據(jù)類型字典，用用DicElement表示字典元素類型，表示字典元素類型，用用KeyType 來表示元素中關(guān)鍵碼的類型，來表示元素中關(guān)鍵碼的類型，用用

16、Position表示字典中元素的位置。表示字典中元素的位置。 ADT Dictionary isoperationsDictionary createEmptyDictionary ( void ) 創(chuàng)建一個(gè)空字典。int search(Dictionary dic, KeyType key, Position p) 在字典dic中檢索關(guān)鍵碼為key的關(guān)聯(lián)的位置p。int insert(Dictionary dic, DicElement ele) 在字典dic中插入關(guān)聯(lián)ele。int delete(Dictionary dic, KeyType key) 在字典dic中刪除關(guān)鍵碼為key的關(guān)

17、聯(lián)。end ADT Dictionary 6.4 字典的順序表示 6.4.1 存儲(chǔ)結(jié)構(gòu)從邏輯結(jié)構(gòu)出發(fā)，字典中的元素是無序的，但為了實(shí)現(xiàn)的方便，可以把字典中的元素按關(guān)鍵碼的大小組織成一個(gè)順序表。 typedef intKeyType;typedef intDataType;typedef struct KeyType key;/* 字典元素的關(guān)鍵碼字段字典元素的關(guān)鍵碼字段*/DataType value;/* 字典元素的屬性字段字典元素的屬性字段*/ DicElement; typedef struct int MAXNUM ; /*字典中元素的個(gè)數(shù)上界字典中元素的個(gè)數(shù)上界*/ int n;/*

18、為字典中實(shí)際元素的個(gè)數(shù)為字典中實(shí)際元素的個(gè)數(shù) */ DicElement *element.; /*存放字典中的元素存放字典中的元素*/ SeqDictionary; 6.4.2 算法的實(shí)現(xiàn)檢索的基本思想是檢索的基本思想是 從字典的一端開始順序掃描，將從字典的一端開始順序掃描，將字典中元素的關(guān)鍵碼和給定值比較，如果相等，則檢字典中元素的關(guān)鍵碼和給定值比較，如果相等，則檢索成功；當(dāng)掃描結(jié)束時(shí)，還未找到關(guān)鍵碼等于給定值索成功；當(dāng)掃描結(jié)束時(shí)，還未找到關(guān)鍵碼等于給定值的元素，則檢索失敗。這稱為順序檢索算法。的元素，則檢索失敗。這稱為順序檢索算法。程序?qū)崿F(xiàn)： int seqSearch(SeqDicti

19、onary * pdic, KeyType key, int * position) 在不考慮檢索失敗的情況下，順序檢索的平均檢索長(zhǎng)度在不考慮檢索失敗的情況下，順序檢索的平均檢索長(zhǎng)度為為:ASL=1P1+2P2+nPn 假設(shè)每個(gè)元素的檢索概率相等，即假設(shè)每個(gè)元素的檢索概率相等，即Pi=1/n，則平均檢索長(zhǎng)度，則平均檢索長(zhǎng)度為為 ASL=（1+n）/2。成功檢索的平均比較次數(shù)約為字典長(zhǎng)度的一半。若字典中不存成功檢索的平均比較次數(shù)約為字典長(zhǎng)度的一半。若字典中不存在關(guān)鍵碼為在關(guān)鍵碼為key的元素，則需進(jìn)行的元素，則需進(jìn)行n次比較。檢索時(shí)間為次比較。檢索時(shí)間為O(n)。算法代價(jià)算法代價(jià)順序檢索的優(yōu)點(diǎn)是

20、算法簡(jiǎn)單且適應(yīng)面廣。無論字典中元素是順序檢索的優(yōu)點(diǎn)是算法簡(jiǎn)單且適應(yīng)面廣。無論字典中元素是否有序均可使用。缺點(diǎn)是平均檢索長(zhǎng)度較大，特別是當(dāng)否有序均可使用。缺點(diǎn)是平均檢索長(zhǎng)度較大，特別是當(dāng)n很很大時(shí)，檢索效率較低。大時(shí)，檢索效率較低。一般情況下，字典中各元素的檢索概率不相等。一般情況下，字典中各元素的檢索概率不相等。則當(dāng)則當(dāng)P1P2Pn時(shí)，平均檢索長(zhǎng)度最小。時(shí)，平均檢索長(zhǎng)度最小。因此，如果已知各元素的檢索概率，則應(yīng)將字典中元素按檢因此，如果已知各元素的檢索概率，則應(yīng)將字典中元素按檢索概率由大到小排序，以便提高檢索效率。索概率由大到小排序，以便提高檢索效率。討論討論6.4.3 有序順序表與二分法檢索

21、一種提高檢索效率的方法是將字典元素按關(guān)鍵碼遞增(或者遞減)的順序排序，這種按照關(guān)鍵碼大小排序的順序表稱為有序順序表有序順序表。對(duì)于有序順序表，可以還采用順序檢索的方法進(jìn)行查找，當(dāng)檢索到元素的關(guān)鍵碼大于(或者小于)給定值時(shí)，就可以返回檢索失敗的信息。下面介紹的另外一種檢索方法，稱為二分法檢索二分法檢索，是專門為有序順序表設(shè)計(jì)的。 二分法檢索二分法檢索又稱折半檢索，是一種效率較高的檢索方法，使用這種方法檢索時(shí)，要求字典的元素在順序表中按關(guān)鍵碼排序。基本思想：首先將給定值key與數(shù)組中間位置上元素的關(guān)鍵碼比較，如果相等，則檢索成功；否則，若key小，則在數(shù)組前半部分中繼續(xù)進(jìn)行二分法檢索，否則在數(shù)組后

22、半部分中繼續(xù)進(jìn)行二分法檢索。這樣，經(jīng)過一次比較就縮小一半的查找區(qū)間，如此進(jìn)行下去，直到能夠確定檢索成功或檢索失敗為止。int binarySearch(SeqDictionary * pdic, KeyType key, int *position) 二分法檢索二分法檢索分析分析二分法檢索每經(jīng)過一次比較就將檢索范圍縮小一半，第i次比較可能比較的元素個(gè)數(shù)如下表比較次數(shù) 可能比較的元素個(gè)數(shù) 1 1=20 2 2=21 3 4=22 j 2j-1若字典元素個(gè)數(shù)n剛好為20+21+2j-1=2j-1則最大檢索長(zhǎng)度為j；若2j-11時(shí)碰撞就不可避免。 數(shù)基本區(qū)域能容納的結(jié)點(diǎn)字典中結(jié)點(diǎn)數(shù)目主要應(yīng)解決兩個(gè)問

23、題：一個(gè)是根據(jù)字典中元素的特點(diǎn)，選擇適當(dāng)?shù)纳⒘泻瘮?shù)，使得散列地址的分布盡可能均勻地分布在基本區(qū)域之中；另一個(gè)是根據(jù)存儲(chǔ)空間的條件，設(shè)計(jì)具體的處理（同義詞）碰撞的方法。 用散列法表示的字典稱為散列表散列表（hash table）。 字典的散列表示字典的散列表示6.5.2 散列函數(shù)散列函數(shù)也稱雜湊函數(shù)雜湊函數(shù)。一般而言，散列函數(shù)的選取應(yīng)根據(jù)具體問題具體分析的原則，針對(duì)具體字典元素關(guān)鍵碼集合的特性，加上用戶的需求和空間、時(shí)間的條件，去構(gòu)造相對(duì)理想的散列函數(shù)。使散列函數(shù)計(jì)算出的地址盡可能均勻地分布在希望的地址空間中。同時(shí)，為了提高關(guān)鍵碼到地址的轉(zhuǎn)換速度，散列函數(shù)應(yīng)該盡可能簡(jiǎn)單。n數(shù)字分析法 常常有這樣

24、的情況，關(guān)鍵碼位數(shù)比基本區(qū)的地址碼位數(shù)多，這時(shí)可以對(duì)關(guān)鍵碼的各位進(jìn)行分析，丟掉分布不均勻的位留下均勻的位作為地址。 key h(key)000319426326000718309709000629443643000758615715000919697997000310329329n折疊法如果關(guān)鍵碼的位數(shù)比地址位數(shù)多，且各位分布較均勻，不適于用數(shù)字分析法，則可以考慮折疊法。折疊法將關(guān)鍵碼從某些地方斷開，分為幾部分，其中最大部分的長(zhǎng)度等于地址碼的長(zhǎng)度，再加上其余部分，舍棄進(jìn)位。例如關(guān)鍵碼為key=582422241，要求轉(zhuǎn)換為4位的地址碼。下面兩種折疊方法都是可行的： 58 | 2422 | 24

25、1 58 | 2422 | 241 移位折疊相加 移位相加 8 5 5 8 1 4 2 2 4 1 2 4 2 2 2 4 2 2 1 1 0 6 4 2 7 2 1h1(key)=1064,h2(key)=2721, n中平方法中平方法先求出關(guān)鍵碼的平方，然后取中間幾位作為地址。例如：關(guān)鍵碼key=4731，47312=22382361。如果地址長(zhǎng)度為3位，則可以取第三位到第五位作為散列地址，即有h1(4731)=382，當(dāng)然也可以取46位，即有h2(4731)= 823。 把關(guān)鍵碼看作是另一個(gè)進(jìn)制的表示，然后再轉(zhuǎn)換成原來進(jìn)制的數(shù)，最后用數(shù)字分析法取其中幾位作為散列地址。一般轉(zhuǎn)換基數(shù)大于原基

26、數(shù)，且兩個(gè)基數(shù)最好互素。例如key=(236075)10是十進(jìn)制數(shù)，把它看作十三進(jìn)制數(shù)(236075)13，再轉(zhuǎn)換成十進(jìn)制數(shù)(236075)13=2135+3134+6133+713+5 =(841547)10然后參考其它關(guān)鍵碼的分布和地址空間大小，通過數(shù)字分析法，選擇其中幾位。假設(shè)選擇了第二位到第五位，則h(236075)=4154。 n基數(shù)轉(zhuǎn)換法選擇一個(gè)適當(dāng)?shù)恼麛?shù)P，用P去除關(guān)鍵碼，余數(shù)作為散列地址，即h(key)=key%P。這個(gè)方法的關(guān)鍵是選取適當(dāng)?shù)腜。一般P為不大于基本區(qū)域長(zhǎng)度m的最大素?cái)?shù)比較好。例如m=8,16,32,64,128,256,512,1024可以?。簆=7,13,3

27、1,61,127,251,503,1019除余法地址計(jì)算公式非常簡(jiǎn)單。但是對(duì)于動(dòng)態(tài)字典和關(guān)鍵碼沒有規(guī)律出現(xiàn)的情況，經(jīng)常采用。 n除余法除余法6.5.3 碰撞的處理-開地址法、拉鏈法設(shè)給定一個(gè)元素，其關(guān)鍵碼為key，首先使用選擇的散列函數(shù)h,計(jì)算出散列地址h(key)。如何執(zhí)行插入?如何執(zhí)行檢索?n碰撞的處理方法一：開地址法在基本區(qū)域內(nèi)形成一個(gè)同義詞的探查序列，沿著探查序列逐個(gè)查找，直到找到查找的元素或碰到一個(gè)未被占用的地址為止。若插入元素，則碰到空的地址單元就存放要插入的同義詞。若檢索元素，則需要碰到空的地址單元后，才能說明表中沒有待查的元素(檢索失敗)。 采用開地址法解決碰撞，是在基本區(qū)域內(nèi)

28、存放同義詞，負(fù)載因子必須小于1，否則，一定有些元素?zé)o處存放。負(fù)載因子越小，碰撞的可能性越小，查找速度越快，當(dāng)然空間開銷也越大。 產(chǎn)生探查序列的最簡(jiǎn)單方法是線性探查線性探查，即將基本存儲(chǔ)區(qū)看作一個(gè)循環(huán)表。若在地址為d=h(key)的單元發(fā)生碰撞，則依次探查下述地址單元d+1,d+2,m-1,0,1,d-1 (m為基本存儲(chǔ)區(qū)的長(zhǎng)度) 直到找到一個(gè)空單元或查找到關(guān)鍵碼為key的元素為止。如果從單元d開始探查，查找一遍后，又回到地址d，則表示基本存儲(chǔ)區(qū)已經(jīng)溢出。 例子例子：已知關(guān)鍵碼集合K=18，73，10，5，68，99，27，41，51，32，25，設(shè)散列表基本區(qū)域用數(shù)組element表示，大小為

29、m(m=13)，散列函數(shù)為h(key)=key%13，用線性探查法解決碰撞。按散列函數(shù)d=key%13計(jì)算每個(gè)元素的散列地址如下： h(18)=5,h(73)=8,h(10)=10,h(5)=5,h(68)=3,h(99)=8 h(27)=1,h(41)=2,h(51)=12,h(32)=6,h(25)=12最后的散列表為：n存儲(chǔ)結(jié)構(gòu)typedef intKeyType;typedef intDataType;typedef struct KeyType key;/* 字典元素的關(guān)鍵碼字段字典元素的關(guān)鍵碼字段*/DataType value;/* 字典元素的屬性字段字典元素的屬性字段*/Dic

30、Element; typedef struct int m;/* m為基本區(qū)域長(zhǎng)度為基本區(qū)域長(zhǎng)度 */DicElement *element; HashDictionary; /*DicElement是字典中元素類型是字典中元素類型*/ n算法創(chuàng)建空散列表PHashDictionary createEmptyDictionary (int m ) 創(chuàng)建空散列表的實(shí)現(xiàn)與算法2.1類似,主要差別在于m在這里代替了MAXNUM的作用;另外,后面算法中假設(shè)所有有效的關(guān)鍵碼都是大于0的整數(shù)，所以當(dāng)創(chuàng)建一個(gè)空字典時(shí)，所有元素的關(guān)鍵碼初始化為一個(gè)不可能作為關(guān)鍵碼的整數(shù)值0。 程序?qū)崿F(xiàn)int linearSe

31、arch(HashDictionary * phash, KeyType key, int *position) 在檢索算法中，返回1表示檢索成功，*position為找到的元素在散列表中element數(shù)組元素的下標(biāo)值；返回0表示檢索失敗，這時(shí)如果散列表中還有可插入的空間，則*position給出合適的插入位置，否則*position中為1。程序?qū)崿F(xiàn)檢索算法 int linearInsert(HashDictionary *phash, DicElememt ele)在插入算法中，首先調(diào)用檢索算法，如果檢索失敗，再根據(jù)提供的位置信息將元素ele插入。 程序?qū)崿F(xiàn)插入算法n堆積問題在上例中，h(3

32、2)=6，h(5)=5，32和5不是同義詞，但是在解決5與18的碰撞時(shí)，5已經(jīng)存入element6，使得在插入32時(shí)，32與5本來不沖突的兩個(gè)非同義詞之間發(fā)生了碰撞。用線性探查法解決碰撞時(shí)，兩個(gè)同義詞子表結(jié)合在一起的現(xiàn)象稱為堆積堆積。為了減少堆積的產(chǎn)生，可以改進(jìn)線性探查方法，使探查序列跳躍式地分布在表中,下面介紹的雙散列函數(shù)法可以提供參考。根本的減少堆積現(xiàn)象的方法是適當(dāng)增加基本區(qū)域的空間。 n雙散列函數(shù)法雙散列函數(shù)法要選擇兩個(gè)散列函數(shù)h1和h2，它們均以關(guān)鍵碼為自變量，h1產(chǎn)生一個(gè)0到m-1之間的數(shù)作為散列地址。h2產(chǎn)生一個(gè)1到m-1之間的并和m互素的數(shù)作為對(duì)地址的增量。要求產(chǎn)生的數(shù)與m互素是

33、為了使得到的存儲(chǔ)地址探查序列能夠分布在整個(gè)基本區(qū)域內(nèi)。例如兩個(gè)散列函數(shù)可以為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, (d+3h2(key)%m, n碰撞的處理方法二：拉鏈法設(shè)基本區(qū)域長(zhǎng)度為m，使用拉鏈法需要建立m條鏈表，所有散列地址相同的元素存放在同一條鏈表中。設(shè)給定字典元素的關(guān)鍵碼為key，首先根據(jù)散列函數(shù)h計(jì)算出h(key)，即確定是在第h(key)條鏈表中，然后在該鏈表中進(jìn)行插入、刪除及檢索操作。 已知關(guān)鍵碼集合K=18，73，10

34、，5，68，99，27，41， 51， 32， 2 5 ， m 取 1 3 ， 設(shè) 散 列 函 數(shù) 為h(key)=key%13，用拉鏈法得到的散列表如下圖所示。6.5.4 散列文件讀寫文件時(shí)，為了節(jié)省外存的存取時(shí)間，需盡量減少訪外的次數(shù)。減少訪外次數(shù)的有效方法是精心設(shè)計(jì)文件的結(jié)構(gòu)，使每次訪外能夠存取更多應(yīng)用程序中需要的邏輯記錄的信息。散列文件是一種存儲(chǔ)在外存的大型字典的存儲(chǔ)結(jié)構(gòu)，它把前面介紹的散列表的思想用于外存之上。通過散列函數(shù)作用到記錄的關(guān)鍵碼，來確定記錄在外存的存儲(chǔ)地址，在處理同義詞時(shí)，常常使用適合外存分塊存取的拉鏈法。下面介紹一種常見的構(gòu)造散列文件的方法：按桶散列。 n基本思想基本思想 按桶散列的文件由若干桶和一個(gè)桶目錄表構(gòu)成。一個(gè)桶由0個(gè)或多個(gè)外存的頁塊通過指針的鏈接而構(gòu)成。散列函數(shù)值相同的記錄存放在同一個(gè)桶里。桶目錄表是一些指針的序列，通常存儲(chǔ)在內(nèi)存中，每個(gè)指針指向一個(gè)桶的首頁塊。 如果有個(gè)桶，其編號(hào)為至-，有些桶可能是空桶，空桶在桶目錄表中對(duì)應(yīng)一個(gè)空指針。下頁圖表示一個(gè)按桶散列的文件結(jié)構(gòu)示意圖。 設(shè)給定字典元素的關(guān)鍵碼為key，首先根據(jù)散列函數(shù)h計(jì)算出h(key)，即是該記錄所在的桶號(hào)，然后在該桶中進(jìn)行插入、刪除及檢索操作。 n文件的操作檢索檢索： 要查找關(guān)鍵碼值為key