C语言 超详细介绍与实现线性表中的带头双向循环链表

简介

本篇文章将介绍C语言中线性表的实现方式之一——带头双向循环链表，同时会对链表的相关知识进行详细阐述。本文中将包含以下内容：
- 什么是链表？
- 什么是双向链表？
- 如何实现带头双向循环链表？
- 带头双向循环链表的相关操作

什么是链表？

链表是一种常见的数据结构，与数组相比具有以下优势：
- 可以动态的分配内存大小
- 插入或删除元素时无需整体移动

链表又分为单向链表和双向链表，其中单向链表每个节点只有一个后继指针，而双向链表每个节点则有一个前驱指针和一个后继指针。

什么是双向链表？

如上所述，双向链表每个节点同时有一个前驱指针和后继指针。这种数据结构有以下优势：
- 在遍历时可以实现双向遍历（单向链表只能顺序遍历）
- 实现插入、删除节点时效率更高

如何实现带头双向循环链表？

带头双向循环链表是指在双向链表的基础上，增加一个头节点，并把头节点的前驱指针和尾节点的后继指针相互连接，使链表形成环形结构。

实现带头双向循环链表可以参照以下步骤：
1. 定义节点的数据结构体，其中应包含前驱指针、后继指针和数据三个成员
2. 定义头节点，前驱指针和后继指针均指向头节点本身
3. 定义相关操作函数（如插入、删除、查找等）

以下是一个基本的带头双向循环链表的数据结构定义：

typedef struct Node{
    int data;
    struct Node* prev;
    struct Node* next;
}Node, *LinkList;

LinkList head = (LinkList)malloc(sizeof(Node));
head->prev = head;
head->next = head;

以上代码中，LinkList为链表结构体类型的指针，表示链表的首地址。同时，头节点的前驱指针和后继指针都指向头节点本身，以此建立链表的环形结构。

带头双向循环链表的相关操作

在实现带头双向循环链表后，我们需要实现一个系列的操作来对链表进行相应的操作。以下为基本的操作：

1. 插入节点
   在链表中插入节点时，需要将该节点的前驱指针和后继指针连接到相应的节点上。例如，在链表中的第2个位置插入一个元素：

void Insert(LinkList L, int i, int e){ //在第i个结点之前插入数据元素e
    int j = 0; LinkList p = L, s;
    while(p != L && j < i - 1){
        p = p->next;
        j ++;
    }
    if(!p || j > i - 1) return ERROR;
    s = (LinkList)malloc(sizeof(Node));
    s->data = e;
    s->prev = p;
    s->next = p->next;
    p->next->prev = s;
    p->next = s;
}

1. 删除节点
   在链表中删除节点时，需要将该节点的前驱指针和后继指针连接起来。例如，从链表中删除第2个节点：

void Delete(LinkList &L, int i){ //在链表L中删除第i个元素
    int j = 0;
    LinkList p = L, q;
    while(p->next != L && j < i - 1){
        p = p->next;
        j ++;
    }
    if(p->next == L || j > i - 1) return ERROR;
    q = p->next;
    q->next->prev = p;
    p->next = q->next;
    free(q);
    return OK;
}

示例

以下是一个例子，展示了如何创建、插入和删除带头双向循环链表。

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

typedef struct Node{
    int data;
    struct Node *prev;
    struct Node *next;
}Node, *LinkList;

LinkList creat_head();
void PrintList(LinkList L);
void Insert(LinkList L, int i, int e);
void Delete(LinkList L, int i);

int main(){
    LinkList L = creat_head();

    Insert(L, 1, 1);
    Insert(L, 2, 2);
    Insert(L, 3, 3);

    printf("Original List:\n");
    PrintList(L);

    Delete(L, 2);
    printf("After deleting the second node:\n");
    PrintList(L);

    return 0;
}

LinkList creat_head(){
    LinkList head = (LinkList)malloc(sizeof(Node));
    head->prev = head;
    head->next = head;
    return head;
}

void PrintList(LinkList L){
    LinkList p = L;
    while(p->next != L){
        printf("%d ", p->next->data);
        p = p->next;
    }
    printf("\n");
}

void Insert(LinkList L, int i, int e){
    int j = 0;
    LinkList p = L, s;
    while(p != L && j < i - 1){
        p = p->next;
        j ++;
    }
    if(!p || j > i - 1) return;
    s = (LinkList)malloc(sizeof(Node));
    s->data = e;
    s->prev = p;
    s->next = p->next;
    p->next = s;
    s->next->prev = s;
}

void Delete(LinkList L, int i){
    int j = 0;
    LinkList p = L, q;
    while(p->next != L && j < i - 1){
        p = p->next;
        j ++;
    }
    if(p->next == L || j > i - 1) return;
    q = p->next;
    p->next = q->next;
    q->next->prev = p;
    free(q);
}

以上是带头双向循环链表的基本介绍和实现步骤，详细讲解了链表、双向链表以及带头双向循环链表的概念和原理，结合代码示例进行了实现和操作演示。