C语言邻接矩阵转邻接列表输入读取异常无法输出问题咨询

现有代码的核心问题 #

• 邻接表数组内存分配错误：createAGraph函数中给adjLists分配内存时，仅申请了1个指针的空间，实际需要申请size个VertexNode*的空间，数组越界访问会直接导致程序崩溃。
• 输入读取逻辑错误：混合使用scanf和fgets时，scanf("%d", &size)执行后输入缓冲区会残留换行符，第一个fgets会读取到空行，导致第一行邻接矩阵数据丢失，后续下标匹配完全错乱。
• 输出顺序不匹配：addEdge使用头插法插入节点，最终邻接表的节点顺序是按列号从大到小排列，和预期的从小到大的输出顺序相反。
• 打印函数语法错误：printGraph中的newline未定义，需要替换为printf("\n")才能正常编译。

修复后的核心代码 #

修正后的创建图函数 #

Graph *createAGraph(int size)
{
    Graph *graph = (Graph *)malloc(sizeof(Graph));
    graph->numVertices = size;
    // 修正：分配size个指针的空间
    graph->adjLists = (VertexNode **)malloc(size * sizeof(VertexNode *));

    for(int i = 0; i < size; i++)
        graph->adjLists[i] = NULL;
    return graph;
}

修正后的边插入函数（改为尾插法匹配输出顺序） #

void addEdge(Graph *graph, int s, int d)
{
    VertexNode *newNode = createVertex(d);
    if (graph->adjLists[s] == NULL) {
        graph->adjLists[s] = newNode;
        return;
    }
    VertexNode *temp = graph->adjLists[s];
    while (temp->Next != NULL) {
        temp = temp->Next;
    }
    temp->Next = newNode;
}

修正后的打印函数 #

void printGraph(Graph *graph)
{
    for(int i = 0; i < graph->numVertices; i++)
    {
        VertexNode *temp = graph->adjLists[i];
        printf("%d", i+1);
        while(temp)
        {
            printf(" -> %d", temp->vertex);
            temp = temp->Next;
        }
        printf("\n");
    }
}

更优的输入读取方案 #

方案1：全用scanf读取整数（推荐） #

邻接矩阵的输入都是整数，scanf读取%d时会自动跳过所有空白字符（包括空格、换行、制表符），不需要手动按行拆分，代码更简洁，出错概率低。只需要循环读取size*size个整数即可，完全不用关心每行有多少个数字、有没有多余换行。
示例代码片段：

int main()
{
    int size;
    scanf("%d", &size);
    Graph *graph = createAGraph(size);

    for(int i = 0; i < size; i++) {
        for(int j = 0; j < size; j++) {
            int temp;
            scanf("%d", &temp);
            if(temp == 1) {
                addEdge(graph, i, j);
            }
        }
    }
    printGraph(graph);
    return 0;
}

方案2：按行读取时先清空缓冲区 #

如果业务要求必须按行校验输入合法性，在scanf读取完顶点数后，加一行代码清空缓冲区残留的换行即可：

scanf("%d", &size);
// 清空输入缓冲区残留的换行
while(getchar() != '\n');

之后再用fgets逐行读取即可正常处理。

对应输入示例的输出 #

1 -> 3
2 -> 1 -> 4
3 -> 1 -> 2 -> 4
4 -> 2

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