1
10.1 查找的基本概念
10.2 静态查找表
10.3 动态查找表
10.4 哈希表
第 10章 排序
2
10.1 查找的基本概念
——若表中存在特定元素,称查找成功,应输出该记录;
——否则,称查找不成功( 也应输出失败标志或失败位置 )
查找表
查 找
查找成功
查找不成功
静态查找
动态查找
关键字
主关键字
次关键字
——由同一类型的数据元素(或记录)构成的集合。
——查询 特定元素 是否在 (数据元素集合)表中的过程。
——只查找,不改变数据元素集合内的数据元素。
——既查找,又改变(增减)集合内的数据元素。
——记录中某个数据项的值,可用来识别一个记录
( 预先确定的记录的某种标志 )
——可以 唯一 标识一个记录的关键字 例如“学号”
例如“女”
是一种数据结构
——识别若干记录的关键字
3
讨论 2,对查找表常用的操作有 哪些?
? 查询某个“特定的”数据元素是否在表中;
? 查询某个“特定的”数据元素的各种属性;
? 在查找表中插入一元素;
? 从查找表中删除一元素。
讨论 3,有哪些查找方法?
查找方法取决于表中数据的排列方式 ;
讨论:
讨论 1,查找的过程是怎样的?
给定一个值 K,在含有 n个记录的文件中进行搜索,寻找
一个关键字值等于 K的记录,如找到则输出该记录,否则输
出查找不成功的信息。
例如查字典
针对静态查找表和动态查找表的查找方法也有所不同 。
―特定的” =关键

