数据结构（第2版）（教育部规划）第8章

第8章查找8.1线性表的查找8.2树表的查找8.3哈希表习题

查找表是由同一类型的数据元素(或记录)构成的集合。若在数据元素中存在一个域，该域的值可以标识(识别)惟一的数据元素，则称这个域为关键字。查找是根据给定的值，在查找表中确定一个数据元素(或记录)，该数据元素的关键字域是等于给定的值。若表中存在这样一个记录，则称为查找成功，查找返回的结果为整个记录信息，或指示该记录在查找表中的位置；若表中不存在这样一个记录，则称为查找失败，此时查找返回结果可以给出一个“空”指针。8.1线性表的查找

查找表是一个线性表，其存储结构采用一维数组存放，数组中每个分量对应一个查找表的记录，该记录中有一个域是关键字域，用C语言描述如下:

typedef

struct

{intkey;/*记录的关键字域*/...;/*记录的其他域*/

}NODE;8.1.1顺序查找顺序查找是一种最简单也是最基本的查找方法。查找过程为：从表的一端开始，逐个将记录关键字与给定的值比较，若某个记录的关键字和给定值比较相等，则查找成功；反之，若直至表的另一端，其关键字和给定值比较都不等，则表明表中没有所查记录，查找失败。该过程用C语言描述如下：

算法8.1

顺序查找算法(array[]是表，n是表长，k是给定值)intseq_search(NODE

array[],int

n,intk){inti;

for(i=0;i<n&&array[i].key!=k;i++);

if(i<n)return(i);elsereturn(-1);/*-1为查找失败的标记*/

}

该算法的时间复杂度是O(n)。8.1.2折半查找若查找表是一个线性有序表，先确定待查记录所在的范围，然后逐步缩小范围，直至得到查找结果。折半查找的算法描述如下：

(1)设指针low和hig分别指示待查元素所在范围的下界和上界，指针mid指示区间的中间位置，即：mid=trunc((low+hig)/2)。查找表所对应一维数组为array[]，并按key域递增有序。待查找的值存放在k中。初始时，low=0，hig=N-1。

(2)比较k和array[mid].key，若相等，则查找成功，返回mid，查找结束；反之，则继续判断。若k比array[mid].key小，则k只可能存在array[mid]之前(即查找区间减小为low，hig=mid-1)；若k比array[mid].key大，则k只可能存在array[mid]之后(即查找区间减小为low=mid+1，hig不变)。

(3)重复(2)，直到查找成功，或查找区间不存在(即low>hig)，查找失败。

0

1

2

3

4

5

6

7

8

9

10

05

13

19

21

37

56

64

74

80

88

92

lowmidhig

0

1

2

3

4

5

6

7

8

9

10

05

13

19

21

37

56

64

74

80

88

92

lowmidhig

0

1

2

3

4

5

6

7

8

9

10

05

13

19

21

37

56

64

74

80

92

midlowhig

(a)查找给定值21成功的过程

例如，已知如下11个数据元素的有序表(关键字即为数据元素的值)：

(05,13,19,21,37,56,64,74,80,88,92)现要查找关键字为21和85的数据元素，查找过程如图8.1所示。

0

1

2

3

4

5

6

7

8

9

10

05

13

19

21

37

56

64

74

80

88

92

lowmidhig

0

1

2

3

4

5

6

7

8

9

10

05

13

19

21

37

56

64

74

80

88

92

lowmidhig

0

1

2

3

4

5

6

7

8

9

10

05

13

19

21

37

56

64

74

80

88

92

lowmidhig

0

1

2

3

4

5

6

7

8

9

10

05

13

19

21

37

56

64

74

80

88

92

higlow

(b)查找给定值85失败的过程

根据上面分析，折半查找算法用C语言描述如下：

算法8.2

有序表的折半查找算法。

intbin_search(NODE

array[],int

n,intk)

