第七章 查找.ppt

文档介绍：第七章查找
[内容提要]
查找的基本概念
顺序表、有序表和索引表的查找
二叉平衡树
B-树、B+树的查找
散列表的查找
1
查找有关的概念与术语
关键字:标识一个数据元素的某个数据项或组合项的值
查找表:具有同一类型(属性)的数据元素(记录)组成的集合,分为静态查找表和动态查找表两类.
查找: 按给定的某个值kx,在查找表中查找关键字为给定值kx的数据元素(记录)。
2
数据元素类型说明
typedef struct {
KeyType key; /* 关键字字段,可以是整型、字符串型、构造类型等*/
……/* 其它字段*/
} ElemType;
3
查找方法评价
查找速度
占用存储空间多少
算法本身复杂程度
平均查找长度ASL(Average Search Length):为确定记录在表中的位置,需和给定值进行比较的关键字的个数的期望值叫查找算法的~
4
静态查找表结构
静态查找表结构:静态查找表是数据元素的线性表,可以是基于数组的顺序存储或以线性链表存储。
5
静态查找表的顺序存储结构
顺序存储结构
typedef struct
{
ElemType *elem; /* 数组基址*/
int length; /* 表长度*/
}S_TBL;
6
静态查找表的链式存储结构
链式存储结构
typedef struct NODE
{
ElemType elem;
/* 结点的值域*/
struct NODE *next;
/* 下一个结点指针域*/
}NodeType;
7
静态查找——顺序查找
查找过程:从表的一端开始逐个进行记录的关键字和给定值的比较
i
例
0 1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
找64
64
监视哨
i
i
i
i
比较次数=5
比较次数:
查找第n个元素: 1
查找第n-1个元素:2
……….
查找第1个元素: n
查找第i个元素: n+1-i
查找失败: n+1
8
顺序查找方法的ASL
9
静态查找——折半查找
条件:有序表——表中数据元素按关键字升序或降序排列。
折半查找的思想是:每次将待查记录所在区间缩小一半
10