tceic.com
简单学习网 让学习变简单
当前位置:首页 >> 学科竞赛 >>

第九章查找


第9章 查找
9.1 基本概念
查找:给定一个值K,在含有 n 个结点的表 (或文件)中找出关键字等于给定值K的结点, 若找到,则查找成功,输出该结点在表中的位 置;则查找败的信息。

查找有内查找和外查找之分。 内查找:若整个查找过程都在内存进行,则称之为内查找。 外查找:若查找过程中需要访问外存,则称之为外查找。 查找算法的评价: 通

常把查找过程中对关键字需要执行的平均比较次数(也称 为平均查找长度)作为衡量一个查找算法效率优劣的标准。平 均查找长度ASL定义为: n ASL=∑pici; i=1 其中,n是结点的个数,pi是查找第i个结点的概率,若不 特殊声明,均认为每个结点的查找概率相等,ci是找到第i个结点 所需要的比较次数。

显然,ASL值越小,时间效率越高。

9.2 线性表的查找
9.2.1 顺序查找
基本思想: 从表的一端开始,顺序扫描线性表,依次将 扫描到的结点关键字和给定值K相比较,若当前 扫描到的结点关键字与K相等,则查找成功;若 扫描结束后,未找到关键字等于K的结点,则查 找失败。

顺序查找方法既适用于线性表的顺序存储结构,也适用 于线性表的链式存储结构 。在等概率假设下, 顺序查找的 平均查找长度为: 查找第1个元素所需的比较次数为1; 查找第2个元素所需的比较次数为2; …… 查找第n个元素所需的比较次数为n; 总计全部比较次数为:1+2+…+n = (1+n)n/2 若求某一个元素的平均查找次数,还应当除以n(等概率), 即: ASL=(1+n)/2 ,时间效率为 O(n)

顺序查找的优点是算法简单,且对表的结构无 任何要求,无论是用向量还是用链表来存放结 点,也无论结点之间是否按关键字有序,它都 同样适用。 顺序查找的缺点是查找效率低,因此,当n较 大时,不宜采用顺序查找。

9.2.2 二分查找
二分查找又称折半查找,它是一种效率较高的 查找方法。但是,二分查找要求线性表是有序表, 即表中结点按关键字有序,并且要用向量作为表的 存储结构。

基本思想:
首先将待查的K值和有序表R[1]到R[n]的中间位置mid 上的结点的关键字进行比较,若相等,则查找完成;否则, 若R[mid].key>K,则说明待查找的结点只可能在左子表R[1] 到R[mid-1]中,在左子表中继续进行二分查找;若 R[mid].key<K,则说明待查找的结点只可能在右子表 R[mid+1]到R[n]中,在右子表中继续进行二分查找。这样, 经过一次关键字比较就缩小一半的查找区间。如此进行下 去,直到找到关键字为K的结点,或者当前的查找区间为 空(表示查找失败)。

例:假设被查找的有序表中关键字序列为:
05,13,19,21,37,56,64,75,80,88,92
当给定的K值分别为21和85时,进行二分查找的过程如图:

[05 13 19 21 37 56 64 75 80 88 92] [05 13 19 21 37] 56 64 75 80 88 92 05 13 19 [21 37] 56 64 75 80 88 92

(a)

查找K=21的过程

[05 13 19 21 37 56 64 75 80 88 92]

05 13 19 21 37 56 [64 75 80 88 92]
05 13 19 21 37 56 64 75 80 [88 92]

05 13 19 21 37 56 64 75 80
(b) 查找K=85的过程

88 92

其算法可描述如下:
Procedure BinarySearch(low:integer;high:integer;var i:integer); var mid:integer; begin if x<a[low] or x>a[high] then exit;{如果x不在表的范围内,直接 退出} while low<=high do{当表中还有元素} begin mid:=(low+high) div 2;{将表分成大致相同的两半} if x=a[mid] then{如果x=a[n div 2],则找到x,算法结束} begin i:=mid; exit; end else if x<a[mid] then high:=mid-1 {如果x<a[n div 2],则在表A的左半部分继续搜索} else low:=mid+1; {如果x>a[n div 2], 则在表A的右半部分继续搜索} end; {while} end;