/*array[]是线性递增有序表，n为查找表长度，k为给定值*/{intlow,hig,mid;low=0,hig=n-1;/*初始化*/

while(low<=hig)/*查找区间存在*/{mid=(low+hig)/2;

if(k==array[mid].key)

return(mid);/*查找成功，返回查找到值的位置*/

if(k<array[mid].key)hig=mid-1;elselow=mid+1;}return(-1);/*查找失败*/}图8.2折半查找所对应的判定树从判定树上可见，查找21过程是走了一条从根到结点③的路径。而与给定值85相等的记录，应在结点⑨的左子树上，但结点⑨的左子树为空，所以查找失败。查找到每个元素需要的比较次数等于该结点在判定树中的深度。查找失败时的比较次数等于此二叉树的深度。这棵判定树的深度为trunc(log2n)+1，所以，折半查找的时间复杂度为O(log2n)。折半查找的过程可用二叉树来描述。树中每个结点表示表中一个记录，结点中的值为该记录在表中的位置，通常称这种描述查找过程的二叉树为判定树。图8.2所示的二叉树，就是图8.1所示查找过程所对应的判定树。8.1.3分块查找分块查找又称为索引顺序查找，这是顺序查找的一种改进方法。在此查找法中，将表中记录分成n(n>1)块。所得到的分块结果是：块内数据元素的关键字是无序的，而块与块之间的数据元素的关键字是有序的，即第i块中关键字的最大值小于第i+1块中关键字的最小值，并以每一块中最大关键字和块的位置建立起索引表。例如，图8.3所示为一个表及其索引表，表中含有18个记录，可分成三个块，每一块有6个记录，并且满足块内的关键字无序，而块与块之间的关键字递增有序。用每个块的最大关键字和指示块中第一个记录在表中位置的指针建立索引表。

2248860

612221213

8

9

20

33

42

44

38

24

48

60

58

74

47

86

53

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17图8.3表及其索引表该数据结构可用C语言描述如下：

typedef

struct

{intkey;/*记录的关键字域*/...;/*记录的其他域*/

}NODE;/*表结点*/

typedef

struct

{intkey,pos;}INDEX;/*索引表结点*/

分块查找的过程需分两步进行。先确定待查记录所在的块，然后在块中顺序查找。假设给定值k=38，则先将k依次在索引表中按顺序比较，因为22<k<48，则关键字为38的记录若存在，必定在第二块中，由索引表结点的指针域可知，第二块的第一个记录是表中下标为6的记录，则自该记录起进行顺序查找，直到array[11]=k为止。若块中没有关键字等于k的记录，则查找失败。分块查找的时间复杂度是O(m+n)。其中，m是块长度，n是索引表长度。8.2树表的查找

查找表是一个二叉树，其存储结构采用二叉链表，链表中每个结点对应查找表一个记录，该记录中有一个域是关键字域，用C语言描述如下：structnode{intkey;/*记录的关键字域*/...;/*记录的其他域*/

structnode*lch,*rch;};8.2.1二叉查找树在第6章树形结构中，已经介绍了二叉排序树。若将查找表用二叉排序树表示，就构成了一棵二叉查找树。设给定值为k，根据二叉排序树的性质，在二叉查找树中进行查找将首先从树根开始比较，若k与根相等，则查找成功；若k比根小，则到左子树找；若k比根大，则到右子树找；直到查找成功，或查找子树为空(查找失败)。若成功，则返回查找到结点的地址；若失败，则返回空指针。查找的非递归算法如下：

算法8.3

二叉排序树中查找的非递归算法。

NODE*search(int

k,NODE*root)

