------第二节-----------------第二讲----单链表的基本操作---------

//包括建立链表的creat(); 输出连标的print(), 删除链表中结点的delete();
#include<stdio.h>
#include<malloc.h>
#define LEN sizeof(struct student)
struct student
{
    long num;
    float score;
    struct student *next;
};
int n;
int main()//开始主函数.
{
    struct student *creat();//    声明   构建链表函数
    struct student *del(struct student *,long);   //删除其中一个节点的时候    需要传送  链表的  首地址
    struct student *insert(struct student *,struct student *);   //
    void print(struct student *);
    struct student *head,stu;
    long del_num;                   //
    printf("input recoders :
");
    head=creat();
    print(head);
    printf("inpit the deleted number :
");
    scanf("%ld",&del_num);
    head=del(head,del_num);
        print(head);
    printf("input the inserted recoder :
");
    scanf("%ld%f",&stu.num,&stu.score);
    head=insert(head,&stu);
    print(head);
}
struct student *creat()   //构建 链表,其实挺简单的....他的关键就是,你要时刻牢记   你键入的东西是储存到物理内存上了,head是头指针  其中的指针域存放的是下一个
{                         //结点的地址     要想方法   让一个个节点彼此之间建立起来联系,,,,最后 手里 拉一个头指针就能知道  这个链表中的所有元素
    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++;                          //n  不仅仅用于下面的  指针 赋值选择   还有  计算  结点个数的功能
        if(n==1)
            head=p1;
        else
        {
            p2->next=p1;      /////////////////////
            p2=p1;           /////////////////////    就这样  一个个节点彼此之间建立起来了联系.
        }                                           //其中的p2永远代表的都是 链表中的最后一个节点.
        p1=(struct student *)malloc(LEN);
        scanf("%ld%f",&p1->num,&p1->score);
    }
    p2->next=NULL;
    return head;
}
struct student *del(struct student *head,long num)   //接收需要修改的链表的头指针 和  需要删除学生的学号.....
{
    struct student *p1,*p2;
    if(head==NULL)                       //     ~~~~
    {
        printf("
list null!
");
        return head;
    }
    p1=head;                              //在不修改原有链表的情况下  进行  一下操作   (让  p1=head的原因就是  不修改 head指向的地址.)
    while(num!=p1->num&&p1->next!=NULL)   //  跳出这个循环的时候  可能有两种情况
    {
        p2=p1;             //1:  成功的找到了储存该学生信息的结点, 并且 p1指向该节点 p2指向  该节点的上一个节点...
        p1=p1->next;       //2:  直到最后也没找到那个学生 所以现在      节点在最后一个节点处,该节点储存着最后一个学生的信息,但是它的指针域是空的.
    }
    if(num==p1->num)       //第一种情况下
    {
        if(p1==head)      //判断 是不是  第一个节点就是 想删除的学生
            head=p1->next;   //如果是的话  这样做
        else               //不是的话
            p2->next=p1->next;  //让该学生的上一个结点的指针域储存这个节点的指针域的内容,这样就将这个节点删除了.
        printf("deleted %ld 
",num);
        n--;                       //     节点个数减一
    }
    else                       //第二种情况下........
        printf("%ld not been found !
",num);
    return head;
}
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;
    }
    else
    {
        while((p0->num>p1->num)&&(p1->next!=NULL))  //本来链表是有顺序的     首节点储存的学号比较小    找到自己的位置或者 遍历到最后跳出循环.
        {
            p2=p1;            
            p1=p1->next;
        }
        if(p0->num<=p1->num)
        {
            if(head==p1)        //链表中只有一个节点的情况下
                head=p0;
            else                //不只有一个
                p2->next=p0;    //前面 接上去
            p0->next=p1;        //不管 以前有几个节点(大于零)  都需要后续加上
         }
        else                   //当插入这个人的学号比较大的时候
        {
            p1->next=p0;        //前面 给一个地址
            p0->next=NULL;       //后面续一下
        }
    }
    n++;                         //节点  长度高了
    return head;
}
void print(struct student *head)//这个就比较简单了,不写了.
{
    struct student *p;
    printf("
 now ,these %ld records are :
",n);
    p=head;
    if(head!=NULL)
        do
        {
            printf("%ld%5.1f
",p->num,p->score);
            p=p->next;
        }while(p!=NULL);
}

typedef struct NNode
{
    int Tag    //标识语:    0代表下面节点是单元素,1表示节点是广义表
    union
    {
        ElementType Date;
        struct GNode *Sublist;        //这里就有点类似于递归调用了.  //只想另外一个广义表
    }URegion;
struct GNode *Next;//指向后继节点
}GList;

/* 下面说一下多重链表   上面的 广义表就是  一个多重链表
多重链表 :链表中的结点可能   同时隶属于 多个链
→  多重链表 中指针的指针域会有多个   如前面 例子包含了 next 和sublist    两个指针域
→  但包含两个指针域的 不一定是多重链表     例如 双向链表就不是  多重链表
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
多重链表  有广泛的用途
  基本上如 树,图这样相对复杂的数据结构都可以采用 多重链表的方式实现储存.
  */
  //下面    说一下自己的理解.      链表应该是计算机里面  十分重要的工具,它可以表示  不同数据之间的关系
  //   可以对生活中比较复杂的问题做出形象的描述.
//↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
/*下面就说一个生活中  可能用到链表的  地方
1:  在大学生 选课的时候就可以  将学生们的选课情况 用  二维数组表示出来,但是用二维数组表示的时候
    因为每一个学生选课的数量 远远小于 可选课的数量  所以 会导致二维数组中存放了很多的零(稀疏矩阵:自己去看教科书目录),导致  时间空间的 大大浪费
    所以 在这个时候 就应该考虑让 链表出手解决这个问题.*/
//   采用 一种典型的多重链表 ----十字链表来储存 稀疏矩阵
//    只储存矩阵非零的元素项.     
//          节点的数据域包括:  行坐标row  列坐标col   数值value
//    每个节点 通过两个指针域 把同行,同列串起来
//    行指针 right
//    列指针 down
/*在知道了 一个数据的行号和列好之后就知道了这个数据的位置信息*/
//这样可以看出每一个节点  同时属于所在行和所在
//注意多重链表和 联合体的结合使用
/*课后作业,最好 完成一个   链表储存  学生选课信息*/