Linux内核链表之共享双链表

说明

共享双链表意义在于,可以用一套函数维护不同数据类型的双链表

准备

定义双链表

1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
#include <string>

using namespace std;

//此处并不包含数据域,仅有指针域用于连接结点
typedef struct _DbLinkList
{
struct _DbLinkList *next;
struct _DbLinkList *prev;
}DbLinkList;

定义结构体

1
2
3
4
5
6
7
8
9
10
11
12
//定义数据类型,并挂载双链表的指针
struct num
{
int data;
DbLinkList node; //此处不用指针,以保证在为该结构体分配内存时同时为双链表分配
};

struct str
{
string data;
DbLinkList node; //此处不用指针,以保证在为该结构体分配内存时同时为双链表分配
};

操作

初始化

1
2
3
4
5
6
7
//因为在保存数据的结构体中未用双链表的指针,所以此处L使用引用而非引用类型的指针
bool initList(DbLinkList &L)
{
L.next = NULL;
L.prev = NULL;
return true;
}

尾插法

1
2
3
4
5
6
7
8
9
10
11
12
bool insertBack(DbLinkList &L, DbLinkList &node)
{
DbLinkList *p = &L;

while(p->next) p = p->next;

node.next = NULL;
p->next = &node;
node.prev = p;

return true;
}

实际操作

对于struct num

main函数

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
int main()
{

num *N = new num;
N->data = -1;

initList(N->node);

//尾插法
num *n = new num;
n->data = 2;
insertBack(N->node, n->node);

//用链表访问结点的数据
DbLinkList *p = &(N->node);
while(p)
{
//获取在结构体中node距离结构体顶点的距离
int offset = offsetof(num, node);
/*
* data地址 = 结构体底地址 - node距离结构体顶点的距离
* 但指针不能直接加减,所以要先转化为size_t类型,得到结果后再转为指针类型
*/
num *tmp = (num *)((size_t)p - offset);
cout << "NUM:" << tmp->data << endl;
p = p->next;
}

return 0;
}

输出结果

1
2
NUM:-1
NUM:2

对于struct str

同理

main函数

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
int main()
{
str *S = new str;
S->data = "hello,world";

initList(S->node);

//尾插法
str *s = new str;
s->data = "你好,世界";
insertBack(S->node, s->node);

//用链表访问结点的数据
DbLinkList *p = &(S->node);
while(p)
{
//获取在结构体中node距离结构体顶点的距离
int offset = offsetof(str, node);
/*
* data地址 = 结构体底地址 - node距离结构体顶点的距离
* 但指针不能直接加减,所以要先转化为size_t类型,得到结果后再转为指针类型
*/
str *tmp = (str *)((size_t)p - offset);
cout << "STR:" << tmp->data << endl;
p = p->next;
}

return 0;
}

输出结果

1
2
STR:hello,world
STR:你好,世界

(注意:本文没有做双链表的销毁操作,虽然程序可以正常运行但这样做是不可取的)

思考

能不能将不同类型的结构体都放在一个双链表上?

如果能该怎么读取数据?

作者

CairBin

发布于

2021-10-05

更新于

2021-10-05

许可协议

评论