双向循环链表
/**
* @file name: 双向链表接口设计
* @brief
* @author [email protected]
* @date 2024/04/24
* @version 1.0 ：版本
* @property ：
* @note
* CopyRight (c) 2023-2024 [email protected] All Right Reseverd
*/
构造双向循环链表的结点
// 指的是双向循环链表中的结点有效数据类型，用户可以根据需要进行修改
typedef int DataType_t;
// 构造双向循环链表的结点,链表中所有结点的数据类型应该是相同的
typedef struct DoubleLinkedList
{
DataType_t data; // 结点的数据域
struct DoubleLinkedList *prev; // 直接前驱的指针域
struct DoubleLinkedList *next; // 直接后继的指针域
} DoubleCirLList_t;
功能函数：创建空双向循环链表
DoubleCirLList_t *DoubleCirLList_Create(void)
{
// 1.创建一个头结点并对头结点申请内存
DoubleCirLList_t *Head = (DoubleCirLList_t *)calloc(1, sizeof(DoubleCirLList_t));
if (NULL == Head)
{
perror("Calloc memory for Head is Failed");
exit(-1);
}
// 2.对头结点进行初始化，头结点是不存储数据域，指针域指向自身即可，体现“循环”
Head->prev = Head;
Head->next = Head;
// 3.把头结点的地址返回即可
return Head;
}
功能函数：创建新的结点，并对新结点进行初始化（数据域 + 指针域）
DoubleCirLList_t *DoubleCirLList_NewNode(DataType_t data)
{
// 1.创建一个新结点并对新结点申请内存
DoubleCirLList_t *New = (DoubleCirLList_t *)calloc(1, sizeof(DoubleCirLList_t));
if (NULL == New)
{
perror("Calloc memory for NewNode is Failed");
return NULL;
}
// 2.对新结点的数据域和指针域（2个）进行初始化,指针域指向结点自身，体现“循环”
New->data = data;
New->prev = New;
New->next = New;
return New;
}
功能函数：在头部插入新元素
bool DoubleCirLList_HeadInsert(DoubleCirLList_t *Head, DataType_t data)
{
DoubleCirLList_t *new = DoubleCirLList_NewNode(data);
DoubleCirLList_t *Phead = Head->next;
if (Head->next == Head) // empty list 链表为空的情况
{
Head->next = new;
return true;
}
Phead->prev->next = new; // normal situation 普通情况
new->prev = Phead->prev;
new->next = Phead;
Phead->prev = new;
Head->next = new;
return true;
}
功能函数：在尾部插入新元素
bool DoubleCirLList_TailInsert(DoubleCirLList_t *Head, DataType_t data)
{
DoubleCirLList_t *new = DoubleCirLList_NewNode(data);
DoubleCirLList_t *Phead = Head->next->prev; // 临时记录尾节点的位置
if (Head->next == Head) // judge is the null 链表为空的情况
{
Head->next = new;
return true;
}
new->prev = Phead; // as the normal situation,insert the last node 普通情况，在尾部插入节点
Phead->next = new;
new->next = Head->next;
Head->next->prev = new;
return true;
}
功能函数：在指定位置插插入新元素
bool DoubleCirLList_DestInsert(DoubleCirLList_t *Head, DataType_t destval, DataType_t data)
{
DoubleCirLList_t *Phead = Head->next; // 临时记录当前节点的位置
// DataType_t i = Head->data;
DoubleCirLList_t *new = DoubleCirLList_NewNode(data);
if (Head->next == Head) // judge the empty list 链表为空的情况
{
printf("The list is empty.\n");
return false;
}
while (destval != Phead->data) // as the normal situation,find the destval找到目标值
{
Phead = Phead->next;
if (Phead == Head->next)
{
printf("There is no destination value.\n"); // 遍历完成以后仍找不到目标值，就退出
return false;
}
}
new->next = Phead->next; // 如果存在目标值，则进行插入操作,因为是循环，因此头插，尾插都能包络
Phead->next->prev = new;
new->prev = Phead;
Phead->next = new;
return true;
}
功能函数：删除首元素
bool DoubleCirLList_HeadDel(DoubleCirLList_t *Head)
{
// 对链表的首结点的地址进行备份
DoubleCirLList_t *Phead = Head->next;
if (Head->next == Head) // 判断当前链表是否为空，为空则直接退出
{
printf("current linkeflist is empty!\n");
return false;
}
if (Head->next->next == Head->next) // 判断当前链表是否仅一个元素
{
Head->next = Head;
Phead->next = NULL;
Phead->prev = NULL;
free(Phead);
}
else // delete the head 普通情况，则进行删除首节点操作
{
Phead->prev->next = Phead->next;
Phead->next->prev = Phead->prev;
Head->next = Phead->next;
Phead->next = NULL;
Phead->prev = NULL;
free(Phead);
}
return true;
}
功能函数：删除尾元素
bool DoubleCirLList_TailDel(DoubleCirLList_t *Head)
{
// 对链表的尾结点的地址进行备份
DoubleCirLList_t *Phead = Head->next->prev;
if (Head->next == Head) // 判断当前链表是否为空，为空则直接退出
{
printf("current linkeflist is empty!\n");
return false;
}
if (Head->next->next == Head->next) // 判断当前链表是否仅一个元素
{
Phead->next = NULL;
Phead->prev = NULL;
Head->next == Head;
free(Phead);
}
else
{
Phead->prev->next = Head->next; // 普通情况下，删除尾节点
Head->next->prev = Phead->prev;
Phead->next = NULL;
Phead->prev = NULL;
free(Phead);
}
return true;
}
功能函数：删除目标值元素
bool DoubleCirLList_MidDel(DoubleCirLList_t *Head, DataType_t destval)
{
DoubleCirLList_t *Phead = Head->next; // 对链表的当前结点的地址进行备份
if (Head->next == Head) // 判断当前链表是否为空，为空则直接退出
{
printf("current linkeflist is empty!\n");
return false;
}
while (Phead->data != destval) // find the specific node找到指定值的节点
{
Phead = Phead->next;
if (Phead == Head->next)
{
printf("There is no destination value.\n"); // 遍历完成以后仍找不到目标值，就退出
return false;
}
}
if (Phead == Head->next) // 删除目标值位于首节点时
{
if (Phead->next == Head->next) // 链表仅单个元素时
{
Head->next = Phead;
Phead->prev = NULL;
Phead->next = NULL;
}
else // 链表不止单个元素时
{
Phead->prev->next = Phead->next;
Phead->next->prev = Phead->next;
Head->next = Phead->next;
Phead->prev = NULL;
Phead->next = NULL;
}
free(Phead);
}
else // 如果存在目标值，且目标值不位于首节点时，进行删除操作
{
Phead->prev->next = Phead->next;
Phead->next->prev = Phead->prev;
Phead->prev = NULL;
Phead->next = NULL;
free(Phead);
}
return true;
}
功能函数：遍历链表
bool DoubleCirLList_Print(DoubleCirLList_t *Head)
{
DoubleCirLList_t *Phead = Head->next; // 对链表头结点的地址进行备份
if (Head->next == Head) // 判断当前链表是否为空，为空则直接退出
{
printf("current linkeflist is empty!\n");
return false;
}
// 从首结点开始遍历
do
{
// 输出头结点的直接后继的数据域
printf("data = %d ", Phead->data);
Phead = Phead->next;
} while (Phead != Head->next);
return true;
}
主函数，测试各功能块：
int main(int argc, char const *argv[])
{
DoubleCirLList_t *H = DoubleCirLList_Create();
DoubleCirLList_TailInsert(H, 10);
DoubleCirLList_TailInsert(H, 20);
DoubleCirLList_HeadInsert(H, 30);
DoubleCirLList_HeadInsert(H, 50);
DoubleCirLList_DestInsert(H, 30, 40);
DoubleCirLList_Print(H); // 测试插入功能函数
printf("1\n");
DoubleCirLList_HeadDel(H);
DoubleCirLList_Print(H); // 测试删除首元素
printf("2\n");
DoubleCirLList_TailDel(H);
DoubleCirLList_Print(H); // 测试删除尾元素
printf("3\n");
DoubleCirLList_MidDel(H, 10);
DoubleCirLList_Print(H); // 测试删除目标元素
printf("3\n");
return 0;
}