大二上数据结构教学ch9查找

CH9

查找引言查找的概念静态查找表顺序查找有序表的查找索引顺序表的查找动态查找表二叉排序树和平衡二叉树哈希表何谓查找表？查找表是由同一类型的数据元素(或记录)构成的集合。由于“集合”中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的结构。9.0查找的概念对查找表经常进行的操作:1）查询某个“特定的”数据元素是否在查找表中；2）检索某个“特定的”数据元素的各种属性；3）在查找表中插入一个数据元素；4）从查找表中删去某个数据元素。9.0查找的概念静态查找表仅作查询和检索操作的查找表。动态查找表有时在查询之后，还需要将“查询”结果为“不在查找表中”的数据元素插入到查找表中；或者，从查找表中删除其“查询”结果为“在查找表中”的数据元素查找表可分为两类:关键字是数据元素（或记录）中某个数据项的值，用以标识（识别）一个数据元素（或记录）。若此关键字可以识别唯一的一个记录，则称之谓“主关键字”。若此关键字能识别若干记录，则称之谓“次关键字”。9.0查找的概念9.0查找的概念查找根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或（记录）查找结果:查找成功(table

中存在给定值的记录)查找不成功(table

中不存在给定值的记录)本章数据元素类型与比较运算的符号约定1）数据类型定义typedef

struct

{keytype

key;……}ElemType;

2）关键字比较的符号约定EQ(a,b)

((a)=

=(b))LT(a,b)

((a)<(b))LQ(a,b)

((a)<=(b))静态查找表动态查找树表哈希表9.1静态查找表一、顺序查找表二、有序查找表三、索引顺序表以顺序表或线性链表表示静态查找表一、顺序查找表假设静态查找表的顺序存储结构为typedef struct

