带头结点的单链表操作

/*带头结点的单向链表操作*/
/*核心：pre=head(pre为前驱结点)*/
/*为方便，结构体只定义一个数据*/
#include"stdio.h"
#include"stdlib.h"
typedef struct Student
{
    int num;
    struct Student *next;
}Stu;


//建立链表
Stu *Creat()
{
    Stu *pre,*p,*head; //pre为p的前驱结点
    pre=head=(Stu *)malloc(sizeof(Stu)); //建立头结点
    head->next=NULL; //不要忘记将头结点指针域置空
    p=(Stu *)malloc(sizeof(Stu)); //建立第一个结点
    scanf("%d",&p->num);
    while(p->num!=0) //输入0，链表建立结束
    {
        pre->next=p;
        pre=p;
        p=(Stu *)malloc(sizeof(Stu));
        scanf("%d",&p->num);
    }
    pre->next=NULL; //pre已指向链尾
    return head;
}


//遍历链表
void Output(Stu *head)
{
    Stu *p;
    p=head->next;
    printf("list:\n");
    while(p!=NULL)
    {
        printf("%d\n",p->num);
        p=p->next;
    }
}


//删除结点
/*需考虑到链表中有多个结点含有待删键值*/
Stu *Delete(Stu *head,int num)
{
    Stu *pre,*p;
    int sign=0; //找到被删结点的标志，0表示未找到，1表示找到
    pre=head; //p的前驱结点
    p=head->next;
    while(p!=NULL) //遍历链表，找到则删之
    {
        if(p->num==num)
        {
            sign=1;
            pre->next=p->next; //删除结点
            free(p); //别释放错了，把pre释放了
        }
        else //*** 关键之处 ***
            pre=p;
        p=pre->next; //考虑到链表中有多个结点含有待删键值，所以不管有没有找到，p始终下移至空。
    }
    if(sign==0) //未找到待删结点
        printf("%d is not in the list!\n");
    return head;
}


//插入结点1(原链表已排序)
/*<不要考虑插入到链尾>*/
Stu *Insert(Stu *head,int num)
{
    Stu *pre,*p,*New_code;
    pre=head;
    p=head->next;
    New_code=(Stu *)malloc(sizeof(Stu)); //开辟一个内存存放新结点
    New_code->num=num;
    while(p!=NULL&&p->num<New_code->num)
    {
        pre=p;
        p=pre->next; //等价于p=p->next;
    }
    pre->next=New_code;
    New_code->next=p;
    return head;
}
/*注意：
在while(p!=NULL&&p->num!=num) 中，p!=NULL与p->num!=num的顺序不能颠倒。
如果写成：while(p->num!=num&&p!=NULL)，将导致程序崩溃。
因为程序从左至右进行运算，先进行p->num运算，再进行p!=NULL运算。当p==NULL时，
p->num运算会泄漏内存，引起程序崩溃！
*/



//插入结点2(原链表已排序)
/*<需要考虑插入到链尾>*/
Stu *Insert_2(Stu *head,int num)
{
    Stu *pre,*p,*New_code;
    pre=head;
    p=head->next;
    New_code=(Stu *)malloc(sizeof(Stu)); //开辟一个内存存放新结点
    New_code->num=num;
    while(New_code->num>p->num&&p->next!=NULL)
    {
        pre=p;
        p=p->next;
    }
    if(New_code->num<=p->num) //待插入结点不在链尾
    {
        pre->next=New_code;
        New_code->next=p;
    }
    else //待插入结点在链尾
    {
        p->next=New_code;
        New_code->next=NULL;
    }
    return head;
}


//统计链表长度
int Length(Stu *head)
{
    Stu *p;
    int i=0;
    p=head->next;
    while(p!=NULL)
    {
        i++;
        p=p->next;
    }
    return i;
}



//查找结点<可查找多个结点>
void Search(Stu *head,int num)
{
    Stu *p;
    int sign=0;
    p=head->next;
    while(p!=NULL)
    {
        if(p->num==num)
        {
            sign=1;
            printf("%d has been fond!\n",num);
        }
        p=p->next;
    }
    if(sign==0)
        printf("%d is not in the list!\n",num);
}



//链表选择排序
Stu *Selectsort(Stu *head)
{
    Stu *p,*q,*min;
    int temp;
    for(p=head->next;p!=NULL;p=p->next)
    {
        min=p;
        for(q=p->next;q!=NULL;q=q->next)
            if(q->num<min->num)
                min=q;
        if(min!=p)
        {
            temp=p->num;
            p->num=min->num;
            min->num=temp;
        }
    }
    return head;
}


//链表逆置
Stu *Reverse(Stu *head)
{
    Stu *pre,*cur,*temp; //cur为当前结点，pre为前驱结点，temp为临时变量，保存前驱结点的地址。
    cur=head->next;
    pre=NULL;
    while(cur->next!=NULL)
    {
        temp=pre;
        pre=cur;
        cur=cur->next;
        pre->next=temp;
    }
    cur->next=pre;
    head->next=cur; //不懂就画个图，一步一步推。
    return head;
}

/*这样也可*/
//链表逆置
Stu *Reverse_2(Stu *head)
{
    Stu *pre,*cur,*temp; //cur为当前结点，pre为前驱结点，temp为临时变量，保存前驱结点的地址。
    cur=head->next;
    pre=NULL;
    while(cur!=NULL)
    {
        temp=pre;
        pre=cur;
        cur=cur->next;
        pre->next=temp;
    }
    head->next=pre; //不懂就画个图，一步一步推。
    return head;
}


void main()
{
    int Length(Stu *head);
    void Output(Stu *head);
    void Search(Stu *head,int num);
    Stu *Creat();
    Stu *Delete(Stu *head,int num);
    Stu *Insert(Stu *head,int num);
    Stu *Selectsort(Stu *head);
    Stu *Reverse(Stu *head);
    Stu *head;
    int del_num,insert_num,search_num,length;
    printf("input data:\n");
    head=Creat();
    printf("The original ");
    Output(head);
    head=Selectsort(head);
    printf("The sorted ");
    Output(head);
    length=Length(head);
    printf("The length of the list is:%d\n",length);
    printf("input the number you want to search:");
    scanf("%d",&search_num);
    Search(head,search_num);
    printf("input the number you want to delete:");
    scanf("%d",&del_num);
    head=Delete(head,del_num);
    Output(head);
    printf("input the number you want to insert:");
    scanf("%d",&insert_num);
    head=Insert(head,insert_num);
    Output(head);
    head=Reverse(head); //不能在插入之前逆置，若逆置，将改变原来的排序方向，导致结果错误。
    printf("The reversed ");
    Output(head);
}