本文介绍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本身可能也会被修改。

如果给链表本身,引入空头节点,可以使得每个有效元素都有前置元素,方便更新链表。但是此种方法有两个缺点:

  1. 头节点需要一个空的node.data域,当此项体积比较庞大的时候,是对空间的浪费
  2. 如果只需要对链表进行读取而不需要修改,那么需要额外的代码提取真正的头节点

# 临时空头节点

解决第二个问题的可行方案是,让空头节点不常驻链表。每次仅当需要修改链表的时候,临时产生一个空头节点。此方案同时部分解决了第一个问题,但是临时修改时,依然存在不必要的空间浪费。

由于我们并不对空头节点predpred->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