数据结构详解：带头双向循环链表及其代码实现

带头双向循环链表是一种特殊的链表结构，它包含一个哨兵节点，并且每个节点都包含指向前一个节点和后一个节点的指针。这种结构使得链表的操作更加灵活和高效。

2.1 创建结构体

首先，我们需要定义一个结构体来表示链表中的节点：

typedef int LTDataType; // 定义数据类型，可以随时更改

typedef struct ListNode {
    LTDataType data; // 节点数据
    struct ListNode* pre; // 指向前一个节点的指针
    struct ListNode* next; // 指向后一个节点的指针
} LSTNode; // 重命名结构体类型

2.2 链表创建

接下来，我们编写一个函数来创建新的节点：

LSTNode* BuyNode(LTDataType x) {
    LSTNode* newnode = (LSTNode*)malloc(sizeof(LSTNode));
    if (newnode == NULL) {
        perror("malloc fail");
        exit(-1);
    }
    newnode->data = x;
    newnode->next = NULL;
    newnode->pre = NULL;
    return newnode;
}

2.3 链表初始化（哨兵位）

为了方便后续操作，我们通常会在链表中添加一个哨兵节点：

LSTNode* Init() {
    LSTNode* phead = BuyNode(-1); // 初始化哨兵节点，数据为-1
    phead->pre = phead; // 哨兵节点的前指针指向自身
    phead->next = phead; // 哨兵节点的后指针指向自身
    return phead;
}

2.4 查找链表中某一元素的位置

我们可以编写一个函数来查找链表中某个特定元素的位置：

LSTNode* LSTFind(LSTNode* phead, LTDataType x) {
    assert(phead); // 哨兵节点不能为空
    LSTNode* cur = phead->next; // 从哨兵节点的下一个节点开始查找
    while (cur != phead) { // 循环链表，直到回到哨兵节点
        if (cur->data == x) {
            return cur; // 找到目标节点，返回该节点
        }
        cur = cur->next; // 继续查找下一个节点
    }
    return NULL; // 未找到目标节点，返回空
}

2.5 任意位置插入数据（在pos位置之前）

我们可以在指定位置之前插入一个新的节点：

void LSTInsert(LSTNode* pos, LTDataType x) {
    assert(pos); // 插入位置不能为空
    LSTNode* newnode = BuyNode(x); // 创建新节点
    LSTNode* prev = pos->pre; // 获取插入位置的前一个节点
    prev->next = newnode; // 更新前一个节点的后指针
    newnode->pre = prev; // 更新新节点的前指针
    newnode->next = pos; // 更新新节点的后指针
    pos->pre = newnode; // 更新插入位置的前指针
}

2.6 任意位置删除数据

我们也可以删除指定位置的节点：

void LSTErase(LSTNode* pos) {
    assert(pos); // 删除位置不能为空
    LSTNode* pos_pre = pos->pre; // 获取删除位置的前一个节点
    LSTNode* pos_next = pos->next; // 获取删除位置的后一个节点
    free(pos); // 释放删除节点的内存
    pos_pre->next = pos_next; // 更新前一个节点的后指针
    pos_next->pre = pos_pre; // 更新后一个节点的前指针
}

2.7 打印链表

最后，我们可以编写一个函数来打印链表中的所有节点：

void LSTPrint(LSTNode* phead) {
    assert(phead); // 哨兵节点不能为空
    LSTNode* cur = phead->next; // 从哨兵节点的下一个节点开始打印
    while (cur != phead) { // 循环链表，直到回到哨兵节点
        printf("%d ", cur->data); // 打印当前节点的数据
        cur = cur->next; // 移动到下一个节点
    }
}

带头双向循环链表通过引入哨兵节点，使得链表的插入和删除操作变得更加简单和高效。无论是头插、尾插、头删还是尾删，都可以借助哨兵节点轻松实现。希望本文能帮助你更好地理解和掌握这种数据结构。