0

我正在尝试使用链表实现一个简单的堆栈。当我运行下面的代码时，我得到

6
<some random integer>

几个小时以来，我一直在寻找我的错误，但没有成功。我想某处有一个未初始化的变量，但我似乎找不到它。

#include <iostream>

using namespace std;

class node {
    public:
        node operator = (const node&);
        node(int d,node* n): data(d), prev(n) {}
        node(){}
        node* prev;
        int data;
};

node node::operator = (const node &n) {
    node r(n.data, n.prev);
    return r;
}

class stack {
    public:
        stack();
        void push(int);
        int pop();
        bool empty();
    private:
        node* top;
};

stack::stack() {
    top = 0;
}

bool stack::empty() {
    return top == 0;
}

void stack::push(int x) {
    node n(x,top);
    top = &n;
}

int stack::pop() {
    if (!empty()) {
        node r = *top;
        //cout << "r.data: " << r.data << endl;
        top = top->prev;
        return r.data;
    }
    else {
        cout << "Stack empty!" << endl;
        return 0;
    }
}

int main() {
    stack a;
    a.push(5);
    a.push(6);
    cout << a.pop() << endl;
    cout << a.pop() << endl;
}

现在让我完全困惑的是，当我取消注释该行时

        //cout << "r.data: " << r.data << endl;

出于测试目的，输出更改为

r.data: 6
6
r.data: 6
6

为什么会这样？

4

3 回答 3

5

这段代码是错误的：

void stack::push(int x) {
    node n(x,top);
    top = &n;
}

在这里，您创建一个局部变量，然后设置top为指向该变量。但是当函数返回时，局部变量不再存在，并top指向一些无效的内存。

您需要node使用操作符在堆上创建一个新的new：

void stack::push(int x) {
    node* n = new node(x,top);
    top = n;
}

当然，现在您必须确保分配的节点在完成后是空闲的。这应该在stack弹出所有节点的析构函数中完成，并且pop您需要使用delete运算符来释放内存。

于 2012-10-09T15:48:41.483 回答
3

除非这是一个类的编程作业，否则请使用 STL 提供的std::stack 。

于 2012-10-09T16:01:43.877 回答
0 
void stack::push(int x) {
    node n(x,top);
    top = &n;
}

这个函数的问题是 n 具有自动存储期限，并且在函数返回后被销毁。

相反，使用动态分配：

node* n = new node(x, top);
于 2012-10-09T15:55:03.403 回答