數(shù)據(jù)結(jié)構(gòu)-第九章查找就是在數(shù)據(jù)集合中尋找滿足某種條

靜態(tài)查找表查找(Search)的概念查找：就是在數(shù)據(jù)集合中尋找滿足某種條件的數(shù)據(jù)對(duì)象。查找表：是由同一類型的數(shù)據(jù)元素(或記錄)組成的數(shù)據(jù)集合。查找的結(jié)果通常有兩種可能：查找成功，即找到滿足條件的數(shù)據(jù)對(duì)象。查找不成功，或查找失敗。作為結(jié)果，報(bào)告一些信息，如失敗標(biāo)志、失敗位置等。關(guān)鍵字：數(shù)據(jù)元素中某個(gè)數(shù)據(jù)項(xiàng)的值，用以標(biāo)識(shí)一個(gè)數(shù)據(jù)元素主關(guān)鍵字：可唯一地標(biāo)識(shí)一個(gè)數(shù)據(jù)元素的關(guān)鍵字次關(guān)鍵字：用以識(shí)別若干記錄的關(guān)鍵字使用基于主關(guān)鍵字的查找，查找結(jié)果應(yīng)是唯一的。9.1

靜態(tài)查找表基本操作：Create(&ST,n); //構(gòu)造含有n個(gè)元素的靜態(tài)查找表STDestroy(&ST); //銷毀表Search(ST,key);

//查找關(guān)鍵字為key的數(shù)據(jù)元素Traverse(ST,visit()); //遍歷查找表衡量一個(gè)查找算法的時(shí)間效率的標(biāo)準(zhǔn)是：在查找過程中關(guān)鍵字的平均比較次數(shù)或平均讀寫磁盤次數(shù)(只適合于外部查找)，這個(gè)標(biāo)準(zhǔn)也稱為平均查找長度ASL(Average

Search

Length)，通常它是查找結(jié)構(gòu)中對(duì)象總數(shù)n或文件結(jié)構(gòu)中物理塊總數(shù)n

的函數(shù)。另外衡量一個(gè)查找算法還要考慮算法所需要的量和算法的復(fù)雜性等問題。在靜態(tài)查找表中，數(shù)據(jù)對(duì)象存放于數(shù)組中，利用數(shù)組元素的下標(biāo)作為數(shù)據(jù)對(duì)象的存放地址。查找算法根據(jù)給定值x，在數(shù)組中進(jìn)行查找。直到找到x在數(shù)組中的存放位置或可確定在數(shù)組中找不到x為止。9.1.1順序表的查找(SequentialSearch)所謂順序查找，又稱線性查找，主要用于

性結(jié)構(gòu)中進(jìn)行查找。?結(jié)構(gòu)：typedef

struct{ElemType

*elem;intlength;}

SSTable;查找過程：從表中最后一個(gè)元素開始，順序用各元素的關(guān)鍵字與給定值x進(jìn)行比較，若找到與其值相等的元素，則查找成功，給出該元素在表中的位置；否則，若直到第一個(gè)記錄仍未找到關(guān)鍵字與x相等的對(duì)象，則查找失敗。算法9.1Search_Seq(SSTable

ST,

KeyType

key){//順序查找的算法，0號(hào)元素為監(jiān)視哨int

i；S

em[0].key=key;for

(i=ST.length;

!EQ(S

em[i].key,key);--i);return

i;}ASLsuccni

1

pi

(n

i

1)succnASL

i

11

(n

i

1)

1

n(n

1)

n

1.n

n

2

2順序查找的平均查找長度設(shè)查找第i個(gè)元素的概率為

pi，查找到第i個(gè)元素所需比較次數(shù)為ci，則查找成功的平均查找長度:n

nASLsui

1

i

1在順序查找情形，ci

=n-i

+1,

i

=

1,

,

n，因此在等概率情形，pi

=1/n,i

=0,

1,

,n-1。9.1.2

有序表的查找折半查找：先求位于查找區(qū)間正中的對(duì)象的下標(biāo)mid，用其關(guān)鍵字與給定值x比較:Element[mid].getKey()=x，查找成功；

Element[mid].getKey()>x，把查找區(qū)間縮小到表的前半部分，再繼續(xù)進(jìn)行對(duì)分查找；

