c - insertAtTail 未在链表中添加节点

Question

我是数据结构的新手。我正在创建一个链表程序。我已经创建了程序。但是不明白为什么 insertAtTail 没有将节点添加到链表中。

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

struct node *head=NULL;

int main( void ) {
    insertAtHead(3);
    insertAtHead(4);
    insertAtHead(5);
    insertAtHead(8);
    insertAtTail(2);
    display();

    return 0;
}

void insertAtHead( int data ){
    struct node *newNode;

    newNode = (struct node *)malloc( sizeof(struct node) );
    newNode->data = data;
    newNode->next = NULL;

    if( head == NULL ){
        head = newNode;
    } else {
        newNode->next = head;
        head = newNode;
    }
}

void insertAtTail(int data){
    struct node *newNode, *temp;

    newNode = (struct node *)malloc( sizeof(struct node) );
    newNode->data = data;
    newNode->next = NULL;

    if( head == NULL){
        head = newNode;
    } else {
        temp = head;
        while ( temp != NULL){
            temp = temp->next;
        }

        temp = newNode;
    }

}

void display(){
    struct node *temp;

    temp = head;
    while ( temp != NULL)
    {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");   
}

期望输出:8 -> 5 -> 4 -> 3 -> 2 -> NULL

实际输出:8 -> 5 -> 4 -> 3 -> NULL

Answer 1

变量 temp 是函数的局部变量，它占用的内存与列表的节点不同。

在这个循环之后

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

变量 temp 设置为 NULL。然后在这个声明中

    temp = newNode;

你正在改变变量本身占用的内存。列表的节点没有改变。

按以下方式更改循环

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

    temp->next = newNode;

还要注意两个，所有在 main 中使用的函数都应该在使用前声明。

例如

void insertAtHead( int data );

//...

int main( void )
{
    //...
}

此外，函数处理全局变量 head 也不是一个好主意。您应该重写函数，将列表的头部作为参数传递给函数。

例如，在这种情况下，函数 insertAtHead 可以按以下方式定义

int insertAtHead( struct node **head, int data )
{
    struct node *newNode = malloc( sizeof(struct node) );

    int success = newNode != NULL;

    if ( success )
    {
       newNode->data = data;
       newNode->next = *head;
       *head = newNode;
    }

    return success;
}

作为一个程序的结果，您可以通过在 main 的头部进行本地声明来拥有多个列表。

这是一个演示程序

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

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

int insertAtHead( struct node **head, int data )
{
    struct node *newNode = malloc( sizeof(struct node) );

    int success = newNode != NULL;

    if ( success )
    {
       newNode->data = data;
       newNode->next = *head;
       *head = newNode;
    }

    return success;
}

int insertAtTail( struct node **head, int data )
{
    struct node *newNode = malloc( sizeof(struct node) );
    int success = newNode != NULL;

    if ( success )
    {
        newNode->data = data;
        newNode->next = NULL;

        while ( *head != NULL ) head = &( *head )->next;

        *head = newNode;
    }

    return success;
}

void display( struct node *head )
{
    for ( struct node *current = head; current != NULL; current = current->next )
    {
        printf("%d -> ", current->data);
    }

    puts( "NULL" );   
}

int main(void) 
{
    struct node *head = NULL;

    insertAtHead( &head, 3 );
    insertAtHead( &head, 4 );
    insertAtHead( &head, 5 );
    insertAtHead( &head, 8 );
    insertAtTail( &head, 2 );

    display( head );

    return 0;
}

它的输出是

8 -> 5 -> 4 -> 3 -> 2 -> NULL