// 方便访问，创建一个带头结点的双向循环链表
// 链表数据域取别名方便修改
typedef int DataType_t;
// 构造双向循环链表的结点
typedef struct DoubleCircularLList
{
DataType_t data; // 数据域
struct DoublLingkedList *prev; // 直接前驱指针域
struct DoublLingkedList *next; // 直接后继指针域
} DoublCirLList_t;
// 创建空的循环链表，有头结点（要申请头节点的内存空间）
DoublCirLList_t *DoublCirLList_Create(void)
{
// 创建一个头节点并申请内存
DoublCirLList_t *Head = (DoublCirLList_t *)calloc(1, sizeof(DoublCirLList_t *));
if (Head == NULL)
{
perror("calloc menmory Head is failed!!!\n"); // 申请不成功做错误处理
exit(-1); // 程序退出
}
Head->prev = Head; // 头节点只用得到后继指针域，前驱指针是用不到的
Head->next = Head; // 两个指针域都指向自身结构体的地址体现循环
return Head; // 返回头结点的地址
}
/****************************************************************
* name；DoublCirLList_NewNode
* function：创建新的待插入的结点
* parameter；
* @DataType_t data
* ReValue；New
* author；小北blog
* attention；
* date；2024.04.25
* Copyright(c) 2024 [email protected] All rights Reserved
*****************************************************************/
// 创建新的待插入的结点，并对新的节点进行初始化（前驱后继指针域 数据域）
DoublCirLList_t *DoublCirLList_NewNode(DataType_t data)
{
// 创建一个新结点并申请内存
DoublCirLList_t *New = (DoublCirLList_t *)calloc(1, sizeof(DoublCirLList_t *));
if (New == NULL)
{
perror("calloc menmory NewNode is failed!!!\n"); // 申请不成功做错误处理
exit(-1); // 程序退出
}
New->data = data;
New->prev = New; // 两个指针域都指向自身结构体的地址体现循环
New->next = New;
return New; // 返回新结点的地址
}
/****************************************************************
* name；DoublCirLList_Insert
* function：双向循环链表的插入处理
* parameter；
* @DoublCirLList_t *Head
* @DataType_t data
* @unsigned int DestPosition
* ReValue；none
* author；小北blog
* attention；
* date；2024.04.25
* Copyright(c) 2024 [email protected] All rights Reserved
*****************************************************************/
// 双向循环链表中插入新的结点分为头部中间插入
void *DoublCirLList_Insert(DoublCirLList_t *Head, DataType_t data, unsigned int DestPosition)
{
// 传入的int DestPosition是想插入的位置
int DestPosition; // 表示插入的位置为首结点的左边
int cnt = 0; // 记录结点位数
DoublCirLList_t *Phead = Head->next; // 备份首结点地址,备份地址不用返回值
// 传入的数据存入到创建的新节点数据域当中
DoublCirLList_t *New = DoublCirLList_NewNode(data);
// 判断双向循环链表为空的情况
if (Head->next == Head)
{
Head->next = New; // 链表插入该结点为首结点
return;
}
else if (DestPosition = 1)
// 链表非空的情况并且头部插入的情况(插入原本首结点的左边)
{
New->next = Head->next; // 首先让新节点的后继指针指向首结点
Head->next->prev = New; // 然后再首结点的前驱指向新节点
Head->next = New; // 最后让头结点指向新节点作为首结点
return;
}
else
// 减少计算次数，仅计算到需要插入的位置
// 遍历找到目标结点
for (cnt = 0; cnt <= DestPosition; cnt++)
{
Phead = Phead->next; // 该动作表示遍历到了目标结点，此时Phead地址为目标结点地址
}
New->next = Phead; // 链接目标结点的地址到新结点的直接后继上
Phead->prev = New; // 链接目标前驱地址指向新结点
New->prev = Phead->prev; // 新结点的直接前驱指针指向目标结点地址
Phead->prev->next = New; // 目标结点的直接前驱地址指向新结点
}
总结：
函数思想：把双向链表的头部插入，中间插入，尾部插入封装成一个函数接口，方便代码移植
1.解决一个双向循环链表的过程，首先需要构造一个双向循环的结点（结构体数据类型类型），相当于数组当中的元素，然后可以根据这个结点的数据类型取别名方便代码书写，既然是双向循环链表，那么结构体里面的元素必须是有能存数据的数据区域，表示循环那必然也存有一个之前前一个结点的指针和指向后一个结点的指针，这是双向循环链表循环。为了表现出循环，当链表中还没有结点的时候或者在创建定义初始化结点的时候结构体里面的指针类型都应该指向自身，而不是指向NULL。
2.第一步已经构造好了双向循环链表，那么定义创建并初始化一个头结点用来指向链表，方便查找首结点。用calloc创建可以省去一些步骤，为头结点申请内存空间，当然头结点也是一个结点，只是不存储数据。表示循环直接前驱后继指针都指向自身。
3.创建新的结点链接头结点用来插入链表当中，当然链表当中原先是没结点的，除非定义很多个结点互相链接，当然链接的意义不在于此。新结点和头结点多了数据域参数，需要传入实参，一样的申请成功做错误处理，然后指针区域两个指针都指向自己，并且传入的参数传到数据区域。
4.创建函数接口，传入的实参要有头结点的指针，后面要备份该指针防止丢失，还要传入数据，还有要插入的位置。
准备工作都做好了，判断链表是否为空，空的话传入的新结点就为首结点，头结点的next指针指向新结点的地址，函数返回。如果非空的情况有两种，第一种是更换首结点，也就是把新结点接入到原来的首结点前面，让头结点指向新结点。第二点情况就是插入到中间和尾部，但是由于是双向循环链表，所以可以算是只有中间插入的情况，为了减少计算次数，用循环遍历到需要插入的结点前面时就不必要循环一次循环，用一个整数变量记录循环到目标函数的次数（第几个结点的位置），到此循环退出，检验有时间再弄！！！