C语言编程数据结构带头双向循环链表全面详解

什么是带头双向循环链表？

带头双向循环链表是一种基于链式存储结构的数据结构，每个节点包含三个关键信息：前驱指针、数据域和后继指针。与单向链表不同的是，每个节点不仅有一个后继指针，还有一个前驱指针，可以实现双向遍历和操作。而带头指针和尾指针更是可以优化链表的插入、删除等操作复杂度。

带头双向循环链表的基本操作

1. 插入操作：

// 在p节点之后插入元素x
void InsertAfter(PNode p, int x) 
{
    PNode q = (PNode)malloc(sizeof(Node));
    q->data = x;
    q->next = p->next;
    p->next->prev = q; // 新节点的next域指向p节点的next域
    q->prev = p;    // 新节点的prev域指向p节点
    p->next = q;    // p节点的next域指向新节点
}

// 在p节点之前插入元素x
void InsertBefore(PNode p, int x) 
{
    PNode q = (PNode)malloc(sizeof(Node));
    q->data = x;
    q->prev = p->prev;
    p->prev->next = q; // 新节点的prev域指向p节点的prev域
    q->next = p;    // 新节点的next域指向p节点
    p->prev = q;    // p节点的prev域指向新节点
}

1. 删除操作：

// 删除p节点
void DeleteNode(PNode p) 
{
    p->prev->next = p->next; // p前驱的next指向p后继
    p->next->prev = p->prev; // p后继的prev指向p前驱
    free(p);
}

1. 查找操作：

// 查找链表中第index个节点
PNode Find(PList L, int index)
{
    if (index < 1) return NULL; // 下标非法返回NULL
    PNode p = L->head->next;
    int j = 1;
    while (p && j < index)
    {
        p = p->next;
        j++;
    }
    return p;
}

基本操作的应用

示例一：将多个链表合并成一个链表

// 将L2合并到L1中
void Merge(PList L1, PList L2) 
{
    L1->tail->prev->next = L2->head->next; 
    L2->head->next->prev = L1->tail->prev;
    L1->tail = L2->tail; 
    free(L2->head);
    L2->head = NULL;
}

示例二：对链表进行排序

// 冒泡排序
void BubbleSort(PList L)
{
    PNode p, q;
    for(p = L->head->next; p != L->tail; p = p->next)
    {
        for(q = p->next; q != L->tail; q = q->next)
        {
            if (p->data > q->data)
            {
                int temp = p->data;
                p->data = q->data;
                q->data = temp;
            }
        }
    }
}

结语

带头双向循环链表是一种非常实用的数据结构，对于掌握C语言编程和数据结构的人来说，是难以绕过的知识点。以上是对基本操作的简单介绍，希望能对你有所帮助，加油！