单向循环链表

循环链表是另一种形式的链式存贮结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。

单向循环链表.png

• 特点

  1. 循环链表的特点是无须增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活。
  2. 循环链表中没有NULL指针。涉及遍历操作时，其终止条件就不再是像非循环链表那样判别p或p->next是否为空，而是判别它们是否等于某一指定指针，如头指针或尾指针。
  3. 在单链表中，从一已知结点出发，只能访问到该结点及其后续结点，无法找到该结点之前的其它结点。而在单循环链表中，从任一结点出发都可访问到表中所有结点，这一优点使某些运算在单循环链表上易于实现。

• 代码实现

  • 初始化

    /*
     循环链表创建!
     2种情况:① 第一次开始创建; ②已经创建,往里面新增数据
     
     1. 判断是否第一次创建链表
        YES->创建一个新结点,并使得新结点的next 指向自身; (*L)->next = (*L);记录尾节点rear
        NO-> 找链表尾结点,将尾结点的next = 新结点. 新结点的next = (*L);
     */
    bool ListInit(LinkList *L){
        
        int item;
        LinkList temp = NULL;
        LinkList rear = NULL;
        printf("请输入新的结点, 当输入0时结束!\n");
        while (1) {
            scanf("%d",&item);
            if (item == 0) {
                break;
            }
            
            //第一次创建
            if(*L == NULL){
                
                *L = (LinkList)malloc(sizeof(Node));
                if(!*L) return ERROR;
                (*L)->data = item;
                (*L)->next = *L;
                rear = *L;
            }else{
                
                temp = (LinkList)malloc(sizeof(Node));
                if(!temp) return  ERROR;
                temp->data = item;
                temp->next = *L;
                rear->next = temp;
                
                rear = temp;
            }
            
        }
        
        return OK;
    }
    
    

  • 销毁

    /*
     销毁线性表，遍历每个结点
     */
    void destroyList(LinkList *L){
        LinkList q = (*L)->next;
        LinkList p = (*L)->next;
        while (p != *L) {
            q = p->next;
            free(p);
            p = q;
        }
        free(*L);
        *L = NULL;
    }
    
    

  • 插入

    /*
     插入结点
        @param L 链表指针
        @param place 位置 从1开始记录
        @param num  数据
     */
    void insertNode(LinkList *L,int place,int num){
        //1. 创建新结点temp,并判断是否创建成功,成功则赋值,否则返回;
        LinkList temp = NULL;
        temp = (LinkList)malloc(sizeof(Node));
        if (temp == NULL) {
            printf("插入失败");
            return;
        }
        temp->data = num;
        //如果插入的位置为1,则属于插入首元结点,所以需要特殊处理
        if (place == 1) {
            //找到链表最后的结点_尾结点,
            LinkList rear = NULL;
            do{
                rear = *L;
            }while (rear->next != *L);
            //尾结点的next 指向新的头结点;
            rear->next = temp;
            //让新结点的next 执行头结点.
            temp->next = *L;
            //让头指针指向temp(临时的新结点)
            *L = temp;
        }else{
            //找到要插入所在位置前驱
            LinkList target = *L;
            int i = 1;
            while (i < place - 1) {
                I++;
                target = target->next;
                if (target == *L) {
                    printf("插入失败,索引越界");
                    return;
                }
            }
            //让新结点的next 指向对应后驱.
            temp->next = target->next;
            //让对应结点指向temp(临时的新结点)
            target->next = temp;
        }
        printf("插入成功");
    }
    

  • 删除

    /*
      删除结点
       @param L 链表指针
       @param place 位置 从1开始记录
    */
    void deleteNode(LinkList *L,int place){
             if (*L == NULL){
                  printf("删除失败,索引越界");
           return;
           }
           LinkList temp = NULL;
           //如果插入的位置为1,则属于插入首元结点,所以需要特殊处理
           if (place == 1) {
               //单结点 直接释放
               if(*L == (*L)->next){
                   temp = *L;
                   *L = NULL;
                   free(temp);
               }
               
               //找到链表最后的结点_尾结点,
               LinkList rear = NULL;
               do{
                   rear = *L;
               }while (rear->next != *L);
               //temp 指向 L
               temp = *L;
               //尾节点的下一个结点指向 L的下一个结点
               rear->next = (*L)->next;
               // L 指向 下一个结点
               (*L) = (*L)->next;
               //释放目标结点
               free(temp);
           }else{
               //找到要删除所在位置前驱
               LinkList target = *L;
               int i = 1;
               while (i < place - 1) {
                   I++;
                   target = target->next;
                   if (target->next == *L) {
                       printf("删除失败,索引越界");
                       return;
                   }
               }
               //临时指针指向目标位置
               temp = target->next;
               //前驱的下一个结点指向新节点
               target->next = temp->next;
               //释放目标
               free(temp);
           }
           printf("删除成功");
    }
    
    

  • 查找

    //根据对应值找到第一个对应的结点
    LinkList findValue(LinkList *L,int value){
        LinkList temp = *L;
        while (temp->data != value) {
            temp = temp->next;
            if (temp->next == *L) {
                printf("未找到对应结点");
                return NULL;
            }
        }
        return temp;
    }