数据结构之循环双链表（C语言）带所有函数功能的教学与代码实现

前言：

LZ大学生一枚，在学习数据结构的过程中进行了相应的代码实现，和大家分享分享我的代码。若有不足之处，还请各位大佬指点指点。

网课链接：《数据结构与算法基础》教学视频目录 - 哔哩哔哩

感谢青岛大学 - 王卓老师的教学视频~（非常好的数据结构教学视频）

本文章实现的是字符数据的链式存储，一个结点有两个指针和一个data域，链表的头结点的前驱为尾元结点，尾元结点的后继为头结点。

在这里我会详细说明LZ在敲链表时候遇到的坑，也希望能够帮助到数据结构的新手们。

循环双链表的结构示意图：

 其中，单个结点的图示为：

首先是单个结点的结构体定义：

typedef struct DuLNode {
    struct DuLNode* prior;
    char data;
    struct DuLNode* next;
}DuLNode,*DuLinkList;

其中——DuLNode是一个结点结构，其数据类型为一个结构体(struct)，struct内包含一个DuLNode*（指向DuLNode结构体的结构体指针）prior、DuLNode*（指向DuLNode结构体的结构体指针）next、和数据域char data。

                他的别名*DuLinkList表示的是一个指针类型的变量，这个指针指向的是一个DuLNode类型的数据，通常我们新建一个链表会用："DuLinkList L;" 这个语句中L是一个指针，它存放的是一个结点的地址，通常我们使用 L 代表头结点。L->next便是首元结点的地址。

当我们定义完DuLinkList L后还不能直接使用它。我们需要为其开辟内存空间，即初始化空链表的操作。（如果不为其分配内存，会报没有Initialization(初始化)的错误）

DuLinkList InitDuLinkList() {
 
    //@ -   初始化链表，返回头结点
 
    DuLinkList L = (DuLinkList)malloc(sizeof(DuLNode));
    // - 需要#include<stdlib.h>
 
    // - 因为是循环链表，所以初始化的时候要把prior域与next域指针指向L
    L->prior = L;
    L->next = L;
    return L;
}

同样的，我们新申请一个结点元素也应该为其初始化（malloc开辟内存空间），这个构建新的结点元素的函数返回值为DuLNode*，这个函数在之后的尾插法建立链表会用到。

DuLNode* CreateDuLNode() {
 
    //@ -   创建一个新结点，并完成初始化
 
    DuLNode* p = malloc(sizeof(DuLNode));
    p->prior = NULL;
    p->next = NULL;    //将新结点的两个指针域置NULL，以免指向不该指的地方
    return p;
}

到了这一步，我们只需要在main函数中有以下代码：

int main(){
    DuLinkList L = InitDuLinkList(); 
    return 0;
}

 好耶，一个像上图一样的空的循环双链表就给我们定义并在内存空间初始化完成了！

我们不需要在初始化函数中为头结点的data域赋值，因为头结点是不存放元素的，头结点的存在的作用是方便我们操作链表结构。

那么怎么样给这个链表添加新的结点元素呢？此时就需要给链表插入元素啦。

插入元素的方法分为头插法和尾插法。

头插法 - 利用链表的头结点L，在头结点后面循环进行元素的插入，插入的元素的顺序是倒序的。

尾插法 - 利用指向尾元结点的尾指针r，在链表最后一个结点后面进行元素的插入，插入的元素的顺序是正序的

因为尾插法会比较方便，所以这里使用尾插法建立链表。代码如下：