也可以写成递归算法:
Procedure BinarySearch(low:integer;high:integer;var i:integer); var mid:integer; begin if x<a[low] or x>a[high] then exit; {如果x不在表的范围内,直接退出} if low>high then i:=0 else begin mid:=(low+high) div 2;{将表分成大致相同的两半} if x=a[mid] then {取a[n div 2]与x做比较} begin i:=mid; exit; end {如果x=a[n div 2],则找到x,算法结束} else if x<a[mid] then begin high:=mid-1;BinarySearch(low,high,i) end {如果x<a[n div 2],则在表A的左半部分继续搜索} else begin low:=mid+1; BinarySearch(low,high,i) end {如果x>a[n div 2], 则在表的右半部分继续搜索} end; {else} end;

二分查找过程可用二叉树描述,我们把当前查找区间的 中间位置上的结点作为根,左子表和右子表中的结点分别作为 根的左子树和右子树,由此得到的二叉树,称为描述二分查找 的判定树。

例如:上述具有11个结点的有序表用判定树表示如下:

图9.1 描述折半查找过程的判定树及查找21的过程

讨论① 若关键字不在表中,怎样得知和停止?
——典型标志是:当查找范围的上界≤下界时停止查找。 讨论② 推 导 过 程 二分查找的效率(ASL)
1次比较就查找成功的元素有1个(20),即中间值; 2次比较就查找成功的元素有2个(21),即1/4处(或3/4)处; 3次比较就查找成功的元素有4个(22),即1/8处(或3/8)处… 4次比较就查找成功的元素有8个(23),即1/16处(或3/16)处… …… 则第m次比较时查找成功的元素会有(2m-1)个; 为方便起见,假设表中全部n个元素= 2m-1个,此时就不讨论第m 次比较后还有剩余元素的情况了。

全部比较总次数为1×20+2×21+3×22+4×23…+m×2m—1 m = j ? 2 j ?1

?
j ?1

平均每个数据的查找时间还要除以n,所以:
1 ASL ? n

? j?2
j ?1

m

j ?1

n ?1 ? log2 ( n ? 1) ? 1 ? log2 n n

课堂练习(多项选择):
使用折半查找算法时,要求被查文件: A.采用链式存贮结构 B.记录的长度≤128 C.采用顺序存贮结构 D.记录按关键字递增有序

√ √

思考:假设在有序线性表a[20]上进行折半查找,则
平均查找长度为 。

总结:

二分查找的效率高,但是要将表按关键字排序。 二分查找只适用顺序存储结构,为保持表的有序性, 在顺序结构里插入和删除都必须移动大量的结点。 因此二分查找特别适用于一经建立就很少改动、而 又经常需要查找的线性表。对查找少而又经常需要 改动的线性表,可采用链表作存储结构,进行顺序 查找。

9.3 树表的查找
树表的引入:当表的插入或删除操作频繁 时,为维护表的有序性,势必要移动表中很多 结点。这种由移动结点引起的额外时间开销, 就会抵消二分查找的优点。在这种情况下,可 采用特殊的树或二叉树作为表的一种组织方式, 在此将它们统称为树表。

二叉排序树
二叉排序树的概念 :
二叉排序树或者是一棵空树,或者是具有如 下性质的二叉树: (1)若它的左子树非空,则左子树上所有结点 的值均小于根结点的值;

(2)若它的右子树非空,则右子树上所有结点
的值均大于根结点的值; (3)左、右子树本身又各是一棵二叉排序树。

二叉排序的重要性质:按中序遍历该树所得到 的中序序列是一个递增有序序列。
例:下图所示的树是二叉排序树,若中序遍历下图所 示的二叉排序树,则可得有序序列为: 3,12,24,37,45,53,61,78,90,100。

45

12
3 37

53
100

24

61
90

78

使用二叉链表作为存储结构,结点结构说明如下:
type bitreptr=^bnodetp bnodetp=record key:keytype; {值域} l,r,p:bitreptr; {左子树域、右右子树域和父结点域} end; var bst,p,f:bitreptr;

将数据元素构造成二叉排序树的优点: ① 查找过程与顺序结构有序表中的折半查找相似,查找效率高; ② 中序遍历此二叉树,将会得到一个关键字的有序序列(即实 现了排序运算); ③ 如果查找不成功,能够方便地将被查元素插入到二叉树的叶 子结点上,而且插入或删除时只需修改指针而不需移动元素。

——这种既查找又插入的过程称为动态查找。 二叉排序树既有类似于折半查找的特性,又采用了链表存储, 它是动态查找表的一种适宜表示。 注:若数据元素的输入顺序不同,则得到的二叉排序树形态 也不同!

讨论1:二叉排序树的插入和查找操作
例:输入待查找的关键字序列=(45,24,53,45,12,24,90) 查 找 成 功, 返 回

则生成二叉排序 树的过程为:
24 12

