第 10章 查找
静态查找表
动态查找表
哈希查找表在各种系统软件和应用软件中，查找表是一种最常见的数据结构，有着广泛的应用。
10.1 查找表基本概念查找表 (table):由同类型的 DE(或记录 )构成的集合,
查找表上的基本运算,
建立查找表 create(ST,n)
查找 search(ST,k)
遍历查找表 traverse(ST)
其抽象数据类型定义见书 P216.
关键字（ key）,是表中数据元素中某个数据元素的某值，
用它可以标识（识别）这个数据元素。若此关键字可以唯一地标识这个元素，则它称为 主关键字 （ Primary Key）；反之，若用它能识别一批元素，则称它为 次关键字 （ Secondary Key）。
查找表基本概念查找,在查找表中确定一个关键字与给定值相等的 DE
的过程,
查找结果,
查找成功 (table 中存在给定值的记录 )
查找不成功 (table 中不存在给定值的记录 )
查找表分为,
静态查找表 (对查找表中的数据元素 不 进行插入和删除操作 )
动态查找表 (对查找表中的数据元素 可 进行插入和删除操作 )
查找表基本概念本章中涉及的关键字类型及数据元素类型如下：
典型的关键字类型说明可以是：
typedef float KeyType; //关键字类型为实型
typedef int KeyType; //关键字类型为整型
typedef char KeyType; //关键字类型为字符串型数据元素类型定义为：
typedef struct{
KeyType key; //关键字域
….,// 其它域
}ElemType;
查找表基本概念关键字比较的常用宏定义用于数值关键字的有：
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
#define LQ(a,b) ((a)<=(b))
用于字符串型关键字的有：
#define EQ(a,b) (!strcmp((a),(b))
#define LT(a,b) (strcmp((a),(b))<0)
#define LQ(a,b) (strcmp((a),(b))<=0)
10.2 顺序查找表一,顺序表的查找静态查找表的顺序存储结构为
typedef struct{
ElemType *elem; //元素存储空间基址,0号单元留空
int length; // 表长度
}SSTable; //顺序查找表类型顺序查找（ Sequential Search）的算法思想：
从表中最后一个元素开始，把给定值与元素的关键字逐个作相等比较，若有某元素的关键字与给定值相等，则查找成功
，返回其位置序号；否则返回 0。
10.2 顺序查找表
1,查找过程,从 n开始,依次与 k进行比较,若相等则查找成功 ; 否则,继续进行,直到与 r[0].key比较为止,
2,算法分析,
(1) 算法结构应由一个循环构成 ;
(2) 循环结束有两种可能：
查找成功 ST.elem[i].key = key
查找不成功 i = 0
int seqsrch(SSTable ST,KeyType key)
{ ST.elem[0]=key;//设置“哨兵”
for (I=ST.length;!EQ(ST.elem[i].key,key);i--);//从后往前找
return i； //找不到时,i为 0
}//seqsrch
10.2 顺序查找表
(2) 循环结束有两种可能：
查找成功 ST.elem[i].key = key 条件控制式
查找不成功 i = 0 计数控制式这两种可能形成两种不同类型的循环控制：
条件循环 while 条件 循环体
do 循环体 while 条件
计数循环 for (I=ST.length;!EQ(ST.elem[i].key,key);i--);
常规解决办法,
(1) 条件循环为主
i=ST.length; while (!EQ(ST.elem[i].key,key)) i=i-1;
(2) 计数循环为主
for (i=ST.length;!EQ(ST.elem[i].key,key);i--);
10.2 顺序查找表
int seqsrch1(SSTable ST,KeyType key)
{ ST.elem[ST.length+1]=key;//设置“哨兵”
for (i=1;!EQ(ST.elem[i].key,key);i++);//从前往后找
if (i!= ST.length+1 ) return 0； //找不到时,i为 ST.length+1
return i;
}//seqsrch1
4,查找方向可换
int seqsrch(SSTable ST,KeyType key)
{ ST.elem[0]=key;
for (I=ST.length;!EQ(ST.elem[i].key,key);i--);
return i； }//seqsrch
3,ST.elem[0]起监视哨作用
10.2 顺序查找表平均查找长度 (ASL):
查找过程中,给定值需与关键字比较的次数的期望值,
n
ASL=∑PiCi
i =1
其中,Pi 为查找第 i 个记录的概率 ;
Ci 为找到第 i 个记录时,已比较的次数,
顺序查找的平均查找长度 ASLss=np1+(n-1)p2+……+p n
n
当 pi=1/n时,ASLss=∑PiCi =(n+1)/2
i =1
10.2 顺序查找表二,有序表的查找有序表,查找表中记录按关键字有序排列的表,
即,ST.elem[i].key<= ST.elem[i+1].key i=1,2,…,n -1
折半查找,
要求,查找表为有序表 ;
查找过程,先确定待查记录范围 ;
然后逐步缩小范围 ;
直到,查找成功或不成功,
10.2 顺序查找表折半查找算法,
int Search_Bin ( SSTable ST,KeyType key ) {
// 在有序表 ST中折半查找其关键字等于 key的数据元素。若找到，则
//函数值为该元素在表中的位置，否则为 0。
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
例,k=21,有序表为,
(5,13,19,21,37,56,64,75,80,88,92)
1,Low =1,high=11,mid=6
2,∵ 21<56 high=6-1 mid=3
3,∵ 21>19 low=4 mid= 4
4,21=21 found=true return(4)
折半查找的平均查找长度
ASLbs=(n+1)/nlog2(n+1)-1
≈log2(n+1)-1
折半查找的平均查找长度分析先看一个具体的情况，假设,n=11
现构造一棵二叉树，将 Ci=i的结点放在这棵树的第 i层,Ci为比较次数。
该二叉树可用以描述折半查找的过程，称之谓“折半查找的判定树”
例如,折半查找在 n=11 时的判定树如下：
二叉树描述的是整个折半查找的过程，对任何一个结点查找来说是走了一条从根结点到该结点的一条路径，比较的次数正好是路径中的结点数目，也即结点所在的层次。方块结点是查表不成功的区域。 一般情况下，表长为 n的折半查找的判定树的深度和含有 n个结点的完全二叉树的深度相同。
对于上面的判定树平均查找次数，（ 1*1+2*2+4*3+4*4） /11
I 1 2 3 4 5 6 7 8 9 10 11
Ci 3 4 2 3 4 1 3 4 2 3 4
假设 n=2h-1 并且查找概率相等则在 n>50时，可得近似结果折半查找的平均查找长度分析
10.3 索引查找表索引顺序表的查找 (分块查找 )
索引表,
1) 按表中记录的关键字分块,R1,R2,…,R L
要求,第 Rk 块中的所有关键字 < Rk+1块中的所有关键字
k=1,2,…,L -1,称为“分块有序”
2) 对每块建立一个索引项,包含以两项内容,
① 关键字项,为该块中最大关键字值 ;
② 指针项,为该块第一个记录在表中位置,
3) 所有索引项组成索引表例,查找表为,
22,12,13,8,9,20,33,42,44,38,24,48,60,58,74,49,86,53
索引表为,
关键字项指针项
22 48 86
1 7 13
10.3 索引查找表查找分为两步,
1,确定待查记录所在块 ; (可以用顺序或折半查找 )
2,在块内顺序查找,(只能用顺序查找 )
关键字项指针项
22 48 86
1 7 13
22,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为止,
10.3 索引查找表分块查找表的平均查找长度 ASL=Lb+Lw
其中,Lb为查索引表确定所在块的平均查找长度 ;
Lw为在块内查找记录的平均查找长度 ;
三种查找方法比较顺序查找 折半查找 分块查找
ASL 大 小 中表结构要求 无 有序表 分段有序
（块之间有序）
10.3 索引查找表
10.4 树表查找（动态查找表）
动态查找表的特点是,表结构本身是在查找过程中动态生成的。
即查找不成功时，将该记录插入在动态查找表中。
一、二叉排序树（ Binary Sort Tree)（又称为二叉查找树）
1,BST定义：
BST或者是一棵空树；或者是具有如下性质的 BT:
若左子树非空，则左子树上所有结点的值均小于根结点的值；
若右子树非空，则右子树上所有结点的值均大于根结点的值；
左、右子树也为 BST
78
100
61
90
12
37
24
8
45
53
例如：
通常，取二叉链表作为二叉排序树的存储结构。中序遍历的结果的序列是有序的，即（ 8,12,24,37,45,53,61,78,90,100）。所以二叉排序树本身可以看成是个有序表，但是这棵树不是有序表构成的，
可以由一个无序序列，构造完以后是个有序表 。
二叉排序树的特点，是用非线形结构来表示一个线形有序表 。
10.4 树表查找（动态查找表）
2、查找过程为,
(1) 当前 BST非空时，将给定值 k与当前根结点的关键字比较,
(2) 若相等，查找成功，结束 ;
若 k小于当前根结点的关键字，则将左子树作为当前 BST;
若 k大于当前根结点的关键字，则将右子树作为当前 BST;
(3) 重复 (1),(2) 。
10.4 树表查找（动态查找表）
算法描述如下：
Status SearchBST (BiTree T,KeyType key,BiTree f,BiTree &p ) {
// 在根指针 T所指二叉排序树中递归地查找其关键字等于 key的数据元
//素，若查找成功，则指针 p指向该数据元素结点，并返回 TRUE，
//否则指针 p指向查找路径上访问的最后一个结点，并返回 FALSE，
//指针 f指向 T的双亲，其初始调用值为 NULL。
if (!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 );// 在右子树中继续查找
} // SearchBST
10.4 树表查找（动态查找表）
3,BST的插入对于动态查找表，在查找不成功的情况下，尚需插入关键字等于给定值的记录，并且从查找的过程容易得出插入的算法：
插入原则,若二叉排序树为空树，则新插入的结点为根结点；否则,
记下查找不成功时比较的最后一个结点的位置，将插入结点作为该结点的左或右孩子。
Status Insert_BST(BiTree &T,ElemType e ) {
// 当二叉排序树 T中不存在关键字等于 e.key的数据元素时，插入 e并返回 TRUE，否则返回 FALSE。
if (!SearchBST ( T,e.key,NULL,p )) { // 查找不成功
s = (BiTree) malloc (sizeof (BiTNode));
s->data = e; s->lchild = s->rchild = NULL;
10.4 树表查找（动态查找表）
if ( !p ) T = s; // 插入 s 为新的根结点,p是查找的结果
else if ( LT(e.key,p->data.key) ) p->.lchild = s// 插入 s 为左孩子
else p->.rchild = s; // 插入 s 为右孩子
return TRUE;}
else return FALSE;// 树中已有关键字相同的结点，不再插入
} // Insert BST
10.4 树表查找（动态查找表）
45
1
45
4
3
7
53
90
2
246
12
5
例：设 BST为空，
查找关键字序列为 {45,24,53,45,12,24,90}，
则经过一系列查找插入操作后，生成的 BST为：
10.4 树表查找（动态查找表）
4,BST的特点：
(1) 中序遍历 BST可得到一个关键字的有序序列。
如上例：中序遍历结果为,12,24,45,53,90
这是由于 BST中左子树的所有结点的值均小于其根结点的值，
右子树的所有结点的值均大于其根结点的值；
而中序遍历又是以 L DR顺序访问的。
10.4 树表查找（动态查找表）
(2) 在 BST上插入新结点时，不必移动其他结点，仅需改动某结点的指针（因新结点总是 BST上的一个新叶结点）。
(3) BST既具有类似折半查找的特性（与 BST的平衡度有关）又采用了链表存储结构（折半查找不能为链表存储结构），因此，对于经常要进行查找、插入和删除记录的有序表，采用 BST尤其合适。
10.4 树表查找（动态查找表）
5,BST的删除和插入相反，删除在查找成功之后进行删除的原则,
删除某个结点后仍保持 BST的特性。
设：被删除结点为 p↑(指针 p所指结点）
其双亲结点为 f ↑,且不失一般性，设 p 是 f 的左孩子。
10.4 树表查找（动态查找表）
c
q
C
SL
s
CL
F
FR
f
PR
p
P
Q
QL S
分三种情况讨论：
若 P结点为叶结点（即 PL和 PR均为空树，仅需将 f->lchild=NULL
若 P结点只有左子树 PL或只有右子树 PR,只需 令 PL或 PR为 f结点的左子树，即
f -> lchild= P-> lchild (或 P->rchild)
若 P↑结点左、右子树均不空，此时，按中序遍历序列为：
…C L C…Q L Q SL S P PR F FR…
删除 p后为,…C LC…Q L Q SL S PR F FR…
结果是将 PR作为 SR 。
10.4 树表查找（动态查找表）
C
SL
CL
PR
Q
QL S
F
S
SL
CL
F
PR
Q
QL
C
对 F的左孩子有两种处理办法：
(1) S不动，仍作为 Q的右孩子,C代替 P,作为 F的左孩子 ;
(2) S代替 P，而 SL为 QR ;
算法实现：
Status DeleteBST (BiTree &T,KeyType key ) {
// 若二叉排序树 T中存在关键字等于 key的数据元素时，则删除该数据元素
//结点 p，并返回 TRUE；否则返回 FALSE
if (!T) return FALSE;// 不存在关键字等于 key的数据元素
else
{if ( EQ (key,T->data.key) ) Delete (T);
// 找到关键字等于 key的数据元素
else if( LT (key,T->data.key) ) DeleteBST ( T->lchild,key );
else DeleteBST ( T->rchild,key );
return TRUE;}
} // DeleteBST
其中删除操作过程如下所描述：
void Delete ( BiTree &p ){
// 从二叉排序树中删除结点 p，并重接它的左或右子树
10.4 树表查找（动态查找表）
if (!p->rchild) // 右子树空则只需重接它的左子树
{ q = p; p = p->lchild; free(q);}
else if (!p->lchild) // 只需重接它的右子树
{ q = p; p = p->rchild; free(q);}
else // 左右子树均不空
{ q = p; s = p->rchild;
while (!s->lchild) { q = s; s = s->lchild; }
p->data = s->data;
if (q != p ) q->lchild = s->rchild;
else q->rchild = s->rchild; // 重接 *q的右子树
free(s);
}
} // Delete
10.4 树表查找（动态查找表）
6,BST 的查找分析
BST 上查找过程与折半查找类似，是从根结点到所找到结点的一条路径。与给定值比较次数等于该路径长度 +1（即结点所在层次数），最大次数不超过树的深度。
但长度为 n的折半查找表对应的判定树是唯一的。而含有 n个结点的 BST却不唯一
。
45
93
53
3712
24
(a)
(45,24,53,12,37,93)
12
24
37
45
53
93(b)
(12,24,37,45,53,93)
ASL(a)=1/6（ 1+2+2+3+3+3） =14/6
ASL(b)=1/6（ 1+2+3+4+5+6） =21/6
10.4 树表查找（动态查找表）
因此，含有 n个结点的 BST的 ASL和树的形态有关。
最差情况是 BST退化为单支树，其深度为 n，
ASL=(n+1)/2 (同顺序查找）。
最好情况与折半查找相同,ASL=log2n
随机情况下，平均查找长度为 1+4log n
为了避免出现单支树，在构成 BST的过程中可进行
“平衡化”处理。
10.4 树表查找（动态查找表）
二,平衡二叉树 (Balanced Binary Tree),又称为 AVL树
1,AVL树定义
AVL树或者是一棵空树，或者是具有下列性质的 BT:
左、右子树均为 AVL，
且任一左、右子树的深度之差的绝对值不超过 1.
称某结点左子树的深度－右子树的深度为该结点的 平衡因子 （ balance factor)
10.4 树表查找（动态查找表）
1
0
0
1
(a)
0
1
-1
0
0
2
(c)
0
1
0
0
-1
1
-1
(b)
例如：
结点中的值为该结点的平衡因子
10.4 树表查找（动态查找表）
2,AVL树的特点
AVL树上任何结点的平衡因子只可能为 -1,0或 1;
AVL树的深度与 log n同数量级 ;
AVL树的 ASL也与 log n同数量级 ;
完全二叉树一定是 AVL,当 AVL树不一定是完全二叉树
10.4 树表查找（动态查找表）
3,BST变为 AVL树
⑴ 例：设表的关键字序列为（ 13,24,37,90,53）,
BST生成过程为：
13
24
13
AVL AVL AVL
旋转
37
24
13
非 AVL
37
24
13
AVL
10.4 树表查找（动态查找表）
非 AVL
90
37
24
13
53
90
37
24
13
旋转 旋转
90
53
37
24
13
AVL
37 90
53
24
13
在 BST上插入结点而失去平衡，失去平衡后需进行调整,
调整 BST为二叉平衡（查找）树的 方法 是：在插入过程中，采用平衡旋转技术。
10.4 树表查找（动态查找表）
(2) 调整形态 (可归纳为四种 )
① LL型平衡旋转（顺时针）
失去平衡结点的平衡因子为 2,其左孩子的平衡因子为 1
LL
0
A
ARBR h-1h-1
0
B
BL h h
调整语句为：
b＝ a->lchild;
a-> lchild =b->rchild ; a-> bf=0
b-> rchild=a; b -> bf=0
2
A
a
AR h-11
B
BRBL h-1h
h+1
L+1
b
② LR型平衡旋转失去平衡结点的平衡因子为 2,其左孩子的平衡因子为 -1
2
A
AR h-1-1
B
BL
CL h-1
h-1
h+1
1
C h
h-2CR
LR
0
C
AR h-1
0
B
BL CL h-1h-1
-1
A
h-2CR
b＝ a->lchild; c= b->rchild；
a->lchild =c->rchild ; b-> rchild = c->lchild
C->rchild＝ a; c->lchild＝ b;
10.4 树表查找（动态查找表）
③ RR型平衡旋转（逆时针，与① LL对称 )
失去平衡点的平衡因子为 -2,其右孩子的平衡因子为 -1
-2
A
AL
BL h-1
h-1
-1
B
hBR
RR
0
B
BLAL h-1
0
A
BR
10.4 树表查找（动态查找表）
④ RL型平衡旋转失去平衡点的平衡因子为 -2,其右孩子的平衡因子为 1
RL
0
C
BR
0
A
AL CL
-1
B
h-2CR
1
B
BR h-1
-2
A
AL h-1
CL h-1
1
C
h-2CR
中序遍历,AL A CL C CR B BR AL A CL C CR B BR
10.4 树表查找（动态查找表）
在平衡树上进行查找的过程和二叉排序树相同，因此，查找过程中和给定值进行比较的关键字的个数不超过平衡树的深度。
假设深度为 h的二叉平衡树上所含结点数的最小值为 Nh，
则显然 Nh = Nh-1 + Nh-2 + 1由此可以推导出,h≈log （ n）
因此，在平衡树上进行查找的时间复杂度为 O(log(n))
平衡树的查找性能分析
10.5 哈希查找表前面介绍的查找算法,有一个共同特点,就是以待查关键字 k
在表中，通过一系列 比较 来确定该记录在表中的“地址”。
这一节将介绍另一种通过 计算 来查找的新型方法 -----哈希法
（ Hash）或称杂凑法、散列法。
设关键字集合为 A，地址空间为 D，哈希法就是在 A和 D之间建立一种函数关系 H，通过计算函数 H（ k），就能得到关键字 K的地址。
关键字集 A
m
地址空间 D
n
哈希函数
H（ k）
设 D是长度为 n的表，
A是含 m个记录的关键字集合，
如果存在一个 函数 H，使得对 A中任一关键字 Ki，均有，
0≤H（ Ki ） ≤n-1 i=1,2．．．,m
同时,Ki 所标识的记录 R i在表 D中的地址是 H(Ki)，
则称函数 H为关键字集合 A到地址空间 D之间的哈希函数，
地址空间 D为哈希表。
哈希函数并不一定是一对一的，例如，当 m＞ n时，对任何哈希函数 H，至少存在两个关键字 Ki ≠ Kj,使得 H(Ki) = H(Kj)，
这种对不同关键字而得到同一地址的现象，成为 冲突 。
10.5 哈希查找表因此，在应用哈希查找方法时，主要要解决两个技术问题：
一是构造好哈希函数的方法 ;
二是研究解决冲突的方法。
一,哈希函数构造方法一个好的哈希函数应满足下列两个条件：
计算简单容易
冲突极少
10.5 哈希查找表
1．直接哈希函数取关键字本身或关键字的某个线性函数值作为哈希地址，
即,H（ key） =key 或 H（ key） =a* key+b （ a,b为常数）
例如：有一个解放后出生人口调查表，每个记录包含年份、人数等数据项，其中年分为关键字，则哈希函数可取为,
H（ key） =key +（ -1948）
这样就可以方便地存储和查找 1948年后任一年的记录。
地址年份人数
01
1949
．．．．．．
．．．．．．
．．．．．．
22
1970
10.5 哈希查找表
2．数字分析法设ｎ个ｄ位数的关键字，由ｒ个不同的符号组成，此ｒ个符号在关键字的各位出现的频率不一定相同，可能在某些位上均匀分布，即每个符号出现的次数都接近于ｎ／ｒ次，而在另一些位上分布不均匀。 则选择其中分布均匀的 s位作为哈希地址，即 H（ key） =“key中数字均匀分布的 s位”，这便是数字分析哈希函数。
例：由 80个记录，关键字为 8位十进制数，（ n=80,r=10,d=8）
对关键字的各位进行分析，发现：第 1,2位都是,8,1”，第 3
位只取 1,2,3或 4，第 8位只取 2,5或 7，即 10个数在这四位分布不均匀，不取。可在剩下的 4,5,6,7位中任取两位，作为哈希地址。
10.5 哈希查找表
3．平方取中法取关键字平方后的中间几位作为哈希地址，即哈希函数为,
H（ key） =“key2的中间几位”
其中，所取的位数由哈希表的大小确定。
10.5 哈希查找表
4．折叠法将关键字分割成位数相等的几部分（最后一部分位数可以不同），取这几部分的叠加和（舍去高位的进位）作为哈希地址。位数由存储地址的位数确定。
相加时有两种方法：
一是移位叠加法，即将每部分得最后一位对齐，然后相加；
另一种是间界叠加法，即将关键字看作一纸条，从一端向另一端沿间界逐次折叠，然后对齐相加。
10.5 哈希查找表设关键字 key=d3 r．．,d 2 r+1d2 r．．,d r+1d r．．,d2d1
允许的存储地址有 r位。
则 移位叠加法为,d r．．,d2d1
d2 r,．,d r+1
+) d３ r,．,d 2 r+1
Sr,．,S2S1
10.5 哈希查找表
5．除留余数法取关键字被某个不大于哈希表长 m的数 p除后的余数为哈希地址。
即 H（ key） =key MOD p,p≤m
p的选择很重要，选得不好会产生很多冲突，
通常，选择 p≤ m的某个质数。
6．随机数法选择一个随机函数，取关键字的随机函数值作为它的哈希地址。
即 H（ key） =random（ key）
10.5 哈希查找表二,处理冲突的方法冲突 是指由关键字得到的 Hash地址上已有其他记录,
处理冲突 就是为该关键字找到另一个“空”的 Hash地址。
1,开放定址法
Hi =（ H（ key） +di） mod m i=1,2．．,m-1;
其中,Hi 为第 i次冲突的地址,
H（ key） 为 Hash函数值,
m 为 Hash表表长,
di 为增量序列
10.5 哈希查找表
Hi =（ H（ key） +di） mod m i=1,2．．,m-1;
其中,di为增量序列,有三种取法：
di =1,2,3．．,m-1 称为线性探测再散列
di =12,-12,22,-22,32．．,± k2 |± k|≤m-1
称为二次探测再散列
di =伪随机序列 称为伪随机探测再散列
10.5 哈希查找表例：设 m=16,表中已有关键字,分别为,19,70,33三个记录，
Hash函数取为 H（ key） = key mod13，现第四个关键字为 18的记录要填入表中，由 Hash函数得地址 5，产生冲突
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
70 19 33
70 19 33 18
H1 H2 H3
18 70 19 33
H2 H1
70 19 33
线性二次伪随机伪随机数序列 9．．．,H1＝１ 4 mod 16 =14
18
2,再哈希法
Hi =RHi （ key） i=1,2．．,n;
RHi 为不同哈希函数用 n个不同哈希函数排成一个序列,当发生冲突时,
由 RHi确定第 i次冲突的地址 Hi
10.5 哈希查找表
3,链地址法 将关键字发生冲突的记录存储在同一个线性链表中。
例,H（ key） = key mod 13
对关键字 19,14,23,01,68,20,84,27,55,11,10,79
处理的结果为：
0
1
2
3
4
5
6
7
8
9
10
11
12
79 01 14
6855
1984
20
2310
11
∧
∧
∧
∧
∧
∧
27
∧
∧
∧
∧
∧
∧
∧
0
1
2
3
4
5
6
7
8
9
10
11
12
∧
∧
68
∧
∧
19
20
∧
∧
23
11
∧
14
Hash表
01
27
55
10
79
84
溢出表顺序查找
4,公共溢出区法将同哈希表中关键字发生冲突的所有记录填入一个溢出表中,
例如上例的结果为：
10.5 哈希查找表数据结构的学习重点
1、如何描述一种新的抽象数据类型？
2、如何分析算法的优劣？
3、线性表的主要特征。
4、线性表的存储表示（顺序表示、单向链表、循环链表、
双向链表）
5、特殊的线性表：栈、队列、串、广义表
6、二叉树的定义、性质、存储结构、遍历算法
7、图的定义、术语、存储结构
8、静态查找表、二叉排序树、哈希函数的构造及冲突处理方法。
9、插入排序、快速排序、选择排序总复习
静态查找表
动态查找表
哈希查找表在各种系统软件和应用软件中，查找表是一种最常见的数据结构，有着广泛的应用。
10.1 查找表基本概念查找表 (table):由同类型的 DE(或记录 )构成的集合,
查找表上的基本运算,
建立查找表 create(ST,n)
查找 search(ST,k)
遍历查找表 traverse(ST)
其抽象数据类型定义见书 P216.
关键字（ key）,是表中数据元素中某个数据元素的某值，
用它可以标识（识别）这个数据元素。若此关键字可以唯一地标识这个元素，则它称为 主关键字 （ Primary Key）；反之，若用它能识别一批元素，则称它为 次关键字 （ Secondary Key）。
查找表基本概念查找,在查找表中确定一个关键字与给定值相等的 DE
的过程,
查找结果,
查找成功 (table 中存在给定值的记录 )
查找不成功 (table 中不存在给定值的记录 )
查找表分为,
静态查找表 (对查找表中的数据元素 不 进行插入和删除操作 )
动态查找表 (对查找表中的数据元素 可 进行插入和删除操作 )
查找表基本概念本章中涉及的关键字类型及数据元素类型如下：
典型的关键字类型说明可以是：
typedef float KeyType; //关键字类型为实型
typedef int KeyType; //关键字类型为整型
typedef char KeyType; //关键字类型为字符串型数据元素类型定义为：
typedef struct{
KeyType key; //关键字域
….,// 其它域
}ElemType;
查找表基本概念关键字比较的常用宏定义用于数值关键字的有：
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
#define LQ(a,b) ((a)<=(b))
用于字符串型关键字的有：
#define EQ(a,b) (!strcmp((a),(b))
#define LT(a,b) (strcmp((a),(b))<0)
#define LQ(a,b) (strcmp((a),(b))<=0)
10.2 顺序查找表一,顺序表的查找静态查找表的顺序存储结构为
typedef struct{
ElemType *elem; //元素存储空间基址,0号单元留空
int length; // 表长度
}SSTable; //顺序查找表类型顺序查找（ Sequential Search）的算法思想：
从表中最后一个元素开始，把给定值与元素的关键字逐个作相等比较，若有某元素的关键字与给定值相等，则查找成功
，返回其位置序号；否则返回 0。
10.2 顺序查找表
1,查找过程,从 n开始,依次与 k进行比较,若相等则查找成功 ; 否则,继续进行,直到与 r[0].key比较为止,
2,算法分析,
(1) 算法结构应由一个循环构成 ;
(2) 循环结束有两种可能：
查找成功 ST.elem[i].key = key
查找不成功 i = 0
int seqsrch(SSTable ST,KeyType key)
{ ST.elem[0]=key;//设置“哨兵”
for (I=ST.length;!EQ(ST.elem[i].key,key);i--);//从后往前找
return i； //找不到时,i为 0
}//seqsrch
10.2 顺序查找表
(2) 循环结束有两种可能：
查找成功 ST.elem[i].key = key 条件控制式
查找不成功 i = 0 计数控制式这两种可能形成两种不同类型的循环控制：
条件循环 while 条件 循环体
do 循环体 while 条件
计数循环 for (I=ST.length;!EQ(ST.elem[i].key,key);i--);
常规解决办法,
(1) 条件循环为主
i=ST.length; while (!EQ(ST.elem[i].key,key)) i=i-1;
(2) 计数循环为主
for (i=ST.length;!EQ(ST.elem[i].key,key);i--);
10.2 顺序查找表
int seqsrch1(SSTable ST,KeyType key)
{ ST.elem[ST.length+1]=key;//设置“哨兵”
for (i=1;!EQ(ST.elem[i].key,key);i++);//从前往后找
if (i!= ST.length+1 ) return 0； //找不到时,i为 ST.length+1
return i;
}//seqsrch1
4,查找方向可换
int seqsrch(SSTable ST,KeyType key)
{ ST.elem[0]=key;
for (I=ST.length;!EQ(ST.elem[i].key,key);i--);
return i； }//seqsrch
3,ST.elem[0]起监视哨作用
10.2 顺序查找表平均查找长度 (ASL):
查找过程中,给定值需与关键字比较的次数的期望值,
n
ASL=∑PiCi
i =1
其中,Pi 为查找第 i 个记录的概率 ;
Ci 为找到第 i 个记录时,已比较的次数,
顺序查找的平均查找长度 ASLss=np1+(n-1)p2+……+p n
n
当 pi=1/n时,ASLss=∑PiCi =(n+1)/2
i =1
10.2 顺序查找表二,有序表的查找有序表,查找表中记录按关键字有序排列的表,
即,ST.elem[i].key<= ST.elem[i+1].key i=1,2,…,n -1
折半查找,
要求,查找表为有序表 ;
查找过程,先确定待查记录范围 ;
然后逐步缩小范围 ;
直到,查找成功或不成功,
10.2 顺序查找表折半查找算法,
int Search_Bin ( SSTable ST,KeyType key ) {
// 在有序表 ST中折半查找其关键字等于 key的数据元素。若找到，则
//函数值为该元素在表中的位置，否则为 0。
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
例,k=21,有序表为,
(5,13,19,21,37,56,64,75,80,88,92)
1,Low =1,high=11,mid=6
2,∵ 21<56 high=6-1 mid=3
3,∵ 21>19 low=4 mid= 4
4,21=21 found=true return(4)
折半查找的平均查找长度
ASLbs=(n+1)/nlog2(n+1)-1
≈log2(n+1)-1
折半查找的平均查找长度分析先看一个具体的情况，假设,n=11
现构造一棵二叉树，将 Ci=i的结点放在这棵树的第 i层,Ci为比较次数。
该二叉树可用以描述折半查找的过程，称之谓“折半查找的判定树”
例如,折半查找在 n=11 时的判定树如下：
二叉树描述的是整个折半查找的过程，对任何一个结点查找来说是走了一条从根结点到该结点的一条路径，比较的次数正好是路径中的结点数目，也即结点所在的层次。方块结点是查表不成功的区域。 一般情况下，表长为 n的折半查找的判定树的深度和含有 n个结点的完全二叉树的深度相同。
对于上面的判定树平均查找次数，（ 1*1+2*2+4*3+4*4） /11
I 1 2 3 4 5 6 7 8 9 10 11
Ci 3 4 2 3 4 1 3 4 2 3 4
假设 n=2h-1 并且查找概率相等则在 n>50时，可得近似结果折半查找的平均查找长度分析
10.3 索引查找表索引顺序表的查找 (分块查找 )
索引表,
1) 按表中记录的关键字分块,R1,R2,…,R L
要求,第 Rk 块中的所有关键字 < Rk+1块中的所有关键字
k=1,2,…,L -1,称为“分块有序”
2) 对每块建立一个索引项,包含以两项内容,
① 关键字项,为该块中最大关键字值 ;
② 指针项,为该块第一个记录在表中位置,
3) 所有索引项组成索引表例,查找表为,
22,12,13,8,9,20,33,42,44,38,24,48,60,58,74,49,86,53
索引表为,
关键字项指针项
22 48 86
1 7 13
10.3 索引查找表查找分为两步,
1,确定待查记录所在块 ; (可以用顺序或折半查找 )
2,在块内顺序查找,(只能用顺序查找 )
关键字项指针项
22 48 86
1 7 13
22,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为止,
10.3 索引查找表分块查找表的平均查找长度 ASL=Lb+Lw
其中,Lb为查索引表确定所在块的平均查找长度 ;
Lw为在块内查找记录的平均查找长度 ;
三种查找方法比较顺序查找 折半查找 分块查找
ASL 大 小 中表结构要求 无 有序表 分段有序
（块之间有序）
10.3 索引查找表
10.4 树表查找（动态查找表）
动态查找表的特点是,表结构本身是在查找过程中动态生成的。
即查找不成功时，将该记录插入在动态查找表中。
一、二叉排序树（ Binary Sort Tree)（又称为二叉查找树）
1,BST定义：
BST或者是一棵空树；或者是具有如下性质的 BT:
若左子树非空，则左子树上所有结点的值均小于根结点的值；
若右子树非空，则右子树上所有结点的值均大于根结点的值；
左、右子树也为 BST
78
100
61
90
12
37
24
8
45
53
例如：
通常，取二叉链表作为二叉排序树的存储结构。中序遍历的结果的序列是有序的，即（ 8,12,24,37,45,53,61,78,90,100）。所以二叉排序树本身可以看成是个有序表，但是这棵树不是有序表构成的，
可以由一个无序序列，构造完以后是个有序表 。
二叉排序树的特点，是用非线形结构来表示一个线形有序表 。
10.4 树表查找（动态查找表）
2、查找过程为,
(1) 当前 BST非空时，将给定值 k与当前根结点的关键字比较,
(2) 若相等，查找成功，结束 ;
若 k小于当前根结点的关键字，则将左子树作为当前 BST;
若 k大于当前根结点的关键字，则将右子树作为当前 BST;
(3) 重复 (1),(2) 。
10.4 树表查找（动态查找表）
算法描述如下：
Status SearchBST (BiTree T,KeyType key,BiTree f,BiTree &p ) {
// 在根指针 T所指二叉排序树中递归地查找其关键字等于 key的数据元
//素，若查找成功，则指针 p指向该数据元素结点，并返回 TRUE，
//否则指针 p指向查找路径上访问的最后一个结点，并返回 FALSE，
//指针 f指向 T的双亲，其初始调用值为 NULL。
if (!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 );// 在右子树中继续查找
} // SearchBST
10.4 树表查找（动态查找表）
3,BST的插入对于动态查找表，在查找不成功的情况下，尚需插入关键字等于给定值的记录，并且从查找的过程容易得出插入的算法：
插入原则,若二叉排序树为空树，则新插入的结点为根结点；否则,
记下查找不成功时比较的最后一个结点的位置，将插入结点作为该结点的左或右孩子。
Status Insert_BST(BiTree &T,ElemType e ) {
// 当二叉排序树 T中不存在关键字等于 e.key的数据元素时，插入 e并返回 TRUE，否则返回 FALSE。
if (!SearchBST ( T,e.key,NULL,p )) { // 查找不成功
s = (BiTree) malloc (sizeof (BiTNode));
s->data = e; s->lchild = s->rchild = NULL;
10.4 树表查找（动态查找表）
if ( !p ) T = s; // 插入 s 为新的根结点,p是查找的结果
else if ( LT(e.key,p->data.key) ) p->.lchild = s// 插入 s 为左孩子
else p->.rchild = s; // 插入 s 为右孩子
return TRUE;}
else return FALSE;// 树中已有关键字相同的结点，不再插入
} // Insert BST
10.4 树表查找（动态查找表）
45
1
45
4
3
7
53
90
2
246
12
5
例：设 BST为空，
查找关键字序列为 {45,24,53,45,12,24,90}，
则经过一系列查找插入操作后，生成的 BST为：
10.4 树表查找（动态查找表）
4,BST的特点：
(1) 中序遍历 BST可得到一个关键字的有序序列。
如上例：中序遍历结果为,12,24,45,53,90
这是由于 BST中左子树的所有结点的值均小于其根结点的值，
右子树的所有结点的值均大于其根结点的值；
而中序遍历又是以 L DR顺序访问的。
10.4 树表查找（动态查找表）
(2) 在 BST上插入新结点时，不必移动其他结点，仅需改动某结点的指针（因新结点总是 BST上的一个新叶结点）。
(3) BST既具有类似折半查找的特性（与 BST的平衡度有关）又采用了链表存储结构（折半查找不能为链表存储结构），因此，对于经常要进行查找、插入和删除记录的有序表，采用 BST尤其合适。
10.4 树表查找（动态查找表）
5,BST的删除和插入相反，删除在查找成功之后进行删除的原则,
删除某个结点后仍保持 BST的特性。
设：被删除结点为 p↑(指针 p所指结点）
其双亲结点为 f ↑,且不失一般性，设 p 是 f 的左孩子。
10.4 树表查找（动态查找表）
c
q
C
SL
s
CL
F
FR
f
PR
p
P
Q
QL S
分三种情况讨论：
若 P结点为叶结点（即 PL和 PR均为空树，仅需将 f->lchild=NULL
若 P结点只有左子树 PL或只有右子树 PR,只需 令 PL或 PR为 f结点的左子树，即
f -> lchild= P-> lchild (或 P->rchild)
若 P↑结点左、右子树均不空，此时，按中序遍历序列为：
…C L C…Q L Q SL S P PR F FR…
删除 p后为,…C LC…Q L Q SL S PR F FR…
结果是将 PR作为 SR 。
10.4 树表查找（动态查找表）
C
SL
CL
PR
Q
QL S
F
S
SL
CL
F
PR
Q
QL
C
对 F的左孩子有两种处理办法：
(1) S不动，仍作为 Q的右孩子,C代替 P,作为 F的左孩子 ;
(2) S代替 P，而 SL为 QR ;
算法实现：
Status DeleteBST (BiTree &T,KeyType key ) {
// 若二叉排序树 T中存在关键字等于 key的数据元素时，则删除该数据元素
//结点 p，并返回 TRUE；否则返回 FALSE
if (!T) return FALSE;// 不存在关键字等于 key的数据元素
else
{if ( EQ (key,T->data.key) ) Delete (T);
// 找到关键字等于 key的数据元素
else if( LT (key,T->data.key) ) DeleteBST ( T->lchild,key );
else DeleteBST ( T->rchild,key );
return TRUE;}
} // DeleteBST
其中删除操作过程如下所描述：
void Delete ( BiTree &p ){
// 从二叉排序树中删除结点 p，并重接它的左或右子树
10.4 树表查找（动态查找表）
if (!p->rchild) // 右子树空则只需重接它的左子树
{ q = p; p = p->lchild; free(q);}
else if (!p->lchild) // 只需重接它的右子树
{ q = p; p = p->rchild; free(q);}
else // 左右子树均不空
{ q = p; s = p->rchild;
while (!s->lchild) { q = s; s = s->lchild; }
p->data = s->data;
if (q != p ) q->lchild = s->rchild;
else q->rchild = s->rchild; // 重接 *q的右子树
free(s);
}
} // Delete
10.4 树表查找（动态查找表）
6,BST 的查找分析
BST 上查找过程与折半查找类似，是从根结点到所找到结点的一条路径。与给定值比较次数等于该路径长度 +1（即结点所在层次数），最大次数不超过树的深度。
但长度为 n的折半查找表对应的判定树是唯一的。而含有 n个结点的 BST却不唯一
。
45
93
53
3712
24
(a)
(45,24,53,12,37,93)
12
24
37
45
53
93(b)
(12,24,37,45,53,93)
ASL(a)=1/6（ 1+2+2+3+3+3） =14/6
ASL(b)=1/6（ 1+2+3+4+5+6） =21/6
10.4 树表查找（动态查找表）
因此，含有 n个结点的 BST的 ASL和树的形态有关。
最差情况是 BST退化为单支树，其深度为 n，
ASL=(n+1)/2 (同顺序查找）。
最好情况与折半查找相同,ASL=log2n
随机情况下，平均查找长度为 1+4log n
为了避免出现单支树，在构成 BST的过程中可进行
“平衡化”处理。
10.4 树表查找（动态查找表）
二,平衡二叉树 (Balanced Binary Tree),又称为 AVL树
1,AVL树定义
AVL树或者是一棵空树，或者是具有下列性质的 BT:
左、右子树均为 AVL，
且任一左、右子树的深度之差的绝对值不超过 1.
称某结点左子树的深度－右子树的深度为该结点的 平衡因子 （ balance factor)
10.4 树表查找（动态查找表）
1
0
0
1
(a)
0
1
-1
0
0
2
(c)
0
1
0
0
-1
1
-1
(b)
例如：
结点中的值为该结点的平衡因子
10.4 树表查找（动态查找表）
2,AVL树的特点
AVL树上任何结点的平衡因子只可能为 -1,0或 1;
AVL树的深度与 log n同数量级 ;
AVL树的 ASL也与 log n同数量级 ;
完全二叉树一定是 AVL,当 AVL树不一定是完全二叉树
10.4 树表查找（动态查找表）
3,BST变为 AVL树
⑴ 例：设表的关键字序列为（ 13,24,37,90,53）,
BST生成过程为：
13
24
13
AVL AVL AVL
旋转
37
24
13
非 AVL
37
24
13
AVL
10.4 树表查找（动态查找表）
非 AVL
90
37
24
13
53
90
37
24
13
旋转 旋转
90
53
37
24
13
AVL
37 90
53
24
13
在 BST上插入结点而失去平衡，失去平衡后需进行调整,
调整 BST为二叉平衡（查找）树的 方法 是：在插入过程中，采用平衡旋转技术。
10.4 树表查找（动态查找表）
(2) 调整形态 (可归纳为四种 )
① LL型平衡旋转（顺时针）
失去平衡结点的平衡因子为 2,其左孩子的平衡因子为 1
LL
0
A
ARBR h-1h-1
0
B
BL h h
调整语句为：
b＝ a->lchild;
a-> lchild =b->rchild ; a-> bf=0
b-> rchild=a; b -> bf=0
2
A
a
AR h-11
B
BRBL h-1h
h+1
L+1
b
② LR型平衡旋转失去平衡结点的平衡因子为 2,其左孩子的平衡因子为 -1
2
A
AR h-1-1
B
BL
CL h-1
h-1
h+1
1
C h
h-2CR
LR
0
C
AR h-1
0
B
BL CL h-1h-1
-1
A
h-2CR
b＝ a->lchild; c= b->rchild；
a->lchild =c->rchild ; b-> rchild = c->lchild
C->rchild＝ a; c->lchild＝ b;
10.4 树表查找（动态查找表）
③ RR型平衡旋转（逆时针，与① LL对称 )
失去平衡点的平衡因子为 -2,其右孩子的平衡因子为 -1
-2
A
AL
BL h-1
h-1
-1
B
hBR
RR
0
B
BLAL h-1
0
A
BR
10.4 树表查找（动态查找表）
④ RL型平衡旋转失去平衡点的平衡因子为 -2,其右孩子的平衡因子为 1
RL
0
C
BR
0
A
AL CL
-1
B
h-2CR
1
B
BR h-1
-2
A
AL h-1
CL h-1
1
C
h-2CR
中序遍历,AL A CL C CR B BR AL A CL C CR B BR
10.4 树表查找（动态查找表）
在平衡树上进行查找的过程和二叉排序树相同，因此，查找过程中和给定值进行比较的关键字的个数不超过平衡树的深度。
假设深度为 h的二叉平衡树上所含结点数的最小值为 Nh，
则显然 Nh = Nh-1 + Nh-2 + 1由此可以推导出,h≈log （ n）
因此，在平衡树上进行查找的时间复杂度为 O(log(n))
平衡树的查找性能分析
10.5 哈希查找表前面介绍的查找算法,有一个共同特点,就是以待查关键字 k
在表中，通过一系列 比较 来确定该记录在表中的“地址”。
这一节将介绍另一种通过 计算 来查找的新型方法 -----哈希法
（ Hash）或称杂凑法、散列法。
设关键字集合为 A，地址空间为 D，哈希法就是在 A和 D之间建立一种函数关系 H，通过计算函数 H（ k），就能得到关键字 K的地址。
关键字集 A
m
地址空间 D
n
哈希函数
H（ k）
设 D是长度为 n的表，
A是含 m个记录的关键字集合，
如果存在一个 函数 H，使得对 A中任一关键字 Ki，均有，
0≤H（ Ki ） ≤n-1 i=1,2．．．,m
同时,Ki 所标识的记录 R i在表 D中的地址是 H(Ki)，
则称函数 H为关键字集合 A到地址空间 D之间的哈希函数，
地址空间 D为哈希表。
哈希函数并不一定是一对一的，例如，当 m＞ n时，对任何哈希函数 H，至少存在两个关键字 Ki ≠ Kj,使得 H(Ki) = H(Kj)，
这种对不同关键字而得到同一地址的现象，成为 冲突 。
10.5 哈希查找表因此，在应用哈希查找方法时，主要要解决两个技术问题：
一是构造好哈希函数的方法 ;
二是研究解决冲突的方法。
一,哈希函数构造方法一个好的哈希函数应满足下列两个条件：
计算简单容易
冲突极少
10.5 哈希查找表
1．直接哈希函数取关键字本身或关键字的某个线性函数值作为哈希地址，
即,H（ key） =key 或 H（ key） =a* key+b （ a,b为常数）
例如：有一个解放后出生人口调查表，每个记录包含年份、人数等数据项，其中年分为关键字，则哈希函数可取为,
H（ key） =key +（ -1948）
这样就可以方便地存储和查找 1948年后任一年的记录。
地址年份人数
01
1949
．．．．．．
．．．．．．
．．．．．．
22
1970
10.5 哈希查找表
2．数字分析法设ｎ个ｄ位数的关键字，由ｒ个不同的符号组成，此ｒ个符号在关键字的各位出现的频率不一定相同，可能在某些位上均匀分布，即每个符号出现的次数都接近于ｎ／ｒ次，而在另一些位上分布不均匀。 则选择其中分布均匀的 s位作为哈希地址，即 H（ key） =“key中数字均匀分布的 s位”，这便是数字分析哈希函数。
例：由 80个记录，关键字为 8位十进制数，（ n=80,r=10,d=8）
对关键字的各位进行分析，发现：第 1,2位都是,8,1”，第 3
位只取 1,2,3或 4，第 8位只取 2,5或 7，即 10个数在这四位分布不均匀，不取。可在剩下的 4,5,6,7位中任取两位，作为哈希地址。
10.5 哈希查找表
3．平方取中法取关键字平方后的中间几位作为哈希地址，即哈希函数为,
H（ key） =“key2的中间几位”
其中，所取的位数由哈希表的大小确定。
10.5 哈希查找表
4．折叠法将关键字分割成位数相等的几部分（最后一部分位数可以不同），取这几部分的叠加和（舍去高位的进位）作为哈希地址。位数由存储地址的位数确定。
相加时有两种方法：
一是移位叠加法，即将每部分得最后一位对齐，然后相加；
另一种是间界叠加法，即将关键字看作一纸条，从一端向另一端沿间界逐次折叠，然后对齐相加。
10.5 哈希查找表设关键字 key=d3 r．．,d 2 r+1d2 r．．,d r+1d r．．,d2d1
允许的存储地址有 r位。
则 移位叠加法为,d r．．,d2d1
d2 r,．,d r+1
+) d３ r,．,d 2 r+1
Sr,．,S2S1
10.5 哈希查找表
5．除留余数法取关键字被某个不大于哈希表长 m的数 p除后的余数为哈希地址。
即 H（ key） =key MOD p,p≤m
p的选择很重要，选得不好会产生很多冲突，
通常，选择 p≤ m的某个质数。
6．随机数法选择一个随机函数，取关键字的随机函数值作为它的哈希地址。
即 H（ key） =random（ key）
10.5 哈希查找表二,处理冲突的方法冲突 是指由关键字得到的 Hash地址上已有其他记录,
处理冲突 就是为该关键字找到另一个“空”的 Hash地址。
1,开放定址法
Hi =（ H（ key） +di） mod m i=1,2．．,m-1;
其中,Hi 为第 i次冲突的地址,
H（ key） 为 Hash函数值,
m 为 Hash表表长,
di 为增量序列
10.5 哈希查找表
Hi =（ H（ key） +di） mod m i=1,2．．,m-1;
其中,di为增量序列,有三种取法：
di =1,2,3．．,m-1 称为线性探测再散列
di =12,-12,22,-22,32．．,± k2 |± k|≤m-1
称为二次探测再散列
di =伪随机序列 称为伪随机探测再散列
10.5 哈希查找表例：设 m=16,表中已有关键字,分别为,19,70,33三个记录，
Hash函数取为 H（ key） = key mod13，现第四个关键字为 18的记录要填入表中，由 Hash函数得地址 5，产生冲突
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
70 19 33
70 19 33 18
H1 H2 H3
18 70 19 33
H2 H1
70 19 33
线性二次伪随机伪随机数序列 9．．．,H1＝１ 4 mod 16 =14
18
2,再哈希法
Hi =RHi （ key） i=1,2．．,n;
RHi 为不同哈希函数用 n个不同哈希函数排成一个序列,当发生冲突时,
由 RHi确定第 i次冲突的地址 Hi
10.5 哈希查找表
3,链地址法 将关键字发生冲突的记录存储在同一个线性链表中。
例,H（ key） = key mod 13
对关键字 19,14,23,01,68,20,84,27,55,11,10,79
处理的结果为：
0
1
2
3
4
5
6
7
8
9
10
11
12
79 01 14
6855
1984
20
2310
11
∧
∧
∧
∧
∧
∧
27
∧
∧
∧
∧
∧
∧
∧
0
1
2
3
4
5
6
7
8
9
10
11
12
∧
∧
68
∧
∧
19
20
∧
∧
23
11
∧
14
Hash表
01
27
55
10
79
84
溢出表顺序查找
4,公共溢出区法将同哈希表中关键字发生冲突的所有记录填入一个溢出表中,
例如上例的结果为：
10.5 哈希查找表数据结构的学习重点
1、如何描述一种新的抽象数据类型？
2、如何分析算法的优劣？
3、线性表的主要特征。
4、线性表的存储表示（顺序表示、单向链表、循环链表、
双向链表）
5、特殊的线性表：栈、队列、串、广义表
6、二叉树的定义、性质、存储结构、遍历算法
7、图的定义、术语、存储结构
8、静态查找表、二叉排序树、哈希函数的构造及冲突处理方法。
9、插入排序、快速排序、选择排序总复习
