本篇次要介绍开源C语言库Melon的双向链表应用,对开源C库感兴趣的读者能够拜访:Github repo。

链表简介

先简略介绍一下什么是双向链表。能够参考下图:

简略来说,链表是将一个一个的结点,通过指针连接起来。而双向链表则是每一个结点不仅记录了指向下一结点的指针,也记录了指向前一结点的指针。

Melon中的双向链表属于上图中带有尾部结点的双向链表。

双向链表的劣势:结点的插入和删除操作的工夫复杂度为O(1),所以应答频繁插入和删除的场景,是非常适合的。

双向链表应用

咱们先定义一个自定义构造体类型:

typedef struct test_s {    int val;} test_t;

后续的介绍中,咱们要做的就是应用Melon的链表组件对这个构造进行革新,将其构建成一个双向链表。

在Melon中,双向链表有两种实现。两种实现进行比照也各有其特点,因而读者在理解各自特点后,可依据本人须要进行抉择应用。

第一种实现

咱们间接上代码,而后再进行阐明:

#include <stdio.h>#include <stdlib.h>#include "mln_defs.h"typedef struct test_s {    int val;    struct test_s *prev;    struct test_s *next;} test_t;MLN_CHAIN_FUNC_DECLARE(test, test_t, static inline void, );MLN_CHAIN_FUNC_DEFINE(test, test_t, static inline void, prev, next);int main(void){  int i;  test_t *head = NULL, *tail = NULL, *t;  for (i = 0; i < 10; ++i) {    t = (test_t *)malloc(sizeof(test_t));    if (t == NULL) {        fprintf(stderr, "malloc failed.\n");        return -1;    }    t->val = i;    t->prev = t->next = NULL;    test_chain_add(&head, &tail, t);  }  for (t = head; t != NULL; t = t->next) {    printf("%d\n", t->val);  }  return 0;}

这段代码中,main函数中的内容很简略,利用一个for循环,malloc10个test_t构造,而后将其val填充数值。随后利用test_chain_add函数将这些结点连成一个链表。而后利用for循环遍历结点并打印val的值。

上面问题就来了,test_chain_add哪里来的?

咱们看到main前有两个MLN_CHAIN_FUNC_xxx的宏,这两个宏是在Melon的mln_defs.h头文件中定义的,用来对链表的插入和删除函数进行定义和申明的。

MLN_CHAIN_FUNC_DECLARE
  • 第一个参数:函数名前缀
  • 第二个参数:自定义构造体类型
  • 第三个参数:函数返回值及函数类型
  • 第四个参数:函数参数限度属性(本例没有应用)
MLN_CHAIN_FUNC_DEFINE
  • 第一个参数:函数名前缀
  • 第二个参数:自定义构造体类型
  • 第三个参数:函数返回值及函数类型
  • 第四个参数:自定义构造中用于拜访前一结点的指针成员名字
  • 第五个参数:自定义构造中用于拜访下一结点的指针成员名字

这两个宏会定义和申明两个函数,别离名为:test_chain_addtest_chain_del,这两个函数的原型相似如下模式:

void (*chain_op)(type **head, type **tail, type *node);

第一个参数为双向链表首指针的指针,第二个参数为双向链表尾指针的指针,第三个参数为要被操作的结点指针。

特点

这种实现计划的益处是:插入和删除函数能够被定义成inline或者减少一些其余属性。并且在遍历链表时,只须要拜访自定义结点的prevnext指针即可。

毛病是:使用者须要晓得自定义构造中本人退出的prevnext成员名字,以及如果定义了很多双向链表,则须要配套定义很多插入和删除函数,会减少可执行程序的体积。

第二种实现

这种实现可能比拟常见了。咱们间接看代码:

#include "mln_list.h"#include "mln_defs.h"#include <stdlib.h>typedef struct {    int        val;    mln_list_t node;} test_t;int main(void){    int i;    test_t *t;    mln_list_t sentinel = mln_list_null();    for (i = 0; i < 3; ++i) {        t = (test_t *)calloc(1, sizeof(*t));        if (t == NULL)            return -1;        mln_list_add(&sentinel, &t->node);        t->val = i;    }    for (t = mln_container_of(mln_list_head(&sentinel), test_t, node); \         t != NULL; \         t = mln_container_of(mln_list_next(&t->node), test_t, node))    {        printf("%d\n", t->val);    }    return 0;}

主函数的行为与第一种实现的代码是齐全一样的。差异在于如下几方面:

  1. 引入了mln_list.h头文件
  2. test_t中不再是增加prevnext成员,而是退出一个固定类型的成员,即mln_list_t类型的node成员。
  3. 双向链表的首尾指针改为了一个名叫sentinelmln_list_t类型变量。
  4. 链表插入函数不再是自定义前缀函数,而是一个固定名称的函数名为mln_list_add.
  5. 拜访链表首结点应用mln_list_head
  6. 想获取链表结点所在的宿主构造(即本例的test_t)指针,须要应用mln_defs.h中的mln_container_of宏。

特点

这种实现的优劣别离是:

劣势:使用者不须要关怀链表的具体实现细节,只须要在自定义类型中引入mln_list_t类型成员即可。并且函数的插入和删除操作都是固定名称的,别离为:mln_list_addmln_list_remove

劣势:对链表结点所属的宿主结点(test_t)的拜访须要借助mln_container_of宏,这看上去并不如第一种实现中那么直观。且链表操作函数都是非inline的,因而频繁调用的开销会高于第一种实现。

事实上,感兴趣的读者可能会发现,第二种双向链表(mln_list.c),是应用第一种双向链表来实现的。

结语

感激浏览,感兴趣的读者能够拜访Melon库查看更多细节,Melon是一个无依赖且开箱即用的开源C语言库,并且有配套的中英文文档。

Github传送门