如何修正C语言链表实现的图打印多余行问题

问题背景 #

用链表实现图结构，读取的文件格式为：第一列是vertex1，第二列是weight，第三列是vertex1连接的vertex2。编写的C代码能正常读取文件并打印图，但输出时出现多余的tTt->行，其余输出正常。

文件内容 #

aAa     5     bBb
bBb     3     cCc
cCc     7     dDd
dDd     2     eEe
eEe     8     fFf
fFf     4     gGg
gGg     6     hHh
hHh     1     iIi
iIi     9     jJj
jJj     5     kKk
kKk     3     lLl
lLl     7     mMm
mMm     4     nNn
nNn     6     oOo
oOo     2     pPp
pPp     8     qQq
qQq     1     rRr
rRr     9     sSs
sSs     5     tTt

实现代码 #

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

typedef struct edge_s edge_t;
typedef struct vertex_s vertex_t;

struct edge_s {
    struct edge_s *next;
    int weight;
    vertex_t *vertex;
};

struct vertex_s {
    struct vertex_s *next;
    char *name;
    edge_t *edge;
    int traversed;
};

typedef struct graph_s {
    vertex_t *head;
    int n;
} graph_t;

vertex_t *find_vertex(graph_t *graph, const char name[20]);
void vertex_add(graph_t *graph, const char *name);
void edge_add(graph_t *graph, vertex_t *vertex1, vertex_t *vertex2, int weight);
graph_t *graph_init(void);
graph_t *fileread(const char *name);
void graph_write(graph_t *graph);

graph_t *graph_init() {
    graph_t *graph = malloc(sizeof(graph_t));
    if (graph == NULL)
        exit(EXIT_FAILURE);
    graph->head = NULL;
    graph->n = 0;

    return graph;
}

void edge_add(graph_t *graph, vertex_t *vertex1, vertex_t *vertex2, int weight) {
    edge_t *edge = malloc(sizeof(edge_t));
    if (edge == NULL)
        exit(EXIT_FAILURE);
    edge->weight = weight;
    edge->vertex = vertex2;
    edge->next = vertex1->edge;
    vertex1->edge = edge;
}

void vertex_add(graph_t *graph, const char *name) {
    vertex_t *vertex = malloc(sizeof(vertex_t));
    if (vertex == NULL)
        exit(EXIT_FAILURE);
    vertex->edge = NULL;
    vertex->traversed = 0;
    vertex->name = strdup(name);
    vertex->next = graph->head;
    graph->head = vertex;
}

vertex_t *find_vertex(graph_t *graph, const char name[20]) {
    vertex_t *v = graph->head;
    while (v != NULL) {
        if (strcmp(v->name, name) == 0)
            return v;
        v = v->next;
    }
    return NULL;
}

graph_t *fileread(const char *name) {
    FILE *fp = fopen(name, "r");
    if (fp == NULL)
        exit(EXIT_FAILURE);

    graph_t *graph = graph_init();
    int weight;
    char name1[20], name2[20];
    vertex_t *vertex1, *vertex2;

    while (fscanf(fp, "%s %d %s", name1, &weight, name2) != EOF) {
        vertex1 = find_vertex(graph, name1);
        if (vertex1 == NULL) {
            vertex_add(graph, name1);
            vertex1 = graph->head; 
        }

        vertex2 = find_vertex(graph, name2);
        if (vertex2 == NULL) {
            vertex_add(graph, name2);
            vertex2 = graph->head; 
        }

        edge_add(graph, vertex1, vertex2, weight);
    }


    fclose(fp);
    return graph;
}

void graph_write(graph_t *graph) {
    vertex_t *vertex = graph->head;
    edge_t *edge;

    while (vertex != NULL) {
        printf("%s->", vertex->name);
        edge = vertex->edge;
        while (edge != NULL) {
            printf(" %d -> %s", edge->weight, edge->vertex->name);
            edge = edge->next;
        }
        printf("\n");
        vertex = vertex->next;
    }
}

int main() {
    graph_t *graph = fileread("file");
    graph_write(graph);
    return 0;
}

当前输出 #

tTt->
sSs-> 5 -> tTt
rRr-> 9 -> sSs
qQq-> 1 -> rRr
pPp-> 8 -> qQq
oOo-> 2 -> pPp
nNn-> 6 -> oOo
mMm-> 4 -> nNn
lLl-> 7 -> mMm
kKk-> 3 -> lLl
jJj-> 5 -> kKk
iIi-> 9 -> jJj
hHh-> 1 -> iIi
gGg-> 6 -> hHh
fFf-> 4 -> gGg
eEe-> 8 -> fFf
dDd-> 2 -> eEe
cCc-> 7 -> dDd
bBb-> 3 -> cCc
aAa-> 5 -> bBb

问题原因 #

tTt是文件最后一行的vertex2，它被正常添加到图中，但没有任何出边（文件中没有以tTt作为vertex1的行）。当前的graph_write函数会无条件先打印顶点->，再遍历输出边信息，没有边时就直接换行，导致出现了多余的tTt->行。

修复方案 #

根据需求，有两种常见的修复方式：

方式一：只打印有出边的顶点 #

修改graph_write函数，在打印前判断顶点是否有出边，只有存在出边时才打印该行：

void graph_write(graph_t *graph) {
    vertex_t *vertex = graph->head;
    edge_t *edge;

    while (vertex != NULL) {
        edge = vertex->edge;
        // 仅当顶点有出边时才打印
        if (edge != NULL) {
            printf("%s->", vertex->name);
            while (edge != NULL) {
                printf(" %d -> %s", edge->weight, edge->vertex->name);
                edge = edge->next;
            }
            printf("\n");
        }
        vertex = vertex->next;
    }
}

方式二：打印所有顶点，但无出边时不显示箭头 #

如果需要保留所有顶点的输出，只是去掉无出边顶点的箭头，修改打印逻辑：

void graph_write(graph_t *graph) {
    vertex_t *vertex = graph->head;
    edge_t *edge;

    while (vertex != NULL) {
        edge = vertex->edge;
        if (edge != NULL) {
            printf("%s->", vertex->name);
            while (edge != NULL) {
                printf(" %d -> %s", edge->weight, edge->vertex->name);
                edge = edge->next;
            }
        } else {
            // 无出边时仅打印顶点名称
            printf("%s", vertex->name);
        }
        printf("\n");
        vertex = vertex->next;
    }
}

修复后效果 #

使用方式一修复后，输出中将不再出现tTt->行；使用方式二修复后，该行会变成tTt，不再显示多余的箭头。

内容的提问来源于stack exchange，提问作者Severjan Lici