2.1.4 查找
考点:
3类查找算法及其时间复杂度
查找(又称检索),是实际应用中经常用到的操作,查找算法包括静态查找、动态查找和哈希查找3类算法。下面我们依次复习这3类查找算法的实现及优缺点。
1.静态查找
顺序查找算法的描述如下。其中,在顺序表st中查找元素key,若找到,就返回索引;否则,返回0。
Int Search(Stable st,keyType key)
{
keyType I;
st.elem[0].key=key;
for(i=st.length;i>=0&&st.elem[i].key!=key;--i);
return(i);
}
有序查找(折半查找)算法的描述如下。
Int Search(sTable st,keytype key)
{
Keytype low,high,mid;
Low=1;
High=st.length; //设置区间初值
While(low<=high)
{
Mid=(low+high)/2;
If(stelem[mid].key==key)return(mid);//找到待查元素
Else if(st.elem[mid].key<key)low=mid+1;
Else high=mid-1; //如果找不到,应根据不同情况缩小区间
}
Return 0;
}
2.动态查找
动态查找的特点是表结构本身在查找过程中动态生成。对于给定的key,若表中存在关键字等于key的记录,则查找成功返回;否则,插入关键字等于key的记录。
动态查找最常用的就是二叉排序树查找。二叉排序树查找法通过一系列的查找和插入过程形成树,按照中序遍历算法可以得到一个有序序列。
动态查找算法的描述如下。
//动态查找(二叉排序树查找)的链式存储结构定义
typedef struct BiTNode{
ElemType data;
Struct BiTNode *lchild,*rchild;
} BiTNode,*BiTree;
//二叉排序树的建立、查找,相关算法的实现和分析
BiTree SearchBST(BiTree bt,KeyType key){
if(bt==NULL) return NULL;//查找失败
else{
if EQ(bt->data.key,key) return bt;//查找成功
else if LT(bt->data.key,key) return(SearchBST(bt->lchild,key));
else return(SearchBST(bt->lchild,key));
}
}
void InsertBST(BiTree &bt,BiTree s){
//在二叉排序树中插入一个节点s
if(bt==NULL) bt=s;
else if EQ(s->data.key,bt->data.key) return ();//不插入节点
else if LT(s->data.key,bt->data.key) InsertBST(bt->lchild,s);//不插入节点
else InsertBST(bt->rchild,s);
}
void CreateBST(Bitree &bt){
//建立一棵二叉排序树,bt指向根节点
bt=NULL;
do{
scanf(&x);
s=(BiTree)malloc(sizeof(BiTNode));s->data.key=x;s->lchild=s->rchild=NUL};
InsertBST(bt,s);}
While(x!=-1);//重复输入一系列值,直至输入的值等于-1结束
}
Status DeleteBST(BiTree &bt,KeyType key){
//若bt指向的二叉排序树中存在关键字等于key的数据元素,则删除它
if(bt==NULL) return FALSE;
else{ if EQ(s->data.key,bt->data.key) Delete(bt);//不插入节点
else if LT(s->data.key,bt->data.key) DeleteBST(bt->lchild,key);
else DeleteBST(bt->rchild,key);
}
二叉排序树的删除是一个性能瓶颈问题。在随机情况下,二叉排序树的平均查找时间是和等数量级的。平衡二叉树用于平衡二叉排序树,当二叉排序树的左、右子树的差值的绝对值大于1时就需要平衡。平衡二叉树的平均查找时间是数量级的。
3.哈希查找
哈希查找是通过计算数据元素的存储地址进行查找的一种方法。
哈希查找的操作步骤如下。
(1)用给定的哈希函数建立哈希表。
(2)根据选择的冲突处理方法解决地址冲突。
(3)在哈希表的基础上进行哈希查找。
建立哈希表的操作步骤如下。
(1)取数据元素的key,计算其哈希函数值(地址)。若该地址对应的存储空间没有被占用,则将该元素存入;否则,执行步骤(2)解决冲突。
(2)根据选择的冲突处理方法,计算key的下一个地址。若下一个地址仍被占用,则继续执行步骤(2),直到找到能用的地址为止。
哈希查找步骤如下。
(1)设哈希表为HST[0~M?1],哈希函数取H(key),解决冲突的方法为R(x)?
(2)对给定k值,计算地址Di=H(k)?若HST为空,则查找失败;若HST=k,则查找成功;否则,执行步骤(2)(处理冲突)。
(3)重复计算处理冲突的下一个地址Dk=R(Dk-1),直到HST[Dk]为空或HST[Dk]=k为止。若HST[Dk]=k,则查找成功;否则,查找失败。
版权声明:51Testing软件测试网获得人民邮电出版社和作者授权连载本书部分章节。
任何个人或单位未获得明确的书面许可,不得对本文内容复制、转载或进行镜像,否则将追究法律责任。