Element[mid].getKey()<x，把查找區(qū)間縮小到表的后半部分，再繼續(xù)進(jìn)行對(duì)分查找。每比較一次，查找區(qū)間縮小一半。如果查找區(qū)間已縮小到一個(gè)對(duì)象，仍未找到想要查找的對(duì)象，則查找失敗。9.1.2

有序表的查找折半查找：（1）mid= (low+high)/2」em[mid].key

==key?em[mid].key

=

=

key，則查找成功，返（2）比較S如果

S回mid值如果S如果Sem[mid].key>key，則置high=mid-1em[mid].key<key，則置low=mid+1(3)重復(fù)計(jì)算mid

以及比較S

em[mid].key與

key，當(dāng)low>high時(shí)，表明查找不成功，查找結(jié)束。查找成功的例子查找失敗的例子算法9.2(p220)int

Search_Bin(SSTable

ST,KeyType

key)

//折半查找{

int

low,high,mid;low

=1;

high=ST.length;while

(low

<

high){

mid

=(low+high)/2;if(EQ(key,Selse

if(LT(key,Sem[mid].key)) return

mid;em[mid].key))

high=mid-1;else

low=mid+1;}return

0;}9.1.3索引順序表的查找——分塊查找分塊有序表：將長度為n的線性表分成m個(gè)子表，各子表的長度可以相等,也可以互不相等,但要求后一個(gè)子表中的每一個(gè)元素均大于前一個(gè)子表中的所有元素。分塊有序表的結(jié)構(gòu)分為兩部分:(l)線性表本身采用順序 結(jié)構(gòu)。(2)再建立一個(gè)索引表。在索引表中,對(duì)線性表的每個(gè)子表建立一個(gè)索引結(jié)點(diǎn).每個(gè)結(jié)點(diǎn)包括兩個(gè)域,一是數(shù)據(jù)域,用于存放對(duì)應(yīng)子表中的最大元素值；二是指針域,用于指示對(duì)應(yīng)子表的第一個(gè)元素在整個(gè)線性表中的序號(hào)。1234522468699103根據(jù)分塊有序表的結(jié)構(gòu),查找過程分以下兩步進(jìn)行：(l)查找索引表,以確定被查元素所在的子表。由于索引表數(shù)據(jù)域中的數(shù)據(jù)是有序的,因此可以采用對(duì)分查找。(2)在相應(yīng)的子表中用順序查找法進(jìn)行具體的查找。44low111high532mid32key86469.2

動(dòng)態(tài)查找表表結(jié)構(gòu)本身是在查找過程中動(dòng)態(tài)生成的。基本操作：InitDSTable(&DT);

//構(gòu)造一個(gè)空的動(dòng)態(tài)查找表DTDestroyDSTable(&DT);

//銷毀表SearchDSTable(DT,key); //查找關(guān)鍵字為key的數(shù)據(jù)元素InsertDSTable(&DT,e);DeleteDSTable(&DT,key);TraverseDSTable(DT,visit()); //遍歷查找表9.2.1二叉排序樹(Binary

SortTree)定義二叉排序樹（二叉查找樹）或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：每個(gè)結(jié)點(diǎn)都有一個(gè)作為查找依據(jù)的關(guān)鍵字(key)，所有結(jié)點(diǎn)的關(guān)鍵字互不相同。左

(若非空)上所有結(jié)點(diǎn)的關(guān)鍵字都小于根結(jié)點(diǎn)的關(guān)鍵字。右

(若非空)上所有結(jié)點(diǎn)的關(guān)鍵字都大于根結(jié)點(diǎn)的關(guān)鍵字。左 和右 也是二叉排序樹。幾個(gè)二叉排序樹的例子如果對(duì)一棵二叉排序樹進(jìn)行中序遍歷，可以按從小到大的順序，將各結(jié)點(diǎn)關(guān)鍵字排列起來。二叉排序樹的構(gòu)建從空樹出發(fā)，依次

R1～

Rn各數(shù)據(jù)值：如果二叉排序樹是空樹，則

結(jié)點(diǎn)就是二叉排序樹的根結(jié)點(diǎn)；如果二叉排序樹是非空的，則

值與根結(jié)點(diǎn)比較，若小于根結(jié)點(diǎn)的值，就插入到左

中去；否則

