引入
上一节,我们讲了如何建立一个静态链表,今天我们就来说说如何建立一个动态链表。还记得他们的区别吗?
静态链表
所有结点都是手动创建的,不是程序创建的。
不能随时创建和随时释放。
动态链表
在程序执行过程中,从无到有地建立起一个链表,即一个一个地开辟结点和输入各个结点数据,并建立起先后相连的关系的链表为动态链表。
例子引入
建立有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 (类型名)就能准确获取该系统中该类型的存储空间了。
尾巴
这是我的个人学习笔记,主要是应付考研复习使用,充斥着一些吐槽和个人观点,并不严谨,欢迎大家参考、指正。
评论