经典计算机教材《算法导论》第十章数据结构部分，就有提及链表。其中的伪代码实现，确实精秒。于是我决定讲其里面的伪代码转录成 C 语言，结合上一篇文章《如何设计一道容器 1》中设计的容器接口，让其成为真正能使用的容器。
01 链表的设计
算法导论中的链表是一个双向循环链表，每个节点都有向前向后的指针，大概长这个样子：
因为我要把它套入到容器中，容器是要实现标准的迭代式的访问，是要实现例如 for 循环之类的。所以这里要在上述的循环链表中还加一个边界 tail。修改如下：
当然那个 tail 与 head 物理上同一个内存对象，只不过逻辑上看上是两个节点。
02 代码实现
链表，一般分为两部分，装载数据的数据节点和链表的数据结构。
typedef struct _list_node list_node_t;struct _list_node{ // 前一个节点的指针 list_node_t* prev; // 后一个节点的指针 list_node_t* next; // 数据内存，这里并不是值只有 1 个字节。 // 这个节点大小需要根据存入的数据大小来申请内存。 T w[1];};
复制代码
typedef struct _list { // 这里可以看作继承 container 这个基类 container_t container; list_node_t _sentinel; int _size; } list_t;
复制代码
static iterator_t __list_first (container_t* plist){ return __iterator(list_first(plist)->w, plist);}
复制代码
static iterator_t __list_last (container_t* plist){ return __iterator(list_last(plist)->w, plist);}
复制代码
static int __list_move(iterator_t* it, int step){ list_node_t* pnode = container_of(it->reference, list_node_t, w); for (int next = step; next; next = step > 0? next - 1: next + 1) { if (step > 0) pnode = pnode->next; else if (step < 0) pnode = pnode->prev; } it->reference = pnode->w; return 0;}
复制代码
这里要特别说明，iterator_t *it 中 refrence 字段是指向节点的数据部分，但是在迭代器移动过程中，需要获取 next 与 prev 的指针。但这就需要知道整个 list_node 的地址，于是这里必要用一种 container_of 的技术，从结构体的某个字段的地址，推算出结构体的首地址：
#define offset_of(TYPE, MEMBER) \ ((char*)&(((TYPE *)0)->MEMBER)) #define container_of(ptr, TYPE, MEMBER) \({ \ TYPE* type_ptr = (((char*)ptr) - offset_of(TYPE, MEMBER)); \ type_ptr; \})
复制代码
container_of 计算过程如下:
static void* __list_insert(container_t* container, iterator_t pos，...){ T data[T_size(container->type_class)]; //从不定参数中读取要插入的数据。 va_list valist; va_start(valist, pos); // 此处调用数据对象对应的 不定参数转换函数。 // 把不定参数的值转换到 data 上。 T_vargs(container)(valist, data); va_end(valist); list_node_t* insert = container_of(pos.reference, list_node_t, w); // 节点的大小根据容器中数据对象的大小申请内存 list_node_t* pnew \ = allocate(container->mem_pool, sizeof(list_node_t) \ + T_size(container->type_clazz)); // 赋值
T_setup(container->type_clazz)(pnew->w, data, 0); // 插入 pnew->prev = insert->prev; pnew->next = insert;
insert->prev->next = pnew; insert->prev = pnew;
list_t *plist = container; plist->_size++; return 0;}
复制代码
为什么插入的接口需要不定参数？那是因为，容器是为多种数据服务的。如果接口写死了一种数据类型的插入，那么就不能做到数据和容器分离。耦合度就了。
使用了不定参数作为接口后，容器可以插入 int 或者 float 类型。以前老旧办法是存入 int 类型变量的指针或者 float 类型的指针。但是如此一来，容器就不能直接插入字面量，而必须把字面量转换成变量，再来获取变量的指针。这样做十分不优雅。
使用了不定参数的接口可以如下插入数据：
// int 型的容器container_insert(list, 1);// float 型的容器container_insert(list, 5.4);
复制代码
但这样做也有缺点，那就是只能依靠程序员，严重按照自己定义的容器去插入数据，例如你定义了 int 型的容器，在 container_insert 的时候就必须插入整形。如果你插入了浮点，编译是不会报错的，但是程序的逻辑错了，追查起来比较麻烦。
static int __list_remove(container_t* container, iterator_t pos, void* rdata){ // 删除 // 同样需要 container_of 的技术 list_node_t* remove = container_of(pos.reference, list_node_t, w); remove->prev->next = remove->next; remove->next->prev = remove->prev;
// 将要删除的值返回出去。 //if (rdata) container->type_def.ty_adapter.bit_cpy(rdata, remove->w); if (rdata) type_value_cpy(rdata, remove->w, T_size(container->type_clazz)); // 回收 deallocate(container->mem_pool, remove); ((list_t*)container)->_size--; return 0;}
复制代码
container_t* list_create(int ty) { T_clazz __t = T_get(ty); list_t* list = (list_t*) malloc( sizeof(list_t)); initialize_container( list, __list_first, __list_last, __list_move, __list_insert, __list_remove, __t, );
list_first(list) = list_head(list); list_last(list) = list_tail(list); list->_size = 0; return list;}
复制代码
至此双向链表与容器接口的代码已经全部实现。
03 测试
搞了这么多，终于可以试用一下。
int main (){ // 测试 int 类型的容器。 list_t* list = list_create(int_t); container_insert(list, 1); container_insert(list, 2); container_insert(list, 3); container_insert(list, 4); container_insert(list, 5); // 输出容器内的整形 1，2，3，4，5 for (iter it = container_first(list); !iter_eqaul(it, container_tail(list); iter_next(it)) { printf("%d ", iter_drefer(it); } // 测试 float 的类型的容器。 list_t list2 = list_create(fl_t); container_insert(list2, 1.1); container_insert(list2, 2.2); container_insert(list2, 3.3); container_insert(list2, 4.4); container_insert(list2, 5.5); // 输出容器内的整形 1.1，2.2，3.3，4.4，5.5 for (iter it = container_first(list); !iter_eqaul(it, container_tail(list); iter_next(it)) { printf("%d ", iter_drefer(it); }}
复制代码
总结：至此一个简单的 C 语言版本的容器就制作好了。在没有模版机制的加持下，实现一套容器，确实也比较麻烦。但也不是不可以。
以上源码出自：https://github.com/zuweie/boring-code
评论