双链表基础操作：初始化、插入、删除与遍历示例

本文档主要介绍了如何在C语言中实现双链表的基本操作，包括初始化、插入、删除和遍历。双链表是一种数据结构，它在每个节点中包含两个指针，一个指向前一个节点（prior），另一个指向后一个节点（next）。这使得双链表在某些场景下比单链表更灵活，例如在需要频繁进行前后节点操作时。 1. **双链表初始化**: - 函数`InitDLinkList`是双链表初始化的关键部分。它首先动态分配一个`DNode`结构体，作为链表的头节点，并将其赋值给输入参数`L`。如果内存分配失败，函数返回`false`。初始化完成后，头节点的`prior`指针设为`NULL`，`next`指针设为`NULL`，表示链表初始状态为空。 2. **判断双链表是否为空**: - `Empty`函数用于检查链表是否为空，通过检查`L->next`是否为`NULL`来确定。如果为空，则返回`true`，否则返回`false`。 3. **双链表插入**: - `InsertDNode`函数用于在指定节点`p`之后插入新节点`s`。首先检查`p`和`s`是否为空，然后更新指针关系：将`s`的`next`指向前一个节点`p->next`，`p->next`的`prior`设置为`s`，并把`s`的`prior`指针设置为`p`，最后将`s`连接到`p`的后面，返回`true`表示成功。 4. **双链表删除**: - `DeleteNextDNode`函数用于删除`p`节点的后继节点`q`。首先检查`p`和`q`是否为空，然后更新指针，将`p`的`next`指向`q->next`，如果`q->next`不为空，则将其`prior`设置为`p`。接着释放`q`的内存空间，返回`true`表示删除成功。 5. **清空双链表**: - `DestoryList`函数用于清除链表中的所有节点，通过一个循环不断调用`DeleteNextDNode`直到`L->next`为空。最后释放头节点`L`的内存，并将其置为`NULL`，表示链表已彻底清空。 6. **双链表遍历（后向）**: - 文档中提到的遍历未给出具体实现，但提到的是后向遍历，即从尾部开始遍历到头部。这通常需要使用一个辅助指针或者递归方式，逐个访问节点直到头节点。在实际操作中，可以设置一个指针`prev = NULL`，从`L->next`开始，每次迭代将当前节点的`next`指针赋给`prev`，然后递归或非递归地处理`prev`，直到`prev`为空。 总结起来，本文档详细展示了双链表的基础操作，包括创建、插入、删除和基本的遍历方法，这对于理解和使用双链表数据结构非常有帮助。在实际编程中，这些函数可以作为构建更复杂数据结构和算法的基石。