数据结构课件 第8章 查找

女 ……
18 ……
计98 ……
一般 ……
关键字：数据元素的某个数据项的值，用它可标识列表中的 一个或一组数据元素 查找：根据给定的关键字值，在列表中确定一个其关键字与给 定值相同的数据元素，并返回该数据元素在列表中的位置。
平均查找长度 定义：为确定数据元素在列表中的位置，需和给定关键值进 行比较的关键值个数的期望值，称为查找算法在查找成功时 的平均查找长度
May 其在等概率(1/12)的情况下，查 找成功的平均查找长度：
Dec Apr Feb June
Oct
Aug
Jan
Mar
Nov
Sep
ASL＝（1+2*2+3*4+4*5)/12=3.1
算法优点
算法缺点
待查表为有序表 插入、删除困难
比较次数少
查找速度快 平均性能好
8.2.3 分块查找法
1、对所查表的要求 ⑴将列表分成若干块（子表），一般情况下，块的长度均匀， 最后一块可不满 ⑵每块内元素无序 ⑶块与块间有序
35
32 查找关键字 == 50 , 35 , 90 , 95 ,
85
88
4、二叉排序树的查找算法
若二叉排序树为空，则查找不成功； 否则 ⑴若给定值等于根结点的关键字，则查 找成功； ⑵若给定值小于根结点的关键字，则继 续在左子树上进行查找； ⑶若给定值大于根结点的关键字，则继 续在右子树上进行查找。
1
8.1查找基本的概念
查找中用到如下的基本概念。例如
列表 关键字 查找 平均查找长度 基本查找方法
列表：由同一类型的数据元素（或记录）构成的集合。
姓名
黄佳 钱昌 王羽
学号
9831 9832 9833
性别
男 女 男
年龄
18 17 19
班级
计98 计98 计98
健康
良好 一般 近视
高甜 ……
9834 ……
}
二叉排序树插入的非递归算法
BSTNode * InsertBST(BSTree root, KeyType key)
//若在二叉排序树中不存在关键字等于key的元素，插入该元素
if (root==NULL） s=(BSTree)malloc(sizeof(BSTNode)) s->key=key; root=s; else {p=root; s->lchild=NULL;
{ if (q->key==key) return q;
int SeqSearch(RecordList l,KeyType k)
不设监视哨
int SeqSearch(RecordList l,KeyType k)
//在顺序表l中顺序查找关键字等于k的元素， //不用监视哨，在顺序表中查找关键字等 若找到，则函数值为该元素在表中的位置， 于k的元素 否则为0.
100），若查找元素58，则它将依次与表中那些元素比较，查找
结果失败。
例2：对于具有144个记录的文件，若采用分块查找，且每块
长度为8,则平均查找长度为多少？
20
8.3基于树的查找法
二叉排序树
平衡二叉排序树 B树
8.3.1 二叉排序树
50
1、定义
30 80
二叉排序树或者是一棵空树， 或者是具有如下性质的二叉树： ⑴若它的左子树非空，则 左子树上所有结点的值均 小于根结点的值
1 b b 1 LB j b j 1 2 1 s s 1 LW i s i 1 2 将b n / s代入 1 ASL (b s ) 1 bs 2
s 1 ASLbs log2 (b 1) 1 2 n s log2 ( 1) s 2
70
…… 75.5 80.0 ……. 68
……
…… …… …… ……. …….
2、基本过程 将表中间位置记录的关键字与需要查找的关键字比较 如果两者相等，则查找成功; 否则利用中间记录将表分成前、后两个子表; 如果列表中间位置记录的关键字大于要查找关键 字，则进一步查找前一子表 否则进一步查找后一子表。
Void InsertBST(BSTree *bst, KeyType key)
//若在二叉排序树中不存在关键字等于key的元素，插入该元素
{ Bitree s;
If(*bst==NULL)
s->key=key;
*bst=s;
//递归结束条件
s=(BSTree)malloc(sizeof(BSTNode))
3、二叉排序树的插入
50 30 20 20 35 32 32 40 80 90
【算法思想】
⑴若二叉树是空，则新结 点Ｓ是二叉树的根 ⑵若二叉树非空，则将 S.key与二叉排序树根结 点的关键字进行比较： a.若S.key的值等于根结 点的值，则停止插入；
85 85
88 88
b.若S.key的值小于根结 点的值，则将Ｓ插入左子 树； c.若S.key的值大于根结点 的值，则将Ｓ插入右子树；
BSTree SearchBST (BSTree bst, KeyType key){
// 在根结点bst所指的二叉排序树中，递归查找关键字等 于key的元素，若查找成功，返回指向该元素结点的指 针，否则返回空指针
if (!bst)
Return NULL Return bst //查找成功
Else if(bst->key==key) Else if (bst->key>key)
//建立新结点
s->rchild=NULL;
r=(BSTree)malloc(sizeof(BSTNode));
r->key=key; r->lchild=NULL; r>rchild=NULL;
while (p) { q=p;
//寻找新结点的插入位置
if(p->key>key) p=p->lchild; else p=p->rchild; } if (q->key==key) else q->rchild=r; //插入r做q的右孩子 return; //插入r做q的左孩子
Lb log2 (b 1) 1
查找方法比较
顺序查找 ASL 表结构 存储结构 最大 有序表，无序表 顺序存储结构， 线性链表 折半查找 最小 有序表 顺序存储结 构， 分块查找 两者之间 分块有序表 顺序存储结构， 线性链表
课堂练习 例1：折半查找有序表（4，6，10，12，20，30，50，70，88，
n
8.2.2 折半查找法
1、折半查找定义 折半查找法又称二分查找法，这种方法对待查找的列表有两个要求 : ⑴列表必须是顺序存储结构 ⑵列表必须按关键字大小有序排列
学号 0001 姓名 王一 平均成绩 90.2 其它 …….
0002
…… 0032 0034 …… 0060
张三
…… 李四 刘四 …… 钱五
3、算法
Int BinSrch(RecordList l,KeyType k)
//在有序表中折半查找其关键字等于k的元素，若找到，则函数 返回值为该元素在表中的位置d
{ low=1; high=l.length; While(low<=high)
//置区间初值
{ mid=(low+high)
if(k==l.r[mid].key) return (mid) else low=mid+1;
ASL P P 1C1 P 2 C2 ...... n Cn
PC
i 1 i
n
i
Pi是查找第i个元素概率，Ci是为找到第i个元素进行的比较次数
4
8.2基于线性表的查找法
顺序查找法
折半查找 分块查找法
8.2.1 顺序查找法
1、数据类型的定义
# define LiST_SIZE 20
6
3
9
1
4
7
10
2
5
8
11
4、性能分析
从根到被查结点路径关键字比较次数为被查 结点层次数
假设表的长度n=2h-1,则相应判定树必为深 度是h的满二叉树，h=log2(n+1) 树中层次为1的结点有1个，层次为2的 结点有2个，层次为h的结点有2h-1个 又假设每个记录的查找概率相等，则折半 查找成功时的平均查找长度为
25 0
58 5
88 10
索引表
18 14 12 25 8
0 1 2 3 4
28 32 45 36 58 60 88 71
5 6 7 8 9 10 11 12
2、基本思想
⑴构造一索引表 ⑵将待查关键字K与索引表中的关键字进行比较，以确定待查 记录所在的块。 ⑶用顺序查找法，在相应块内查找关键字为K的元素
Return SearchBST(bst->lchild,key);
//在左子树中继续查找
else Return SearchBST(bst->rchild,key);
//在右子树中继续查找
BSTree SearchBST (BSTree bst, KeyType key){
// 在根结点bst所指的二叉排序树中，查找关键字等于key 的元素，若查找成功，返回指向该元素结点的指针，否则 返回空指针 { BSTree q; q=bst; While (q)
if (q->key>key) q->lchild=r;
}
return root; }
结论
• 一个无序序列可以通过构造一棵二 叉排序树而变成一个有序序列 • 每次插入的新结点都是二叉排序树 上新的叶子结点 • 插入时不必移动其它结点，仅需修 改某个结点的指针