从文件读取无向图邻接表函数更正

Question

从文件读取无向图邻接表函数，代码如下。在主函数中输出顶点数8后，进入循环只能输出一个1，然后就没有了。请问该如何修改？

//定义邻接表
typedef struct node{
    int adjvex;//顶点编号
    struct node *next;//指向下一个结点
}edgenode;//
typedef struct vnode{
    int vertex;//顶点
    edgenode *firstedge;//指向第一个表结点
}vertexnode,AdjList[MAX];//头结点
typedef struct{
    AdjList vertices; //顶点数组
    int vexnum;//顶点数
    int arcnum;//弧的条数
}Graph;

int CreatGraph(Graph &G)//从文件读取并输出邻接表
{
    FILE *fp;edgenode *p;
    if((fp=fopen("graph.txt","r"))==NULL)
    {
      printf("文件打开失败\n");
      return 0;
    }

    fscanf(fp,"%d",&G.vexnum);
    G.arcnum=G.vexnum+1;
    printf("顶点个数%d\n",G.vexnum);
    int i,a;
    for(i=1;i<=G.arcnum;i++)
    {
        p=(edgenode*)malloc(sizeof(edgenode));
        
        if(fscanf(fp,"%d",&a)!=0)
        {
         
          p=(edgenode*)malloc(sizeof(edgenode));
          p->adjvex=a;
          p->next=G.vertices[i].firstedge;
          G.vertices[i].firstedge=p;
      
        }
    }
   
    fclose(fp);
return 1;
}

文件内容如下
8
1 2 3 0
2 1 4 5 0
3 1 6 7 0
4 2 8 0
5 2 8 0
6 3 7 0
7 3 6 0
8 4 5 0

Answer 1

• 在读取文件时，你的循环条件是 i <= G.arcnum，但这里的 G.arcnum 实际上并没有正确初始化。在你的文件格式中，每一行代表一个顶点和它的所有邻接顶点，所以你应该根据顶点数量来循环。

• 你的代码在读取每个顶点的邻接顶点时，没有正确处理文件中的 0，它应该是邻接顶点列表的结束标志。

• 你的代码在分配内存时出现了冗余。你在循环开始时就分配了内存，但在读取到一个顶点后又重新分配了内存，这导致了内存泄漏。

根据这些点，下面是修改后的代码示例：

##include <stdio.h>
#include <stdlib.h>

#define MAX 100

// 定义邻接表节点
typedef struct node {
    int adjvex; // 顶点编号
    struct node *next; // 指向下一个结点
} edgenode;

// 定义邻接表头结点
typedef struct vnode {
    int vertex; // 顶点
    edgenode *firstedge; // 指向第一个表结点
} vertexnode, AdjList[MAX];

// 定义图结构
typedef struct {
    AdjList vertices; // 顶点数组
    int vexnum; // 顶点数
    int arcnum; // 弧的条数
} Graph;

// 从文件读取并创建邻接表
int CreateGraph(Graph &G) {
    FILE *fp;
    edgenode *p;

    if ((fp = fopen("graph.txt", "r")) == NULL) {
        printf("文件打开失败\n");
        return 0;
    }

    fscanf(fp, "%d", &G.vexnum);
    printf("顶点个数: %d\n", G.vexnum);

    for (int i = 0; i < G.vexnum; i++) {
        G.vertices[i].vertex = i + 1;
        G.vertices[i].firstedge = NULL;

        int a;
        while (1) {
            fscanf(fp, "%d", &a);
            if (a == 0) break;

            // 只有当a不等于当前顶点编号时，才将其添加到邻接表中
            if (a != i + 1) {
                p = (edgenode *)malloc(sizeof(edgenode));
                p->adjvex = a;
                p->next = G.vertices[i].firstedge;
                G.vertices[i].firstedge = p;
            }
        }
    }

    fclose(fp);
    return 1;
}

// 打印图的邻接表
void PrintGraph(Graph &G) {
    for (int i = 0; i < G.vexnum; i++) {
        printf("顶点 %d 的邻接顶点: ", i + 1);
        edgenode *p = G.vertices[i].firstedge;
        while (p != NULL) {
            printf("%d ", p->adjvex);
            p = p->next;
        }
        printf("\n");
    }
}

int main() {
    Graph G;
    if (CreateGraph(G)) {
        PrintGraph(G);
    }
    return 0;
}