数据结构图用邻接表创建并且深度和广度遍历出bug了

Russellll 发布于 2013/05/23 22:42
阅读 298
收藏 0

代码是:

#include<stdio.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define NULL 0
typedef int Status;
#define MAX_VERTEX_NUM 20
typedef struct Node
{
 int elem;
 struct Node *next;
}Node,*QNode;
typedef struct Queue{
QNode front;
QNode rear;
}Queue;
typedef struct ArcNode{//表结点
int adjvex;     //该狐所指向的顶点的位置
struct ArcNode *nextarc;//指向下一条狐的指针
}ArcNode;
typedef struct VNode{    //头结点
int data;//顶点信息
ArcNode *firstarc;//指向第一条依附该顶点的狐的指针
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct{
AdjList vertices;
int vexnum,arcnum;     //图的当前顶点数和狐数
}ALGraph;
Status InitQueue(Queue *Q)
{
Q->front=Q->rear=(QNode)malloc(sizeof(Node));
if(!Q->front) exit(OVERFLOW);
Q->front->next=NULL;
return OK;
}
Status EnQueue(Queue *Q,int e)
{
QNode p=(QNode)malloc(sizeof(Node));
if(!p) exit(OVERFLOW);
p->elem=e;
p->next=NULL;
Q->rear->next=p;
Q->rear=p;
return OK;
}
Status DeQueue(Queue *Q,int *e)
{
QNode p;
p=Q->front->next;
Q->front->next=p->next;
if(Q->rear==p)
Q->rear=Q->front;
*e=p->elem;
free(p);
return OK;
}
Status QueueEmpty(Queue Q)
{
if(Q.rear==Q.front)
return TRUE;
else
return FALSE;
}
int LocateVex(ALGraph *G,int v)//返回结点v在图中的位置
{
int i;
for(i=0;i<G->vexnum;++i)
{
if(G->vertices[i].data==v)
break;

else
continue;
}
if(i<G->vexnum)
return i;
else
return -1;
}
Status CreateGraph(ALGraph *G)//以邻接表形式创建无向连通图G
{
int m,n,i,j,k,v1,v2,flag=0;
ArcNode *p1,*q1,*p,*q;
printf("请输入图的顶点数目:");
scanf("%d",&m);
    printf("请输入图的边的数目:");
scanf("%d",&n);
G->vexnum=m;
G->arcnum=n;
for(i=0;i<G->vexnum;++i)
{
G->vertices[i].data=i+1;
G->vertices[i].firstarc=NULL;
}
printf("输出顶点信息是:\n");
for(i=0;i<G->vexnum ;++i)
printf("v%d\n",G->vertices[i].data);
for(k=0;k<G->arcnum;++k)
{
printf("请输入第%d条弧的两个端点:",k+1);
   scanf("%d%d",&v1,&v2);
i=LocateVex(G,v1);
j=LocateVex(G,v2);


if(i>=0&&j>=0)
{
++flag;
p=(ArcNode *)malloc(sizeof(ArcNode));
p->adjvex=j;
p->nextarc=NULL;
if(!G->vertices[i].firstarc)
G->vertices[i].firstarc=p;
else
{
for(p1=G->vertices[i].firstarc;p1->nextarc;p1=p1->nextarc)
p1->nextarc =p;
}
q=(ArcNode *)malloc(sizeof(ArcNode));
q->adjvex=i;
q->nextarc =NULL;
if(!G->vertices[j].firstarc)
G->vertices[j].firstarc=q;
else
{
for(q1=G->vertices[j].firstarc;q1->nextarc;q1=q1->nextarc )
q1->nextarc =q;
}
}
else
{
printf("所输入的弧不符合规范!\n");
k=flag;
}
}
printf("邻接表是:\n");
for(i=0;i<G->vexnum;++i)
{
printf("\t%dv%d->",i,G->vertices[i].data);
p=G->vertices[i].firstarc;
while(p->nextarc)
{
printf("%d->",p->adjvex);
p=p->nextarc;
}
printf("%d\n",p->adjvex);
}
return OK;
}
int FirstAdjVex(ALGraph G,int v)
{//返回v的第一个邻接顶点
if(G.vertices[v].firstarc)
return G.vertices[v].firstarc->adjvex;
else
return -1;
}
int NextAdjVex(ALGraph G,int v,int w)
{//返回v中相对于W的下一个邻接顶点
int flag=0;
ArcNode *p;
p=G.vertices[v].firstarc;
while(p)
{
if(p->adjvex==w)
{
flag=1;
break;
}
p=p->nextarc;
}
if(flag&&p->nextarc)
return p->nextarc->adjvex;
else
return -1;
}
int Visited[MAX_VERTEX_NUM];
void DFS(ALGraph G,int v)
{//深度优先遍历
int w;
Visited[v]=TRUE;
printf("v%d ",G.vertices[v].data);
    for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))
        if(!Visited[w])
               DFS(G,w);
}
void DFSTraverse(ALGraph G)
{
int v;
for(v=0;v<G.vexnum;++v)
Visited[v]=FALSE;
for(v=0;v<G.vexnum;++v)
if(!Visited[v])
DFS(G,v);
}
void BFSTraverse(ALGraph G)
{//广度优先遍历
 int v,v1,w;
 Queue q;        //定义一个队列
 for(v=0;v<G.vexnum;++v)
   Visited[v]=FALSE;
 InitQueue(&q);   //初始化队列
 for(v=0;v<G.vexnum;++v)
   if(!Visited[v])
   {
   Visited[v]=TRUE;
    printf("v%d ",G.vertices[v].data);
   EnQueue(&q,v);  //第一个顶点入队
   while(!QueueEmpty(q))
    {
    DeQueue(&q,&v1); //第一个顶点出对
    for(w=FirstAdjVex(G,v1);w>=0;w=NextAdjVex(G,v1,w))
     if(!Visited[w])
     {
      Visited[w]=TRUE;
                 printf("v%d ",G.vertices[w].data);
      EnQueue(&q,w);
     }
    }
   }
}
int main()
{
ALGraph G;
CreateGraph(&G);
    printf("深度优先:\n");
    DFSTraverse(G);
    printf("\n广度优先:\n");
    BFSTraverse(G);
    printf("\n");
system("pause");
return 0;
}
    









