dfs.c

用c++语言实现的dfs非递归算法 个人感觉不错仅供参考

#include<iostream.h>
#include<malloc.h>
#define LEN sizeof(struct Node)
#define MAXSIZE 100
bool visited[MAXSIZE];
int N;
struct Table{
char data;
struct Node*next;
};
struct Node{
int num;
struct Node*next;
};
struct STACK
         { Node stack[MAXSIZE];  
            int  top; 
         } ;  
void Initstack(struct STACK &s)
    { 
        s.top= -1;    //设置栈顶指针top，表示栈空
     }
void push(struct STACK &s, Node x)
     { if (s.top>=MAXSIZE-1)
             cout<<" ERROR";       //栈满，上溢
         else { s.top++;  
         s.stack[s.top]=x;
                      }
        }   //push
Node pop(struct STACK &s, Node &e)
{		 if (s.top<0){
	cout<<" ERROR";  
	//return ('0');
}      //栈空，下溢
         else {  e= s.stack[s.top];
                  s.top--;
                    return e;
                 }
        }  // pop
Node gettop(struct STACK &s,Node &e)
{ if (s.top<0){
	cout<<" ERROR"; 
		//return ('0');
}      //栈空，返回空值
         else { 
                   e= s.stack[s.top];
                  	return e; 
                 }
        }  // gettop
int StackEmpty (struct STACK &s)
     { if (s.top<0)
              return 1;       //栈空，返回TRUE
         else { 
                   return 0;
                 }
        }  // empty
void VisitFunc(struct Table *&G,int v){
cout<<G[v].data<<endl;
}
void DFS1(struct Table *&G, int v) {
int w,i,j;
STACK stack;
Node *p;
bool zhen=true;
Initstack(stack);
while(zhen){
	if(visited[v] == false) 
	{visited[v] =true;VisitFunc(G,v); }     // 访问第v 个结点
	else{
	if(!StackEmpty(stack))
	{*p=pop(stack,*p);
	v=p->num;if(visited[v] == false){visited[v] =true;VisitFunc(G,v);}}
	}//if end
    
	if(G[v].next==NULL){
		if(StackEmpty(stack)){
zhen=false;
		}
		else 	{*p=pop(stack,*p);v=p->num;if(p->next!=NULL)
		push(stack,*p);}
	}
	else{
	p=G[v].next;
	if(p->next!=NULL)
		push(stack,*p->next);
	v=p->num;
	}
	if(StackEmpty(stack)) {zhen=false;if(visited[v] == false){visited[v] =true;VisitFunc(G,v);}}
	
}
}
void DFSTraverse2(struct Table *&G , int v) {
	DFS1(G, v);
for (v=0; v<N; ++v) 
         if (!visited[v])  DFS1(G, v); 
} 
void main(){
struct Table  table[MAXSIZE],*aa;
struct Node *head,*p,*q;
int n,i,j;
char c;
cout<<"请输入节点数目"<<endl;
cin>>n;
N=n;
for(i=0;i<n;i++)
visited[i]=false;
for(i=0;i<n;i++){
cout<<"请输入第"<<i+1<<"个节点字母"<<endl;
cin>>c;
table[i].data=c;
cout<<"请输入与该节点相关联的节点,以#号结束"<<endl;
cin>>c;
j=0;
head=(struct Node *)malloc(LEN);
q=head;
while(c!='#'){
	p=(struct Node *)malloc(LEN);
	j++;
	p->num=c-48;
	p->next=NULL;
	q->next=p;
	q=p;
	cin>>c;
}//while
if(j==0)table[i].next=NULL;
else table[i].next=head->next;
}//表结构建立完
aa=table;
//建彪的测试
/*for(i=0;i<n;i++){
	if(aa[i].next!=NULL){
	p=aa[i].next;
	do{
	cout<<table[p->num].data;
	p=p->next;
	}
	while(p->next!=NULL);
	cout<<aa[p->num].data<<"  ";
	}
	else continue;
}
cout<<endl;*/
cout<<"请输入您想开始查找的节点"<<endl;
cin>>i;
DFSTraverse2(aa,i);
}