Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1095987
  • 博文数量: 242
  • 博客积分: 10209
  • 博客等级: 上将
  • 技术积分: 3028
  • 用 户 组: 普通用户
  • 注册时间: 2008-03-12 09:27
文章分类

全部博文(242)

文章存档

2014年(1)

2013年(1)

2010年(51)

2009年(65)

2008年(124)

我的朋友

分类: C/C++

2010-09-20 17:53:11

#include
using namespace std;

#define PAUSE system("PAUSE")
#define NUM 9

enum COLOR {WHITE,GRAY,BLACK};

typedef struct Node
{
char vertex;
struct Node *next;
}*pNode;

typedef struct NodeLink
{
COLOR color;
char vertex;
int StartTime;
int FinishTime;
struct Node *link;
}*pNodeLink;

typedef struct Stack
{
char vertex[NUM];
int top;
}*pStack;

void InitStack(pStack s)
{
s->top = -1;
}

void Push(pStack s,char vertex)
{
s->top++;
s->vertex[s->top] = vertex;
}

char Pop(pStack s)
{
s->top--;
return s->vertex[s->top+1];
}

char GetStackTop(pStack s)
{
return s->vertex[s->top];
}

bool IsEmpty(pStack s)
{
return (s->top == -1)?(true):(false);
}

pNodeLink CreatLink()
{
char listTable[NUM][4]={{'h','b'},{'h','c','a'},{'i','f','d','b'},{'f','e','c'},{'f','d'},{'g','e','d','c'},{'i','h','f'},{'i','g','b','a'},{'h','g','c'}};
int size[NUM]={2,3,4,3,2,4,3,4,3};

pNodeLink p = new NodeLink[NUM];

for (int i=0;i {
   p[i].color = WHITE;
   p[i].link = NULL;
   p[i].vertex = 'a' + i;

   for (int j=0;j    {
    pNode newNode = new Node[1];
    newNode->vertex = listTable[i][j];
    newNode->next = p[i].link;
    p[i].link = newNode;
   }
}

return p;

}

void DFS(pNodeLink p,char vertex)
{
pStack s = new Stack[1];
pNode ptr;
int time = 0;

InitStack(s);
Push(s,vertex);
cout<<"Visit "< p[vertex-'a'].color = GRAY;
p[vertex-'a'].StartTime = ++time;

while (!IsEmpty(s))
{
   char c = GetStackTop(s);

   ptr = p[c-'a'].link;

   while (ptr&&p[ptr->vertex-'a'].color!=WHITE)
    ptr = ptr->next;

   if (ptr)
   {
    if (p[ptr->vertex-'a'].color==WHITE)
    {
     cout<<"Visit "<vertex<      p[ptr->vertex-'a'].color = GRAY;
     p[ptr->vertex-'a'].StartTime = ++time;
     Push(s,ptr->vertex);
    }
   }
   else
   {
    c = Pop(s);
    p[c-'a'].color = BLACK;
    p[c-'a'].FinishTime = ++time;
   }
}

}

void main()
{
pNodeLink p = CreatLink();
DFS(p,'a');
PAUSE;

}

阅读(4852) | 评论(1) | 转发(0) |
给主人留下些什么吧!~~

chinaunix网友2010-09-23 19:00:05

很好的, 收藏了 推荐一个博客,提供很多免费软件编程电子书下载: http://free-ebooks.appspot.com