//循环链表(容易忽略尾指针所指向的尾节点)
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>

typedef struct Ndoe{

    int data;
    struct Ndoe *next;

} Linklist;

bool InitList(Linklist** L)//构造一个空的循环链表（注：L表示尾指针）
{

    (*L) = (Linklist *)malloc(sizeof(Linklist));//创建头结点，并使尾指针指向头结点。

    if((*L)==NULL)
        return false;

    (*L)->next = (*L);
    
    return true;

}

void DestoryList(Linklist **L)//销毁循环链表(包括头结点)。
{
    Linklist *p,*q;

    p = (*L)->next;//p指向头结点

    while((*L)!=p->next)
    {
        q = p->next;//q指向第一个结点
        free(p);
        p = q;
    }
    
    free(p);
    (*L) = NULL;//因为此处修改了尾指针，故参数类型为Linklist **。
}

void ClearList(Linklist **L)//将循环链表清空（不包括头结点）成功的标志是尾指针指向头结点
{
    Linklist *p,*q;

    p = (*L)->next->next;//让p指向第一个有效结点

    while(p!=(*L))
    {
        q = p;//q此时指向第一个有效结点
        p = p->next;
        free(q);
    }
    
    *L = p->next;//释放掉尾节点
    free(p);
}

bool ListEmpty(Linklist *L)//判断线性表是否为空
{
    if(L->next==L)//当尾指针指向头结点时才会出现这种效果，也即循环链表为空。
    {
        return true;
    }
    else
    {
        return false;
    }
}

int ListLength(Linklist *L)//返回循环链表中数据元素个数
{
    int i = 0;
    Linklist *p;

    p = L->next->next;//指向第一个有效结点

    while(p!=L)
    {
        i++;
        p = p->next;
    }

    return i+1;//加1表示尾指针所指向的那个节点
}

int GetElem(Linklist *L,int item)//返回线性表第item个元素的值
{
    Linklist *p;
    int i;

    p = L->next->next;//让p指向第一个有效结点

    for(i=1;i<item;i++)
    {
        if(p!=L->next){
            p = p->next;
        }
        else{
            printf("指定查询的位置不存在!\n");
            return -1;
        }
    }
    if(p!=L->next)//此步不能少
        return p->data;
    else
        return -1;
}

int LocateElem(Linklist *L,int item)//返回线性表第一个与给定参数匹配的元素的位序，不存在则返回-1
{
    Linklist *p;
    int i = 0;
    
    p = L->next->next;

    while(p!=L->next)
    {
        i++;

        if(p->data==item)
            return i;

        p = p->next;
    }
    
    return -1;//表示返回指定位置元素失败
}

int PriorElem(Linklist *L,int item)//返回线性表中，指定参数的前驱
{
    Linklist *p,*before;
    
    p = L->next->next;//p此时指向第一个有效元素

    while(p->next!=L->next)//从第二有效元素开始遍历（第一有效元素的数据域即使和item相等，也不存在前驱。）
    {
        before = p;
        p = p->next;//p此时指向第二个有效元素

        if(p->data==item)
            return before->data;

        //p = p->next;
    }
    
    return -1;//表示返回指定位置元素失败
}

int NextElem(Linklist *L,int item)//返回线性表中，指定参数的后继
{
    Linklist *p,*tail;
    
    p = L->next->next;//p此时指向第一个有效元素

    while(p->next!=L->next)//如果一个链表只有一个有效结点同样不存在后继
    {
        tail = p->next;

        if(p->data==item)//最后一个元素是不存在后继的
            return tail->data;

        p = tail;
    }
    
    return -1;//表示返回指定位置元素失败
}

bool ListInsert(Linklist **L,int loc,int item)//向线性表指定位置插入元素
{
    Linklist *p,*New;
    int i=1;//设置为1，很重要哦
    
    if((*L)==NULL||loc>ListLength(*L)+1||loc<1)//销毁后就不能插入数据了
        return false;

    p = (*L)->next;//指向头结点

    while(i<loc)//获取第loc-1位置地址
    {
        p = p->next;
        i++;
    }

    New = (Linklist *)malloc(sizeof(Linklist));
    New->data = item;
    New->next = p->next;
    p->next = New;

    if(p==(*L))
        (*L) = New;//改变了尾指针，所以使用Linklist **类型。
    
    return true;
}

bool ListDelete(Linklist **L,int loc,int *e)//删除线性表第i个位置的元素，并把删除元素返回
{
    Linklist *p,*q;
    int i=1;
    
    if(*L==NULL||loc>ListLength(*L)||loc<1)
        return false;

    p = (*L)->next;//指向头结点

    while(i<loc)//获取第loc-1位置地址
    {
        p = p->next;
        i++;
    }

    q = p->next;//指向位于loc位置的结点
    (*e) = q->data;
    p->next = q->next;

    if((*L)==q)
        (*L) = p;

    free(q);

    return true;
}

void ListTraverse(Linklist *L)//将线性表进行遍历
{
    Linklist *p;

    p = L->next->next;//指向第一个有效结点

    while(p!=L->next)
    {
        printf("%d ",p->data);
        p = p->next;
    }
    printf("\n");
}

int main()
{

    Linklist* L;
    int i,e;
    
    if(!InitList(&L))//初始化线性表
    {
        printf("抱歉，内存分配失败！\n");
    }
    
    for(i=1;i<=13;i++)//向线性表中插入新元素
    {
        //printf("插入的位置:%d\n",i);
        if(!ListInsert(&L,i,i))
        {
            printf("插入失败\n");
            return 0;
        }
    }
    //ListInsert(L,2,6666);
    ListTraverse(L);//遍历线性表
    //DestoryList(&L);//销毁线性表（破坏表结构）
    //ListTraverse(L);//遍历线性表
    //ClearList(L);/清空线性表（不破坏表结构）

    ListDelete(&L,2,&e);//删除线性表指定位置元素
    printf("线性表被删除的元素是：%d\n",e);
    printf("执行删除操作后的线性表:");
    ListTraverse(L);//遍历线性表

    if(PriorElem(L,3)!=-1)//获取值为3的元素的前驱
    {
        printf("元素3的前驱为：%d\n",PriorElem(L,3));
    }
    else
    {
        printf("查询的元素可能不存在或者位于线性表的第一个位置不存在前驱！\n");
    }
    
    if(NextElem(L,3)!=-1)//获取值为3的元素的后继
    {
        printf("元素3的后继为：%d\n",NextElem(L,3));
    }
    else
    {
        printf("查询的元素可能不存在或者位于线性表的最后一个位置不存在后继！\n");
    }
    
    if(LocateElem(L,3)!=0)//查询指定元素在线性表中的位置
    {
        printf("值为3的元素在线性表中的位置：%d\n",LocateElem(L,3));
    }
    else
    {
        printf("你所查询的元素不存在\n");
    }

    return 0;
}