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


typedef struct Node *PtrToNode;
typedef PtrToNode Position;


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


Position Create(void);  //创建一个循环链表 
void Taverse(Position Head); //遍历
void Inser(Position Head); //插入一个元素 
void Delete(Position Head); //删除一个元素 
int GetListLenth(Position Head); //获得单向循环链表元素个数，用于判断用户输入的序号 


int main()  //测试 
{
Position Head;
Head=Create();
Taverse(Head);
Inser(Head);
Delete(Head);
delete Head;
return 0;
}


Position Create(void) //创建一个单向循环链表 
{
int i,a[N]={10,20,25,59,18,11}; 

Position Head,Tail=NULL,New=NULL;
Head=(struct Node *)malloc(LEN);
if(Head==NULL)
   cout <<"空间不足创建失败!" <<endl ;
Tail=Head;
Head->Element=0;
Head->Next=Head;  //循环链表，当只有一个元素时，它总是指向自己 
for(i=0;i<N;i++)
{
New=(struct Node *)malloc(LEN);
if(New==NULL)
   cout <<"空间不足!" <<endl ;
New->Element=a[i];
New->Next=Head;  //最新的New是末尾，所以指向头 
Tail->Next=New;  //所以现在Tail不是末尾，而Tail的Next New才是末尾 
Tail=New;        //让New成为新的末尾 
}
return Head; 
}




void Taverse(Position Head)
{
Position Head_L=Head->Next;
while(Head_L!=Head)
{
cout <<Head_L->Element <<' ';
Head_L=Head_L->Next; 
}
cout <<"\n遍历完毕!\n" ;
}


void Inser(Position Head)  //插入一个元素 
{
int X,SubLabel;
cout <<"请输入要插入的元素：";
cin >>X ;
cout <<"请输入要插到的序号：";
cin >>SubLabel ;
if(SubLabel>0&&SubLabel<=GetListLenth(Head))
{
Position Head_L=Head->Next;
Position New=(struct Node *)malloc(LEN);  //开辟内存 
if(New==NULL)
   cout <<"内存不足!插入失败\n" ; 
while(SubLabel-2)    //寻找要插入的位置的前一个元素的地址 
{
SubLabel--;
Head_L=Head_L->Next;
}
New->Element=X;  //赋值 
New->Next=Head_L->Next;  //把New的下一个元素与要插入的位置对应的元素连接起来 
Head_L->Next=New;        //把New与要插入的位置的前一个元素连接起来，这样就实现了插入 
cout <<"插入后：" ;  
Taverse(Head);
}
else cout <<"输入的下标有误!\n" ; 
}


void Delete(Position Head) //删除一个元素 
{
int SubLabel;
cout <<"请输入你要删除的序号：" ;
cin >>SubLabel ;
if(SubLabel>0&&SubLabel<=GetListLenth(Head))
{
Position Head_L=Head->Next;
Position Deletion=NULL;
while(SubLabel-2)  //寻找要插入的位置的前一个元素的地址 
{
SubLabel--;
Head_L=Head_L->Next;
}
Deletion=Head_L->Next;  //让要删除的元素与序号前一个元素连接起来 
Head_L->Next=Deletion->Next; //让序号前一个元素与deletion的下一个元素连接起来，这样就实现了删除 
delete Deletion;  //delete释放空间 
cout <<"删除后：" ;
Taverse(Head);
}
else cout <<"输入的序号有误！\n" ;
}


int GetListLenth(Position Head)  //获取循环链表的元素个数 
{

int Lenth=0;
Position Head_L=Head->Next;
while(Head_L!=Head)
{
Lenth++;
Head_L=Head_L->Next;
}
return Lenth;
}