45 53 90

查 找 成 功, 返 回

如果待查找的关键字序列输入顺序为: (24,53, 45,45,12,24,90), 则生成的二叉排 查 序树形态不同: 找
查 找 成 功, 返 回
24 12 45 53 90

成 功, 返 回

二叉排序树的查找&插入算法如何实现?

静态查找算法
查找算法 动态查找算法 (插入)

二叉排序 树的静态查找思想
若二叉排序树为空,则查找 失败,否则,先拿根结 点值与待查值进行比较,若相等,则查找成功,若根 结点值大于待查值,则进入左子树重复此步骤,否则, 进入右子树重复此步骤,若在查找过程中遇到二叉排 序树的叶子结点时,还没有找到待查结点,则查找不 成功。

function bstsrch(t:bitreptr;k:keytype):bitreptr; {在指针t所指的二叉排序树上查找其关键字等于给定值k的记录,当查找成功 时,返回指向该记录结点的指针,否则返回空指针} begin if (t=nil) or (t^.key=k) then bstsrch:=t {查找成功返回该结点指 针,否则返回空指针} else if t^.key<k then bstsrch:=bstsrch(t^.l,k){在左子树上继续 查找} else bstsrch:=bstsrch(t^.r,k){在右子树上继续查找} end;

可以把这个函数写成非递归的形式,在一般情况下, 这种非递归要更有效些。
function bintree_search(t:bitreptr;k:keytype):bittreptr; begin while (t<>nil)and (k<>t^.key) do if k<t^.key then t:=t^.l{在左子树上继续查找} else t:=t^.r {在右子树上继续查找} bintree_search:=t;{查找成功返回该结点指针,否则返回空指针} end;

例如:在图9.2所示的二叉排序树中查找关键字等于100的记 录。首先以K(100)和根结点的关键字作比较,因为K>45,则 查找以45为根的右子树,此时右子树不空,且K>53,则继续 查找以结点53为根的右子树,由于K和53的右子树根的关键字 100相等,则查找成功,返回指向结点100的指针值。又如查找 关键字等于40的记录,和上述过程类似,在给定值K与关健字 45、12及37相继比较之后,继续查找以结点37为根的右子树, 此时右子树为空,则说明该树中没有待查记录,故查找不成功 ,返回指针值为“NIL”。

在排序二叉树上,其最小值和最大值分别在排序二叉树的左 子树和右子树上。
function minnum_bstree(bst:bitreptr):integer;{查找排序二叉树中 最小的值} begin while bst^.l<>nil do bst:=bst^.l;{在左子树上继续查找} minnum_bstree:=bst^.key end; function maxnum_bstree(bst:bitreptr):integer;{查找排序二叉树中 最大的值} begin while bst^.r<>nil do bst:=bst^.r;{在右子树上继续查找} maxnum_bstree:=bst^.key end;

在实际应用中寻找一个结点的后继结点算法也很重要。由二 叉排序树中序遍历的性质,我们可知,一个结点x后继,如果结 点x有右子树,则x的后继一定是它的右子树上的最小值,例如 图9.3中的结点15,后继是17。如果结点x没有右子树且存在后 继结点y,则结点x的后继y是它最近的祖先,并且y的左孩子也 是x的祖先。只要从结点x开始向上寻找后继结点,直到找到一 个结点是其父结点的左孩子结点,则后继y是就是其父结点。例 如下图中的结点13,其后继结点是15。

图9.3 后继结点示例

function successor_bstree(x:bitreptr):bitreptr;{查找结点x的后继 } begin if x^.r<>nil {存在右子树,则后继是右子树的最小值} then successor_bstree:=minnum_bstree(x^.r) else begin f:=x^.p;{f是该结点的父结点} while (f<>nil) and (x=f^.r) do {当父结点存在并且当前结点是 父结点的右孩子} begin x:=f;{用父结点替换当前结点} f:=f^.p {用父结点的父结点替换父结点} end; successor_bstree:=f {返回父结点,即后继结点} end; end;

二叉排序树的插入 二叉排序树是一种动态树表。其特点是,树的结 构通常不是一次生成的,而是在查找过程中,当树 中不存在关键字等于给定值的结点时再进行插入, 插入的原则是:若二叉排序树为空,则插入结点应 为新的根结点,否则继续在其左子树或右子树上查 找。直到某个结点的左子树或右子树空为止,则插 入结点应作为一个新的叶结点并成为该结点的左孩 子或右孩子,为了在查找不成功时返回插入位置, 首先要将上边查找算法改动一下:

