//我发现，插入操作时，总是先把New与已有节点连接 

#include<iostream>
#include<cstdlib>
#define LEN sizeof(struct Node)
using namespace std;

typedef struct Node *PtrToNode;
typedef PtrToNode Position;

struct Node
{
int Element;
struct Node *Last;
struct Node *Next;
};


Position Create(void);           //创建双向循环链表 
void Traverse(Position Head);    //正序遍历/n反序遍历 
void Insert(Position Head);      //插入一个元素 
void Delete(Position Head);      //删除一个元素 
int GetListLenth(Position Head); //用于插入 

int main()  //测试 
{
Position Head;
Head=Create();
Traverse(Head);
Insert(Head);
Delete(Head);
return 0;
}


Position Create(void)  //创建 
{
int a[6]={11,41,18,49,35,66},i;
Position Head=NULL;
    Position New=NULL,Tail=NULL;
    Head=(struct Node *)malloc(LEN);
    if(Head==NULL)
        cout <<"空间不足!" <<endl ;
    Head->Next=Head;
    Head->Last=Head;
    Head->Element=0;
    Tail=Head;
    for(i=0;i<6;i++)
    {
    New=(struct Node *)malloc(LEN);
    if(New==NULL)
       cout <<"空间不足!" <<endl ;
    New->Element=a[i];     //赋值 
    New->Last=Tail;        //先把New与已有的节点连接 
    New->Next=Head;
    Tail->Next=New;        //把原来的尾节点与New连接 
    Head->Last=New;        //把Head的Last与New连接 
    Tail=New;              //现在，New是新的Tail，在末尾插入完毕 
   
}
return Head;
}


void Traverse(Position Head)  //遍历，这里的Head_L用来遍历，而不一直是头指针 
{
Position Head_L=Head->Next;  //从这开始，正序遍历总是指向Next 
while(Head_L!=Head)
{
cout <<Head_L->Element <<' ' ;
Head_L=Head_L->Next;
}
cout <<"正序遍历完毕" <<endl ;
Head_L=Head->Last;          //从这开始，反序遍历总是指向Last 
while(Head_L!=Head)
{
cout <<Head_L->Element <<' ' ;
Head_L=Head_L->Last;
}
cout <<"反序遍历完毕" <<endl ; 
}




void Insert(Position Head)   //插入
{
int X,SubLabel;
Position New=NULL;
Position Head_L=Head->Next;
cout <<"请输入你要插入的元素值：" ;
cin >>X ;
cout <<"请输入你要插到的序号：" ;
cin >>SubLabel ;

if(SubLabel>0&&SubLabel<=GetListLenth(Head))
{
while(SubLabel-1)   //找到链表要插入的位置 
       {
        Head_L=Head_L->Next;
        SubLabel--;
       }
   New=(struct Node *)malloc(LEN);
   if(New==NULL)
       cout <<"空间不足！" <<endl ;
   New->Element=X;    //赋值 
   New->Last=Head_L->Last;  //先把New与已有节点连接 
   New->Next=Head_L;
   Head_L->Last->Next=New;  //趁着还有着Head_L的上一个节点位置，及早把它与New连接 
   Head_L->Last=New;        //最后把New与Head_L连接 
   Traverse(Head);  
}
else cout <<"输入的序号有误！" <<endl ;
}


void Delete(Position Head)
{
int SubLabel;
Position Head_L=Head->Next;
cout <<"请输入要删除元素对应的序号：" ;
cin >>SubLabel ;

if(SubLabel>0&&SubLabel<=GetListLenth(Head))
{
while(SubLabel-1) //找到要删除的位置 
{
Head_L=Head_L->Next;
SubLabel--;
}
Head_L->Last->Next=Head_L->Next; //把要删除的位置Head_L的前一个位置与Head_L的下一个位置连接起来 
Head_L->Next->Last=Head_L->Last; //建议画个图，很清晰 
delete Head_L;  //释放 
Traverse(Head);
}
else cout <<"输入的序号有误！" <<endl ;
}


int GetListLenth(Position Head)  //获得元素个数，这与单链表，循环链表的想法是一样的 
{
int Lenth=0;
Position Head_L=Head->Next;
while(Head_L!=Head)
{
Lenth++;
Head_L=Head_L->Next;
}
return Lenth;
}