Вставка в связанный список всегда возвращает последний узел, а не текущий узел

Question

Итак, я пишу программу, которая создает динамический список, она вставляет новый узел после последнего узла и в конце концов печатает только что созданный список.Я хочу, чтобы, когда я его печатал, он фактически печатал номер текущего узла подряд (например, Info: 1, Info: 2, Info: 3), но оказалось, что он всегда печатает последний узел.Я предполагаю, что это ошибка указателя, но не могу найти что.

#include <stdio.h>
#include <stdlib.h>

struct node{
  int info;
  struct node* pNext;
};

typedef struct node Node;

void tail_insertion(Node* pFirst, Node* pLast);
void print_list(Node* pFirst);

static int n=3;

int main()
{
    Node *pFirst=NULL, *pLast=NULL;
    tail_insertion(pFirst, pLast);
}

void tail_insertion(Node* pFirst, Node* pLast){
  // Creation of a new node in the heap
  Node *pNew = (Node*) malloc(sizeof(Node));
  pNew->info=0;
  pNew->pNext= NULL;

  for(int i=0; i<3;i++){
    if(pFirst == NULL){// No node in the list
      pNew->info++;
      pFirst = pNew; // The first node is the newly created one
      pLast = pNew; // The last node is the newly created one
      printf("Ok the list was empty\n");
    }
    else{
      // Else, there is already at least one node in the list
      pNew->info++;
      pLast-> pNext= pNew; // the last node becomes the second one
      pLast= pNew; // The last node is the newly created one
      printf("Ok the list wasn't empty\n");
    }
  }
  print_list(pFirst);
  return;
}


void print_list(Node* pFirst){
  if(pFirst == NULL){
    printf("No node in the list!\n");
  }
  else{
    // New pointer used to scan the list.
    Node* pScan = pFirst;
    do{
      printf("Info: %d\n", pScan->info);
      // ptrScan is updated to point to the next node in the
      // list
      pScan = pScan->pNext;
    }while(pScan!= NULL && --n); //NULL when this was the last node
  }
  return;
}

Он печатает так:

Ok the list was empty
Ok the list wasn't empty
Ok the list wasn't empty
Info: 3
Info: 3
Info: 3

Answer 1

Общий анализ кода

Давайте рассмотрим tail_insertion(...) и то, что вы хотите, чтобы он делал:

• Вы создаете новый узел;
• Вы даете ему правильные значения;
• Вы запускаете цикл for с намерением создать больше узлов на основе определенных условий;
• Вы печатаете весь список, чтобы проверить, работал ли;

Теперь посмотрите на код для tail_insertion(...) функции ( комментариев удалено ):

Node *pNew = (Node*) malloc(sizeof(Node));

pNew->info=0;
pNew->pNext= NULL;

for(int i=0; i<3;i++){

    if(pFirst == NULL){

        pNew->info++;

        pFirst = pNew;
        pLast = pNew;

        printf("Ok, the list was empty.\n");

    } else {

        pNew->info++;

        pLast-> pNext= pNew;
        pLast= pNew;

        printf("Ok, the list wasn't empty.\n");

    }

}

print_list(pFirst);

Видите еще проблемы?Нет?Что ж, давайте продолжим.

Отладка

Мы собираемся пошагово отладить эту функцию .Помимо исправлений программы, это важно и для процесса обучения:

• Создание узла :
  • Вы создаете pNEW.Это пусто;
  • Давайте дадим ему адрес 0x01 (выдуманный);
  • A 0 назначен на pNew->info;
  • A NULL назначен на pNew->pNext;
• Начало цикла for - попытка создать 3 узла для списка:
  • i = 0:
    • Вы проверяете, пустой ли список.Это:
    • Вы добавляете 1 к pNew->info значению.Адрес pNew равен 0x01;
    • pFirst назначен для точки по адресу 0x01;
    • pLast назначен для точки по адресу 0x01поскольку список был пуст;
    • Вы печатаете сообщение о том, что список пуст;
  • В конце i = 0 список выглядит следующим образом:
    • pFirst точек по адресу 0x01;
    • pLast точек по адресу 0x01;
    • 0x01->info равно 1;
  • i = 1
    • Вы проверяете, пустой ли список.Это не:
    • Вы добавляете 1 к pNew->info значению.Адрес pNew - 0x01.Создание другого узла никогда не было;
    • pLast->pNext назначено для указания на адрес 0x01;
    • pLast назначено для указания на адрес 0x01;
    • Вы печатаете сообщение о том, что список не был пустым;
  • В конце i = 1 список выглядит следующим образом:
    • pFirst указывает по адресу 0x01;
    • pLast указывает по адресу 0x01;
    • pLast->pNext указывает по адресу 0x01;
    • 0x01->info is 2;
  • i = 2
    • Вы проверяете, пустой ли список.Это не:
    • Вы добавляете 1 к pNew->info значению.Адрес pNew - 0x01.Никогда не было создания другого узла;
    • pLast->pNext назначен для указания по адресу 0x01;
    • pLast назначен для указания по адресу 0x01;
    • Вы печатаете сообщение о том, что список не был пустым;
  • В конце i = 2 список выглядит следующим образом:
    • pFirst точек по адресу 0x01;
    • pLast точек по адресу 0x01;
    • pLast->pNext точек по адресу 0x01;
    • pLast->pNext->pNext указывает на адрес 0x01;
    • 0x01->info is 3;
  • Конец цикла for;
