链表(C)
本文最后更新于 2024年6月25日 早上
本文主要说明C的链表实现,方式来源于rt-thread,实际好像是来源于linux内核,后者没看过,不清楚咯。这种链表就很科学,通用性很高。也扔到了github仓库中,list文件夹下。
1 双向链表
1.1 与传统链表的不同
传统链表是怎么实现的呢,随便搜索”链表 C”打开个链接都基本相同,定义一个结构体,然后结构体的一个成员是一个指向此结构体的指针。如下:
1 |
|
这种方式就很死板,不同使用场景就需要定义新的结构体,实现新的链表。但接下来这种方式就把链表相关操作抽取了出来,弄成了一个可重复利用的工具。
1.2 使用
首先来看看这种链表的使用方式
定义新的结构体,只需要加入一个链表成员即可
1
2
3
4
5
6
7
8
9
10
11
12typedef struct text
{
int data;
list_t list;
int data2;
}test_t;
typedef struct text2
{
int data;
list_t list;
}test_t2;然后将三个结构体数据连接起来
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17//三个示例的节点,链表部分为0则表示未连接状态
static test_t node1={1,{0,0},1};
static test_t node2={2,{0,0},2};
static test_t node3={3,{0,0},3};
//将三个节点关联起来
void main()
{
list_t head;//新建了一个链表,关联所有加入的节点
list_init(&head);
//分别将节点加入
list_inster_after(&head,&node1.list);
list_inster_after(&head,&node2.list);
list_inster_after(&head,&node3.list);
}然后就是获取链表中节点的信息
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17void test(list_t *head)
{
test_t *object;
printf("len=%d\n",list_len(head));
list_t *temp=0;
//轮询链表,第一个节点为头指针所指所以是temp=head->next
//由于是循环链表,所以最后一个节点指向了头temp!=head
//切换到下一个节点temp=temp->next
for(temp=head->next;temp!=head;temp=temp->next)
{
//使用此宏可以由结构体的链表成员得到此节点的首地址
object = LIST_ENTER(temp,test_t,list);
printf("node:data=%d\n",object->data);
}
}
1.3 实现
1.3.1 获取结构体首地址的关键宏
1 |
|
不看看别人的代码长长见识,我自己想是肯定弄不出这么巧妙的方式的。
这里通过传入结构体链表成员指针、结构体、结构体链表成员来计算结构节点的首地址。
我们都知道,在实例一个结构体的时候,里面成员存储位置是连续的,例如下列结构体
1 |
|
如果t.a的地址是0x407970,那么t.b的地址则是0x407971,&((tt_t *)0)->b的意思则是如果t.a的地址是0,那么t.b的地址是多少呢,很显示就是1了,这样就得到了改成员相较于首地址的偏移量。
所以在实际下列结构体时,我们先知道了一个指针指向了list_t list这个成员,然后也知道了改成员相较于首地址的便宜了,那么直接相减便得到了节点的首地址咯。
1 |
|
1.3.2 初始化链表
这里函数均使用了内联的方式,也就在调用的时候是直接将函数代码复制到相应位置的。
初始化也即将头节点的首尾指针相连接。
1 |
|
1.3.3 插入新节点
1 |
|
1.3.4 删除新节点
1 |
|
1.3.5 获取链表长度
仍然传入链表头,然后轮询,直到最后一个节点指向了链表头
1 |
|