线性表-循环单链表

循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环，从表中任何一结点出发均可找到表中其他结点
循环链表的操作和线性链表基本一致，差别仅在于算法中的循环条件不是p或p->next是否为空，而是在于它们是否等于头指针。

image.png

0、定义

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <malloc.h>

typedef int ElemType ;

struct Node{
    ElemType data;//数据域
    struct Node *next;//节点
};
typedef Node CircleList;

1、初始化链表

/**
 * 功能：初始化链表
 */
void Init_List(CircleList* head){
    head->next=head;
}

2、判断是否为空链表

/**
 * 功能：判断链表是否是空表
 * 参数：链表头指针
 * 返回值：true 是  false 否
 */
bool IsEmpty(CircleList *head){
    if(head->next==head){
        printf("CircleList为空表\n");
        return true;
    }
    return false;
}

3、获取链表长度

/**
 * 功能：获取链表长度
 * 参数：链表地址
 * 返回值：链表长度
 */
int Length_List(CircleList *head){
    CircleList* p=head->next;
    int length=0;
    while(p!=head){
        p=p->next;
        length++;
    }
    return length;
}

4、展示链表

/**
 * 功能：遍历链表
 * 参数：链表地址
 */
void Show_List(CircleList *head){
    if(head==NULL){
        printf("链表未初始化\n");
        return ;
    }
    if(head->next==head){
        printf("[]\n");
        return;
    }
    bool flag=true;
    printf("[");
    CircleList *p=head->next;//第一个节点
    while(p!=head){
      if(flag){
         printf("%d",p->data);
         flag=false;
      }else{
         printf(",%d",p->data);
      }
        p=p->next;
    }
    printf("]\n");
}

5、插入操作

  /**
 * 功能：向链表插入数据元素
 * 参数：链表地址 下标  插入的元素
 * 返回值：链表长度
 */
bool Insert_List(CircleList *head,int index, ElemType e){
    if(head==NULL){
        printf("链表未初始化\n");
        return false;
    }
    if(index<1||index>Length_List(head)+1){
        printf("下标越界\n");
        return false;
    }
    //开始插入
    int i;
    CircleList* pre=head;
    //遍历获取到插入位置的前一个元素
    for(i=1;i<index&&(pre->next!=head);i++){
        pre=pre->next;
    }
    //校验
    if(!pre||i>index){
        printf("搜索index位置元素失败\n");//已判断下标越界，不会存在这个问题
        return false;
    }
   CircleList* newNode=(CircleList*)malloc(sizeof(CircleList));
   newNode->data=e;
   newNode->next=pre->next;
   pre->next=newNode;
   return true;
}

6、删除元素

  /**
 * 功能：删除某个下标的数据元素
 * 参数：链表地址 下标  删除的元素
 * 返回值：链表长度
 */
bool Delete_List(CircleList *head,int index, ElemType *e){
    if(head==NULL){
        printf("链表未初始化\n");
        return false;
    }
    if(index<1||index>Length_List(head)){
        printf("下标越界\n");
        return false;
    }
    CircleList *pre,*temp;
    pre=head;
    int i=1;
     //遍历获取到删除的前一个元素
    while(pre->next!=head && i<index){
        pre=pre->next;
        i++;
    }
    temp=pre->next;
    *e=temp->data;
    pre->next=temp->next;
    free(temp);
    return true;
}

7、查找元素

/**
 * 功能：查找元素，返回下标
 * 参数：链表地址 元素
 * 返回值: 下标 -1 为查找不到
 */
int Search_List(CircleList *head,ElemType e){
    if(IsEmpty(head)){
        return -1;
    }
    CircleList *p=head->next;//第一个节点
    int i=1;
    while(p!=head){
        if(p->data==e){
            return i;
        }
        p=p->next;
        i++;
    }
    return -1;
}

8、获取下标的元素

/**
 * 功能：获取某个下标的元素
 * 参数：链表地址 下标
 * 返回值: true ,false
 */
bool GetElem(CircleList *head,int index,ElemType *e){
    if(IsEmpty(head)){
        return false;
    }
    if(index<1||index>Length_List(head)){
         printf("数组下标越界\n");
         return false;
    }
    CircleList *p=head->next;//第一个节点
    int j=1;
    while((p!=head)&&j<index){
       p=p->next;
       j++;
    }
    if((p==head)||j>index)return false;
    *e=p->data;
    return false;
}

9、清空链表

/**
 * 功能：清空线性表
 * 参数：pList：链表地址
 */
bool Clear_List(CircleList* head){
    CircleList *temp,*p;
    temp=head->next;//第一个节点
    while(temp != head){
        p=temp->next;
        free(temp);
        temp=p;
    }
    head->next=head;
    return true;
}