双向循环链表（C语言描述）（一）

时间：2024-04-18 17:35:37

　　双向循环链表是链表的一种，它的每个节点也包含数据域和指针域。为了方便程序维护，可以单独为数据域定义一种数据类型，这里以整型为例：

 typedef int LinkedListData;

双向循环链表（以下简称链表）的指针域包含前驱指针和后继指针，为了方便对链表的操作，通常在建立链表时会创建一个头结点，链表类型的就是指向头结点的指针类型：

 typedef struct LinkedListNode {

     LinkedListData data;

     struct LinkedListNode * prior;

     struct LinkedListNode * next;

 } LinkedListNode, * LinkedList;

　　在链表没有元素时，头结点的前驱指针和后继指针应指向头结点本身；建立链表的函数linkedlist_new()如下：

 LinkedList linkedlist_new() {

     // alloc head node

     LinkedList list = malloc(sizeof(LinkedListNode));

     assert(list);

     // initialize head node's pointer field

     list->prior = list;

     list->next = list;

     return list;

 }

assert()函数用于判断头结点使用的内存空间是否申请成功，当内存空间申请失败（即malloc()函数返回值为空）时，它会终止程序运行，并将原因打印在标准错误输出上。如果定义了宏NDEBUG，assert()函数不采取任何操作。

　　在C语言中，手动申请的内存空间需要手动进行释放，否则有可能造成程序内存溢出；linkedlist_destory()函数供程序在不需要再使用链表时对其进行销毁：

 void linkedlist_destory(LinkedList * list) {

     while (linkedlist_length(*list)) {

         linkedlist_delete(*list, TRAVELDIR_FORWARD, );

     }

     free (*list);

     *list = NULL;

 }

linkedlist_length()函数和linkedlist_delete()函数分别用于计算链表长度和删除链表中的节点并释放删除节点的内存空间，稍后再提及它们的实现。链表实例的实质是指向头结点的指针，因此在释放头结点的内存空间后，需将它置为空，以防后续的程序再次使用造成内存访问出错。

相关文章