4
讨论 4,如何评估查找方法的优劣?
明确,查找的过程就是将给定的 K值与文件中各记录的
关键字项进行比较的过程。所以用比较次数的平均值来
评估算法的优劣。称为 平均查找长度 ASL。
?? ??
n
i
ii CPA S L
1
其中:
n是文件记录个数;
Pi是查找第 i个记录的查找概率(通常取等概率,即 Pi =1/n) ;
Ci是找到第 i个记录时所经历的比较次数。
统计意义上的
数学期望值
物理意义,假设每一元素被查找的概率相同,则查找每一
元素所需的比较次数之总和再取平均,即为 ASL。
显然,ASL值越小,时间效率越高。
Average Search Length
5
针对静态查找表的查找算法主要有:
10.2 静态查找表
顺序查找(线性查找)
折半查找(二分查找)
分块查找(索引顺序查找)
静态查找表 主要有 三种结构,
顺序表
有序顺序表
索引顺序表
6
一、顺序表
( 1) 顺序表的机内存储结构
在顺序表上的 顺序查找(又称线性查找 )的基本思想:
从顺序表的一端开始,用给定数据元素的关键字逐个与顺序
表中各数据元素的关键字比较,若在顺序表中查找到要查找
的数据元素,则查找成功,函数返回该数据元素在顺序表中
的位置;否则查找失败,函数返回 -1。
typedef struct
{ DateType list[MaxSize];
int size;
}SeqList;
7
( 2) 算法的实现
int SeqSearch(SeqList S,DataType x)
{ int i = 0;
while(i<S.size && S.list[i].key!=x.key)
i++;
if(S.list[i].key == x.key) return i;
else return -1;
}
8
( 3) 顺序查找算法性能评价
分析:
查找第 1个元素所需的比较次数为 1;
查找第 2个元素所需的比较次数为 2;
……
查找第 n个元素所需的比较次数为 n;
总计全部比较次数为,1+ 2+ … + n = (1+n)n/2
这是查找成功的情况
若求某一个元素的平均查找次数,还应当除以 n(等概率),
即,ASL成功 =( 1+ n) /2,时间效率为 O(n)
同理,ASL失败 =( 1+ n) /2
( 4) 顺序查找的特点
优点,算法简单,且对顺序结构或链表结构均适用。
缺点,ASL 太大,时间效率太低。
9
思考题:
1、问:对 顺序结构 如何线性查找?
答:利用顺序表
2、问:对 单链表结构 如何线性查找?
答:从头指针始, 顺藤摸瓜,
3、问:对 非线性 ( 树结构) 如何顺序查找?
答,借助各种二叉树遍历操作!
10
(1)算法的基本思想,先给数据排序 (例如按升序排好),形
成 有序表,然后再将 key与 正中 元素相比,若 key小,则缩小至
前半部内查找;再取其 中值 比较,每次缩小 1/2的范围,直到
查找成功或失败为止。(详细见教材 P263)
思考题:
问:能否使用 单链表结构 进行折半查找?
——无法实现 ! 因全部元素的定位只能从头指针 head开始
问:对 非线性 (树 )结构 如何进行折半查找?
——可借助 二叉排序树 来查找(属动态查找表形式)。
二、有序顺序表
有序顺序表上的查找算法主要有 顺序查找 和 折半查找 两种方法。
1、顺序查找
有序顺序表上顺序查找算法类同顺序表上的顺序查找算法。
2、二分查找( 又称 折半查找)
11
② 运算步骤,
(1) low =0,high =10,故 mid =5,待查范围是 [0,10];
(2) 若 S.list[mid].key < key,说明 key?[ mid+1,high],
则令,low =mid+1;重算 mid= ?(low+high)/2?;,
(3) 若 S.list[mid].key > key,说明 key?[low,mid-1],
则令,high =mid–1;重算 mid ;
(4)若 S.list[ mid ].key= = key,说明查找成功,元素序号 =mid;
结束条件,( 1)查找成功, S.list[mid].key = key
( 2)查找不成功, high≤low (意即区间长度小于 0)
解:① 先设定 3个辅助标志,low,high,mid,
折半查找举例:
Low指向待查元素
所在区间的下界
high指向待查元素所
在区间的上界mid指向待查元素所在区间的中间位置
已知如下 11个元素的 有序表,
( 05 13 19 21 37 56 64 75 80 88 92),请查找关键字为 21
的数据元素的查找思路。
显然有,mid= ?(low+high)/2?
12
(2)算法的实现
int BinarySearch(SeqList S,DataType x)
{int low = 0,high = S.size-1;/确定初始查找区间上下界
int mid;
while(low <= high)
{
mid=(low + high)/2;//确定初始查找区间中心位置
if(S.list[mid].key == x.key) return mid;//查找成功
else if(S.list[mid].key < x.key) low = mid + 1;
else if(S.list[mid].key > x.key) high = mid - 1;
}
return -1; //查找失败
}
13
( 3) 折半查找 算法性能评价
nn
n
nj
n
A S L
m
j
j
22
1
1 l o g1)1(l o g121 ??????? ?
?
?
课堂练习 1(多选题)使用折半查找算法时,要求被查文件:
A.采用链式存贮结构 B.记录的长度 ≤ 12
C.采用顺序存贮结构 D.记录按关键字递增有序√ √
课堂练习 2 在有序线性表 a[20]上进行折半查找,则平均查
找长度为 。3.7
14
? 找到有序表中任一记录的过程就是,走了一条从根结点到与该记
录对应结点的路径。
? 比较的关键字个数为,该结点在判定树上的层次数。
? 查找成功时 比较的关键字个数最多不超过树的深度 d,
d = ? log2 n ? + 1
? 查找不成功的过程就是,走了一条从根结点到 外部结点 的路径。
再用 查找二叉树 /判定树 来分析 ASL
以 ( a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11) 为例:
a6
a3 a9 判定树由表中元素个数决定,且 n个元素表的折半
查找判定树是 唯一 的。a
1 a10a7a4
a11a8a2 a5
15
三、分块查找 ( 索引 顺序查找)
思路,先让数据 分块有序,即分成若干子表,要求
每个子表中的数据元素值都比后一块中的数值小
( 但子表内部未必有序 )。
然后将各子表中的 最大 关键字构成一个 索引表,表
中还要包含每个子表的起始地址(即头指针)。
讨论,对顺序查找除了 折半 改进法外,还有无其他改进算法?
有,例如 分块查找 法。
24 48 60 58 74 491312 9 20 33 42 44 38 86 53822
例:
特点:块间有序,块内无序
16
分块查找过程举例:
索引表
块内最大关键字
各块起始地址
22 12 13 8 9 20 33 42 44 38 24 48 60 58 74 49 86 53
第 1块 第 2块 第 3块
22 48 86
1 7 13
特点:块间有序,块内无序
查找步骤 分两步进行:
① 对索引表使用折半查找法(因为索引表是有序表);
② 确定了待查关键字所在的子表后,在子表内采用顺序
查找法(因为各子表内部是无序表);
查找:块间折半,块内线性
17
查找效率 ASL分析:
对索引表查找的 ASL 对块内查找的 ASL
)2 1( l o g2)1(l o g 22 ?????? nA S LnssnA S L bsbs
S为每块内部的记录个数,n/s即块的数目
例如当 n=9,s=3时,
分块法的 ASLbs =3.5
而折半法的 ASL≈log 2n=3.1
顺序法的 ASL=(1+ n)/2 = 5
ASL=Lb+Lw
但折半法要
预先全排序,
仍需时间。
18
讨论,当有序表中各记录的 查找概率不相等 时,该如何查找?
提 醒,此时用 折半查找法未必最优 !
改 进,若将各记录的概率看作是二叉树之权值,则转为研究
带权路径长度最小的二叉树(类似 最优 二叉树)。
19
特点:
10.3 动态查找表
表结构在查找过程中动态生成。
要求,对于给定值 key,若表中存在其关键字等于 key的记录,
则查找成功返回; 否则插入关键字等于 key 的记录。
典型的动态表 ———二叉排序树
动态查找表主要有二叉树结构和树结构两种类型。二叉
树结构有二叉排序树、平衡二叉树等。树结构有 B-树,B+树
等。
20
一、二叉排序树的基本概念
----或是一棵空树;或者是具有如下性质的非空二叉树:
( 1)左子树的所有结点均小于根的值;
( 2)右子树的所有结点均大于根的值;
( 3)它的左右子树也分别为二叉排序树。
( a) ( b)
例,下列 2种图形中,哪个不是二叉排序树?
想一想:对它中序遍历之后是什么效果?
74
1 10
2 6
5
3
9
8
5
10
2
1
6
4
7
3
9
8
21
45
24 53
12 90
如果改变 输入顺序为( 24,53,45,45,12,24,90),



功,





功,


例, 输入待查找的关键字序列 =( 45,24,53,45,12,24,90)



功,





功,


查找不成功
则插入树中
则生成的二
叉排序树形
态不同
24
53
45
12
90
二、二叉排序树的插入与删除
这种既查找又插入的
过程称为动态查找
22
① 查找过程与顺序结构有序表中的 折半查找 相似,查
找效率高;
② 中序遍历 此二叉树,将会得到一个关键字的有序序
列( 即实现了排序运算 );
③ 如果查找不成功,能够方便地将被查元素 插入到二
叉树的叶子结点 上,而且插入或删除时只需修改指
针而不需移动元素。
二叉排序树既有类似于折半查找的特性,
又采用了链表存储,它是动态查找表的
一种适宜表示。
将线性表构造成二叉排序树的优点:
23
讨论 1,二叉排序树的 查找 &插入 算法如何实现?
思路,查找不成功,生成一个新结点(如 s),并将 (s)插
入到二叉排序树中;查找成功则返回。
程序:
int Insert(BiTreeNode **root,DataType item)
{ BiTreeNode *current,*parent=NULL,*p;
current = *root;
while(current != NULL)
{ if(current->data.key == item.key) return 0;
parent=current;
if(current->data.key<item.key)
current=current->rightChild;
else current=current->leftChild; }
24
p=(BiTreeNode *)malloc(sizeof(BiTreeNode));
if(p==NULL) { printf("空间不够 !");exit(1);}
p->data = item;
p->leftChild = NULL;
p->rightChild = NULL;
if(parent == NULL) *root = p;
else if(item.key < parent->data.key)
parent->leftChild = p;
else parent->rightChild = p;
return 1;
}
25
对于二叉排序树,删除树上一个结点相当于删除有序序
列中的一个记录,要求删除后仍需保持二叉排序树的特性。
讨论 2,二叉排序树的删除操作如何实现?
如何删除一个结点?
假设,*p表示被删结点的指针; PL和 PR分别表示 *P的左、右孩子指针;
*f表示 *p的双亲结点指针;并假定 *p是 *f的 左孩子 ;则可能有三种情况:
*p为叶子,删除此结点时,直接修改 *f指针域即可;
*p只有一棵子树(或左或右),令 PL或 PR为 *f的左孩子即可;
*p有两棵子树:情况最复杂 →
f
p
PL PR
26
分析:
设删除前的 中序 遍历序列为:
…,P L s p PR f …,//显然 p的直接前驱是 s
//s是 *p左子树最右下方的结点
希望删除 p后,其它元素的相对位置不变。有两种解决方法:
法 1,令 *p的左子树为 *f的左子树,*p的右子树接为 *s的右
子树; //即 fL=PL ; SR=PR ;
法 2,直接令 *s代替 *p // *s为 *p左子树最右下方的结点
难点,*p有两棵子树时,如何进行删除操作?
f
p
PL PR
s
27
F
C
CL
S
SL
QL
P
PR
Q PR
F
C
CL
S
SL
QL
P
PR
Q
法 2:
F
C
CL
S
SL
QL
P
PR
Q
法 1:
例,请从下面的二叉排序树中删除结点 P。
S
SL
28
1) 二叉排序树上查找某关键字等于结点值的过程,其实就是
走了一条从根到该结点的路径。
比较的关键字次数= 此结点的层次数 ;
最多的比较次数= 树的深度(或高度),即 ?log2 n?+1
2) 一棵二叉排序树的平均查找长度为:
三、二叉排序树的查找分析
?? ??
m
i
ii Cn
n
AS L
1
1
其中:
ni 是每层结点个数;
Ci 是结点所在层次数;
m 为树深。
最坏情况,插入的 n个元素从一开始就有序(单调增或减),
——变成了单支树的形态!
此时树的深度为 n ; ASL= (n+1)/2
与线性查找的 ASL相同!
29
最好情况,与折半查找中的判定树相同(即形态比较均衡)
3)对有 n 个关键字的二叉排序树的平均查找长度,
设每种树态出现概率相 同,查找每个关键字也是等概率的。
则 ASL求解过程可推导。
树的深度为,?log 2n ? +1 ; ASL=log 2(n+1) –1
结论:二叉排序树的
n ) l n
n
12 ( 1A S L ?? (与 log n 同阶)
思考:如何提高二叉排序树的查找效率?
尽量让二叉树的形状均衡
平衡二叉树
30
平衡二叉树的特点:
任一结点的平衡因子只能取,-1,0 或 1。
例:判断下列二叉树是否 AVL树?
0
00 1
1 -1
-1 2
0
0
0
1
-1
? 对于一棵有 n个结点的 AVL树,其 高度 保持在
O(log2n)数量级,ASL也保持在 O(log2n)量级。
31
如果在一棵 AVL树中插入一个新结点,就有可能
造成失衡,此时必须 重新调整树的结构,使之恢
复平衡。我们称调整平衡过程为 平衡旋转 。
平衡旋转可以归纳为四类:
? LL平衡旋转
? RR平衡旋转
? LR平衡旋转
? RL平衡旋转