C语言带权双向图输入异常问题求助

你编写的带权无向图C程序编译正常，但存在三个核心问题：

• 部分节点无法正常插入，邻接链表丢失已有节点
• 输入错误检测不完整（负数顶点、非法输入未处理）
• 同一顶点对的无向边会被重复添加，无法正确检测重复

以下是问题根源分析及修复方案：

1. 核心问题：isPresent函数破坏邻接链表结构 #

你的isPresent函数直接修改了图的邻接链表头指针，导致每次调用后，原链表的头节点丢失，后续无法访问已插入的节点，也无法正确检测重复边：

// 错误的实现
int isPresent(graph_t* g1, int source, int key)
{
    graph_t* gTmp = g1;
    while(gTmp->adjList[source] != NULL)
    {
      if(gTmp->adjList[source]->key == key)
      {
          printf("Key in Common: %d\n", key);
          return 1;
      }
        gTmp->adjList[source] = gTmp->adjList[source]->next; // 修改了原链表头
    }
    return 0;
}

修复方法：使用临时指针遍历链表，不修改原链表的头指针：

int isPresent(graph_t* g1, int source, int key)
{
    node_t* curr = g1->adjList[source]; // 用临时指针遍历
    while(curr != NULL)
    {
      if(curr->key == key)
      {
          printf("Found duplicate edge %d-%d\n", source, key);
          return 1;
      }
        curr = curr->next;
    }
    return 0;
}

2. 输入验证逻辑不完整 #

当前输入验证仅检查顶点索引小于nV，未覆盖以下场景：

• 顶点索引为负数（如输入-1作为source）
• 用户重新输入后未再次验证合法性
• scanf输入失败（如输入字母）时，输入缓冲区残留垃圾数据导致死循环

修复方法：完善输入验证逻辑，添加负数检查、重复验证，处理非法输入：
修改main函数中的输入循环部分：

for(int i = 0; i < nV; i++)
{
    int source = -1, key = -1, weight = 0;
    printf("\nInsert edge %d: enter Source, Key and Weight: ", i+1);
    
    // 处理输入格式错误
    while(scanf("%d %d %d", &source, &key, &weight) != 3) {
        while(getchar() != '\n'); // 清空输入缓冲区垃圾
        printf("Invalid input, please enter three integers: ");
    }

    // 验证source合法性（非负+不越界）
    while(source < 0 || source >= nV){
        printf("Source Out of Bounds (0-%d), retry: ", nV-1);
        while(scanf("%d", &source) != 1) {
            while(getchar() != '\n');
            printf("Invalid input, enter a valid source: ");
        }
    }

    // 验证key合法性
    while(key < 0 || key >= nV){
        printf("Key Out of Bounds (0-%d), retry: ", nV-1);
        while(scanf("%d", &key) != 1) {
            while(getchar() != '\n');
            printf("Invalid input, enter a valid key: ");
        }
    }

    // 检测重复边，重新输入后再次验证合法性
    while(isPresent(graph, source, key) == 1)
    {
        printf("Edge already exists, enter new source and key: ");
        while(scanf("%d %d", &source, &key) != 2) {
            while(getchar() != '\n');
            printf("Invalid input, enter two integers: ");
        }
        // 重新验证新输入的source和key
        while(source < 0 || source >= nV){
            printf("Source Out of Bounds (0-%d), retry: ", nV-1);
            while(scanf("%d", &source) != 1) {
                while(getchar() != '\n');
                printf("Invalid input, enter a valid source: ");
            }
        }
        while(key < 0 || key >= nV){
            printf("Key Out of Bounds (0-%d), retry: ", nV-1);
            while(scanf("%d", &key) != 1) {
                while(getchar() != '\n');
                printf("Invalid input, enter a valid key: ");
            }
        }
    }

    addEdge(graph, source, key, weight);
    printf("\nCurrent graph state:\n");
    printGraph(graph);
}

3. 补充：无向边自环处理 #

原addEdge函数在添加自环（source=key）时会重复添加两条相同的边，需添加判断避免：

void addEdge(graph_t* graph, int src, int key, int w) {
    // Add edge from src to key
    node_t* newN = newNode(key);
    newN->weight = w;
    newN->next = graph->adjList[src];
    graph->adjList[src] = newN;

    // Add edge from key to src (仅当不是自环时添加)
    if(src != key) {
        node_t* newN2 = newNode(src);
        newN2->weight = w;
        newN2->next = graph->adjList[key];
        graph->adjList[key] = newN2;
    }
}

