本文介绍C语言中,如何无中生有,给链表创造出一个不占空间的伪头节点
# 基本定义
设我们有一个不带空头节点的链表,其节点定义为
//typedef int dtype;
typedef struct node{
dtype data;
struct node *next;
} node;
链表定义为
typedef struct linklist{
node *head;
//...
} linklist;
# 空头节点
# 常驻的空头节点
设现在有一个链表linklist *L
,那么它的头节点的指针为L->head
。如果我们要写一个对链表进行修改的功能,那么L->head
本身可能也会被修改。
如果给链表本身,引入空头节点,可以使得每个有效元素都有前置元素,方便更新链表。但是此种方法有两个缺点:
- 头节点需要一个空的
node.data
域,当此项体积比较庞大的时候,是对空间的浪费 - 如果只需要对链表进行读取而不需要修改,那么需要额外的代码提取真正的头节点
# 临时空头节点
解决第二个问题的可行方案是,让空头节点不常驻链表。每次仅当需要修改链表的时候,临时产生一个空头节点。此方案同时部分解决了第一个问题,但是临时修改时,依然存在不必要的空间浪费。
由于我们并不对空头节点pred
的pred->next
以外的域进行更改,本质上pred->data
域是纯粹的空间浪费。
# 临时伪空头节点
我们注意到:
只需要存在
next
域的存储空间,就可以根据next
域的地址,推算出一个不存在的假的结构体地址。
以下struct_addr_from_elem
宏,便可以根据元素的地址推算出结构体的地址
#define struct_addr_from_elem(struct_, elem, obj) (void*)&(obj) - offsetof((struct_), (elem))
那么我们可以由此轻松产生空头节点指针pred
:
linklist *L;
node *prev = struct_addr_from_elem(node, next, L->head);
# 实例
对不带头节点的链表插入元素,并使得链表元素保持升序。
node* init_node(dtype data, node* next);
void ascend_insert(linklist *L, dtype data){
//初始化空头节点指针和头指针
node *prev = struct_addr_from_elem(node, next, L->head), *p=L->head;
//找到插入点
while(p && (data > p->data)){
prev = p;
p = p->next;
}
//插入
prev->next = init_node(data, p);
}
Comments
comments powered by Disqus