Ошибка при вставке нового элемента в отсортированный связанный список - PullRequest
Новая
       19

Ошибка при вставке нового элемента в отсортированный связанный список

1 голос
/ 19 марта 2011

Я использую следующую функцию для вставки нового узла в отсортированный связанный список целых чисел 

 // Insert new element
template <class Type>
bool list<Type> :: Insert (const Type& NewElement)
{
    Node *NewNode, *TempNext, *TempPrevious;
    NewNode = new Node;
    NewNode -> Element = NewElement;

    for (TempNext = Head; TempNext != NULL; TempPrevious = TempNext, TempNext = TempNext -> Next) 
    {
        NewNode -> Next = TempNext;
        if (TempNext == Head) Head = NewNode; // Check for empty list
        else if (NewNode -> Element >= TempNext -> Element) continue; // Check for correct point in list
        else TempPrevious -> Next = NewNode;
        return true;
    }

    // If execution reaches this point, then the new node goes at the end of the list    
    TempPrevious -> Next = NewNode;
    return true;
}

Всякий раз, когда я пытаюсь вставить элемент в пустой список, используя этот алгоритм, программа возвращает ошибку сегментации. Проверка с помощью GDB определяет строку TempPrevious -> Next = NewNode; в самом конце как причину, но выполнение не должно достигать ее, поскольку return true в конце цикла for должно вернуть управление вызывающей функции, но для по какой-то причине это не так. Кто-нибудь может увидеть, где я здесь не так? *

Ответы [ 2 ]

5 голосов
/ 19 марта 2011

Обратите внимание, что если список пуст, TempPrevious будет неинициализированным указателем.Когда вы попытаетесь запустить цикл for в пустом списке, TempNext сразу же будет NULL, и вы не выполните оператор TempPrevious = TempNext.Поскольку вы никогда не устанавливаете для TempPrevious значение по умолчанию, оно не будет инициализировано, и поэтому код 

TempPrevious -> Next = NewNode;

будет разыменовывать указатель мусора, следовательно, ваш сбой.

Чтобы исправить это, вам либо понадобится особый случай, когда список пуст, либо использовать какой-то другой подход для вставки списка (возможно, сохраняя указатель на указатель узла для перезаписи), который изящно обрабатывает вставку в пустой список.

1 голос
/ 19 марта 2011

Прошло много времени с тех пор, как я написал C ++, но потому ли, что TempPrevious создано, но никогда не назначается?

...