您好,欢迎访问代理记账网站
移动应用 微信公众号 联系我们

咨询热线 -

电话 15988168888

联系客服
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

TAILQ链表学习笔记

TAILQ 链表前前后后也看了不少次了,把学习过程中一些点记录一下。

1. 数据结构

#define TAILQ_ENTRY(type)
struct\
{\
    struct type *tqe_next;\
    struct type **tqe_prev;\
}

TAILQ 链表使用一个叫 TAILQ_ENTRY 的结构,其包含两个指针:
1)指向下一个结点的指针 tqe_next;
2)指向上一个结点的 tqe_next 指针地址的二级指针 tqe_prev;
即:
node2->tqe_prev = &(node1->tqe_next);

所以有:
*(node2->tqe_prev) = *&(node1->tqe_next) = node1->tqe_next = node2

定义一个数据结点,如:

struct node
{
    int data;
    TAILQ_ENTRY(node) link;
}

展开为

struct node
{
    int data;
    struct link
    {
        struct node *tqe_next;
        struct node **tqe_prev;
    }
}

TAILQ 链表没有头结点,其将头结点抽象为一个包含两个指针的数据结构 TAILQ_HEAD

#define TAILQ_HEAD(name, type)\
struct name\
{\
    struct type *tqh_first;\
    struct type **tqh_last;\
}

1)tqh_first 指向链表第一个结点;
2)tqh_last 指向链表最后一个结点的 tqe_next;

2. 链表初始化

#define TAILQ_INIT(head)\
{\
    (head)->tqh_first = NULL;\
    (head)->tqh_last = &(head)->tqh_first;\
}

使用 TAILQ_INIT 对链表进行初始化,简单的两步:
1)tqh_first 指向 NULL;
2)tqh_last 指向 tqh_first;
TAILQ_INIT

3. 插入结点

3.1 头插入

3.1.1 插入第一个结点

#define	TAILQ_INSERT_HEAD(head, elm, field)\
do {\
    if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL)\
        TAILQ_FIRST((head))->field.tqe_prev = &TAILQ_NEXT((elm), field);\
	else\
        (head)->tqh_last = &TAILQ_NEXT((elm), field);\
    TAILQ_FIRST((head)) = (elm);\
    (elm)->field.tqe_prev = &TAILQ_FIRST((head));\
} while (0)

在这里插入图片描述

代码图示
TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))在这里插入图片描述
是第一个结点,走else分支
(head)->tqh_last = &TAILQ_NEXT((elm), field);在这里插入图片描述
TAILQ_FIRST((head)) = (elm);在这里插入图片描述
(elm)->field.tqe_prev = &TAILQ_FIRST((head))在这里插入图片描述

3.1.2 插入非第一个结点

#define	TAILQ_INSERT_HEAD(head, elm, field)\
do {\
    if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL)\
        TAILQ_FIRST((head))->field.tqe_prev = &TAILQ_NEXT((elm), field);\
	else\
        (head)->tqh_last = &TAILQ_NEXT((elm), field);\
    TAILQ_FIRST((head)) = (elm);\
    (elm)->field.tqe_prev = &TAILQ_FIRST((head));\
} while (0)

在这里插入图片描述

代码图示
TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))在这里插入图片描述
不是第一个结点,走if分支
TAILQ_FIRST((head))->field.tqe_prev = &TAILQ_NEXT((elm), field);在这里插入图片描述
TAILQ_FIRST((head)) = (elm);在这里插入图片描述
(elm)->field.tqe_prev = &TAILQ_FIRST((head));在这里插入图片描述

3.2 尾插入

在这里插入图片描述

#define	TAILQ_INSERT_TAIL(head, elm, field)\
do {\
	TAILQ_NEXT((elm), field) = NULL;\
	(elm)->field.tqe_prev = (head)->tqh_last;\
	*(head)->tqh_last = (elm);\
	(head)->tqh_last = &TAILQ_NEXT((elm), field);\
} while (0)
代码图示
TAILQ_NEXT((elm), field) = NULL;在这里插入图片描述
(elm)->field.tqe_prev = (head)->tqh_last;在这里插入图片描述
*(head)->tqh_last = (elm);在这里插入图片描述
(head)->tqh_last = &TAILQ_NEXT((elm), field);在这里插入图片描述

4. 删除结点

在这里插入图片描述

4.1 删除最后一个结点