到右中輸入數(shù)據(jù)，建立二叉排序樹的過程輸入數(shù)據(jù)序列

{53,78,

65,

17,

87,09,

81,

45,

23}同樣3個(gè)數(shù)據(jù){1,2,3}，輸入順序不同，建立起來的二叉排序樹的形態(tài)也不同。這直接影響到二叉排序樹的查找性能。如果輸入序列選得不好，會(huì)建立起一棵單支樹，使得二叉排序樹的高度達(dá)到最大，這樣必然會(huì)降

低查找性能。{2,

1,

3}{1,

2,

3} {1,

3,

2} {2,3,

1} {3,

1,

2} {3,

2,

1}1

1

2

3

32

3

1

3

1

23

2

2

1二叉排序樹的數(shù)據(jù)類型描述typedef struct

{

int

key;

}

ElemType;typedef

struct

BiTNode{ElemType

data;struct

BiTNode

*lchild,*rchild;}

BiTNode,

*

BiTree;二叉排序樹上的查找在二叉排序樹上進(jìn)行查找，是一個(gè)從根結(jié)點(diǎn)開始，沿某一個(gè)分支逐層向下進(jìn)行比較判等的過程。它可以是一個(gè)遞歸的過程。假設(shè)想要在二叉排序樹中查找關(guān)鍵字為x的元素，查找過程從根結(jié)點(diǎn)開始。如果根指針為NULL，則查找不成功；否則用給定值x與根結(jié)點(diǎn)的關(guān)鍵字進(jìn)行比較：如果給定值等于根結(jié)點(diǎn)的關(guān)鍵字，則查找成功。如果給定值小于根結(jié)點(diǎn)的關(guān)鍵字，則繼續(xù)遞歸查找根結(jié)點(diǎn)的左

；否則。遞歸查找根結(jié)點(diǎn)的右

。int

SearchBST(BiTree

T,KeyType

key,BiTreef,BiTree

&p){//二叉排序樹的遞歸查找算法if

(!T)

{p=f;

return

FALSE;}else

if

(EQ(key,T->data.key)){p=T;returnTRUE;}else

if

(LT(key,T->data.key))

returnSearchBST(T->lchild,key,T,p);else

returnSearchBST(T->rchild,key,T,p);}二叉排序樹的為了向二叉排序樹中

一個(gè)新元素，必須先檢查這個(gè)元素是否在樹中已經(jīng)存在。在

之前，先使用查找算法在樹中檢查要元素有還是沒有。查找成功:樹中已有這個(gè)元素，不再

查找不成功:樹中原來沒有關(guān)鍵字等于給定值的結(jié)點(diǎn)，把新元素加到查找操作停止的地方。二叉排序樹的查找

新結(jié)點(diǎn)88每次結(jié)點(diǎn)的

，都要從根結(jié)點(diǎn)出發(fā)查找插入位置，然后把新結(jié)點(diǎn)作為葉結(jié)點(diǎn)

。emType

e){int

InsertBST(BiTree

&//二叉排序樹

算法BiTree

s,p;if

(!SearchBST(T,e.key,NULL,p)){

s=(BiTree)malloc(sizeof(BiTNode));s->data=e;

s->lchild=s->rchild=NULL;if

(!p)

T=s;else

if

(LT(e.key,p->data.key))

p->lchild=s;else

p->rchild=s;(右

)return

TRUE;}else

return

FALSE;}二叉排序樹的刪除在二叉排序樹中刪除一個(gè)結(jié)點(diǎn)時(shí)，必須將因刪除結(jié)點(diǎn)而斷開的二叉鏈表重新起來，同時(shí)確保二叉排序樹的性質(zhì)不會(huì)失去。為保證在執(zhí)行刪除后，樹的查找性能不至于降低，還需要防止重新后樹的高度增加。–刪除葉結(jié)點(diǎn)，只需將其雙親結(jié)點(diǎn)指向它的指針清零，再它即可。結(jié)點(diǎn)頂替它結(jié)點(diǎn)頂替它被刪結(jié)點(diǎn)缺右的位置，再被刪結(jié)點(diǎn)缺左的位置，再，可以拿它的左它。，可以拿它的右它。–

被刪結(jié)點(diǎn)左、右

都存在，可以在它的右

中尋找中序下的第一個(gè)結(jié)點(diǎn)(關(guān)鍵字最小),用它的值填補(bǔ)到被刪結(jié)點(diǎn)中，再來處理這個(gè)結(jié)點(diǎn)的刪除問題。或：在它的左 中尋找中序下的最后一個(gè)結(jié)點(diǎn)，用它的值替換被刪結(jié)點(diǎn)，再處理該結(jié)點(diǎn)的刪除。（書上算法9.8即為第二種辦法）二叉排序樹的刪除遞歸算法（算法9.7)int

