c++ - 程序在释放动态分配的内存时崩溃

Question

我在这里使用邻接表表示一个图。

代码如下:

// A program to check the reachability between two nodes within a specified number of steps using an adjacency list
/***************************************************************************/

#include <iostream>
#include <fstream>

using namespace std;

struct node {
    int value;
    node* next;

    // Constructors:
    node() {
        value = 0;
        next = 0;
    }
    node(int x) {
        value = x;
        next = 0;
    }
};


node* al; // Adjacency list
int n; // Number of nodes
int node1, node2, k; // For reading input from the console
int counter;

bool checkReachability(int, int, int);
void freeMemory();

int main() {

    ifstream in;
    in.open("Input.txt");
    if(in) {
        in >> n;
        al = new node[n];
        for (int i = 0; i < n; i++) {
            al[i].value = i+1;
        }

        int a, b;
        while(in >> a >> b) {
            node* temp = &al[a-1];
            while(temp->next != 0) {
                temp = temp->next;
            }
            temp->next = new node(b);    
        }

        cout << "\n\nThe adjacency list representation of the graph is as follows: \n";
        cout << "________________________________\n\n";
        for (int i = 0; i < n; i++) {
            cout << al[i].value;
            node* temp = al[i].next;
            while(temp != 0) {
                cout << "->" << temp->value;
                temp = temp->next;
            }
            cout << endl;
        }
        cout << "________________________________\n";
        in.close();
        char c;
        do {
            cout << "\nPlease enter the input (node1, node2, k): \n";
            cin >> node1 >> node2 >> k;
            counter = 0;
            if (checkReachability(node1 - 1, node2, k)) {
                cout << "\nReachable within " << k << " steps";
                if (counter < k) {
                    cout << " (actually " << counter << ")";
                }
                cout << endl << endl;
            }
            else {
                cout << "\nNot reachable within " << k << " steps  \n";
            }
            cout << "\nDo you want to continue? Y/N \n\n";
            cin >> c;
        } while (c == 'Y' || c == 'y');
        freeMemory();
    } else {
        cout << "\nCouldn't find the input file\n\n";
    }
    return 0;
}

bool checkReachability(int n1, int n2, int k) {
    if ((n1 + 1) == n2) return true;
    counter++;
    if (counter <= k) {
        node* temp = &(al[n1]);
        while (temp != 0) {
            if (temp->value == n2) return true;
            temp = temp->next;
        }
        temp = al[n1].next; 
        while (temp != 0) {
            if (checkReachability(((temp->value)-1),n2,k)) return true;
            counter--;
            temp = temp->next;
        }   
    }
    return false;
}

void freeMemory() {
    cout << "\nFreeing memory...\n";
    // To free the dynamically allocated memory on the heap
    for (int i = 0; i < n; i++) {
        node* temp = &al[i];
        while(temp != 0) {
            node* temp2 = temp;
            temp = temp->next;
            delete temp2;
        }
    }
    //delete [] al;
    cout << "\nMemory freed.\n";
}

程序运行良好。只有当我选择退出它时，它会调用它崩溃的 freeMemory 函数。请帮助我找出问题所在。

输入.txt文件:

5
1 2
2 5
3 4
1 3

输出:

The adjacency list represent
____________________________

1->2->3
2->5
3->4
4
5
____________________________

Please enter the input (node
1 2 1

Reachable within 1 steps


Do you want to continue? Y/N

y

Please enter the input (node
2 4 4

Not reachable within 4 steps

Do you want to continue? Y/N

N

Freeing memory...

然后，它崩溃了。

Answer 1

这是错误的:

void freeMemory() {
    cout << "\nFreeing memory...\n";
    // To free the dynamically allocated memory on the heap
    for (int i = 0; i < n; i++) {
        node* temp = &al[i]; // HERE
        while(temp != 0) {
            node* temp2 = temp;
            temp = temp->next;
            delete temp2;
        }
    }
    delete [] al;
    cout << "\nMemory freed.\n";
}

初始 vector a1是通过new node[n]分配的。这意味着所有插槽 a1[0...n-1] 中的初始条目都是 vector 分配的一部分；不属于此后与每个节点相关联的链接邻接序列的一部分。我相信你需要这样做:

void freeMemory() {
    cout << "\nFreeing memory...\n";
    // To free the dynamically allocated memory on the heap
    for (int i = 0; i < n; i++) {
        node* temp = al[i].next; // start with next pointer
        while(temp != 0) {
            node* temp2 = temp;
            temp = temp->next;
            delete temp2;
        }
    }
    delete [] al;
    cout << "\nMemory freed.\n";
}

或者，您可以从开始使用指针数组并动态地单分配所有节点，而不仅仅是邻接链，此时您的释放循环将起作用，但您的其余代码将需要进行一些更改。考虑到您对此的支持程度，我只会进行上面显示的更改并称其为好。