#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h> 
typedef int DataType;
typedef struct Node
{
    DataType data;            //    數(shù)據(jù)域 
    struct Node * prior;      //    前趨指針 
    struct Node * next;       //    后繼指針 
        
}LinkList;
 
LinkList* Init_List();                                //    初始化循環(huán)雙鏈表 
bool Creat_List(LinkList * L);                        //    創(chuàng)建鏈表 
int Length_List(LinkList * L);                        //    鏈表長度 
bool Empty_List(LinkList * L);                        //    判空 
bool Insert_List(LinkList * L, int pos, DataType x);  //    插入 
bool Delete_List(LinkList * L, int pos, DataType * x);//    刪除 
bool Destroy_List(LinkList * L);                      //    銷毀鏈表
bool Traverse_List(LinkList * L);                     //    遍歷鏈表 
int Prior_Value(LinkList * L, int pos);               //    前趨結(jié)點的值 
 
int main()
{
    DataType x;
    int pos;
    
    LinkList * L = Init_List();
    if(Creat_List(L))
        printf("鏈表構(gòu)造成功！\n");
    else
        printf("鏈表構(gòu)造失??！\n");
    printf("遍歷鏈表：");
    Traverse_List(L);
    
    printf("鏈表結(jié)點個數(shù)：%d\n\n", Length_List(L));
    
    printf("輸入要求前趨結(jié)點的結(jié)點：");
    scanf("%d",&pos); 
    printf("第%d個結(jié)點的前趨結(jié)點：%d\n\n",pos,Prior_Value(L, pos));
    
    Insert_List(L, 2, 5);
    printf("插入結(jié)點：第2個結(jié)點\n");
    printf("插入元素：5\n");
    printf("遍歷鏈表：");
    Traverse_List(L);
    
    Delete_List(L, 3, &x);
    printf("刪除結(jié)點：第3個結(jié)點\n");
    printf("被刪除元素：%d\n",x);
    printf("遍歷鏈表：");
    Traverse_List(L);
    
    if(Destroy_List(L))
        printf("銷毀成功！\n");
    else
        printf("銷毀失敗！\n");
     
    return 0; 
} 
 
LinkList* Init_List()
{
    LinkList * L = (LinkList *)malloc(sizeof(LinkList));    //    創(chuàng)建頭結(jié)點 
    if(!L)
    {
        printf("申請空間失??！\n");
        exit(-1);
    }
    
    L->next = L->prior = L;    //    空表，前趨指針和后繼指針均指向其自身
    return L;                 //    返回頭結(jié)點的地址 
}
 
bool Creat_List(LinkList * L)
{
    int i,n,val;
    LinkList * p = L;    //    保證L始終指向頭結(jié)點 
    
    printf("請輸入循環(huán)雙鏈表的結(jié)點個數(shù)：");
    scanf("%d",&n);
    
    for(i=0; i<n; ++i)
    {
        printf("第%d個結(jié)點：",i+1);
        scanf("%d",&val);
        
        LinkList * q = (LinkList*)malloc(sizeof(LinkList));
        q->data = val;
        p->next = q;
        q->prior = p;
        p = q;
    }
    
    p->next = L;    //    保證最后一個結(jié)點的后繼指針指向頭結(jié)點 
    L->prior = p;    //    保證頭結(jié)點的前趨指針指向最后一個結(jié)點 
    return true;
}
 
int Length_List(LinkList * L)
{
    int len = 0;
    LinkList * p = L->next;    
     
    while(p!=L)    //    最后一個結(jié)點也要加上 
    {
        len++;
        p = p->next;
    }
    
    return len;
}
 
bool Empty_List(LinkList * L)
{
    if(L->next==L&&L->prior==L)
        return true;
    else
        return false;
}
 
bool Insert_List(LinkList * L, int pos, DataType x)
{
    int i = 1;
    LinkList * p = L->next;
    
    if(pos<1||pos>Length_List(L))
        return false;
    
    while(i<pos-1&&L!=p)    //    指針移動到被插入結(jié)點的前一個結(jié)點 
    {
        i++;
        p = p->next;
    }
    
    LinkList * q = (LinkList*)malloc(sizeof(LinkList));
    q->data = x;
    q->next = p->next;
    q->prior = p;
    p->next->prior = q;
    p->next = q;
    return true;
}
 
bool Delete_List(LinkList * L, int pos, DataType * x)
{
    int i = 1;
    LinkList * p = L->next;
    
    if(pos<1||pos>Length_List(L))
        return false;
    
    while(i<pos-1&&L!=p)
    {
        i++;
        p = p->next;
    }
    
    LinkList * q = p->next;
    *x = q->data;
    p->next = q->next;
    q->next->prior = p;
    free(q);
    return true;
}
 
bool Destroy_List(LinkList * L)
{
//    將循環(huán)雙鏈表變成單鏈表 
    LinkList * p = L->next;
    L->next = NULL;        //    空表時， 頭結(jié)點的前趨指針、后繼指針都是指向其自身 
    L->prior = NULL;    //    銷毀時，頭結(jié)點前趨指針、后繼指針指向空 
    
    while(p)
    {
        LinkList * q = p->next;
        free(p);
        p = q;
    }
    
    L = p = NULL; 
    return true;
}
 
bool Traverse_List(LinkList * L)
{
    if(Empty_List(L))
        return false;
         
    LinkList * p = L->next;
    
    while(p!=L)
    {
        printf("%3d",p->data);
        p = p->next;
    }
    
    printf("\n\n");
    
}
 
int Prior_Value(LinkList * L, int pos)
{
    int i = 1;
    LinkList * p = L->next;
    
    if(pos<1||pos>Length_List(L))
        return false;
    
    while(i<pos&&L!=p)    //    指向pos要求的結(jié)點 
    {
        i++;
        p = p->next;
    }
    
    return p->prior->data;
    
}