DeleteBST(BiTree

&T,KeyType

key){if

(!T)

return

FALSE;else{if(EQ(key,T->data.key))

{return

Delete(T);}else

if(LT(key,T->data.key))return

DeleteBST(T->lchild,key);else

return

DeleteBST(T->rchild,key);}}int

Delete(BiTree

&p){//算法9.8BiTree

q,s;if

(!p->rchild){q=p;

p=p->lchild;

free(q);

}else

if

(!p->lchild){q=p;

p=q->rchild;

free(q);

}else{q=p;

s=p->lchild;while(s->rchild){q=s;

s=s->rchild;}p->data=s->data;if

(q!=p)

q->rchild

=

s->lchild;else

q->lchild

=

s->lchild;delete

s; }return

TRUE;}AVL樹

高度平衡的二叉查找樹AVL樹的定義一棵AVL樹或者是空樹，或者是具有下列性質(zhì)的二叉查找樹：它的左

和右都是AVL樹，且左

和右

的高度之差的絕對(duì)值不超過1。高度不平衡的二叉排序樹

高度平衡的二叉查找樹結(jié)點(diǎn)的平衡因子balance

(balance

factor)每個(gè)結(jié)點(diǎn)附加一個(gè)數(shù)字，給出該結(jié)點(diǎn)左的高度減去右

的高度所得的高度差。這個(gè)數(shù)字即為結(jié)點(diǎn)的平衡因子balance

。根據(jù)AVL樹的定義，任一結(jié)點(diǎn)的平衡因子只能取-1，0和1。如果一個(gè)結(jié)點(diǎn)的平衡因子的絕對(duì)值大于1，則這棵二叉查找樹就失去了平衡，不再是AVL樹。平衡化旋轉(zhuǎn)如果在一棵平衡的二叉查找樹中 一個(gè)新結(jié)點(diǎn)，造成了不平衡。此時(shí)必須調(diào)整樹的結(jié)構(gòu)，使之平衡化。平衡化旋轉(zhuǎn)有兩類：單旋轉(zhuǎn)(左旋和右旋)雙旋轉(zhuǎn)(左平衡和右平衡)每 一個(gè)新結(jié)點(diǎn)時(shí)，AVL樹中相關(guān)結(jié)點(diǎn)的平衡狀態(tài)會(huì)發(fā)生改變。因此，在 一個(gè)新結(jié)點(diǎn)后，需要：從

位置沿通向根的路徑回溯，檢查各結(jié)點(diǎn)的平衡因子(左、右

的高度差)。如果在某一結(jié)點(diǎn)發(fā)現(xiàn)高度不平衡，停止回溯。從發(fā)生不平衡的結(jié)點(diǎn)起，沿剛才回溯的路徑取直接下兩層的結(jié)點(diǎn)。如果這三個(gè)結(jié)點(diǎn)處于一條直線上，則采用單旋轉(zhuǎn)進(jìn)行

平衡化。單旋轉(zhuǎn)可按其方向分為左單旋轉(zhuǎn)和右單旋轉(zhuǎn)，其中一個(gè)是另一個(gè)的鏡像，其方向與不平衡的形狀相關(guān)。如果這三個(gè)結(jié)點(diǎn)處于一條折線上，則采

旋轉(zhuǎn)進(jìn)行平衡化。雙旋轉(zhuǎn)分為先左后右和先右后左兩類。右單旋轉(zhuǎn)左單旋轉(zhuǎn)左右雙旋轉(zhuǎn)右左雙旋轉(zhuǎn)左單旋轉(zhuǎn)(Rotaeft

)hhhEBD(a)(b)hhh+1BAEDhhh+1EBD如果在

