#include<IOSTREAM>
using namespace std;

typedef struct Single_link
{
    int data;
    struct Single_link *next;
}node;

//单链表的创建
node *Create()
{
    node *head,*p,*s;
    int x,cycle=1;

    head=(node *)malloc(sizeof(node));
    p=head;

    cout<<"Input the elements of the link:"<<endl;
    while (cycle)
    {
        
        cin>>x;

        if (x!=0)
        {
            s=(node *)malloc(sizeof(node));
            s->data=http://www.mamicode.com/x;
            
            p->next=s;
            p=s;
        }
        else
            cycle=0;
    }
    head=head->next;
    p->next=NULL;

    return head;
}
//单链表测长
int length(node *head)
{
    node *p;
    p=head;
    int count=0;
    while (p!=NULL)
    {
        p=p->next;
        count++;
    }
    return count;
}
//////////////////////////////////单链表插入///////////////////////////////////////
node *Insert(node *head,int element)
{
    //p是遍历指针，q用于保存插入节点的位置节点，s是将要插入的节点
    node *p,*q,*s;
    p=head;

    //创建插入的新节点
    s=(node *)malloc(sizeof(node));
    s->data=http://www.mamicode.com/element;

    while (s->data>p->data && p->next!=NULL)
    {
        q=p;
        p=p->next;
    }
    if (s->data<=p->data)
    {
        if (head==p)
        {
            s->next=p;
            head=s;
        }
        else
        {
            q->next=s;
            s->next=p;
        }
    }
    else
    {
        p->next=s;
        s->next=NULL;
    }

    return head;
}
/////////////////////////////单链表删除/////////////////////////////////////////////
node *del(node *head,int element)
{
    //p是遍历指针，q用于保存删除的位置节点
    node *p,*q;
    p=head;
    
    while (p->data!=element && p->next!=NULL)
    {
        q=p;
        p=p->next;
    }
    if (p->data=http://www.mamicode.com/=element)
    {
        if (head==p)
        {
            head=p->next;
            free(p);
        }
        else
        {
            q->next=p->next;
        }
    }
    else
    {
        cout<<" Not find the delete element."<<endl;
    }

    return head;
}
///////////////////////////////单链表逆序///////////////////////////////////////////
node *Reverse(node *head)
{
    node *p,*q,*s;

    if (head==NULL && head->next==NULL)
    {
        return head;
    }
    p=head;
    q=p->next;

    while (q)
    {
        s=q->next;
        q->next=p;
        p=q;
        q=s;
    }
    head->next=NULL;
    head=p;

    return head;
}

///////////////////////////////单链表排序///////////////////////////////////////////
node *Sort(node *head)
{
    node *p;
    int n;
    int temp;
    n=length(head);

    if(head==NULL && head->next==NULL)
    {
        return head;
    }

    p=head;
    for (int j=1;j<n;j++)
    {
        p=head;
        for (int i=0;i<n-j;i++)
        {
            if (p->data > p->next->data)
            {
                temp=p->data;
                p->data=http://www.mamicode.com/p->next->data;
                p->next->data=http://www.mamicode.com/temp;
            }
            p=p->next;
        }
    }

    return head;
}
////////////////////////打印单链表///////////////////////////////////////////////////////////
void print(node *head)
{
    node *p;
    p=head;

    int n=length(head);
    cout<<"链表中共有"<<n<<"记录."<<endl;

    if (head!=NULL)
    {
        cout<<"链表中元素为："<<endl;
        while (p!=NULL)
        {
            cout<<p->data<<" ";
            p=p->next;
        }
        cout<<endl;
    }
}
int main()
{
    node *head;
    int n;

    head=Create();
    print(head);

    head=Sort(head);
    print(head);

    cout<<"Input the insert number:"<<endl;
    cin>>n;
    Insert(head,n);
    print(head);

    cout<<"Input the delete number:"<<endl;
    cin>>n;
    del(head,n);
    print(head);

    head=Reverse(head);
    print(head);

    return 0;
}