单向循环列表 是什么呢？

与单向链表的区别就是，单向链表的最后一个节点指针是指向 NULL 的，单向循环链表最后一个节点的指针是指向 头节点 的。

线性表.png

一、循环链表创建

我们在考虑 创建 时，有两种情况：

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⃣️

图1-循环链表插入数据-插入位置在首元结点上

3.2 当插入位置是 其他位置 时，我们要：

1、创建新结点temp，并判断是否创建成功，成功则赋值，否则返回ERROR；
2、先找到插入的位置 target(place-1)，如果超过链表长度，则自动插入队尾；---> 如图2中步骤1⃣️
3、新结点的next 指向 target 原来的next位置；---> 如图2中步骤2⃣️
4、通过 target 找到要插入的位置的前一个结点，让 target->next = temp； --->如图2中步骤3⃣️

图2-循环链表插入数据-插入位置在其他位置

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;