E中 一個(gè)新結(jié)點(diǎn)，該(c)高度增1導(dǎo)致結(jié)點(diǎn)A的平衡因子變成-2，出現(xiàn)不平衡。沿 路徑檢查三個(gè)結(jié)點(diǎn)A、C和E。它們處于一條方向?yàn)椤癨”的直線上，需要做左單旋轉(zhuǎn)。以結(jié)點(diǎn)C為旋轉(zhuǎn)軸，讓結(jié)點(diǎn)A反時(shí)針旋轉(zhuǎn)。-1-2A0

C-1

CA

0C

0右單旋轉(zhuǎn)(RotateRight)hhhCEDhh+1CEDhhh+1CED(a)

(b)

(c)在左

D上 新結(jié)點(diǎn)使其高度增1，導(dǎo)致結(jié)點(diǎn)A的平衡因子增到2，造成了不平衡。為使樹恢復(fù)平衡，從A沿路徑連續(xù)取3個(gè)結(jié)點(diǎn)A、B和D，它們處于一條方向?yàn)椤?”的直線上，需要做右單旋轉(zhuǎn)。以結(jié)點(diǎn)B為旋轉(zhuǎn)軸，將結(jié)點(diǎn)A順時(shí)針旋轉(zhuǎn)。hB0

A0A

1B

0A

2B

1左單旋轉(zhuǎn)右單旋轉(zhuǎn)0012-1100-1先左后右雙旋轉(zhuǎn)

(RotationLeftRight)在

F或G中 新結(jié)點(diǎn)，該 的高度增1。結(jié)點(diǎn)A的平衡因子變?yōu)?/p>

2，發(fā)生了不平衡。從結(jié)點(diǎn)A起沿

路徑選取3個(gè)結(jié)點(diǎn)A、B和E，它們位于一條形如“”的折線上，因此需要進(jìn)行先左后右的雙旋轉(zhuǎn)。首先以結(jié)點(diǎn)E為旋轉(zhuǎn)軸，將結(jié)點(diǎn)B反時(shí)針旋轉(zhuǎn)，以E代替原來B的位置，做左單旋轉(zhuǎn)。再以結(jié)點(diǎn)E為旋轉(zhuǎn)軸，將結(jié)點(diǎn)A順時(shí)針旋轉(zhuǎn)，做右單旋轉(zhuǎn)。使之平衡化。左單旋轉(zhuǎn)-100右單旋轉(zhuǎn)0011-1-2先右后左雙旋轉(zhuǎn)

(RotationRightLeft)右左雙旋轉(zhuǎn)是左右雙旋轉(zhuǎn)的鏡像。在

F或G中

新結(jié)點(diǎn)，該

高度增1。結(jié)點(diǎn)A的平衡因子變?yōu)?2，發(fā)生了不平衡。從結(jié)點(diǎn)A起沿

路徑選取3個(gè)結(jié)點(diǎn)A、C和D，它們位于一條形如“”的折線上，需要進(jìn)行先右后左的雙旋轉(zhuǎn)。首先做右單旋轉(zhuǎn)：以結(jié)點(diǎn)D為旋轉(zhuǎn)軸，將結(jié)點(diǎn)C順時(shí)針旋轉(zhuǎn)，以D代替原來C的位置。再做左單旋轉(zhuǎn)：以結(jié)點(diǎn)D為旋轉(zhuǎn)軸，將結(jié)點(diǎn)A反時(shí)針旋轉(zhuǎn)，恢復(fù)樹的平衡。AVL樹的在向一棵本來是高度平衡的AVL樹中一個(gè)新結(jié)點(diǎn)時(shí)，如果樹中某個(gè)結(jié)點(diǎn)的平衡因子的絕對(duì)值|balance|>1，則出現(xiàn)了不平衡，需要做平衡化處理。算法從一棵空樹開始，通過輸入一系列對(duì)象的關(guān)鍵字，逐步建立AVL樹。在新結(jié)點(diǎn)時(shí)使用了前面所給的算法進(jìn)行平衡旋轉(zhuǎn)。（具體見

p235-236）9.3哈希表哈希表哈希函數(shù)的構(gòu)造方法處理

的方法哈希表的查找及其分析哈希(Hashing)

性表、樹結(jié)構(gòu)中查找 是通過與關(guān)鍵字的“比較”完成的。順序查找，比較的結(jié)果為“=”或“≠”非順序查找，比較的結(jié)果為“<”，“=”，“>”哈希的思想：根據(jù)

