循环链表：将单链表中终端结点的指针域由空改成指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表。
循环链表-空表
image
在空表中，只有头结点，故头结点的指针域指向本身。
*L = (*LinkList)malloc(sizeof(Note));
(*L)->data = item;
(*L)->next = *L;
循环链表-非空表
image
在非空表中，尾结点的指针域指向首元结点。
temp = (*LinkList)malloc(sizeof(Node));
(*temp)->data = item;
(*temp)->next = *L;//尾结点的指针指向首元结点
prev->next = temp;//前一个结点的指针指向新结点
循环链表创建
循环链表创建分为两种情况：
- 第一次开始创建
- 已经创建了链表，往里面新增数据元素
算法思路：
判断当前是否是第一次开始创建，如果是则新建结点，并将结点的指针域指向本身。
如果不是第一次开始创建，则新增结点将前面结点的指针域指向新结点，将新结点的指针域指向首元结点。
Status CreateList(LinkList *L){
int num;
LinkList temp = NULL;
LinkList target = NULL;
printf("输入节点的值，输入0结束\n");
while(1){
scanf("%d", num);
if(num == 0) break;
if(*L == NULL){
*L = (LinkList*)malloc(sizeof(Node));
if(!L) return ERROR;
(*L)->data = num;
(*L)->next = *L;
}
else{
temp = (LinkList*)malloc(sizeof(Node));
if(!temp) return ERROR;
temp->data = num;
//找到最后一个结点
for(target = *L; target->next != *L; target = target->next);
temp->next = *L;
target->next = temp;
}
}
return OK;
}
循环链表插入数据
- 插入位置是否是首元结点
- 插入位置为其它
算法思路：
1.1 插入位置是首元结点
创建新结点，并判断新结点是否malloc成功，如果创建失败退出；
找到链表的尾结点，将链表的尾结点指针域指向新结点；
将新结点的指针域指向首元结点；
将头结点指针指向新结点；
2.1 插入其它位置（思路与单链表插入相同）；
创建新结点，并判断新结点是否malloc成功，如果创建失败退出；
找到插入位置的前一个结点，将前一个结点的指针域指向新结点；
将新结点的指针域指向前一个结点的next；
Status ListInsert(LinkList *L, int place, int num){
LinkList temp ,target;
int i;
if (place == 1) {
temp = (LinkList)malloc(sizeof(Node));
if (temp == NULL) {
return ERROR;
}
temp->data = num;
for (target = *L; target->next != *L; target = target->next);
temp->next = *L;
target->next = temp;
*L = temp;
}else
{
temp = (LinkList)malloc(sizeof(Node));
if (temp == NULL) {
return ERROR;
}
temp->data = num;
for ( i = 1,target = *L; target->next != *L && i != place - 1; target = target->next,i++) ;
temp->next = target->next;
target->next = temp;
}
return OK;
}
循环链表删除数据
- 链表中只有首元结点
- 链表中有除首元结点外其它数据时，删除首元结点
- 删除非首元结点的其它结点
算法思路
1.1 链表中只有首元结点
直接将链表指针置空，释放首元结点的位置；
2.1 链表中有除首元结点外其它数据时，删除首元结点
找到链表的尾结点，将尾结点的指针域指向首元结点的下一个结点；
将链表的指针指向首元结点的下一个结点；
释放首元结点的内存；
3.1 删除非首元结点的其它结点
找到预删除结点并用指针指向预删除结点temp；
找到预删除结点的前一个结点target；
target的指针域指向temp的指针域指向的下个结点；
释放temp的内存；
Status LinkListDelete(LinkList *L,int place){
LinkList temp,target;
int i;
//temp 指向链表首元结点
temp = *L;
if(temp == NULL) return ERROR;
if (place == 1) {
if((*L)->next == (*L)){
temp = *L;
free(temp);
(*L) = NULL;
return OK;
}
for (target = *L; target->next != *L; target = target->next);
temp = *L;
*L = (*L)->next;
target->next = *L;
free(temp);
}else
{
for(i=1,target = *L;target->next != *L && i != place -1;target = target->next,i++) ;
temp = target->next;
target->next = temp->next;
free(temp);
}
return OK;
}
总结：在单向链表中，头指针是相当重要的，因为单向链表的操作都需要头指针，所以如果头指针丢失或者破坏，那么整个链表都会遗失，并且浪费链表内存空间，因此我们引入了单向循环链表这种数据结构。
