目录
线性表：
顺序表
静态顺序表：
动态顺序表：
链表：
不带头单向非循环链表：
带头双向循环链表（List）：
线性表：
线性表(linear list)是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串.......线性表在逻辑上是线性结构,也就说是连续的一条直线,但是在物理结构上并不一定是连续的线性表在物理上存储时,通常以数组和链式结构的形式存储。
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储。在数组上完成数据的增删查改。
顺序表顺序表一般可以分为:
1.静态顺序表:使用定长数组存储。（提前开辟好空间）
2.动态顺序表:使用动态开辟的数组存储。（动态管理内存）
静态顺序表的结构大体如下：
动态顺序表的物理结构大体如下：
在实现功能的时候，时刻注意不要无意间修改了顺序表的内容数据，如用了++或--，可通过心得局部变量存储数据，对局部变量操作！
静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，我们先来讲讲静态顺序表。
静态顺序表：静态顺序表非重点浅了解即可，缺点：给少了用不完，给多了不够用，浪费空间，不灵活（不建议使用）
静态顺序表概括：定义一个结构体，结构体包含数据有一个数组和一个整型数据，数组负责存储数据，整型数据记录存入了多少个数据同时可以表示数组中待存入数据位置的下标。
主要函数有头删，尾删，头插，尾插，打印：
void SeqListInit(SL *ps);//初始化顺序表，传入一个结构体指针，初始化
void SeqListPushBack(SL* ps, SQDataType x);//尾插Back，在顺序表尾部插入x
void SeqListPushFront(SL* ps, SQDataType x);//头插Front，在顺序表头部插入x
void SeqListPopBack(SL* ps);//尾删Back，删去顺序表最后一个元素
void SeqListPopFront(SL* ps);//头删Front，删去顺序表第一个元素
（相应细节请看代码备注）具体看头文件：
SeqList.h 静态顺序表头文件：
#pragma one #includeusing namespace std; #define MAX_SIZE 10 //更改N的值实现数组大小改变（提高数组灵活性和可维护性） typedef int SQDataType; //更改typedef使数组类型改变（提高数组灵活性和可维护性-平台无关性） typedef struct SeqList { SQDataType a[MAX_SIZE]; int size;//用于计算存入了多少个数据 }SL; //为了C中少写struct，在C++中没有必要 void SeqListInit(SL *ps);//初始化顺序表 void SeqListPushBack(SL* ps, SQDataType x);//尾插Back void SeqListPushFront(SL* ps, SQDataType x);//头插Front void SeqListPopBack(SL* ps);//尾删Back void SeqListPopFront(SL* ps);//头删Front
SeqList.cpp 静态顺序表源文件
#include"SeqList.h"
void SeqListInit(SL *ps)
{
memset(ps->a, 0, sizeof(SQDataType) * MAX_SIZE);//用0来初始化数组元素
ps->size = 0;
}
void SeqListPushBack(SL* ps, SQDataType x)//尾插Back
{
if (ps->size >= MAX_SIZE)
{
cout << "SeqList is Full";
return;
}
//防止数据已经存满，导致越界
ps->a[ps->size] = x;
//ps->size是数组存入数据的个数，同时也是数组待存入位置的下标
ps->size++;
//重新计算计入数据个数
}
void SeqListPushFront(SL* ps, SQDataType x);//头插Front
void SeqListPopBack(SL* ps);//尾删Back
void SeqListPopFront(SL* ps);//头删Front
//静态顺序表十分简单，也非重点，这里不予描述
还有的函数大同小异，静态顺序表缺陷大，非重点。
动态顺序表：动态顺序表概述：定义结构体，结构体中包含一个指针变量和两个整型数据分别为size和capacity，指针用来动态分配空间（相当于数组），size记录数组中元素的个数同时可以作为数组中带存入数据的位置的下标，capacity是容量，用于用于检测是否需要扩容。动态顺序表通过指针动态分配空间减少浪费。相应的需要为结构体提供函数，实现初始化，头插，尾插，头删，尾删，中间插入数据，中间删除数据，查找元素，修改指定位置的数据，答应数据等功能。主要函数如下：
void SeqListInit(SL *ps);//初始化顺序表，传入一个结构体地址，初始化
void SeqListPushBack(SL* ps, SQDataType x);//尾插，在顺序表尾部插入x元素
void SeqListPushFront(SL* ps, SQDataType x);//头插，在顺序表头部插入x元素
void SeqListPopBack(SL* ps);//尾删，删去顺序表的最后一个元素
void SeqListPopFront(SL* ps);//头删，删去顺序表第一个元素
void SeqListInsert(SL* ps,int pos,SQDataType x);//在pos（顺序表中对应）位置前插入数据x
void SeqListErase(SL* ps, int pos);//删除pos（顺序表中对应）位置数据
int SeqListFind(SL* ps, SQDataType x);//查找数组元素中等于x的元素
void SeqListModity(SL* ps, int pos, SQDataType x);//修改pos位置的数值，
void SeqListPrint(SL* ps);//打印元素
（相应细节请看代码备注），具体看头文件：
SeqList.h头文件：
#pragma one #include#include using namespace std; typedef int SQDataType; //更改typedef使数组类型改变（提高数组灵活性和可维护性-平台无关性） typedef struct SeqList { SQDataType *a; int size; //有效数据个数,用于插入数据使用 int capacity; //容量，容量不够则扩容，达到动态的目的 }SL; //为了C中少写struct，在C++中没有必要 void SeqListInit(SL *ps);//初始化顺序表 void SeqListPushBack(SL* ps, SQDataType x);//尾插 void SeqListPushFront(SL* ps, SQDataType x);//头插 void SeqListPopBack(SL* ps);//尾删 void SeqListPopFront(SL* ps);//头删 void SeqListInsert(SL* ps,int pos,SQDataType x);//在pos位置前插入数据x void SeqListErase(SL* ps, int pos);//删除pos位置数据 int SeqListFind(SL* ps, SQDataType x);//查找数组元素中等于x的元素 void SeqListModity(SL* ps, int pos, SQDataType x);//修改pos位置的数值， void SeqListPrint(SL* ps);//打印元素
SeqList.cpp源文件：
#include"SeqList.h"
void SeqListInit(SL *ps)//初始化
{
ps->a = NULL;
ps->size = 0;
ps->capacity = 0;
}
void SeqListCheckCapacity(SL* ps) //扩容的函数包装
{
if (ps->size == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
//这里newcapacity并不多余！仔细看！
SQDataType* tmp = (SQDataType*)realloc(ps->a, newcapacity *sizeof(SQDataType));
if (tmp == NULL)
{
cout << "realloc failed";
exit(-1);
}
else
{
ps->a = tmp;
ps->capacity = newcapacity;
//申请成功就更新数据值
}
}
}
void SeqListPushBack(SL* ps, SQDataType x)//尾插
{
SeqListCheckCapacity(ps);
ps->a[ps->size] = x;//ps->size就是待存入数据的位置的下标
ps->size++;
}
void SeqListPushFront(SL* ps, SQDataType x)//头插
{
SeqListCheckCapacity(ps);
int end = ps->size - 1;//注意要用局部变量，不要直接对ps->size操作！
while (end >= 0)//注意数据交换的方向，数从后往前逐个后移！
{
ps->a[end + 1] = ps->a[end];
--end;
}
ps->a[0] = x;
ps->size++;
}
void SeqListPopBack(SL* ps)//尾删
{
assert(ps->size > 0);//如果没有数据，删个毛！
ps->a[ps->size - 1] = 0;
//这句是可以没有的，SeqListPrint(SL* ps)通过ps->size输出，改变ps->size的值即可
//size是顺序表数组中最后一个元素的下一个元素的下标，ps->size - 1是最后一个元素的下标
ps->size--;
//删除了一个数据，重新计算size
}
void SeqListPopFront(SL* ps)//头删Front
{
assert(ps->size > 0);//做判断，如果没有数据，删个毛！
int start = 0;
while (start < ps->size)//从前往后，数据逐个前移
{
ps->a[start - 1] = ps->a[start];
start++;
}
ps->size--;
//删除了一个数据，重新计算零
}
void SeqListInsert(SL* ps, int pos, SQDataType x)//pos前插入x，pos代表的是数组元素下标
{
assert(pos < ps->size);//只允许在有数据的部分插入数据
SeqListCheckCapacity(ps);//容量不够，则增容
int End = ps->size-1;
while (End >=pos)//将pos及往后的数据移后面一格
{
ps->a[End + 1] = ps->a[End];
End--;
}
ps->a[pos ] = x;
ps->size++;
}
void SeqListErase(SL* ps, int pos)//删除pos位置数据，pos代表的是数组元素下标
{
assert(pos < ps->size);//只允许删除已经有的数据
int start = pos + 1;
while (start <= ps->size-1)
{
ps->a[start - 1] = ps->a[start];
start++;
}
ps->size--;
//此时数组最后两个元素相等，但SeqListPrint是通过size来打印，所以最后那个元素相当于没有
}
int SeqListFind(SL* ps, SQDataType x)//查找数组元素中等于x的元素
{
for (int i = 0; i < ps->size; i++)
{
if (ps->a[i] == x)
{
return i;//找到了就返回这个位置的下标
}
}
return -1;//无效的下标
}
void SeqListModity(SL* ps, int pos, SQDataType x)//修改pose位置的数值
{
assert(pos < ps->size);//必须只能修改有效的位置
ps->a[pos] = x;
}
void SeqListPrint(SL* ps)//打印数据
{
for (int i = 0; i < ps->size; i++)
{
cout << ps->a[i] <<" ";
}
cout << endl;
}
动态顺序表缺陷：
1、还是会有浪费空间，增容也可能符出一定的性能消耗
2、在头部或者中部插入的效率比较低（时间复杂度O（N））
动态顺序表中函数实现有诸多细节，要一一注意。
链表：链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（即链表中每一个元素）组成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。链表有很多种不同的类型：单向或者双向，带头或者不带头，循环或者非循环自由组合等八类链表（2*2*2）。首先大体了解各类和特点，后面仔细介绍无头单向非循环和带头双向循环链表（重点），其余的可类比。
1. 单向或者双向：
2. 带头或者不带头（带头指针的链表不需要用到二级指针）：
3. 循环（尾结点指向头结点）或者非循环（尾结点指向NULL）：
但实际中我们主要都用的是两种链表：无头单向非循环和带头双向循环链表如下：
1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希、图的邻接表等等。另外这种结构在笔试面试中出现很多。
2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我会讲解大家就清楚了。
不带头单向非循环链表：不带头单向非循环链表结构：
单向链表由结点（结构体）组成，结构体有数据域和指针域，数据域存储数据，指针域是一个指向结构体类型的指针，起到链接每个结点的作用。
单向链表缺点：找不到前驱！只能从前往后读取信息！要对某个结点操作，必须找到他的前一个结点！所以尾插PushBack，尾删PopBack，插入元素Insert，删除元素Erase的时间复杂度都是O(N)。接口函数实现功能有：打印数据，尾插，头插，尾删，头删，查找指定元素，插入元素，删除元素等等。
无头单向非循环链表的结点定义：
（其实只要是单向链表其结点定义均一致，只是不同的操作罢了）
typedef int SLTDataType;
//更改typedef使结构体中Data类型改变（提高数组灵活性和可维护性-平台无关性）
typedef struct SListNode//单向链表的节点
{
SLTDataType Data;
SListNode* next;
//定义一个指向下一个结构体的指针，起串联的作用
//结构体中不能再次定义结构体（套娃），但可以有指针
}SLTNode;
//为了C中少写struct，在C++中没有必要
无头单向非循环链表主要函数物理结构（代码实现原理）：
删除指定位置元素（代码实现原理）：
插入元素（代码实现原理）：
以下是标准的单向链表的头文件和源文件（备注有详细解释）单向链的易错点和难点，在本部分结尾处有总结
链表由结点和函数组成，头文件中起始部分是结构体定义（结点），后一部分是函数定义
SList.h头文件：
#pragma once #includeusing namespace std; typedef int SLTDataType; //更改typedef使结构体中Data类型改变（提高数组灵活性和可维护性-平台无关性） typedef struct SListNode//单向链表的节点 { SLTDataType Data; SListNode* next; //定义一个指向下一个结构体的指针，起串联的作用 //结构体中不能再次定义结构体（套娃），但可以有指针 }SLTNode; //为了C中少写struct，在C++中没有必要 void SListPrint(SLTNode* phead);//打印 //void SListPushBack(SLTNode* phead, SLTDataType x)//传值尾插是标准错误 void SListPushBack(SLTNode** pphead, SLTDataType x);//尾插 //也可以用void SListPushBack(SLTNode*& phead, SLTDataType x)；//最好用 void SListPushFront(SLTNode **pphead,SLTDataType x);//头插 //这里需要改变头指针，所以要传二级指针 void SListPopBack(SLTNode **pphead);//尾删 //如果是只有一个节点需要释放*pphead，要改变头指针，传二级指针 void SListPopFront(SLTNode **pphead);//头删 //需要改变头指针，用二级指针 SLTNode* SListFind(SLTNode* phead,SLTDataType x);//在链表中查找x元素 //不用改变头指针，用一级指针 void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);//插入元素 //在pos前面插入x，pos通常是函数查找链表数据返回的地址 void SListErase(SLTNode** pphead, SLTNode* pos);//删除pos位置元素 //pos通常是函数查找链表数据返回的地址 //void SListInsert(SLTNode* phead, int i, SLTDataType x);//插入元素，在i位置前插入x（i是下标）不太规范的写法 //void SListErase(SLTNode* phead,int i);//删除i位置的元素（i是下标）不太规范的写法
SList.cpp源文件：
（注意想要在链表中存储数据，必须是要一节点的形式存储进去，所以在写链表的时候都会包装一个函数：实现将x包装成结点并返回结点地址的函数，如下第一个函数）
#include"SList.h"
SLTNode* BuySLTNode(SLTDataType x)//构造节点的函数（包装）
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
//首先开辟空间存储数据
newnode->next = NULL;
newnode->Data = x;//建立相应的节点
return newnode;
}
void SListPrint(SLTNode* phead)//打印链表数据
{
SLTNode* cur = phead;
//cur是当前位置的英文（见名思意）将头地址给cur，此时cur指向第一个节点
while (cur != NULL)//当cur==NULL的时，即为最后一个节点，停止打印
{
cout << cur->Data << "->";
cur = cur->next;
//cur->next为下个节点的首地址，cur=cur->next执行后，cur指向下一个节点的首地址
}cout << "NULL" << endl;
}
//void SListPushBack(SLTNode* phead, SLTDataType x)//传值尾插标准错
void SListPushBack(SLTNode** pphead, SLTDataType x) //尾插
//也可以用void SListPushBack(SLTNode*& phead, SLTDataType x)；最好用
{
SLTNode* newnode = BuySLTNode(x);//调用函数构造节点，返回首地址
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
SLTNode* tail = *pphead;//tail是尾部的意思
while (tail->next != NULL)//这里容易写成（tail!=NULL）
{
tail = tail->next;
}//在最后一个节点停止，出循环后tail是最后节点的首地址（尾节点的next==NULL）
tail->next = newnode;
//newnode链接在表尾
}
}
void SListPushFront(SLTNode** pphead, SLTDataType x)//头插,要么传二级指针，要么传指针引用
{
SLTNode* newnode = BuySLTNode(x);//调用函数构造节点，返回首地址
newnode->next = *pphead;
*pphead = newnode;
}
void SListPopBack(SLTNode** pphead)//尾删
{
//如果链表有没有或者只有一个节点要特别考虑
if (*pphead == NULL)
{
return;
}
else if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
//用两个指针找到最后一个节点的前一个节点（双指针的玩法）
SLTNode* prev = NULL;
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
free(tail);
prev->next = NULL;
}
}
void SListPopFront(SLTNode** pphead)//头删
{
SLTNode* next = (*pphead)->next;
//释放之前需要保存地址，否则整个链表全部丢失！
//*和->都是解引用的意思，优先及相同需要加上括号，否组可能会报错
//*解就是对不同类型解引用（取不同的字节数）
free(*pphead);
*pphead = next;
//头指针指向下一个节点的首地址
}
SLTNode* SListFind(SLTNode* phead, SLTDataType x)//在链表中查找x元素
{
SLTNode* cur = phead;
while (cur) //cur非空即为真（简洁）
{
if (cur->Data == x)
{
return cur;
}
cur = cur->next;//但其实如果链表中有多个x会出现问题
}
return NULL;
//没找到返回空
}
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)//插入元素
//在pos前面插入x，pos通常是函数查找链表数据返回的地址
{
//如过pos刚好是首地址，相当于头插，要特殊考虑
if (pos == *pphead)
{
SListPushFront(pphead, x);
}
else
{
SLTNode* prev = *pphead;
//用一个指针变量保存头指针的值，切记不能直接对头指针操作，会改变头指针！
while (prev->next != pos)
{
prev = prev->next;
}
SLTNode* newnode = BuySLTNode(x);
prev->next = newnode;
newnode->next = pos;
}
}
void SListErase(SLTNode** pphead, SLTNode* pos)//删除pos位置元素
//pos通常是函数查找链表数据返回的地址
{
//如过pos刚好是首地址，相当于头插，要特别考虑
if (pos == *pphead)
{
SListPopFront(pphead);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
}
}
易错点和重点大总结：
1、二级指针的使用：在头插，尾插，头删，尾删功能的函数实现上出现修改头指针的情况。这时的指针不能传值！（如：void SListPushBack(SLTNode* phead, SLTDataType x)；//尾插函数错误写法），传值传递的是副本，不会改变原来的指针。所以我么会用传地址或引用，如下：
void SListPushBack(SLTNode** pphead, SLTDataType x)；//传地址
void SListPushBack(SLTNode*& phead, SLTDataType x)；//传引用
引用很好理解，引用即是别名，别名就是本身。这里解释传地址的方式：传地址由于传是指针的地址，所以用到了二级指针，为了方便理解，如下示图：pphead是指针变量的地址，*pphead是pphead地址解引用一次，也就是指针值本身，而*pphead里面存放的是结构体的地址，可通过*pphead访问结构体。
需注意，两种函数（传地址方式和传引用方式）的时候传实参也是不同的。
2、尾插：尾插函数在定义的时候需要考虑链表本身一个节点都没有得情况，否则会bug（会看函数体自行体悟）尾删：需要考虑到空链表和指头一个链表的情况，否则会bug（会看函数体自行体悟）此外删除pos位置元素的函数和在pos（节点地址）前插入元素的函数都需要考虑pos是第一个节点的情况。当然这些问题时建立在上文的函数实现上的，不同函数实现注意点不同。最重要实现函数的时候需要考虑到特殊情况是否满足要求———即空链表是否满足？
3、SLTNode* next = (*pphead)->next;
*和->都是解引用的意思，优先及相同需要加上括号，否组可能会报错
带头双向循环链表结构及作用：
带头双向循环链表：结构在链表中最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但这个链表设计的是非常完美的，后续代码实现中会发现此结构的优势很多。
带头双向循环链表概述：
带头双向循环链表是由结点组成，第一个称为哨兵位的头节点head，（这里简述哨兵位的作用，哨兵位其实是为了方便操作而引入的结点，不存储有效数据，在很多时候,我们处理某个节点需要用到它的前驱节点，比如删除链表的某个节点,对于没有哨兵的单链表，当待删除的节点为链表的第一个节点,，由于没有前驱,需要进行特殊处理.从而代码的复杂性增加.而如有哨兵节点,则第一个节点的处理方式与其他节点相同,可以统一进行处理。）带头双向循环链表后续就是由结点组成，结点中由有效数据成员和两个指向自身类型的结构体指针，两个指针分别叫做结点的前驱和后继，分别指向上一个结点和下一个结点。每个结点都是一前一后链接在链表上的，下面是结点的定义：
typedef int LTDataType;//提高维护性和平台无关性
struct ListNode
{
ListNode* next;//后继，指向后一个指针
ListNode* prev;//前驱，指向前一个结点
LTDataType Data;//存储有效数据成员
};
本部分思路为：先弄清楚带头双向循环链表的实现，接着介绍如何在10分钟内完整实现带头双向循环链表，老规矩！链表的增删查改功能请看头文件和源文件！代码精华会在后面详细解答！
List.h头文件：
#pragma once #include#include using namespace std; typedef int LTDataType;//提高维护性和平台无关性 struct ListNode { ListNode* next;//后继，指向后一个指针 ListNode* prev;//前驱，指向前一个结点 LTDataType Data;//存储有效数据成员 }; void ListInit(ListNode*& phead);//初始化 void ListPrint(ListNode*phead);//打印链表 void ListDestory(ListNode* phead);//消除数据 void ListPushBack(ListNode* phead, LTDataType x);//尾插 void ListPushFront(ListNode* phead, LTDataType x);//头插 void ListPopBack(ListNode* phead);//尾删 void ListPopBack(ListNode* phead);//头删 ListNode* ListFind(ListNode* phead, LTDataType x);//查找存有x的结点，并返回该节点地址 void ListInsert(ListNode* pos, LTDataType x); //在pos位置前插入存有x的结点,pos一般是ListFind函数查找返回的地址 void ListErase(ListNode* pos); //删除pos位置的结点，pos一般是ListFind函数查找返回的地址 bool ListEmpty(ListNode* phead);//判断空 int ListSize(ListNode* phead);//判断大小
List.cpp源文件：
（注意想要在链表中存储数据，必须是要一节点的形式存储进去，所以在写链表的时候都会包装一个函数：实现将x包装成结点并返回结点地址的函数，如下第一个函数）
#include"List.h"
ListNode* BuyListNode(LTDataType x) //创造结点功能的函数包装
{
ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
newnode->Data = x;
newnode->next = NULL;
newnode->prev = NULL;
return newnode;
}
void ListInit(ListNode*& phead)//初始化,改变指针用指针和引用均可，此处用引用
{
phead = BuyListNode(0);//head哨兵位头节点，不存有效数据
phead->next = phead;
phead->prev = phead;
//head哨兵位指针都是自己指向自己，很完美的设计，后面详解
}
void ListPrint(ListNode* phead)//打印链表
{
assert(phead);//排除空指针闯传入
ListNode* cur = phead->next;
while (cur != phead)
{
//当cur=phead时说明刚好遍历一次或者该链表没有数据
cout << cur->Data<<" ";
cur = cur->next;
}
cout << endl;
}
void ListIniDestory(ListNode* phead)//消除数据
{
assert(phead);//排除空指针闯传入
ListNode* cur = phead->next;
while (cur != phead)
{
ListNode* next = cur->next;
free(cur);
cur = next;
}//要每个指针都释放，而不是不负责的只释放phead
free(phead);
phead = NULL;
}
void ListPushBack(ListNode* phead, LTDataType x)//尾插
{
//循环链表中哨兵位的prev指针指向的就是尾结点！
assert(phead);//排除空指针闯传入
ListNode* tail = phead->prev;//tail就是尾结点地址
ListNode* newnode = BuyListNode(x);//将x包装成结点
//三个结点之间链接！phead newnode tail
tail->next = newnode;
newnode->prev = tail;
newnode->next = phead;
phead->prev = newnode;
}
void ListPushFront(ListNode* phead, LTDataType x)//头插
{
assert(phead);//排除空指针闯传入
ListNode* newnode = BuyListNode(x);//将x包装成结点
ListNode* first = phead->next;//first就是第一个结点地址
//三个结点之间链接！phead,first,newnode
phead->next = newnode;
newnode->prev = phead;
newnode->next = first;
first->prev = newnode;
}
void ListPopBack(ListNode* phead)//尾删
{
assert(phead);//排除空指针闯传入
assert(phead->next != phead);//只有哨兵位头节点不能删
ListNode* tail = phead->prev;//tail就是尾结点地址
ListNode* prev = tail->prev;//prev是倒数第二个结点的地址
prev->next = phead;
phead->prev = prev;
free(tail);
tail = NULL;//别忘了释放指针并置空
}
void ListPopFront(ListNode* phead)//头删
{
assert(phead);//排除空指针闯传入
assert(phead->next != phead);//只有哨兵位头节点不能删
ListNode* first = phead->next;//first就是第一个结点地址
ListNode* second = first->next;//second就是第二个结点地址
phead->next = second;
second->prev = phead;
free(first);
first = NULL;//别忘了释放指针并置空
}
ListNode* ListFind(ListNode* phead, LTDataType x)//查找存x的结点,返回该结点的地址
{ //ListFind函数是可以修改结点有效数据的，对函数返回值解引用"->"可修改特定位置的数值
assert(phead);//排除空指针闯传入
ListNode* cur = phead->next;
while (cur != phead)//cur=phead就遍历一次或者链表为空链表
{
if (cur->Data == x)
{
return cur;//找到x的结点返回结点地址
}
cur = cur->next;
}return NULL;
}
//在pos位置前插入存有x的结点,pos一般是ListFind函数查找返回的地址
void ListInsert(ListNode* pos, LTDataType x)
{
assert(pos);//排除空指针闯传入
ListNode* prev = pos->prev;
ListNode* newnode = BuyListNode(x);
//三个结点之间链接！prev newnode pos
prev->next=newnode;
newnode->prev = prev;
newnode->next = pos;
pos->prev = newnode;
}
//删除pos位置的结点，pos一般是ListFind函数查找返回的地址
void ListErase(ListNode* pos)
{
assert(pos);//排除空指针闯传入
ListNode* prev = pos->prev;
ListNode* next = pos->next;
//找到pos的前一个prev，和后一个next，链接next和prev释放free
prev->next = next;
next->prev = prev;
free(pos);
pos = NULL;
}
精华和细节：
1、一分钟之内完整实现带头双向循环链表：不难发现所谓头删，尾删，头插，尾插其实不过是最后两个再pos位置删除插入函数（ListInsert，ListErase）的特殊形式，所以实现带头双向循环链表的头删，尾删，头插，尾插函数只需要写两个再pos位置删除插入函数（ListInsert，ListErase）的函数其余就行啦！看cpp代码！
void ListPushBack(ListNode* phead, LTDataType x)//尾插
{
assert(phead);//排除空指针闯传入
ListInsert(phead->prev，x);
}
void ListPushFront(ListNode* phead, LTDataType x)//头插
{
assert(phead);//排除空指针闯传入
ListInsert(phead->next,x);
}
void ListPopBack(ListNode* phead)//尾删
{
assert(phead);//排除空指针闯传入
ListErase(phead->prev);
}
void ListPopFront(ListNode* phead)//头删
{
assert(phead);//排除空指针闯传入
ListErase(phead)一句化搞定上面所有，当然还是要断言以下的
}
2、带头双向循环链表的结构完美性：任意位置都可以删除插入都是O(1),但查找还是O(N)。以后查找会用平衡搜索树（AVL树和红黑树），哈希表，B树，B+树系列，跳表，布隆过滤器，位图等。此外会发现在无头单向非循环链表中，头插尾插头删尾删等函数需要考虑链表的特殊情况，如链表只有一个结点或者空链表的情况都需要单独考虑，但在带头双向循环链表中是不需要考虑的（不信回试），带头双向循环链表的代码实现满足一般情况也能满足特殊情况！所以写代码的时候只需要按下面这个结构写：
3、头插，尾插的代码实现最好的思路是，找到插入的结点newnode和前一个结点prev和后一个结点next，然后再对这三个结点newnode，prev，next进行链接，这样的链接方式不需要考虑链接顺序，思路清晰不会出错。直接插入的方式代码简单一丢丢，需要注意链接顺序，必须先链接后面再链接前面，否则会出现修改了前面的指针找不到后面的指针的情况，以头插为例子：
//正确写法：
void ListPushFront(ListNode* phead, LTDataType x)//头插
{
assert(phead);//排除空指针闯传入
ListNode* newnode = BuyListNode(x);//将x包装成结点
newnode->next=phead->next;//先把后面链接
phead->next->prev = newnode;//先把后面链接
phead->next = newnode;//再链接前面
newnode->prev = phead;//再链接前面
}
//错误写法：
void ListPushFront(ListNode* phead, LTDataType x)//头插
{
assert(phead);//排除空指针闯传入
ListNode* newnode = BuyListNode(x);//将x包装成结点
phead->next = newnode;//先链接了前面
newnode->prev = phead;//先链接了前面
newnode->next=phead->next;//此处出现问题phead->next就是newnode本身！
phead->next->prev = newnode;//phead->next->prev是phead
//可以发现已经乱套了！
}
4、哨兵位头节点中的哨兵位的头节点一定不要存有效数据！存了会在某些类型问题上出现问题：
typedef int LTDataType;
struct ListNode
{
ListNode* next;
LTDataType Data;
};
不少人希望通过再哨兵位数据中存储数组中元素个数来达到遍历的方便，但在一些情况会出现问题，当这里LTDataType是int类型一般没有问题，但LTDataType是char类型的时候，当数组元素超过128时，再插入数据就会出现溢出现象，此外还有其他情况也可能出现问题，就不在此一一列举了。
5、assert断言的好处，未来在大厂工作，代码少则都时万行，assert的好处在于程序出现问题，会告诉你出发了那个断点，当程序代码多时，告诉你错误的位置好处不言而喻，维护性大大提高。
欢迎大家指正，有任何问题欢迎评论区提问哦！创作不易，点赞收藏是对我最大的支持~
