#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define LEN sizeof(struct Student)
struct Student
{
    long num;
    float score;
    struct Student*next;
};
int n;
int main()
{
    /*-----------------------------程序描述--------------------------------------------
        題目：寫出一個主函數(shù)，分別調(diào)用建立鏈表的函數(shù)create()，輸出鏈表的函數(shù)print(),
              刪除鏈表結(jié)點的函數(shù)del(),插入結(jié)點的函數(shù)insert(),一共5個函數(shù)。
        Author：KillerLegend
        Date：  2013.12.6
    ----------------------------------------------------------------------------------*/
//函數(shù)聲明
    struct Student* create();//創(chuàng)建動態(tài)鏈表的函數(shù)聲明，函數(shù)類型為student結(jié)構(gòu)體類型，返回頭指針
    struct Student* del(struct  Student* ,long);//刪除指定位置結(jié)點的函數(shù)聲明,參數(shù)：鏈表頭結(jié)點+刪除結(jié)點位置+返回頭指針
    struct Student* insert(struct Student*,struct Student*);//插入一個Student類型數(shù)據(jù)的函數(shù)聲明
    void   print(struct Student*);//輸出鏈表中數(shù)據(jù)的函數(shù)聲明，參數(shù)為鏈表的頭指針
//定義變量
    struct Student *head,*stu;//定義動態(tài)鏈表的頭指針與新的結(jié)點
    long del_num;
//建立鏈表操作
    printf("Input records:\n");
    head = create();//建立鏈表并返回頭指針
    print(head);//輸出全部結(jié)點

//刪除結(jié)點操作
    printf("\nInput the deleted number:");
    scanf("%ld",&del_num);
    while(del_num!=0)//當(dāng)輸入學(xué)號為0時結(jié)束循環(huán)
    {
        head = del(head,del_num);//刪除結(jié)點后返回鏈表的頭地址
        print(head);//輸出全部結(jié)點
        printf("Input the deleted number:");
        scanf("%ld",&del_num);
    }
//插入結(jié)點操作
    printf("\nInput the inserted number:");
    stu=(struct Student*)malloc(LEN);//每插入一個結(jié)點需要開辟一個新的結(jié)點
    scanf("%ld %f",&stu->num,&stu->score);
    while(stu->num!=0)//當(dāng)輸入的學(xué)號為0時結(jié)束循環(huán)
    {
        head = insert(head,stu);//返回鏈表的頭地址
        print(head);
        printf("\nInput the inserted number:");
        stu = (struct Student*)malloc(LEN);
        scanf("%ld %f",&stu->num,&stu->score);
    }
    return 0;
}
//建立鏈表的函數(shù)
struct  Student* create()
{
    struct Student *head;
    struct Student *p1,*p2;
    n=0;
    p1=p2=(struct Student *)malloc(LEN);
    scanf("%ld %f",&p1->num,&p1->score);
    head=NULL;
    while(p1->num!=0)
    {
        n++;
        if(n==1)head=p1;
        else p2->next=p1;//第一次執(zhí)行時，這一步是將頭指針指向自身，當(dāng)n從2起，這一步用于使p2指向下一個元素
        p2=p1;//使p2和p1指向同一個存儲區(qū)
        p1=(struct Student*)malloc(LEN);//開辟動態(tài)存儲區(qū)，強制返回struct Student類型的指針
        scanf("%ld %f",&p1->num,&p1->score);
    }
    p2->next=NULL;
    return (head);
}

//刪除結(jié)點的函數(shù)
struct Student* del(struct  Student* head,long num)
{
    struct Student *p1,*p2;
    if(head==NULL)
    {
        printf("List null!\n");
        return (head);
    }
    p1=head;
    while(num!=p1->num && p1->next!=NULL)
    {
        p2=p1;
        p1=p1->next;
    }
    if(num==p1->num)
    {
        if(p1==head)
        {
            head=p1->next;
        }
        else
        {
            p2->next=p1->next;
        }
        printf("Delete:%ld\n",num);
        n=n-1;
    }
    else
    {
        printf("%ld not been found!",num);
    }
    return (head);
}

//插入結(jié)點的函數(shù)
struct   Student* insert(struct Student* head,struct Student * stud)
{
    struct Student *p0,*p1,*p2;
    p1=head;
    p0=stud;
    if(head==NULL)//原來的鏈表是空表
    {
        head=p0;p0->next=NULL;//空表時使插入的結(jié)點作為頭結(jié)點
    }
    else//如果不是空表，則遍歷尋找合適的插入位置
    {
        while((p0->num>p1->num)&&(p1->next!=NULL))//按學(xué)號順序插入，如果插入的學(xué)號數(shù)字比較大，則應(yīng)該向后推移
        {
            p2=p1;
            p1=p1->next;//后移
        }
    }
    if(p0->num<=p1->num)//找到插入的位置，插入的位置是p1所指向的位置之前，也就是p2指向的位置
    {
        if(head==p1)head=p0;//如果插入的位置是頭位置之前，則使head指向p0
        else p2->next=p0;//如果不是頭位置之前，則使p2的next指針指向插入的數(shù)據(jù)地址即p0
        p0->next=p1;//使p0的next指針指向p1，完成了數(shù)據(jù)的加入
    }
    else//插入的學(xué)號位置在最后一個
    {
        p1->next=p0;
        p0->next=NULL;
    }
    n=n+1;//記錄數(shù)加一
    return(head);
}
//輸出鏈表的函數(shù)
void print(struct Student * head)
{
    struct Student * p;
    printf("Now,These %d records are:\n",n);
    p=head;
    if(head!=NULL)
    do
    {
        printf("%ld %5.1f\n",p->num,p->score);
        p=p->next;
    }while(p!=NULL);
}