/*在根指针为root的二叉排序树中找关键值为k的结点的地址*/{NODE*p;p=root;

while(p!=NULL){if(p->key==k)return(p);if(p->key>k)p=p->lch;elsep=p->rch;}

return(NULL);}在二叉排序树中进行查找的时间复杂度与树的深度有关，同样一组数据元素，所构造出的二叉排序树是不相同的，最好情况与折半查找类似，时间复杂度为O(log2n)；而最坏情况下，二叉排序树会退化成一个单链表，这时，在二叉排序树中查找相当于顺序查找，时间复杂度为O(n)。(a)最好情况下的二叉排序树(b)退化成单链表的二叉排序树图8.4不同形态的二叉排序树8.2.2二叉平衡树二叉平衡树又称为AVL树，树中每个结点增加了一个平衡因子域bf，该域中的值为结点左子树的深度减去右子树的深度。二叉平衡树(AVL树)定义如下：它或者是一个空树；或具有以下性质：它的左右子树均为二叉平衡树，且左右子树的深度之差的绝对值不超过1。从二叉平衡树的定义可知，二叉平衡树上所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。如图8.5所示为平衡和不平衡二叉树的示例。

因为二叉平衡树上任何结点的左右子树的深度之差都不超过1，则可以证明它的深度和log2n是同一数量级的。由此，在二叉平衡树中查找时间是O(log2n)。所以将二叉排序树构造成一棵平衡树，这样，在二叉排序树中进行查找的时间复杂度就较小。图8.6平衡树的生成过程下面通过一个例子来讨论如何构造平衡的二叉排序树。假设表中关键字序列为(13,24,37,90,53)，构造过程如图8.6所示。

(1)在图8.6(d)中，当二叉树中插入37关键字后，二叉树失去平衡，通过对树作一个逆时针“旋转”的操作，即令结点24为根，而13和37分别它的左右子树，调整后的二叉树为图8.6(e).(2)在图8.6(f)中，当二叉树中插入53关键字后，二叉树失去平衡，这时失去平衡的结点有两个，找与离插入结点最近且失去平衡的结点，将以该结点为根的子树调整成平衡树，要调整的子树是以结点37为根的子树。作了两次“旋转”操作：首先顺时针旋转，如图8.6(g)；然后逆时针旋转，调整后的树如图8.6(h)所示.

根据插入位置不同，失去平衡后进行调整的规律可归纳为以下四种情况（见下页图）：(1)LL旋转平衡：由于在A的左子树的左子树中插入结点，使A的平衡因子由1增至2而失去平衡，需要进行一次顺时针旋转操作，如图8.7(a)所示。旋转操作用C语言描述如下：

b=a->lch；/*b指向是a的左孩子*/a->lch=b->rch；/*a的左指针指向b的右孩子*/b->rch=a；/*a作为b的右孩子*/a->bf=b->bf=0；/*调整后的树以b为根*/(2)RR旋转平衡：由于在A的右孩子的右子树中插入结点，使A的平衡因子由-1增至-2而失去平衡，需要进行一次逆时针旋转操作，如图8.7(b)所示。旋转操作用C语言描述如下：

b=a->rch

；/*b指向是a的右孩子*/

a->rch=b->lch

；/*a的左指针指向b的左孩子*

b->lch=a；/*a作为b的左孩子*/a->bf=b->bf=0；/*调整后的树以b为根*/(3)LR旋转平衡：由于在A的左孩子的右子树中插入结点，使A的平衡因子由1增至2而失去平衡，需要进行两次旋转操作(先逆时针、后顺时针)，如图8.7(c)所示。旋转操作用C语言描述如下：

b=a->lch；c=b->rch；/*b指向是a的左孩子，而c指向是b的右孩子*/a->lch=c->rch；/*a的左指针指向c的右孩子*/b->rch=c->lch；/*b的右指针指向c的左孩子*/c->rch=a；/*c的右指针指向a*/c->lch=b；/*c的左指针指向b，c为调整后子树的根*/(4)RL旋转平衡：由于在A的右孩子的左子树中插入结点，使A的平衡因子由-1增至-2而失去平衡，需要进行两次旋转操作(先顺时针、后逆时针)，如图8.7(d)所示。旋转操作用C语言描述如下：

