链表

一、链表（linkedlist）

1. 定义：动态分配内存的数据结构，按需随时开辟，随时释放

2. 由结点组成

3. 结点：

4. 数据成员：存储数据

5. 指针成员：储存下一结点的首地址

6. 定义形式：

   struct stu_node{
       int num;
       float score;
       struct stu_node *next;        //next指向下一个结点
   };
   

7. 表头结点的地址最为重要，常定义一个头指针来存放表头结点的地址，用来找到该链表

8. 对链表的操作：
   1. 建立链表
   2. 输出链表
   3. 删除结点
   4. 插入结点

二、建立链表

1. 逐个开辟，并且建立联系
2. 两种方法：
3. 表尾添加法（常用）：
   1. 将新结点插入表尾
   2. 结点的次序和输入顺序一致
4. 表头添加法
   1. 将新结点插入表头
   2. 节点的次序和输入顺序相反
5. 步骤：
6. 建立头指针及头结点（头结点不放数据）
7. 循环输入数据，并连接结点

8. 最后一个结点地址域空置

9. 实例：学生管理系统

#include <stdio.h>
#include <stdlib.h>
typedef struct stu_node{
    int num;
    float score;
    struct stu_node *next;
}stu;
#define LEN sizeof(struct stu_node)
stu * creat(){              //无参数
    stu *p1 = NULL,*p2 = NULL,*head = NULL;
    int n;
    float s;
    printf("请输入学号和成绩（输入0时结束）\n");
    scanf("%d %f",&n, &s);              //读取学号与成绩
    while(n!=0){        //判断是否继续
        p1 = (stu *)malloc(LEN);        //开辟一块内存
        p1->num = n;                    //读入学号和成绩
        p1->score = s;
        if(head == NULL) head = p1;     //头指针为空，则指向表头结点
        else p2->next = p1;             //头指针不为空，则p2的指针成员指向p1
        p2 = p1;                        //p2指向新的表尾结点
        scanf("%d %f",&n,&s);           //再次读取数据
    }
    p2->next = NULL;                    //结尾
    return head;                        //返回头指针
}

三、输出链表

1. 遍历
2. 使用
3. 通过头指针找到链表
4. 输出，并利用一个指针指向下一个结点
5. 重复2，直到指针指向NULL
6. 实例：学生管理系统

void list(stu *head){
    stu *p;
    if(head==NULL)printf("链表为空\n" );
    else{
        p = head;
        while (p != NULL){
            printf("%d,%5.2f\n",p->num,p->score);
            p=p->next;                  //令p指向下一个结点
        }
    }
}
void main(){
    stu *head;                          //定义一个结点类型的指针变量
    head = creat();                     //创建链表
    list(head);                         //输出
}

四、删除结点

五、插入结点