查找
查找的概念
主关键字：可唯一地标识一个记录的关键字就是主关键字
次关键字：用以识别若干记录的关键字就是次关键字
对查找表经常进行的操作：
- 查询某个“特定的”数据元素是否在查找表中；
- 检索某个“特定的”数据元素的各种属性；
- 在查找表中插入一个数据元素；
- 删除查找表中的某个数据元素；
查找表可以分为两类：
- 静态查找表：
仅作“查询”（检索）操作的查找表； - 动态查找表：
作“插入”和“删除”操作的查找表；
有时在查询之后，还需要将“查询”结果为“不在查找表中”的数据元素插入到查找表中；或者，从查找表中删除其“查询”结果为“在查找表中”的数据元素，此类为动态查找表；
查找算法的评价指标：
关键字的平均比较次数，也称平均查找长度ASL(Average Search Length)
A
S
L
=
∑
i
=
1
n
p
i
c
i
(
关
键
字
比
较
次
数
的
期
望
值
)
ASL= \sum_{i=1}^n {p_i}{c_i}\,(关键字比较次数的期望值)
ASL=i=1∑npici(关键字比较次数的期望值)
n
n
n：记录的个数；
p
i
p_i
pi：查找第i个记录的概率（通常认为
p
i
p_i
pi =
1
/
n
1/n
1/n）；
c
i
c_i
ci：找到第i个记录所需的比较次数；
查找的方法取决于查找表的结构，即表中数据元素是依何种关系组织在一起的；
因为“查询”或“检索”在计算机应用系统中使用频度都很高，因此需要设法提高查找表的查找效率；
为提高查找效率，一个办法就是在构造查找表时，在集合中的数据元素之间认为地加上某种确定的约束关系；
线性表的查找
顺序查找（线性查找）
顺序查找的特点：
优点：算法简单，逻辑次序无要求，且不同存储结构均适用；
缺点：ASL太长，时间效率低；
应用范围：
- 顺序或线性链表表示的静态查找表
- 表内元素之间无序
顺序表的表示：
//数据元素类型定义
typedef struct{
KeyType key; //关键字域
...... //其他域
}ElemType;
//顺序表结构定义类型
typedef struct{
ElemType *R; //表基址
int length; //表长
}SStable; //Sequential Search Table
SStable ST; //定义顺序表ST
算法：
int Search_Seq(SSTable ST, KeyType key){
//若成功返回其位置信息，否则返回0
for(i = ST.length; i >= 1; --i){
if(ST.R[i].key == key) return i;
else return 0;
}
}
其他形式：
int Search_Seq(SSTable ST, KeyType key){
for(i = ST.length; i >= 1;ST.R[i].key != key; --i)
if(i <= 0) break;
if(i > 0) return i;
else return 0;
}
改进：把待查关键字key存入表头（“哨兵”、“监视哨”），从后往前逐个比较，可免去查找过程中每一个都要检测是否完毕，加快速度
//设置监视哨的顺序查找
int Search_Seq(SSTable ST, KeyType key){
ST.R.key = key;
for(i = ST.length; ST.R[i].key != key; --i);
return i;
}
时间复杂度：
O
(
n
)
O(n)
O(n)
A
S
L
s
(
n
)
=
(
1
+
2
+
.
.
.
+
n
)
/
n
=
(
n
+
1
)
/
2
ASL_s(n)=(1+2+...+n) /n= (n+1)/2
ASLs(n)=(1+2+...+n)/n=(n+1)/2
1、记录的查找概率不相等时如何提高查找效率
查找表存储记录原则——按查找概率高低存储：
1）查找概率越高，比较次数越少；
2）查找概率越低，比较次数越多；
2、记录的查找概率无法测定时如何提高查找效率
方法——按查找概率动态调整记录顺序
1）在每个记录中设一个访问频度域；
2）始终保持记录按非递增有序的次序排列；
3）每次查找后均将刚查到的记录直接移至表头；
折半查找（二分或对分查找）
折半查找：每次将待查记录所在区间缩小一半
折半查找的特点：
优点：效率比顺序查找高；
缺点：只适用于有序表，且限于顺序存储结构（对线性链表无效）；
算法：
int Search_Binary(SSTable St, KeyType key){
low = 1;
high = ST.length; //置区间初值
while(low <= high){
mid = (low + high)/2;
if(ST.R[mid].key == key)
return mid; //找到待查元素
else if(key < ST.R[mid].key) //缩小查找区间
high = mid - 1; //继续在前半区间进行查找
else low = mid +1; //继续在后半区间进行查找
}
return 0; //顺序表中不存在待查元素
}//Search_Binary
递归算法：
int Search_Binary(SStable ST, keyType key, int low, int high){
if(low > high) return 0; //查找不到时返回0
mid = (low + high)/2;
if(key == ST.elem[mid].key)
return mid;
else if(key < ST.elem[mid].key)
...... //递归，在前半区间进行查找
else...... //递归，在后半区间进行查找
}
如果为顺序查找，则
A
S
L
=
(
11
+
1
)
/
2
=
6
ASL= (11+1)/2 = 6
ASL=(11+1)/2=6
平均查找长度ASL（成功时）：
设表长
n
=
2
h
−
1
n = 2^h - 1
n=2h−1， 则
h
=
l
o
g
2
(
n
+
1
)
h = log_2(n+1)
h=log2(n+1)（此时，判定树为深度 = h的满二叉树），且表中每个记录的查找概率相等：
P
i
=
1
/
n
P_i = 1/n
Pi=1/n，则：
A
S
L
=
∑
i
=
1
n
p
i
c
i
=
1
n
∑
i
=
1
n
c
i
=
n
∑
j
=
1
h
j
⋅
2
j
−
1
ASL=\sum_{i=1}^{n} p_ic_i = \frac{1}{n}\sum_{i=1}^{n}c_i= {n}\sum_{j=1}^{h}j·2^{j-1}
ASL=i=1∑npici=n1i=1∑nci=nj=1∑hj⋅2j−1
=
n
+
1
n
l
o
g
2
(
n
+
1
)
−
1
= \frac{n+1}{n}log_2(n+1)-1
=nn+1log2(n+1)−1
≈
l
o
g
2
(
n
+
1
)
−
1
（
n
>
50
）
≈log_2(n+1)-1（n > 50）
≈log2(n+1)−1（n>50）
j
j
j 为第
j
j
j 层的每个结点要比较的次数；
2
j
−
1
2^{j-1}
2j−1 为第
j
j
j 层结点数
分块查找
优点：插入和删除比较容易，无需进行大量移动；
缺点：要增加一个索引表的存储空间并对初始索引表进行排序运算；
适用情况：如果线性表既要快速查找又经常动态变化，则可采用分块查找；
查找方法的比较：