b=a->rch；c=b->lch；

a->rch=c->lch；

b->lch=c->rch；

c->lch=a；

c->rch=b；在LR型和RL型旋转平衡中，平衡因子的变化如下：switchc->bf/*插入前c->bf为0，插入后有三种情况*/{case1:/*在c的左子树上插入结点*/a->bf=-1;b->bf=0;break;case-1:/*在c的右子树上插入结点*/a->bf=0;b->bf=-1;break;case0/*c本身为插入的新结点*/a->bf=0;b->bf=0;break;}

由图8.6中的例子可见，平衡旋转是当排序树在插入结点后产生不平衡时进行的，并且由于失去平衡的结点可能有多个，所以是找离插入结点最近的失去平衡的结点。而对在插入后失去平衡的结点，该结点在插入前的平衡因子的绝对值一定大于零。在一个平衡的排序树中插入结点s，需要注意以下几点：

(1)在查找s结点的插入位置的过程中，记下离插入结点最近且平衡因子不等于0的结点，令指针a指向该结点。

(2)修改自a至s路径上所有结点的平衡因子。

(3)判别以a为根的子树是否失去平衡。若是，则需要判别旋转类型并作相应的处理，否则插入结束。在一棵二叉排序树中插入一个结点的具体算法省略。8.2.3B_树(1)B_树及其定义一棵m阶的B_树，或是空树，或是满足以下条件的m叉树:(1)树中每个结点至多有m棵子树(树的度=m)。

(2)若根结点不是叶子结点，则至少有二棵子树。

(3)除根外的所有非终端结点至少有int(m/2)棵子树(注：int函数为上取整函数)。

(4)所有结点包含信息：(n,A0,K1,A1,…,Kn,An)，其中Ki为关键字且有序(Ki<Ki+1)，Ai为指向子树根结点的指针，Ai所指子树中所有结点的关键字均小于Ki+1，An所指子树中所有结点的关键字均大于Kn。

(5)所有叶子结点都出现在同一层次上，即：所有为空的指针出现在同一层上。

n

A0

K1

A1

…

…

Kn

An图8.8一个含有n个关键字的B-树结点的结构图8.9一棵4阶的B-树(2)B-树的操作对B-树的操作主要有查找、插入、删除等。

(a)查找。由B-树的定义可知，在B-树上进行查找的过程和二叉排序树的查找类似。假设要查找关键字为k的记录，首先从根结点开始，若找到k，就找到k所对应的记录，算法结束，否则沿着p所指的子树继续查找，p由下式确定：

A0k<K1p=Ank<KnAiKi<k<Ki+1

若直到叶子结点还未找到，则查找失败。

(b)插入。设要插入关键字为k的记录，它包含关键值k和指向k所在记录的指针p，(k,p)称为插入项，则插入过程如下:

