C语言 为什么我们需要返回头在一个函数中插入一个节点在一个链表的末尾，为什么不在数组的情况下进行类似的操作

rryofs0p  于 2023-04-05  发布在  其他
关注(0)|答案(2)|浏览(122)

要在链表的末尾插入一个新节点，我们在main（）函数中有以下代码：

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

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

temp->next = newNode;

要将其作为一个函数，我们有以下代码：

struct node *insertAtEnd(struct node *head, int data)
{
    struct node *ptr = (struct node *)malloc(sizeof(struct node));
    ptr->data = data;
    struct node *p = head;

    while (p->next != NULL)
    {
        p = p->next;
    }
    p->next = ptr;
    ptr->next = NULL;
    return head;
}

int main()
{
    struct node *head;
    struct node *first;
    struct node *second;
    struct node *third;

    head = (struct node *)malloc(sizeof(struct node));
    first = (struct node *)malloc(sizeof(struct node));
    second = (struct node *)malloc(sizeof(struct node));
    third = (struct node *)malloc(sizeof(struct node));

    // fill data in head and point it to next node
    head->data = 69;
    head->next = first;

    // fill data in first and point it to next node
    first->data = 54;
    first->next = second;

    // fill data in second and point it to next node
    second->data = 33;
    second->next = third;

    // fill data in third and point it to null
    third->data = 36;
    third->next = NULL;
    printf("linked list before traversal : ");
    linkedListTraversal(head);
    printf("\n\nlinked list after traversal : ");

    head = insertAtEnd(head, 88);

    // a function to print all the data in linked list
    linkedListTraversal(head);
    return 0;
}

为什么我们必须返回head的值，并将其再次存储到main中声明的同一个head中，即使它的值没有改变，并且，就我对c语言的了解而言，与它的前导节点发生的变化无关，因为它只有下一个节点的信息。
关于这个疑问的想法是这样的：
我们使用指针是因为我们想在链表数据结构中做一些永久性的改变，所以我们需要通过值来传递。在链表的情况下，我们返回指针并将其存储在头节点中，但在数组的情况下，我们不必返回任何东西，因为，在数组的情况下我们只是篡改了存储在数组索引内的数据但是在链表的情况下我们篡改了它们的地址，改变它们的值。所以要么我们需要返回指针并将其存储到头节点中（这也是一个指针）或者我们需要使用双指针，在这种情况下，我们可以用void返回类型来实现这些函数。换句话说，with不需要返回任何东西。双指针是指一个指针变量，它可以存储特定数据类型的地址。

c

2条答案

按热度按时间
abithluo

abithluo1#

您发布的代码不正确。代码

struct node *p = head;

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

如果head == NULL（即列表为空），则函数insertAtEnd将崩溃，因为当p为NULL时，不允许取消引用p。
我建议你把函数insertAtEnd写成这样：

struct node *insertAtEnd( struct node *head, int data )
{
    struct node *new_node = malloc( sizeof *new_node );
    if ( new_node == NULL )
    {
        fprintf( stderr, "Memory allocation error!\n" );
        exit( EXIT_FAILURE );
    }
    new_node->data = data;
    new_node->next = NULL;

    if ( head == NULL )
    {
        return new_node;
    }

    struct node *p = head;

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

    p->next = new_node;

    return head;
}

现在，如果在列表为空时调用函数insertAtEnd，函数将不再崩溃，而是返回新头的地址。因此，现在重要的是，函数main通过用新头的地址覆盖旧头指针来使用此返回值。
然而，我个人不喜欢让函数insertAtEnd返回新头的地址。相反，我更喜欢将指向main中的指针head的指针传递给函数insertAtEnd，这样函数insertAtEnd就可以通过指针修改函数main中的指针head：

void insertAtEnd( struct node **pp_head, int data )
{
    struct node **pp_next = pp_head;

    //make pp_next point to the NULL pointer at the end of the list, or
    //to the head pointer in "main" if the list is empty
    while ( *pp_next != NULL )
    {
        pp_next = &(*pp_next)->next;
    }

    //allocate and initialize new node
    struct node *new_node = malloc( sizeof *new_node );
    if ( new_node == NULL )
    {
        fprintf( stderr, "Memory allocation error!\n" );
        exit( EXIT_FAILURE );
    }
    new_node->data = data;
    new_node->next = NULL;

    //link new node with the end of the list, or make it the new head if
    //the list was empty
    *pp_next = new_node;
}