• Печать полученного списка :
  • Вызов print_list(...)

Заключение

На данный момент вы, вероятно, видели , что не так : вы не создали новый узел внутри цикла for.Вы создали это вне цикла.Это приводит к повторяющемуся процессу , добавляющему тот же самый узел с тем же адресом в список .

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

Исправление кода

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

Node *pNew; /* Declaring pNew *without* assignment. */

for(int i = 0; i < 3; i++){

    pNew = (Node*) malloc(sizeof(Node)); /* Allocation of new memory address. */

    pNew->info  = i; /* pNew->info works like an ID in you current code. */

    pNew->pNext = NULL; /* It is proper to assign NULL */

    if(pFirst == NULL){

        pNew->info++;

        pFirst       = pNew;
        pLast        = pNew;

        printf("The list was empty.\n");

    } else {

        pNew->info++;

        pLast->pNext = pNew;
        pLast        = pNew;

        printf("The list wasn't empty.\n");

    }
}

print_list(pFirst);

Обратите внимание, что я удалил функцию return(...), так как в этом не было необходимости.В этом нет необходимости, поскольку tail_insertion(...) имеет тип void.

Кроме того, pNew->info сохраняет идентификатор узла на момент моего чтения.Поэтому не должно быть проблем с присвоением i.При необходимости внесите необходимые изменения.

Заключительные замечания

Есть комментарии о том, что вам не нужно pLast.Хотя это действительно так, вам необходимо учитывать:

• Если вы используете только pFirst, вам нужно убедиться, что после вставки нового узла в pFirst->pNext вы выполните pFirst->pNext->pNext = NULL.Таким образом, вы можете узнать, когда достигли конца списка, сравнивая с NULL;
• Если вы продолжаете использовать pLast, вы можете сравнить с pLast, чтобы узнать, является ли адреспоследний адрес в списке.Очевидно, что вы также можете сравнить с NULL после моего исправления;
• Учитывая хвостовые вставки , наличие pLast значительно облегчает работу и снижает нагрузку на процессор в долгосрочной перспективе;

Вы, наверное, знаете, но вы должны поместить print_list(pFirst); в функцию main(...), чтобы сделать вещи более организованными.Кроме того, это заставляет мой «код OCD» достигать новых уровней отчаяния!; -)

Answer 2

Две проблемы:

• вы не передаете указатели на указатели списка (Node * -> Node **)
• вы пытаетесь вставить то же самое Node три раза (переместите malloc() в цикл)

Я думаю, static int n = 3 и while ... && --n), вероятно, были добавлены в отчаянной попытке "исправить" бесконечноецикл в print_list(), потому что pscan->pNext дал pscan в исходном коде ...

Исправлен и очищен код:

#include <stdio.h>
#include <stdlib.h>

typedef struct node Node;
typedef struct node {
  int   info;
  Node* pNext;
} Node;

static void print_list(Node* pFirst) {
  // New pointer used to scan the list.
  Node* pScan = pFirst;
  while (pScan) {
    printf("Info: %d\n", pScan->info);
    // ptrScan is updated to point to the next node in the
    // list
    pScan = pScan->pNext;
  }
}

static void tail_insertion(Node** pFirst, Node** pLast) {
  for (int i=0; i<3; i++) {
    // Creation of a new node in the heap
    Node *pNew  = malloc(sizeof(Node));
    pNew->info  = i + 1;
    pNew->pNext = NULL;

    if (*pFirst == NULL) {    // No node in the list
      *pFirst = pNew;         // The first node is the newly created one
      *pLast  = pNew;         // The last node is the newly created one
      printf("Ok the list was empty\n");
    } else {                  // Else, there is already at least one node in the list
      (*pLast)->pNext = pNew; // the last node becomes the second one
      *pLast          = pNew; // The last node is the newly created one
      printf("Ok the list wasn't empty\n");
    }
  }
  print_list(*pFirst);
}

int main(int argc, char *argv[]) {
  Node *pFirst = NULL;
  Node *pLast  = NULL;
  tail_insertion(&pFirst, &pLast);
}

Тестовый прогон:

$ gcc -Wall -Werror -o dummy dummy.c
$ ./dummy
Ok the list was empty
Ok the list wasn't empty
Ok the list wasn't empty
Info: 1
Info: 2
Info: 3