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

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

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>

typedef struct Node *PtrToNode;
typedef PtrToNode Position;

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

struct Node;
typedef struct Node *PtrToNode;
//typedef PtrToNode List; 
typedef PtrToNode Position;

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

typedef struct Node *PtrToNode;
typedef PtrToNode Position;

struct Node
{
int Element;   //元素 
//int Subscrit;  //下标 
struct Node *Next;    
};

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

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

Position Create(void);  //创建链表 
void TraverseList(Position Head);//遍历 
void FindPosition(Position Head);   //根据元素找下标 
void FindElement(Position Head); //根据下标位置找元素
void Insert(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);           //创建双向循环链表 
void Traverse(Position Head);    //正序遍历/n反序遍历 
void Insert(Position Head);      //插入一个元素 
void Delete(Position Head);      //删除一个元素 
int GetListLenth(Position Head); //用于插入 

int main()  //主函数 
{
Position Head;
Head=Create();
TraverseList(Head);  //先遍历 

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

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

int Choose;
printf(“1.输入序号查找元素n2.输入元素输出序号n3.插入元素n4.删除元素n5.退出n请输入你的选择:”);
scanf(“%d”,&Choose);
switch(Choose)
{
   case 1:
    FindElement(Head);     break;   
   case 2:
    FindPosition(Head);    break; 
   case 3:
    Insert(Head);       break;
   case 4:
    Delete(Head);       break;
   case 5:
                          break;
   default:
    printf(“选项输入有误!n”);     break;
}
return 0;
 } 

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; 
}

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;
}

Position Create(void)    //创建链表 
{
Position Head,New,Tail;
int i,arr[]={21,3,15,27,11,18};
New=Tail=NULL;   //New是用来开辟新的node,Tail是尾node 
Head=malloc(sizeof(struct Node));

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 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 ; 
}

if(Head==NULL)
{
printf(“空间不足! n”);
exit(0);     //跳到函数尾 
}
Head->Element=0;    //初始化头指针 
Head->Next=NULL;
Tail=Head;          //初始事尾就是头 

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 Insert(Position Head)   //插入
{
int X,SubLabel;
Position New=NULL;
Position Head_L=Head->Next;
cout <<“请输入你要插入的元素值:” ;
cin >>X ;
cout <<“请输入你要插到的序号:” ;
cin >>SubLabel ;

for(i=0;i<6;i++)
{
New=malloc(sizeof(struct Node));
if(New==NULL)
{
printf(“空间不足! n”);
   exit(0);     //跳到函数尾
}
New->Element=arr[i];  //元素值  
New->Next=NULL;       //新开辟的node总数在末尾 
Tail->Next=New;       //旧尾部Tail的Next就是新的尾部New 
Tail=New;             //旧尾部Tail变成新的尾部New 
}
//printf(“已创建链表!n”); 
return Head; //返回头指针,这步很重要 
}

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” ;
}

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 TraverseList(Position Head)  //遍历 
{
Head=Head->Next;
while(Head!=NULL)  //只要不是尾,就输出其元素的值 
{
printf(“%d “,Head->Element);
Head=Head->Next;
}
printf(“n输出结束!n”);
}

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

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

void FindElement(Position Head)  //根据序号位置找元素 
{
int i=1,SubLabel;
printf(“请输入序号:”);
scanf(“%d”,&SubLabel); 

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

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 ;
}

Head=Head->Next;
while(Head!=NULL)
{
if(i==SubLabel)
{
printf(“序号%d对应的元素为%dn”,SubLabel,Head->Element);  
//判断序号不存在的条件 
break;
}
else if(Head->Next==NULL&&i<SubLabel)
printf(“输入的序号异常!n”);
i++;
Head=Head->Next;
}
}

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

void FindPosition(Position Head)  //根据元素找序号
{
int SubLabel=1;
int X;
printf(“请输入元素值:”);
scanf(“%d”,&X);

Head=Head->Next;
while(Head!=NULL)
{

if(Head->Element==X)
{
printf(“元素%d的序号为%d n”,X,SubLabel);
break;
}
else if(Head->Next==NULL&&Head->Element!=X)  
//判断元素不存在的条件 
       printf(“不存在这个元素!n”);
SubLabel++;
Head=Head->Next;
}
}

void Insert(Position Head)  //插入一个元素 
{
int X,SubLabel;
Position Head0=Head;    //用来重新遍历 

printf(“请输入要插入的值:”);
scanf(“%d”,&X);
printf(“请输入%d要插入的序号:”,X);
scanf(“%d”,&SubLabel);

if(SubLabel>0&&SubLabel<GetListLenth(Head)+2)
{
Position New=NULL;        //代码规范 
New=malloc(sizeof(struct Node));    //开辟内存 
   if(New==NULL)
      {
      printf(“空间不足插入失败!n”);
      exit(0);
      }
while(1)
{
SubLabel–;
if(SubLabel==0)
break;       //打破时Head就是序号对应的位置的再前面一个位置(指针)  
Head=Head->Next;   
}
New->Element=X;       //赋予New的元素值 
New->Next=Head->Next; //将New与下一个元素连接起来 
Head->Next=New;      //将New与上一个元素连接起来  
TraverseList(Head0);  
}
else printf(“输入的序号异常!n”);
}

void Delete(Position Head)  //根据序号删除一个序号 
{
int SubLabel;
Position Deletion;
Position Head0=Head;   //用于重新遍历 

printf(“请输入要删除的元素个数的序号:”);
scanf(“%d”,&SubLabel);
if(SubLabel>0&&SubLabel<GetListLenth(Head)+1)
 //序号存在的情况下进行 
{
while(Head!=NULL)   //这个循环跟插入时的循环作用一样 
{
SubLabel–;
if(SubLabel==0)
break; 
Head=Head->Next;
}
Deletion=Head->Next;   //得到要删除的序号的地址 
Head->Next=Deletion->Next;  //删除:跳过序号对应的地址 
free(Deletion);             //删除:一定要释放空间 
TraverseList(Head0);
}
else printf(“输入的序号异常!n”); 
 } 

int GetListLenth(Position Head)  //获取链表的元素个数 
{
int Lenth=0;
Head=Head->Next;
while(Head!=NULL)
{
Lenth++;
Head=Head->Next;
}
return Lenth;
}