修复后的完整代码 #

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

typedef struct node {
    int key;
    int weight;
    struct node* next;
} node_t;

typedef struct graph {
    int V;
    node_t** adjList;
} graph_t;

node_t* newNode(int dest);
graph_t* createGraph(int V);
void addEdge(graph_t* graph, int src, int key, int w);
void printGraph(graph_t* graph);
int isPresent(graph_t* g, int source, int key);

int main() {
    int nV = 0;
    printf("Insert number of vertices (nV): ");
    while(scanf("%d", &nV) != 1 || nV <= 0) {
        while(getchar() != '\n');
        printf("Invalid input, enter a positive integer: ");
    }

    graph_t* graph = createGraph(nV);

    for(int i = 0; i < nV; i++)
    {
        int source = -1, key = -1, weight = 0;
        printf("\nInsert edge %d: enter Source, Key and Weight: ", i+1);
        
        while(scanf("%d %d %d", &source, &key, &weight) != 3) {
            while(getchar() != '\n');
            printf("Invalid input, please enter three integers: ");
        }

        while(source < 0 || source >= nV){
            printf("Source Out of Bounds (0-%d), retry: ", nV-1);
            while(scanf("%d", &source) != 1) {
                while(getchar() != '\n');
                printf("Invalid input, enter a valid source: ");
            }
        }

        while(key < 0 || key >= nV){
            printf("Key Out of Bounds (0-%d), retry: ", nV-1);
            while(scanf("%d", &key) != 1) {
                while(getchar() != '\n');
                printf("Invalid input, enter a valid key: ");
            }
        }

        while(isPresent(graph, source, key) == 1)
        {
            printf("Edge already exists, enter new source and key: ");
            while(scanf("%d %d", &source, &key) != 2) {
                while(getchar() != '\n');
                printf("Invalid input, enter two integers: ");
            }
            while(source < 0 || source >= nV){
                printf("Source Out of Bounds (0-%d), retry: ", nV-1);
                while(scanf("%d", &source) != 1) {
                    while(getchar() != '\n');
                    printf("Invalid input, enter a valid source: ");
                }
            }
            while(key < 0 || key >= nV){
                printf("Key Out of Bounds (0-%d), retry: ", nV-1);
                while(scanf("%d", &key) != 1) {
                    while(getchar() != '\n');
                    printf("Invalid input, enter a valid key: ");
                }
            }
        }

        addEdge(graph, source, key, weight);
        printf("\nCurrent graph state:\n");
        printGraph(graph);
    }
    printf("\n=== Final Graph ===\n");
    printGraph(graph);
    return 0;
}

node_t* newNode(int dest) {
    node_t* newNode = (node_t*) malloc(sizeof(node_t));
    newNode->key = dest;
    newNode->weight = 0;
    newNode->next = NULL;
    return newNode;
}

graph_t* createGraph(int V) {
    graph_t* graph = (graph_t*) malloc(sizeof(graph_t));
    graph->V = V;
    graph->adjList = (node_t**) malloc(V * sizeof(node_t*));
    int i;
    for (i = 0; i < V; i++) {
        graph->adjList[i] = NULL;
    }
    return graph;
}

void addEdge(graph_t* graph, int src, int key, int w) {
    node_t* newN = newNode(key);
    newN->weight = w;
    newN->next = graph->adjList[src];
    graph->adjList[src] = newN;

    if(src != key) {
        node_t* newN2 = newNode(src);
        newN2->weight = w;
        newN2->next = graph->adjList[key];
        graph->adjList[key] = newN2;
    }
}

int isPresent(graph_t* g1, int source, int key)
{
    node_t* curr = g1->adjList[source];
    while(curr != NULL)
    {
        if(curr->key == key)
        {
            printf("Found duplicate edge %d-%d\n", source, key);
            return 1;
        }
        curr = curr->next;
    }
    return 0;
}

void printGraph(graph_t* graph) {
    int i;
    for (i = 0; i < graph->V; i++) {
        node_t* currNode = graph->adjList[i];
        printf("Vertex %d: ", i);
        if(currNode == NULL) {
            printf("No adjacent vertices\n");
            continue;
        }
        while (currNode != NULL) {
            printf("%d(W:%d) ", currNode->key, currNode->weight);
            currNode = currNode->next;
        }
        printf("\n");
    }
}

修复后效果 #

• 邻接链表不再丢失节点，所有插入的边能正确显示
• 可检测重复无向边并阻止添加
• 输入验证覆盖负数、越界、非法输入场景
• 自环不会被重复添加

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