首先进行查找操作，找到k应插入的叶子结点，将k和p插入。然后，判断被插入结点是否满足m叉B-树的定义，即插入后结点的分支数是否大于m(结点的关键字数是否大于m-1)，若不大于m，则插入结束；否则，要把该结点分裂成两个。分裂的方法是：申请一个新结点，由指针p’指向，将插入后的结点按照关键字的值大小分成左、中、右三部分，中间只含有一项，左右数量相等或相差1；左边的留在原结点中，右边的移入新结点，中间的一个关键值k’和指向新结点的指针p，(k’,p’)构成一个新的插入项，插入到它们的双亲结点中，若双亲结点在插入后也需要分裂，则在分裂后再往上插入，递归地进行下去，直到某个结点在插入后无须再分裂，或者分裂产生新树根为止。图8.10在B-树中进行插入(c)删除要删除关键字为k的记录，仍要以查找为先导，若查找失败则出错(不能删除不存在的记录)，否则分两种情况删除(删除项是k以及指向k所在记录的指针p)：第一种，删除项在叶结点中。若删除后剩余关键字数不小于int(m/2)-1，则直接删除即可；若删除后剩余关键字数等于int(m/2)-1，则分两种情况。①若与该结点相邻接的右兄弟(或左兄弟)结点中的关键字数大于int(m/2)-1，则需将其兄弟结点中的最小(或最大)的关键字上移双亲结点中，而将双亲结点中小于(或大于)该上移关键字的关键字下移至被删关键字所在结点中。例如，在图8.11(a)中删除50，需将其右兄弟结点中的最小关键字61上移至双亲，而将双亲中53下移至删除结点中，如图8.11(b)所示。②若与该结点相邻接的右兄弟(或左兄弟)结点中的关键字数均等于int(m/2)-1。假设该结点有右兄弟(由Ai指向)，则在删除关键字后，将剩余的关键字和指针，加上双亲结点中的关键字Ki一起，合并到右兄弟中。例如，在图8.11(b)中删除70，将删除后的剩余信息和双亲中的90一起合并到右兄弟中，如图8.11(c)所示。第二种，删除项在非终端结点中。假若所删除关键字为非终端结点中的Ki，则可以指针Ai所指子树中的最小关键字s代替Ki，然后在相应的叶子结点中删除s，这样就变成第一种情况。例如，在如图8.11(b)所示的B-树中删除45，可以用叶子结点中的50替代45，然后在叶子结点中删除50。图8.11在B-树中删除关键字的情况8.3哈希表8.3.1哈希表的定义在前面讨论的各种结构(线性表、树表)中，记录在结构中的相对位置是随机的，它与记录的关键字之间不存在确定的关系，因此，在结构中查找记录时需要进行一系列关键字的比较。这一类查找是建立在比较的基础上。能否通过对待查记录关键值(查找值)的计算，直接得到待查记录的存放地址？即在记录的存储地址和查找值之间建立一个确定的对应关系，使每一个查找值与结构中唯一的存储地址对应，并能通过查找值，直接找到对应记录的地址，这就是哈希表的方法。例如，在线性表中按记录号查找，只要知道第一个记录的存储地址，并知道每个记录所占存储单元数，那么，每给一个要查找的记录号，就可以得到要查找记录的地址。哈希函数：这种在记录的存储地址和查找值之间所建立的对应关系，称为哈希函数。哈希表：按某个哈希表函数值来存放各个记录，所形成的数据集合，称为哈希(hash)表。为保证哈希表查找得以实现，必须使记录的存放规则和查找规则一致，即：使用同样的哈希函数。在存储时，以每个记录的关键字为自变量，通过哈希函数计算出存储地址，将该记录存放在存储地址所对应的存储单元中。在查找时，以查找值为自变量，通过哈希函数计算出地址，从该地址所对应的存储单元中取出记录数据。

冲突：在存储哈希表时会遇到这样情况，即两个记录的关键字不等，但它们的哈希函数的值相同(两个记录对应的存储地址相同)，称为冲突。

同义词：具有相同函数值的关键字被称为同义词。8.3.2哈希函数的构造构造哈希函数的方法很多。一个好的哈希函数，其值应该是均匀分布在整个地址空间中，并且冲突次数少。常用的构造哈希函数的方法有以下几种：(1)直接定址法直接取关键字的某个线性函数值作为哈希地址。即：

H(key)=key或H(key)=a*key+b其中a和b为常数(这种哈希函数叫做自身函数)。例如，有一个建国后出生的人口调查表，关键字是年份，哈希函数取关键字加一个常数：

H(key)=key+(-1949)如表8.1所示（见下一页）表8.1直接定地址哈希函数示例地址

00

01

02

03

…

21

…年份

949

950

1951

952

…

1970

…人数

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

