C语言链表: 在结尾插入节点

Question

我在C语言中的链表插入方法上遇到了一些麻烦。它似乎只能在链表开头添加。我做其他插入都失败了。而且这个CodeBlocks调试器很难理解，我还是不懂。它从来没有给我值，只有内存地址。无论如何，这是我的函数。你有看到它失败的原因吗？

/* function to add a new node at the end of the list */
int addNodeBottom(int val, node *head){

    //create new node
    node *newNode = (node*)malloc(sizeof(node));

    if(newNode == NULL){
        fprintf(stderr, "Unable to allocate memory for new node\n");
        exit(-1);
    }

    newNode->value = val;

    //check for first insertion
    if(head->next == NULL){
        head->next = newNode;
        printf("added at beginning\n");
    }

    else
    {
        //else loop through the list and find the last
        //node, insert next to it
        node *current = head;
        while(current->next != NULL)
        {
            if(current->next == NULL)
            {
                current->next = newNode;
                printf("added later\n");
            }
            current = current->next;
        }
    }
    return 0;
}

然后在主函数中，只添加了929。

   //testing addNodeBottom function
    addNodeBottom(929, head);
    addNodeBottom(98, head);
    addNodeBottom(122, head);
    addNodeBottom(11, head);
    addNodeBottom(1034, head);

- user445338

---

如果我将newNode->next设置为NULL，它仍然只插入第一个。 - user445338

在 current->next = newNode; 之后执行 break;。 - samplebias

你能为 node 提供结构定义并添加新行吗？另外，你是如何知道这是这种情况的？ - Mr. Shickadance

你也可以保留一个尾指针，使得在链表末尾插入元素变得简单，而不必遍历整个链表。 - Hristo

+1 同意，保持尾指针以使附加 O(1)。 - samplebias

Answer 1

这段代码是可行的。samplebias的答案几乎正确，但是需要进行第三次修改：

int addNodeBottom(int val, node *head){

    //create new node
    node *newNode = (node*)malloc(sizeof(node));

    if(newNode == NULL){
        fprintf(stderr, "Unable to allocate memory for new node\n");
        exit(-1);
    }

    newNode->value = val;
    newNode->next = NULL;  // Change 1

    //check for first insertion
    if(head->next == NULL){
        head->next = newNode;
        printf("added at beginning\n");
    }

    else
    {
        //else loop through the list and find the last
        //node, insert next to it
        node *current = head;
        while (true) { // Change 2
            if(current->next == NULL)
            {
                current->next = newNode;
                printf("added later\n");
                break; // Change 3
            }
            current = current->next;
        };
    }
    return 0;
}

修改1: newNode->next必须设置为NULL，以便在列表末尾不插入无效指针。

修改2/3：将循环改为一个无限循环，并在找到最后一个元素时跳出。请注意，在此之前，while(current->next != NULL)与if(current->next == NULL)相矛盾。

编辑：关于while循环，这种方式要好得多：

  node *current = head;
  while (current->next != NULL) {
    current = current->next;
  }
  current->next = newNode;
  printf("added later\n");

- schnaader

---

为什么我们要使用 malloc？为什么不直接创建一个类型为 node 的新变量，获取其指针并将其设置为下一个变量呢？ - Abhinav Manchanda

@AbhinavManchanda malloc在堆上分配空间，该空间在函数调用之间保持不变。如果我们“只是创建一个新的节点类型变量，获取其指针并将其设置为下一个”，那么空间将在函数的堆栈帧中分配，因此指针将指向该函数的堆栈帧中的某个位置。一旦我们到达返回语句，堆栈帧就会被释放，留下一个指向不安全位置的指针。 - philx_x

Answer 2

在你使用malloc分配一个node之后，一定要确保将node->next = NULL。

int addNodeBottom(int val, node *head)
{    
    node *current = head;
    node *newNode = (node *) malloc(sizeof(node));
    if (newNode == NULL) {
        printf("malloc failed\n");
        exit(-1);
    }    

    newNode->value = val;
    newNode->next = NULL;

    while (current->next) {
        current = current->next;
    }    
    current->next = newNode;
    return 0;
}    

我应该指出，在这个版本中，head 仍然被用作虚拟节点，而不是用于存储值。这使得你可以通过只有一个 head 节点来表示一个空列表。

- samplebias

---

但这不是唯一的错误，例如在while循环中也缺少了break;。 - schnaader

Answer 3

我知道这是一篇旧帖子，但仅供参考。以下是如何在不检查空列表的特殊情况下进行追加的方法，尽管牺牲了代码的简洁性。

void Append(List * l, Node * n)
{
    Node ** next = &list->Head;
    while (*next != NULL) next = &(*next)->Next;
    *next = n;
    n->Next = NULL;
}

- Ashley Duncan

Answer 4

在编写代码之前，我想提及一下关键点供您考虑。

//关键点

temp = 由C语言alloc.h库中的malloc函数分配的新节点的地址

prev = 现有链表中最后一个节点的地址。

next = 包含下一个节点的地址

struct node {
    int data;
    struct node *next;
} *head;

void addnode_end(int a) {
    struct node *temp, *prev;
    temp = (struct node*) malloc(sizeof(node));
    if (temp == NULL) {
        cout << "Not enough memory";
    } else {
        node->data = a;
        node->next = NULL;
        prev = head;

        while (prev->next != NULL) {
            prev = prev->next;
        }

        prev->next = temp;
    }
}

- user2800488

Answer 5

这个很好用：

struct node *addNode(node *head, int value) {
    node *newNode = (node *) malloc(sizeof(node));
    newNode->value = value;
    newNode->next = NULL;

    if (head == NULL) {
        // Add at the beginning
        head = newNode;
    } else {
        node *current = head;

        while (current->next != NULL) {
            current = current->next;
        };

        // Add at the end
        current->next = newNode;
    }

    return head;
}

使用示例：

struct node *head = NULL;

for (int currentIndex = 1; currentIndex < 10; currentIndex++) {
    head = addNode(head, currentIndex);
}

- BullyWiiPlaza

Answer 6

新节点始终添加在给定链表的最后一个节点之后。例如，如果给定的链表是5->10->15->20->25，并且我们在末尾添加一个项目30，则链表变为5->10->15->20->25->30。 由于链表通常由其头部表示，因此我们必须遍历列表直到结尾，然后将最后一个节点的下一个更改为新节点。

/* Given a reference (pointer to pointer) to the head
   of a list and an int, appends a new node at the end  */


    void append(struct node** head_ref, int new_data)
    {
    /* 1. allocate node */
         struct node* new_node = (struct node*) malloc(sizeof(struct node));

        struct node *last = *head_ref;  /* used in step 5*/

    /* 2. put in the data  */
        new_node->data  = new_data;

    /* 3. This new node is going to be the last node, so make next 
          of it as NULL*/
        new_node->next = NULL;

    /* 4. If the <a href="#">Linked List</a> is empty, then make the new node as head */
        if (*head_ref == NULL)
        {
       *head_ref = new_node;
       return;
        }  

    /* 5. Else traverse till the last node */
        while (last->next != NULL)
        last = last->next;

    /* 6. Change the next of last node */
        last->next = new_node;
        return;    
}

- Nikhil Sharma