的關(guān)鍵字直接找到記錄的位置，即為關(guān)鍵字和記錄的 位置建立一個(gè)對(duì)應(yīng)關(guān)系f，使每個(gè)關(guān)鍵字和結(jié)構(gòu)中一個(gè)唯一的位置相對(duì)應(yīng)。對(duì)應(yīng)關(guān)系f為哈希函數(shù)哈希表的定義根據(jù)設(shè)定的哈希函數(shù)H(key)和處理

的方法將一組關(guān)鍵字映像到一個(gè)有限的連續(xù)的地址集（區(qū)間）上，并以關(guān)鍵字在地址集中的“像”作為記錄在表中的

位置，這種表便稱為哈希表，這一映像過程稱為哈希造表或散列，所得

位置稱哈希地址或散列地址。哈希方法在表項(xiàng)的 位置與它的關(guān)鍵字之間建立一個(gè)確定的對(duì)應(yīng)函數(shù)關(guān)系Hash(

)，使每個(gè)關(guān)鍵字與結(jié)構(gòu)中一個(gè)唯一 位置相對(duì)應(yīng)：Address

＝Hash

( Rec.key

)在查找時(shí)，首先對(duì)表項(xiàng)的關(guān)鍵字進(jìn)行函數(shù)計(jì)算，把函數(shù)值當(dāng)做表項(xiàng)的位置，在結(jié)構(gòu)中按此位置取表項(xiàng)比較。若關(guān)鍵字相等，則查找成功。在存放表項(xiàng)時(shí)，依相同函數(shù)計(jì)算位置，并按此位置存放。構(gòu)造哈希函數(shù)時(shí)的幾點(diǎn)要求：哈希函數(shù)的定義域必須包括需要的全部關(guān)鍵碼，如果哈希表允許有m個(gè)地址時(shí),其值域必須在0到m-1之間。散列函數(shù)計(jì)算出來的地址應(yīng)能均勻分布在整個(gè)地址空間中：若key是從關(guān)鍵字集合中隨機(jī)抽取的一個(gè)關(guān)鍵字，散列函數(shù)應(yīng)能以同等概率取

0到m-1中的每一個(gè)值。散列函數(shù)應(yīng)是簡單的，能在較短的時(shí)間內(nèi)計(jì)算出結(jié)果。哈希函數(shù)的構(gòu)造方法1.直接定址法此類函數(shù)直接取關(guān)鍵字或關(guān)鍵字的某個(gè)線性函數(shù)值作為散列地址：Hash(key)＝

a*key+b

{a,b為常數(shù)}這類散列函數(shù)是一對(duì)一的

，一般不會(huì)產(chǎn)生。但是，它要求散列地址空間的大小與關(guān)鍵字集合的大小相同。2.數(shù)字分析法設(shè)有n個(gè)d位數(shù)，每一位可能有r種不同的符號(hào)。這r種不同的符號(hào)在各位上出現(xiàn)的頻率不一定相同，可能在某些位上分布均勻些；在某些位上分布不均勻，只有某幾種符號(hào)經(jīng)常出現(xiàn)?？筛鶕?jù)哈希的大小，選取其關(guān)鍵字中若干位作為哈希地址。?942148?941269?940527?941630?941805?941558?942047?940001?①②③④⑤⑥數(shù)字分析法僅適用于事先明確知道表中所有關(guān)鍵字每一位數(shù)值的分布情況，它完全依賴于關(guān)鍵字集合。如果換一個(gè)關(guān)鍵字集合，選擇哪幾位要重新決定。平方取中法此方法在詞典處理中使用十分廣泛。它先計(jì)算構(gòu)成關(guān)鍵字的標(biāo)識(shí)符的內(nèi)碼的平方，然后按照散列表的大小取中間的若干位作為散列地址。設(shè)標(biāo)識(shí)符可以用一個(gè)計(jì)算機(jī)字長的內(nèi)碼表示。因?yàn)閮?nèi)碼平方數(shù)的中間幾位一般是由標(biāo)識(shí)符所有字符決定，所以對(duì)不同的標(biāo)識(shí)符計(jì)算出的散列地址大多不相同，即使其中有些字符相同。在平方取中法中，一般取散列地址為2的某次冪。例如，若散列地址總數(shù)取為m=2r，則對(duì)內(nèi)碼的平方數(shù)取中間的r位。折疊法此方法把關(guān)鍵字自左到右分成位數(shù)相等的幾部分，每一部分的位數(shù)應(yīng)與散列表地址位數(shù)相同，只有最后一部分的位數(shù)可以短一些。把這些部分的數(shù)據(jù)疊加起來，就可以得到具有該關(guān)鍵字的記錄的散列地址。有兩種疊加方法：–移位疊加法—把各部分的最后一位對(duì)齊相加；–間接疊加法—各部分不折斷，沿各部分的分界來回折疊，然后對(duì)齊相加，將相加的結(jié)果當(dāng)做散列地址。示例：設(shè)給定的關(guān)鍵字為key

