目录 [TOC]
/**
* @file name: main.c
* @brief 双向循环链表的接口设计
* @author [email protected]
* @date 2024/04/24
* @version 1.0 :版本
* @property :属性介绍
* @note 补充 注意 说明
* CopyRight (c) 2023-2024 [email protected] All Right Reseverd
*/
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
// 指的是双向链表中的结点有效数据类型,用户可以根据需要进行修改
typedef int DataType_t;
// 构造双向链表的结点,链表中所有结点的数据类型应该是相同的
typedef struct DoubleCirtureLinked
{
DataType_t data; // 结点的数据域
struct DoubleCirtureLinked *prev; // 直接前驱的指针域
struct DoubleCirtureLinked *next; // 直接后继的指针域
} DoubleCirLinked;
# 创建一个空双向链表
/**
* @function name: DoubleLList_Create
* @brief 创建一个空双向链表,空链表应该有一个头结点,对链表进行初始化
* @param 介绍函数参数 void
* @retval void
* @date 2024/04/23
* @version 1.0 :版本
* @note 补充 注意 说明
*/
// 创建一个空双向链表,空链表应该有一个头结点,对链表进行初始化
DoubleCirLinked *DoubleLList_Create(void)
{
DoubleCirLinked *Head = (DoubleCirLinked *)calloc(1, sizeof(DoubleCirLinked));
if (NULL == Head)
{
perror("Calloc memory for Head is Failed");
exit(-1);
}
// 2.对头结点进行初始化,头结点是不存储数据域,指针域指向NULL
Head->prev = Head;
Head->next = Head;
// 3.把头结点的地址返回即可
return Head;
}
创建一个新的结点
// 创建新的结点,并对新结点进行初始化(数据域 + 指针域)
/**
* @function name: DoubleLList_NewNode
* @brief // 1.创建一个新结点并对新结点申请内存
* @param 介绍函数参数 @data
* @retval void
* @date 2024/04/24
* @version 1.0 :版本
* @note 补充 注意 说明
*/
DoubleCirLinked *DoubleCircLList_NewNode(DataType_t data)
{
// 1.创建一个新结点并对新结点申请内存
DoubleCirLinked *New = (DoubleCirLinked *)calloc(1, sizeof(DoubleCirLinked));
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;
}
#头插
/**
* @function name: DoubleLList_NewNode
* @brief 在列表头部插入新结点
* @param 介绍函数参数 @head @data
* @retval bool
* @date 2024/04/23
* @version 1.0 :版本
* @note 补充 注意 说明
*/
bool DoubleCirLList_HeadInsert(DoubleCirLinked *Head, DataType_t data)
{
// 对链表的头文件的地址进行备份
DoubleCirLinked *Phead = Head->next;
// 1.创建新的结点,并对新结点进行初始化
DoubleCirLinked *New = DoubleCircLList_NewNode(data);
if (NULL == New)
{
printf("can not insert new node\n");
return false;
}
// 2.判断链表是否为空,如果为空,则直接插入即可
if (Head == Head->next)
{
Head->next = New;
New->next = New;
return true;
}
// 3.如果链表为非空,则把新结点插入到链表的头部
New->prev = Phead->prev; // 新结点的prev指针指向尾结点的地址
Phead->prev->next = New; // 尾结点的next指针指向新结点的地址
New->next = Head->next; // 新结点的next指针指向原首结点的地址
Head->next->prev = New; // 原首结点的prev指针指向新结点的地址
Head->next = New; // 头结点的next指向新结点的地址
return true;
}
尾插
/**
* @function name: DoubleLList_t_TailInsert
* @brief 在列表尾部插入新结点
* @param 介绍函数参数 @head @data
* @retval bool
* @date 2024/04/23
* @version 1.0 :版本
* @note 补充 注意 说明
*/
bool DoubleLList_t_TailInsert(DoubleCirLinked *Head, DataType_t data)
{
// 1.创建新的结点,并对新结点进行初始化
DoubleCirLinked *Phead = Head->next;
DoubleCirLinked *New = DoubleCircLList_NewNode(data);
if (NULL == New)
{
printf("can not insert new node\n");
return false;
}
// 2.判断链表是否为空,如果为空,则直接插入即可
if (Head == Head->next)
{
Head->next = New;
return true;
}
New->prev = Phead->prev;
Phead->prev->next = New;
New->next = Head->next;
Head->next->prev = New;
return true;
}
中间位置插入
/**
* @function name: DoubleLList_t_DestInsert
* @brief 在列表任意部插入新结点
* @param 介绍函数参数 @head @data @dest
* @retval bool
* @date 2024/04/23
* @version 1.0 :版本
* @note 补充 注意 说明
*/
bool DoubleCirLList_DestInsert(DoubleCirLinked *Head, DataType_t destval, DataType_t data)
{
// 对链表的头文件的地址进行备份
DoubleCirLinked *Phead = Head;
// 1.创建新的结点,并对新结点进行初始化
DoubleCirLinked *New = DoubleCircLList_NewNode(data);
if (NULL == New)
{
printf("can not insert new node\n");
return false;
}
// 2.判断链表是否为空,如果为空,则直接插入即可
if (NULL == Head->next)
{
Head->next = New;
return true;
}
// 3.如果链表为非空,则把新结点插入到双向链表的指定位置
while (Phead->next) // 遍历找到目标结点进行后插
{
Phead = Phead->next;
if (Head->next == Phead->next || Phead->data == destval)
{
break;
}
}
// 如果遍历链表找不到目标结点,则退出即可
if (Phead->next == Head->next && Phead->data != destval)
{
printf("dest node is not found\n");
return false;
}
// 如果遍历链表找到目标结点,则有三种情况(头部插入 尾部插入 中间插入)
if (Phead->next == Head->next) // 进行尾插
{
New->prev = Phead; // 新结点的prev指针指向原尾结点地址
Phead->next = New; // 尾结点的next指针指向新结点地址
New->next = Head->next; // 新结点的next指针指向首结点的地址
Head->next->prev = New; // 首结点的prev指针指向新结点的地址
}
else
{
New->next = Phead->next; // 新结点的next指向目标结点的直接后继结点的地址
Phead->next->prev = New; // 目标结点的直接后继结点的prev指针指向新结点
New->prev = Phead; // 新结点的prev指向目标结点的地址
Phead->next = New; // 目标结点的next指针指向新结点
}
return true;
}
头删
/**
* @function name: DoubleLList_t_HeadDel
* @brief 删除首结点
* @param 介绍函数参数 @head @data
* @retval bool
* @date 2024/04/23
* @version 1.0 :版本
* @note 补充 注意 说明
*/
bool DoubleLList_t_HeadDel(DoubleCirLinked *Head)
{
DoubleCirLinked *Phead = Head->next;
if (Head->next == Head)
{
printf("list is empty , can not delate");
return false;
}
else if (Phead->next == Phead)
{
Head->next = Head;
free(Phead);
return true;
}
else
{
Phead->prev->next = Phead->next;
Phead->next->prev = Phead->prev;
Head->next = Phead->next;
Phead->prev = NULL;
Phead->next = NULL;
free(Phead);
return true;
}
}
尾删
/**
* @function name: DoubleLList_t_TailDel
* @brief 删除尾结点
* @param 介绍函数参数 @head @data
* @retval bool
* @date 2024/04/23
* @version 1.0 :版本
* @note 补充 注意 说明
*/
bool DoubleLList_t_TailDel(DoubleCirLinked *Head)
{
DoubleCirLinked *Phead = Head->next->prev;
if (Head->next == Head)
{
printf("list is empty , can not delate");
return false;
}
// 判断是否只有一个结点
else if (Head->next->next == Head->next)
{
Head->next->next = NULL;
Head->next->prev = NULL;
Head->next = Head;
free(Phead);
return true;
}
else
{
Phead->prev->next = Head->next;
Head->next->prev = Phead->prev;
Phead->prev = NULL;
Phead->next = NULL;
free(Phead);
return false;
}
}
指定位置删除结点
/**
* @function name: DoubleLList_t_DestDel
* @brief 删除指定位置结点
* @param 介绍函数参数 @head @data @dest
* @retval bool
* @date 2024/04/23
* @version 1.0 :版本
* @note 补充 注意 说明
*/
bool DoubleLList_t_DestDel(DoubleCirLinked *Head, DataType_t destval)
{
DoubleCirLinked *Phead = Head;
DoubleCirLinked *Temp = Head->next;
// 判断链表是否为空
if (Head->next == Head)
{
printf("list is empty , can not delate");
return false;
}
// 判断链表是否只有一个结点
else if (Phead->next == Phead)
{
Head->next = Head;
free(Phead);
return true;
}
// 遍历到指定结点
while (Temp->next) // 遍历找到目标结点进行后插
{
Temp = Temp->next;
if (Temp->data == destval)
{
break;
}
}
// 判断所给数据是否是在尾结点
if (Temp->next == Head->next)
{
Head->next->prev = Temp->prev;
Temp->prev->next = Head->next;
Temp->prev = NULL;
Temp->next = NULL;
free(Temp);
}
Temp->prev->next = Temp->next;
Temp->next->prev = Temp->prev;
Temp->next = NULL;
Temp->prev = NULL;
free(Temp);
return true;
}
遍历链表
/**
* @function name: DoubleCirLList_Print
* @brief 遍历链表输出
* @param 介绍函数参数 @head
* @retval bool
* @date 2024/04/23
* @version 1.0 :版本
* @note 补充 注意 说明
*/
bool DoubleCirLList_Print(DoubleCirLinked *Head)
{
// 对单向循环链表的头结点的地址进行备份
DoubleCirLinked *Temp = Head;
// 判断当前链表是否为空,为空则直接退出
if (Head->next == Head)
{
printf("current DoubleCirLList is empty!\n");
return false;
}
// 从首结点开始遍历
while (1)
{
// 把头结点的直接后继作为新的头结点
Temp = Temp->next;
// 输出头结点的直接后继的数据域
printf("data = %d\n", Temp->data);
// 判断是否到达尾结点,尾结点的next指针是指向首结点的地址
if (Temp->next == Head->next)
{
break;
}
}
printf("\n");
return true;
}
函数验证
int main()
{
DoubleCirLinked *Manager = DoubleLList_Create();
// 头插
DoubleCirLList_HeadInsert(Manager, 1);
DoubleCirLList_HeadInsert(Manager, 2);
DoubleCirLList_HeadInsert(Manager, 3);
DoubleCirLList_HeadInsert(Manager, 4);
DoubleCirLList_HeadInsert(Manager, 5);
DoubleCirLList_HeadInsert(Manager, 6);
// 尾差
DoubleLList_t_TailInsert(Manager, 7);
DoubleLList_t_TailInsert(Manager, 8);
// 指定值后插入
DoubleCirLList_DestInsert(Manager, 5, 10);
// 头删
DoubleLList_t_HeadDel(Manager);
// 尾删
DoubleLList_t_TailDel(Manager);
// 打印
DoubleCirLList_Print(Manager);
// 指定值删除
DoubleLList_t_DestDel(Manager, 3);
// 最终遍历验证
DoubleCirLList_Print(Manager);
return 0;
}
标签:结点,Phead,Head,next,链表,循环,双向,New,prev
From: https://www.cnblogs.com/zeratul/p/18157826