C++ - стек со связанным списком-ошибка плохой памяти?

Question

C++ - стек со связанным списком-ошибка плохой памяти?

В настоящее время я пишу стек, который реализуется с помощью связанного списка. Я получаю эту ошибку:

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;



}

Большое спасибо! Я считаю, что большая часть моей логики верна. Я просто упускаю что-то маленькое. Если это что-то еще, Пожалуйста, скажите мне, и я отправлю этот код.

526 2

c++stack linked-list

2 ответов:

Comments

Ничего не найдено.

Vlad · Accepted Answer · 2010-11-03 02:18:41

Вы не должны удалять свой temp в push! Это часть списка. Поэтому, когда вы обращаетесь к этим данным позже, вы наверняка получаете исключение.
Во-вторых, вы должны инициализировать ваш pred с NULL в pop(), иначе вы получите неопределенное значение, присвоенное 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.

Dan8080 · Accepted Answer · 2010-11-03 01:59:20

Ваша функция push удаляет "temp". Однако temp указывает на данные, которые вы только что добавили в свой список. Если вызвать delete на указателе, вы не выбрасываете указатель, а скорее удаляете память, на которую он указывает! Избавьтесь от вашего оператора delete в push и протестируйте его первым (без pop). Я не просматривал вашу функцию pop, но я оставлю это в качестве упражнения для вас, чтобы проверить ошибки после тестирования pop().

- Dan8080