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

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

struct Node
{
int Element;   //元素 
//int Subscrit;  //下标 
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();
TraverseList(Head);  //先遍历 

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

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

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

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

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

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