基本概念静态查找表动态查找表哈希查找表

• 折半查找在查找成功时关键字比较次数 不超过树的深度,即: log2n + 1
假设 n=2h-1 并且查找概率相等
则
ASLbs

1 n
n i1
Ci

1 n

h j1
j

2
j1



n
n
1
log
2
(n

1)

1
在n>50时，可得近似结果
ASLbs log2(n 1) 1
若此关键字能识别若干记录，则称
之谓“次关键字”。
查找（搜索 、 Search)
所谓查找，就是在数据集合中寻找满足某种条 件的数据对象。
查找的结果通常有两种可能： 查找成功，即找到满足条件的数据对象。这 时，作为结果，可报告该对象在结构中的位置， 还可进一步给出该对象中的具体信息。 查找不成功，或搜索失败。作为结果，也应 报告一些信息，如失败标志、失败位置等。
• 分块有序原则：第二个子表的所有记录的关键字均 大于第一个字表中的最大关键字，……，依此类推。
索引顺序表的查找过程：
1）由索引确定记录所在块（子表）； 2）在顺序表的某个块内进行顺序查找。
可见， 索引顺序查找的过程也是一个
“缩小区间”的查找过程。
注意：索引可以根据查找表的特点来构造。
因为索引表中的 索引项是按关键字有 序排列的，因此可用顺序查找，也可用 折半查找；而块（子表）中的记录是任 意排列的，只能用顺序查找的方法。
for (i=ST.length; ST.elem[i].key!=key; --i);
// 从后往前找
return i ;

第九章查找本章中介绍下列主要内容：静态查找表及查找算法：顺序查找、折半查找动态查找表及查找算法：二叉排序树哈希表及查找算法第一节基本概念查找表用于查找的数据元素集合称为查找表。

查找表由同一类型的数据元素（或记录）构成。

静态查找表若只对查找表进行如下两种操作：（1）在查找表中查看某个特定的数据元素是否在查找表中，（2）检索某个特定元素的各种属性，则称这类查找表为静态查找表。

静态查找表在查找过程中查找表本身不发生变化。

对静态查找表进行的查找操作称为静态查找。

动态查找表若在查找过程中可以将查找表中不存在的数据元素插入，或者从查找表中删除某个数据元素，则称这类查找表为动态查找表。

动态查找表在查找过程中查找表可能会发生变化。

对动态查找表进行的查找操作称为动态查找。

关键字是数据元素中的某个数据项。

唯一能标识数据元素（或记录）的关键字，即每个元素的关键字值互不相同，我们称这种关键字为主关键字；若查找表中某些元素的关键字值相同，称这种关键字为次关键字。

例如，银行帐户中的帐号是主关键字，而姓名是次关键字。

查找在数据元素集合中查找满足某种条件的数据元素的过程称为查找。

最简单且最常用的查找条件是"关键字值等于某个给定值"，在查找表搜索关键字等于给定值的数据元素（或记录）。

若表中存在这样的记录，则称查找成功，此时的查找结果应给出找到记录的全部信息或指示找到记录的存储位置；若表中不存在关键字等于给定值的记录，则称查找不成功，此时查找的结果可以给出一个空记录或空指针。

若按主关键字查找，查找结果是唯一的；若按次关键字查找，结果可能是多个记录，即结果可能不唯一。

查找表的存储结构查找表是一种非常灵活的数据结构，对于不同的存储结构，其查找方法不同。

为了提高查找速度，有时会采用一些特殊的存储结构。

本章将介绍以线性结构、树型结构及哈希表结构为存储结构的各种查找算法。

查找算法的时间效率查找过程的主要操作是关键字的比较，所以通常以"平均比较次数"来衡量查找算法的时间效率。

122
99
250
110
300
280
类C程序实现： void InsertBST(*&t，key) //在二叉排序树中插入查找关键字key { if(t= = NULL){ t=new BiTree; t->lchild=t->rchild=NULL; t->data=key; return; } if(key<t->data ) InsertBST(t->lchild,key); else InsertBST (t->rchild, key ); } void CreateBiTree(tree,d[ ],n） //n个数据在数组d中，tree为二叉排序树根 { tree=NULL; for(i=0;i<n;i++) InsertBST(tree,d[i]); }
p q
void delete(*&p) { if(p->rchild = = NULL) { q=p; p=p->lchild; delete q; } else if(p->lchild= =NULL) { q=p; p=p->rchild; delete q; } else { q=p; s=p->lchild; while(s->rchild!=NULL) {q=s; s=s->rchild;} p->data=s->data; if(q!=p) q->rchild=s->lchild; else q->lchild=s->lchild; } delete s; }
在xL中选值最大的代替x，该数据按二叉排序树的性质应在 最右边。
f x f s c

6
3
9
1
4
7
10
从二分法检索可知： 查找结点的比较次数等 找到第6个数仅需比较1次， 于该结点的层数,查找结 找到第3和第9个数需2次， 点的过程就是从根结点 找到第1，4，7，10个数 到相应结点的路径。 需3次，找到第2，5，8和 11个数需4次。
11
2
5
8
8.1.2 有序表的查找
检索成功时比较次数不超过树深度。n结点判定树深度至多为 log2n+1。所以二分法检索成功时的比较次数最多为log2n+1。 检索不成功时的判定树如下（方框表示检索不成功情况）：
k=6 n=10
2 4 2 4 2 4 2 4 2 4 2 4 2 4
8.1.1 顺序表的查找
开始: 3 9 1 5 8 10 6 7 2 4 k=6 n=10
―哨兵”ቤተ መጻሕፍቲ ባይዱ
第1次比较: 6 3 9 1 5 8 10 6 7 2 4 i=n 第2次比较: 6 3 9 1 5 8 10 6 7 2 4 i=n-1 第3次比较: 6 3 9 1 5 8 10 6 7 2 4 i=n-2 第4次比较: 6 3 9 1 5 8 10 6 7 2 4 i=n-3 查找成功,返回序号6
8.1.3 索引顺序表的查找
分块查找分两个阶段 确定待查元素所在的块——索引表内查找
索引表是按块内最大关键码有序的，且长度不大，可 以用二分查找，也可以顺序查找
在块内查找待查的元素——子表(块)内查找
各子表内各个记录不是按记录关键码有序，只能顺序 查找
分块查找性能分析
ASL bs=ASL b+ ASL w
查找的效率评价
主要运算是关键字的比较,所以通常把查找过程中对关 键字需要执行的平均比较次数(也称为平均查找长度)作 为衡量一个查找算法效率优劣的标准。平均查找长度 姓 名 其 他 ASL(Average Search Length)定义为：