青岛菲比爱上酒吧招聘:关于“图的深度优先遍历”调试问题

/*我将你的程序调试一下,现在搞定了
程序当中你的错误是出在那个void trave(adjlist g,int n)函数当中,
因为你在这个函数当中的第二行声明了一个函数叫做void dfs();而错误
就是出在这个地方,你给的错误的意思是:dfs函数不接受3个参数,
很显然你声明的void dfs()没有3个参数,所以编译时报错了,即使你
在下面给个一个带有3个参数的dfs定义,但是已经太晚了.
故,你要先声明一个带有三个参数的dfs函数
像这样:void dfs(adjlist g,int k,int visited[]);

再改你的一个说法的错误:你说是调试时错误,这句话也是不准确的
应该说是在编译时出错,因为此时程序还没有正式开始运行,也就是
还没有到调试这一步程序就已经有语法上的错误了.

这个是大错误,经过我的解释,我想你应该已经了解了
你这个程序还有几个小错误:
我运行了一下发现了算发上有一点小错误(我猜测这只是你打字时的笔误,而
不是理解上的错误)
错误一:在你的main函数中有一个循环:

for(k=0;k<n;k++)
{
cout<<"node="<<k;
g[k].firstarc=NULL;
}
这个是初始化数组的循环，但是g中的vertex成员变量未被初始化,我将其改为
for(k=0;k<n;k++)
{
cout<<"node="<<k;
g[k].firstarc=NULL;
g[k].vertex=k; //这个是我增加的一行
}
因为你的vertex要初始化，要不然，你的dfs函数里面的第四句话
cout<<g[k].vertex;
就会随意打印出一些错误的，未经过初始化的数字出来，因为你没有在任何地方对g[k].vertex赋值

好了这个是第一个错误
下面再看
第二个错误:
在你的main函数中的
for(;;)循环里面有一段

p=(arcnode *)malloc(sizeof(arcnode));
p->adivex=i;
p->nextarc=g[i].firstarc;
g[i].firstarc=p;

我将你的g[i].firstarc改为g[j].firstarc，向j这个顶点中加入j到i这条边的信息.
根据你的算法用的应该是邻接表存储无向图的，如果不改为g[j]的话，你就向g[i]中一次插入两个边信息了,分别为从i到j这条边和从j到i这条边，而且程序运行也得不到正确结果的。那有什么意义呢？

好了错误讲完了，希望楼主彻底理解。
我将你的代码修改了一下并给出了一个我测试并且编译通过，运行正确的代码。
你可以直接拷贝运行，如果有什么不懂的话发我邮箱: ddrmsdos@163.com
*/
#include <iostream>
using namespace std;
#define maxnode 40

typedef struct st_arc
{
int adivex; //存放依附于该边的另一顶点在一维数组中的序号
int weigh; //存放和帽哂泄氐男畔ⅲ?缛ㄖ档?
struct st_arc *nextarc; //依附于该顶点的下一个边结点的指针
}arcnode; //链式结构存储边信息

typedef struct
{
int vertex; //存放与顶点有关的信息
struct st_arc *firstarc; //指针域，存放与该顶点相邻接的所有顶点组成的单链表的头指针
}vernode; //存储顶点信息

//注意：在这里声明dfs函数
typedef vernode adjlist[maxnode];
void dfs(adjlist g,int k,int visited[]);
void trave(adjlist g,int n) //当图采用邻接表作存储结构时，深度优先遍历该图
{
int i,visited[maxnode]; //数组visited标志图中的定点是否已被访问
// void dfs(); 函数dfs在trave前面声明了
for(i=0;i<n;i++)
visited[i]=0; //数组初始化
for(i=0;i<n;i++)
if(visited[i]==0)
dfs(g,i,visited);
}

void dfs(adjlist g,int k,int visited[]) //从顶点k出发，深度优先遍历图g
{
arcnode *p;
int w;
visited[k]=1;
cout<<g[k].vertex;
p=g[k].firstarc;
while(p!=NULL)
{
w=p->adivex;
if(visited[w]==0)
dfs(g,w,visited);
p=p->nextarc;
}
}

void main()
{
int i,j,n,k,v;
arcnode *p,*q;
adjlist g;
cout<<"Input node: ";
cin>>n;
for(k=0;k<n;k++)
{
cout<<"node="<<k;
g[k].firstarc=NULL;
//注意这个地方，我加入了下面这一行
g[k].vertex=k;
}
for(;;)
{
cout<<"Insert edge i-j: ";
cin>>i>>j;
if(i==-1&&j==-1)
break;
q=(arcnode *)malloc(sizeof(arcnode));
q->adivex=j;
q->nextarc=g[i].firstarc;
g[i].firstarc=q;
p=(arcnode *)malloc(sizeof(arcnode));
p->adivex=i;
p->nextarc=g[j].firstarc; //

//注意这个地方我将i改为j了
g[j].firstarc=p;

}
cout<<"dfs: ";
trave(g,n);
cout<<endl;
}