function srch_bstree(bst:bitreptr;k:keytype;var found:boolean):bitreptr; {在根指针bst的二叉排序树上查找其关键字等于给定值k的记录,若存在,则found为 “真”,返回指向该记录节点的指针;否则found为“假”,并返回指向查找路径上最后一 个结点的指针} begin if bst=nil then begin found:=false;srch_bstree:=bst end { 查找不成功,返回flase} else if bst^.key=k then begin found:=true;srch_bstree:=bst end{查找成功,返回true} else if k<bst^.key {继续在左右子树上查找} then srch_bstree:=srch_bstree(bst^.l,k,found) else srch_bstree:=srch_bstree(bst^.r,k,found) end;

则插入新结点过程的算法可描述为:
procedure ins_bstree(var bst:bireptr;k:keytype); {在根指针为bst的二叉排序树上插入关键字为k的结点} var x:bitreptr; begin p:=srch_bstree(bst,k,found); if found then writeln(p^.key:5,' key has in the bstree') else begin f:=nil;{父结点指针} x:=bst; while x<>nil do {找插入结点的位置} begin f:=x;{记录父结点指针} if k<x^.key{在左右子树中寻找插入位置} then x:=x^.l else x:=x^.r end; new(s);s^.key:=k;{动态申请一个指针} s^.l:=nil; s^.r:=nil; s^.p:=f;{f是结点k的父结点} if f=nil then bst:=s{排序二叉树为空} else if k<f^.key{确定k是f左右子树} then f^.l:=s else f^.r:=s end; end;

例:在图(a)所示的二叉排序树插入关键字为58 的结点的过程,如图所示

45
12 3 24 58 37 61 90 78 53 100

如果从空树出发,经过一系列的查找插入操作之后,可生成 一棵二叉树。 例:设关键字的输入次序为:45,24,53,12,24,90 , 按上述算法生成的二叉排序树的过程,过程如图9.5所示。

图9.5 二叉排序树的构造过程

设关键字的输入次序为:45,24,53,12,28,90 ,按上述算 法生成的二叉排序树的过程,如图所示。
45 45

45
(a)空树 (b)插入45

24
(c)插入24

24

53

(d)插入53

45

45

45

24
12

53
12

24
28

53
12

24
28

53
90

(e)插入12

(f)插入28

(g)插入90

容易看出,中序遍历二叉排序树可得到一个关键 字的有序序列(这个性质是由二又排序树的定义决定 的)。这就是说,一个无序序列可以通过构造一棵二 叉排序树而变成一个有序序列,构造树的过程即为对 无序序列进行排序的过程。 不仅如此,从上面的插入过程还可以看到,每次 插入的新结点都是二叉排序树上新的叶子结点,则在 进行插入操作时,不必移动其它结点,仅需改动某个 结点的指针。由空变为非空即可。这就相当于在一个 有序序列上插入—个记录而不需要移动其它记录。它 表明,二叉排序树既拥有类似于折半查找的特性、又 采用了链表作存储结构,因此是动态查找表的 一种适宜表示。

3. 二叉排序树的删除

从二叉排序树中删除一个结点,不能把以该 结点为根的子树都删掉,只能删除该个结点,并 且还要保证删除后所得的二叉树仍然满足二叉排 序树的性质。也就是说,在二叉排序树中删去一 个结点相当于删去有序序列中的一个结点。

假设在二叉排序树上被删去的结点为z(指向结点的指针为z ),下面分三种情况进行讨论: (1)若z为叶子结点,即左右子树均为空。则直接删去叶子 结点,不破坏整棵树的结构。如图9.6(a)所示。

图9.6 在二叉排序树中删除结点示例

(2)若z结点只有左子树或只有右子树。此时只要令z的左 右子树的根结点直接成为其父结点的左右子树即可。显然修 改并不破坏二叉树的特性。如 图9.6(b)所示。

图9.6 在二叉排序树中删除结点示例

(3)若z结点的左右子树均不空。则令z的直接后继(或 直接前驱)替代z,然后在从二叉排序树中删去它的直接后 继(或直接前驱),如图9.6(c)所示。

图9.6 在二叉排序树中删除结点示例

