解释C语言中简单链表的一些基本概念

ejk8hzay  于 2023-03-01  发布在  其他
关注(0)|答案(4)|浏览(114)

所以我只是用C语言做了一个简单的链表,我有点困惑,为什么别人用节点引用和return函数都能形成链表,而我的用void函数。是因为我全局声明了头指针,而函数只是分别修改和使用createlist func和print func的指针吗?我对引用的概念很弱。谢谢你的帮助!

#include <stdio.h>

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

} node;

node *head = NULL;

void data(int item)
{
    node *newnode = (node *)malloc(sizeof(node));
    newnode->data = item;
    newnode->next = NULL;
    if (head == NULL)
    {
        head = newnode;
    }
    else
    {
        node *ptr = head;
        while (ptr->next != NULL)
        {
            ptr = ptr->next;
        }
        ptr->next = newnode;
    }
}

void print()
{
    node *ptr = head;
    printf("%d ->", ptr->data);

    while (ptr->next != NULL)
    {

        ptr = ptr->next;
        printf("%d ->", ptr->data);
    }
}
0wi1tuuw

0wi1tuuw1#

当其他人使用节点引用和返回函数,而我的使用void函数时,是因为我全局声明了头指针吗
简短的回答是:是的,通过使用全局变量,你避开了在函数内部更新头指针的常规麻烦,你的代码变得更简单,但是它也有代价--很大的代价。
一个简单的链表通常是这样的形式:

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

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

    ....

    return 0;
}

如果你想用一个函数来添加新节点到列表中,这个函数必须能够改变main中定义的head的值,因为C使用了传值的方式,你不能只把head传递给这个函数--这个函数不能改变mainhead的值,它只能改变一个初始值相同的局部变量。
两种"解决"的方法
1.让函数返回可能的新head值。
例如:

struct node * insert(struct node * head, T data)
{
    ... add node which may include head = malloc(....), i.e. head is changed

    return head;  // Return the possibly changed head
}

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

    head = insert(head, ...);

    ....

    return 0;
}

1.传递一个指向head的指针,以便函数可以使用该指针更改head的值
例如:

void insert(struct node ** phead, T data)
{
    ... add node which may include *phead = malloc(....), i.e. head is changed
                                   ^^^^^
                               Change head using the pointer

}

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

    insert(&head, ...);

    ....

    return 0;
}
    • 回到您的问题...**正确,因为您使用head作为全局变量,所以您避免了所有这些问题。您的insert函数可以只读取和修改全局变量,不需要向函数传递任何内容或从函数返回任何内容。

不错,但是有一个很大的缺点......在你的程序中你只能有一个列表。如果你需要第二个列表,你必须复制所有的代码。这是糟糕的设计。所以避免使用全局变量,使用两种"常用方法"中的一种。
也就是说......还有其他选择。
例如,通过将head指针 Package 在另一个结构体中。

struct list
{
    struct node* head;
};

现在,insert函数可以是void insert(struct list* list, T data),在main中,代码如下所示:struct list * list = calloc(....); insert(list, ...);。通过这种方式,您可以避免处理地址、双指针和返回值。
如果你想存储更多关于列表的信息,而不仅仅是head指针,那么将head封装在另一个结构体中就特别有用。

struct list
{
    struct node* head;
    struct node* tail;  // For fast list append implementation
    size_t size;        // For tracking number of list elements
};

另一个我见过的用来解决"更新头"问题的"技巧"是要求一个列表总是至少有一个元素(即固定的head)。这个元素将被认为是一个不保存任何数据的元素。这个技巧有一点内存开销,但简化了其他代码。

bxpogfeg

bxpogfeg2#

是的,因为你使用的是全局头指针,直接赋值给newnode是可以的,使用node引用的原因是因为在C语言中,所有的函数调用参数都是默认的传值,在函数内部对参数所做的改变对实参没有影响。
所以如果你需要改变你的头指针,你还需要一个间接层,那就是需要传递一个node**head参数,在你的func里面,只要做 *head = newnode,就会起作用。或者如果把指针传递给func,你需要返回新的头指针,否则新的错位头节点内存泄漏,因为它根本没有改变你传递的指针。

djmepvbi

djmepvbi3#

另外,要避免使用全局变量。在打印之前,请注意检查head是否为nullptr

void print()
{ 
    node *ptr = head; # if you never add item into the linklist, you will get into trouble.
    printf("%d ->", ptr->data);

如下所示会更安全

void print()
{ 
    node *ptr = head; 
    if( ptr )
    {
        printf("%d ->", ptr->data);
        while( .... )
    }

}

ws51t4hk

ws51t4hk4#

依赖于全局变量的实现没有什么技术上的错误(见下文)。全局变量可以在任何地方修改,问题就在于此,你必须审计你的整个代码库,以找出它在哪里被修改了。与函数式编程风格相反,在函数式编程风格中,每个函数都在其参数中记录了正在使用的内容和正在修改的内容:

void print(const node *root) {
    for(; root; root = root->next)
        printf("%d%s", root->data, root->next ? " -> " : "\n");
}

在程序中只能有链接列表的单个示例。作为泛型数据类型,这是有问题的。即使只需要单个示例,也可能需要测试代码,而只有单个示例会碍事。
另一件要考虑的事情是封装的概念。您可能希望对库的用户隐藏实现细节。这允许在不干扰库的用户的情况下更改您的实现。例如,您可能认为为每个32位数据值存储64位指针的200%开销过大,因此您可能决定每个节点应该保存一个数组,比如说,32个数据值,因此开销现在仅为6.25%。
全局变量还使多重处理变得更加复杂,因为现在必须为阅读操作锁定共享数据。
当然,也有一些缺陷,比如如果headNULL,那么print()就会出现segfault。

相关问题