单向链表：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

这里

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 like

初始化

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

Answer 2

感谢@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 3

首先，您看到的警告（应该被视为错误，仅供参考）与您的整体问题无关，但它仍然很重要。它既不正确又会泄漏内存，并且具有测试意大利面条的模糊外观。万一你从来没有做过，一个老派的厨房技术来检查意大利面是否 "done" 是从锅里拿出一根线，然后把它扔到墙上看它是否粘住。这行看似无关的代码看起来就是这样；就像你往墙上扔东西看它是否卡住了：

这个：

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

根本不应该出现在您的代码中；后续行做了应该做的事情，即：

tmp_node->data = number_x; // KEEP THIS

连接一个链表

虽然之前的谩骂令人担忧，但这并不是导致您没有正确连接列表的令人羡慕的立场的原因。这本身就是一个问题。考虑以下因素：

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

这只是构建链表的一种方法。还有很多其他的（例如，递归地做，在学校学习递归时并不少见）。但它可能是最简单的，几乎肯定是最快的。

无论如何，这比我预期的要长，但我希望它有所帮助。

单向链表：newNode 函数不指向下一个节点

Singly Linked List: newNode function doesn't point to next Node

c

int

linked-list

nodes

singly-linked-list