综合上述三种情况,二叉排序树上删除一个结点的 完整算法可描述如下:
procedure delete_bstree(var bst:bitreptr;z:bitreptr;k:integer); {从根指针为bst的二叉排序树上删除结点k,它的指针为z} var x:bitreptr; begin z:=srch_bstree(bst,k,found);{找到结点k的位置} if not found then begin writeln(‘the key is not here’); exit end;{没找到,退 出} if (z^.l=nil) or (z^.r=nil){结点z最多只有左子树或右子树} then y:=z {结点y为要删除的结点z} else y:=successor_bstree(bst);{左右子树都不为空,y为z的后继结点} if y^.l<>nil {x为y的非空子结点,如果y没有子结点x为nil} then x:=y^.l else x:=y^.r; if x<>nil{x非空,表示结点y有子结点} then x^.p:=y^.p; if y^.p=nil{y是根结点} then bst:=x {删除的是根结点,x作为新的根结点} else if y=y^.p^.l{如果y是它父结点的左孩子} then y^.p^.l:=x{把x替换成它父结点的左孩子} else y^.p^.r:=x;{否则把x替换成它父结点的右孩子} if y<>z then z^.key:=y^.key;{把结点z用y替换} end;

二叉排序树的查找分析
从前述的两个查找例子〔K=l00和K=40)可见 ,在二叉排序树上查找其关键字等于给定值的结 点的过程,恰是走了一条从根结点到该结点的路 径的过程,和给定值比较的关键字个数等于路径 长度加1(或结点所在层次数),因此,和折半查找 类似,与给定值比较的关键字个数不超过树的深 度。然而,折半查找长度为n的表的判定树是唯一 的,而含有n个结点的二叉排序树却不唯一。

例如:图9.7中(a)和(b)的两棵二叉排序树中结点的 值都相同,但前者由关键字序列(45,34,53,l2, 37,93)构成,而后者由关键字序列(12,24,37, 45,53,93)构成。(a)树的深度为3,而(b)树的深度 为6。

图9.7 不同形态的二叉查找树

再从平均查找长度来看,假设6个记录的查找概率相 等,为1/6,则(a)树的平均查找长度为: ASL(a)=1/6(1+2+2+3+3+3)=14/6 (b)树的平均查找长度为: ASL(b)=1/6(1+2+3+4+5+6)=21/6 因此,含有n个结点的二叉排序树的平均查找长度 和树的形态有关。当先后插入的关键字有序时,构成 的二叉排序树蜕变为单支树。树的深度为n,其平均 查找长度为n+1/2(和顺序查找相同),这是最差的情况 。显然,最好的情况是二叉排序树的形态和折半查找 的判定树相同。其平均查找长度和log2n成正比。

小结
与二分查找类似,和关键字比较的次数不超过 树的深度。二分查找法平均查找长度也是O(log2n)。 然而,二分查找法查找长度为n的有序表,其判定 树是唯一的,而含有n个结点的二叉排序树却不唯 一。

就平均性能而言,二叉排序树上的查找和二分 查找相差不大,并且二叉排序树上的插入和删除结 点十分方便,无须移动大量结点。因此,对于需要 经常做插入、删除和查找运算的表,宜采用二叉排 序树结构。

9.4 散列表的查找
什么是散列表 在前面讨论的各种结构(线性表、树等)中,记录在结 构中的相对位置是随机的,记录的关键字之间不存在 确定的关系,因此,在结构中查找记录时需进行一系 列和关键字的比较。这一类查找方法建立在“比较” 的基础上。在顺序查找时,比较的结果为“=”与 “≠”两种可能;在折半查找、二叉排序树查找时,比 较的结果为“<”、“=”和“>”三种可能。查找 的效率依赖于查找过程中所进行的比较次数。

理想的情况是希望不经过任何比较,—次存取便能 得到所查记录,那就必须在记录的存储位置和它的关 键字之间建立一个确定的对应关系h,使每个关键字 和结构中一个唯一的存储位置相对应。因而在查找时 ,只要根据这个对应关系h找到给定值K的映像h(K) 。若结构中存在关键字和K相等的记录,则必定在 h(K)的存储位置上,由此,不需要进行比较便可直接 取得所查记录。在此,我们称这个对应关系h为散列 函数,h(K)称为散列地址,按这个思想建立的表为散列 表。

散列是一种重要的存储方式,它的基本思想是以关键 码的值为自变量,通过一定的函数关系(散列函数) ,计算出对应的函数值来,把这个值解释为结点的存 储地址,将结点存入地址为该函值的存储单元里去, 检索时再根据要检索的关键码用同样的函数计算地址 ,然后到相应的单元里去取要找的结点。所以又称关 键码—地址转换法。在散列表里可以对结点进行快速 检索。 通常散列表的存储空间是一个一维数组,散列地址 是数组的下标,在不致于混淆之处,我们将这个一维 数组空间就简称为散列表

