一、单向循环链表
(一)单向循环链表的构造
单向循环链表的尾结点的指针域中必须指向链表的首结点的地址
1）构造单向循环链表的结点
//单向循环链表中的结点有效数据类型，用户可以根据需要进行修改
typedef int DataType_t;
//构造单向循环链表的结点,链表中所有结点的数据类型应该是相同的
typedef struct cirLinkedList {
DataType_t data; //结点的数据域
struct cirLinkedList *next; //结点的指针域
} cirLList_t;
2）创建空单向循环链表的head
注意：有无头结点，本章中都存在头结点。
/************************************************************************************
* name : headCreate
* function ：创建一个空单向循环链表，空链表应该有一个头结点，对链表进行初始化
* argument : None
* retval : @head:返回头结点的地址
* date ：2024/04/23
* note ：Note
************************************************************************************/
cirLList_t *headCreate()
{
//创建一个头结点并对头结点申请内存
cirLList_t *head = (cirLList_t *) calloc(1, sizeof(cirLList_t));
//判断申请空间是否成功
if (NULL == head) {
perror("Calloc memory for Head is Failed");
exit - 1;
}
//头结点初始化
head->next = head;
return head;
}
3）创建单向循环链表的新结点
/************************************************************************************
* name : newNode_create
* function ：创建新结点，并对新结点进行初始化（数据域 + 指针域）
* argument : @data ：该结点数据域存放的数据
* retval : @newNode:返回新结点的地址
* date ：2024/04/23
* note ：Note
************************************************************************************/
cirLList_t *newNode_Create(DataType_t data)
{
//创建一个新结点并对新结点申请内存
cirLList_t *newNode = (cirLList_t *) calloc(1, sizeof(cirLList_t));
if (NULL == newNode) perror("Calloc memory for Head is Failed");
//对新结点的数据域和指针域进行初始化
newNode->data = data;
newNode->next = NULL;
return newNode;
}
(二)单向循环链表操作（方法）
1）向单向循环链表头部添加新结点
/************************************************************************************
* name : headIns
* function ：向链表头部添加新结点
* argument : @head:单向循环链表的头结点地址
* @data:新结点数据域存放的数据
* retval : None
* date ：2024/04/23
* note ：Note
************************************************************************************/
bool headIns(cirLList_t *head, DataType_t data)
{
//创建一个新结点
cirLList_t *newNode = newNode_Create(data);
//定义一个变量temp记录首结点地址，后续做遍历结点
cirLList_t *temp = head->next;
//首先判断传进来的链表head中的next是否指向自身
//如果head指向自身地址说明该链表为空链表
if (head == head->next) {
head->next = newNode;
newNode->next = newNode;
return true;
}
//链表非空情况，从首结点next开始去判断是否为head->next，循环找到尾结点地址
while (temp->next != head->next) temp = temp->next;
//新结点添加头部流程
temp->next = newNode;
newNode->next = head->next;
head->next = newNode;
return true;
}
2）向单向循环链表尾部添加新结点
/************************************************************************************
* name : endIns
* function ：向链表尾部添加新结点
* argument : @head:单向循环链表的头结点地址
* @data:新结点数据域存放的数据
* retval : None
* date ：2024/04/23
* note ：Note
************************************************************************************/
bool endIns(cirLList_t *head, DataType_t data)
{
cirLList_t *newNode = newNode_Create(data);
cirLList_t *temp = head->next;
if (head == head->next) {
head->next = newNode;
newNode->next = newNode;
return true;
}
while (temp->next != head->next) temp = temp->next;
//新结点添加尾部流程
temp->next = newNode;
newNode->next = head->next;
return true;
}
3）向单向循环链表任意地方添加新结点
/************************************************************************************
* name : insert
* function ：根据目标值向链表任意地方添加新结点
* argument : @head:单向循环链表的头结点地址
* @data:新结点数据域存放的数据
* retval : None
* date ：2024/04/23
* note ：Note
************************************************************************************/
bool insert(cirLList_t *head,DataType_t destval, DataType_t data)
{
//创建一个新结点
cirLList_t *newNode = newNode_Create(data);
//定义一个变量temp记录首结点地址，后续做遍历结点
cirLList_t *temp = head->next;
//判断链表是否为空，则不能根据destval找到要添加的地方
if (head == head->next) {
perror("The place you want to add is not found in the linked list");
return true;
}
//该链表就一个首结点的情况，或者遍历到最后位时的data==destval
//遍历一遍链表找destval所在的结点，找不到也可以退出循环
while (head->next != temp->next){
if(destval == temp->data) break;
temp = temp->next;
}
newNode->next = temp->next;
temp->next = newNode;
return true;
}