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

Question

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

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

我相信它可能来 self 的 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()中分配的节点。

总的来说，您的方法似乎不是很有效。您最好以相反的方式存储指针:从堆栈顶部到底部项目。这样你就不需要在每个 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。