#include <iostream>
using namespace std;

struct Node
{
     int Value;  
     Node *next;
};

//创建链表
Node *CrtNode(int n)
{
     Node *head;  //声明头指针head
     Node *p,*s;  
     int x;
     head=new Node;  //创建头结点由head指向(空的头结点)
     s=head;        
     cout<<"请输入数字:"<<endl;
     for(int i=0;i<n;i++)
     {
          p=new Node;   //创建一个结点
          cin>>x;
          p->Value=x;   //把输入的x的值赋给创建的结点
          s->next=p;    //把创建的结点由s的next指向
          s=p;          //指针s的指向向后移一个结点
     }
     p->next=NULL;     //最后一个结点的next指向空
     return head;      //返回头指针
}


//显示
void ShowNode(Node *head)
{
Node *p;
//显示除头结点以后所有结点(因为创建时头结点为空）
p=head->next;  
while(p!=NULL)
{
  cout<<p->Value<<"  ";
  p=p->next;
}
cout<<endl;
}


//排序(从大到小)
void sort(Node *head,int n)
{
Node *p,*s;
//对所有值排序(冒泡排序)
for(int i=0;i<n-1;i++)
{
  p=head->next;
  for(int j=0;j<n-i-1;j++)
  {
   s=p->next;
   if(p->Value<s->Value)
   {
    int N=p->Value;
    p->Value=s->Value;
    s->Value=N;
   }
   p=p->next;
  }
}
}

//插入
void InsNode(Node *head)
{
int newValue;
Node *p,*s,*d;

s = head;  //s为头结点
d = s->next;  //d为s的后一个结点
cout<<"请输入需要插入的数:";
cin>>newValue;
p=new Node;     //创建需要插入的结点
p->Value = newValue;
p->next = NULL;
    if(d == NULL)     //如果链表为空，直接插在头结点后面
  s->next = p;
else          
{                //不为空链表则循环
  while(1)  
  {
   if(p->Value >= d->Value)   //如果待插入结点的值不小于d结点则插到d结点前，跳出循环
   {
    s->next = p;
    p->next = d;
    break;
   }
   else if(d -> next == NULL)   //如果待插入的结点的值小于最后一个结点，则插在最后结点之后，跳出循环
   {
    d->next = p;
    break;
   }  
   s = d;        //
   d = d->next;  //指针s，d的指向都向后跳一个结点
  }
}
}



//删除
void DelNode(Node *head)
{
Node *p,*s;
int delValue;
p = head;
s = p->next;
cout<<"请输入需要删除的数:";
cin>>delValue;
if(s == NULL)              //判断空链表
  cout<<"这是一个空链表!"<<endl;
else
{
  while(s != NULL&&s->Value != delValue)  //判断s结点的值是否等于输入的值，不等于则指针p，s指向向后移一个结点
  {
   p = s;
   s = s->next;
  }
  
  if(s != NULL)      //已经找到，则删除S结点    
  {
   p->next = s->next;
   delete s;
  }
  else         //没有找到
   cout<<"没有找到要删除的数值!"<<endl;

}
}

//计算长度
int LenNode(Node *head)
{
Node *p;
//头结点没有计入
p=head->next;
int count=0;
while(p)
{
  p=p->next;
  count++;
}
return count;
}

void contraryNode(Node *head)
{
Node *p,*s,*t = NULL;  //声明一个辅助结点
p = head->next;    //p指向头结点后的第一个结点
while(p != NULL)   //p结点不为空
{
  s = p;        
  p = p->next;  
  s->next = t;  
  t = s;        
}
head->next = t;
}


int main()
{
Node *head;
int n;
char ch;
cout<<"请输入需要创建的链表的结点数:";
cin>>n;
head=CrtNode(n);
sort(head,n);
cout<<"此链表共有 "<<LenNode(head)<<" 个结点."<<endl;
cout<<"排序后：";
ShowNode(head);
contraryNode(head);
cout<<"逆置后：";
    ShowNode(head);
sort(head,n);
cout<<"排序后：";
ShowNode(head);
do
{
        InsNode(head);
  ShowNode(head);
  DelNode(head);
  ShowNode(head);
  cout<<"此链表共有 "<<LenNode(head)<<" 个结点."<<endl;
  cout<<"是否继续操作(Y/N)?";
  cin>>ch;
}
while(ch=='y'||ch=='Y');
return 0;
}