文档文本内容
本节内容
静态链表
王道考研/CSKAOYAN.COM知识总览
王道考研/CSKAOYAN.COM什么是静态链表
静态链表
单链表:各个结点在内存中星罗棋布、散落天涯。
addr
0 头 2
0号结点充当
静态链表:分配一整片连续的内存空间,各个结
1 e 6 “头结点”
2
点集中安置。
2 e 1
1
3 e 4 -1 游标为 -1 表示 每个数据元素 4B,每个游标4B(每个结点共 8B)
已经到达表尾 设起始地址为 addr
4
5
e 的存放地址为 addr + 8*2
1
6 e 3
3 游标充当
“指针”
7
L 头 e e e e NULL
1 2 3 4
8
单链表
9 数据 指向下一个结点
下一个结点
元素 的指针(地址)
数据 的数组下标
元素 (游标)
内存
王道考研/CSKAOYAN.COM用代码定义一个静态链表
a
0
1
2
3
4
5
数组 a 作为
6 静态链表
7
8
9
next
data
(游标)
(数据元素)
内存
王道考研/CSKAOYAN.COM用代码定义一个静态链表
a 是一个
静态链表
a
0
1
2
3
等 等
4
价 价
5
6
7
8
a 是一个
9 Node型数组
可用 SLinkList 定义“一个长度
内存 为 MaxSize 的Node 型数组”
王道考研/CSKAOYAN.COM对猜想的验证
结论:
SLinkList b —— 相当于定义了一个长度
为 MaxSize 的 Node型数组
运行结果
王道考研/CSKAOYAN.COM简述基本操作的实现
静态链表
a
0 头 -1
1
2
3
初始化静态链表:
4
L 头 NULL
5
把 a[0] 的 next 设为 -1
单链表
6
把其他结点的 next 设为一个特殊
7
值用来表示结点空闲,如 -2
8
9
下一个节点
数据 的数组下标
元素 (游标)
内存
王道考研/CSKAOYAN.COM简述基本操作的实现
静态链表
a
0 头 2
1 e 6
2
2 e 1
1
3 e -1
4
查找:
4
从头结点出发挨个往后遍历结点
5
可让 next 为某个
6 e 3 特殊值,如 -2
3
如何判断结
7 插入位序为 i 的结点: 点是否为空?
8 删除某个结点:
①找到一个空的结点,存入数据元素
9
②从头结点出发找到位序为 i-1 的结点
①从头结点出发找到前驱结点
数据 ③修改新结点的 next
②修改前驱结点的游标
元素 ④修改 i-1 号结点的 next
③被删除结点 next 设为 -2
内存
王道考研/CSKAOYAN.COM知识回顾与重要考点
静态链表
a
0 头 2
0号结点充当
1 e 6 “头结点”
2
2 e 1
1
3 e 4 -1 游标为 -1 表示
已经到达表尾
4 -2
5 -2
6 e 3 游标充当“指针” 静态链表:用数组的方式实现的链表
3
-2
7
优点:增、删 操作不需要大量移动元素
用一个特殊的数
8 -2
值标记空闲结点 缺点:不能随机存取,只能从头结点开始依次往后查
-2
9 找;容量固定不可变
下一个节点
数据
的数组下标
适用场景:①不支持指针的低级语言;②数据元素数
元素
(游标)
量固定不变的场景(如操作系统的文件分配表FAT)
王道考研/CSKAOYAN.COM