当前位置: article > 正文

＜C语言数据结构三＞C语言带你玩转“单向链表”_链表实现c语言为什么要用list来封装node

作者：小蓝xlanll | 2024-05-20 15:43:10

踩

链表实现c语言为什么要用list来封装node

一、链表的基础知识

链表是C语言中比较常用的一种数据结构，相对与上几篇文章的队列结构来说，链表是在一种物理存储单元上非连续、非顺序的存储结构。链表中的每个节点都是通过链表中的指针链接次序实现的；一般来说每个节点都会包含以下两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
链表又会分成很多个类型：单线链表，单向循环链表，双向链表，双向循环链表等；
这篇文章我们主要聊聊单向链表，单向链表又分为以下两种类型：

无头节点链表：无头节点链表表示的是头节点中是没有数据域的，只包含了指针域
有头节点链表：有头节点链表表示的是头节点中既有指针域也有数据域

二、单向链表的常用接口

链表的创建
链表的插入：头插和尾插
链表节点的删除
链表的销毁
链表的遍历
…

三、单向链表的实现

1、无头节点的单向链表

链表的数据定义

typedef struct {
    uint8_t id;
} USER_DATA_T;

typedef struct list{
    struct list *next;
    USER_DATA_T data;
} LIST_T;

LIST_T *head_list = NULL; //链表头节点指针
1
2
3
4
5
6
7
8
9
10

链表的创建

