C语言实现带头双向环形链表

C语言实现带头双向环形链表的完整攻略

什么是双向环形链表

双向链表是在单向链表的基础上增加了一个指向前驱节点的指针，使得链表可以双向遍历。双向环形链表是在双向链表的基础上将尾指针指向头节点，形成一个环形结构。带头结点的链表是在链表头增加一个头结点，并将头结点的指针指向第一个节点，使得链表的插入和删除操作更加简单。

如何实现带头双向环形链表

实现带头双向环形链表的关键是设计链表节点结构体以及头结点的指针。节点结构体中需要包含数据域，指向前驱节点和后继节点的指针域。头结点为一个普通的节点，其中数据域可以为空，指针域指向链表中的任一节点均可。

以下是实现带头双向环形链表的完整攻略：

1. 定义链表节点结构体

   c
typedef struct ListNode {
int data;
struct ListNode *prev;
struct ListNode *next;
} ListNode;

2. 定义头结点

   c
ListNode *head = NULL;

3. 实现链表的初始化操作

   c
void initList() {
head = (ListNode*)malloc(sizeof(ListNode));
head->prev = head;
head->next = head;
}

4. 实现链表的插入操作，包括头插入和尾插入

   ```c
   void insertFront(int x) {
   ListNode node = (ListNode)malloc(sizeof(ListNode));
   node->data = x;
   node->prev = head;
   node->next = head->next;
   head->next->prev = node;
   head->next = node;
   }

   void insertEnd(int x) {
   ListNode node = (ListNode)malloc(sizeof(ListNode));
   node->data = x;
   node->prev = head->prev;
   node->next = head;
   head->prev->next = node;
   head->prev = node;
   }
   ```

5. 实现链表的删除操作

   c
void deleteNode(ListNode *node) {
node->prev->next = node->next;
node->next->prev = node->prev;
free(node);
}

示例说明

以下是两个示例分别实现了带头双向环形链表的初始化、头插入和删除操作：

#include <stdio.h>
#include <stdlib.h>

typedef struct ListNode {
    int data;
    struct ListNode *prev;
    struct ListNode *next;
} ListNode;

ListNode *head = NULL;

void initList() {
    head = (ListNode*)malloc(sizeof(ListNode));
    head->prev = head;
    head->next = head;
}

void insertFront(int x) {
    ListNode *node = (ListNode*)malloc(sizeof(ListNode));
    node->data = x;
    node->prev = head;
    node->next = head->next;
    head->next->prev = node;
    head->next = node;
}

void deleteNode(ListNode *node) {
    node->prev->next = node->next;
    node->next->prev = node->prev;
    free(node);
}

int main() {
    initList();

    insertFront(1);
    insertFront(2);
    insertFront(3);

    ListNode *node = head->next;
    while (node != head) {
        printf("%d ", node->data);
        node = node->next;
    }

    printf("\n");

    deleteNode(head->next->next);

    node = head->next;
    while (node != head) {
        printf("%d ", node->data);
        node = node->next;
    }

    return 0;
}

输出结果为：

3 2 1 
3 1

第一个示例中，首先初始化了带头双向环形链表，然后进行了头插入操作，插入了3、2、1三个节点，最后输出了链表中的所有节点。第二个示例中，在第一个示例的基础上实现了一个删除操作，删除了节点2，最后再次输出了链表中的所有节点。

阅读剩余 68%