下面是一个完整的代码示例：

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

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

void insertAtEnd( struct node **pp_head, int data )
{
    struct node **pp_next = pp_head;

    //make pp_next point to the NULL pointer at the end of the list, or
    //to the head pointer in "main" if the list is empty
    while ( *pp_next != NULL )
    {
        pp_next = &(*pp_next)->next;
    }

    //allocate and initialize new node
    struct node *new_node = malloc( sizeof *new_node );
    if ( new_node == NULL )
    {
        fprintf( stderr, "Memory allocation error!\n" );
        exit( EXIT_FAILURE );
    }
    new_node->data = data;
    new_node->next = NULL;

    //link new node with the end of the list, or make it the new head if
    //the list was empty
    *pp_next = new_node;
}

void print_list( struct node *head )
{
    for ( struct node *p = head; p != NULL; p = p->next )
    {
        printf( "%d\n", p->data );
    }
}

void free_list( struct node *head )
{
    for ( struct node *p = head; p != NULL;  )
    {
        struct node *temp = p;
        p = p->next;
        free( temp );
    }
}

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

    //add nodes to the initially empty list, one node
    //at a time
    insertAtEnd( &head, 69 );
    insertAtEnd( &head, 54 );
    insertAtEnd( &head, 33 );
    insertAtEnd( &head, 36 );
    insertAtEnd( &head, 88 );

    //print content of linked list
    printf( "The linked list has the following content:\n");
    print_list( head );

    //free all nodes in the list
    free_list( head );

    return EXIT_SUCCESS;
}

此程序具有以下输出：

The linked list has the following content:
69
54
33
36
88

正如您所看到的，所有五个节点都成功地添加到了最初为空的链表中，并且当head == NULL（即当链表为空时）调用insertAtEnd时，程序现在不会崩溃。
我添加了一些代码来检查malloc的返回值，因为否则，如果malloc返回NULL，代码将崩溃（例如，如果内存不足，可能会发生这种情况）。
此外，我还添加了释放所有节点的代码，以防止出现memory leak。

赞(0）分享  回复(0）举报  2023-04-05
siotufzp

siotufzp2#

在回顾你的初始代码时，我实际上没有看到在函数调用中返回头节点指针的必要。相反，我做了一些重构，使函数成为“void”函数。下面是你的代码的重构版本，将insert函数改为“void return”函数。

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

// Educated guess of the node structure

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

// Functional traversal and print function

void linkedListTraversal(struct node * head)
{
    struct node * work = head;

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

    return;
}

void insertAtEnd(struct node *head, int data)
{
    struct node *ptr = (struct node *)malloc(sizeof(struct node));
    ptr->data = data;
    struct node *p = head;

    while (p->next != NULL)
    {
        p = p->next;
    }
    p->next = ptr;
    ptr->next = NULL;
    return;
}
int main()
{
    struct node *head;

    head = (struct node *)malloc(sizeof(struct node));

    // Set up initial node data in head

    head->data = 69;
    head->next = NULL;

    // Fill data into first new node after the head node

    insertAtEnd(head, 54);

    // Fill data in second new node after the head node

    insertAtEnd(head, 33);

    // Fill data in third new node after the head node

    insertAtEnd(head, 36);

    printf("linked list before traversal : ");
    linkedListTraversal(head);
    printf("\n\nlinked list after traversal : ");

    // Create one more node

    insertAtEnd(head, 88);

    // A function to print all the data in linked list
    linkedListTraversal(head);
    return 0;
}

以这种方式使用该函数实际上使创建与头节点结构相关联的后续节点变得更简单。我只是使用重构后的函数来创建所有后续结构，而不是重复声明节点结构，然后手动链接结构。
下面是运行重构代码测试的终端输出。

@Vera:~/C_Programs/Console/NodeList/bin/Release$ ./NodeList 
linked list before traversal : Data: 69
Data: 54
Data: 33
Data: 36

linked list after traversal : Data: 69
Data: 54
Data: 33
Data: 36
Data: 88

可能我错过了问题的某些元素，但如果没有，这个重构的函数应该满足创建和链接节点结构到头部结构的要求，并提供必要的链接结构列表。
给予一下，看看它是否符合你的项目精神。

赞(0）分享  回复(0）举报  2023-04-05
我来回答

相关问题

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新问答

    更多
    • 蜀ICP备2022004421号-2 NULL123 https://www.null123.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com