单向循环列表 是什么呢？
与单向链表的区别就是，单向链表的最后一个节点指针是指向
NULL的，单向循环链表最后一个节点的指针是指向头节点的。
一、循环链表创建
我们在考虑 创建 时，有两种情况：
1⃣️ 第一次开始创建；
2⃣️ 已经创建，往里面添加数据。
所以我们首先要 判断当前链表是否是第一次创建
YES： 创建第一个新结点(*L)，并使得新结点的next指向自身；(*L)->next = (*L)
NO： 找链表的尾结点(target)，将尾结点的next指向新结点 (temp)，新结点的next指向头结点temp->next = (*L)
Status CreateList(LinkList *L){
if (L) {
printf("当前表已存在\n");
return ERROR;
}
int item;
LinkList temp = NULL;
LinkList target = NULL;
printf("输入节点的值，输入0结束\n");
while(1)
{
scanf("%d",&item);
if(item==0) break;
//如果输入的链表是空。则创建一个新的节点，使其next指针指向自己 (*head)->next=*head;
if(*L==NULL)
{
*L = (LinkList)malloc(sizeof(Node));
if(!L)exit(0);
(*L)->data=item;
(*L)->next=*L;
}
else
{
//输入的链表不是空的，寻找链表的尾节点，使尾节点的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;//尾节点指向新节点
}
}
return OK;
}
上面我们用到了 for 循环来获取尾结点，看着是不是有点不习惯呢？下面我们换一种写法：
Status CreateList2(LinkList *L){
if (L) {
printf("当前表已存在\n");
return ERROR;
}
int item;
LinkList temp = NULL;
LinkList target = NULL;
printf("输入节点的值，输入0结束\n");
LinkList lastTarget;
while(1)
{
scanf("%d",&item);
if(item==0) break;
//如果输入的链表是空。则创建一个新的节点，使其next指针指向自己 (*head)->next=*head;
if(*L==NULL)
{
*L = (LinkList)malloc(sizeof(Node));
if(!L)exit(0);
(*L)->data=item;
(*L)->next=*L;
lastTarget = *L;
}
else
{
temp=(LinkList)malloc(sizeof(Node));
if(!temp) return ERROR;
temp->data=item;
temp->next=*L; //新节点指向头节点
target->next=temp;//尾节点指向新节点
lastTarget->next = temp;
lastTarget = temp;
}
}
return OK;
}
这里我们用 结点(lastTarget)来记录尾结点
1、当是第一次创建时，只有一个结点，
*L既是首结点也是尾结点，lastTarget直接等于*L即可;
2、当不是第一次时，lastTarget的next每次指向新结点(temp)，且lastTarget要等于temp。
二、遍历循环链表
循环列表的遍历我们最好用
do while，因为头结点就有值
void showList(LinkList L)
{
//如果链表是空
if(L == NULL){
printf("打印的链表为空!\n");
return;
}else{
LinkList temp;
temp = L;
do{
printf("%5d",temp->data);
temp = temp->next;
}while (temp != L);
printf("\n");
}
}
三、循环链表插入数据
- 插入位置是
首元结点 - 插入位置是
其他位置
3.1 当插入位置是 首元结点 时，我们要：
1、创建新结点temp，并判断是否创建成功，成功则赋值，否则返回ERROR；
2、找到链表最后的结点——尾结点；
3、让新结点的next 指向头结点；---> 如图1中步骤1⃣️
4、尾结点的next指向新的头结点(temp)；---> 如图1中步骤2⃣️
5、让头指针指向 临时的新结点(temp)。---> 如图1中步骤3⃣️
3.2 当插入位置是 其他位置 时，我们要：
1、创建新结点temp，并判断是否创建成功，成功则赋值，否则返回ERROR；
2、先找到插入的位置target(place-1)，如果超过链表长度，则自动插入队尾；---> 如图2中步骤1⃣️
3、新结点的next 指向target原来的next位置；---> 如图2中步骤2⃣️
4、通过target找到要插入的位置的前一个结点，让target->next = temp； --->如图2中步骤3⃣️
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;
}
四、循环链表删除数据
- 删除位置是
首元结点 - 删除位置是
其他位置
4.1 当删除位置是 首元结点 时，我们要：
1、只剩下首元结点，则直接将
*L置空；
2、链表中还有很多数据，但是删除的是首结点；
a、找到尾结点，使得尾结点next指向头结点的下一个结点target->next = (*L)->next;
b、新结点作为头结点，则释放原来的头结点。
4.2 当删除位置是 其他位置 时，我们要：
1、判断删除的位置是否合法，合法则进入下一步，否则返回ERROR;
2、找到删除结点前一个结点target；
3、使得target->next指向下一个结点；
4、释放需要删除的结点temp。
Status LinkListDelete(LinkList *L,int place,int length){
LinkList temp,target;
int i;
if (place < 0 || place > length) {
printf("没有找到要删除的数\n");
return ERROR;
}
//temp 指向链表首元结点
temp = *L;
if(temp == NULL) return ERROR;
if (place == 1) {
//①.如果删除到只剩下首元结点了,则直接将*L置空;
if((*L)->next == (*L)){
(*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;
}
五、循环列表查询值的位置
1、先判断表是否存在，存在则继续，否则返回ERROR;
2、通过while循环，寻找链表中的结点data == value；
3、当尾结点指向头结点就会直接跳出循环，所以要额外增加一次判断尾结点的data == value,不存在则返回 -1;
int findValue(LinkList L,int value){
if(L == NULL) return ERROR;
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;
}
那么问题来了，上面的🌰为顺时间查找，那 逆时针查找又是怎样的呢？
1、先判断表是否存在，存在则继续，否则返回ERROR;
2、通过while循环，寻找链表中的结点data == value；
3、当尾结点指向头结点就会直接跳出循环，所以要额外增加一次判断尾结点的data == value,不存在则返回 -1;
