树、二叉树、图的遍历—软件测试工程师面试秘籍(4)

发表于:2014-11-12 13:29

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

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

分享:
(51Testing软件测试网获得作者授权连载本书部分章节。任何个人或单位未获得明确的书面许可,不得对本文内容复制、转载或进行镜像,否则将追究法律责任。)
  图的广度优先搜索法是树的按层次遍历的推广,它的基本思想是:首先访问初始点vi,并将其标记为已访问,接着访问vi的所有未被访问的邻接点vi1,vi2,……,vit,并均标记已访问。然后再按照vi1,vi2,……,vit的次序,访问每一个顶点的所有未被访问的邻接点,并均标记为已访问,依此类推,直到图中所有和初始点vi有路径相通的顶点都被访问为止。其非递归算法如下。
Boolean visited[MAX_VERTEX_NUM]; //访问标志数组
Status (*VisitFunc)(int v); //VisitFunc是访问函数,对图的每个顶点调用该函数
void BFSTraverse (Graph G, Status(*Visit)(int v)){
VisitFunc = Visit;
for(v=0; v<G.vexnum, ++v)
visited[v] = FALSE;
initQueue(Q); //置空辅助队列Q
for(v=0; v<G.vexnum; ++v)
if(!visited[v]){
visited[v]=TRUE; VisitFunc(v);
EnQueue(Q, v); //v入队列
while(!QueueEmpty(Q)){
DeQueue(Q, u); //队头元素出队并置为u
for(w=FirstAdjVex(G,u); w>=0; w=NextAdjVex(G,u,w))
if(!Visited[w]){ //w为u的尚未访问的邻接顶点
Visited[w]=TRUE; VisitFunc(w);
EnQueue(Q, w);
}
}
}
}
  2.1.4  查找
  三大类查找算法及其时间复杂度。
  查找,又称为检索,是实际应用中经常用到的操作,它包括静态查找表、动态查找表、哈西查找表三大类。下面我们依次复习这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){
// 在二叉排序树bt中插入一个结点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结束
}//CreateBST
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,计算其哈希函数值(地址)。若该地址对应的存储空间还没有被占用,则将该元素存入;否则执行step2解决冲突。
  (2)根据选择的冲突处理方法,计算关键字key的下一个存储地址。若下一个存储地址仍被占用,则继续执行step2,直到找到能用的存储地址为止。
  哈希查找步骤为如下。
  (1)设哈希表为HST[0~M-1],哈希函数取H(key),解决冲突的方法为R(x);
  (2)对给定k值,计算哈希地址 Di=H(k);若HST为空,则查找失败;若HST=k,则查找成功;否则,执行step2(处理冲突)。
  (3)重复计算处理冲突的下一个存储地址 Dk=R(Dk-1),直到HST[Dk]为空,或HST[Dk]=k为止。若HST[Dk]=K,则查找成功,否则查找失败。
本文选自《软件测试工程师面试秘籍》,本站经作者的授权。
版权声明:51Testing软件测试网获作者授权连载本书部分章节。
任何个人或单位未获得明确的书面许可,不得对本文内容复制、转载或进行镜像,否则将追究法律责任。
相关文章:
磨刀霍霍,有备无患—软件测试工程师面试秘籍(3)
33/3<123
重磅发布,2022软件测试行业现状调查报告~

关注51Testing

联系我们

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

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

沪ICP备05003035号

沪公网安备 31010102002173号