//一个无向图关糸邻接表的遍历,有几个错误,大家帮帮忙.拜托了,
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#define OVERFLOW -2
#define ERROR -1
#define NULL 0
#define OK 1
#define MAX_VEX_NUM 20
#define MAXQSIZE 20
typedef struct ArcNode{
int adjvex;
struct ArcNode *nextarc;
}ArcNode;
typedef struct VNode{
int data;
ArcNode *firstarc;
}VNode ;
typedef struct{
VNode Adjlist[1+MAX_VEX_NUM];
int vexnum,arcnum;
}ALGraph;
typedef struct Qnode
{
int data;
struct Qnode *next;
}Qnode,*QueuePtr;
typedef struct linkqueue
{
QueuePtr front;
QueuePtr rear;
}linkqueue;
linkqueue Q;
ALGraph G;
ArcNode *p[1+MAX_VEX_NUM];//建邻接表所用的每个顶点的指针
int visite[1+MAX_VEX_NUM];//顶点是否被访问过的的标志
void creat();
void DFSTraverse();
void DFS(ALGraph G,int v);
void cread(ALGraph &G);
int FirstAdjVex(ALGraph G,int v);
int NextAdjVex(ALGraph G,int v,int u);
void BFSTraverse();
int EnQueue(linkqueue &Q,int e);
int InitQueue(linkqueue Q)
{
Q.front =Q.rear =(QueuePtr)malloc(sizeof(Qnode));
if(!Q.front )exit(0);
Q.front ->next = NULL;
return OK;
}
int EnQueue(linkqueue &Q,int e)
{
QueuePtr p;
p=(QueuePtr)malloc(sizeof(Qnode));
if(!p)exit(OVERFLOW);
P->data = e; // F:\c\data struct\53l.cpp(63) : error C2065: 'P' : undeclared identifier
Q.rear ->next=p; //明明 声明了为什么说没声明呢?????
Q.rear =p;
return OK;
}
int DeQueue(linkqueue &Q,int &e)
{
Qnode *p;
if(Q.front==Q.rear)return ERROR;
p= Q.front ->next ;
e=p->data ;
Q.front->next =p->next ;
if(Q.rear ==p)Q.rear =Q.front ;
free(p);
return OK ;
}
int QueueEmpty(linkqueue Q);
{ //F:\c\data struct\53l.cpp(84) : error C2447: missing function header (old-style formal list?)
//这是什么错误啊,,
if(Q.front==Q.rear)return OK;
else return 0;
}
void creat(ALGraph &G)
{
int i;
int m,n;
ArcNode *q;
for(i=1;i<=G.vexnum;i++)
{
G.Adjlist[i].data=i;//初始化顶点名。用数字从1开始。
G.Adjlist[i].firstarc->adjvex=0;
p[i]=G.Adjlist[i].firstarc;
}
for(i=0;i<G.arcnum;i++)
{
printf("the arc:");
scanf("%d",&m); scanf("%d",&n);
q=(ArcNode *)malloc(sizeof(ArcNode));
q->adjvex=n;
if(!G.Adjlist[m].firstarc)
{
G.Adjlist[m].firstarc->adjvex=q->adjvex;
p[m]=q->nextarc;
}
else
{
p[m]->adjvex=q->adjvex;
p[m]=q->nextarc;
}
}
}
void DFSTraverse(ALGraph G)
{
int v;
for(v=1;v<=G.vexnum;++v)visite[v]=0;
for(v=1;v<=G.vexnum;++v)
{
if(!visite[v])DFS(G,v);
}
}
void DFS(ALGraph G,int v)
{
int w;
visite[v]=1;printf("%d,",v);
for(w=FirstAdjVex(G,v);w>0;w=NextAdjVex(G,v,w))
if(!visite[v])DFS(G,w);
}
int FirstAdjVex(ALGraph G,int v)//在图G中寻找第v个顶点的第一个邻接顶点
{
if(!G.Adjlist[v].firstarc->adjvex) return 0;
else return(G.Adjlist[v].firstarc->adjvex);
}
int NextAdjVex(ALGraph G,int v,int u)//在图G中寻找第v个顶点的相对于u的下一个邻接顶点
{
ArcNode *p;
p=G.Adjlist[v].firstarc;
while(p->adjvex!=u) p=p->nextarc; //在顶点v的弧链中找到顶点u
if(p->nextarc==NULL) return 0; //若已是最后一个顶点，返回0
else return(p->nextarc->adjvex); //返回下一个邻接顶点的序号
}
void BFSTraverse(ALGraph G)
{
int v,w,u;
for(v=1;v<G.vexnum;++v)visite[v]=0;
InitQueue(Q);
for(v=1;v<G.vexnum;++v)
if(!visite[v])
{
printf("%d,",v);
EnQueue(Q,v);
while(!QueueEmpty(Q))
{
DeQueue(Q,u);
for(w=FirstAdjVex(G,u);w>0;w=NextAdjVex(G,u,w))
if(visite[w])
{
visite[w]=1;printf("%d,",w);
EnQueue(Q,w);
}//if
}//while
}//if
}
void main()
{
printf("input the vexnum of the graph:");
scanf("%d",&G.vexnum);
printf("input the arcnum of the graph:");
scanf("%d",&G.arcnum);
creat(G);
printf("deepfisrt:");
DFSTraverse(G);
printf("\nbroadfist:");
BFSTraverse(G);
}
