数据结构：第七章 查找

iii
比较次数：
查找第n个元素： 1
查找第n-1个元素：2
……….
查找第1个元素： n
查找第i个元素： n+1-i
查找失败：
n+1
ii
比较次数=5
数据结构定义：
因一般不对查找表做修改，表长不变，所以可将其 作为常量。以顺序表为例：
#define n 100
typedef struct
{ keytype key;
1、 顺序查找
查找过程：从表的一端开始逐个进行记录的关键字和给 定值的比较。若相等则成功；若扫描结束仍未找到，则 失败。
找64
例 0 1 2 3 4 5 6 7 8 9 10 11 64 5 13 19 21 37 56 64 75 80 88 92
监视哨：设置在两 端r[0]或r[n+1]， 使其关键字值为给 定值k。避免每次 的越界判断。
第七章 查 找
➢线性表的查找 ➢树上的查找 ➢散列技术
7.1 基本概念
查找——也叫检索，是根据给定的某个值，在表(指查找表) 中确定一个关键字等于给定值的记录或数据元素。
关键字——是数据元素中某个数据项的值，它可以标识一 个数据元素。
平均查找长度ASL——由于查找运算的关键操作是关键字的 比较。通常以查找过程中对关键字执行的平均比较次数， 即平均查找长度(ASL)，作为衡量一个查找算法效率优劣的 标准。
high low
1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92
6
56
3
9
19
80
1
4
7
10
5 21 64 88
比较1次 比较2次 比较3次
2
13
5
8
37 75
11
92
比较4次
判定树(二叉排序树)：描 述查找过程的二叉树
把当前查找区间的中间位 置上的结点作为根,左子表 和右子表中的结点分别作 为根的左子树和右子树
1 n
则ASL
n i 1
pi ci
1 n
n i 1
(n i 1)
n 1 2
顺序查找的优缺点：
优点：简单且适用面广，对表的结构没有要求， 无论记录是否按关键字有序都可应用。
缺点：效率低。
2、 折半查找(二分查找)
查找过程：以中间位置记录关键字与给定值比 较。相等则成功；不等，则缩小查找范围，继 续查找。每次将待查记录所在区间缩小一半。
查找方法的确定：首先取决于使用的数据结构（线性表、 图）；其次是表的有序性（有序、无序）。主要分为：顺 序查找、折半查找和分块查找，这3种属于静态查找（查找 过程不修改原结构），一般以线性表做为数据结构。另一 类是二叉排序树查找，属于动态查找（即动态生成查找结 构，在查找同时，对原结构做修改）。
7.2 线性表的查找——静态查找
return 0;
// 顺序表中不存在待查元素
} // Search_Bin
算法评价
❖折半查找过程恰好是走了一条从根结点到被查结点的 路径.比较次数为路径上结点个数(被查结点在树上的 层数),在查找过程中进行的比较次数最多不超过其判 定树的深度.
算法描述
找21 例 1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
low
mid
123456 7 5 13 19 21 37 56 64
high
8 9 10 11 75 80 88 92
low
mid
high
1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
lowmid high
找70 例 1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
low
mid
123456 7
5 13 19 21 37 56 64
high 8 9 10 11 75 80 88 92
{ mid = (low + high) / 2;
if（k= = r[mid].key ) return mid; //找到
if ( k < r[mid].key ) high = mid - 1;
// 继续在前半区间内进行查找
else low = mid + 1; // 继续在后半区间内进行查找
} //while
折半查找算法：
int Search_Bin ( Seqlist r, KeyType k )
{// 在有序表ST中折半查找其关键字等于kval的数据元素。 // 若找到，则函数值为该元素在表中的位置，否则为0。
int low = 1, high = n, mid; // 置区间初值
while (low <= high)
low
mid
high
1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
low mid high 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92
low high mid
1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92
若找到则返回该元素在表中的位置，否则为0。
int i=n;
r[0].key == k;

// 设置"哨兵“
while(r[i].key != k) i--; // 从后往前查找
return i; // 成功则返回位置不成功返回0
} // Search_Seq
顺序查找方法的ASL
设表中每个元素的查找概率相等pi
适用条件：采用顺序存储结构的有序表。 算法实现
❖设表长为n，low、high 和 mid分别指向待查元素所 在区间的上界、下界和中点,k为给定值
❖初始时，令low=1, high=n, mid=(low+high)/2 ❖让k与mid指向的记录比较
若k==r[mid].key，查找成功 若k<r[mid].key，则high=mid-1 若k>r[mid].key，则low=mid+1 ❖重复上述操作，直至low>high时，查找失败
//关键字
infotype otherinfo; //其他数据项
} NodeType;
Typedef NodeType Seqlist[n+1]； //多一个设置哨兵
顺序查找算法：
int Search_Seq (Seqlist r, KeyType k)
{ // 在顺序表ST中顺序查找其关键字等于kval的数据元素，