C语言无向图邻接表运行错误

Question

想建立的图如下

代码如下

#include <stdio.h>
#include <stdlib.h>
#define MAX 20
typedef struct node{
    int adjvex;//顶点编号
    struct node *next;//指向下一个结点
}edgenode;//
typedef struct vnode{
    int vertex;//顶点V_{i}
    edgenode *firstedge;//指向第一个邻接的结点
}vertexnode;//头结点
void Creatlist(vertexnode g[],int n,int e)//n为顶点数,e为边数
{
  edgenode *p;int i;//数组从1开始使用，0闲置
  for(i=1;i<=n;i++)//头结点结构体数组初始化
  {
    g[i].vertex=i;
    g[i].firstedge=NULL;
  }
  printf("已建立顶点如下\n");
  for(i=1;i<=n;i++)
      printf("V%d\n",i);
  int j,k;
  for(k=1;k<=e;k++)
  {
      printf("输入要建立的边:i,j\n");
      scanf("%d,%d",&i,&j);
      //在结点i的单链表插入结点j
      p=(edgenode*)malloc(sizeof(edgenode));
      p->adjvex=j;
      p->next=g[j].firstedge;
      g[i].firstedge=p;
      //在结点j的单链表插入结点i
      p=(edgenode*)malloc(sizeof(edgenode));
      p->adjvex=i;
      p->next=g[i].firstedge;
      g[j].firstedge=p;
  }
}
void PrintfList(vertexnode g[],int n)//顶点数n,边数e
{
    edgenode *p;
    int i;
    for(i=1;i<=n;i++)
    {
        printf("V%d->",i);
        p=g[i].firstedge;//指向第一个表结点
        while(p!=NULL)
        {
          printf("%d->",p->adjvex);
          p=p->next;
        }
        printf("NULL\n");
    }
}
int main(void)
{
    vertexnode g[MAX];
    int n,e;
    printf("输入顶点数\n");
    scanf("%d",&n);
    printf("输入边数\n");
    scanf("%d",&e);
    Creatlist(g,n,e);
    PrintfList(g,n);
    return 0;
}

运行结果如下

感觉是打印函数哪里出错了，还是p指针没有处理对？所以是哪里出错了呢，如何解决？

Answer 1

引自强大而免费的微信小程序：皆我百晓生。

你的代码在建立无向图的邻接表时存在一些问题。在插入边的过程中，你没有正确地更新每个顶点的邻接表。你需要将第15行的g[i].firstedge=p;和第20行的g[j].firstedge=p;修改为：

g[i].firstedge=p;
p->next=g[j].firstedge;
g[j].firstedge=p;

这样，你就可以正确地构建无向图的邻接表了。以下是修改后的完整代码：

#include <stdio.h>
#include <stdlib.h>
#define MAX 20
typedef struct node{
    int adjvex;//顶点编号
    struct node *next;//指向下一个结点
}edgenode;//
typedef struct vnode{
    int vertex;//顶点V_{i}
    edgenode *firstedge;//指向第一个邻接的结点
}vertexnode;//头结点
void Creatlist(vertexnode g[],int n,int e)//n为顶点数，e为边数
{
  edgenode *p;int i;//数组从1开始使用，0闲置
  for(i=1;i<=n;i++)//头结点结构体数组初始化
  {
    g[i].vertex=i;
    g[i].firstedge=NULL;
  }
  printf("已建立顶点如下
");
  for(i=1;i<=n;i++)
      printf("V%d
",i);
  int j,k;
  for(k=1;k<=e;k++)
  {
      printf("输入要建立的边：i,j
");
      scanf("%d,%d",&i,&j);
      //在结点i的单链表插入结点j
      p=(edgenode*)malloc(sizeof(edgenode));
      p->adjvex=j;
      p->next=g[j].firstedge;
      g[i].firstedge=p;
      //在结点j的单链表插入结点i
      p=(edgenode*)malloc(sizeof(edgenode));
      p->adjvex=i;
      p->next=g[j].firstedge;
      g[j].firstedge=p;
  }
}
void PrintfList(vertexnode g[],int n)//顶点数n,边数e
{
    edgenode *p;
    int i;
    for(i=1;i<=n;i++)
    {
        printf("V%d->",i);
        p=g[i].firstedge;//指向第一个表结点
        while(p!=NULL)
        {
          printf("%d->",p->adjvex);
          p=p->next;
        }
        printf("NULL
");
    }
}
int main(void)
{
    vertexnode g[MAX];
    int n,e;
    printf("输入顶点数
");
    scanf("%d",&n);
    printf("输入边数
");
    scanf("%d",&e);
    Creatlist(g,n,e);
    PrintfList(g,n);
    return 0;
}