C语言邻接表图物理删除顶点程序崩溃问题排查求助

问题描述 #

在C语言中实现邻接表形式的图的顶点物理删除（通过重新分配邻接表数组实现）时出现异常：删除顶点2时程序运行正常，但删除顶点4时直接崩溃，输出乱码地址。怀疑问题出在处理其他顶点邻接表的循环中，realloc功能确认正常。

图结构体定义 #

typedef struct edge{
    int value; // 目标顶点的编号
    struct edge * next; 
    // 该结构体表示一条边，而非顶点!!!
}edge;

typedef struct graph {
    int nv; // 顶点数量
    edge **adj; // 邻接表数组，每个元素是边链表的头指针
}graph;

原删除顶点函数代码 #

void deleteVertex(graph* G, int vertex) {

// vertex = 要删除的顶点编号
int i = 0, j = 0;
 
edge * currNode = G->adj[vertex];

// 清空待删除顶点自身的邻接链表
while (currNode != NULL) {
    edge* tmp = currNode;
    currNode = currNode->next;
    free(tmp);
}

// 移动邻接表数组元素，覆盖待删除顶点的位置
for(i = vertex; i < G->nv-1; i++) {
    printf("sono nel for i:%d i+1:%d\n", i, i+1);
    G->adj[i] = G->adj[i+1];
}

// 将原最后一个位置置空，更新顶点数量并重新分配内存
G->adj[G->nv-1] = NULL;
G->nv -= 1;
G->adj = (edge **)realloc(G->adj, G->nv * sizeof(edge));

// 移除其他顶点邻接表中指向被删除顶点的边
for(i = 0; i < G->nv; i++){
    
    edge* testa = G->adj[i];
    if(testa != NULL){
        // 头节点是目标顶点的情况
        if(testa->value == vertex){
            G->adj[i] = testa->next;
        }
        // 中间节点是目标顶点的情况
        else {
            edge * scorri = testa;
            while(scorri->next) {
                if(scorri->next->value == vertex){
                    testa = scorri->next;
                    scorri->next = scorri->next->next;
                    
                }
                else scorri = scorri->next;
            }
            
        }
        free(testa);
    }   
}
}

测试案例 #

原始图结构（顶点数为5） #

0 :NULL
1 :2-->3-->NULL
2 :3-->NULL
3 :4-->NULL
4 :1-->2-->NULL

删除顶点2后的正常输出 #

0 :NULL
1 :3-->NULL
2 :4-->NULL
3 :1-->NULL

删除顶点4时的崩溃输出 #

0 :NULL
1 :11168960-->11168896->....

问题分析与修复 #

1. realloc内存分配大小错误 #

原代码中realloc的参数是G->nv * sizeof(edge)，但G->adj是edge**类型（指向指针的指针），正确的内存大小应该是G->nv * sizeof(edge*)。使用sizeof(edge)会导致分配的内存不足，当删除顶点4（处于数组末尾附近）时，会触发内存越界访问，直接导致崩溃。

修复：

G->adj = realloc(G->adj, G->nv * sizeof(edge*));
// C语言中无需强制转换realloc的返回值，void*可自动转换为任意指针类型

2. 邻接表删除逻辑的内存错误 #

原代码在处理其他顶点的邻接表时存在多个问题：

• 无论是否找到要删除的节点，最后都会free(testa)，如果没找到目标节点，这会直接释放整个邻接链表，导致后续访问野指针。
• 处理中间节点时，找到目标节点后未移动scorri指针，会导致死循环；同时错误地将testa赋值为要删除的节点，后续free(testa)虽然释放了目标节点，但逻辑混乱。
• 未处理顶点编号更新：当删除顶点后，编号大于被删除顶点的顶点，其邻接表中的目标顶点编号需要减1（因为邻接表数组前移了一位），否则会出现指向不存在顶点的情况。

修复后的邻接表处理循环：

// 移除其他顶点邻接表中指向被删除顶点的边，并更新剩余顶点的编号
for(i = 0; i < G->nv; i++){
    edge** curr = &G->adj[i]; // 使用二级指针，方便处理头节点删除
    while(*curr != NULL){
        if((*curr)->value == vertex){
            // 删除当前指向被删除顶点的边
            edge* temp = *curr;
            *curr = (*curr)->next;
            free(temp);
        } else {
            // 若目标顶点编号大于被删除的顶点，编号减1（因为邻接表已前移）
            if((*curr)->value > vertex){
                (*curr)->value -= 1;
            }
            curr = &(*curr)->next; // 移动到下一个节点
        }
    }
}

3. 邻接表数组移动后的边界处理 #

原代码在移动数组元素后将G->adj[G->nv-1]置空，这一步在realloc前是多余的，因为realloc会调整数组大小，原最后一个元素会被丢弃，不过这一步不会导致崩溃，可保留或移除。

修复后的完整函数 #

void deleteVertex(graph* G, int vertex) {
    // 检查顶点编号合法性（可选，防止越界）
    if(vertex < 0 || vertex >= G->nv){
        return;
    }

    // 清空待删除顶点自身的邻接链表
    edge * currNode = G->adj[vertex];
    while (currNode != NULL) {
        edge* tmp = currNode;
        currNode = currNode->next;
        free(tmp);
    }

    // 移动邻接表数组元素，覆盖待删除顶点的位置
    for(int i = vertex; i < G->nv-1; i++) {
        G->adj[i] = G->adj[i+1];
    }

    // 更新顶点数量并重新分配内存
    G->nv -= 1;
    G->adj = realloc(G->adj, G->nv * sizeof(edge*));
    if(G->adj == NULL && G->nv > 0){
        // 内存分配失败处理（可选）
        perror("realloc failed");
        exit(EXIT_FAILURE);
    }

    // 移除其他顶点邻接表中指向被删除顶点的边，并更新剩余顶点的编号
    for(int i = 0; i < G->nv; i++){
        edge** curr = &G->adj[i];
        while(*curr != NULL){
            if((*curr)->value == vertex){
                edge* temp = *curr;
                *curr = (*curr)->next;
                free(temp);
            } else {
                if((*curr)->value > vertex){
                    (*curr)->value -= 1;
                }
                curr = &(*curr)->next;
            }
        }
    }
}

内容的提问来源于stack exchange，提问作者Luigi V.