图的广度优先搜索法是树的按层次遍历的推广,它的基本思想是:首先访问初始点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软件测试网获作者授权连载本书部分章节。
任何个人或单位未获得明确的书面许可,不得对本文内容复制、转载或进行镜像,否则将追究法律责任。
相关文章: