Вставка в конец двусвязного списка

Я впервые работаю со связанными списками, и мне нужно создать функцию, которая может вставлять узел в конец двусвязного списка. Пока у меня есть

void LinkedList::insertAtTail(const value_type& entry) {
    Node *newNode = new Node(entry, NULL, tail);
    tail->next = newNode;
    tail = newNode;
    ++node_count;
}

Класс Node принимает значение для сохранения, значение для следующего указателя, на который нужно указывать, и значение для предыдущего указателя в этом порядке. Всякий раз, когда я пытаюсь вставить сюда узел, я получаю сообщение об ошибке, в котором говорится, что произошло необработанное исключение и было нарушение прав доступа при записи в местоположение 0x00000008.

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

РЕДАКТИРОВАТЬ:

Я должен был уточнить заранее, хвост - это указатель, указывающий на последний узел в списке. Tail-> next обращается к следующей переменной этого последнего узла, которая перед запуском функции указывает на NULL, но после ее выполнения должна указывать на новый созданный узел.


c++ nodes linked-list doubly-linked-list
person Brandon Bosso    schedule 09.10.2012    source источник
comment
Покажите нам: классы LinkedList и Node, поскольку в вашем первом посте не так много контекста.   -  person Thomas Matthews    schedule 09.10.2012
comment
Что-то не так с tail и tail->next, указывающими на newNode? (Похоже на круговую ссылку, но я могу ошибаться.)   -  person Thomas Matthews    schedule 09.10.2012
comment
Ваш tail изначально NULL? Вы не можете разыменовать его в tail->next, пока он не укажет на первый элемент   -  person Jonathan Wakely    schedule 09.10.2012
comment
Вам кажется, что порядок действий правильный. Параметры, которые вы передаете, указывают на правильную инициализацию узла. Просто по этому поводу я рискну предположить, что ваш указатель на хвосте сломан или конструктор копирования value_type топает по памяти. Покажите нам больше кода, пожалуйста. и подумайте о if (tail) перед этим tail->next заданием. Точно так же, где назначение заголовка на случай, если этот список чисто пустой, а хвостовая вставка - первая ?? может захотеть и этого.   -  person WhozCraig    schedule 09.10.2012
comment
@Thomas, когда tail- ›next настроен так, чтобы указывать на новый узел, tail ссылается на предыдущий хвост.   -  person imreal    schedule 09.10.2012
comment
@BrandonBosso и не забывайте, что если хвост равен NULL, скорее всего, голова тоже. Т.е. первая вставка узла в голову ИЛИ в хвосте должна привести к тому, что оба будут ссылаться на узел.   -  person WhozCraig    schedule 09.10.2012

Ответы (3)


arrow_upward
8
arrow_downward

На что указывает tail изначально? Если он NULL, вы разыменовываете нулевой указатель при попытке вставить первый элемент.

Помогает ли проверка tail перед разыменованием?

void LinkedList::insertAtTail(const value_type& entry) {
    Node *newNode = new Node(entry, NULL, tail);
    if (tail)
        tail->next = newNode;
    tail = newNode;
    ++node_count;
}

" снова вижу.

person Jonathan Wakely    schedule 09.10.2012
comment
Спасибо всем за помощь! Оказалось, что хвост указывает на NULL. После того, как я понял, что это легко исправить. Спасибо еще раз! - person Brandon Bosso; 09.10.2012

arrow_upward
1
arrow_downward

Предполагая, что ваш LinkedList имеет как голову, так и хвост, возможно, попробуйте:

void LinkedList::insertAtTail(const value_type& entry) 
{
    Node *newNode = new Node(entry, NULL, tail);
    if (tail)
        tail->next = newNode;
    tail = newNode;
    if (!head)
        head = newNode;
    ++node_count;
}

Просто выстрел в темноте

person WhozCraig    schedule 09.10.2012

arrow_upward
1
arrow_downward

Трудно сказать, что вызывает ошибку, не зная состояния списка перед операцией вставки (которая, кстати, на самом деле является добавлением, а не вставкой).

Есть большая вероятность, что вы не обрабатываете начальный случай добавления в пустой список. Базовый алгоритм (пустой список обозначается нулевым указателем на заголовок, все остальное не определено):

def append (entry):
    # Common stuff no matter the current list state.

    node = new Node()
    node->payload = entry
    node->next = NULL

    # Make first entry in empty list.

    if head = NULL:
        node->prev = NULL
        head = node
        tail = node
        return

    # Otherwise, we are appending to existing list.

    next->prev = tail
    tail->next = node
    tail = node
person paxdiablo    schedule 09.10.2012