=23938587841，若空間限定3位,則劃分結(jié)果為每段3位.上述關(guān)鍵字可劃分為4段：239

385

878

41刪去,僅保留最低的3位，把超出地址位數(shù)的最

做為可用的散列地址。一般當(dāng)關(guān)鍵字的位數(shù)很多，而且關(guān)鍵字每一位上數(shù)字的分布大致比較均勻時(shí)，可用這種方法得到散列地址。5.除留余數(shù)法設(shè)散列表中允許的地址數(shù)為m,取一個(gè)不大于m，但最接近于或等于m的質(zhì)數(shù)p,或選取一個(gè)不小于20的質(zhì)因數(shù)的合數(shù)作為除數(shù)，利用以下公式把關(guān)鍵字轉(zhuǎn)換成散列地址。散列函數(shù)為：hash

(key

)=key%

p p

m其中,“%”是整數(shù)除法取余的運(yùn)算，要求這時(shí)的質(zhì)數(shù)p不是接近2的冪。示例：有一個(gè)關(guān)鍵字key=962148，散列表大小m=25，即HT[25]。取質(zhì)數(shù)p=

23。散列函數(shù)hash(key)=key%p。則散列地址為：hash

(

962148

)

=962148

%

23

=

12可以按計(jì)算出的地址存放記錄。需要注意的是，使用上面的散列函數(shù)計(jì)算出來的地址范圍是0到22，因此，從23到24這幾個(gè)散列地址實(shí)際上在一開始是不可能用散列函數(shù)計(jì)算出來的，只可能在處理溢出時(shí)達(dá)到這些地址。以上介紹了幾種常用的散列函數(shù)。在實(shí)際工作中應(yīng)根據(jù)關(guān)鍵字的特點(diǎn)，選用適當(dāng)?shù)姆椒?。有人曾用“賭”的統(tǒng)計(jì)分析方法對(duì)它們進(jìn)行了模擬分析，結(jié)論是平方取中法最接近于“隨機(jī)化”。在應(yīng)用平方取中法時(shí)，若關(guān)鍵字不是整數(shù)而是字符串時(shí)，可以把每個(gè)字符串轉(zhuǎn)換成整數(shù)。轉(zhuǎn)換的方法：把字符串從右向左，按一個(gè)固定長度(例如4)進(jìn)行分段，必要時(shí)可在最左端添一些空格。把每一個(gè)字符看成為一個(gè)數(shù)字，把字符串的每一段看作為一個(gè)整數(shù)。如,

ASCII碼采用7位字符代碼，因此每一個(gè)字符可以看成一個(gè)128進(jìn)制的數(shù)字。字符串a(chǎn)bcd看成整數(shù)

a*(128)3

+b*(128)2

+c*(128)

+

d。把字符串的每一段都轉(zhuǎn)換成一個(gè)整數(shù)后，再把各段轉(zhuǎn)換成的整數(shù)加起來。如果這個(gè)整數(shù)之和太大，再選擇一個(gè)適當(dāng)?shù)某?shù)C(大于任一段字符串轉(zhuǎn)換成的整數(shù))來除這個(gè)和并取其余數(shù)，就得到這個(gè)字符串所對(duì)應(yīng)的整數(shù)了。開放定址法（閉散列）——是處理溢出的一種常用的方法Hash函數(shù)：Hi

=

(H(key)+di)

MOD

m,

i=1,2,…,k(k≤m-1)其中：H(key)為哈希函數(shù)，m為哈希表表長，di為增量序列。di分別有三種取法：di=1,2,3,…,m-