C基础 之 list 库奥义

C基础 之 list 库奥义

前言 - 关于 list 思考

　　list 是最基础的数据结构也是数据结构的基础. 高级 C 代码纽带也是 list.

扯一点, 当你走进了 C 的殿堂, 那么你和 list 增删改查那就是一辈子丫 ~ 这里不妨分享一下作者对于 list 认知经历的几个阶段 (比心)
i) 原生链表

struct list {struct list * next;...
}

链表结构和业务数据绑定在一起. 朴实无华丽, 重剑可破军

ii) 万能链表

struct list {struct list * next;void * node;
}

所有业务结点抽象为 void * 万能指针. 瑕疵是存在 sizeof (void *) 内存浪费.

像一杯甜酒喝起来还挺爽, 只是热量有点高.
iii) 内核链表

struct $list {struct $list * next;
};#define $LIST_HEAD struct $list $node

$LIST_HEAD 宏放在需要实现的链式结构的头位置. 有点继承味道, 例如下面这样

struct list {$LIST_HEAD;...
}

住用利用隐含条件 &list = &(list.$node) => list->next = &(list.$node)->next.

链表结点首地址和业务结点首地址值相等. 瞟内核的时候看挺常见. 四两拨千斤 ~ iv) 注册链表

struct $list {struct $list * next;
};#define $LIST struct $list $node;typedef struct {struct $list * root; // 存储链表的头节点
icmp_f fadd; // 链表中插入数据执行的方法icmp_f fget; // 链表中查找数据执行的方法node_f fdie; // 链表中删除数据执行的方法
} * list_t;//
// list_next - 获取结点n的下一个结点.
// n        : 当前结点
//
#define list_next(n) ((void *)((struct $list *)(n))->next)//
// list_create - 构建 list 对象
// fadd : 插入数据方法
// fget : 获取数据方法
// return : 创建好的链表对象
//
#define list_create(fadd, fget) 
list_create_((icmp_f)fadd, (icmp_f)fget)inline list_t list_create_(icmp_f fadd, icmp_f fget) {list_t list = malloc(sizeof *list);list->root = NULL;list->fadd = fadd;list->fget = fget;list->fdie = NULL;return list;
}

注册行为定义如下

//
// icmp_f - 比较行为的类型
// : int add_cmp(const void * now, const void * node)
//
typedef int (* icmp_f)();//
// node_f - 销毁当前对象节点
// : void list_die(void * node);
//
typedef void (* node_f)(void * node);

当时产生这个想法是太迷恋基于函数注册的方式. 希望一次注册终身受用.

但在实战中发现, C 很多时候只用到局部部分. 功能越强大, 考虑的越全面, 代码写起来就越难受. 等同于衣服太多, 搬家就会很麻烦. 领证还要房子车子票子, 这么麻烦, 那结个 pi 呀. 必须要整改 :)
v) 取舍链表

struct list {struct list * next;...
}or//
// list.h 通用的单链表库
// void * list = NULL;
//
struct $list {struct $list * next;
};#define $LIST struct $list $node;

简单业务上使用第一个原生链表, 在特定场合(顺序有要求)使用内核链表.

成熟在于取舍, 渣往往是抉择的时候不定, 遇到的时候不克制. 有感情那 OK, 有票子 那 OK, else 自己玩毛 ~
说了这么多没用的, 希望读者能够理解作者关于链表结构的思考心路. 本文后续重点就是讲解 $LIST ~

正文 - 接口设计

　　 list 首先从总体接口设计感受此中气息

//
// list.h 通用的单链表库
// void * list = NULL;
// 
struct $list {struct $list * next;
};#define $LIST struct $list $node;//
// list_next - 获取结点n的下一个结点.
// n        : 当前结点
//
#define list_next(n) ((void *)((struct $list *)(n))->next)//
// list_delete - 链表数据销毁操作
// list     : 基础的链表结构
// pist     : 指向基础的链表结构
// fdie     : 链表中删除数据执行的方法
// return   : void
//
#define list_delete(list, fdie)                                         
list_delete_((void **)&(list), (node_f)(fdie))
extern void list_delete_(void ** pist, node_f fdie);//
// list_get - 匹配得到链表中指定值
// list     : 基础的链表结构
// fget     : 链表中查找数据执行的方法
// left     : 待查找的结点内容 
// return   : 查找到的节点, NULL 表示没有查到
//
#define list_get(list, fget, left)                                      
list_get_((list), (icmp_f)(fget), (const void *)(intptr_t)(left))
extern void * list_get_(void * list, icmp_f fget, const void * left);//
// list_pop - 匹配弹出链表中指定值
// list     : 基础的链表结构
// pist     : 指向基础的链表结构
// fget     : 链表中查找数据执行的方法
// left     : 待查找的结点内容 
// return   : 查找到的节点, NULL 表示没有查到 
//
#define list_pop(list, fget, left)                                      
list_pop_((void **)&(list), (icmp_f)(fget), (const void *)(intptr_t)(left))
extern void * list_pop_(void ** pist, icmp_f fget, const void * left);//
// list_add - 链表中添加数据, 从小到大 fadd(left, ) <= 0
// list     : 基础的链表结构
// pist     : 指向基础的链表结构
// fadd     : 插入数据方法
// left     : 待插入的链表结点
// return   : void
//
#define list_add(list, fadd, left)                                      
list_add_((void **)&(list), (icmp_f)(fadd), (void *)(intptr_t)(left))
extern void list_add_(void ** pist, icmp_f fadd, void * left);

大量用到一个宏技巧

// list     : 基础的链表结构
// pist     : 指向基础的链表结构

