主题：关于结构体的第三次课件

1 静态链表
# include <stdio.h>

struct student{
        int num;
        float score;
        struct student * next;
};

void main()
{
        struct student stus[]={{1001,90.5,NULL},{1002,89,NULL},{1003,79,NULL}};
        struct student * header=stus;
        struct student * pointer=header;
        stus[0].next=&stus[1];
        stus[1].next=&stus[2];
        while(pointer!=NULL)
        {
                printf("学号是%d，成绩是%f\n",pointer->num,pointer->score);
                pointer=pointer->next;
        }
}

2 动态链表
# include <stdio.h>
# include <malloc.h>

struct student{
        int num;
        float score;
        struct student * next;
};

void main()
{
        struct student *p1,*p2,*header;
        p1 =(struct student *)malloc(sizeof(struct student));

        printf("请输入学号：");
        scanf("%d",&p1->num);
        printf("请输入成绩：");
        scanf("%f",&p1->score);

        p2=p1;//1
        header=p1;//3
        p1 =(struct student *)malloc(sizeof(struct student));  
        printf("请输入学号：");
        scanf("%d",&p1->num);
        printf("请输入成绩：");
        scanf("%f",&p1->score);

        p2->next=p1;//2
        p2=p1;
        p1 =(struct student *)malloc(sizeof(struct student));
        printf("请输入学号：");
        scanf("%d",&p1->num);
        printf("请输入成绩：");
        scanf("%f",&p1->score);

        p2->next=p1;
        p1->next=NULL;//4

        p1=header;
        while(p1!=NULL)
        {
                printf("学号是%d，成绩是%f\n",p1->num,p1->score);
                p1=p1->next;
        }

}

改进的循环方法：
# include <stdio.h>
# include <malloc.h>

struct student{
        int num;
        float score;
        struct student * next;
};

void main()
{
        struct student *p1,*p2,*header;
        int n=0;

        p1 =(struct student *)malloc(sizeof(struct student));

        printf("请输入学号：");
        scanf("%d",&p1->num);
        printf("请输入成绩：");
        scanf("%f",&p1->score);

        while(n<2)
        {
                n++;
                if(n==1)
                        header=p1;
                else
                        p2->next=p1;
                p2=p1;
                p1 =(struct student *)malloc(sizeof(struct student));  
                printf("请输入学号：");
                scanf("%d",&p1->num);
                printf("请输入成绩：");
                scanf("%f",&p1->score);
        }

        p2->next=p1;
        p1->next=NULL;

        p1=header;
        while(p1!=NULL)
        {
                printf("学号是%d，成绩是%f\n",p1->num,p1->score);
                p1=p1->next;
        }

}

增加更为灵活的处理方法——一旦输入0，则退出循环
# include <stdio.h>
# include <malloc.h>

struct student{
        int num;
        float score;
        struct student * next;
};

void main()
{
        struct student *p1,*p2,*header;
        int n=0;

        p1 =(struct student *)malloc(sizeof(struct student));

        printf("请输入学号：");
        scanf("%d",&p1->num);
        printf("请输入成绩：");
        scanf("%f",&p1->score);

        while(p1->num!=0)//1
        {
                n++;
                if(n==1)
                        header=p1;
                else
                        p2->next=p1;
                p2=p1;
                p1 =(struct student *)malloc(sizeof(struct student));  
                printf("请输入学号：");
                scanf("%d",&p1->num);
                printf("请输入成绩：");
                scanf("%f",&p1->score);
        }

        //p2->next=p1;
        //p1->next=NULL;
        p2->next=NULL;//2

        p1=header;
        while(p1!=NULL)
        {
                printf("学号是%d，成绩是%f\n",p1->num,p1->score);
                p1=p1->next;
        }

}

3 删除节点
先考虑删除中间的节点情况
# include <stdio.h>
# include <malloc.h>

