线性表——带头循环双向链表的增删查改

本节复习带头循环双向链表的增删查改。

带头循环双向链表的结构很完美，是我们日常生活中使用最多的一种链表的形式。但是考的频率要少于单链表。

双链表的全部接口

准备文件

建立双链表的结构体蓝图

创建返回链表的头节点

申请新节点函数接口

双向链表尾插函数接口

双向链表打印函数接口

双向链表头插函数接口

双向链表尾删函数接口

双向链表头删函数接口

双向链表查找函数接口

双向链表在pos位置之前插入数据函数接口

双向链表删除pos位置节点函数接口

双链表销毁函数接口

双链表的全部接口

//返回双链表的头节点接口
DLNode* DLCreate();
//双链表尾插函数接口
void DLPushBack(DLNode* head, DSLDataType x);
//双链表打印函数接口
void DLPrint(DLNode* head);
//双链表头插函数接口
void DLPushFront(DLNode* head, DSLDataType x);
//双链表尾删函数接口
void DLEraseBack(DLNode* head);
//双链表头删函数声明
void DLEraseFront(DLNode* head);
//双链表查找函数接口
DLNode* ListFind(DLNode* head, DSLDataType x);
//双向链表再pos位置之前插入函数接口
void DLInsert(DLNode* head, DLNode* pos, DSLDataType x);
//双向链表删除pos位置节点函数接口
void DLErase(DLNode* head, DLNode* pos);
//双向链表销毁函数接口
void DLDestory(DLNode* head);

准备文件

三个文件，一个main.c, 一个.h文件用于接口声明。还有一个.c文件用于接口实现。

如图：

---------------------------------------------------------------------------------------------------------------------------------

建立双链表的结构体蓝图

先包含头文件，将要保存的数据类型重新定义。如图：

然后创建结构体。

带头循环双向链表的结构体成员比单链表多出一个指向前一个节点的指针。双向链表的取名就是从这取的。每一个节点都是双向的。一个指向下一个结点的指针，一个指向上一个节点的指针。还有一个保存数据的指针。

如图：

---------------------------------------------------------------------------------------------------------------------------------

创建返回链表的头节点

该函数接口是为了创建哨兵位头节点。

.h声明：

.c函数实现

---------------------------------------------------------------------------------------------------------------------------------

申请新节点函数接口

尾插，头插，任意位置插入都需要申请新的链表节点。所以可以将这个操作封装成为一个函数，然后在尾插，头插，任意位置插入函数中进行复用即可。

不需要在.h文件中声明

只需要在.c文件中实现。确保尾插头插，任意位置插入可以使用

.c实现：

---------------------------------------------------------------------------------------------------------------------------------

双向链表尾插函数接口

双向链表的尾插非常简单，因为哨兵位头节点的prev指针指向尾节点，所以可以直接用头节点的prev指针找到尾节点。然后将新节点插到尾节点的后面。

尾插的实现方式如下：这是第一步，先让newnode前指针指向尾节点，再让newnode的后指针指向head节点。

接下来是第二步：

让尾节点的后指针指向newnode， head的前指针指向newnode。注：头插，任意位置插入都可以用类似的方法进行插入，就是先让newnode的两个指针连接两边。再让两边连接newnode。