第 10章 查找
10.1 查找的基本概念本章小结
10.2 线性表的查找
10.3 树表的查找
10.4 哈希表查找
10.1 查找的基本概念被查找的对象是由一组记录组成的表或文件,而每个记录则由若干个数据项组成,并假设每个记录都有一个能惟一标识该记录的关键字 。
在这种条件下,查找的定义是：给定一个值 k,在含有 n个记录的表中找出关键字等于 k的记录 。 若找到,则查找成功,返回该记录的信息或该记录在表中的位臵；否则查找失败,返回相关的指示信息 。
采用何种查找方法?
(1) 使用哪种数据结构来表示,表,,即表中记录是按何种方式组织的 。
(2) 表中关键字的次序 。 是对无序集合查找还是对有序集合查找?
若在查找的同时对表做修改运算 (如插入和删除 ),则相应的表称之为动态查找表,否则称之为静态查找表 。
由于查找运算的主要运算是关键字的比较,所以通常把查找过程中对关键字需要执行的平均比较次数 (也称为平均查找长度 )作为衡量一个查找算法效率优劣的标准 。 平均查找长度
ASL(Average Search Length)定义为：
n
1i ii
cpA S L
其中,n是查找表中记录的个数。 pi是查找第 i个记录的概率,一般地,均认为每个记录的查找概率相等,即 pi=1/n(1≤i≤n),ci
是找到第 i个记录所需进行的比较次数 。
10.2 线性表的查找在表的组织方式中,线性表是最简单的一种 。 三种在线性表上进行查找的方法：
(1) 顺序查找
(2) 二分查找
(3) 分块查找 。
因为不考虑在查找的同时对表做修改,故上述三种查找操作都是在静态查找表上实现的 。
查找与数据的存储结构有关,线性表有顺序和链式两种存储结构 。 本节只介绍以顺序表作为存储结构时实现的顺序查找算法 。 定义被查找的顺序表类型定义如下：
#define MAXL <表中最多记录个数 >
typedef struct
{ KeyType key; /*KeyType为关键字的数据类型 */
InfoType data; /*其他数据 */
} NodeType;
typedef NodeType SeqList[MAXL]; /*顺序表类型 */
10.2.1 顺序查找顺序查找是一种最简单的查找方法 。
它的基本思路是：从表的一端开始,顺序扫描线性表,依次将扫描到的关键字和给定值 k相比较,若当前扫描到的关键字与 k相等,
则查找成功；若扫描结束后,仍未找到关键字等于 k的记录,则查找失败 。
例如,在关键字序列为 {3,9,1,5,8,10,6,7,2,4}的线性表查找关键字为 6的元素 。
顺序查找过程如下：
开始,3 9 1 5 8 10 6 7 2 4
第 1次比较,3 9 1 5 8 10 6 7 2 4
i=0
第 2次比较,3 9 1 5 8 10 6 7 2 4
i=1
第 3次比较,3 9 1 5 8 10 6 7 2 4
i=2
第 4次比较,3 9 1 5 8 10 6 7 2 4
i=3
第 5次比较,3 9 1 5 8 10 6 7 2 4
i=4
第 6次比较,3 9 1 5 8 10 6 7 2 4
i=5
第 7次比较,3 9 1 5 8 10 6 7 2 4
i=6
查找成功,返回序号 6
顺序查找的算法如下 (在顺序表 R[0..n-1]中查找关键字为 k
的记录,成功时返回找到的记录位臵,失败时返回 -1)：
int SeqSearch(SeqList R,int n,KeyType k)
{ int i=0;
while (i<n && R[i].key!=k) i++; /*从表头往后找 */
if (i>=n)
return -1;
else
return i;
}
从顺序查找过程可以看到 (不考虑越界比较 i<n),ci取决于所查记录在表中的位臵。如查找表中第 1个记录 R[0]时,仅需比较一次；而查找表中最后一个记录 R[n-1]时,需比较 n次,即
ci=i。因此,成功时的顺序查找的平均查找长度为：
2
1n
2
)1n(n
n
1i
n
1
icipsqAS L
n
1i
n
1i
查找成功时的平均比较次数约为表长的一半 。
10.2.2 二分查找二分查找也称为折半查找要求线性表中的结点必须己按关键字值的递增或递减顺序排列 。 它首先用要查找的关键字 k
与中间位臵的结点的关键字相比较,这个中间结点把线性表分成了两个子表,若比较结果相等则查找完成 ;若不相等,再根据 k
与该中间结点关键字的比较大小确定下一步查找哪个子表,这样递归进行下去,直到找到满足条件的结点或者该线性表中没有这样的结点 。
例如,在关键字有序序列 {2,4,7,9,10,14,18,26,32,40}中采用二分查找法查找关键字为 7的元素 。
二分查找过程如下：
开始,2 4 7 9 10 14 18 26 32 40
low=0 high=9 mid=(0+9)/2=4
第 1次比较,2 4 7 9 10 14 18 26 32 40
low=0 high=3 mid=(0+3)/2=1
第 2次比较,2 4 7 9 10 14 18 26 32 40
low=2 high=3 mid=(2+3)/2=2
第 3次比较,2 4 7 9 10 14 18 26 32 40
R[2].key=7
查找成功,返回序号 2
其算法如下 (在有序表 R[0..n-1]中进行二分查找,成功时返回记录的位臵,失败时返回 -1)：
int BinSearch(SeqList R,int n,KeyType k)
{ int low=0,high=n-1,mid;
while (low<=high)
{ mid=(low+high)/2;
if (R[mid].key==k) /*查找成功返回 */
return mid;
if (R[mid].key>k) /*继续在 R[low..mid-1]中查找 */
high=mid-1;
else
low=mid+1; /*继续在 R[mid+1..high]中查找 */
}
return -1;
}
二分查找过程可用二叉树来描述,我们把当前查找区间的中间位臵上的记录作为根,左子表和右子表中的记录分别作为根的左子树和右子树,由此得到的二叉树,称为描述二分查找的判定树或比较树 。
5
2 8
0 3 6 9
- ∞ ～ - 1 1 2 ～ 3 4 5 ～ 6 7 8 ～ 9 10
0 ～ 1 1 ～ 2 3 ～ 4 4 ～ 5 6 ～ 7 7 ～ 8 9 ～ 10 10 ～ ∞
< >
=
< >
=
< > = <
>
=
< >
=
< > =
< > =
< > =
< > = < > = < > =
R[0..10]的二分查线的判定树 (n=11)
例 10.1 对于给定 11 个数据元素的有序表
{2,3,10,15,20,25,28,29,30,35,40},采用二分查找,试问：
(1)若查找给定值为 20的元素,将依次与表中哪些元素比较？
(2)若查找给定值为 26的元素,将依次与哪些元素比较？
(3)假设查找表中每个元素的概率相同,求查找成功时的平均查找长度和查找不成功时的平均查找长度 。
25
10 30
2 15 28 35
3 20 29 40
二分查找判定树
(2)若查找给定值为 26的元素,依次与 25,30,28元素比较,共比较 3次 。
(3)在查找成功时,会找到图中某个圆形结点,则成功时的平均查找长度：
311 44342211A S L s u c c ＝＝
(1)若查找给定值为 20的元素,依次与表中 25,10,15,20
元素比较,共比较 4
次 。
在查找不成功时,会找到图中某个方形结点,则不成功时的平均查找长度：
67.312 4834AS L u n s u c c ＝＝
10.2.3 分块查找分块查找又称索引顺序查找,它是一种性能介于顺序查找和二分查找之间的查找方法 。
它要求按如下的索引方式来存储线性表：将表 R[0..n-1]
均分为 b块,前 b-1块中记录个数为 s=?n/b?,最后一块即第 b块的记录数小于等于 s；每一块中的关键字不一定有序,但前一块中的最大关键字必须小于后一块中的最小关键字,即要求表是,分块有序,的；抽取各块中的最大关键字及其起始位臵构成一个索引表 IDX[0..b-1],即 IDX[i](0≤i≤b-1)中存放着第 i块的最大关键字及该块在表 R中的起始位臵 。 由于表 R是分块有序的,所以索引表是一个递增有序表 。
索引表的数据类型定义如下：
#define MAXI <索引表的最大长度 >
typedef struct
{ KeyType key; /*KeyType为关键字的类型 */
int link; /*指向对应块的起始下标 */
} IdxType;
typedef IdxType IDX[MAXI]; /*索引表类型 */
例如,设有一个线性表,其中包含 25个记录,其关键字序列为 {8,14,6,9,10,22,34,18,19,31,40,38,54,66,46,71,78,68,80,85,
100,94,88,96,87}。假设将 25个记录分为 5块,每块中有 5个记录,该线性表的索引存储结构如下图所示。
1 4 3 4 6 6 8 5 1 0 0
0 5 1 0 1 5 2 0
8 1 4 6 9 10 2 2 3 4 18 19 31 4 0 3 8 5 4 6 6 4 6 7 1 7 8 6 8 8 0 8 5 1 0 0 9 4 8 8 9 6 8 7
0 1 2 3 4 5 6 7 8 9 1 0 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 2 0 2 1 2 2 2 3 2 4
k ey
l i n k
采用二分查找索引表的分块查找算法如下 (索引表 I的长度为 m)：
int IdxSearch(IDX I,int m,SeqList R,int n,KeyType k)
{ int low=0,high=m-1,mid,i;
int b=n/m; /*b为每块的记录个数 */
while (low<=high) /*在索引中二分查找 */
{ mid=(low+high)/2;
if (I[mid].key>=k) high=mid-1;
else low=mid+1;
}
if (low<m) /*在块中顺序查找 */
{ i=I[low].link;
while (i<=I[low].link+b-1 && R[i].key!=k) i++;
if (i<=I[low].link+b-1) return i;
else return -1;
}
return -1;
}
若以二分查找来确定块,则分块查找成功时的平均查找长度为：
若以顺序查找确定块,则分块查找成功时的平均查找长度为：
2
s)1s/n(l o g
2
1s1)1h(l o gAS LAS LAS L
22sqbnb l k
s2
ns2s
2
1s
2
1bA S LA S LLAS 2
sqbnb l k
10.3 树表的查找当表的插入或删除操作频繁时,为维护表的有序性,需要移动表中很多记录 。 这种由移动记录引起的额外时间开销,就会抵消二分查找的优点 。 也就是说,二分查找只适用于静态查找表 。 若要对动态查找表进行高效率的查找,可采用下面介绍的几种特殊的二叉树或树作为表的组织形式,在这里将它们统称为树表 。 下面将分别讨论在这些树表上进行查找和修改操作的方法 。
10.3.1 二叉排序树二叉排序树 (简称 BST)又称二叉查找 (搜索 )树,其定义为：二叉排序树或者是空树,或者是满足如下性质的二叉树：
(1) 若它的左子树非空,则左子树上所有记录的值均小于根记录的值；
(2) 若它的右子树非空,则右子树上所有记录的值均大于根记录的值；
(3) 左,右子树本身又各是一棵二叉排序树 。
在讨论二叉排序树上的运算之前,定义其结点的类型如下：
typedef struct node /*记录类型 */
{ KeyType key; /*关键字项 */
InfoType data; /*其他数据域 */
struct node *lchild,*rchild; /*左右孩子指针 */
} BSTNode;
1,二叉排序树上的查找因为二叉排序树可看做是一个有序表,所以在二叉排序树上进行查找,和二分查找类似,也是一个逐步缩小查找范围的过程 。 递归查找算法 SearchBST()如下 (在二叉排序树 bt上查找关键字为 k的记录,成功时返回该结点指针,否则返回 NULL)：
BSTNode *SearchBST(BSTNode *bt,KeyType k)
{ if (bt==NULL || bt->key==k) /*递归终结条件 */
return bt;
if (k<bt->key)
return SearchBST(bt->lchild,k); /*在左子树中递归查找 */
else
return SearchBST(bt->rchild,k); /*在右子树中递归查找 */
}
2,二叉排序树的插入和生成在二叉排序树中插入一个新记录,要保证插入后仍满足
BST性质 。 其插入过程是：若二叉排序树 T为空,则创建一个
key域为 k的结点,将它作为根结点；否则将 k和根结点的关键字比较,若二者相等,则说明树中已有此关键字 k,无须插入,直接返回 0；若 k<T->key,则将 k插入根结点的左子树中,否则将它插入右子树中 。 对应的递归算法 InsertBST()如下：
int InsertBST(BSTNode *&p,KeyType k)
/*在以 *p为根结点的 BST中插入一个关键字为 k的结点 。 插入成功返回 1,否则返回 0*/
{ if (p==NULL) /*原树为空,新插入的记录为根结点 */
{ p=(BSTNode *)malloc(sizeof(BSTNode));
p->key=k;p->lchild=p->rchild=NULL;
return 1;
}
else if (k==p->key) /*存在相同关键字的结点,返回 0*/
return 0;
else if (k<p->key)
return InsertBST(p->lchild,k);/*插入到左子树中 */
else
return InsertBST(p->rchild,k); /*插入到右子树中 */
}
二叉排序树的生成,是从一个空树开始,每插入一个关键字,
就调用一次插入算法将它插入到当前已生成的二叉排序树中 。
从关键字数组 A[0..n-1]生成二叉排序树的算法 CreatBST()如下：
BSTNode *CreatBST(KeyType A[],int n) /*返回树根指针 */
{ BSTNode *bt=NULL; /*初始时 bt为空树 */
int i=0;
while (i<n)
{ InsertBST(bt,A[i]); /*将 A[i]插入二叉排序树 T中 */
i++;
}
return bt; /*返回建立的二叉排序树的根指针 */
}
例 10.2 已 知 一 组 关 键 字 为
{25,18,46,2,53,39,32,4,74,67,60,11} 。
按表中的元素顺序依次插入到一棵初始为空的二叉排序树中,画出该二叉排序树,并求在等概率的情况下查找成功的平均查找长度 。
解：生成的二叉排序树如右图所示 。
25
18 46
39 53 2
4
11
32 74
67
60
5.312 615243332211A S L
3,二叉排序树的删除删除操作必须首先进行查找,假设在查找过程结束时,已经保存了待删除结点及其双亲结点的地址 。 指针变量 p指向待删除的结点,指针变量 q指向待删除结点 p的双亲结点 。 删除过程如下：
(1) 若待删除的结点是叶子结点,直接删去该结点。如图 (a)
所示,直接删除结点 9。这是最简单的删除结点的情况。
5
2 6
1 4
3
7
8
9
( a )
删除结点 9
q
p
2 6
1 4
3
7
8
5
(2) 若待删除的结点只有左子树而无右子树 。 根据二叉排序树的特点,可以直接将其左子树的根结点放在被删结点的位臵 。 如图 (b)所示,*p作为 *q的右子树根结点,要删除 *p结点,只需将 *p的左子树 (其根结点为 3)作为 *q结点的右子树 。
( b )
删除结点 4
q
p
5
2 6
1 4
3
7
8
9
5
2 6
1 3 7
8
9
(3) 若待删除的结点只有右子树而无左子树 。 与 (2)情况类似,可以直接将其右子树的根结点放在被删结点的位臵 。 如图
(c)所示,*p作为 *q的左子树根结点,要删除 *p结点,只需将 *p的右子树 (其根结点为 8)作为 *q结点的右子树 。
( c )
删除结点 7 p
q
5
2 6
1 4
3
7
8
9
5
2 6
1 4
3
8
9
(4) 若待删除的结点同时有左子树和右子树 。 根据二叉排序树的特点,可以从其左子树中选择关键字最大的结点或从其右子树中选择关键字最小的结点放在被删去结点的位臵上 。 假如选取左子树上关键字最大的结点,那么该结点一定是左子树的最右下结点 。 如图 (d)所示,若要删除 *p(其关键字为 5)结点,找到其左子树最右下结点 4,它的双亲结点为 2,用它代替 *p结点,并将其原来的左子树 (其根结点为 3)作为原来的双亲结点 2的右子树 。
( d )
删除结点 5
p 5
2 6
1 4
3
7
8
9
4
2 6
1 3 7
8
9
删除二叉排序树结点的算法 DeleteBST()如下 (指针变量 p指向待删除的结点,指针变量 q指向待删除结点 *p的双亲结点 )：
void Delete1(BSTNode *p,BSTNode *&r)
/*当被删 *p结点有左右子树时的删除过程 */
{ BSTNode *q;
if (r->rchild!=NULL)
Delete1(p,r->rchild); /*递归找最右下结点 */
else /*找到了最右下结点 *r*/
{ p->key=r->key; /*将 *r的关键字值赋给 *p*/
q=r; r=r->lchild;
/*将左子树的根结点放在被删结点的位臵上 */
free(q); /*释放原 *r的空间 */
}
}
void Delete(BSTNode *&p) /*从二叉排序树中删除 *p结点 */
{ BSTNode *q;
if (p->rchild==NULL) /**p结点没有右子树的情况 */
{ q=p; p=p->lchild;
/*其右子树的根结点放在被删结点的位臵上 */
free(q);
}
else if (p->lchild==NULL) /**p结点没有左子树 */
{ q=p; p=p->rchild;
/*将 *p结点的右子树作为双亲结点的相应子树 /
free(q);
}
else Delete1(p,p->lchild);
/**p结点既没有左子树又没有右子树的情况 */
}
int DeleteBST(BSTNode *&bt,KeyType k)
/*在 bt中删除关键字为 k的结点 */
{ if (bt==NULL) return 0; /*空树删除失败 */
else
{ if (k<bt->key) return DeleteBST(bt->lchild,k);
/*递归在左子树中删除为 k的结点 */
else if (k>bt->key) return DeleteBST(bt->rchild,k);
/*递归在右子树中删除为 k的结点 */
else
{ Delete(bt); /*调用 Delete(bt)函数删除 *bt结点 */
return 1;
}
}
}
10.3.2 平衡二叉树若一棵二叉树中每个结点的左,右子树的高度至多相差
1,则称此二叉树为平衡二叉树 。 在算法中,通过平衡因子
(balancd factor,用 bf表示 )来具体实现上述平衡二叉树的定义 。
平衡因子的定义是：平衡二叉树中每个结点有一个平衡因子域,每个结点的平衡因子是该结点左子树的高度减去右子树的高度 。 从平衡因子的角度可以说,若一棵二叉树中所有结点的平衡因子的绝对值小于或等于 1,即平衡因子取值为 1,0或 -1,
则该二叉树称为平衡二叉树 。
5
2 6
1 4
3
7
1
0
- 1
0 1
0
- 1
3
1 4
2
5
6
7
(b )
(a )
0
- 1
- 2
- 3
- 2
- 1
0
平衡二叉树和不平衡二叉树定义 AVL树的结点的类型如下：
typedef struct node /*记录类型 */
{ KeyType key; /*关键字项 */
int bf; /*增加的平衡因子 */
InfoType data; /*其他数据域 */
struct node *lchild,*rchild; /*左右孩子指针 */
} BSTNode;
假定向平衡二叉树中插入一个新结点后破坏了平衡二叉树的平衡性,首先要找出插入新结点后失去平衡的最小子树根结点的指针,然后再调整这个子树中有关结点之间的链接关系,使之成为新的平衡子树 。 当失去平衡的最小子树被调整为平衡子树后,
原有其他所有不平衡子树无需调整,整个二叉排序树就又成为一棵平衡二叉树 。
失去平衡的最小子树是指以离插入结点最近,且平衡因子绝对值大于 1的结点作为根的子树 。 假设用 A表示失去平衡的最小子树的根结点,则调整该子树的操作可归纳为下列四种情况：
(1) LL型调整
(2) RR型调整
(3) LR型调整
(4) RL型调整例 10.3 输入关键字序列 {16,3,7,11,9,26,18,14,15},给出构造一棵 AVL树的步骤 。
16
0
( a) 插入 16
16
1
( b ) 插入 3
3
0
16
2
( c ) 插入 7
3
- 1
7
0
7
0
(d )LR 调整
3
0
16
0
7
- 1
( e ) 插入 11
3
0
16
1
11
0
7
- 2
( f ) 插入 9
3
0
16
2
11
1
9
0
7
- 1
( g ) LL 调整
3
0
1 1
0
9
0
16
0
7
- 2
3
0
1 1
- 1
9
0
16
- 1
( h ) 插入 26
26
0
7
0
3
0
1 1
0
9
0
16
- 1
26
0
( i ) RR 调整
7
0
3
0
1 1
- 1
9
0
16
- 2
26
1
( j ) 插入 18
18
0
7
0
3
0
1 1
0
9
0
18
0
26
0
( k ) RL 调整
16
0
7
0
3
0
1 1
- 1
9
0
18
1
26
0
16
1
( l ) 插入 14
14
0
7
0
3
0
1 1
- 2
9
0
18
2
26
0
16
2
( m ) 插入 15
14
- 1
15
0
7
0
3
0
1 1
- 1
9
0
18
1
26
0
15
0
0
14 16
0
( n ) L R 调整在平衡二叉树上进行查找的过程和在二叉排序树上进行查找的过程完全相同,因此,在平衡二叉树上进行查找关键字的比较次数不会超过平衡二叉树的深度 。
在最坏的情况下,普通二叉排序树的查找长度为 O(n)。 那么,
平衡二叉树的情况又是怎样的呢？ 下面分析平衡二叉树的高度 h
和结点个数 n之间的关系 。
首先,构造一系列的平衡二叉树 T1,T2,T3,…,其中,
Th（ h=1,2,3,… ） 是高度为 h且结点数尽可能少的平衡二叉树,
如图 10.12中所示的 T1,T2,T3和 T4。 为了构造 Th,先分别构造
Th-1和 Th-2,使 Th以 Th-1和 Th-2作为其根结点的左,右子树 。 对于每一个 Th,只要从中删去一个结点,就会失去平衡或高度不再是
h（ 显然,这样构造的平衡二叉树在结点个数相同的平衡二叉树中具有最大高度 ） 。
T 1
T 2
T 3
T 4
T h
T h - 1 T h - 2
图 10.12 结点个数 n最少的平衡二叉树然后,通过计算上述平衡二叉树中的结点个数,来建立高度与结点个数之间的关系 。 设 N(h)为 Th的结点数,从图 10.12中可以看出有下列关系成立：
N(1)=1,N(2)=2,N(h)=N(h-1)+N(h-2)
当 h>1时,此关系类似于定义 Fibonacci数的关系：
F(1)=1,F(2)=1,F(h)=F(h-1)+F(h-2)
通过检查两个序列的前几项就可发现两者之间的对应关系：
N(h)=F(h+2)-1
由于 Fibonacci数满足渐近公式,F(h)=
其中,
故由此可得近似公式,N(h)=
即,h≈log2(N(h)+1)
所以,含有 n个结点的平衡二叉树的平均查找长度为 O(log2n)。
h51
2
51
12151 h2h
10.3.3 B-树
B-树又称为多路平衡查找树,是一种组织和维护外存文件系统非常有效的数据结构 。
B-树中所有结点的孩子结点最大值称为 B-树的阶,通常用
m表示,从查找效率考虑,要求 m≥3。 一棵 m阶 B-树或者是一棵空树,或者是满足下列要求的 m叉树：
(1) 树中每个结点至多有 m个孩子结点 (即至多有 m-1个关键字 )；
(2) 除根结点外,其他结点至少有?m/2?个孩子结点 (即至少有?m/2?-1=?(m-1)/2?个关键字 )；
(3) 若根结点不是叶子结点,则根结点至少有两个孩子结点；
(4) 每个结点的结构为：
n p0 k1 p1 k2 p2 … kn pn
其中,n为该结点中的关键字个数,除根结点外,其他所有结点的 n大于等于?m/2?-1,且小于等于 m-1； ki(1≤i≤n)为该结点的关键字且满足 ki＜ ki+1； pi(0≤i≤n)为该结点的孩子结点指针且满足 pi(0≤i≤n-1)结点上的关键字大于等于 ki且小于
ki+1,pn结点上的关键字大于 kn。
(5) 所有叶子结点都在同一层上,即 B-树是所有结点的平衡因子均等于 0的多路查找树 。
3 ∧ 12 ∧ 15 ∧ 22 ∧ 2 ∧ 2 ∧ 7 ∧ 2 ∧ 35 ∧ 41 ∧ 3 ∧ 53 ∧ 54 ∧ 63 ∧ 4 ∧ 68 ∧ 69 ∧ 71 ∧ 76 ∧ 3 ∧ 79 ∧ 84 ∧ 93 ∧
2? 11? 30? 2? 66? 78?
1? 51?
一棵 5阶 B-树在 B-树的存储结构中,各结点的类型定义如下：
#define MAXM 10 /*定义 B-树的最大的阶数 */
typedef int KeyType; /*KeyType为关键字类型 */
typedef struct node /*B-树结点类型定义 */
{ int keynum; /*结点当前拥有的关键字的个数 */
KeyType key[MAXM]; /*[1..keynum]存放关键字,[0]不用 */
struct node *parent; /*双亲结点指针 */
struct node *ptr[MAXM];/*孩子结点指针数组 [0..keynum]*/
} BTNode;
1,B-树的查找在 B-树中查找给定关键字的方法类似于二叉排序树上的查找,不同的是在每个记录上确定向下查找的路径不一定是二路
(即二叉 )的,而是 n+1路的 。 因为记录内的关键字序列是有序的数量 key[1..n],故既可以用顺序查找,也可以用折半查找 。 在一棵 B-树上顺序查找关键字为 k的方法为：将 k与根结点中的
key[i]进行比较：
(1) 若 k=key[i],则查找成功；
(2) 若 k＜ key[1],则沿着指针 ptr[0]所指的子树继续查找；
(3) 若 key[i]＜ k＜ key[i+1],则沿着指针 ptr[i]所指的子树继续查找；
(4) 若 k＞ key[n],则沿着指针 ptr[n]所指的子树继续查找 。
2,B-树的插入将关键字 k插入到 B-树的过程分两步完成：
(1) 利用前述的 B-树的查找算法找出该关键字的插入结点 (注意
B-树的插入结点一定是叶子结点 )。
(2) 判断该结点是否还有空位臵,即判断该结点是否满足 n＜ m-
1,若该结点满足 n＜ m-1,说明该结点还有空位臵,直接把关键字 k插入到该结点的合适位臵上 (即满足插入后结点上的关键字仍保持有序 )；若该结点有 n=m-1,说明该结点已没有空位臵,需要把结点分裂成两个 。 分裂的做法是,取一新结点,把原结点上的关键字和 k
按升序排序后,从中间位臵 (即?m/2?=?(m+1)/2?之处 )把关键字 (不包括中间位臵的关键字 )分成两部分,左部分所含关键字放在旧结点中,右部分所含关键字放在新结点中,中间位臵的关键字连同新结点的存储位臵插入到父亲结点中 。 如果父结点的关键字个数也超过 Max,则要再分裂,再往上插,直至这个过程传到根结点为止 。
例如 关键字序列为：
{1,2,6,7,11,4,8,13,10,5,17,9,16,20,3,12,14,18,19,15}。
创建一棵 5阶 B-树 。
建立 B-的过程如下图所示 。
1 2 6 7
6
1 2 7 1 1
6
1 2 4 7 8 1 1 1 3
6 1 0
1 2 4 1 1 1 3 7 8
6 1 0
1 2 4 5 1 1 1 3 1 6
17
7 8 9
6 1 0 1 6
1 2 4 5 7 8 9
3 6 1 0 16
1 2 7 8 9 1 7 1 8 1 9 2 0 4 5
10
1 4 1 5
1 3 1 6 3 6
1 2 7 8 9
(a ) 插入 1,2,6,7 (b ) 插入 11 (c ) 插入 4,8,1 3 (d ) 插入 10
(e ) 插入 5,1 7,9,1 6 (f) 插入 20
(g ) 插入 3,1 2,1 4,1 8,1 9 (h ) 插入 15
1 1 1 3 1 7 2 0
1 7 1 8 1 9 2 0
1 1 1 2 1 3 1 4
4 5 1 1 1 2
3,B-树的删除
B-树的删除过程与插入过程类似,只是稍为复杂一些 。 要使删除后的结点中的关键字个数 ≥?m/2?-1,将涉及到结点的,合并,问题 。 在 B-树上删除关键字 k的过程分两步完成：
(1) 利用前述的 B-树的查找算法找出该关键字所在的结点 。
(2) 在结点上删除关键字 k分两种情况：一种是在叶子结点上删除关键字；另一种是在非叶子结点上删除关键字 。
(3) 在非叶子结点上删除关键字的过程：假设要删除关键字
key[i](1≤i≤n),在删去该关键字后,以该结点 ptr[i]所指子树中的最小关键字 key[min]来代替被删关键字 key[i]所在的位臵 (注意 ptr[i]
所指子树中的最小关键字 key[min]一定是在叶子结点上 ),然后再以指针 ptr[i]所指结点为根结点查找并删除 key[min](即再以 ptr[i]
所指结点为 B-树的根结点,以 key[min]为要删除的关键字,然后再次调用 B-树上的删除算法 ),这样也就把在非叶子结点上删除关键字 k的问题转化成了在叶子结点上删除关键字 key[min]的问题 。
(4) 在 B-树的叶子结点上删除关键字共有以下三种情况：
① 假如被删结点的关键字个数大于 Min,说明删去该关键字后该结点仍满足 B-树的定义,则可直接删去该关键字 。
② 假如被删结点的关键字个数等于 Min,说明删去关键字后该结点将不满足 B-树的定义,此时若该结点的左 (或右 )兄弟结点中关键字个数大于 Min,则把该结点的左 (或右 )兄弟结点中最大 (或最小 )的关键字上移到双亲结点中,同时把双亲结点中大于 (或小于 )
上移关键字的关键字下移到要删除关键字的结点中,这样删去关键字 k后该结点以及它的左 (或右 )兄弟结点都仍旧满足 B-树的定义 。
③ 假如被删结点的关键字个数等于 Min,并且该结点的左和右兄弟结点 (如果存在的话 )中关键字个数均等于 Min,这时,需把要删除关键字的结点与其左 (或右 )兄弟结点以及双亲结点中分割二者的关键字合并成一个结点 。 如果因此使双亲结点中关键字个数小于 Min,则对此双亲结点做同样处理,以致于可能直到对根结点做这样的处理而使整个树减少一层 。
例如,对于上例生成的 B-树,给出删除 8,16,15,4等四个关键字的过程 。
10
3 6 13 17
1 2 4 5 7 9 1 1 12 14 15 18 19 20
(a ) 初始 5 阶 B - 树 (b ) 删除 8,16 后的结果
10
3 6 13 18
1 2 4 5 1 1 12 14 17 19 20
(c ) 删除 15 后的结果
6 10 13 18
1 2 3 5 7 9 14 17 19 20
(d ) 删除 4 后的结果
7 9
1 1 12
10
14 15
13 16 3 6
1 2 7 8 9 17 18 19 20 4 5 1 1 12
10.3.4 B+树在索引文件组织中,经常使用 B-树的一些变形,其中 B+树是一种应用广泛的变形 。 一棵 m阶 B+树满足下列条件：
(1) 每个分支结点至多有 m棵子树 。
(2) 除根结点外,其他每个分支结点至少有?(m+1)/2?棵子树 。
(3) 根结点至少有两棵子树,至多有 m棵子树 。
(4) 有 n棵子树的结点有 n个关键字 。
(5) 所有叶子结点包含全部 (数据文件中记录 ) 关键字及指向相应记录的指针 (或存放数据文件分块后每块的最大关键字及指向该块的指针 ),而且叶子结点按关键字大小顺序链接 (可以把每个叶子结点看成是一个基本索引块,它的指针不再指向另一级索引块,而是直接指向数据文件中的记录 )。
(6) 所有分支结点 (可看成是索引的索引 )中仅包含它的各个子结点 (即下级索引的索引块 )中最大关键字及指向子结点的指针 。
33
1 8 2 3 48
1 0 1 2 1 5 1 8 1 9 2 0 2 1 2 2 2 3 3 0 3 1 3 3 4 5 4 7 4 8 5 0 5 2
一棵 4阶的 B+树
m阶的 B+树和 m阶的 B-树,定义中的前三点是相同的,主要的差异是：
(1) 在 B+树中,具有 n个关键字的结点含有 n棵子树,即每个关键字对应一棵子树,而在 B-树中,具有 n个关键字的结点含有 (n+1)
棵子树 。
(2) 在 B+树中,每个结点 (除根结点外 )中的关键字个数 n的取值范围是?m/2?≤n ≤m,根结点 n的取值范围是 1≤n≤m；而在 B-树中,
它们的取值范围分别是?m/2?-1≤n≤m-1和 1≤n≤m-1。
(3) B+树中的所有叶子结点包含了全部关键字,即其他非叶子结点中的关键字包含在叶子结点中,而在 B-树中,叶子结点包含的关键字与其他结点包含的关键字是不重复的 。
(4) B+树中所有非叶子结点仅起到索引的作用,即结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针,不含有该关键字对应记录的存储地址 。 而在 B-树中,每个关键字对应一个记录的存储地址 。
(5) 通常在 B+树上有两个头指针,一个指向根结点,另一个指向关键字最小的叶子结点,所有叶子结点链接成一个不定长的线性链表 。
10.4 哈希表查找
10.4.1 哈希表的基本概念哈希表 (Hash Table)又称散列表,是除顺序表存储结构、链接表存储结构和索引表存储结构之外的又一种存储线性表的存储结构。哈希表存储的基本思路是：设要存储的对象个数为 n,
设臵一个长度为 m(m≥n)的连续内存单元,以线性表中每个对象的关键字 ki(0≤i≤n-1)为自变量,通过一个称为哈希函数的函数
h(ki),把 ki映射为内存单元的地址 (或称下标 )h(ki),并把该对象存储在这个内存单元中。 h(ki)也称为哈希地址 (又称散列地址 )。
把如此构造的线性表存储结构称为 哈希表。
但是存在这样的问题,对于两个关键字 ki和 kj(i≠j),有
ki≠kj(i≠j),但 h(ki)=h(kj)。 我们把这种现象叫做 哈希冲突 。
通常把这种具有不同关键字而具有相同哈希地址的对象称做,同义词,,由同义词引起的冲突称作 同义词冲突 。 在哈希表存储结构的存储中,同义词冲突是很难避免的,除非关键字的变化区间小于等于哈希地址的变化区间,而这种情况当关键字取值不连续时是非常浪费存储空间的 。 通常的实际情况是关键字的取值区间远大于哈希地址的变化区间 。
归纳起来：
(1)哈希函数是一个映象,即：将关键字的集合映射到某个地址集合上,它的设臵很灵活,只要这个地址集合的 大小不超出允许范围即可；
(2)由于哈希函数是一个压缩映象,因此,在一般情况下,很容易产生,冲突,现象,即,key1?key2,而 f(key1) = f(key2)。
(3) 很难找到一个不产生冲突的哈希函数 。 一般情况下,
只能选择恰当的哈希函数,使冲突尽可能少地产生 。
10.4.2 哈希函数构造方法构造哈希函数的目标是使得到的哈希地址尽可能均匀地分布在 n个连续内存单元地址上,同时使计算过程尽可能简单以达到尽可能高的时间效率 。
1,直接定址法直接定址法是以关键字 k本身或关键字加上某个数值常量 c
作为哈希地址的方法 。 直接定址法的哈希函数 h(k)为：
h(k)=k+c (c≥0)
这种哈希函数计算简单,并且不可能有冲突发生 。 当关键字的分布基本连续时,可用直接定址法的哈希函数；否则,若关键字分布不连续将造成内存单元的大量浪费 。
2,除留余数法除留余数法是用关键字 k除以某个不大于哈希表长度 m的数 p所得的余数作为哈希地址的方法 。 除留余数法的哈希函数
h(k)为：
h(k)=k mod p (mod为求余运算,p≤m)
3,数字分析法该方法是提取关键字中取值较均匀的数字位作为哈希地址的方法 。 它适合于所有关键字值都已知的情况,并需要对关键字中每一位的取值分布情况进行分析 。
例如,对于一组关键字：
{92317602,92326875,92739628,92343634,92706816,92774638,92
381262,92394220}
通过分析可知,每个关键字从左到右的第 1,2,3位和第 6位取值较集中,不宜作为哈希函数,剩余的第 4,5,7和 8位取值较分散,可根据实际需要取其中的若干位作为哈希地址 。 若取最后 两 位 作 为 哈 希 地 址,则 哈 希 地 址 的 集 合 为
{2,75,28,34,16,38,62,20}。
例 10.4 假设哈希表长度 m=13,采用除留余数法哈希函数建立如下关键字集合的哈希表：
{16,74,60,43,54,90,46,31,29,88,77}。
解,n=11,m=13,除留余数法的哈希函数为 h(k)=k mod
p,p应为小于等于 m的素数,假设 p取值 13。 则有：
h(16)=3,h(74)=9,h(60)=8,h(43)=4,
h(54)=2,h(90)=12,h(46)=7,h(31)=5,
h(29)=3,h(88)=10,h(77)=12。
10.4.3 哈希冲突解决方法
1,开放定址法开放定址法是一类以发生冲突的哈希地址为自变量,通过某种哈希冲突函数得到一个新的空闲的哈希地址的方法。
(1)线性探查法 。 线性探查法是从发生冲突的地址 (设为
d)开始,依次探查 d的下一个地址 (当到达下标为 m-1的哈希表表尾时,下一个探查的地址是表首地址 0),直到找到一个空闲单元为止 (当 m≥n时一定能找到一个空闲单元 )。 线性探查法的数学递推描述公式为：
d0=h(k)
di=(di-1+1) mod m (1≤i≤m-1)
(2)平方探查法 。 设发生冲突的地址为 d,则平方探查法的探查序列为,d+12,d+22,… 。 平方探查法的数学描述公式为：
d0=h(k)
di=(d0+i2) mod m (1≤i≤m-1)
平方探查法是一种较好的处理冲突的方法,可以避免出现堆积问题 。 它的缺点是不能探查到哈希表上的所有单元,但至少能探查到一半单元 。
例 10.5 对上例构造的哈希表采用线性探查法解决冲突 。
解,h(16)=3,h(74)=9,h(60)=8,h(43)=4,
h(54)=2,h(90)=12,h(46)=7,h(31)=5,
h(29)=3 冲突
d0=3,d1=(3+1) mod 13=4 仍冲突
d2=(4+1) mod 13=5 仍冲突
d3=(5+1) mod 13=6
h(88)=10
h(77)=12 冲突
d0=12,d1=(12+1) mod 13=0
建立的哈希表 ha[0..12]如下表所示 。
下标 0 1 2 3 4 5 6 7 8 9 10 11 12
k 77 54 16 43 31 29 46 60 74 88 90
探查次数 2 1 1 1 1 4 1 1 1 1 1
哈希表 ha[0..12]
2,拉链法拉链法是把所有的同义词用单链表链接起来的方法 。 在这种方法中,哈希表每个单元中存放的不再是记录本身,而是相应同义词单链表的头指针 。 由于单链表中可插入任意多个结点,所以此时装填因子 α根据同义词的多少既可以设定为大于 1,
也可以设定为小于或等于 1,通常取 α=1。
例 10.6 对上例构造的哈希表采用拉链法解决冲突 。
解：采用拉链法解决冲突建立的链表如下图所示 。
∧
∧
∧
∧
0
1
2
3
4
5
6
7
8
9
10
11
12
5 4 ∧
7 4 ∧
8 8 ∧
4 6 ∧
6 0 ∧
3 1 ∧
4 3 ∧
2 9 1 6 ∧
7 7 9 0 ∧
下标 哈希表本章小结本章基本学习要点如下：
(1) 理解查找的基本概念,包括静态查找表和动态查找表,内查找和外查找之间的差异 。
(2) 重点掌握线性表上各种查找算法,包括顺序查找,
二分查找和分块查找的基本思路,算法实现和查找效率等 。
(3) 掌握各种树表的查找算法,包括二叉排序树,AVL
树和 B-树的基本思路,算法实现和查找效率等 。
(4) 掌握哈希表查找技术以及哈希表与其他表的本质区别 。
(5) 灵活运用各种查找算法解决一些综合应用问题 。
练习教材中 p265习题 1,2,3和 5。
上机实习题教材中 p166题 3和 5。
10.1 查找的基本概念本章小结
10.2 线性表的查找
10.3 树表的查找
10.4 哈希表查找
10.1 查找的基本概念被查找的对象是由一组记录组成的表或文件,而每个记录则由若干个数据项组成,并假设每个记录都有一个能惟一标识该记录的关键字 。
在这种条件下,查找的定义是：给定一个值 k,在含有 n个记录的表中找出关键字等于 k的记录 。 若找到,则查找成功,返回该记录的信息或该记录在表中的位臵；否则查找失败,返回相关的指示信息 。
采用何种查找方法?
(1) 使用哪种数据结构来表示,表,,即表中记录是按何种方式组织的 。
(2) 表中关键字的次序 。 是对无序集合查找还是对有序集合查找?
若在查找的同时对表做修改运算 (如插入和删除 ),则相应的表称之为动态查找表,否则称之为静态查找表 。
由于查找运算的主要运算是关键字的比较,所以通常把查找过程中对关键字需要执行的平均比较次数 (也称为平均查找长度 )作为衡量一个查找算法效率优劣的标准 。 平均查找长度
ASL(Average Search Length)定义为：
n
1i ii
cpA S L
其中,n是查找表中记录的个数。 pi是查找第 i个记录的概率,一般地,均认为每个记录的查找概率相等,即 pi=1/n(1≤i≤n),ci
是找到第 i个记录所需进行的比较次数 。
10.2 线性表的查找在表的组织方式中,线性表是最简单的一种 。 三种在线性表上进行查找的方法：
(1) 顺序查找
(2) 二分查找
(3) 分块查找 。
因为不考虑在查找的同时对表做修改,故上述三种查找操作都是在静态查找表上实现的 。
查找与数据的存储结构有关,线性表有顺序和链式两种存储结构 。 本节只介绍以顺序表作为存储结构时实现的顺序查找算法 。 定义被查找的顺序表类型定义如下：
#define MAXL <表中最多记录个数 >
typedef struct
{ KeyType key; /*KeyType为关键字的数据类型 */
InfoType data; /*其他数据 */
} NodeType;
typedef NodeType SeqList[MAXL]; /*顺序表类型 */
10.2.1 顺序查找顺序查找是一种最简单的查找方法 。
它的基本思路是：从表的一端开始,顺序扫描线性表,依次将扫描到的关键字和给定值 k相比较,若当前扫描到的关键字与 k相等,
则查找成功；若扫描结束后,仍未找到关键字等于 k的记录,则查找失败 。
例如,在关键字序列为 {3,9,1,5,8,10,6,7,2,4}的线性表查找关键字为 6的元素 。
顺序查找过程如下：
开始,3 9 1 5 8 10 6 7 2 4
第 1次比较,3 9 1 5 8 10 6 7 2 4
i=0
第 2次比较,3 9 1 5 8 10 6 7 2 4
i=1
第 3次比较,3 9 1 5 8 10 6 7 2 4
i=2
第 4次比较,3 9 1 5 8 10 6 7 2 4
i=3
第 5次比较,3 9 1 5 8 10 6 7 2 4
i=4
第 6次比较,3 9 1 5 8 10 6 7 2 4
i=5
第 7次比较,3 9 1 5 8 10 6 7 2 4
i=6
查找成功,返回序号 6
顺序查找的算法如下 (在顺序表 R[0..n-1]中查找关键字为 k
的记录,成功时返回找到的记录位臵,失败时返回 -1)：
int SeqSearch(SeqList R,int n,KeyType k)
{ int i=0;
while (i<n && R[i].key!=k) i++; /*从表头往后找 */
if (i>=n)
return -1;
else
return i;
}
从顺序查找过程可以看到 (不考虑越界比较 i<n),ci取决于所查记录在表中的位臵。如查找表中第 1个记录 R[0]时,仅需比较一次；而查找表中最后一个记录 R[n-1]时,需比较 n次,即
ci=i。因此,成功时的顺序查找的平均查找长度为：
2
1n
2
)1n(n
n
1i
n
1
icipsqAS L
n
1i
n
1i
查找成功时的平均比较次数约为表长的一半 。
10.2.2 二分查找二分查找也称为折半查找要求线性表中的结点必须己按关键字值的递增或递减顺序排列 。 它首先用要查找的关键字 k
与中间位臵的结点的关键字相比较,这个中间结点把线性表分成了两个子表,若比较结果相等则查找完成 ;若不相等,再根据 k
与该中间结点关键字的比较大小确定下一步查找哪个子表,这样递归进行下去,直到找到满足条件的结点或者该线性表中没有这样的结点 。
例如,在关键字有序序列 {2,4,7,9,10,14,18,26,32,40}中采用二分查找法查找关键字为 7的元素 。
二分查找过程如下：
开始,2 4 7 9 10 14 18 26 32 40
low=0 high=9 mid=(0+9)/2=4
第 1次比较,2 4 7 9 10 14 18 26 32 40
low=0 high=3 mid=(0+3)/2=1
第 2次比较,2 4 7 9 10 14 18 26 32 40
low=2 high=3 mid=(2+3)/2=2
第 3次比较,2 4 7 9 10 14 18 26 32 40
R[2].key=7
查找成功,返回序号 2
其算法如下 (在有序表 R[0..n-1]中进行二分查找,成功时返回记录的位臵,失败时返回 -1)：
int BinSearch(SeqList R,int n,KeyType k)
{ int low=0,high=n-1,mid;
while (low<=high)
{ mid=(low+high)/2;
if (R[mid].key==k) /*查找成功返回 */
return mid;
if (R[mid].key>k) /*继续在 R[low..mid-1]中查找 */
high=mid-1;
else
low=mid+1; /*继续在 R[mid+1..high]中查找 */
}
return -1;
}
二分查找过程可用二叉树来描述,我们把当前查找区间的中间位臵上的记录作为根,左子表和右子表中的记录分别作为根的左子树和右子树,由此得到的二叉树,称为描述二分查找的判定树或比较树 。
5
2 8
0 3 6 9
- ∞ ～ - 1 1 2 ～ 3 4 5 ～ 6 7 8 ～ 9 10
0 ～ 1 1 ～ 2 3 ～ 4 4 ～ 5 6 ～ 7 7 ～ 8 9 ～ 10 10 ～ ∞
< >
=
< >
=
< > = <
>
=
< >
=
< > =
< > =
< > =
< > = < > = < > =
R[0..10]的二分查线的判定树 (n=11)
例 10.1 对于给定 11 个数据元素的有序表
{2,3,10,15,20,25,28,29,30,35,40},采用二分查找,试问：
(1)若查找给定值为 20的元素,将依次与表中哪些元素比较？
(2)若查找给定值为 26的元素,将依次与哪些元素比较？
(3)假设查找表中每个元素的概率相同,求查找成功时的平均查找长度和查找不成功时的平均查找长度 。
25
10 30
2 15 28 35
3 20 29 40
二分查找判定树
(2)若查找给定值为 26的元素,依次与 25,30,28元素比较,共比较 3次 。
(3)在查找成功时,会找到图中某个圆形结点,则成功时的平均查找长度：
311 44342211A S L s u c c ＝＝
(1)若查找给定值为 20的元素,依次与表中 25,10,15,20
元素比较,共比较 4
次 。
在查找不成功时,会找到图中某个方形结点,则不成功时的平均查找长度：
67.312 4834AS L u n s u c c ＝＝
10.2.3 分块查找分块查找又称索引顺序查找,它是一种性能介于顺序查找和二分查找之间的查找方法 。
它要求按如下的索引方式来存储线性表：将表 R[0..n-1]
均分为 b块,前 b-1块中记录个数为 s=?n/b?,最后一块即第 b块的记录数小于等于 s；每一块中的关键字不一定有序,但前一块中的最大关键字必须小于后一块中的最小关键字,即要求表是,分块有序,的；抽取各块中的最大关键字及其起始位臵构成一个索引表 IDX[0..b-1],即 IDX[i](0≤i≤b-1)中存放着第 i块的最大关键字及该块在表 R中的起始位臵 。 由于表 R是分块有序的,所以索引表是一个递增有序表 。
索引表的数据类型定义如下：
#define MAXI <索引表的最大长度 >
typedef struct
{ KeyType key; /*KeyType为关键字的类型 */
int link; /*指向对应块的起始下标 */
} IdxType;
typedef IdxType IDX[MAXI]; /*索引表类型 */
例如,设有一个线性表,其中包含 25个记录,其关键字序列为 {8,14,6,9,10,22,34,18,19,31,40,38,54,66,46,71,78,68,80,85,
100,94,88,96,87}。假设将 25个记录分为 5块,每块中有 5个记录,该线性表的索引存储结构如下图所示。
1 4 3 4 6 6 8 5 1 0 0
0 5 1 0 1 5 2 0
8 1 4 6 9 10 2 2 3 4 18 19 31 4 0 3 8 5 4 6 6 4 6 7 1 7 8 6 8 8 0 8 5 1 0 0 9 4 8 8 9 6 8 7
0 1 2 3 4 5 6 7 8 9 1 0 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 2 0 2 1 2 2 2 3 2 4
k ey
l i n k
采用二分查找索引表的分块查找算法如下 (索引表 I的长度为 m)：
int IdxSearch(IDX I,int m,SeqList R,int n,KeyType k)
{ int low=0,high=m-1,mid,i;
int b=n/m; /*b为每块的记录个数 */
while (low<=high) /*在索引中二分查找 */
{ mid=(low+high)/2;
if (I[mid].key>=k) high=mid-1;
else low=mid+1;
}
if (low<m) /*在块中顺序查找 */
{ i=I[low].link;
while (i<=I[low].link+b-1 && R[i].key!=k) i++;
if (i<=I[low].link+b-1) return i;
else return -1;
}
return -1;
}
若以二分查找来确定块,则分块查找成功时的平均查找长度为：
若以顺序查找确定块,则分块查找成功时的平均查找长度为：
2
s)1s/n(l o g
2
1s1)1h(l o gAS LAS LAS L
22sqbnb l k
s2
ns2s
2
1s
2
1bA S LA S LLAS 2
sqbnb l k
10.3 树表的查找当表的插入或删除操作频繁时,为维护表的有序性,需要移动表中很多记录 。 这种由移动记录引起的额外时间开销,就会抵消二分查找的优点 。 也就是说,二分查找只适用于静态查找表 。 若要对动态查找表进行高效率的查找,可采用下面介绍的几种特殊的二叉树或树作为表的组织形式,在这里将它们统称为树表 。 下面将分别讨论在这些树表上进行查找和修改操作的方法 。
10.3.1 二叉排序树二叉排序树 (简称 BST)又称二叉查找 (搜索 )树,其定义为：二叉排序树或者是空树,或者是满足如下性质的二叉树：
(1) 若它的左子树非空,则左子树上所有记录的值均小于根记录的值；
(2) 若它的右子树非空,则右子树上所有记录的值均大于根记录的值；
(3) 左,右子树本身又各是一棵二叉排序树 。
在讨论二叉排序树上的运算之前,定义其结点的类型如下：
typedef struct node /*记录类型 */
{ KeyType key; /*关键字项 */
InfoType data; /*其他数据域 */
struct node *lchild,*rchild; /*左右孩子指针 */
} BSTNode;
1,二叉排序树上的查找因为二叉排序树可看做是一个有序表,所以在二叉排序树上进行查找,和二分查找类似,也是一个逐步缩小查找范围的过程 。 递归查找算法 SearchBST()如下 (在二叉排序树 bt上查找关键字为 k的记录,成功时返回该结点指针,否则返回 NULL)：
BSTNode *SearchBST(BSTNode *bt,KeyType k)
{ if (bt==NULL || bt->key==k) /*递归终结条件 */
return bt;
if (k<bt->key)
return SearchBST(bt->lchild,k); /*在左子树中递归查找 */
else
return SearchBST(bt->rchild,k); /*在右子树中递归查找 */
}
2,二叉排序树的插入和生成在二叉排序树中插入一个新记录,要保证插入后仍满足
BST性质 。 其插入过程是：若二叉排序树 T为空,则创建一个
key域为 k的结点,将它作为根结点；否则将 k和根结点的关键字比较,若二者相等,则说明树中已有此关键字 k,无须插入,直接返回 0；若 k<T->key,则将 k插入根结点的左子树中,否则将它插入右子树中 。 对应的递归算法 InsertBST()如下：
int InsertBST(BSTNode *&p,KeyType k)
/*在以 *p为根结点的 BST中插入一个关键字为 k的结点 。 插入成功返回 1,否则返回 0*/
{ if (p==NULL) /*原树为空,新插入的记录为根结点 */
{ p=(BSTNode *)malloc(sizeof(BSTNode));
p->key=k;p->lchild=p->rchild=NULL;
return 1;
}
else if (k==p->key) /*存在相同关键字的结点,返回 0*/
return 0;
else if (k<p->key)
return InsertBST(p->lchild,k);/*插入到左子树中 */
else
return InsertBST(p->rchild,k); /*插入到右子树中 */
}
二叉排序树的生成,是从一个空树开始,每插入一个关键字,
就调用一次插入算法将它插入到当前已生成的二叉排序树中 。
从关键字数组 A[0..n-1]生成二叉排序树的算法 CreatBST()如下：
BSTNode *CreatBST(KeyType A[],int n) /*返回树根指针 */
{ BSTNode *bt=NULL; /*初始时 bt为空树 */
int i=0;
while (i<n)
{ InsertBST(bt,A[i]); /*将 A[i]插入二叉排序树 T中 */
i++;
}
return bt; /*返回建立的二叉排序树的根指针 */
}
例 10.2 已 知 一 组 关 键 字 为
{25,18,46,2,53,39,32,4,74,67,60,11} 。
按表中的元素顺序依次插入到一棵初始为空的二叉排序树中,画出该二叉排序树,并求在等概率的情况下查找成功的平均查找长度 。
解：生成的二叉排序树如右图所示 。
25
18 46
39 53 2
4
11
32 74
67
60
5.312 615243332211A S L
3,二叉排序树的删除删除操作必须首先进行查找,假设在查找过程结束时,已经保存了待删除结点及其双亲结点的地址 。 指针变量 p指向待删除的结点,指针变量 q指向待删除结点 p的双亲结点 。 删除过程如下：
(1) 若待删除的结点是叶子结点,直接删去该结点。如图 (a)
所示,直接删除结点 9。这是最简单的删除结点的情况。
5
2 6
1 4
3
7
8
9
( a )
删除结点 9
q
p
2 6
1 4
3
7
8
5
(2) 若待删除的结点只有左子树而无右子树 。 根据二叉排序树的特点,可以直接将其左子树的根结点放在被删结点的位臵 。 如图 (b)所示,*p作为 *q的右子树根结点,要删除 *p结点,只需将 *p的左子树 (其根结点为 3)作为 *q结点的右子树 。
( b )
删除结点 4
q
p
5
2 6
1 4
3
7
8
9
5
2 6
1 3 7
8
9
(3) 若待删除的结点只有右子树而无左子树 。 与 (2)情况类似,可以直接将其右子树的根结点放在被删结点的位臵 。 如图
(c)所示,*p作为 *q的左子树根结点,要删除 *p结点,只需将 *p的右子树 (其根结点为 8)作为 *q结点的右子树 。
( c )
删除结点 7 p
q
5
2 6
1 4
3
7
8
9
5
2 6
1 4
3
8
9
(4) 若待删除的结点同时有左子树和右子树 。 根据二叉排序树的特点,可以从其左子树中选择关键字最大的结点或从其右子树中选择关键字最小的结点放在被删去结点的位臵上 。 假如选取左子树上关键字最大的结点,那么该结点一定是左子树的最右下结点 。 如图 (d)所示,若要删除 *p(其关键字为 5)结点,找到其左子树最右下结点 4,它的双亲结点为 2,用它代替 *p结点,并将其原来的左子树 (其根结点为 3)作为原来的双亲结点 2的右子树 。
( d )
删除结点 5
p 5
2 6
1 4
3
7
8
9
4
2 6
1 3 7
8
9
删除二叉排序树结点的算法 DeleteBST()如下 (指针变量 p指向待删除的结点,指针变量 q指向待删除结点 *p的双亲结点 )：
void Delete1(BSTNode *p,BSTNode *&r)
/*当被删 *p结点有左右子树时的删除过程 */
{ BSTNode *q;
if (r->rchild!=NULL)
Delete1(p,r->rchild); /*递归找最右下结点 */
else /*找到了最右下结点 *r*/
{ p->key=r->key; /*将 *r的关键字值赋给 *p*/
q=r; r=r->lchild;
/*将左子树的根结点放在被删结点的位臵上 */
free(q); /*释放原 *r的空间 */
}
}
void Delete(BSTNode *&p) /*从二叉排序树中删除 *p结点 */
{ BSTNode *q;
if (p->rchild==NULL) /**p结点没有右子树的情况 */
{ q=p; p=p->lchild;
/*其右子树的根结点放在被删结点的位臵上 */
free(q);
}
else if (p->lchild==NULL) /**p结点没有左子树 */
{ q=p; p=p->rchild;
/*将 *p结点的右子树作为双亲结点的相应子树 /
free(q);
}
else Delete1(p,p->lchild);
/**p结点既没有左子树又没有右子树的情况 */
}
int DeleteBST(BSTNode *&bt,KeyType k)
/*在 bt中删除关键字为 k的结点 */
{ if (bt==NULL) return 0; /*空树删除失败 */
else
{ if (k<bt->key) return DeleteBST(bt->lchild,k);
/*递归在左子树中删除为 k的结点 */
else if (k>bt->key) return DeleteBST(bt->rchild,k);
/*递归在右子树中删除为 k的结点 */
else
{ Delete(bt); /*调用 Delete(bt)函数删除 *bt结点 */
return 1;
}
}
}
10.3.2 平衡二叉树若一棵二叉树中每个结点的左,右子树的高度至多相差
1,则称此二叉树为平衡二叉树 。 在算法中,通过平衡因子
(balancd factor,用 bf表示 )来具体实现上述平衡二叉树的定义 。
平衡因子的定义是：平衡二叉树中每个结点有一个平衡因子域,每个结点的平衡因子是该结点左子树的高度减去右子树的高度 。 从平衡因子的角度可以说,若一棵二叉树中所有结点的平衡因子的绝对值小于或等于 1,即平衡因子取值为 1,0或 -1,
则该二叉树称为平衡二叉树 。
5
2 6
1 4
3
7
1
0
- 1
0 1
0
- 1
3
1 4
2
5
6
7
(b )
(a )
0
- 1
- 2
- 3
- 2
- 1
0
平衡二叉树和不平衡二叉树定义 AVL树的结点的类型如下：
typedef struct node /*记录类型 */
{ KeyType key; /*关键字项 */
int bf; /*增加的平衡因子 */
InfoType data; /*其他数据域 */
struct node *lchild,*rchild; /*左右孩子指针 */
} BSTNode;
假定向平衡二叉树中插入一个新结点后破坏了平衡二叉树的平衡性,首先要找出插入新结点后失去平衡的最小子树根结点的指针,然后再调整这个子树中有关结点之间的链接关系,使之成为新的平衡子树 。 当失去平衡的最小子树被调整为平衡子树后,
原有其他所有不平衡子树无需调整,整个二叉排序树就又成为一棵平衡二叉树 。
失去平衡的最小子树是指以离插入结点最近,且平衡因子绝对值大于 1的结点作为根的子树 。 假设用 A表示失去平衡的最小子树的根结点,则调整该子树的操作可归纳为下列四种情况：
(1) LL型调整
(2) RR型调整
(3) LR型调整
(4) RL型调整例 10.3 输入关键字序列 {16,3,7,11,9,26,18,14,15},给出构造一棵 AVL树的步骤 。
16
0
( a) 插入 16
16
1
( b ) 插入 3
3
0
16
2
( c ) 插入 7
3
- 1
7
0
7
0
(d )LR 调整
3
0
16
0
7
- 1
( e ) 插入 11
3
0
16
1
11
0
7
- 2
( f ) 插入 9
3
0
16
2
11
1
9
0
7
- 1
( g ) LL 调整
3
0
1 1
0
9
0
16
0
7
- 2
3
0
1 1
- 1
9
0
16
- 1
( h ) 插入 26
26
0
7
0
3
0
1 1
0
9
0
16
- 1
26
0
( i ) RR 调整
7
0
3
0
1 1
- 1
9
0
16
- 2
26
1
( j ) 插入 18
18
0
7
0
3
0
1 1
0
9
0
18
0
26
0
( k ) RL 调整
16
0
7
0
3
0
1 1
- 1
9
0
18
1
26
0
16
1
( l ) 插入 14
14
0
7
0
3
0
1 1
- 2
9
0
18
2
26
0
16
2
( m ) 插入 15
14
- 1
15
0
7
0
3
0
1 1
- 1
9
0
18
1
26
0
15
0
0
14 16
0
( n ) L R 调整在平衡二叉树上进行查找的过程和在二叉排序树上进行查找的过程完全相同,因此,在平衡二叉树上进行查找关键字的比较次数不会超过平衡二叉树的深度 。
在最坏的情况下,普通二叉排序树的查找长度为 O(n)。 那么,
平衡二叉树的情况又是怎样的呢？ 下面分析平衡二叉树的高度 h
和结点个数 n之间的关系 。
首先,构造一系列的平衡二叉树 T1,T2,T3,…,其中,
Th（ h=1,2,3,… ） 是高度为 h且结点数尽可能少的平衡二叉树,
如图 10.12中所示的 T1,T2,T3和 T4。 为了构造 Th,先分别构造
Th-1和 Th-2,使 Th以 Th-1和 Th-2作为其根结点的左,右子树 。 对于每一个 Th,只要从中删去一个结点,就会失去平衡或高度不再是
h（ 显然,这样构造的平衡二叉树在结点个数相同的平衡二叉树中具有最大高度 ） 。
T 1
T 2
T 3
T 4
T h
T h - 1 T h - 2
图 10.12 结点个数 n最少的平衡二叉树然后,通过计算上述平衡二叉树中的结点个数,来建立高度与结点个数之间的关系 。 设 N(h)为 Th的结点数,从图 10.12中可以看出有下列关系成立：
N(1)=1,N(2)=2,N(h)=N(h-1)+N(h-2)
当 h>1时,此关系类似于定义 Fibonacci数的关系：
F(1)=1,F(2)=1,F(h)=F(h-1)+F(h-2)
通过检查两个序列的前几项就可发现两者之间的对应关系：
N(h)=F(h+2)-1
由于 Fibonacci数满足渐近公式,F(h)=
其中,
故由此可得近似公式,N(h)=
即,h≈log2(N(h)+1)
所以,含有 n个结点的平衡二叉树的平均查找长度为 O(log2n)。
h51
2
51
12151 h2h
10.3.3 B-树
B-树又称为多路平衡查找树,是一种组织和维护外存文件系统非常有效的数据结构 。
B-树中所有结点的孩子结点最大值称为 B-树的阶,通常用
m表示,从查找效率考虑,要求 m≥3。 一棵 m阶 B-树或者是一棵空树,或者是满足下列要求的 m叉树：
(1) 树中每个结点至多有 m个孩子结点 (即至多有 m-1个关键字 )；
(2) 除根结点外,其他结点至少有?m/2?个孩子结点 (即至少有?m/2?-1=?(m-1)/2?个关键字 )；
(3) 若根结点不是叶子结点,则根结点至少有两个孩子结点；
(4) 每个结点的结构为：
n p0 k1 p1 k2 p2 … kn pn
其中,n为该结点中的关键字个数,除根结点外,其他所有结点的 n大于等于?m/2?-1,且小于等于 m-1； ki(1≤i≤n)为该结点的关键字且满足 ki＜ ki+1； pi(0≤i≤n)为该结点的孩子结点指针且满足 pi(0≤i≤n-1)结点上的关键字大于等于 ki且小于
ki+1,pn结点上的关键字大于 kn。
(5) 所有叶子结点都在同一层上,即 B-树是所有结点的平衡因子均等于 0的多路查找树 。
3 ∧ 12 ∧ 15 ∧ 22 ∧ 2 ∧ 2 ∧ 7 ∧ 2 ∧ 35 ∧ 41 ∧ 3 ∧ 53 ∧ 54 ∧ 63 ∧ 4 ∧ 68 ∧ 69 ∧ 71 ∧ 76 ∧ 3 ∧ 79 ∧ 84 ∧ 93 ∧
2? 11? 30? 2? 66? 78?
1? 51?
一棵 5阶 B-树在 B-树的存储结构中,各结点的类型定义如下：
#define MAXM 10 /*定义 B-树的最大的阶数 */
typedef int KeyType; /*KeyType为关键字类型 */
typedef struct node /*B-树结点类型定义 */
{ int keynum; /*结点当前拥有的关键字的个数 */
KeyType key[MAXM]; /*[1..keynum]存放关键字,[0]不用 */
struct node *parent; /*双亲结点指针 */
struct node *ptr[MAXM];/*孩子结点指针数组 [0..keynum]*/
} BTNode;
1,B-树的查找在 B-树中查找给定关键字的方法类似于二叉排序树上的查找,不同的是在每个记录上确定向下查找的路径不一定是二路
(即二叉 )的,而是 n+1路的 。 因为记录内的关键字序列是有序的数量 key[1..n],故既可以用顺序查找,也可以用折半查找 。 在一棵 B-树上顺序查找关键字为 k的方法为：将 k与根结点中的
key[i]进行比较：
(1) 若 k=key[i],则查找成功；
(2) 若 k＜ key[1],则沿着指针 ptr[0]所指的子树继续查找；
(3) 若 key[i]＜ k＜ key[i+1],则沿着指针 ptr[i]所指的子树继续查找；
(4) 若 k＞ key[n],则沿着指针 ptr[n]所指的子树继续查找 。
2,B-树的插入将关键字 k插入到 B-树的过程分两步完成：
(1) 利用前述的 B-树的查找算法找出该关键字的插入结点 (注意
B-树的插入结点一定是叶子结点 )。
(2) 判断该结点是否还有空位臵,即判断该结点是否满足 n＜ m-
1,若该结点满足 n＜ m-1,说明该结点还有空位臵,直接把关键字 k插入到该结点的合适位臵上 (即满足插入后结点上的关键字仍保持有序 )；若该结点有 n=m-1,说明该结点已没有空位臵,需要把结点分裂成两个 。 分裂的做法是,取一新结点,把原结点上的关键字和 k
按升序排序后,从中间位臵 (即?m/2?=?(m+1)/2?之处 )把关键字 (不包括中间位臵的关键字 )分成两部分,左部分所含关键字放在旧结点中,右部分所含关键字放在新结点中,中间位臵的关键字连同新结点的存储位臵插入到父亲结点中 。 如果父结点的关键字个数也超过 Max,则要再分裂,再往上插,直至这个过程传到根结点为止 。
例如 关键字序列为：
{1,2,6,7,11,4,8,13,10,5,17,9,16,20,3,12,14,18,19,15}。
创建一棵 5阶 B-树 。
建立 B-的过程如下图所示 。
1 2 6 7
6
1 2 7 1 1
6
1 2 4 7 8 1 1 1 3
6 1 0
1 2 4 1 1 1 3 7 8
6 1 0
1 2 4 5 1 1 1 3 1 6
17
7 8 9
6 1 0 1 6
1 2 4 5 7 8 9
3 6 1 0 16
1 2 7 8 9 1 7 1 8 1 9 2 0 4 5
10
1 4 1 5
1 3 1 6 3 6
1 2 7 8 9
(a ) 插入 1,2,6,7 (b ) 插入 11 (c ) 插入 4,8,1 3 (d ) 插入 10
(e ) 插入 5,1 7,9,1 6 (f) 插入 20
(g ) 插入 3,1 2,1 4,1 8,1 9 (h ) 插入 15
1 1 1 3 1 7 2 0
1 7 1 8 1 9 2 0
1 1 1 2 1 3 1 4
4 5 1 1 1 2
3,B-树的删除
B-树的删除过程与插入过程类似,只是稍为复杂一些 。 要使删除后的结点中的关键字个数 ≥?m/2?-1,将涉及到结点的,合并,问题 。 在 B-树上删除关键字 k的过程分两步完成：
(1) 利用前述的 B-树的查找算法找出该关键字所在的结点 。
(2) 在结点上删除关键字 k分两种情况：一种是在叶子结点上删除关键字；另一种是在非叶子结点上删除关键字 。
(3) 在非叶子结点上删除关键字的过程：假设要删除关键字
key[i](1≤i≤n),在删去该关键字后,以该结点 ptr[i]所指子树中的最小关键字 key[min]来代替被删关键字 key[i]所在的位臵 (注意 ptr[i]
所指子树中的最小关键字 key[min]一定是在叶子结点上 ),然后再以指针 ptr[i]所指结点为根结点查找并删除 key[min](即再以 ptr[i]
所指结点为 B-树的根结点,以 key[min]为要删除的关键字,然后再次调用 B-树上的删除算法 ),这样也就把在非叶子结点上删除关键字 k的问题转化成了在叶子结点上删除关键字 key[min]的问题 。
(4) 在 B-树的叶子结点上删除关键字共有以下三种情况：
① 假如被删结点的关键字个数大于 Min,说明删去该关键字后该结点仍满足 B-树的定义,则可直接删去该关键字 。
② 假如被删结点的关键字个数等于 Min,说明删去关键字后该结点将不满足 B-树的定义,此时若该结点的左 (或右 )兄弟结点中关键字个数大于 Min,则把该结点的左 (或右 )兄弟结点中最大 (或最小 )的关键字上移到双亲结点中,同时把双亲结点中大于 (或小于 )
上移关键字的关键字下移到要删除关键字的结点中,这样删去关键字 k后该结点以及它的左 (或右 )兄弟结点都仍旧满足 B-树的定义 。
③ 假如被删结点的关键字个数等于 Min,并且该结点的左和右兄弟结点 (如果存在的话 )中关键字个数均等于 Min,这时,需把要删除关键字的结点与其左 (或右 )兄弟结点以及双亲结点中分割二者的关键字合并成一个结点 。 如果因此使双亲结点中关键字个数小于 Min,则对此双亲结点做同样处理,以致于可能直到对根结点做这样的处理而使整个树减少一层 。
例如,对于上例生成的 B-树,给出删除 8,16,15,4等四个关键字的过程 。
10
3 6 13 17
1 2 4 5 7 9 1 1 12 14 15 18 19 20
(a ) 初始 5 阶 B - 树 (b ) 删除 8,16 后的结果
10
3 6 13 18
1 2 4 5 1 1 12 14 17 19 20
(c ) 删除 15 后的结果
6 10 13 18
1 2 3 5 7 9 14 17 19 20
(d ) 删除 4 后的结果
7 9
1 1 12
10
14 15
13 16 3 6
1 2 7 8 9 17 18 19 20 4 5 1 1 12
10.3.4 B+树在索引文件组织中,经常使用 B-树的一些变形,其中 B+树是一种应用广泛的变形 。 一棵 m阶 B+树满足下列条件：
(1) 每个分支结点至多有 m棵子树 。
(2) 除根结点外,其他每个分支结点至少有?(m+1)/2?棵子树 。
(3) 根结点至少有两棵子树,至多有 m棵子树 。
(4) 有 n棵子树的结点有 n个关键字 。
(5) 所有叶子结点包含全部 (数据文件中记录 ) 关键字及指向相应记录的指针 (或存放数据文件分块后每块的最大关键字及指向该块的指针 ),而且叶子结点按关键字大小顺序链接 (可以把每个叶子结点看成是一个基本索引块,它的指针不再指向另一级索引块,而是直接指向数据文件中的记录 )。
(6) 所有分支结点 (可看成是索引的索引 )中仅包含它的各个子结点 (即下级索引的索引块 )中最大关键字及指向子结点的指针 。
33
1 8 2 3 48
1 0 1 2 1 5 1 8 1 9 2 0 2 1 2 2 2 3 3 0 3 1 3 3 4 5 4 7 4 8 5 0 5 2
一棵 4阶的 B+树
m阶的 B+树和 m阶的 B-树,定义中的前三点是相同的,主要的差异是：
(1) 在 B+树中,具有 n个关键字的结点含有 n棵子树,即每个关键字对应一棵子树,而在 B-树中,具有 n个关键字的结点含有 (n+1)
棵子树 。
(2) 在 B+树中,每个结点 (除根结点外 )中的关键字个数 n的取值范围是?m/2?≤n ≤m,根结点 n的取值范围是 1≤n≤m；而在 B-树中,
它们的取值范围分别是?m/2?-1≤n≤m-1和 1≤n≤m-1。
(3) B+树中的所有叶子结点包含了全部关键字,即其他非叶子结点中的关键字包含在叶子结点中,而在 B-树中,叶子结点包含的关键字与其他结点包含的关键字是不重复的 。
(4) B+树中所有非叶子结点仅起到索引的作用,即结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针,不含有该关键字对应记录的存储地址 。 而在 B-树中,每个关键字对应一个记录的存储地址 。
(5) 通常在 B+树上有两个头指针,一个指向根结点,另一个指向关键字最小的叶子结点,所有叶子结点链接成一个不定长的线性链表 。
10.4 哈希表查找
10.4.1 哈希表的基本概念哈希表 (Hash Table)又称散列表,是除顺序表存储结构、链接表存储结构和索引表存储结构之外的又一种存储线性表的存储结构。哈希表存储的基本思路是：设要存储的对象个数为 n,
设臵一个长度为 m(m≥n)的连续内存单元,以线性表中每个对象的关键字 ki(0≤i≤n-1)为自变量,通过一个称为哈希函数的函数
h(ki),把 ki映射为内存单元的地址 (或称下标 )h(ki),并把该对象存储在这个内存单元中。 h(ki)也称为哈希地址 (又称散列地址 )。
把如此构造的线性表存储结构称为 哈希表。
但是存在这样的问题,对于两个关键字 ki和 kj(i≠j),有
ki≠kj(i≠j),但 h(ki)=h(kj)。 我们把这种现象叫做 哈希冲突 。
通常把这种具有不同关键字而具有相同哈希地址的对象称做,同义词,,由同义词引起的冲突称作 同义词冲突 。 在哈希表存储结构的存储中,同义词冲突是很难避免的,除非关键字的变化区间小于等于哈希地址的变化区间,而这种情况当关键字取值不连续时是非常浪费存储空间的 。 通常的实际情况是关键字的取值区间远大于哈希地址的变化区间 。
归纳起来：
(1)哈希函数是一个映象,即：将关键字的集合映射到某个地址集合上,它的设臵很灵活,只要这个地址集合的 大小不超出允许范围即可；
(2)由于哈希函数是一个压缩映象,因此,在一般情况下,很容易产生,冲突,现象,即,key1?key2,而 f(key1) = f(key2)。
(3) 很难找到一个不产生冲突的哈希函数 。 一般情况下,
只能选择恰当的哈希函数,使冲突尽可能少地产生 。
10.4.2 哈希函数构造方法构造哈希函数的目标是使得到的哈希地址尽可能均匀地分布在 n个连续内存单元地址上,同时使计算过程尽可能简单以达到尽可能高的时间效率 。
1,直接定址法直接定址法是以关键字 k本身或关键字加上某个数值常量 c
作为哈希地址的方法 。 直接定址法的哈希函数 h(k)为：
h(k)=k+c (c≥0)
这种哈希函数计算简单,并且不可能有冲突发生 。 当关键字的分布基本连续时,可用直接定址法的哈希函数；否则,若关键字分布不连续将造成内存单元的大量浪费 。
2,除留余数法除留余数法是用关键字 k除以某个不大于哈希表长度 m的数 p所得的余数作为哈希地址的方法 。 除留余数法的哈希函数
h(k)为：
h(k)=k mod p (mod为求余运算,p≤m)
3,数字分析法该方法是提取关键字中取值较均匀的数字位作为哈希地址的方法 。 它适合于所有关键字值都已知的情况,并需要对关键字中每一位的取值分布情况进行分析 。
例如,对于一组关键字：
{92317602,92326875,92739628,92343634,92706816,92774638,92
381262,92394220}
通过分析可知,每个关键字从左到右的第 1,2,3位和第 6位取值较集中,不宜作为哈希函数,剩余的第 4,5,7和 8位取值较分散,可根据实际需要取其中的若干位作为哈希地址 。 若取最后 两 位 作 为 哈 希 地 址,则 哈 希 地 址 的 集 合 为
{2,75,28,34,16,38,62,20}。
例 10.4 假设哈希表长度 m=13,采用除留余数法哈希函数建立如下关键字集合的哈希表：
{16,74,60,43,54,90,46,31,29,88,77}。
解,n=11,m=13,除留余数法的哈希函数为 h(k)=k mod
p,p应为小于等于 m的素数,假设 p取值 13。 则有：
h(16)=3,h(74)=9,h(60)=8,h(43)=4,
h(54)=2,h(90)=12,h(46)=7,h(31)=5,
h(29)=3,h(88)=10,h(77)=12。
10.4.3 哈希冲突解决方法
1,开放定址法开放定址法是一类以发生冲突的哈希地址为自变量,通过某种哈希冲突函数得到一个新的空闲的哈希地址的方法。
(1)线性探查法 。 线性探查法是从发生冲突的地址 (设为
d)开始,依次探查 d的下一个地址 (当到达下标为 m-1的哈希表表尾时,下一个探查的地址是表首地址 0),直到找到一个空闲单元为止 (当 m≥n时一定能找到一个空闲单元 )。 线性探查法的数学递推描述公式为：
d0=h(k)
di=(di-1+1) mod m (1≤i≤m-1)
(2)平方探查法 。 设发生冲突的地址为 d,则平方探查法的探查序列为,d+12,d+22,… 。 平方探查法的数学描述公式为：
d0=h(k)
di=(d0+i2) mod m (1≤i≤m-1)
平方探查法是一种较好的处理冲突的方法,可以避免出现堆积问题 。 它的缺点是不能探查到哈希表上的所有单元,但至少能探查到一半单元 。
例 10.5 对上例构造的哈希表采用线性探查法解决冲突 。
解,h(16)=3,h(74)=9,h(60)=8,h(43)=4,
h(54)=2,h(90)=12,h(46)=7,h(31)=5,
h(29)=3 冲突
d0=3,d1=(3+1) mod 13=4 仍冲突
d2=(4+1) mod 13=5 仍冲突
d3=(5+1) mod 13=6
h(88)=10
h(77)=12 冲突
d0=12,d1=(12+1) mod 13=0
建立的哈希表 ha[0..12]如下表所示 。
下标 0 1 2 3 4 5 6 7 8 9 10 11 12
k 77 54 16 43 31 29 46 60 74 88 90
探查次数 2 1 1 1 1 4 1 1 1 1 1
哈希表 ha[0..12]
2,拉链法拉链法是把所有的同义词用单链表链接起来的方法 。 在这种方法中,哈希表每个单元中存放的不再是记录本身,而是相应同义词单链表的头指针 。 由于单链表中可插入任意多个结点,所以此时装填因子 α根据同义词的多少既可以设定为大于 1,
也可以设定为小于或等于 1,通常取 α=1。
例 10.6 对上例构造的哈希表采用拉链法解决冲突 。
解：采用拉链法解决冲突建立的链表如下图所示 。
∧
∧
∧
∧
0
1
2
3
4
5
6
7
8
9
10
11
12
5 4 ∧
7 4 ∧
8 8 ∧
4 6 ∧
6 0 ∧
3 1 ∧
4 3 ∧
2 9 1 6 ∧
7 7 9 0 ∧
下标 哈希表本章小结本章基本学习要点如下：
(1) 理解查找的基本概念,包括静态查找表和动态查找表,内查找和外查找之间的差异 。
(2) 重点掌握线性表上各种查找算法,包括顺序查找,
二分查找和分块查找的基本思路,算法实现和查找效率等 。
(3) 掌握各种树表的查找算法,包括二叉排序树,AVL
树和 B-树的基本思路,算法实现和查找效率等 。
(4) 掌握哈希表查找技术以及哈希表与其他表的本质区别 。
(5) 灵活运用各种查找算法解决一些综合应用问题 。
练习教材中 p265习题 1,2,3和 5。
上机实习题教材中 p166题 3和 5。
