JZTXT

C语言数据结构解析与实例-链表

发布时间 2023-06-26 15:45:42作者: 言叶以上

链表是C语言中的一种基本数据结构。

对于C程序员来说，了解链表是必要的。

链表是一种动态数据结构，其长度可以在运行时增加或减少。

链表与数组有什么不同？考虑以下几点：

  • 数组是一种静态数据结构。这意味着数组的长度在运行时无法改变，而链表是一种动态数据结构。
  • 在数组中，所有元素都保持在连续的内存位置上，而在链表中，元素（或节点）可以位于任何位置，但仍然相互连接。

何时优先选择链表而不是数组？在不知道要存储的数据量时，通常首选链表。例如，在员工管理系统中，无法使用数组，因为数组长度是固定的，而任意数量的新员工可以加入。在这种情况下，使用链表（或其他动态数据结构），因为它们的容量可以在运行时根据需要增加（或减少）。

链表在内存中是如何排列的？

链表基本上由位于随机内存位置的内存块组成。现在，有人可能会问它们是如何连接或如何遍历的？嗯，它们是通过指针连接起来的。通常，链表中的一个块通过以下结构表示：

struct test_struct
{
    int val;
    struct test_struct *next;
};

正如你在这里所看到的，这个结构体包含一个值 val 和一个指向相同类型结构体的指针。值 val 可以是任意值（取决于链表所存储的数据），而指针 next 包含了链表中下一个块的地址。因此，通过这些包含下一个节点地址的 next 指针，实现了链表的遍历。最后一个节点（或者只有一个节点的链表）的 next 指针将包含一个 NULL 值。

节点是如何创建的？

节点是通过以下方式将内存分配给一个结构（如上文所示）来创建的：

struct test_struct *ptr = (struct test_struct*)malloc(sizeof(struct test_struct));

这个结构体包含一个值 val 和一个指向相同类型结构体的指针。值 val 可以是任意值（取决于链表所存储的数据），而指针 next 包含了链表中下一个块的地址。因此，通过这些包含下一个节点地址的 next 指针，实现了链表的遍历。最后一个节点（或者只有一个节点的链表）的 next 指针将包含一个 NULL 值。

...
...
ptr->val = val;
ptr->next = NULL;
...
...

搜索节点

搜索一个节点意味着查找包含要搜索的值的节点。实际上，如果我们谈论线性搜索的话，这是一个非常简单的任务（请注意，还有许多搜索算法）。只需从第一个节点开始，然后将要搜索的值与该节点中包含的值进行比较。如果值不匹配，则通过“next”指针（它包含下一个节点的地址）访问下一个节点，并在那里进行相同的值比较。搜索会继续进行，直到访问到最后一个节点，或者找到了值等于要搜索的值的节点。以下是一个代码片段示例：

...
...
...
    while(ptr != NULL)
    {
        if(ptr->val == val)
        {
            found = true;
            break;
        }
        else
        {
            ptr = ptr->next;
        }
    }
...
...
...

删除节点

节点的删除通过首先在链表中找到该节点，然后在包含其地址的指针上调用free()函数来实现。如果被删除的节点不是第一个或最后一个节点，那么需要将被删除节点之前的节点的“next”指针指向被删除节点之后的节点的地址。就像如果一个人从人链中脱离出来，那么这个人之前的两个人需要重新握手来保持链条的完整。

一个实际的C链表示例

这里有一个实际的示例，它创建一个链表，向其添加一些节点，然后在链表中搜索和删除节点

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

struct test_struct
{
    int val;
    struct test_struct *next;
};

struct test_struct *head = NULL;
struct test_struct *curr = NULL;

struct test_struct* create_list(int val)
{
    printf("\n creating list with headnode as [%d]\n",val);
    struct test_struct *ptr = (struct test_struct*)malloc(sizeof(struct test_struct));
    if(NULL == ptr)
    {
        printf("\n Node creation failed \n");
        return NULL;
    }
    ptr->val = val;
    ptr->next = NULL;

    head = curr = ptr;
    return ptr;
}

struct test_struct* add_to_list(int val, bool add_to_end)
{
    if(NULL == head)
    {
        return (create_list(val));
    }

    if(add_to_end)
        printf("\n Adding node to end of list with value [%d]\n",val);
    else
        printf("\n Adding node to beginning of list with value [%d]\n",val);

    struct test_struct *ptr = (struct test_struct*)malloc(sizeof(struct test_struct));
    if(NULL == ptr)
    {
        printf("\n Node creation failed \n");
        return NULL;
    }
    ptr->val = val;
    ptr->next = NULL;

    if(add_to_end)
    {
        curr->next = ptr;
        curr = ptr;
    }
    else
    {
        ptr->next = head;
        head = ptr;
    }
    return ptr;
}

struct test_struct* search_in_list(int val, struct test_struct **prev)
{
    struct test_struct *ptr = head;
    struct test_struct *tmp = NULL;
    bool found = false;

    printf("\n Searching the list for value [%d] \n",val);

    while(ptr != NULL)
    {
        if(ptr->val == val)
        {
            found = true;
            break;
        }
        else
        {
            tmp = ptr;
            ptr = ptr->next;
        }
    }

    if(true == found)
    {
        if(prev)
            *prev = tmp;
        return ptr;
    }
    else
    {
        return NULL;
    }
}

int delete_from_list(int val)
{
    struct test_struct *prev = NULL;
    struct test_struct *del = NULL;

    printf("\n Deleting value [%d] from list\n",val);

    del = search_in_list(val,&prev);
    if(del == NULL)
    {
        return -1;
    }
    else
    {
        if(prev != NULL)
            prev->next = del->next;

        if(del == curr)
        {
            curr = prev;
        }
        else if(del == head)
        {
            head = del->next;
        }
    }

    free(del);
    del = NULL;

    return 0;
}

void print_list(void)
{
    struct test_struct *ptr = head;

    printf("\n -------Printing list Start------- \n");
    while(ptr != NULL)
    {
        printf("\n [%d] \n",ptr->val);
        ptr = ptr->next;
    }
    printf("\n -------Printing list End------- \n");

    return;
}

int main(void)
{
    int i = 0, ret = 0;
    struct test_struct *ptr = NULL;

    print_list();

    for(i = 5; i<10; i++)
        add_to_list(i,true);

    print_list();

    for(i = 4; i>0; i--)
        add_to_list(i,false);

    print_list();

    for(i = 1; i<10; i += 4)
    {
        ptr = search_in_list(i, NULL);
        if(NULL == ptr)
        {
            printf("\n Search [val = %d] failed, no such element found\n",i);
        }
        else
        {
            printf("\n Search passed [val = %d]\n",ptr->val);
        }

        print_list();

        ret = delete_from_list(i);
        if(ret != 0)
        {
            printf("\n delete [val = %d] failed, no such element found\n",i);
        }
        else
        {
            printf("\n delete [val = %d]  passed \n",i);
        }

        print_list();
    }

    return 0;
}

在上面的代码中：

第一个节点始终通过一个全局的“head”指针来访问。当第一个节点被删除时，该指针会被调整。
类似地，还有一个“curr”指针，它包含链表中的最后一个节点。当最后一个节点被删除时，该指针也会被调整。
每当向链表中添加一个节点时，都会检查链表是否为空，如果为空，则将其作为第一个节点添加。