单链表

struct Node
{
    int data;
    Node *next;
};
//创建链表 输入为数字，如果输入0 链表结束（0不计）
Node *creat()
{
    Node *head,*p,*s;
    int x,cycle=1;
    head=(Node *)malloc(sizeof(Node));
    p=head;
    while (cycle)
    {
        cout<<"please input the data:";
        cin>>x;
        if (x!=0)
        {
            s=(Node*)malloc(sizeof(Node));
            s->data=x;
            p->next=s;
            p=s;
        }
        else 
        {
            cycle=0;
                
        }
    }
    head=head->next;
    p->next=NULL;
    return head;
}



//计算链表的长度
int ComputLength(Node * head)
{
    Node *p;
    int n=0;
    if (head==NULL)
    {
        return 0;
    }
    p=head;
    while(p!=NULL)
    {
        n++;
        p=p->next;
    }
    return n;
}




//打印链表中的数据
void PrintList(Node *head)
{
    Node *p;
    if (head==NULL)
    {
        cout<<"The list has no value!"<<endl;
        return;
    }
    p=head;
    while (p!=NULL)
    {
        cout<<p->data<<endl;
        p=p->next;
    }
}



//删除数据为num的节点 可能是首节点或者其他节点
Node * DeleNode(Node *head,int num)
{
    Node *p1,*p2;
    p1=head;
    while (p1->data!=num&&p1->next!=NULL)
    {
        p2=p1;
        p1=p1->next;
    }
    if (p1->data==num)
    {
        if (p1==head)//删除的是头结点
        {
            head=p1->next;
            delete p1;
        }
        else//删除的是其他节点
        {
            p2->next=p1->next;
        }
    }
    else
        cout<<"Not find the num !"<<endl;
    return head;
}




//删除链表
void DeleList(Node *head)
{
    Node *p;
    p=head;
    while (p!=NULL)
    {
        Node *temp=p;
        p=p->next;
        delete temp;
    }
    cout<<"Delete List Success"<<endl;
}



//在链表中插入节点 三种情况 头 中 尾
Node * InsertNode(Node * head,int num)
{
    Node *pre,*inser,*nex;
    inser=(Node*)malloc(sizeof(Node));
    inser->data=num;
    nex=head;
    while (nex->data<inser->data&&nex->next!=NULL)
    {
        pre=nex;
        nex=nex->next;
    }
    if (inser->data<=nex->data)//判断插入数据在最后一个节点之前（包括最后一个节点）
    {
        if (nex==head)//插入头前
        {
            head=inser;
            inser->next=nex;
        }
        else//插入中部
        {
            pre->next=inser;
            inser->next=nex;
        }
    }
    else//大于最后一个元素 插入尾部
    {
        nex->next=inser;
        inser->next=NULL;
    }
    return head;
}