这样，若要查找1970年出生的人数，则只要查找第(1970-1949)=21项即可(2)数字分析法假设关键字是以r为基的数(如：以10为基的十进制数)，并且哈希表中可能出现的关键字都是事先知道的，则可取关键字的若干数位组成哈希表。例如，有80个记录，其关键字为8位十进制数。假设哈希表的表长为100，则可取两位十进制数组成哈希地址。取数的原则是使得到的哈希地址尽量避免冲突，则需从这80个关键字着手。假设这80个关键字中的一部分如下：见下一页对关键字全体的分析中我们发现：①②③位都是“993”，第⑧位只可取2、3、7，因此这四位都不可取。由于中间的四位可看成随机的，因此可以取其中任意两位作为哈希地址。…99346532993722429938743399301367993228179933896799354157993541579936853799368532…①②③④⑤⑥⑦⑧(3)除留余数法将关键字值除以一个整数后所得的余数作为哈希地址，该整数p不大于哈希表表长m，可以保证哈希函数的值在有效的地址空间之内。即

H(key)=keyMODpp≤m这是一种最简单，也是最常用的构造哈希函数的方法。但要注意对p的选择，若选择不好，容易产生同义词。p一般选质数。(4)平方取中法计算关键字值的平方，取中间若干位作为哈希地址。例如，在如图8.12所示的一个长度为1000哈希表中的4个关键字，将它们平方后取中间的三位作为哈希函数的值。记录关键字关键字平方哈希地址

1

11052501

22157778355001

778

2

11052502122157800460004

800

3

01110525001233265775625

256

4

02110525004454315775625

315图8.12平方取中法(5)折叠法和移位法如关键字的位数比地址码的位数多，而且各位数字的分布较均匀，则可考虑用折叠法和移位法。

(a)折叠法：将关键字值分成位数相同的几部分，然后折叠相加作为哈希地址。例如，关键字为326348725，按每三位数分成一段，左边的326向右折叠为623，右边的725向左折叠为527，三部分相加得：623+348+527=1493

当记录数不到10000时，哈希地址取1493；若记录数不到1000时，哈希地址可以取493。

(b)移位法：将关键字值分成位数相同的几部分，然后移位相加作为哈希地址。例如，关键字为326348725，按每三位数分成一段，左边的326向右移，右边的725向左移，三部分相加得：326+348+725=1399

同样，当记录数不到10000时，哈希地址取1399；若记录数不到1000时，哈希地址可以取399。(6)随机法选择一个随机函数，取关键字的随机函数值为它的哈希地址，即：H(key)=random(key)random()不能是一般的随机函数，固定的参数必须返回确定的值。实际工作中需视不同的情况采用不同的哈希函数，通常考虑的因素有：

(1)计算哈希函数的效率。

(2)关键字的长度。

(3)哈希表的大小。

(4)关键字的分布情况。

(5)记录的查找频率。一般说，实际中的哈希表，会多开辟一些空间(如5%～10%)，以避免冲突。8.3.3冲突处理方法在实际应用中，很难有绝对一一对应的规则，冲突总是存在。因此，如何处理冲突是哈希表不可缺少的另一方面。(1)开放地址法当冲突发生时，形成一个地址序列，沿该序列逐个探测，直到找出一个“空”的开放地址(只要哈希表不满)，将发生冲突的关键字值存于此间:Hi=(H(key)+di)MODm(i=1,2,…,m-1)

其中，H(key)为哈希函数；m为哈希表长；di是增量序列。根据di的取法，又分为：

(1)线性探测法。di=1,2,…,m-1，称线性探测再散列。即某地址冲突后，依次探测后续地址单元，直至所有空间中无“空”单元时，才真正溢出。

(2)二次方探测法。di=12,-12,22,-22,…,-k2，(k≤m/2)称二次探测再散列。

(3)伪随机探测法。di=伪随机数序列，称伪随机数再散列。例如，在长度为11的哈希表中已填有关键字17,60,29的记录(哈希函数H(