加载中
0
平原君
平原君
Status CreateGraph(ALGraph *G)//以邻接表形式创建无向连通图G
{
    int m,n,i,j,k,v1,v2,flag=0;
    ArcNode *p1,*q1,*p,*q;
    printf("请输入图的顶点数目:");
    scanf("%d",&m);
    printf("请输入图的边的数目:");
    scanf("%d",&n);
    G->vexnum=m;
    G->arcnum=n;
    for(i=0;i<G->vexnum;++i)
    {
        G->vertices[i].data=i+1;
        G->vertices[i].firstarc=NULL;
    }
    printf("输出顶点信息是:\n");
    for(i=0;i<G->vexnum ;++i)
        printf("v%d\n",G->vertices[i].data);
    for(k=0;k<G->arcnum;++k)
    {
        printf("请输入第%d条弧的两个端点:",k+1);
        //我改的,获取两个数,怎么也要用个分隔符吧
        scanf("%d %d",&v1,&v2);
        i=LocateVex(G,v1);
        j=LocateVex(G,v2);


        if(i>=0&&j>=0)
        {
            ++flag;
            p=(ArcNode *)malloc(sizeof(ArcNode));
            p->adjvex=j;
            p->nextarc=NULL;
            if(!G->vertices[i].firstarc)
                G->vertices[i].firstarc=p;
            else
            {
                //我改的
                for(p1=G->vertices[i].firstarc;p1 != NULL && p1->nextarc == NULL;p1=p1->nextarc)
                {
                    p1->nextarc =p;
                    break;
                }
            }
            q=(ArcNode *)malloc(sizeof(ArcNode));
            q->adjvex=i;
            q->nextarc =NULL;
            if(!G->vertices[j].firstarc)
                G->vertices[j].firstarc=q;
            else
            {
                //我改的
                for(q1=G->vertices[j].firstarc;q1 != NULL && q1->nextarc == NULL;q1=q1->nextarc )
                {
                    q1->nextarc =q;
                    break;
                }
            }
        }
        else
        {
            printf("所输入的弧不符合规范!\n");
            k=flag;
        }
    }
    printf("邻接表是:\n");
    for(i=0;i<G->vexnum;++i)
    {
        printf("\t%dv%d->",i,G->vertices[i].data);
        p=G->vertices[i].firstarc;
        while(p->nextarc != NULL)
        {
            printf("%d->",p->adjvex);
            p=p->nextarc;
        }
        printf("%d\n",p->adjvex);
    }
    return OK;
}

我总共改了三处代码,你搜下“我改的”就知道了
优雅先生
优雅先生
回复 @谈七七 : 惭愧
Russellll
Russellll
回复 @jxqlovedn : thank you all the same~
优雅先生
优雅先生
回复 @谈七七 : 哈哈 比我快了好多步,我还在研究邻接图是咋回事呢,谁让我数据结构基础不扎实,人又笨,╮(╯▽╰)╭
Russellll
Russellll
回复 @平原君 : 来北京绝对请你~
平原君
平原君
回复 @谈七七 : 语言奖励不如来顿饭实在啊
下一页
0
平原君
平原君
你也描述描述出啥bug了撒
平原君
平原君
回复 @谈七七 : 你的错误在于添加弧的时候错了,代码是for(p1=G->vertices[i].firstarc;p1->nextarc;p1=p1->nextarc) p1->nextarc =p; 这个本来应该是加到链表结尾吧,但因为首节点的nextarx肯定是null,所以添加不上去的
Russellll
Russellll
可今天晚上就要上机检查了
平原君
平原君
回复 @谈七七 : 等我晚上回去给你跑跑看,表还是很麻烦的,上学时就是头大的问题
Russellll
Russellll
就是输出的邻接表不对
0
平原君
平原君
我把那部分代码修改了下,深度和广度就都可以出来了
Russellll
Russellll
怎么改呀?
0
中山野鬼
中山野鬼

图这种东西,没经验的,最好先用最简单的存储方式,把图的逻辑实现了,然后在处理存储方式的指针实现。上来就玩,反正我的水平,不可能没bug的。我最多比其他人debug更熟练点。

现在这类开发,我再碰上,通常的做法是先做数学模型,然后做宏,然后最简单测试,最后才把宏依次展开实现。

Russellll
Russellll
3q
返回顶部
顶部