{ElemType

*elem;//数据元素存储空间基址，建表时//按实际长度分配，0号单元留空int

length;

//表的长度}

SSTable;数据元素类型的定义为:typedef

struct

{keyType

key;…

…//关键字域//其它属性域;}

ElemType

,

TElemType

;2137881992056456807513回顾顺序表的查找过程：k

kST.elem0

1

2

3

4

5

6

7

8

9

10

11ST.Length假设给定值e=64,要求ST.elem[k].key=e,

问:k=?int

location(

SqList

ST,

ElemType&

e)

{k

=

1;while(

k<=ST.length

&&ST.elem[k].key!=e))k++;if

(

k<=

ST.length)

return

k;else return

0;}

//locationiiST.elem602137881992056456807513i0

1

2

3

4

5

6

7

8

9

10

11key=64

ST.Length0

1

2

3

4

5

6

7

8

9

10

11key=60

ST.Lengthi642137881992056456807513如何消除比较：k<=L.lengthST.elemint

Search_Seq(SSTable

ST,KeyType

key)

{//在顺序表ST中顺序查找其关键字等于//

key的数据元素。若找到，则函数值为//该元素在表中的位置，否则为0。ST.elem[0].key

=

key;//“哨兵”for

(i=ST.length;

ST.elem[i].key!=key;

--i);//从后往前找//找不到时，i为0return

i;}

//

Search_Seq其中:n为表长，Pi

为查找表中第i个记录的概率，值比较过的关键字的个数。n分析顺序查找的时间性能定义：查找算法的平均查找长度(Average

Search

Length)为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值ASL

=

PiCii=1ni=1且

Pi

=

1

，

Ci为找到该记录时，曾和给定顺序表查找成功的平均查找长度为：ni在等概率查找的情况下，P

=121n

+1(n

-

i

+1)

=nni=1ASLss

=对顺序表而言，Ci

=

n-i+1ASL

=

nP1

+(n-1)P2

++2Pn-1+Pn任意关键字查找不成功的比较次数为n＋1，则平均查找长度为Pi=1/2n顺序表的平均查找长度为：2=1

n

+1(n

-

i

+1)nASLss

=2n

i=1+=3/4(n+1)二、有序查找表上述顺序查找表的查找算法简单，但平均查找长度较大，特别不适用

于表长较大的查找表。若以有序表表示静态查找表，则查找过程可以基于“折半”（二分查找）进行。0513192137566475808892ST.length例如:key=64

的查找过程如下：lowhighmidmidST.elem0

1

2

3

4

5

6

7

8

9

10

11low

highmidlow

指示查找区间的下界high

指示查找区间的上界mid

=(low+high)/2int

Search_Bin

(

SSTable

ST,

KeyType

key

)

{//置区间初值low=1;

high

=ST.length;while(low<=high)

{mid=(low+high)/2;if

（EQ

(key

,

ST.elem[mid].key)

)return

mid;//找到待查元素else if

(

LT

(key

,ST.elem[mid].key))high

=mid

-1;//继续在前半区间进行查找else

low=mid+1;//继续在后半区间进行查找//顺序表中不存在待查元素}return

0;}

//

Search_Bin先看一个具体的情况，假设：n=11分析折半查找的平均查找长度69425781011判定树31i1234567891011Ci34234134234可以看出：n个结点的判定树的深度和n个结点的完全二叉树的深度相同；查找过程：从根到结点（或外部结点）走出的路径；二叉树第k层结点的查找次数各为k次(根结点为第1层)，而第k层结点数最多为2k－1个。设有序表的长度为n＝2h－1(即h=log2(n+1)),则折半查找的判定树为深为h的满二叉树，并设每条记录的查找概率(pi=1/n)相等，则查找成功时的平均查找长度：2

j

-1hi

=1

j

=1j1ni

inASL

bs

=

p

c

=2

2n=

n

+

1

log (

n

+

1)

-

1

»

log (

n

+

1)

-

1可见，折半查找的效率比顺序查找高，但是，折半查找只适用于有序表，且限于用顺序存储结构（对线性链表无法有效进行折半查找）索引表:按表中记录的关键字分块,R1,R2,…,RL要求:

第Rk

块中的所有关键字<

Rk+1块中的所有关键字k=1,2,…,L-1,

称为“分块有序”对每块建立一个索引项,包含以两项内容:①关键字项:为该块中最大关键字值;②指针项:为该块第一个记录在表中位置.所有索引项组成索引表三、索引顺序表的查找(分块查找)项

2248861713三、索引顺序表的查找(分块查找)例.查找表为:22,

12,

13,

8,

9,

20,

33,

42,

44,

38,

24,

48,

60,

58,

74,

49,

86,

53索引表为:关键字指针项22,

12,

13,

8,

9,

20,

33,

42,

44,

38,

24,

48,

60,

58,

74,

49,

86,

53关键字项指针项2248861

7

1322,

12,

13,

8,

9,

20,

33,

42,

44,

38,

24,

48,

60,

58,

74,

49,

86,

53查找分为两步:确定待查记录所在块;

(可以用顺序或折半查找)在块内顺序查找.

(只能用顺序查找)例如:k=38第1步:k=38

的记录只可能在块2中;第2步:从r[7]开始,直到k=r[i].key

或i>12为止.三、索引顺序表的查找(分块查找)分块查找表的平均查找长度ASL=Lb+Lw其中:Lb为查索引表确定所在块的平均查找长度;Lw为在块内查找记录的平均查找长度;.性能分析设长度为n的表均匀地分为b块，每块有s个记录，且表中每个记录的查找概率相等，则：三、索引顺序表的查找(分块查找)1）若顺序查找确定所在块：2

2

2

2

s‡

n

+

1=

b

+

1

+

s

+

1

=

1

(b

+

s

)

+

1

=

1

(

n

+

s

)

+

1sb+

ASLASL

=

ASLsj

+

1

ib=

1

j

=1

i

=1wbbs2）若折半查找确定所在块：1222s

2isswbbs(

n

+

1)

+

ss

2=

log (

n

+

1)

+

s

+

1

»

log»

log (

b

+

1)

-

1

++

ASLASL

=

ASLi

=1小结：静态查找表三种查找方法的比较顺序查找折半查找分块查找平均查找长度最大最小介于二者之间表结构有序/无序表有序表表中元素逐段有序存储结构顺序/链式存储顺序存储顺序/链式存储9.2动态查找表动态查找表的特点：

表结构本身是在查找过程中动态生成的，即对于给定值key,若表中存在其关键字等于key的记录，则查找成功返回，否则插入关键字等于key的记录。一、二叉排序树（二叉查找树）二、二叉平衡树三、B-树和B+树一、二叉排序树（二叉查找树）定义查找算法插入算法删除算法查找性能的分析1．定义：二叉排序树或者是一棵空树；或者是具有如下特性的二叉树：若它的左子树不空，则左子树上

所有结点的值均小于根结点的值；若它的右子树不空，则右子树上

所有结点的值均大于根结点的值；它的左、右子树也都分别是二叉排序树。5030802090854010

25

352388例如:66不是二叉排序树。通常，取二叉链表作为二叉排序树的存储结构typedef

struct

BiTNode

{

//结点结构TElemType

data;struct

BiTNode

*lchild,

*rchild;//左右孩子指针}

BiTNode,

*BiTree;1）若给定值等于根结点的关键字，则查找成功；2）若给定值小于根结点的关键字，则继续在左子树上进行查找；3）若给定值大于根结点的关键字，则继续在右子树上进行查找。2．二叉排序树的查找算法：若二叉排序树为空，则查找不成功；否则，858832例如:

二叉排序树335555003020

40809900查找关键字==50

,

35

,

90

,

95

,从上述查找过程可见，在查找过程中，生成了一条查找路径：从根结点出发，沿着左分支或右分支逐层向下直至关键字等于给定值的结点;或者

——查找成功从根结点出发，沿着左分支或右分支逐层向下直至指针指向空树为止。——查找不成功查找过程算法9.5-a

递归过程BiTree

SearchBST(BiTree

T,KeyType

key){if

(!T)

||EQ(key,T->data.key)

return

T;else

if

LT(key,T->data.key)return(SearchBST(T->lchild,key));elsereturn(SearchBST(T->rchild,key));}//

SearchBST算法描述如下：Status

SearchBST

(BiTree

T,

KeyType

key,BiTree

f,

BiTree

&p

)

{//在根指针T

所指二叉排序树中递归地查找其//关键字等于key

的数据元素，若查找成功，//则返回指针p

指向该数据元素的结点，并返回//

函数值为TRUE;

否则表明查找不成功，返回//指针p

指向查找路径上访问的最后一个结点，//并返回函数值为FALSE,指针f

指向当前访问//的结点的双亲，其初始调用值为NULL…

…

…

…}

//

SearchBSTif

(!T){p=f;

return

FALSE;}

//查找不成功else if

(EQ(key,

T->data.key)

){p=T;

return

TRUE;}

//查找成功else if

(

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

(T->lchild,

key,

T,

p

);//在左子树中继续查找else

SearchBST

(T->rchild,

key,

T,

p

);//在右子树中继续查找3020104023fT48fTfT设key=22pfTfTTTTfff

25

35p3．二叉排序树的插入算法根据动态查找表的定义，“插入”操作在查找不成功时才进行；新插入的结点必为一个新的叶子结点（若二叉排序树为空树，则新插入的结点为新的根结点）

，其插入位置由查找路径上访问最后一个结点的左孩子或右孩子。Status

Insert

BST(BiTree

&T,

ElemType

e

){//当二叉排序树中不存在关键字等于e.key

的//数据元素时，插入元素值为e

的结点，并返//回TRUE;

否则，不进行插入并返回FALSEif

(!SearchBST

(

T,

e.key,

NULL,

p

))}else

return

FALSE;}

//

InsertBST{

…

…s

=

(BiTree)

malloc

(sizeof

(BiTNode));//为新结点分配空间s->data=e;s->lchild

=

s->rchild

=

NULL;if

(

!p

) T

=

s;//插入s

为新的根结点else if

(

LT(e.key,

p->data.key)

)p->lchild

=

s;else

p->rchild=s;//插入*s

为*p的左孩子//插入*s

为*p

的右孩子return

TRUE;//插入成功例：设BST为空，查找关键字序列为{45，24，53，45，12，24，90}，则经过一系列查找插入操作后，生成的BST为：45245312904．二叉排序树的删除算法和插入相反，删除在查找成功之后进行，并且要求在删除二叉排序树上某个结点之后，仍然保持二叉排序树的特性。可分三种情况讨论：（1）被删除的结点是叶子；（2）被删除的结点只有左子树或者只有右子树；（3）被删除的结点既有左子树，也有右子树。503080209085403588（1）被删除的结点是叶子结点例如:20被删关键字=8832其双亲结点中相应指针域的值改为“空”30802090854035（2）被删除的结点只有左子树或者只有右子树5032

88其双亲结点的相应指针域的值改为

“指向被删除结点的左子树或右子树”。40被删关键字=802090854035（3）被删除的结点既有左子树，也有右子树4088以其前驱替代之，然后再删除该前驱结点32前驱结点

被删结点被删关键字=50540030

80Status

DeleteBST

(BiTree

&T,

KeyType

key

)

{//若二叉排序树T

中存在其关键字等于key

的//数据元素，则删除该数据元素结点，并返回//函数值TRUE，否则返回函数值FALSEif

(!T)

return

FALSE;//不存在关键字等于key的数据元素else

{}}

//

DeleteBST算法描述如下：……if

(

EQ

(key,

T->data.key)

){ Delete(T);

return

TRUE;

}//找到关键字等于key的数据元素else

if

(

LT

(key,

T->data.key)

)DeleteBST

(

T->lchild,

key

);//继续在左子树中进行查找else

DeleteBST

(

T->rchild,

key

);//继续在右子树中进行查找}其中删除操作过程如下所描述：void

Delete

(

BiTree

&p){//从二叉排序树中删除结点p，//并重接它的左子树或右子树if

(!p->rchild)

{

…

…

}…

…else

if

(!p->lchild)

{else{

…

…

}}//

Delete//右子树为空树则只需重接它的左子树q

=

p; p

=

p->lchild;

free(q);pp//左子树为空树只需重接它的右子树q

=

p; p

=

p->rchild;

free(q);pp//左右子树均不空q=p; s

=p->lchild;while

(!s->rchild)

{

q

=

s; s=s->rchild;

}//s

指向被删结点的前驱p->data=s->data;if

(q

!=p) q->rchild=s->lchild; //重接*q右子树pqspqselse

q->lchild

=

s->lchild;//重接*q的左子树free(s);5．查找性能的分析对于每一棵特定的二叉排序树，均可按照平均查找长度的定义来求它的ASL

值，显然，由值相同的n个关键字，构造所得的不同形态的各棵二叉排序树的平均查找长度的值不同，甚至可能差别很大。例如：2134535412由关键字序列1，2，3，4，5构造而得的二叉排序树，ASL

=（1+2+3+4+5）/

5=

3由关键字序列3，1，2，5，4构造而得的二叉排序树，ASL

=（1+2+3+2+3）/

5=

2.2二、二叉平衡树何谓“二叉平衡树”？如何构造“二叉平衡树”二叉平衡树的查找性能分析二叉平衡树是二叉查找树的另一种形式，其特点为：树中每个结点的左、右子树深度之差的绝对值不大于1例如:hL

-hR

£1

。548254821是平衡树不是平衡树构造的二叉排序树成为平衡树的方法是：25868在插入过程中，采用平衡旋转技术。例如:依次插入的关键字为5,4,2,8,6,95

4

44

2

2

6向右旋转一次5先向右旋转再向左旋转42

65

89642895向左旋转一次继续插入关键字9ABDCEACDBEACEDB右单旋左单旋1.2.ABDCEhABDCFEGAEBDCFG左单旋右单旋ABDCFEhh-1G3.右单旋左单旋4.DACBEFhh-1GACBEFGDACBEFGD平衡树的查找性能分析：在平衡树上进行查找的过程和二叉排序树相同，因此，查找过程中和给定值进行比较的关键字的个数不超过平衡树的深度。问：含n个关键字的二叉平衡树可能达到的最大深度是多少？n

=

0空树最大深度为0n

=

1最大深度为1n

=

2最大深度为2n

=

4最大深度为3n

=

7最大深度为4先看几个具体情况:反过来问，深度为h的二叉平衡树中所含结点的最小值Nh

是多少？h

=

0

N0

=

0

h

=

1N1

=

1h

=

2

N2

=

2

h

=

3

N3

=

4一般情况下

Nh

=

Nh-1

+

Nh-2

+

1平衡树上查找的时间复杂度：O(logn)9.2.2

B-树和B+树一、B-树(多路搜索树）1.定义：一棵m阶的B-树，或为一棵空树，或为满足下列条件的m叉树：树中每个结点至多m棵子树；若根结点不是叶结点，则至少2棵子树；除根以外的所有非终端结点至少有┌m/2┐棵子树；所有非终端结点中包含下列信息数据：（n,A0,K1,A1,K2,A2,…，Kn,An)叶结点位于同一层次（外部结点/失败点）351181784321112713916447533991FFFFFFFFFFFFbcdefgh2.示例（一棵4阶B－树及查找过程）Ta查找时间取决因素等于给定值的关键字所在结点的层次；结点中关键字的个数。（M=3）3阶B-树3.查找过程：顺指针查找结点和在结点的关键字中顺序查找交叉进行的过程。具体方法：从根结点开始，将key与根结点中的各个关键字k1,k2,……，kj进行比较，由于该关键字序列有序，可采用顺序/二分查找方法。若key=ki,(1≤i≤j),则查找成功；若key<k1,则沿指针A0所指的子树中继续查找；若ki<key<ki+1,则沿指针Ai所指的子树中继续查找；若key>kj,则沿指针Aj所指的子树中继续查找。在自上向下的查找过程中，若直到叶结点也没有找到值为key的关键字，则查找失败。9.2.2

B-树和B+树B＋树（B－的变型树）

B+树是B-树的变体，也是一种多路搜索树，其定义基本与B-树同，除了：–

1）非叶子结点的子树指针与关键字个数相同；

2）非叶子结点的子树指针P[i]，指向关键字值属于[K[i],K[i+1])的子树（B-树是开区间）；3）为所有叶子结点增加一个链指针；4）所有关键字都在叶子结点出现；（M=3）3阶B+树B+的搜索与B-树也基本相同，区别是B+树只有达到叶子结点才命中（B-树可以在非叶子结点命中），其性能也等价于在关键字全集做一次二分查找；B+的特性：1.所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；2.不可能在非叶子结点命中；3.非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；4.更适合文件索引系统；一、哈希表是什么？二、哈希函数的构造方法三、处理冲突的方法四、哈希表的查找五、哈希表的删除操作六、对静态查找表，．．．9.3

哈

希

表一、哈希表是什么？以上两节讨论的表示查找表的各种结构的共同特点：记录在表中的位置和它的关键字之间不存在一个确定的关系，查找的过程为给定值依次和关键字集合中各个关键字进行比较，查找的效率取决于和给定值进行比较的关键字个数。用这类方法表示的查找表，其平均查找长度都不为零。不同的表示方法，其差别仅在于：

关键字和给定值进行比较的顺序不同。对于频繁使用的查找表，希望

ASL

=

0。只有一个办法：预先知道所查关键字在表中的位置，即，要求：记录在表中位置和其关键字之间存在一种确定的关系。例如：为每年招收的1000

名新生建立一张查找表，其关键字为学号，其值的范围为xx000

~

xx999(前两位为年份)。若以下标为000~999

的顺序表表示之。则查找过程可以简单进行：取给定值（学号）的后三位，不需要经过比较便可直接从顺序表中找到待查关键字。但是，对于动态查找表而言，表长不确定；在设计查找表时，只知道关键字所 属范围，而不知道确切的关键字。因此在一般情况下，需在关键字与记录在表中的存储位置之间建立一个函数关系，以f(key)作为关键字为key

的记录在表中的位置，通常称这个函数f(key)为哈希函数。例如：对于如下9

个关键字{Zhao,

Qian,Sun,

Li,

Wu,

Chen,Han,Ye,Dei}ChenDeiHanLiQianSunWuYe

Zhao设哈希函数f(key)=(Ord(第一个字母)-Ord('A')+1)/20

1

2

3

4

5

6

7

8

9

10

1

1

1

2

1

3问题:

若添加关键字

Zhou,怎么办？能否找到另一个哈希函数？从这个例子可见：哈希函数是一个映象，即：将关键字的集合映射到某个地址集合上，它的设置很灵活，只要这个地址集合的

大小不超出允许范围即可；由于哈希函数是一个压缩映象，因此，在一般情况下，很容易产生“冲突”现象，即：

key1„

key2，而

f(key1)

=f(key2)。3)

很难找到一个不产生冲突的哈希函数。一般情况下，只能选择恰当的哈希函数，使冲突尽可能少地产生。因此，在构造这种特殊的“查找表”时，除了需要选择一个“好”(尽可能少产生冲突)的哈希函数之外；还需要找到一种“处理冲突”的方法。哈希表的定义：根据设定的哈希函数H(key)和所选中的处理冲突的方法，将一组关键字映象到一个有限的、地址连续的地址集(区间)上，并以关键字在地址集中的“象”作为相应记录在表中的存储位置，如此构造所得的查找表称之为“哈希表”。二、构造哈希函数的方法对数字的关键字可有下列构造方法：若是非数字关键字，则需先对其进行数字化处理。折叠法除留余数法随机数法直接定址法数字分析法平方取中法1.

直接定址法哈希函数为关键字的线性函数H(key)=key

或者H(key)=a

·

key+b此法仅适合于：地址集合的大小==关键字集合的大小2.

数字分析法假设关键字集合中的每个关键字都是由s位数字组成(u1,u2,…,us)，分析关键字集中的全体，并从中提取分布均匀的若干位或它们的组合作为地址。此方法仅适合于：能预先估计出全体关键字的每一位上各种数字出现的频度。3.

平方取中法以关键字的平方值的中间几位作为存储地址。求“关键字的平方值”的目的是“扩大差别”，同时平方值的中间各位又能受到整个关键字中各位的影响。此方法适合于:关键字中的每一位都有某些数字重复出现频度很高的现象。4.

折叠法将关键字分割成若干部分，然后取它们的叠加和为哈希地址。有两种叠加处理的方法：移位叠加和间界叠加。此方法适合于:关键字的数字位数特别多。5.

除留余数法设定哈希函数为:H(key)

=key

MOD

p其中，

p≤m

(表长)

并且p应为不大于m的最大的素数或是不含20

以下的质因子为什么要对p

加限制？例如：给定一组关键字为：12,

39,

18,

24,

33,

21，若取p=9,则他们对应的哈希函数值将为：

3,3,0,6,6,3可见，若p中含质因子3，则所有含质因子3的关键字均映射到“3的倍数”的地址上，从而增加了“冲突”的可能。6.随机数法设定哈希函数为:H(key)=Random(key)其中，Random

为伪随机函数通常，此方法用于对长度不等的关键字构造哈希函数。实际造表时，采用何种构造哈希函数的方法取决于建表的关键字集合的情况(包括关键字的范围和形态)，总的原则是使产生冲突的可能性降到尽可能地小。190123145568118236811302053例如:

关键字集合{19,

01,

23,

14,

55,

68,

11,

82,

36},表长=11用除留余数法，构造Hash函数。可设Hash函数：H(key)=key

MOD

11keyH(key)三、处理冲突的方法“处理冲突”的实际含义是：为产生冲突的地址寻找下一个哈希地址。1.

开放定址法2.再哈希法3.

链地址法(拉链法）4.建立一个公共溢出区为产生冲突的地址H(key)求得一个地址序列：1≤

s≤m-1H0,

H1,

H2,

…,

Hs其中：H0

=H(key)Hi

=(

H(key)

+

di

)

MODmi=1,2,…,s1.

开放定址法对增量

di

有三种取法：1)

线

性

探

测

再

散

列di

=

c·

i最简单的情况

c=12)

平

方

探

测

再

散

列di

=

12,

-12,

22,

-22,

…,3)

随

机

探

测

再

散

列di

是一组伪随机数列

或者di=i×H2(key)(又称双散列函数探测)例如:

关键字集合{

19,

01,

23,

14,

55,

68,

11,

82,

36

}设定哈希函数H(key)=key

MOD

11(表长=11)78

910若采用线性探测再散列处理冲突550123143682681911012345678910550123146811823619112136251若采用二次探测再散列处理冲突0

1

2

3

4

5

61

1

2

1

2

1

413ASL

=22/9ASL

=16/9H2(key)是另设定的一个哈希函数，它的函数值应和m

互为素数。230168141182551936若m

为素数，则H2(key)可以是1

至m-1之间的任意数；若m为2的幂次，则

H2(key)应是1

至m-1之间的任意奇数。例如，当m=11时，可设di=H2(key)=(3×key)MOD10+10

1

2

3

4

5

6

7

8

9

102

1

1

1

2

1

2

1

32.再哈希法基本思想：当发生冲突时，利用不同的哈希函数

再求得一个新的地址，直到不出现冲突为止，即：Hi=RHi(key)

i=1,2,……，m其中:RHi

为一组不同的哈希函数。当第一次发生冲突时，用RH1计算得到一个新的哈希地址H1

，如果仍然有冲突，又用RH2计算得到一个新的哈希地址H2

，……。依次类推，直到求得某个Hi

不再冲突为止。特点：这种方法一般不会产生“聚集”现象，但需要定义多个不同的哈希函数，并且增加了计算的时间。3.

链地址法

将所有哈希地址相同的记录（拉链法）

都链接在同一链表中。0123456140136198223116855ASL=(6×1+2×2+3)/9=13/9例如:同前例的关键字，哈希函数为

H(key)=key

MOD

74.建立一个公共溢出区基本思想：在基本哈希表以外，另外设立一个溢出表，存放与基本表中记录冲突的所有记录。四、哈希表的查找查找过程和造表过程一致。假设采用开放定址处理冲突，则查找过程为：对于给定值K，计算哈希地址i=H(K)若

r[i]

=

NULL

则查找不成功若

r[i].key

=

K

则查找成功否则“求下一地址Hi”，直至r[Hi]=NULL

(查找不成功)或

r[Hi].key

=

K

(查找成功)

为止。TA[i]

为空？i=H（key)A[i].key==key?i＝下一个哈希存储地址失败成功TFF1.哈希查找法是一种直接计算地址的方法，在查找