数据结构之查找——软件测试工程师面试秘籍(08)

发表于:2021-11-23 09:44

字体: | 上一篇 | 下一篇 | 我要投稿

 作者:G. li    来源:51Testing软件测试网原创

#
面试
#
求职
分享:
  2.1.4  查找
  考点:
  3类查找算法及其时间复杂度
  查找(又称检索),是实际应用中经常用到的操作,查找算法包括静态查找、动态查找和哈希查找3类算法。下面我们依次复习这3类查找算法的实现及优缺点。

  1.静态查找
  顺序查找、有序查找都属于静态查找。其中,顺序查找的平均时间是,即时间复杂度为O(n)。有序查找的前提是表必须是有序的,性能在平均分布的时候最优,平均时间是,即时间复杂度为
  顺序查找算法的描述如下。其中,在顺序表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软件测试网获得人民邮电出版社和作者授权连载本书部分章节。
任何个人或单位未获得明确的书面许可,不得对本文内容复制、转载或进行镜像,否则将追究法律责任。
《2023软件测试行业现状调查报告》独家发布~

关注51Testing

联系我们

快捷面板 站点地图 联系我们 广告服务 关于我们 站长统计 发展历程

法律顾问:上海兰迪律师事务所 项棋律师
版权所有 上海博为峰软件技术股份有限公司 Copyright©51testing.com 2003-2024
投诉及意见反馈:webmaster@51testing.com; 业务联系:service@51testing.com 021-64471599-8017

沪ICP备05003035号

沪公网安备 31010102002173号