// 创建链表
int list_creat(void)
{
    if (NULL == head_list) {
        head_list = (LIST_T *)malloc(sizeof(LIST_T));
        if (NULL == head_list) {
            return -1;
        }
        head_list->next = NULL;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12

链表的插入：头插和尾插

//链表的头插，在头节点后面插入数据
int list_inset_head(USER_DATA_T *data)
{
    if (NULL == head_list) {
        if (list_creat() != 0) {
            return -1;
        }
    }

    LIST_T *p_node = (LIST_T *)malloc(sizeof(LIST_T));
    memset(p_node, 0, sizeof(LIST_T));
    memcpy(&p_node->data, data, sizeof(USER_DATA_T));
    p_node->next = head_list->next;
    head_list->next = (struct list *)p_node;
    return 0;
}

//链表的尾插，在最后节点插入数据
int list_inset_tail(USER_DATA_T *data)
{
    if (NULL == head_list) {
        if (list_creat() != 0) {
            return -1;
        }
    }
    //创建节点数据
    LIST_T *p_node = (LIST_T *)malloc(sizeof(LIST_T));
    memset(p_node, 0, sizeof(LIST_T));
    memcpy(&p_node->data, data, sizeof(USER_DATA_T));
    p_node->next = NULL;

    LIST_T *p_list = head_list;
    while (p_list) {
        if (p_list->next) {
            p_list = (LIST_T *)p_list->next;
            continue;
        }
        p_list->next = (struct list *)p_node;
        return 0;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

链表的删除：根据数据内容或者节点序号

// 根据数据内容删除节点
void list_node_del_by_data(USER_DATA_T *data)
{
    if (NULL == head_list) {
        return;
    }

    LIST_T *p_list = (LIST_T *)head_list;
    LIST_T *q = NULL;
    while (p_list->next) {
        if (0 == memcmp(data, &p_list->next->data, sizeof(USER_DATA_T))) {
            q = (LIST_T *)p_list->next;
            p_list->next = q->next;
            free(q);
            q = NULL;
        }
        p_list = (LIST_T *)p_list->next;
    }
}

// 根据节点编号删除节点：头节点为0，数据节点从1开始
void list_node_del_by_index(uint8_t index)
{
    if ((NULL == head_list) || (0 == index)) {
        return;
    }
    uint8_t cnt = 1;
    LIST_T *q = NULL;
    LIST_T *p_list = (LIST_T *)head_list;
    while (p_list) {
        if (cnt == index) {
            q = p_list->next;
            p_list->next = q->next;
            free(q);
            q = NULL;
            return;
        }
        p_list = (LIST_T *)p_list->next;
        cnt++;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

链表的销毁

//链表销毁
int list_destory(void)
{
    if (NULL == head_list) {
        return -1;
    }

    LIST_T *p_list = NULL, *q = NULL;
    for (p_list = head_list->next; p_list != NULL; p_list = q) {
        q = p_list->next;
        free(p_list);
    }
    free(head_list);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

链表的遍历

//遍历链表
void list_traverse(void)
{
    if ((NULL == head_list) || (NULL == head_list->next)) {
        return;
    }

    LIST_T *p_node = (LIST_T *)head_list->next;
    while (p_node) {
        printf("node data:%d\r\n", p_node->data);
        p_node = (LIST_T *)p_node->next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

2、有头节点的单向链表

链表的创建

// 创建链表
int list_creat(USER_DATA_T *data)
{
    if (NULL == head_list) {
        head_list = (LIST_T *)malloc(sizeof(LIST_T));
        if (NULL == head_list) {
            return -1;
        }

        memcpy(&head_list->data, data, sizeof(USER_DATA_T));
        head_list->next = NULL;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

链表的插入：头插和尾插

//链表的头插，在头节点前面插入数据
int list_inset_head(USER_DATA_T *data)
{
    if (NULL == head_list) {
        return -1;
    }
    
    LIST_T *p_node = (LIST_T *)malloc(sizeof(LIST_T));
    memset(p_node, 0, sizeof(LIST_T));
    memcpy(&p_node->data, data, sizeof(USER_DATA_T));

    p_node->next = head_list;
    head_list = p_node;
    return 0;
}

//链表的尾插，在最后节点插入数据
int list_inset_tail(USER_DATA_T *data)
{
    if (NULL == head_list) {
        return -1;
    }

    //创建节点数据
    LIST_T *p_node = (LIST_T *)malloc(sizeof(LIST_T));
    memset(p_node, 0, sizeof(LIST_T));
    memcpy(&p_node->data, data, sizeof(USER_DATA_T));
    p_node->next = NULL;

    LIST_T *p_list = head_list;
    while (p_list) {
        if (p_list->next) {
            p_list = (LIST_T *)p_list->next;
            continue;
        }
        p_list->next = (struct list *)p_node;
        return 0;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

链表节点的删除：根据数据或者节点序号删除

// 根据数据内容删除节点
void list_node_del_by_data(USER_DATA_T *data)
{
    if (NULL == head_list) {
        return;
    }

    LIST_T *p_list = (LIST_T *)head_list;
    LIST_T *q = NULL;
    while (p_list) {
        if (0 == memcmp(data, &p_list->data, sizeof(USER_DATA_T))) {
            if (p_list == head_list) {
                q = head_list;
                head_list = head_list->next;
                free(q);
                q = NULL;
                p_list = head_list;
            } else {
                q->next = p_list->next;
                free(p_list);
                p_list = NULL;
                q = (LIST_T *)q->next;
            }
            continue;
        }
        q = p_list;
        p_list = (LIST_T *)p_list->next;
    }
}

// 根据节点编号删除节点：头节点为0
void list_node_del_by_index(uint8_t index)
{
    if (NULL == head_list) {
        return;
    }

    uint8_t cnt = 0;
    LIST_T *q = NULL;
    LIST_T *p_list = (LIST_T *)head_list;

    while (p_list) {
        if (cnt == index) {
            if (0 == index) {
                q = head_list;
                head_list = head_list->next;
                free(q);
                q = NULL;
            } else {
                q->next = p_list->next;
                free(p_list);
                p_list = NULL;
            }
            return;
        }
        q = p_list;
        p_list = (LIST_T *)p_list->next;
        cnt++;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

链表节点的查找

// 根据数据内容查找节点
LIST_T *list_node_find(USER_DATA_T *data)
{
    if (NULL == head_list) {
        return;
    }

    LIST_T *p_list = (LIST_T *)head_list;
    while (p_list) {
        if (0 == memcmp(data, &p_list->data, sizeof(USER_DATA_T))) {
            return p_list;
        }
        p_list = (LIST_T *)p_list->next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

3、demo程序

demo测试代码

int main(void)
{
    USER_DATA_T data = {0};
    list_creat();
    data.id = 3;
    list_inset_head(&data);
    data.id = 2;
    list_inset_head(&data);
    data.id = 4;
    list_inset_tail(&data);
    data.id = 5;
    list_inset_tail(&data);
    data.id = 1;
    list_inset_head(&data);
    data.id = 3;
    list_inset_head(&data);
    data.id = 3;
    list_node_del_by_data(&data);
    list_node_del_by_index(3);
    list_traverse();
    list_destory();
    list_traverse();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小蓝xlanll/article/detail/598276