Единственный связанный список: функция newNode не указывает на следующий узел

Question

Я сейчас экспериментирую с односвязным списком на C. Я написал функцию newNode для создания узла и функцию printNodes для распечатки всех узлов - это выглядит так:

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

struct Node 
{
  int data;
  struct Node *next;
}; 

void printNodes(struct Node *current_node)
{
  while(current_node != NULL)
  {
    printf("Node is: %d\n", current_node->data);
    current_node = current_node->next;
  }
}

int main()
{
  int number_1 = 2;
  int number_2 = 3;
  int number_3 = 4;

  struct Node *head;
  struct Node *second;
  struct Node *third;

  head = (struct Node*)malloc(sizeof(struct Node));  
  second = (struct Node*)malloc(sizeof(struct Node)); 
  third = (struct Node*)malloc(sizeof(struct Node));

  head->data = number_1;      
  head->next = second; 

  second->data = number_2;      
  second->next = third; 

  third->data = number_3;     
  third->next = NULL; 

  printNodes(head);

}

вывод выводится правильно:

Node is: 2
Node is: 3 
Node is: 4

Теперь я хотел написать функцию newNode, которая используется для создания нового узла, я изменил свой код следующим образом:

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

struct Node 
{
    int data;
    struct Node *next;
};

struct Node *newNode(int number_x, struct Node *nextnode)
{
    struct Node *tmp_node;

    tmp_node = malloc(sizeof(struct Node));
    tmp_node->data = malloc(sizeof(struct Node));
    tmp_node->data = number_x;
    tmp_node->next = nextnode;

    return tmp_node;
}   

void printNodes(struct Node *current_node)
{
    while(current_node != NULL)
    {
        printf("Node is: %d\n", current_node->data);
        current_node = current_node->next;
    }
}

int main()
{
    int number_1 = 2;
    int number_2 = 3;
    int number_3 = 4;

    struct Node *head;
    struct Node *second;
    struct Node *third;

    head = newNode(number_1, second);
    second = newNode(number_2, third);
    third = newNode(number_3, NULL);

    printNodes(head);

}

После компиляции я сначала получаю это предупреждение:

test.c:16:20: warning: incompatible pointer to integer conversion 
assigning to 'int' from 'void *' [-Wint-conversion]
tmp_node->data = malloc(sizeof(struct Node));
               ^ ~~~~~~~~~~~~~~~~~~~~~~~~~~~

И вывод выглядит так:

Node is: 2

Он показывает только узел head, я думаю, что-то естьнеправильно с указанием next (например, head->next = second), но что не так?Я не могу решить эту проблему.

Спасибо

Answer 1

Спасибо @WhozCraig за разъяснения.

Как он упомянул, узел second не знает, что он вводит.Чтобы разбить его, то же самое происходит, если вы напишите что-то вроде этого: int num; printf("%d",num)

Программа не знает, что является вводом, так как не было инициализированного ввода.

То же самое происходит с моей программой, там не было инициализированного узла, поэтому программа не знает, где находится next-node.Но если я напишу программу задом наперед, она теперь поймет, что это за значение, и сможет работать с ним:

    //use it backwards
    third = newNode(number_3, NULL);
    second = newNode(number_2, third);
    head = newNode(number_1, second);

Теперь вывод выводится правильно:

Node is: 2
Node is: 3
Node is: 4

спасибо запомогая, ура.

Answer 2

Во-первых, предупреждение (которое следует рассматривать как ошибку, к вашему сведению), которое вы видите, не связано с вашей общей проблемой, но, тем не менее, важно.Это и неподходящее, и утечки памяти, и имеет смутный вид тестирующих спагетти.В случае, если вы никогда этого не делали, кухонная техника старой школы, чтобы увидеть, «готово» ли макароны, - это взять веточку из кастрюли и буквально бросить ее в стену, чтобы увидеть, прилипает ли она.Эта, казалось бы, посторонняя строка кода выглядит именно так;как будто вы бросили что-то в стену, чтобы увидеть, застряло ли оно:

Это:

