引入

上一节，我们讲了如何建立一个静态链表，今天我们就来说说如何建立一个动态链表。还记得他们的区别吗？

静态链表
所有结点都是手动创建的，不是程序创建的。
不能随时创建和随时释放。

动态链表

在程序执行过程中，从无到有地建立起一个链表，即一个一个地开辟结点和输入各个结点数据，并建立起先后相连的关系的链表为动态链表。

例子引入

建立有3名学生的单向动态链表

#include <stdio.h>
#include <stdlib.h>
#define LEN sizeof(struct Student)

struct Student{
long num;
float score;
struct Student *next;
};

int n;

struct Student *create(void){
struct Student *p1,*p2, *head;
p1=p2=(struct Student *)malloc(LEN);
scanf("%ld %f",&p1->num,&p1->score);
while(p1->num!=0){
n=n+1; 
if(n==1){
head=p1;
}else{
p2->next=p1;
}
p2=p1; 
p1=(struct Student *)malloc(LEN); 
scanf("%ld %f",&p1->num,&p1->score);
}
p2->next =NULL; 
return (head); 
}

int main(){
struct Student *pt;
pt=create(); 
printf("\n学号是：%ld\n成绩是：%3.1f\n",pt->num , pt->score);
return 0;
}

输出结果

输入：
0101001 88.6
101002 77.4
101003 95.3
0 0

学号是：101001
成绩是：88.6

代码逐行解析

#include <stdio.h>
#include <stdlib.h>
//因为要用到 malloc 函数创建动态存储空间
#define LEN sizeof(struct Student)  //注意，不要加分号

struct Student{
long num;
float score;
struct Student *next;
};
// 创建全局链表结构体类型

int n; //用于计数，看看到哪个结点了

struct Student *create(void){
//创建一个指针函数，返回 student 类型数据地址
struct Student *p1,*p2, *head;
// p1 用于作为节点进行操作
// p2 作为 p1 的备份，用于存储新 p1 的地址
// head 是链表的头指针，第一个 p1 的地址要给 head
p1=p2=(struct Student *)malloc(LEN);
//创建 Student 类型动态存储空间，把地址传给 p1 和 p2
//记住，p2 是替身，要存地址的
scanf("%ld %f",&p1->num,&p1->score);
//p1 是我们主要操作的节点，所以都传递给 p1
while(p1->num!=0){
// 开始判断，结点 1 有没有数据，如果有，进入结点处理环节
n=n+1; //开始计数，现在表明有一个结点了
if(n==1){
//如果这是第一个结点，那么把 p1 地址传给 head
head=p1;
}else{
//如果不是第一个结点，那么就把地址传递给替身 p2
//注意，此时p2 还是上一个结点
p2->next=p1;
}
p2=p1; //把 p2 作为当前这个 p1 的替身
p1=(struct Student *)malloc(LEN); //p1重新获取动态存储空间
scanf("%ld %f",&p1->num,&p1->score);
// 新的动态存储空间 p1 获取值
}
p2->next =NULL; 
//处理表尾，最后一个动态存储空间的 next 记录为 NULL 即 0；
return (head); //返回链表头，即可找到整个链表
}

int main(){
struct Student *pt;
//建立一个 Student 的指针，方便存储 head 链表头指针
pt=create();  // 调用 create 创建链表并获得链表头指针
printf("\n学号是：%ld\n成绩是：%3.1f\n",pt->num , pt->score);
// 输出的是链表头指针所指向的第一个结点的数据
return 0;
}

解析

一定要养成以下重要的思路：

谈起链表，一定有表头、表尾
头指针，设置计数，如果是第一个结点，将地址传递给头指针，搞定。
表尾，设置条件，判断为最后一个结点，将尾节点的 next 地址设置为 NULL，即 0；
传递地址，使用替身，p2 为 p1的替身，p1 已经是新地址了，p2 还是老结点，就可以存储 p1 的新地址了，循环往复。
记得返回的是表头，链表很有趣，知道表头就能知道链表中所有结点的情况，切记。
我们在创建动态存储空间时，地址大小一定要匹配，使用sizeof (类型名) 就能准确获取该系统中该类型的存储空间了。

尾巴

这是我的个人学习笔记，主要是应付考研复习使用，充斥着一些吐槽和个人观点，并不严谨，欢迎大家参考、指正。