#define	TAILQ_REMOVE(head, elm, field)\
do {\
	if ((TAILQ_NEXT((elm), field)) != NULL)\
		TAILQ_NEXT((elm), field)->field.tqe_prev = (elm)->field.tqe_prev;\
	else								\
		(head)->tqh_last = (elm)->field.tqe_prev;\
	*(elm)->field.tqe_prev = TAILQ_NEXT((elm), field);\
} while (0)
代码图示
if ((TAILQ_NEXT((elm), field)) != NULL)删除最后一个结点,走else分支
(head)->tqh_last = (elm)->field.tqe_prev;在这里插入图片描述
*(elm)->field.tqe_prev = TAILQ_NEXT((elm), field);在这里插入图片描述
移除结点并回收资源在这里插入图片描述

4.2 删除非最后一个结点

代码图示
if ((TAILQ_NEXT((elm), field)) != NULL)删除非最后一个结点,走if分支
TAILQ_NEXT((elm), field)->field.tqe_prev = (elm)->field.tqe_prev;在这里插入图片描述
*(elm)->field.tqe_prev = TAILQ_NEXT((elm), field);在这里插入图片描述
移除结点并回收资源在这里插入图片描述

5. TAILQ链表特点

5.1 二级指针

在这里插入图片描述
TAILQ 使用了二级指针,如果将其替换为一级指针,那么上图将是以下形式:
在这里插入图片描述
由于 TAILQ 没有设置头结点,因此第一个结点的 tqe_prev 会指向 NULL,删除结点时需要区分是否是第一个结点。

5.2 反向查找

tqe_prev 指针指向的是前一个结点的 tqe_next,那么 TAILQ 反向查找是怎么做的?
在这里插入图片描述
从 node 3 开始,为了取到 node 2 ,需要拿到 node 1 的 tqe_next。但是从 node 3 只能拿到 node 2 的 tqe_next,想拿到 node 1 的 tqe_next,需要先拿到 node 2 的 tqe_prev。

获取 node 2 的 tqe_prev 的方法:

  1. node2->field.tqe_prev
  2. &(node2->field.tqe_next) + sizeof(node2->field.tqe_next),即 node3->field.prev + sizeof(node3->field.tqe_next)

第一种需要先知道 node 2,pass
第二种需要做地址运算,会带来额外的系统开销

下面看看 TAILQ 的操作

#define	TAILQ_PREV(elm, headname, field)\
	(*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))

elm 是当前结点,headname 是链表数据结构名,field 是链表入口,这里 TAILQ 用了一个巧妙的技巧:
将 (elm)->field.tqe_prev) 做了一次类型转换,转为了 (struct headname *),即 TAILQ_HEAD 数据结构,由于 TAILQ_HEAD 和 TAILQ_ENTRY 的数据结构相同,都包含一个一级指针和一个二级指针。因此转换后取 tqh_last 就偏移了一个指针的地址,取到了 node2 的 tqe_prev,也就拿到了 node1 的 tqe_next,再 * 取值即获得了 node2 。

之所以使用 TAILQ_HEAD 做类型转换,是因为 TAILQ_ENTRY 定义在结点内部且不一定有 struct name,为了代码兼容性更好,因此使用有 struct name 的 TAILQ_HEAD。

TAILQ 的反向查找效率较低,为了尽可能的降低开销,可以在结构体设计上做点手法:

struct node
{
    TAILQ_ENTRY(node) link;
    int data;
}

struct node
{
    struct link
    {
        struct node *tqe_next;
        struct node **tqe_prev;
    };
    int data;
}

将 TAILQ_ENTRY 作为结点结构体的首个成员,那么 tqe_next 指针的地址就代表结点的内存首地址,对地址做一次类型转换通过 data 成员即可获取到数据。

5.3 ,运算符

TAILQ 提供的安全遍历 TAILQ_FOREACH_SAFE 中使用了较少见的逗号运算符:

(var) && ((tvar) = ((var)->field.tqe_next), 1);\ 

这里是提前将下一个结点取出保存到了 tvar 中,如果下一个结点为 NULL,那么下面的语句就为假,当前结点就无法处理了。

(var) && ((tvar) = ((var)->field.tqe_next));\

加入逗号运算符后,表达式的返回值就是逗号后面的值,即 1,表达式为真,那么即取到了下一个结点,同时保证当前结点的处理:

((tvar) = ((var)->field.tqe_next), 1)

分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进