7.24.c

部分高校使用anyview编程测试数据结构习题,此代码为数据结构题集(c语言版)严蔚敏版的课后习题答案.专门提供给在anyview上运行,全部为通告代码

7.24③  试利用栈的基本操作编写，按深度优先搜索策略
遍历一个强连通图的非递归形式的算法。算法中不规定具
体的存储结构，而将图Graph看成是一种抽象的数据类型。

实现下列函数：
void Traverse(Graph dig, VertexType v0, void(*visit)(VertexType));
/* Travel the digraph 'dig' with Depth_First Search. */

图以及相关类型、函数和辅助变量定义如下：
Status visited[MAX_VERTEX_NUM];
int LocateVex(Graph g, VertexType v);
VertexType GetVex(Graph g, int i);
int FirstAdjVex(Graph g, int v);
int NextAdjVex(Graph g, int v, int w);
void visit(char v);

Status InitStack(SStack &s);
Status Push(SStack &s, SElemType x);
Status Pop(SStack &s, SElemType &x);
Status StackEmpty(SStack s);
Status GetTop(SStack s, SElemType &e);
void Traverse(Graph dig,  VertexType v0, void (*visit)(VertexType)) 
/* Travel the digraph 'dig' with Depth_First Search. */
{
 SStack s;
 SElemType e;
 int i,j,k,n=1,m=0,tag=0;   //n标记是否往下个连接点走一步
 InitStack(s);              //tag标记第一个往回走时是否有第一连接点
 if(dig.vexnum!=0)
  {
   i=LocateVex(dig,v0);
   Push(s,i);
   m++;
   visited[i]=1;   
   visit(GetVex(dig,i));
   while(!StackEmpty(s))
    {GetTop(s,e);
     j=FirstAdjVex(dig,e);
     while(!visited[j]&&j>=0)
      {Push(s,j);
       m++;
       visit(GetVex(dig,j));
       visited[j]=1;
       if(m==dig.vexnum) break;
       j=FirstAdjVex(dig,j);
           }//wlile
     while(n)
      {GetTop(s,e);
       if(!FirstAdjVex(dig,e)||tag)
        {Pop(s,e);
         tag=0;
             }
       if(!StackEmpty(s))
        {GetTop(s,e);
         i=FirstAdjVex(dig,e);
         if(i>=0&&visited[i])
          {k=NextAdjVex(dig,e,i);
           while(k>=0&&visited[k])
                   k=NextAdjVex(dig,e,k);
          } 
         tag=1; 
        } 
       else n=0;
       if(k>=0&&!visited[k])
        {Push(s,k);
         m++;       
         visit(GetVex(dig,k));
         visited[k]=1;
         n=0;
        }
     }
     n=1;
     tag=0;
    }//while
  }//if
}