struct student{
        int num;
        float score;
        struct student * next;
};

void main()
{
        struct student *p1,*p2,*header;
        int n=0;
        int number=0;

        p1 =(struct student *)malloc(sizeof(struct student));

        printf("请输入学号：");
        scanf("%d",&p1->num);
        printf("请输入成绩：");
        scanf("%f",&p1->score);

        while(p1->num!=0)
        {
                n++;
                if(n==1)
                        header=p1;
                else
                        p2->next=p1;
                p2=p1;
                p1 =(struct student *)malloc(sizeof(struct student));  
                printf("请输入学号：");
                scanf("%d",&p1->num);
                printf("请输入成绩：");
                scanf("%f",&p1->score);
        }

        p2->next=NULL;

        p1=header;
        while(p1!=NULL)
        {
                printf("学号是%d，成绩是%f\n",p1->num,p1->score);
                p1=p1->next;
        }

        printf("请输入需要删除的学号：");
        scanf("%d",&number);
        
        p1=header;
        p2=header;
        while(1)
        {
                if(p1->num==number)
                {
                        p2->next=p1->next;
                        break;
                }
                else
                {
                        p2=p1;
                        p1=p1->next;
                }
        }

        p1=header;
        while(p1!=NULL)
        {
                printf("学号是%d，成绩是%f\n",p1->num,p1->score);
                p1=p1->next;
        }
}

增加对第一个节点的删除情况
# include <stdio.h>
# include <malloc.h>

struct student{
        int num;
        float score;
        struct student * next;
};

void main()
{
        struct student *p1,*p2,*header;
        int n=0;
        int number=0;

        p1 =(struct student *)malloc(sizeof(struct student));

        printf("请输入学号：");
        scanf("%d",&p1->num);
        printf("请输入成绩：");
        scanf("%f",&p1->score);

        while(p1->num!=0)
        {
                n++;
                if(n==1)
                        header=p1;
                else
                        p2->next=p1;
                p2=p1;
                p1 =(struct student *)malloc(sizeof(struct student));  
                printf("请输入学号：");
                scanf("%d",&p1->num);
                printf("请输入成绩：");
                scanf("%f",&p1->score);
        }

        p2->next=NULL;

        p1=header;
        while(p1!=NULL)
        {
                printf("学号是%d，成绩是%f\n",p1->num,p1->score);
                p1=p1->next;
        }

        printf("请输入需要删除的学号：");
        scanf("%d",&number);
        
        p1=header;
        p2=header;
        while(1)
        {
                if(p1->num==number)
                {
                        if(p1==header)
                        {
                                header=p1->next;
                                break;
                        }
                        else
                                p2->next=p1->next;
                        break;
                }
                else
                {
                        p2=p1;
                        p1=p1->next;
                }
        }

        p1=header;
        while(p1!=NULL)
        {
                printf("学号是%d，成绩是%f\n",p1->num,p1->score);
                p1=p1->next;
        }
}

考虑删除最后一个节点的情况（不用改）

考虑没有命中的情况
# include <stdio.h>
# include <malloc.h>

struct student{
        int num;
        float score;
        struct student * next;
};

void main()
{
        struct student *p1,*p2,*header;
        int n=0;
        int number=0;

        p1 =(struct student *)malloc(sizeof(struct student));

        printf("请输入学号：");
        scanf("%d",&p1->num);
        printf("请输入成绩：");
        scanf("%f",&p1->score);

        while(p1->num!=0)
        {
                n++;
                if(n==1)
                        header=p1;
                else
                        p2->next=p1;
                p2=p1;
                p1 =(struct student *)malloc(sizeof(struct student));  
                printf("请输入学号：");
                scanf("%d",&p1->num);
                printf("请输入成绩：");
                scanf("%f",&p1->score);
        }

        p2->next=NULL;

        p1=header;
        while(p1!=NULL)
        {
                printf("学号是%d，成绩是%f\n",p1->num,p1->score);
                p1=p1->next;
        }

        printf("请输入需要删除的学号：");
        scanf("%d",&number);
        
        p1=header;
        p2=header;
        while(1)
        {
                if(p1->num==number)
                {
                        if(p1==header)
                        {
                                header=p1->next;
                                break;//去除
                        }
                        else
                                p2->next=p1->next;
                        break;
                }
                else
                {
                        p2=p1;
                        p1=p1->next;
                        if(p1==NULL)
                                break;
                }
        }

        p1=header;
        while(p1!=NULL)
        {
                printf("学号是%d，成绩是%f\n",p1->num,p1->score);
                p1=p1->next;
        }
}

