1.定义
将单链表中尾结点的指针指向头结点，使得单链表形成一个环，这样就构成了一个单向循环链表。
循环链表解决了一个很麻烦的问题，即如何从一个结点出发，访问到链表中所有的结点。
2.创建
循环链表的创建，会有两种情况：
1、 第一次开始创建
创建一个新结点，将新结点的next，指向自身：(*L)->next = (*L)
*L = (LinkList)malloc(sizeof(Node));
if(!L)exit(0);
(*L)->data=item; // 赋值
(*L)->next=*L; // 第一个结点next指向自身
2、已经创建，往其中新增数据结点
创建一个新结点，将新结点的next指向*L，找到尾结点，将尾结点的next指向新结点。
为避免结点丢失，需要先执行新结点的next指向*L，再执行尾结点的next指向新结点
//输入的链表不是空的，寻找链表的尾节点，使尾节点的next=新节点。新节点的next指向头节点
for (target = *L; target->next != *L; target = target->next); // 找到尾结点结点
temp=(LinkList)malloc(sizeof(Node)); //创建新结点
if(!temp) return ERROR;
temp->data=item; //新结点赋值
temp->next=*L; //新节点指向头节点
target->next=temp; //尾节点指向新节点
3.遍历
// 遍历循环链表，循环链表的遍历最好用do while语句，因为头节点就有值
void show(LinkList p)
{
//如果链表是空
if(p == NULL){
printf("打印的链表为空!\n");
return;
}else{
LinkList temp;
temp = p;
do{
printf("%5d",temp->data);
temp = temp->next;
}while (temp != p);
printf("\n");
}
}
4.插入
插入循环链表需要注意两种情况
4、1 插入的位置在链表的头结点
步骤：
1、 创建新结点temp,并判断是否创建成功,成功则赋值,否则返回ERROR;
2、 找到链表最后的结点_尾结点,
3、 让新结点的next 执行头结点.
4、 尾结点的next 指向新的头结点;
5、 让链表指针L指向temp(临时的新结点) // 为保证结点不会丢失，指针指向的步骤不可变
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; //新结点的next指向头结点
target->next = temp; //尾结点的next指向新结点
*L = temp; // *L 指向 新的头结点
4、2 插入链表的其他位置
1、 创建新结点temp,并判断是否创建成功,成功则赋值,否则返回ERROR;
2、 先找到插入的位置,如果超过链表长度,则自动插入队尾;
3、 通过target找到要插入位置的前一个结点, 让target->next = temp;
4、 插入结点的前驱指向新结点,新结点的next 指向target原来的next位置 ;
temp = (LinkList)malloc(sizeof(Node)); // 创建新结点
if (temp == NULL) {
return ERROR;
}
temp->data = num; //结点赋值
// i 计数 为了让循环正常结束 找到要插入的位置place的结点
for (i = 1,target = *L; target->next != *L && i != place - 1; target = target->next,i++) ;
temp->next = target->next; // 新结点的next指向插入位置结点的next
target->next = temp; // 插入位置结点的next指向新结点
5.删除
类似插入的操作，也是两种情况
5、1 删除第一个位置
1、 找到尾结点, 使得尾结点next 指向头结点的下一个结点 target->next = (*L)->next;
2、 新结点做为头结点,则释放原来的头结点
//如果删除到只剩下首元结点了,则直接将*L置空;
if((*L)->next == (*L)){
(*L) = NULL;
return OK;
}
// 找到尾结点
for (target = *L; target->next != *L; target = target->next);
temp = *L; // temp为首元结点 获取temp为了free
*L = (*L)->next; //*L 指向下一个位置结点
target->next = *L; //尾结点指向新的首远结点
free(temp);
5、2删除其他位置
1、 找到删除结点前一个结点target
2、 使得target->next 指向下一个结点
3、 释放需要删除的结点temp
// 找到要删除结点的前一个结点
for(i=1,target = *L;target->next != *L && i != place -1;target = target->next,i++) ;
temp = target->next; // 得到要删除的结点
target->next = temp->next; // 将前一个结点的next指向要删除结点的下一个结点
free(temp); // free
6.单向链表查询
// 循环链表查询值
int findValue(LinkList L,int value){
int i = 1;
LinkList p;
p = L;
//寻找链表中的结点 data == value
while (p->data != value && p->next != L) {
i++;
p = p->next;
}
//当尾结点指向头结点就会直接跳出循环,所以要额外增加一次判断尾结点的data == value;
if (p->next == L && p->data != value) {
return -1;
}
return i; // 返回value所在的位置
}
留一个问题：如何将两个循环链表合并成一个？