文档介绍：第九章查找
静态查找表
顺序表的查找
有序表的查找
动态查找表
二叉排序树和二叉平衡树
哈希( Hashing )表(散列表)
第九章查找
查找表(search table):
同一类型数据元素构成的集合。
查找操作:
(1)查询某个“特定的”数据元素是否在查找表中;
(2)检索某个“特定的”数据元素的各种属性;
(3)在查找表中插入一个数据元素;
(4)从查找表中删除某个数据元素.
静态查找表:对查找表只作(1)、(2)操作;
动态查找表:可以对查找表作(1)-(4)操作。
有关查找的“词”的含义
关键字(KEY):
数据元素(或记录)的某个数据项的值,用以标识一个数据元素(或记录).
可以唯一标识一个记录的关键字称为主关键字(Primary Key); 否则称为次关键字(Secondary Key).
查找(Searching)
根据给定的值,在查找表中确定一个关键字等于给定值的记录或数据元素.
静态查找表
可以用顺序表,也可以用线性链表来表示静态查找表。
顺序表的查找
typedef struct{ //静态查找表的顺序存储结构
ElemType *elem;
int length;
}SSTable;
elem
length
key
0
1
2
...
length-1
length
顺序查找(Sequential Search)
int Search_Seq(SSTable ST, KeyType key){
[0].key = key; // “哨兵”
for(i=; !EQ([i].key, key); --i);
return i;
}
性能分析: 设Pi为查找表中第i个记录的概率(取Pi=1/n);
Ci为找到第i个记录所需的查找次数。则
n
ASL =  Pi Ci = nP1+(n-1)P2+...+2Pn-1+Pn
i=1
= [n+(n-1) +...+2+1]*1/n = (n+1)/2
若查找成功与不成功的概率相同,即Pi=1/2n,
ASL = nP1+(n-1)P2+...+2Pn-1+Pn+(n+1)/2 = (n+1)*3/4
有序表的查找:折半查找(Binary Search)
确定待查记录的区间,逐步缩小范围直到找到或找不到该记录为止。
例子: 数据元素有序表如下,查找关键字key=21的数据元素。
21(05,13,19,21,37,56,64,75,80,88,92)
下标: 0 1 2 3 4 5 6 7 8 9 10 11
05,13,19,21,37,56,64,75,80,88,92
low mid high
mid = [(low+high)/2]; key=[mid].key查找成功;
当key<[mid].key时,下一个待查区间为[low,mid-1]
05,13,19,21,37,56,64,75,80,88,92
low mid high
当key>[mid].key时下一个待查区间为[mid+1,high]
折半查找的性能分析查找上例中所有元素的判定二叉树为
6
3
1
4
7
9
5
10
2
11
8
判定树
判定树上每个结点需要的
查找次数刚好为该结点所
在的层数.
查找成功时查找次数不会
超过判定树的深度
n个结点的判定树的深度
为[log2n]+1.
折半查找的算法复杂度为
[log2n]+1
动态查找表二叉排序树
什么是二叉排序树(Binary Sort Tree) ?
二叉排序树是空树,或者是具有以下性质的二叉树:
(1)若左子树非空,则左子树上所有结点的值均小于
它的根结点的值;
(2)若右子树非空,则右子树上所有结点的值均大于
它的根结点的值;
(3)它的左、右子树也分别为二叉排序树。
二叉排序树举例
45
12
3
37
53
78
100
24
90
61
二叉排序树
查找过程:
从根结点出发,结点的值与key进行比较:(1)相等时查找成功;
(2)key较大时,沿右子树继续查找(无右子树表明查找失败);
(3)key较小时,沿左子树继续查找(无左子树表明查找失败)。
其中序遍历序列:
3,12,24,37,45,53,61,78,90,100
二叉排序树的生成(插入结点)
二叉排序树的生成(连续进行插入操作)
例如:对{45,24,53,45,12,24,90}
关键字序列的二叉排序树生成过