目录
源文件(Double_Linked_List)对函数功能的具体实现：
引言：
数据结构学习目录：
数据结构系列学习(一) - An Introduction to Data Structure
数据结构系列学习（二） - 顺序表（Contiguous_List）
数据结构系列学习（三） - 单链表(Linked_List)
数据结构系列学习（四） - 单向循环链表(Circular Linked List)
在上一篇文章中，我们学习了单项循环链表的理论知识并使用代码对它进行了实现，在链式存储结构中还有另外一种表现形式——双向链表。在我们之前学习的单链表或者单向循环链表中，链表中的每一个节点保存的都是它的后继节点的地址，而我们今天将要介绍和学习的双向链表却不一样，双向链表中的节点既能保存它的后继节点的地址，也能保存它的前驱节点的地址。这也是他为什么叫做双向链表的原因。
学习：
双向链表和单链表不同，双向链表每一个节点既保存后继节点的地址，又保存前驱节点的地址。
为什么会有双向链表？
在严蔚敏的《数据结构（C语言版）》中是这样说的，链式存储结构中只有一个指示直接后继的指针域，由此，从某个节点出发只能顺指针往后寻查其他节点。为克服单链表这种单向性的缺点，就产生了双向链表。
双向链表存在的意义：每个节点既可以找到直接后继，也可以找到直接前驱。且每一个节点既可以向后走，也可以向前走，相当于是对单链表的改进，如图：
代码实现：
双向链表中我们要实现的功能（15个）：
初始化函数(Init_dlist)；
清空函数(Clear)；
销毁函数（无线头删）(Destroy1)；
销毁函数（双指针协作释放节点）(Destroy2)；
打印函数(Show)；
查找函数(Search)；
获取有效长度函数(Get_Length)；
判空函数(IsEmpty)；
头插函数(Insert_head)；
尾插函数(Insert_tail)；
按位置插函数(Insert_pos)；
头删函数(Delete_head)；
尾删函数(Delete_tail)；
按位置删函数(Delete_pos)；
按值删函数(Delete_val)；
头文件(Double_Linked_List)：
结构体的设计：
顾名思义，在双向链表中
typedef int Elem_type;
typedef struct DNode
{
Elem_type data;
struct DNode* next;
struct DNode* prior;
}DNode, *PDnode;函数的声明：
void Init_dlist(PDnode dlist);
void Clear(PDnode dlist);
void Destroy(PDnode dlist);
void Destroy1(PDnode dlist);
void Show(PDnode dlist);
struct DNode* Search(PDnode dlist,Elem_type val);
int Get_Length(PDnode dlist);
bool IsEmpty(PDnode dlist);
bool Insert_head(PDnode dlist,Elem_type val);
bool Insert_tail(PDnode dlist,Elem_type val);
bool Insert_pos(PDnode dlist,int pos,Elem_type val);
bool Delete_head(PDnode dlist);
bool Delete_tail(PDnode dlist);
bool Delete_pos(PDnode dlist,int pos);
bool Delete_val(PDnode dlist,Elem_type val);源文件(Double_Linked_List)对函数功能的具体实现：
初始化函数(Init_dlist)：
void Init_dlist(PDnode dlist)
//如果没有有效节点，则双向链表的头节点，应该：头节点的数据域浪费掉，不使用，头节点的next域
{
assert(dlist != nullptr);
dlist->next = nullptr;
dlist->prior = nullptr;
}清空函数(Clear)：
void Clear(PDnode dlist)
{
Destroy(dlist);
}销毁函数（无线头删）(Destroy1)：
void Destroy(PDnode dlist)//无线头删
{
while(!IsEmpty(dlist)){
Delete_head(dlist);
}
}销毁函数（双指针协作释放节点）(Destroy2)：
void Destroy1(PDnode dlist)//两个指针辅助
{
assert(dlist != nullptr);
PDnode p = dlist->next;
PDnode q = nullptr;
dlist->next = nullptr;
while(p != nullptr){
q = q->next;
free(p);
p = q;
}
}打印函数(Show)：
void Show(PDnode dlist)
{
assert(dlist != nullptr);
PDnode p = dlist->next;
for(;p != nullptr;p = p->next){
printf("%5d",p->data);
}
printf("\n");
}查找函数(Search)：
struct DNode* Search(PDnode dlist,Elem_type val)
{
assert(dlist != nullptr);
PDnode p = dlist->next;
for(;p->next != nullptr;p = p->next){
if(p->data == val){
return p;
}
}
return nullptr;
}获取有效长度函数(Get_Length)：
int Get_Length(PDnode dlist)
{
assert(dlist != nullptr);
int count = 0;
PDnode p = dlist->next;
for(;p != nullptr;p = p->next){
count++;
}
return count;
}判空函数(IsEmpty)：
bool IsEmpty(PDnode dlist)
{
return dlist->next == nullptr;
}头插函数(Insert_head)：
bool Insert_head(PDnode dlist,Elem_type val)
{
assert(dlist != nullptr);
PDnode pnewnode = (PDnode) malloc(1 * sizeof(DNode));
//先修改pnewnode自身的两个域，再处理下一个节点的prior域，最后处理上一个节点的next域
assert(pnewnode != nullptr);
pnewnode->data = val;
pnewnode->next = dlist->next;//1
pnewnode->prior = dlist;
if(dlist->next != nullptr) {
dlist->next->prior = pnewnode;
}
dlist->next = pnewnode;
return true;
}尾插函数(Insert_tail)：
bool Insert_tail(PDnode dlist,Elem_type val)//不存在特殊情况 每一种情况都是修改三个指针域
{
assert(dlist != nullptr);
PDnode pnewnode = (PDnode) malloc(1 * sizeof(DNode));
assert(pnewnode != nullptr);
pnewnode->data = val;
PDnode p = dlist;
for(;p->next != nullptr;p = p->next);
pnewnode->next = p->next;
pnewnode->prior = p;
p->next = pnewnode;
return true;
}按位置插函数(Insert_pos)：
bool Insert_pos(PDnode dlist,int pos,Elem_type val)//当pos==0的时候是头插 当pos等于length的时候是尾插，其他位置pos >0 && pos < length 的时候是中间插入
{
assert(dlist != nullptr);
assert(pos >= 0 && pos <= Get_Length(dlist));
PDnode pnewnode = (PDnode) malloc(1 * sizeof(DNode));
assert(pnewnode != nullptr);
pnewnode->data = val;
if(pos == 0){
return Insert_head(dlist,val);
}
else if(pos == Get_Length(dlist)){
return Insert_tail(dlist,val);
}
PDnode p = dlist;
for(int i = 0;i < pos;i++){//当pos等于几
p = p->next;
}
pnewnode->next = p->next;//1
pnewnode->prior = p;//2
p->next->prior = pnewnode;//4
p->next = pnewnode;//3
return true;
}头删函数(Delete_head)：
bool Delete_head(PDnode dlist)
{
assert(dlist != nullptr);
if(IsEmpty(dlist)){
return false;
}
if(dlist->next->next == nullptr){
dlist->next = nullptr;
}
PDnode p = dlist->next;
dlist->next = p->next;
p->next->prior = dlist;
free(p);
return true;
}尾删函数(Delete_tail)：
bool Delete_tail(PDnode dlist)
{
//尾删不存在特殊情况，因为待删除节点就是尾节点，且待删除节点的后一个节点永远永远不存在
assert(dlist != nullptr);
if(IsEmpty(dlist)){
return false;
}
PDnode p = dlist;
for(;p->next != nullptr;p = p->next);
PDnode q = dlist;
for(;q->next != p;q = q->next);
q->next = p->next;
free(p);
return true;
}按位置删函数(Delete_pos)：
bool Delete_pos(PDnode dlist,int pos)
{
assert(dlist != nullptr);
assert(pos >= 0 && pos < Get_Length(dlist));
if(IsEmpty(dlist)){
return false;
}
//头删的情况
if(pos == 0){
return Delete_head(dlist);
}
//尾删的情况
if(pos == Get_Length(dlist) - 1){
return Delete_tail(dlist);
}
//既不是头删也不是尾删的情况——中间位置的删除，需要统一修改两个指针域
PDnode q = dlist;
for(int i = 0;i < pos;i++){
q = q->next;
}
PDnode p = q->next;
q->next = p->next;
p->next->prior = q;
free(p);
return true;
}按值删函数(Delete_val)：
bool Delete_val(PDnode dlist,Elem_type val)
{
assert(dlist != nullptr);
if(IsEmpty(dlist)){
return false;
}
PDnode p = Search(dlist,val);
if(p == nullptr){
return false;
}
PDnode q = dlist;
for(;q->next != p;q = q->next);
if(p->next == nullptr){
q->next = nullptr;
}
else{
q->next = p->next;
p->next->prior = q;
}
free(p);
return true;
}测试：
测试初始化函数、打印函数：
#include<cstdio>
#include<cassert>
#include<cstdlib>
#include "Double_Linked_List.h"
int main()
{
DNode head;
Init_dlist(&head);
for(int i = 0;i < 10;i++){
Insert_pos(&head,i,i + 1);
}
printf("原始数据为：\n");
Show(&head);
/*
其他函数的测试代码在此添加...
*/
}运行结果：
测试头插函数：
printf("经过头插后的数据为：\n");
Insert_head(&head,100);
Show(&head);运行结果：
测试尾插函数：
printf("经过尾插后的数据为：\n");
Insert_tail(&head,100);
Show(&head);运行结果：
测试按位置插函数：
printf("经过按位置插后的数据为：\n");
Insert_pos(&head,2,100);
Show(&head);运行结果：
测试头删函数：
printf("经过头删后的数据为：\n");
Delete_head(&head);
Show(&head);运行结果；
测试尾删函数：
printf("经过尾删后的数据为：\n");
Delete_tail(&head);
Show(&head);运行结果：
测试按位置删函数：
printf("经过按位置删后的数据为：\n");
Delete_pos(&head,4);
Show(&head);运行结果：
测试按值删函数：
printf("经过按值删后的数据为：\n");
Delete_val(&head,2);
Show(&head);运行结果；
测试查找函数：
PDnode p = Search(&head,4);
printf("地址为：%p",p);运行结果：
PDnode p = Search(&head,100);
printf("地址为：%p",p);运行结果：
测试清空函数：
Clear(&head);
Show(&head);运行结果：
测试销毁函数1：
Destroy(&head);
Show(&head);运行结果：
测试销毁函数2:
Destroy1(&head);
Show(&head);运行结果：
本文含有隐藏内容，请 开通VIP 后查看