【数据结构】环形蛇？链表之带头双向循环链表_双向循环链表操作的实现参考文献

目录

1.摘要
2.带头双向循环链表的介绍
    2.1.双向链表
    2.2.循环链表
    2.3.带头双向循环链表
3.代码实现
    3.1.头文件
    3.2.接口文件
    3.3.测试文件
4.参考文献

1.摘要

本文主要介绍带头双向循环链表的概念及其C语言的代码实现。

2.带头双向循环链表的介绍

2.1.双向链表

我们在上一节介绍了单向无头非循环链表，但是我们仔细想想，既然该链表是单向的，那么直接带来的一个后果是只能通过前一个节点找后一个节点，而不能通过后一个节点找到前一个结点。

为什么会这样呢？很简单，因为节点只拥有一个标识后继节点地址的指针域。

那么如果我们想要直接找到一个节点的前一个节点呢？也很简单，只要再为节点增加一个指针域，记录前驱的地址即可。

typedef struct DLList
{
   
	struct DLList* next; //记录后继节点地址的指针
	struct DLList* prev; //记录前驱节点地址的指针
	DLListDataType data; //数据域
}DLList;
1
2
3
4
5
6
7

2.2.循环链表

另外，在单向无头非循环链表中，最后一个节点的指针域我们存放NULL，表示它的后面没有节点了。所以该链表是非循环的。

那么如果是循环的链表呢？聪明的你一定想到了，只要让尾节点的next指针域中存储头节点的地址，整个链表就会形成一个完美的闭环！

对，就像这样，不知大家在物理课上有没有见过这样一张图片，这就是一个闭环！

2.3.带头双向循环链表

好了，好了，我们不跑题了，既然我们已经介绍了什么是双向链表以及什么是循环链表，那让我们把这两个性质结合起来，看一看带头双向循环链表的庐山真面目：

链表包含一个头节点，每个节点拥有一个数据域和两个指针域next和prev，头节点的数据域不存放有效数据

3.代码实现

3.1.头文件

#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
typedef int DLListDataType;

typedef struct DLList
{
   
	struct DLList* next;
	struct DLList* prev;
	DLListDataType data;
}DLList;

DLList* DLListInit();
void DLListDestroy(DLList* phead);
void DLListPrint(const DLList* phead);
void DLListPushBack(DLList* pphead, DLListDataType x);
void DLListPushFront(DLList* pphead,DLListDataType x);
void DLListPopBack(DLList* pphead);
void DLListPopFront(DLList* pphead);
DLList* DLListFind(const DLList* phead,DLListDataType x);
void 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23