tmp_node->data = malloc(sizeof(struct Node)); // DELETE THIS

даже не должно быть в вашем коде вообще ;последующая строка делает то, что должно быть сделано, а именно:

tmp_node->data = number_x; // KEEP THIS

---

Создание связного списка

Хотя предыдущий диатрибу касается, это не 't то, что обеспечивает вашу незавидную позицию неправильного составления списка.Это проблема сама по себе.Рассмотрим следующее:

struct Node *head;      // indeterminate
struct Node *second;    // indeterminate
struct Node *third;     // indeterminate

В первых двух вызовах newNode вы передаете неопределенные значения указателя тому, что в конечном итоге будет вновь выделенным указателем next узла.Это важно.Изменив порядок сборки, вы можете получить поведение, которое вам нужно.

third = newNode(number_3, NULL);    // third is set, next points to NULL
second = newNode(number_2, third);  // second it set, next points to third
head = newNode(number_1, second);   // head is set, next points to second

Очевидно, что делать это не идеально, но просто узнать, как все устроено, это один из способов сделать это.Другим было бы назначить следующих членов напрямую.Например:

head = newNode(number_1, NULL); 
head->next = newNode(number_2, NULL);
head->next->next = newNode(number_3, NULL);

Это также работает, но, опять же, не идеально.Вы действительно хотите сделать это для построения связного списка из ста узлов?

Формирование цепочки связанного списка вперед

Там это оченькраткий способ построить восходящий связанный список без необходимости делать выше.Он называется forward-chaining и использует указатель на указатель, который изначально указывает на сам указатель головы (который изначально равен NULL):

struct Node *head = NULL;
struct Node **pp = &head; // points to a pointer, initially the head pointer

С учетом вышеизложенного мыможете связать воедино список из любого количества элементов, которые вы хотите.Сотня ?нет проблем:

for (int i=1; i<=100; ++i)
{
    // allocate a new node, storing the address at whatever pointer
    // is being addressed by the pointer-to-pointer pp. Initially it
    // will be the `head` pointer variable.

    *pp = malloc(sizeof **pp);
    (*pp)->data = i;

    // move pp to point to the next pointer of the node we just added
    pp = &(*pp)->next;
}
*pp = NULL; // terminate the list


printNodes(head);

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

Во всяком случае, это было дольше, чем я хотел, но я надеюсь, что это помогло.

Answer 3

Здесь

tmp_node->data = malloc(sizeof(struct Node)); /* remove this statement */

data является членом struct Node и это целое число, для этого отдельно вам не нужно выделять память.Вы уже выделили полную структуру здесь

tmp_node = malloc(sizeof(struct Node)); /* this is enough */

Также здесь

head = newNode(number_1, second);

Что такое second?Его следует инициализировать с помощью NULL, как

struct Node *second = NULL;

, затем только в newNode() функции tmp_node->next, назначенной с правильным значением

tmp_node->next = nextnode; /* now nextnode contains NULL, that's correct */

Или вы можете сделать это, как показано ниже

head = newNode(number_1, NULL);
second = newNode(number_2, head);
third = newNode(number_3, second);

и затем при вызове printNodes() передайте third вместо head.Например,

printNodes(third);

Пример кода:

struct Node  {
    int data;
    struct Node *next;
};

struct Node *newNode(int number_x, struct Node *nextnode) {
    struct Node *tmp_node;
    tmp_node = malloc(sizeof(struct Node));
    tmp_node->data = number_x;
    tmp_node->next = nextnode;
    return tmp_node;
}

void printNodes(struct Node *current_node) {
    while(current_node != NULL) {
        printf("Node is: %d\n", current_node->data);
        current_node = current_node->next;
    }
}

int main(void) {
    int number_1 = 2;
    int number_2 = 3;
    int number_3 = 4;

    struct Node *head = NULL;
    struct Node *second = NULL;
    struct Node *third = NULL;

    head = newNode(number_1, NULL);
    second = newNode(number_2, head);
    third = newNode(number_3, second);
    printNodes(third);
        return 0;
}