单向循环链表大纲
/***********************************************************
*
* file name:
* author : [email protected]
* date : 2024/04/23
* function :
* note : None
*
* CopyRight (c) 2023-2024 [email protected] All Right Reseverd
*
* ***********************************************************/
/***********************************************************
*
* 函数名称： CircularLinkedList
* 函数功能：
* 函数参数：
*
*
* 返回结果：
* 注意事项： None
* 函数作者： [email protected]
* 创建日期： 2024/04/23
* 修改历史:
* 函数版本： V1.0
* ***********************************************************/
// 指的是单向循环链表中的结点有效数据类型，用户可以根据需要进行修改
typedef int DataType_t;
// 构造单向循环链表的结点，链表中所有结点的数据类型应该是相同的
typedef struct CircularLinkedList
{
DataType_t data; // 结点的数据域
struct CircularLinkedList *next; // 结点的指针域
} CircLList_t;
// 创建一个空单向循环链表，空链表应该有一个头结点，对链表进行初始化
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_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;
}
// 在头部进行插入操作
bool CircLList_HeadInsert(CircLList_t *Head, DataType_t data)
{
CircLList_t *Phead = Head;
// 1.创建新的结点，并对新结点进行初始化
CircLList_t *New = CircLList_NewNode(data);
if (NULL == New)
{
printf("can not insert new node\n");
return false;
}
// 2.判断链表是否为空，如果为空，则把新结点作为首结点，，体现“循环”。
if (Head->next == Head)
{
New->next = New;
Head->next = New;
return true;
}
// 3.如果链表为非空,则需要对链表尾结点next指针域进行处理，指向首结点。
while (Phead->next)
{
Phead = Phead->next;
if (Phead->next == Head->next)
{
break;
}
}
Phead->next = New; // 尾结点的next指针指向新的首结点
New->next = Head->next; // 新结点的next指针指向原本的首结点
Head->next = New;
return true;
}
// 尾部插入
bool CircLList_TailInsert(CircLList_t *Head, DataType_t data)
{
CircLList_t *Phead = Head;
// 1.创建新的结点，并对新结点进行初始化
CircLList_t *New = CircLList_NewNode(data);
if (NULL == New)
{
printf("can not insert new node\n");
return false;
}
// 2.判断链表是否为空，如果为空，则把新结点作为首结点，，体现“循环”。
if (Head->next == Head)
{
New->next = New;
Head->next = New;
return true;
}
// 3.如果链表为非空,则需要对链表尾结点next指针域进行处理，指向首结点。
while (Phead->next) // 移动到最后一个有效节点
{
Phead = Phead->next;
if (Phead->next == Head->next)
{
break;
}
}
Phead->next = New; // 3.进行插入操作
New->next = NULL;
return true;
}
/*******************************************************************
*
* 函数名称: CircLList_DestInsert
* 函数功能: 在指定值位置处，插入指定的数据data
* 函数参数:
* CircLList_t *Head: 需要操作的链表头节点
* DataType_t dest: 插入位置的值
* DataType_t data: 需要插入的指定的数据
* 返回结果: true or false
* 注意事项: None
* 函数作者: [email protected]
* 创建日期: 2024/04/23
* 修改历史:
* 函数版本: V1.0
* *****************************************************************/
bool CircLList_DestInsert(CircLList_t *Head, DataType_t dest, DataType_t data)
{
// 1.创建新的结点，并对新结点进行初始化
CircLList_t *New = CircLList_NewNode(data);
if (NULL == New)
{
printf("can not insert new node\n");
return false;
}
CircLList_t *tmp = Head;
while (tmp->data != dest && tmp->next != NULL) // 2.移动到指定位置节点
{
tmp = tmp->next;
}
if (NULL == tmp->next)
{
if (tmp->data == dest)
{
New->next = NULL; // 3.如果指定目标值在末尾，且dest正好也在末尾，
tmp->next = New->next;
return true;
}
else
{
printf("There is no dest\n"); // 4.如果未找到指定目标值，则返回
return false;
}
}
New->next = tmp->next; // 5.如果指定目标值在中间，则进行插入操作。
tmp->next = New->next;
return true;
}
// 头删
bool CircLList_HeadDel(CircLList_t *Head, DataType_t data)
{
// 对单向循环链表的头结点的地址进行备份
CircLList_t *Phead = Head;
// 1.对单向循环链表的首结点的地址进行备份
CircLList_t *Temp = Head->next;
// 2.判断链表是否为空，如果为空，则退出
if (Head->next = Head)
{
printf("linkedlist is Empty\n");
return false;
}
// 3。判断链表中是否只有首结点
if (Head->next = Head->next->next)
{
Temp->next = NULL;
Head->next = Head;
free(Temp);
return true;
}
// 4.如果链表非空的，则需要对尾结点的next指针进行处理，指向新的首结点
while (Phead->next) // 移动到最后一个有效节
{
Phead = Phead->next;
if (Phead->next == Head->next)
{
break;
}
}
Phead->next = Head->next->next; // 让尾结点的next指针指向新的首结点
Head->next = Phead->next; // 更新首结点，让头结点的next指针指向新的首结点
Temp->next = NULL; // 旧的首结点的next指针指向NULL，从链表中断开
free(Temp); // 释放待删除结点的内存
return true;
}
// 尾删(一般情况下用不上)
bool CircLList_TailDel(CircLList_t *Head, DataType_t data)
{
// 对单向循环链表的头结点的地址进行备份
CircLList_t *Phead = Head;
// 1.对单向循环链表的首结点的地址进行备份
CircLList_t *Temp = Head->next;
// 2.判断链表是否为空，如果为空，则退出
if (Head->next = Head)
{
printf("linkedlist is Empty\n");
return false;
}
// 3。判断链表中是否只有首结点
if (Head->next = Head->next->next)
{
Temp->next = NULL;
Head->next = Head;
free(Temp);
return true;
}
// 4.如果链表非空的，则需要对尾结点的next指针进行处理，指向新的首结点
while (Phead->next) // 移动到最后一个有效节
{
Phead = Phead->next;
if (Phead->next == Head->next)
{
break;
}
}
Phead->next = Head->next->next; // 让尾结点的next指针指向新的首结点
Head->next = Phead->next; // 更新首结点，让头结点的next指针指向新的首
Temp->next = NULL; // 旧的首结点的next指针指向NULL，从链表中断开
free(Temp); // 释放待删除结点的内存
return true;
}
/*******************************************************************
*
* 函数名称: CircLList_DestDel
* 函数功能: 在指定值位置处，删除指定的数据
* 函数参数:
*
* 返回结果: true or false
* 注意事项: None
* 函数作者: [email protected]
* 创建日期: 2024/04/24
* 修改历史:
* 函数版本: V1.0
* *****************************************************************/
bool CircLList_DestDel(CircLList_t *Head, DataType_t destval)
{
CircLList_t *tmpFormer;
CircLList_t *tmp = Head->next;
if (Head->next == Head) // 判断当前链表是否为空，为空则直接退出
{
printf("current linkeflist is empty!\n");
return false;
}
while (tmp->data != destval && tmp->next != Head->next)
{
tmpFormer = tmp;
tmp = tmp->next;
}
if (tmp->data == destval)
{
tmpFormer->next = tmp->next;
tmp->next = NULL;
free(tmp);
return true;
}
else
{
printf("The is no destival\n");
return false;
}
}