例如,已知一个有10个结点的线性表,其关键字都是数字组 成,则可将此线性表存储在如下说明的散列中。 4 6 8 14 23 26 55 50 63 其中散列函数为:h(key)=key mod p p=13,HT1[h(key)]为 关键字key的存储地址。

HT 1

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

26

14

55

4

6

8

23

50

63

由上面的例子可知: (1) 在建立散列表时,若散列函数是一个一对一的函数,则 在查找时,只需根据散列函数对给定值进行某种运算,即可得 到待查结点的存储位置。因此,查找过程无须进行关键字比较 。 (2) 在一般情况下,散列表的空间必须比结点集合大,此时 虽然浪费了一定的空间,但换取的是查找效率。设散列表空间 大小为m,填入表中的结点数是n,则称α=n/m为散列表的装填因 子。 装填因子的大小对于碰撞的发生频率影响很大。直观上容易 想象,散列表装得越满,则再要载入新的结点时碰上已有结点 的可能性越大。特别当α>1时碰撞是不可避免的。一般总是取α <1,即分配给散列表的基本区域大于所有结点所需要的空间。 当然分配的基本区域太大了也是浪费的。一般取α=0.75左右。

(3) 散列函数的选取原则是:运算应尽可能简单;函数 的值域必须在表长的范围之内;尽可能使得关键字不同 时,其散列函数值亦不相同。 (4) 若某个散列函数f对于不相等的关键字key1和 key2得到相同的散列地址(即f(key1)=f(key2)),则将该现 象称为冲突。而发生冲突的这两个关键字则称为该散 列函数H的同义词。

散列函数的构造方法 构造散列函数的方法很多。在介绍各种方法之前, 首先需要明确什么是“好”的散列函数。若对于关键 字集合中的任一个关键字,经散列函数映象到地址集 合中任何一个地址的概率是相等的,则称此类散列函 数为均匀散列函数。换句话说,就是使关键字经过散 列函数得到一个“随机的地址”,以便使一组关键字 的散列地址均匀分布在整个地址区间中,从而减少冲 突。 常用的构造哈希函数的方法有:

数字选择法: 若事先知道关键字集合,且关键字的位数比散列 表的地址位数多,则可选取数字分布比较均匀的若 干位作为散列地址。 例:有一组由8位数字组成的关键字。如表左边 一列表示: 关键字 散列地址1(0~999) 87142653 465 87172232 723 87182745 874 87107136 013 87127281 228 87137394 339

平方取中法: 通常,要预先估计关键字的数字分布并不容易,要 找数字均匀分布的位数则更难。例如,下列一组关键 字(0100,0110,1010,1001,0111)就无法使用数字选择法 得到较均匀的散列函数。此时可采用平方取中法,即 先通过求关键字的平方值扩大差别,然后,再取中间 的几位或其组合作为散列地址 例如,上述一组关键字的平方结果是 :(0010000,0012100,1020100,1002001,0012321)若表长 为1000,则可取中间三位作为散列地址集: (100,121,201,020,123)

折叠法: 若关键字位数较多,也可将关键字分割成位数相 同的几段(最后一段的位数可以不同),段的长度 取决于散列表的地址位数,然后将各段的叠加(舍 去进位)作为散列地址。 折叠法分移位叠加和边界叠加两种。移位叠加是 将各段的最低位对齐,然后相加;边界叠加则是两 个相邻的段沿边界来回折迭,然后对齐相加。

除余法: 选择一个适当的正整数p,用p去除关键码,取其余数作为地 址,既h(key)=key mod p。这个方法的关键是选取的p,如果选 p为偶数,则它总是把奇数的关键码转换到奇数地址,把偶数 的关键码转换到偶数地址,这当然不好。如果选p为关键码的 基数的幂次也不好,因为那就等于选择关键码的最后几个数字 作为地址。例如,关键码是十进制数,若选p=100,则实际上 就是取关键码的最后两位作为地址。一般地选p为小于某个区 域长度n的最大素数比较好。 例如:n=8,16,32,64,128,256,512,1024 p=7,13,31,61,127,251,503,1019 除余法地址计算公式非常简单。实践证明恰恰是这种简单的方 法在许多情况下效果较好。

例如、用散列存储线性表:A=(18,75,60,43,54 ,90,46)。 分析:假定选取的散列函数为: h(K)=K mod p, K为元素的关键字,m为散列表的长度。这里假定K和 m均为正整数,并且m要大于等于线性表的长度n。此 例n=7,取m=14,故假定取p=13,则得到的每个元素 的散列地址为: h(18)=18 mod 13=5 h(75)=75 mod 13 =10 h(60)=60 mod 13=8 h(43)=43 mod 13=4 h(54)=54 mod 13=2 h(90)=90mod 13=12 h(46)=46 mod 13=7

