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

Question

Характер указателей, являющихся NULL в 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; 
     } 

    } 
} 

При добавлении 2-й узел в списке, в случае 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 потому, что оценивается как ложное и позволяет выполнять простые проверки, такие как while (*current) без большого количества накладных расходов. В CPU это обычно заканчивается тем, что выполняется как операция «тест-если-нуль».

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

Answer 3

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); 
} 

EDIT: Модифицированная выше на основе ваших комментариев, что ll является членом класса.

Answer 4

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

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

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

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

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

Вы также должны перенести кромку края из петли.