再次整理：
1）去除标注处代码break
2）思考循环的功能，提炼条件
3）整理代码
# include <stdio.h>
# include <malloc.h>

struct student{
        int num;
        float score;
        struct student * next;
};

void main()
{
        struct student *p1,*p2,*header;
        int n=0;
        int number=0;

        p1 =(struct student *)malloc(sizeof(struct student));

        printf("请输入学号：");
        scanf("%d",&p1->num);
        printf("请输入成绩：");
        scanf("%f",&p1->score);

        while(p1->num!=0)
        {
                n++;
                if(n==1)
                        header=p1;
                else
                        p2->next=p1;
                p2=p1;
                p1 =(struct student *)malloc(sizeof(struct student));  
                printf("请输入学号：");
                scanf("%d",&p1->num);
                printf("请输入成绩：");
                scanf("%f",&p1->score);
        }

        p2->next=NULL;

        p1=header;
        while(p1!=NULL)
        {
                printf("学号是%d，成绩是%f\n",p1->num,p1->score);
                p1=p1->next;
        }

        printf("请输入需要删除的学号：");
        scanf("%d",&number);
        
        p1=header;
        p2=header;
        while(p1->num!=number && p1->next!=NULL)
        {
                p2=p1;
                p1=p1->next;
        }

        if(p1->num==number)
                if(p1==header)
                        header=p1->next;
                else
                        p2->next=p1->next;
        
        p1=header;
        while(p1!=NULL)
        {
                printf("学号是%d，成绩是%f\n",p1->num,p1->score);
                p1=p1->next;
        }
}

4 插入节点
首先考虑在中间插入的情况
# include <stdio.h>
# include <malloc.h>

struct student{
        int num;
        float score;
        struct student * next;
};

void main()
{
        struct student *p1,*p2,*header,*p0;
        int n=0;
        int number=0;

        p1 =(struct student *)malloc(sizeof(struct student));

        printf("请输入学号：");
        scanf("%d",&p1->num);
        printf("请输入成绩：");
        scanf("%f",&p1->score);

        while(p1->num!=0)
        {
                n++;
                if(n==1)
                        header=p1;
                else
                        p2->next=p1;
                p2=p1;
                p1 =(struct student *)malloc(sizeof(struct student));  
                printf("请输入学号：");
                scanf("%d",&p1->num);
                printf("请输入成绩：");
                scanf("%f",&p1->score);
        }

        p2->next=NULL;

        p1=header;
        while(p1!=NULL)
        {
                printf("学号是%d，成绩是%f\n",p1->num,p1->score);
                p1=p1->next;
        }

        //需要链表元素的学号升序排列
        p0=(struct student *)malloc(sizeof(struct student));    
        printf("请输入要插入的学号：");
        scanf("%d",&p0->num);
        printf("请输入要插入的成绩：");
        scanf("%f",&p0->score);

        p1=header;
        p2=header;
        while(1)
        {
                if(p1->num<p0->num)
                {
                        p2=p1;
                        p1=p1->next;
                }
                else if(p1->num>p0->num)
                {
                        p2->next=p0;
                        p0->next=p1;
                        break;
                }
        }

        p1=header;
        while(p1!=NULL)
        {
                printf("学号是%d，成绩是%f\n",p1->num,p1->score);
                p1=p1->next;
        }
}