根据散列地址把元素存储到散列表H[0..m-1]中,存储映象 为:

H

0

1

2 54

3

4 43

5 18

6

7 46

8 60

9

10 75

11

12 90

随机数法: 选择一个随机函数,取关键字的随机函数值为它的散列地 址,即H(key)=random(key)。 其中:random为随机函数。 基数转换法: 把关键字看成是另一个进制上的数后,再把它转换成原来 进制上的数,取其中的若干位作为散列地址。一般取大于原 来基数的数作为转换的基数,并且两个基数要互素。 例:给定一个十进制数的关键字为(210485)10,我们把它看 成以13为数的十三进制数(210485)13,再把它转换为十进制数 :(210485)13=(771932)10。假设散列表长度10000,则可取低四 位1932作为散列地址。

处理冲突的方法
一 . 开放地址法

做法:当冲突发生时,使用某种方法在散 列表中形成一个探查序列,沿着此探查序 列逐个单元地查找,直到找到给定的关键 字、或者碰到一个开放的地址(即该地址 单元为空)为止。插入时碰到开放的地址, 则可将待插入的新结点存放在该地址单元 中,查找时碰到开放的地址,则说明表中 没有待查的关键字。

1. 线性探查法 基 本思想:将散列表看成是一个环形表。 若地址为d(即H(key)=d)的单元发生冲突,则依 次探查下述地址单元: d+1,d+2,…,m-1,0,1,…,d-1 直到找到一个空单元 或查找到关键字为key 的 结点为止。当然,若沿着该探查序列查找一遍 之后,又回到了地址d,则无论是做插入操作还 是做查找操作,都意味着失败(即此时表满)。

用线性探查法解决冲突,求下一个开放地址 的公式为:
di=(d+i) mod m 其中:d=H(key)。 2 .二次探查法 二次探查法的探查序列依次是12,-12, 2 2 ,-22,…等 ,也就是说,发生冲突时,将同 义词来回散列在第一个地址d=H(key)的两端。 d2i-1=(d+i2) mod m d2i=(d-i2) mod m (1≤i≤(m-1)/2) i=1,2,…,s(1≤s<≤m-1)

3. 随机探查法 求下一个开放地址的公式为: di=(d+Ri) mod m (1≤i≤(m-1))

其中,d=H(key),R1,R2,…,Rm-1是1,2,…,m-1的一 个随机排列. 4. 双散列函数探查法

这种方法使用两个散列函数H1和H2,其中H1 和前面的H一样,以关键字为自变量,产生一个1 到m-1之间的数作为散列地址,H2也是以关键字为 自变量,产生一个1到m-1之间的,并和m互素的数 作为对散列地址的补偿。

di=(d+iH2(key)) mod m

(1≤i≤m-1)

定义H2的方法很多,都必须使H2(key)的值与m 互素。 ? 若m是素数,则H2(key)取1到m-1的任何数均与 m互素。 例:H2(key)=key mod (m-2)+1 ? 若m是2的方幂,则H2(key)可取1到m-1之间的任 何奇数。

拉链法 基本思想:拉链法解决冲突的做法,是将所有关键 字为同义词的结点链接在同一个单链表中.若选定的 散列函数的值域为1到m,则可将散列表定义为一个 由m个头指针组成的指针数组HTP[m],凡是散列地 址为i的结点,均插入到HTP[i]为头指针的单链表中 。 例:已知一组关键字为 (26,36,41,38,44,15,68,12,06,51,25)散列函数为H( key)=key mod 13。

例:已知一组关键字为(26,36,41,38,44,15,68,12,06,51,25)散列 函数为H(key)=key%13。

拉链法的优点: 拉链法不会产生堆积现象,平均查找长度较短。 结点空间动态申请,适合表长不定情况。 删除结点的操作易于实现。 当装填因子α较大时,拉链法所用的空间比开放地 址法多,但α越大,开放地址法所需的探查次数越大, 所以,拉链法所增加的空间是合算的。

