C ++ - стек со связанным списком - ошибка памяти? - PullRequest
Новая
       1

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

2 голосов
/ 03 ноября 2010

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

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;

}

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

Ответы [ 2 ]

2 голосов
/ 03 ноября 2010

Вы не должны удалять свои 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.

2 голосов
/ 03 ноября 2010

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

-Dan8080

...