void CreateDuLinkList_W(DuLinkList L,char* elem) {
    /*
    @   - 尾插法建立循环双链表
    @   - 传入的数据类型为 char* [字符串]
    @   - *必须传入一个空链表* -
    */
    DuLinkList r = L;   //尾指针
    int i;
    //这里需要#include<string.h>
    for ( i = 0; i < strlen(elem); i++){    //字符串有多长就循环多少次
        DuLNode* p = CreateDuLNode();    //新初始化一个新结点
        p->data = elem[i];    //将结点的data域赋上值
        p->prior = r;    //新结点的前驱指针指向r(尾指针所存放的地址)
        p->next = L;    //新结点是新的尾元结点,next域就是L啦.
        r->next = p;    //处理旧尾元结点的next域,指向p
        L->prior = p;    //处理一下头结点的前驱指针，指向新的尾元结点p
        r = p;  //尾指针后移
    }
    //下面来验证一下创建链表的成功与否
    printf("
* - 您所创建的循环双链表内容为：");
    r = L->next;    //尾指针重新指向首元结点
    while (r->next && r != L){ //当r指向尾元结点之后，r->next为L,所以结束条件为r!=L
        printf("%%c", r->data);
        r = r->next;
    }
}

尾插法建立链表的图示为：

首先①②新申请一个新的结点，并为结点的data域赋上值。

①：DuLNode* p = CreateDuLNode();

②：p->data = elem[i];

然后③④处理新结点的两个指针域，前驱指针指向r；因为p是新的尾元结点，所以p的后继指针应该指向链表的头结点。

③：p->prior = r;

④：p->next = L;

然后⑤⑥处理旧的尾元结点的next域，应该指向p；处理原本头结点的prior域，应该指向新的尾元结点p。

⑤：r->next = p;

⑥：L->prior = p;

最后⑦将尾指针后移，移到指向p结点。

⑦：r = p;

这样，尾插法建立链表的操作就完成啦

随后我们输出一下我们的链表内的所有元素吧。

因为这是一个数据类型为字符类型的链式结构，所以我希望输出链表元素的返回值的类型为字符串。

在这之前我们需要一个函数来统计链表内结点的个数：

int CountDuLinkList(DuLinkList L) {
 
    //@ -   统计链表结点个数，返回 @int - 结点个数
 
    DuLinkList p = L;    //用 p - 指向DuLNode类型的指针来将链表扫一遍
    int cnt = 0;
    while (p->next != L){ //只有尾元结点的next域才是L，所以结束条件自然是这个
        p = p->next;
        cnt++;
    }
    return cnt;
}

char* ReturnStringDuLinkList(DuLinkList L) {
 
    //@ - 以 @string* 的形式返回链表内的所有元素
 
    int Count = CountDuLinkList(L);    //链表(字符元素)的长度(个数)
    DuLinkList p = L->next; // p 指向首元结点,用p扫描链表
    char* string = malloc(Count + 1 * sizeof(char));//用一个字符串string存放
    int i;
    for ( i = 0; i < Count; i++){
        string[i] = p->data;
        p = p->next;
    }
    string[i] = '';//C中字符串必须以为末尾
    return string;
}

此时我们就可以操作我们的链表啦 来试试构建链表并输出：

int main(){
    DuLinkList L = InitDuLinkList();      //初始化链表
    char* String; int i; 
    printf("请输入字符串：");
    scanf("%%s", &String);
    CreateDuLinkList_W(L, &String);
    printf("
链表内储存的元素的字符串为：%%s",ReturnStringDuLinkList(L));
    return 0;
}

%%s表示的是一个字符串，它必须是一个以 '' 结尾的char*（一维的字符类型数组）

那么接下来就是实现链表的插入、删除操作

int InsertDuLinkList(DuLinkList L, int index, char elem) {
 
    //@ - 在第 index 个位置前面插入元素elem.
 
    if (index <= 0 || index > CountDuLinkList(L) + 1)
        return ERROR;   //判断index值的合法性
    DuLinkList p = L;
    int i;
    if (index == CountDuLinkList(L) + 1) {
 
        //@ 表示在最后一个结点后插入元素
 
        p = L->prior;   // p 指向尾元结点
        DuLNode* s = CreateDuLNode();    //申请新的结点s
        s->data = elem;
        s->next = L;
        s->prior = p;    //这些操作和前面尾插法建立链表相似
        p->next = s;
        return OK;
    }
    else {
    //
    //如果是在特定位置前插入元素，操作就不一样了
    //
        for (i = 0; i < index; i++) {
            p = p->next;    //使 p 移动到操作结点
        }
        DuLNode* s = CreateDuLNode();
        s->data = elem;    //对新结点的data域赋值
        s->prior = p->prior;    //新的结点s将成为p的前驱结点，这里要让s成为p的前驱结点
        p->prior->next = s;    //前一结点的后继就是p啦
        s->next = p;    //s结点的后继是p
        p->prior = s;    //p的前驱是s
        return OK;
    }
}

插入操作是分两种情况的。

第一种情况：要插入的位置是在最后一个元素的后面（即index为链表长度+1），那么插入操作和尾插法构建新链表的操作一致，p充当尾指针，因为链表的循环性，所以通过p = L->prior;可以快速到达尾元结点。

第二种情况：要插入的位置是在链表的除尾元结点后的某一处，那么操作图示如下：

先令p指针指向要操作的index位置。然后操作将s结点接在p指针的前面。 

要点就是——依次处理s的前驱、p前驱的后继、s的后继、p的前驱。

可以想象一下如果不按照这种次序处理，不按逻辑地处理指针域会造成前驱元素或后继元素的丢失

s结点的两个指针域，前驱指针和后继指针是可以率先操作的，因为不会对原链表造成影响。

1.2和4的次序是不可以对调的。我们先要将p->prior->next(存放a元素的结点的next域)接到s结点上，若我们先操作p->prior = s，p->prior就被修改了，p->prior的地址就不是那个存放a元素的结点了。如果是这样，我们就没有办法操作s的prior域指向a结点，也没有办法操作a结点的next域了

 插入操作是链表的关键操作，只需要掌握了插入操作，那么就可以类推出来删除、查找元素的操作了。下面附赠其他操作函数的代码。

获取第index位置的元素

char GetElemDuLinkList(DuLinkList L, int index) {
 
    //  @ - 寻找第index位元素 ,返回 @char - 第index位置的数据元素
 
    if (index <= 0 || index > CountDuLinkList(L))
        return ERROR;   //判断index值的合法性
    DuLinkList p = L;
    int i;
    for ( i = 0; i < index; i++){
        p = p->next;
    }
    return p->data;
}

查找链表内第一个与元素elem匹配的元素的位置

int FindElemDuLinkList(DuLinkList L, char elem) {
 
    //  @ - 寻找链表中第一个出现匹配值的元素的位置，返回 @index - 位置序号
 
    DuLinkList p = L->next; //p指针指向首元结点
    int index = 1;
    do{
        if (p->data == elem) {
            return index;
            break;
        }
        index++;
        p = p->next;
    } while (p->next != L->next);
    return ERROR;
}

删除结点、删除链表

int DeleteDuLNode(DuLinkList L, int index) {
 
    //@ - 删除第 index 位置的元素结点.
 
    if (index <= 0 || index > CountDuLinkList(L))
        return ERROR;   //判断index值的合法性
    DuLinkList p = L;
    int i;
    for (i = 0; i < index; i++) {
        p = p->next;    //使 p 移动到操作结点
    }
    p->prior->next = p->next;
    p->next->prior = p->prior;
    free(p);
    return OK;
}
int DeleteDuLinkList(DuLinkList L) {
 
    //@ - 删除整个链表
 
    DuLinkList p = L->prior;    // p 指针指向最后一个元素
    DuLinkList r;
    while (p->prior != L){
        r = p;
        p = p->prior;
        free(r);
    }
    return OK;
}

来看看所有功能的操作吧：