散列表的查找及分析 散列表的查找过程和建表过程相似。假设给定的值为K,根 据建表时设定的散列函数H,计算出散列地址H(K),若表中 该地址对应的空间未被占用,则查找失败,否则将该地址中 的结点与给定值K比较,若相等则查找成功,否则按建表时设 定的处理冲突方法找下一个地址,如此反复下去,直到某个 地址空间未被占用(查找失败)或者关键字比较相等(查找成功) 为止。
const empty=maxlongint; {用非常大的整数代表这个位置没有存储元素} p=97; s=100 {表的大小} procedure makenull; var i:integer; begin for i:=0 to s do A[i]:=empty; End;

哈希函数值的运算根据函数的不同而变化,例如除 余法的一个例子:

function h(x:longint):Integer; begin h:= x mod p; end;

我们注意到,插入和查找首先都需要对这个元素定位,即 如果这个元素若存在,它应该存储在什么位置,因此加入一 个定位的函数 locate
function locate(x:longint):integer; var orig,i:integer; begin orig:=h(x); i:=0; while (i<S)and(A[(orig+i)mod S]<>x)and(A[(orig+i)mod S]<>empty) do inc(i); {当这个循环停下来时,要么找到一个空的存储单元,要么找 到这个元素存储的单元,要么表已经满了} locate:=(orig+i) mod S; end;

procedure insert(x:longint);{插入元素} var posi:integer; begin posi:=locate(x); {定位函数的返回值} if A[posi]=empty then A[posi]:=x else writeln('error'); {error 即为发生了错误,当然 这是可以避免的} end; procedure member(x:longint):boolean;{查找元素是否已经在表中} var posi:integer; begin posi:=locate(x); if A[posi]=x then member:=true else member:=false; end;

小结 从上述查找过程可知,虽然散列表是在关键字和存储位置 之间直接建立了对应关系,但是,由于冲突的产生,散列表 的查找过程仍然是一个和关键字比较的过程,不过散列表的 平均查找长度比顺序查找要小得多,比二分查找也小。 对于不成功的查找,顺序查找和二分查找所需进行的关键 字比较次数仅取决于表长,而散列查找所需进行的关键字比 较次数和待查结点有关。因此,在等概率情况下,也可将散 列表在查找不成功的平均查找长度,定义为查找不成功时对 关键字需要执行的平均比较次数。


推荐相关:

第九章 查找

第九章 查找_理学_高等教育_教育专区。班级: 学号: 姓名: 第九章一、选择题 查找的线性表。 1.顺序查找法适合于存储结构为 A. 散列存储 C. 压缩存储 A. ...


习题第九章查找

第九章 查找一、 选择题 1.若查找每个记录的概率均等,则在具有 n 个记录的连续顺序文件中采用顺序查找法查找一个记录,其平均查找长度 ASL 为 ( )。 【北京...


习题第九章查找(1)

习题第九章查找(1)_理化生_初中教育_教育专区。第九章 查找一、 选择题 1.若查找每个记录的概率均等,则在具有 n 个记录的连续顺序文件中采用顺序查找法查找一...


第九章 查找

34页 20财富值 第9章 查找 142页 免费 第九章 查找简述 21页 2财富值 第9章查找 71页 1财富值 第九章 查找表 7页 免费 习题第九章查找 4页 免费喜欢...


第九章习题

第九章 查找一、 选择题 1.若查找每个记录的概率均等, 则在具有 n 个记录的连续顺序文件中采用顺序查找法查找一 个记录,其平均查找长度 ASL 为( )。 A. (...


数据结构第九章 查找 习题及答案

数据结构第九章 查找 习题及答案_理学_高等教育_教育专区 暂无评价|0人阅读|0次下载|举报文档 数据结构第九章 查找 习题及答案_理学_高等教育_教育专区。数据结构...


第九章查找 习题解答

第九章查找 习题解答 9.5 画出对长度为 10 的有序表进行折半查找的判定树, 并求其等概率时查找成功的平 均查找长度。 解:求得 的判定树如下: 5 2 1 ...


习题第九章查找答案

习题第九章查找答案_IT/计算机_专业资料 暂无评价|0人阅读|0次下载|举报文档习题第九章查找答案_IT/计算机_专业资料。文档贡献者 ☆→の嶽ん 贡献于2012-03-...


数据结构 第九章 查找 作业及答案

第九章 查找一、填空题 1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是 表中与 k 相等的元素,在查找不成功的情况下,最多需要检索 用二分法查找时,...


《数据结构题集》答案 第9章 查找

第九章 查找 9.25 int Search_Sq(SSTable ST,int key)//在有序表上顺序查找的算法,监视哨设在高下 标端 { ST.elem[ST.length+1].key=key; for(i=1;...

网站首页 | 网站地图
All rights reserved Powered by 简单学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com