考虑在尾部增加的情况
# include <stdio.h>
# include <malloc.h>

struct student{
        int num;
        float score;
        struct student * next;
};

void main()
{
        struct student *p1,*p2,*header,*p0;
        int n=0;
        int number=0;

        p1 =(struct student *)malloc(sizeof(struct student));

        printf("请输入学号：");
        scanf("%d",&p1->num);
        printf("请输入成绩：");
        scanf("%f",&p1->score);

        while(p1->num!=0)
        {
                n++;
                if(n==1)
                        header=p1;
                else
                        p2->next=p1;
                p2=p1;
                p1 =(struct student *)malloc(sizeof(struct student));  
                printf("请输入学号：");
                scanf("%d",&p1->num);
                printf("请输入成绩：");
                scanf("%f",&p1->score);
        }

        p2->next=NULL;

        p1=header;
        while(p1!=NULL)
        {
                printf("学号是%d，成绩是%f\n",p1->num,p1->score);
                p1=p1->next;
        }

        //需要链表元素的学号升序排列
        p0=(struct student *)malloc(sizeof(struct student));    
        printf("请输入要插入的学号：");
        scanf("%d",&p0->num);
        printf("请输入要插入的成绩：");
        scanf("%f",&p0->score);

        p1=header;
        p2=header;
        while(1)
        {
                if(p1->num<p0->num)
                {
                        p2=p1;
                        p1=p1->next;
                        if(p1==NULL)
                        {
                                p2->next=p0;
                                p0->next=NULL;
                                break;
                        }
                }
                else if(p1->num>p0->num)
                {
                        p2->next=p0;
                        p0->next=p1;
                        break;
                }
        }

        p1=header;
        while(p1!=NULL)
        {
                printf("学号是%d，成绩是%f\n",p1->num,p1->score);
                p1=p1->next;
        }
}

考虑在第一个节点前插入
# include <stdio.h>
# include <malloc.h>

struct student{
        int num;
        float score;
        struct student * next;
};

void main()
{
        struct student *p1,*p2,*header,*p0;
        int n=0;
        int number=0;

        p1 =(struct student *)malloc(sizeof(struct student));

        printf("请输入学号：");
        scanf("%d",&p1->num);
        printf("请输入成绩：");
        scanf("%f",&p1->score);

        while(p1->num!=0)
        {
                n++;
                if(n==1)
                        header=p1;
                else
                        p2->next=p1;
                p2=p1;
                p1 =(struct student *)malloc(sizeof(struct student));  
                printf("请输入学号：");
                scanf("%d",&p1->num);
                printf("请输入成绩：");
                scanf("%f",&p1->score);
        }

        p2->next=NULL;

        p1=header;
        while(p1!=NULL)
        {
                printf("学号是%d，成绩是%f\n",p1->num,p1->score);
                p1=p1->next;
        }

        //需要链表元素的学号升序排列
        p0=(struct student *)malloc(sizeof(struct student));    
        printf("请输入要插入的学号：");
        scanf("%d",&p0->num);
        printf("请输入要插入的成绩：");
        scanf("%f",&p0->score);

        p1=header;
        p2=header;
        while(1)
        {
                if(p1->num<p0->num)
                {
                        p2=p1;
                        p1=p1->next;
                        if(p1==NULL)
                        {
                                p2->next=p0;
                                p0->next=NULL;
                                break;
                        }
                }
                else if(p1->num>p0->num)
                {
                        if(header==p1)
                        {
                                header=p0;
                                p0->next=p1;
                                break;
                        }
                        else
                        {
                                p2->next=p0;
                                p0->next=p1;
                                break;
                        }
                }
        }

        p1=header;
        while(p1!=NULL)
        {
                printf("学号是%d，成绩是%f\n",p1->num,p1->score);
                p1=p1->next;
        }
}

