详解C语言内核中的链表与结构体

1. 链表的概念

链表是一种线性数据结构，由多个节点组成，每个节点包含了两部分内容：数据和指针。

链表有多种类型，但其中最常见的是单向链表和双向链表。在单向链表中，每个节点只包含一个指针，它指向下一个节点；在双向链表中，每个节点包含两个指针，一个指向上一个节点，一个指向下一个节点。

链表的特点是可以动态地添加或删除节点，是一种非常灵活的数据结构。它可以用来实现其他数据结构，比如栈和队列等。

2. 结构体的概念

结构体是一种用户自定义类型，可以包含多个不同类型的变量，这些变量可以是基本类型，也可以是其他结构体类型。结构体可以用来表示一个实体，比如人或汽车等。

结构体的定义语法如下：

struct <结构体名> {
    <成员1类型> <成员1名>;
    <成员2类型> <成员2名>;
    ...
};

结构体成员可以通过.运算符来访问，比如：

struct person {
    char name[20];
    int age;
};

struct person p;
strcpy(p.name, "Tom");
p.age = 25;

3. 链表和结构体的结合使用

链表和结构体可以结合使用，使得链表中每个节点都可以包含一个结构体实体。这种结构体称为链表节点的数据域，它包含了节点的数据信息。

链表节点又包含了一个指针，指向下一个节点。这个指针称为链表节点的指针域。使用指针可以方便的连接多个节点，形成链表。如下示例所示：

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

struct student {
    int id;
    char name[20];
    struct student *next; // 指向下一个节点的指针
};

int main() 
{
    // 创建三个学生结构体
    struct student *head = NULL, *p, *prev;
    int i;

    for (i = 0; i < 3; i++) {
        p = (struct student*)malloc(sizeof(struct student));
        p->id = i + 1;
        sprintf(p->name, "student%d", i + 1);
        p->next = NULL;
        // 构建链表
        if (head == NULL) {
            head = p;
        } else {
            prev->next = p;
        }
        prev = p;
    }

    // 遍历链表
    p = head;
    while (p != NULL) {
        printf("id=%d, name=%s\n", p->id, p->name);
        p = p->next;
    }

    // 释放链表
    p = head;
    while (p != NULL) {
        prev = p;
        p = p->next;
        free(prev);
    }

    return 0;
}

代码中先定义了一个学生结构体，包含了学生的ID、姓名和指向下一个节点的指针。然后创建了三个学生结构体，并链接到一起，形成链表。最后遍历链表，输出每个学生的信息。

注意到，在构建链表的过程中，需要记录上一个节点的指针prev，供下一个节点链接使用。

4. 在Linux内核中的链表

在Linux内核中，经常使用带有链表结构的数据结构。为了避免每次都重新实现链表，Linux内核提供了一个链表库，定义了基于链表的一些常见操作，包括创建、添加、删除和遍历等。

这个库定义在include/linux/list.h头文件中。在这个头文件中，定义了几个重要的结构体：

struct list_head {
    struct list_head *prev, *next;
};

struct hlist_head {
    struct hlist_node *first;
};

struct hlist_node {
    struct hlist_node *next, **pprev;
};

其中最重要的是list_head结构体，它被用作链表节点的指针域。由于链表节点需要包含在其他的结构体内，我们可以通过内嵌结构体来实现，例如：

struct student {
    int id;
    char name[20];
    struct list_head list; // 链表指针域
};

这里我们定义了一个含有链表指针的学生结构体，可以用它作为链表节点的数据域。在这个结构体中，使用了list_head结构体作为链表节点的指针域。这个list_head结构体包含了两个指针，分别指向上一个节点和下一个节点。

与普通链表类似，Linux内核中的链表可以使用一系列函数进行操作。下面展示如何创建一个包含链表节点的内核对象：

#include <linux/list.h>
#include <linux/kernel.h>
#include <linux/module.h>

struct student {
    int id;
    char name[20];
    struct list_head list;
};

struct student stu1 = {
    .id = 1,
    .name = "Tom",
    .list = LIST_HEAD_INIT(stu1.list)
};

struct student stu2 = {
    .id = 2,
    .name = "Jerry",
    .list = LIST_HEAD_INIT(stu2.list)
};

struct student stu3 = {
    .id = 3,
    .name = "Mike",
    .list = LIST_HEAD_INIT(stu3.list)
};

static int __init hello_init(void)
{
    printk("Hello, world!\n");

    // 链接学生对象到链表
    INIT_LIST_HEAD(&stu1.list);
    list_add_tail(&stu2.list, &stu1.list);
    list_add_tail(&stu3.list, &stu1.list);

    // 遍历链表
    struct list_head *pos;
    struct student *stu;

    list_for_each(pos, &stu1.list) {
        stu = list_entry(pos, struct student, list);
        printk("id=%d, name=%s\n", stu->id, stu->name);
    }

    return 0;
}

static void __exit hello_exit(void)
{
    printk("Goodbye, world!\n");
}

module_init(hello_init);
module_exit(hello_exit);

MODULE_LICENSE("GPL");

本示例中定义了三个学生对象，然后将它们通过链表链接起来，并遍历整个链表，输出每个学生的信息。

在本示例中，INIT_LIST_HEAD和list_add_tail函数用于初始化并添加链表元素，list_for_each和list_entry函数用于遍历链表。

总结

通过本文，我们详细讲解了在C语言中使用链表和结构体的基础知识，并介绍了Linux内核中的链表库，方便编写高可靠性的内核代码。本文中的示例可以帮助您更深入了解链表和结构体的使用方法，供读者参考。