#define list_delete(list, fdie)                                         
list_delete_((void **)&(list), (node_f)(fdie))

通过宏将一维指针转成二维指针来使用. 缺点是指针不可复制. 或者复制后不能再使用上一个指针.

(等同于破坏型智能指针)优势在于潇洒, 宁可 BUG 不断, 也要帅气到底 ~

 

接口实现部分

开头从 delete 讲起. C 可以没有 create(alloc) , 但一定要有 delete(free). 来不及销毁证据那就不用出去嗨了.

//
// list_delete - 链表数据销毁操作
// pist     : 指向基础的链表结构
// fdie     : 链表中删除数据执行的方法
// return   : void
//
void 
list_delete_(void ** pist, node_f fdie) {if (pist && fdie) {// 详细处理链表数据变化struct $list * head = *pist;while (head) {struct $list * next = head->next;fdie(head);head = next;}*pist = NULL;}
}

核心招式在于 *pist = NULL; 希望置空. (虽然没有卵用, 因为指针可复制, 存在多个引用)

如果场景不允许复制的话, 可以一用. 

 

对于后面几个函数核心设计围绕头结点处理上, 如果处理的对象是头结点, 需要重新设置.

//
// list_get - 匹配得到链表中指定值
// list     : 基础的链表结构
// fget     : 链表中查找数据执行的方法
// left     : 待查找的结点内容 
// return   : 查找到的节点, NULL 表示没有查到
//
void * 
list_get_(void * list, icmp_f fget, const void * left) {if (fget) {struct $list * head = list;while (head) {if (fget(left, head) == 0)return head;head = head->next;}}return NULL;
}//
// list_pop - 匹配弹出链表中指定值
// pist     : 指向基础的链表结构
// fget     : 链表中查找数据执行的方法
// left     : 待查找的结点内容 
// return   : 查找到的节点, NULL 表示没有查到 
//
void * 
list_pop_(void ** pist, icmp_f fget, const void * left) {struct $list * head, * next;if (!pist || fget)return NULL;// 看是否是头节点head = *pist;if (fget(left, head) == 0) {*pist = head->next;return head;}// 不是头节点挨个处理while (!!(next = head->next)) {if (fget(left, next) == 0) {head->next = next->next;return next;}head = next;}return NULL;
}//
// list_next - 获取结点n的下一个结点.
// n        : 当前结点
//
#undef  list_next
#define list_next(n) ((struct $list *)(n))->next//
// list_add - 链表中添加数据, 从小到大 fadd(left, ) <= 0
// pist     : 指向基础的链表结构
// fadd     : 插入数据方法
// left     : 待插入的链表结点
// return   : void
//
void 
list_add_(void ** pist, icmp_f fadd, void * left) {struct $list * head;if (!pist || !fadd || !left)return;// 看是否是头结点head = *pist;if (!head || fadd(left, head) <= 0) {list_next(left) = head;*pist = left;return;}// 不是头节点, 挨个比对while (head->next) {if (fadd(left, head->next) <= 0)break;head = head->next;}// 添加最终的连接关系list_next(left) = head->next;head->next = left;
}

很多代码强烈推荐自己多打几遍. 这是实践派绝招, 可以啥都不懂, 但会写(有思考更好)应该也是及格吧. 

其中 list_next 宏设计思路也很洒脱. 对外暴露是读操作, 对内是写操作.

 

这里不妨赠送个测试接口

//
// node_f - 销毁当前对象节点
//  : void list_die(void * node); 
//
typedef void (* node_f)(void * node);//
// list_each - 链表循环处理函数, 仅仅测试而已
// list     : 基础的链表结构
// feach    : 处理每个结点行为函数
// return   : void
//
#define list_each(list, feach)                                          
list_each_((list), (node_f)(feach))
extern void list_each_(void * list, node_f feach);void 
list_each_(void * list, node_f feach) {    if (list && feach) {struct $list * head = list;while (head) {struct $list * next = head->next;feach(head);head = next;}}
}

 

list 使用 demo 可以参照这下面的写法

#define INT_NAME (64)struct peoples {$LISTdouble age;char name[INT_NAME + 1];
};// peoples_add : 默认年龄从小到大排序, 并且获取
inline static int peoples_add(struct peoples * left, struct peoples * node) {return (int)(left->age - node->age);
}// peoples_each : 单纯的打印接口信息
inline static void peoples_each(struct peoples * node) {printf("age = %9.6lf, name = %sn", node->age, node->name);
}//
// list test demo
//
void list_test(void) {void * peops = NULL;// 这里添加数据struct peoples peop[5];for (int i = 0; i < LEN(peop); ++i) {peop[i].age = rand() % 100 + rand() * 1.0 / rand();snprintf(peop[i].name, LEN(peop[i].name), "peop_%d", i);list_add(peops, peoples_add, peop + i);}// 这里打印数据
    list_each(peops, peoples_each);
}

到这关于 list 了解的一切都传入糖果中 : ) 更好例子, 基于 list 设计了重复定时器例子

　　timer - .c

(扯一点, 定时器有很多实现思路. 采用 list, heap, double list, array + list 都有, 看应用领域.) 能够写好 list,

算数据结构结业了吧. 想起朴实的大学数学老师说, 走出学校的时候还记得数学分析, 那数学系就算学合格了.

现在想起来有些心痛, 真实在.  对于大家都懂的需要多练习,  对于都不明白的需要多调研.

顺势而为, 耕田日下.

 

后记 - 有序展望

　　错误和成长是难免的, 欢迎指正 ~ :-

小雨中的回忆 - =119664

 

:- >

 

转载于:.html