技术
查找
查找的基本概念
列表:由同一类型的数据元素(或记录)构成的集合,可利用任意数据结构实现
关键字:数据元素的某个数据项的值可标识列表中的一个数据元素
主关键字可唯一标识列表中的一个数据元素,否则为次关键字
查找:根据给定的关键字值,在特定的列表中确定一个其关键字与给定值相同的数据元素,并返回该数据元素在列表中的位置
- 查找对象 K(找什么)
- 查找范围 L(在哪找)
- K 在 L 中的位置(查找的结果)
平均查找长度(ASL):查找过程中对关键码的比较次数的平均值
ASL=P_1C_1+P_2C_2+…+P_nC_n=\sum_{i=1}^nP_iC_i\\ P_i为查找概率,C_i为查找次数
查找基本方法:
- 线性表查找法
- 树表式查找法
- 计算式(哈希)查找法
基于线性表的查找法
顺序查找法
数据类型定义
#define KeyType int
#define OtherType int
#define LIST_SIZE 20
typedef struct
{
KeyType key;
OtherType other_data;
} RecordType;
typedef struct
{
RecordType r[LIST_SIZE + 1]; // r[0]为工作单元
int length;
} RecordList;
顺序结构算法
此处为从后往前的顺序:
//不设置监视哨,在顺序表中查找关键字等于k的元素
int SeqSearch_1(RecordList L, KeyType k)
{
int i;
for (i = L.length; i >= 1 && L.r[i].key != k; i--)
;
if (i >= 1)
return i;
else
return 0;
}
//设置监视哨,顺序表L由后往前查找关键字k,查到返回k在L中的位置,否则返0
int SeqSearch_2(RecordList L, KeyType k)
{
int i;
L.r[0].key = k;
for (i = L.length; L.r[i].key != k; i--)
;
return i;
}
性能分析
n为表长,c_i为比较次数\\
c_1=n-1+1\\
c_2=n-2+1\\
…\\
c_n=n-n+1\\
即c_i=n-i+1\\
查找每个元素的概率相等,即P_i=\frac{1}{n}\\
查找成功时平均查找长度为\\
ASL_{succ}=\sum_{i=1}^nP_iC_i=\frac{1}{n}\sum_{i=1}^nC_i=\frac{1}{n}\sum_{i=1}^n(n-i+1)=\frac{n+1}{2}
ASL为
O(n)
折半查找法
定义
折半查找(二分查找),要求:
- 采用顺序存储
- 关键字有序排列
基本过程
中间记录关键字与查找关键字比较:
如果两者相等,则查找成功;
否则如查找关键字小于中间位置关键字,则查前部子表,否则查找后部子表。
算法
int BinSrchZ(SqList L, KeyType k)
{
int low, high, mid;
low = 1;
high = L.length; //置区间初值
while (low <= high)
{
mid = (low + high) / 2;
if (k == L.r[mid].key)
return mid; //查找成功
else if (k < L.r[mid].key)
high = mid - 1; //继续在前半区间查找
else
low = mid + 1; //继续在后半区间查找
}
return 0;
}
性能分析
折半查找过程可用判定树描述判定树结构:
- 树中每一结点表示表中一记录结点值记录在表中的位置
- 从根到被查结点路径关键字比较次数为被查结点层数
- 成功进行最多比较次数不超过树深度
\lfloor\log_2n\rfloor +1
假定表的长度n=2h-1
,则相应判定树必为深度是 h 的满二叉树,h=\log_2(n+1)
折半查找成功的平均查找长度:
ASL_{bs}=\sum_{i=1}^nP_iC_i=\frac{1}{n}\sum_{j=1}^hj×2^{j-1}=\frac{n+1}{n}\log_2(n+1)-1
每个记录的查找概率相等,j 为每层的比较次数,2^{j-1}
为每层的元素个数
ASL为
O(\log_2n)
- 优点:
- 比较次数少
- 查找速度快
- 平均性能好
- 适用于固定长度频繁查找的有序表
- 缺点:
- 要求待查表为有序表
- 插入删除时需再排序
分块查找法
对所查表要求
- 等长分块,最后一块可不满
- 块内无序
- 块间有序
基本思想
- 分块构造索引表
- 定块可用顺序或折半查找关键字 k 与索引表关键字比较,确定该查记录所在块
- 块内顺序查找
平均查找长度
查找索引表的平均查找长度L_B
,相应块内顺序查找的平均查找长度L_W
平均查找长度:ASL_{bs}=L_B+L_W
假定将长度为 n 的表分成 b 块,每块含 s 个元素,则b=\frac{n}{s}
,
又假定表中每个元素的查找概率相等,则每个索引项的查找概率为\frac{1}{b}
,块中每个元素的查找概率为\frac{1}{s}
。则有
顺序法平均查找长度:
L_B=\frac{1}{b}\sum_{j=1}^bj=\frac{b+1}{2}\\ L_W=\frac{1}{s}\sum_{i=1}^si=\frac{s+1}{2}\\
将
b=\frac{n}{s}
代入得ASL_{bs}=\frac{\frac{n}{s}+1}{2}+1\\ =\frac{b+1+s+1}{2}\\ =\frac{b+s}{2}+1
折半法平均查找长度:
L_B=\log_2(b+1)-1\\ ASL_{bs}=\log_2(b+1)-1+\frac{s+1}{2}\\ =\log_2(\frac{s}{n}+1)+\frac{s-1}{2}
基于树的查找法
步骤:
- 将待查表组织成特定树
- 在树结构上实现查找
有三种树:
- 二叉排序树
- 平衡二叉树
- B 树
此处重点讲述二叉排序树
二叉排序树
定义
二叉树排序树或者是一棵空树,或者是具有如下性质的二叉树:
- 若它的左子树非空,则左子树上所有结点的值均小于根结点的值
- 若它的右子树非空,则右子树上所有结点的值均大于根结点的值
- 它的左右子树也分别为二叉排序树
插入和生成
- 若二叉排序树是空树,则
key
成为二叉排序树的根 - 若二叉排序树非空,
key
与二叉排序树的根比较:key
的值小于根结点的值,则将key
插入左子树key
的值大于等于根结点的值,则将key
插入右子树
void CreateBST(BSTree *bst) //从键盘输入元素的值,创建相应的二叉排序树
{
KeyType key;
*bst = NULL;
scanf("%d", &key);
while (key != ENDKEY)
{
InsertBST(bst, key);
scanf("%d", &key);
}
}
void InsertBST(BSTree *bst, KeyType key) // key插入到bst为根的二叉排序树,从根比
{
BiTree s;
if (!*bst)
{
s = (BSTree)malloc(sizeof(BSTNode));
s->key = key;
s->LChild = s->RChild = NULL;
*bst = s;
}
else if (key < (*bst)->key)
InsertBST(&((*bst)->LChild), key);
else
InsertBST(&((*bst)->RChild), key);
}
插入一个结点
InsertBST(bst, key)
时间复杂度为O(\log_2n)
,创建二叉排序树 n 个结点的时间复杂度为O(n\log_2n)
。
对二叉排序树进行中序遍历,一定会得到一个递增有序序列。
查找
方法:
根据二叉排序树的特点,关键字 k 与根 t 比较:
- key = t:返回根结点地址
- key < t:进一步查左子树
- key > t:进一步查右子树
算法:
递归
BSTree SearchBST(BSTree bst, KeyType key) { if (!bst) return NULL; else if (bst->key == key) return bst; else if (bst->key > key) return SearchBST(bst->LChild, key); else return SearchBST(bst->RChild, key); }
非递归
BSTree SearchBST_2(BSTree bst, KeyType key) //非递归查找 { BSTree q; q = bst; while (q) { if (q->key == key) return q; //查找成功 else if (q->key > key) q = q->LChild; else q = q->RChild; } return NULL; //查找失败 }
查找性能
平均查找长度和二叉排序树的形态有关:
就平均性能而言,二叉排序树上的查找和二分查找相差不大,并且二叉排序树上的插入和删除结点十分方便,无需移动大量结点
最好情况:
二叉排序树接近二分平衡树,平均查找长度大约是
\log_2n
最坏情况:
得到一棵深度为 n 的单支树,平均查找长度和单链表上的顺序查找相同,是
\frac{n+1}{2}
。
平衡二叉树
定义
平衡二叉排序树又称为 AVL 树。
一棵平衡二叉排序树或者是空树,或者是具有下列性质的二叉排序树:
- 左子树与右子树的高度之差的绝对值小于等于 1
- 左子树和右子树也是平衡二叉排序树
平衡因子
平衡因子(balance factor)即结点的左子树深度与右子树深度之差。
对一棵平衡二叉排序树而言,其所有结点的平衡因子只能是 -1、0 或 1。
计算式查找法——哈希法
哈希的基本思想
比较式查找通过对关键字的一系列查找比较实现,效率与查找表长有关,当关键字可能取值的集合远远大于实际表长时,比较式查找效率低。
而计算式查找对关键字计算得到对应元素的地址H(key)=Addr
哈希法(散列法、杂凑法)基本思想:
哈希函数:
建立哈希函数
p=H(key)
,计算关键字 key 在哈希表中的存储位置 p。冲突:
冲突问题:若关键字
key_1 key_2
,哈希函数值H(key_1)= H(key_2)
,则发生冲突。
冲突原因:
- 必然性:由于关键字可能的取值空间远远大于哈希表的地址空间,冲突不可避免
- 可能性:哈希函数
H(key)
的散列性能不好,可能加剧冲突发生
哈希函数的构造方法
原则:
- 函数本身便于计算
- 计算出来的地址分布均匀
方法:
数字分析法:
从关键字中选出分布较均匀的若干位,构成哈希地址
平方取中法:
先求出关键字的平方值,然后按需要取平方值的中间几位作为哈希地址
分段叠加法:
按哈希表地址位数将关键字分成位数相等的几部分(最后一部分可以较短),然后将这几部分相加,舍弃最高进位后的结果就是该关键字的哈希地址。
除留余数法:
哈希函数为
H(K)=K\%P
,其中%为模 P 取余运算,表长为 m,P 应为小于等于 m 的最大素数伪随机数法:
采用一个伪随机函数做哈希函数,即
h(key)=random(key)
。
处理冲突的方法
开放定址法
当关键字 key 的哈希地址
p=H (key)
出现冲突时,以 p 为基础,产生另一个哈希地址p_1
,如果p_1
仍然冲突,再以 p 为基础,产生另一个哈希地址p_2
,…,直到找出一个不冲突的哈希地址p_i
,将相应元素存入其中。通用的再散列函数形式:H_i=(H(key)+d_i)\%m
形成$d_i$的方法:
线性探测再散列
d_i=1,2,3,…,m-1
冲突发生时,顺序查看表中下一单元,直到找出一个空单元或查遍全表
二次探测再散列
d_i=1^2,-1^2,2^2,-2^2,…,k^2,-k^2
特点:冲突发生时,在表的左右进行跳跃式探测,比较灵活
伪随机探测再散列
d_i=伪随机数序列
再哈希法
同时构造多个不同的哈希函数:
H_i=RH_1(key), i=1,2,…,k
当哈希地址
H_i=RH_1(key)
发生冲突时,再计算H_i=RH_2(key)
……直到冲突不再产生。这种方法不易产生聚集,但增加了计算时间。
链地址法
建立公共溢出区
将哈希表分为基本表和溢出表两部分,凡是和基本表发生冲突的元素,一律填入溢出表
哈希表的查找过程
哈希表的查找过程与哈希表的创建过程规则一致
注意:查到空单元时表示找不到
查找过程:
计算
p_0=hash(K)
如果单元
p_0
为空,则所查元素不存在如果单元
p_0
中元素的关键字为K,则找到所查元素否则重复下述解决冲突的过程:
按解决冲突的方法,找出下一个哈希地址
p_i
- 如果单元
p_i
为空,则所查元素不存在 - 如果单元
p_i
中元素的关键字为K,则找到所查元素
- 如果单元
查找算法:
int HashSearch(HashTable ht, KeyType K)
{
int i, p0, pi;
p0 = hash(K);
if (ht[p0].key == NULLKEY)
return -1;
else if (ht[p0].key == K)
return 0;
else //线性探测再散列
{
for (i = 1; i <= m - 1; i++)
{
pi = (p0 + i) % m;
if (ht[pi].key == NULLKEY)
return -1;
else if (ht[pi].key == K)
return pi;
}
return -1;
}
}
哈希法性能分析
影响比较次数的因素:
哈希函数
处理冲突的方法
装填因子
哈希表的装填因子 α 的定义:
α=\frac{哈希表中元素个数}{哈希表的长度}
α 可描述哈希表的装满程度。显然,α 越小,发生冲突的可能性越小;而 α 越大,发生冲突的可能性也越大。
等概率情况下查找成功的平均查找长度:
ASL_{succ}=\frac{1}{表中置入元素个数n}\sum_{i=1}^nC_i
等概率情况下查找不成功的平均查找长度公式
ASL_{unsucc}=\frac{1}{哈希函数取值个数r}\sum_{i=0}^{r-1}C_i
线性探测再散列:
ASL_{succ}≈\frac{1+\frac{1}{1-α}}{2}\\ ASL_{unsucc}=\frac{1+\frac{1}{(1-α)^2}}{2}
伪随机探测再散列、二次探测再散列、再哈希:
ASL_{succ}≈-\frac{\ln(1-α)}{α}\\ ASL_{unsucc}=\frac{1}{1-α}
链址法:
ASL_{succ}≈1+\frac{α}{2}\\ ASL_{unsucc}=α+e^{-α}