自定义单向循环链表的增删改查接口函数
/*******************************************************************
*
- 文件名称 : 01 单向循环链表的接口程序
- 文件作者 : [email protected]
- 创建日期 : 2024/04/23
- 文件功能 : 对单向循环链表的增删改查功能的定义
- 注意事项 : None
- CopyRight (c) 2024 [email protected] All Right Reseverd
- *****************************************************************/
定义结构体中数据域的数据类型，用户可以根据需求修改数据类型
typedef int DataType_t;
构造单向循环链表的结点,链表中所有结点的数据类型应该是相同的
typedef struct CircularLinkedList
{
DataType_t data; //结点的数据域
struct LinkedList *next; //结点的指针域
}CircLList_t;
创建单向循环链表，空链表中有一个头结点，便于管理该链表
/*******************************************************************
*
* 函数名称: CircLList_Create
* 函数功能: 创建单向循环链表，空链表中有一个头结点
* 函数参数: none
* 返回结果:
* @Head : 返回头结点地址便于管理链表
* 注意事项: None
* 函数作者: [email protected]
* 创建日期: 2024/04/23
* 修改历史:
* 函数版本: V1.0
* *****************************************************************/
//创建一个空单向循环链表，空链表应该有一个头结点，对链表进行初始化
CircLList_t * CircLList_Create(void)
{
//1.创建一个头结点并对头结点申请内存
CircLList_t *Head = (CircLList_t *)calloc(1,sizeof(CircLList_t));
if (NULL == Head)
{
perror("Calloc memory for Head is Failed");
exit(-1);
}
//2.对头结点进行初始化，头结点是不存储数据域，指针域指向自身，体现“循环”思想
Head->next = Head;
//3.把头结点的地址返回即可
return Head;
}
创建新结点，并返回新结点的地址便于操作
/*******************************************************************
*
* 函数名称: CircLList_NewNode
* 函数功能: 创建新结点
* 函数参数:
* @data ：传入新建结点的数据域中的值
* 返回结果:
* @New : 返回新建结点地址
* 注意事项: None
* 函数作者: [email protected]
* 创建日期: 2024/04/23
* 修改历史:
* 函数版本: V1.0
* *****************************************************************/
//创建新的结点，并对新结点进行初始化（数据域 + 指针域）
CircLList_t * CircLList_NewNode(DataType_t data)
{
//1.创建一个新结点并对新结点申请内存
CircLList_t *New = (CircLList_t *)calloc(1,sizeof(CircLList_t));
if (NULL == New)
{
perror("Calloc memory for NewNode is Failed");
return NULL;
}
//2.对新结点的数据域和指针域进行初始化
New->data = data;
New->next = NULL;
return New;
}
向链表的开头插入元素
/*******************************************************************
*
* 函数名称: CircLList_HeadInsert
* 函数功能: 向链表的头结点中插入元素
* 函数参数:
* @Head ：传入需要操作的链表的头结点地址
* @data ：传入需要插入的结点中的数据域
* 返回结果:
* @bool : 返回插入操作是否成功
* 注意事项: None
* 函数作者: [email protected]
* 创建日期: 2024/04/23
* 修改历史:
* 函数版本: V1.0
* *****************************************************************/
//头插
bool CircLList_HeadInsert(CircLList_t *Head,DataType_t data)
{
//1.新建结点并传入结点中的数据域中的值,定义指针记录新建结点的地址
CircLList_t *New=CircLList_NewNode( data);
if(NULL==New){
return false;
}
//2.定义指针以备份头结点的地址用作遍历链表
CircLList_t *temp=Head;
//3.判断链表是否为空
if(Head->next==Head){
Head->next=New; //如果为空，让头结点的next指针指向新结点,并将NEW结点的next指针指向自身
New->next=New;
}
//4.遍历链表找到单向循环链表的尾结点
while(temp->next!=Head-next){
temp=temp->next;
}
//5.将新结点插入头部
temp-next=New;
New->next=Head->next;
return true;
}
向链表的尾结点后插入元素
/*******************************************************************
*
* 函数名称: CircLList_TailInsert
* 函数功能: 向链表的尾结点后插入元素
* 函数参数:
* @Head ：传入需要操作的链表的头结点地址
* @data ：传入需要插入的结点中的数据域
* 返回结果:
* @bool : 返回插入操作是否成功
* 注意事项: None
* 函数作者: [email protected]
* 创建日期: 2024/04/23
* 修改历史:
* 函数版本: V1.0
* *****************************************************************/
//尾插
bool CircLList_TailInsert(CircLList_t *Head,DataType_t data)
{
//1.新建结点并传入结点中的数据域中的值,定义指针记录新建结点的地址
CircLList_t *New=CircLList_NewNode( data);
if(NULL==New){
return false;
}
//2.定义指针以备份头结点的地址用作遍历链表
CircLList_t *temp=Head;
//3.判断链表是否为空
if(Head->next==Head){
Head->next=New; //如果为空，让头结点的next指针指向新结点,并将NEW结点的next指针指向自身
New->next=New;
}
//4.遍历链表找到单向循环链表的尾结点
while(temp->next!=Head-next){
temp=temp->next;
}
//5.将新结点插入链表尾结点之后
New->=Head->next ;
temp->next=New;
return true;
}
向链表的目标结点后插入元素
/*******************************************************************
*
* 函数名称: CircLList_DestInsert
* 函数功能: 向链表的目标结点后插入元素
* 函数参数:
* @Head ：传入需要操作的链表的头结点地址
* @data ：传入需要插入的结点中的数据域
* @destval :传入需要插入的目标结点数据域
* 返回结果:
* @bool : 返回插入操作是否成功
* 注意事项: None
* 函数作者: [email protected]
* 创建日期: 2024/04/23
* 修改历史:
* 函数版本: V1.0
* *****************************************************************/
//指定位置插入
bool CircLList_DestInsert(CircLList_t *Head,DataType_t destval,DataType_t data)
{
//1.新建结点并传入结点中的数据域中的值,定义指针记录新建结点的地址
CircLList_t *New=CircLList_NewNode( data);
if(NULL==New){
return false;
}
//2.定义指针以备份头结点的地址用作遍历链表
CircLList_t *temp=Head;
//3.判断链表是否为空
if(Head->next==Head){
Head->next=New; //如果为空，让头结点的next指针指向新结点,并将NEW结点的next指针指向自身
New->next=New;
}
//4.遍历链表查找目标结点的位置
while(temp->data!=destval){
temp=temp->next;
}
//5.将新结点插入目标结点之后
New->next=temp->next;
temp->next=New;
return true;
}
遍历链表
bool CircLList_Print(CircLList_t *Head)
{
//对单向循环链表的头结点的地址进行备份
CircLList_t *Phead = Head;
//判断当前链表是否为空，为空则直接退出
if (Head->next == Head)
{
printf("current linkeflist is empty!\n");
return false;
}
//从首结点开始遍历
while(Phead->next)
{
//把头结点的直接后继作为新的头结点
Phead = Phead->next;
//输出头结点的直接后继的数据域
printf("data = %d\n",Phead->data);
//判断是否到达尾结点，尾结点的next指针是指向首结点的地址
if (Phead->next == Head->next)
{
break;
}
}
return true;
}
从链表删除与目标值相同的结点
/*******************************************************************
*
* 函数名称: CircLList_DestInsert
* 函数功能: 从链表删除与目标值相同的结点
* 函数参数:
* @destval :传入需要删除的目标结点数据域
* 返回结果:
* @bool : 返回插入操作是否成功
* 注意事项: None
* 函数作者: [email protected]
* 创建日期: 2024/04/23
* 修改历史:
* 函数版本: V1.0
* *****************************************************************/
bool CircLList_DestDel(DataType_t destval)
{
//1.判断当前链表是否为空，为空则直接退出
if (Head->next == Head)
{
printf("current linkeflist is empty!\n");
return false;
}
//2.对单向循环链表的头结点的地址进行备份,并备份目标结点的直接前驱位置
CircLList_t *Phead = Head->next;
CircLList_t *prev =Head;
while(Phead->data!==destval){
Phead=Phead->next;
prev=prev->next;
if(Phead->next==Head->next){
printf("No target node!");
return false;
}
}
//3.找到结点后判断该结点的位置并进行删除操作
if(Head->next==Phead->next&&Head->next==Phead){ //说明该结点是链表中的唯一结点
Phead->next=NULL;
Head->next=Head;
free(Phead);
}
else if(Phead->next!=Head->next&&Head->next==Phead){ //说明该结点不是唯一节点且是首结点
Head->next=Phead->next;
Phead->next=NULL;
free(Phead);
}else if(Phead->next!=Head->next&&Head->next!=Phead){ //说明该结点既不是首结点也不是尾结点
prev->next=Phead->next;
Phead->next=NULL;
free(Phead);
}
else if(Head->next!=Phead&&Phead->next==Head->next){ //说明该结点不是唯一结点并且是尾结点
prev->next=Head->next;
Phead->next=NULL:
free(Phead);
}
return true;
}
总结：
对单向循环链表进行操作前，需判断链表是否为空
对非空单向循环链表操作时，需要判别操作项是否在特殊位置。（如首结点或尾结点）
对仅有一个结点的链表操作时，需要注意头结点指针域指向的位置