Вопрос о связанных списках / указателях в c ++

Question

Природа указателей на N ++ в C ++ кажется произвольной.Я уверен, что есть метод, который я пропускаю, но следующее имеет смысл для меня, но, похоже, не работает.У меня есть следующий метод для добавления узла в связанный список:

LLNode *ll; // set to NULL in constructor.
void addToLL(Elem *e)
{
    LLNode *current = ll;
    while(true)
    {
        // edge case of an empty list.
        if (ll == NULL)
        {

            ll = new LLNode(e);
            break;
        }
        else if (current == NULL)
        {
            current = new LLNode(e);
            break;
        }
        else {
            current = current->next;
        }

    }
}

При добавлении второго узла в список, случай для current == NULL не обнаруживается, поэтому он пытается вызвать current = current->next и сбои делают доступ к недействительной памяти.Почему это так?LLNode имеет указатель на Elem и указатель, вызываемый рядом с другим LLNode.

Answer 1

Возможно, вы не установили указатель next на NULL в конструкторе LLNode.

Объекты основных типов в C ++ (типы указателей, числовые типы и т. Д.) Имеют неопределенные начальные значения: они не инициализируются по умолчанию.Вам необходимо явно инициализировать такие объекты перед их использованием.

Answer 2

Для такого рода вещей вам нужен указатель на указатель, чтобы убрать множество ненужных исключений в вашей реализации:

LLNode *ll = NULL;

void addToLL(Elem *e)
{
  LLNode** current = ≪

  // While the current pointer to pointer is mapped to something,
  // step through the linked list.
  while (*current)
    current = &(*current->next);

  // At this point current is pointing to a NULL pointer and can
  // be assigned to.
  *current = new LLNode(e);
}

Причина, по которой указатели NULL, заключается в том, чтов false и позволяет выполнять простые проверки, такие как while (*current), без лишних затрат.В CPU это обычно заканчивается реализацией операции test-if-zero.

Указатели имеют значение NULL, только если они инициализированы как таковые.В C они часто не определены, если не инициализированы должным образом, и обращение к неинициализированному указателю не приводит к катастрофе.Вы должны убедиться, что любые указатели, которые вы определяете, всегда инициализируются чем-то допустимым перед их использованием.

Answer 3

Первое, что я вижу в вашем коде, это то, что current является локальным, распределяется с новым, но фактически никогда не присоединяется к списку.

Конечно, ваш код должен быть

else if( current->next == NULL )
{
   current->next = new LLNode( e );
   break;
}

Конечно, LLNode должен инициализироваться рядом с NULL в своем конструкторе.

Конечно, ваш список имеет время вставки O (N), и если это что-то иное, чем упражнение, вы почти наверняка должны использовать контейнеры стандартной библиотеки.

Возможно, вам также следует переместить край ребра из цикла.

Answer 4

1) Вы говорите, что ll имеет значение NULL в конструкторе. Но какой конструктор? Здесь нет определения класса. ll глобальная переменная? И вы уверены, что конструктор для LLNode устанавливает указатель next в NULL?

2) Состояние

    if (ll == NULL)

можно и нужно проверять вне цикла, поскольку ll не изменяется внутри цикла.

3) current - локальная переменная стека, поэтому ее назначение не будет иметь никакого эффекта после выхода из функции. В частности, current = new LLNode(e) - это утечка памяти.

4) Чтобы добавить узел в связанный список, вы должны найти последний узел существующего списка и изменить его указатель next. Примерно так будет работать:

 // ll is a field representing the first node in your existing linked list.
 if (ll == NULL) {
     ll = new LLNode(e);
 }
 else {
     current = ll;
     while (current->next != NULL) {
         current = current->next;
     }
     current->next = new LLNode(e);
 }

РЕДАКТИРОВАТЬ : Изменено выше на основе вашего комментария, что ll является членом класса.