C++ - 堆栈与链表 - 内存错误？

Question

我目前正在编写使用链表实现的堆栈。我收到此错误：

Unhandled exception at 0x75249617 in STACK_LinkedList.exe: Microsoft C++ exception: std::bad_alloc at memory location 0x002ee8f8. 

我相信它可能来自我的 push() 或 pop() 函数。我找不到我的错误。我对链表相当陌生，所以我很难找到错误。

这是我的 push() 函数：

// Adds an item to the top of the stack
template <class S>
void Stack<S>::push(const S & e)
{
    NodePointer temp = new Node(e);

    if ( isEmpty() )
    {
        theTop = theFront = temp;
    }
    else
    {
            // Whatever is after top is stored in temp to keep track of it
        theTop->next = temp;

            // TheTop is stored in temp
        theTop = temp;  
        delete temp; 
    }
}

这是我的 pop() 函数：

//Takes the item off the top of the stack
template <class S>
void Stack<S>::pop()
{
    if ( !isEmpty() )
    {        
                //temp node is set equal to the front
        NodePointer temp = theFront;

                //Holds the second to last node in the linked list
        NodePointer pred;

                //loops through until the node after temp is 0
        while (temp->next != 0)
        {
                        //sets the second to last as temp
            pred = temp ;

                        //basically "increments" temp to the next node
            temp = temp->next ;
        }

                //sets temp equal to the top
        temp = theTop;

                //the top is then set to its predecessor
        theTop = pred;

                //deletes what was known as the top
        delete temp;
    }

    else
        cout << "STACK IS EMPTY" << endl;

}

非常感谢！我相信我的大部分逻辑都是正确的。我只是缺少一些小东西。如果还有其他问题，请告诉我，我将发布该代码。

Answer 1

您不应该在 push 中删除您的temp！这是列表的一部分。因此，当您稍后访问此数据时，您肯定会遇到异常。

其次，您必须在 pop() 中使用 NULL 初始化您的 pred，否则您将获得分配给 theTop 的未定义值 如果堆栈仅包含 1 个项目。

第三，您应该在 pop() 中删除您在 push() 中分配的 Node。

总的来说，你的方法似乎不是很有效。您应该更好地以相反的方式存储指针：从堆栈顶部到底部项目。这样您就不需要在每个 pop() 上遍历整个堆栈。您的代码将类似于：

void push(data)
{
    allocate new top
    new top's next is the old top
    store new top in the class
}

void pop()
{
    if empty, ERROR;
    new top = old top's next
    deallocate old top
}

请注意，您根本不需要 theFront 。

Answer 2

您的推送功能正在删除“temp”。但是，temp 指向您刚刚添加到列表中的数据。如果对指针调用delete，您不会丢弃该指针，而是删除它指向的内存！删除推送中的删除语句并首先测试它（不弹出）。我没有查看您的 pop 函数，但我会将其作为练习，供您在测试 pop() 后检查错误。

-Dan8080