//---------------实现循环单链表的各种基本运算和整体建表算法-----------------

#include<stdio.h>
#include<malloc.h>
#define ElemType int

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LinkNode; 

//初始化循环单链表
void InitList(LinkNode *&L){
    L = (LinkNode *)malloc(sizeof(LinkNode));
    L->next = L;            //单链表初始化时头指针指向NULL，循环单链表头指针指向头结点本身 
}

//释放循环单链表
void DestroyList(LinkNode *&L){
    /*----------------------------
    LinkNode *p = L;
    while(p->next != L){
        p=p->next;
        free(p);    错误原因：无法找到下一个结点 
    }-------------------------------*/
    LinkNode *p,*s;
    /*---------------方法一:从第一个结点开始释放，最后释放头结点 
    s=L;
    p=s;
    while(s->next != L){
    p=s->next;
    s->next = p->next;
    free(p);
    }
    free(s);
    --------------------*/ 
    //法二：从头结点开始释放，最后释放尾结点
    p=L;
    s=p->next;
    while(s!=L){    //释放循环单链表，因为最后一个结点的指针指向了头结点地址，所以是 判断不等于NULL
                    //而不是NULL 
        free(p);
        p=s;
        s=p->next;    
    } 
    free(p);
} 

//判断循环单链表是否为NULL
bool ListEmpty(LinkNode *&L){
    LinkNode *p = L;
    return(p->next == L);
} 

//返回循环单链表的元素个数
int ListLength(LinkNode *L){
    int i=0;
    LinkNode *p = L->next;
    while(p!=L){
        i++;
        p=p->next;
    }
    
    /*-------------法二
    p=L;
    while(p->next != L){
        i++;
        p=p->next;
    }
    --------------------------*/
    return i;
}
//输出循环单链表
void DispList(LinkNode *L){
    LinkNode *p=L->next;
    while(p != L){
        printf("%d",p->data);
        p=p->next;
    }
    printf("\n");
}
//获取循环单链表中第i个元素
bool GetElem(LinkNode *L,int i,ElemType &e){
    LinkNode *p = L;
    int j=0;
    if(i<1)
        return false;
    while(p->next != L && j<i){
        
        p=p->next;
        j++;    //表示当前结点位序 
    }
    if(j!=i)
        return false;
    e=p->data;
    return true;
}
//在循环单链表中查找元素e
int LocateElem(LinkNode *L,ElemType e){
    LinkNode *p=L->next;
    int i=1;
    while(p->data != e && p!=L){
        i++;
        p=p->next;
    }
    if(p==L)
        return 0;
    return i;    //返回元素位序； 
}
//在循环单链表中第i个位置上插入元素e
bool ListInsert(LinkNode *&L,int i,ElemType e){
    LinkNode *p,*s;
    int j=0;
    if (i<1 || L->next==NULL)
        return false;
    p=L;
    s=(LinkNode *)malloc(sizeof(LinkNode));
    s->data = e;
    while(j<i-1 && p->next != L){
        
        p=p->next;
        j++;    //表示当前结点位序 
    }

    s->next = p->next;
    p->next = s;
    return true;
    
}
//从循环单链表中删除第i个元素
bool ListDelet(LinkNode *& L ,int i,ElemType &e){
    LinkNode *p=L,*s=p->next;
    int j=1;
    if (i<1 || L->next == L)
        return false; 
    while(j<i && p->next!=L){
        p=s;
        s=p->next;
        j++;    //当前s指针指向第几个结点 
                //循环结束找到第 i个结点 
    }
    if(j!=i)
        return false; //如果没有找到第i个结点 
    e=s->data;
    p->next = s->next;
    free(s);
    return true;
}

//头插法建立循环单链表
void CreateListF(LinkNode *&L,ElemType a[],int n){
    InitList(L);  //初始化循环单链表
    LinkNode *p=L,*s;    //p指针可以不要，因为p总是指向头结点，可以用L代替 
    int i=0;
    while(i<n){
        s=(LinkNode *)malloc(sizeof(LinkNode));
        s->data=a[i];
        s->next=p->next;
        p->next=s;
        i++;
    } 
} 
//尾插法建立循环 单链表 
void CreateListR(LinkNode *&L,ElemType a[],int n){
    InitList(L);
    LinkNode *p=L,*s;
    int i=0;
    while(i<n){
        s=(LinkNode *)malloc(sizeof(LinkNode));
        s->data=a[i];
        s->next=p->next;
        p->next=s;
        p=s;
        i++;
    } 
} 

#include "clinklist.cpp"            //包含双链表的基本运算算法文件
int main(){
    //定义头指针;
    LinkNode *h,*R,*F;
    ElemType e = 8;
    printf("循环单链表的基本运算如下\n");
    printf("（1）初始化单链表h\n");
    InitList(h);
    printf("(2)依次采用尾插法插入1,2,3,4元素\n");
    ListInsert(h,1,1);
    ListInsert(h,2,2);
    ListInsert(h,3,3);
    ListInsert(h,4,4);
    ListInsert(h,5,5);
    ListInsert(h,6,5);
    ListInsert(h,7,6);
    printf("3/输出循环单链表h\n");
    DispList(h);
    printf("4/循环单链表h长度：%d\n",ListLength(h));
    printf("5/循环单链表h为%s\n",(ListEmpty(h)?"空":"非空"));
    GetElem(h,5,e); 
    printf("6/循环单链表h的第5个元素：%d\n",e);
    printf("7/元素a的位置：%d\n",LocateElem(h,3));
    printf("8/在第4个元素位置上插入f元素\n");
    ListInsert(h,4,9); 
    printf("9/输出循环单链表h：");
    DispList(h);
    printf("10/删除h的第5个元素\n");
    ListDelet(h,5,e);
    printf("11/输出循环单链表h：");
    DispList(h);
    printf("12/释放循环单链表h\n");
    DestroyList(h);
    ElemType a[6]={1,2,3,4,5,6};
    CreateListF(F,a,6);
    printf("13/输出循环单链表F：");
    DispList(F);
    CreateListR(R,a,6);
    printf("12/释放循环单链表F\n");
    DestroyList(F);
    printf("14/输出循环单链表R：");
    DispList(R);
    printf("12/释放循环单链表R\n");
    DestroyList(R);
    return 1;
    
     
}