考虑等于的情况
# include <stdio.h>
# include <malloc.h>

struct student{
        int num;
        float score;
        struct student * next;
};

void main()
{
        struct student *p1,*p2,*header,*p0;
        int n=0;
        int number=0;

        p1 =(struct student *)malloc(sizeof(struct student));

        printf("请输入学号：");
        scanf("%d",&p1->num);
        printf("请输入成绩：");
        scanf("%f",&p1->score);

        while(p1->num!=0)
        {
                n++;
                if(n==1)
                        header=p1;
                else
                        p2->next=p1;
                p2=p1;
                p1 =(struct student *)malloc(sizeof(struct student));  
                printf("请输入学号：");
                scanf("%d",&p1->num);
                printf("请输入成绩：");
                scanf("%f",&p1->score);
        }

        p2->next=NULL;

        p1=header;
        while(p1!=NULL)
        {
                printf("学号是%d，成绩是%f\n",p1->num,p1->score);
                p1=p1->next;
        }

        //需要链表元素的学号升序排列
        p0=(struct student *)malloc(sizeof(struct student));    
        printf("请输入要插入的学号：");
        scanf("%d",&p0->num);
        printf("请输入要插入的成绩：");
        scanf("%f",&p0->score);

        p1=header;
        p2=header;
        while(1)
        {
                if(p1->num<p0->num)
                {
                        p2=p1;
                        p1=p1->next;
                        if(p1==NULL)
                        {
                                p2->next=p0;
                                p0->next=NULL;
                                break;
                        }
                }
                else if(p1->num>p0->num)
                {
                        if(header==p1)
                        {
                                header=p0;
                                p0->next=p1;
                        }
                        else
                        {
                                p2->next=p0;
                                p0->next=p1;
                        }
                        break;
                }              
                else
                {
                        break;
                }
        }

        p1=header;
        while(p1!=NULL)
        {
                printf("学号是%d，成绩是%f\n",p1->num,p1->score);
                p1=p1->next;
        }
}

完善整理
# include <stdio.h>
# include <malloc.h>

struct student{
        int num;
        float score;
        struct student * next;
};

void main()
{
        struct student *p1,*p2,*header,*p0;
        int n=0;
        int number=0;

        p1 =(struct student *)malloc(sizeof(struct student));

        printf("请输入学号：");
        scanf("%d",&p1->num);
        printf("请输入成绩：");
        scanf("%f",&p1->score);

        while(p1->num!=0)
        {
                n++;
                if(n==1)
                        header=p1;
                else
                        p2->next=p1;
                p2=p1;
                p1 =(struct student *)malloc(sizeof(struct student));  
                printf("请输入学号：");
                scanf("%d",&p1->num);
                printf("请输入成绩：");
                scanf("%f",&p1->score);
        }

        p2->next=NULL;

        p1=header;
        while(p1!=NULL)
        {
                printf("学号是%d，成绩是%f\n",p1->num,p1->score);
                p1=p1->next;
        }

        //需要链表元素的学号升序排列
        p0=(struct student *)malloc(sizeof(struct student));    
        printf("请输入要插入的学号：");
        scanf("%d",&p0->num);
        printf("请输入要插入的成绩：");
        scanf("%f",&p0->score);

        p1=header;
        p2=header;
        while(p1->num<p0->num && p1->next!=NULL)
        {
                p2=p1;
                p1=p1->next;
        }
        
        if(p1->num>p0->num)
        {
                if(header==p1)
                        header=p0;
                else
                        p2->next=p0;
                p0->next=p1;
        }
        else if(p1->next==NULL)
        {
                p1->next=p0;
                p0->next=NULL;                          
        }

        p1=header;
        while(p1!=NULL)
        {
                printf("学号是%d，成绩是%f\n",p1->num,p1->score);
                p1=p1->next;
        }
}