为何这段C++图结构代码会触发非法访问错误异常？

核心问题分析 #

1. 顶点存在性检查逻辑完全错误（add_edge_no_direction函数） #

原代码里的这段检查逻辑完全颠倒且逻辑矛盾：

// check if edge present
for (int i = 0; i < size; i++) {
    if (array[i].data != source || array[i].data != destination) {
        return false;
    }
}

一个数不可能同时等于两个不同的source和destination，因此这个条件永远为真，第一次循环就会直接返回false，导致边根本无法添加，后续操作也会因为边未正确创建出现问题。正确逻辑应该是确认source和destination两个顶点都存在于图中。

2. display函数的空指针访问 #

原display函数有两处致命的空指针风险：

• 当array[i].next为nullptr时（比如i>=5，因为只添加了5个顶点，而图的size是200），直接访问current->data会触发崩溃。
• 循环中current = current->next;后，未判断current是否为nullptr就直接访问current->data，遍历到链表最后一个节点时，current会变成nullptr，此时访问会抛出异常。

3. addvertex函数未正确初始化顶点头节点 #

原addvertex只把新顶点放到array[j].next，但array[j].data一直是构造函数初始化的0，没有设置为当前添加的顶点值，导致后续找顶点时无法通过array[i].data匹配到对应顶点，进而add_edge函数无法找到正确的顶点链表。

4. add_edge_no_direction函数的遍历与边添加逻辑错误 #

• 遍历整个size（200次）完全没必要，只需遍历已添加的顶点（前j个）。
• 找到对应顶点后，边的添加逻辑混乱，且未处理顶点不存在的情况，还可能出现空指针访问。

修复后的完整代码 #

#include <iostream>
using namespace std;

struct node {
    int data;
    int weight;
    node* next;
    node() : data(0), weight(0), next(nullptr) {}
    node(int data, int weight) : data(data), weight(weight), next(nullptr) {}
};

class Graph {
private:
    node* array;
    int size;
    int vertexCount; // 改用更清晰的变量名，记录已添加的顶点数

public:
    Graph(int size) : size(size), vertexCount(0) {
        array = new node[size];
        // 利用node的默认构造函数完成初始化
    }

    // 辅助函数：查找顶点所在的数组索引，未找到返回-1
    int findVertex(int value) {
        for (int i = 0; i < vertexCount; i++) {
            if (array[i].data == value) {
                return i;
            }
        }
        return -1;
    }

    bool addvertex(int value) {
        // 先检查顶点是否已存在
        if (findVertex(value) != -1) {
            return false;
        }
        // 直接初始化头节点的data为顶点值
        array[vertexCount].data = value;
        vertexCount++;
        return true;
    }

    bool add_edge_no_direction(int source, int destination, int weight) {
        int srcIdx = findVertex(source);
        int destIdx = findVertex(destination);
        // 检查两个顶点是否都存在
        if (srcIdx == -1 || destIdx == -1) {
            return false;
        }

        // 给source的链表添加destination节点
        node* newNodeDest = new node(destination, weight);
        node* current = &array[srcIdx];
        while (current->next != nullptr) {
            current = current->next;
        }
        current->next = newNodeDest;

        // 给destination的链表添加source节点（无向边双向存储）
        node* newNodeSrc = new node(source, weight);
        current = &array[destIdx];
        while (current->next != nullptr) {
            current = current->next;
        }
        current->next = newNodeSrc;

        return true;
    }

    void display() {
        for (int i = 0; i < vertexCount; i++) {
            cout << array[i].data;
            node* current = array[i].next;
            while (current != nullptr) {
                cout << " -> (" << current->data << ", 权重:" << current->weight << ")";
                current = current->next;
            }
            cout << endl;
        }
    }

    // 析构函数：释放内存，避免泄漏
    ~Graph() {
        for (int i = 0; i < vertexCount; i++) {
            node* current = array[i].next;
            while (current != nullptr) {
                node* temp = current;
                current = current->next;
                delete temp;
            }
        }
        delete[] array;
    }
};

int main() {
    Graph g1(200);
   
    g1.addvertex(1);
    g1.addvertex(2);
    g1.addvertex(3);
    g1.addvertex(4);
    g1.addvertex(5);
    g1.add_edge_no_direction(1, 2, 100);
    g1.add_edge_no_direction(1, 3, 150);
    g1.add_edge_no_direction(1, 4, 200);
    g1.add_edge_no_direction(1, 5, 250);
    g1.display();
    return 0;
}

修复说明 #

1. 修正顶点存在性检查：新增findVertex辅助函数快速定位顶点索引，add_edge时通过该函数确认两个顶点都存在。
2. 修复display函数：只遍历已添加的顶点（vertexCount次），遍历链表时先判断current是否为nullptr再访问成员，同时输出边的权重信息，展示更清晰。
3. 修正addvertex逻辑：直接将顶点值赋值给数组头节点的data，让头节点代表顶点本身，链表后续节点代表邻接顶点。
4. 优化add_edge逻辑：找到对应顶点索引后，分别在两个顶点的链表末尾添加邻接节点，实现无向边的双向存储。
5. 添加析构函数：释放链表节点和数组内存，避免内存泄漏。

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