文档文本内容
本节内容
单链表
定义
王道考研/CSKAOYAN.COM知识总览
a a a a a
1 2 3 4 5
王道考研/CSKAOYAN.COM知识总览
王道考研/CSKAOYAN.COM什么是单链表
顺序表 单链表
逻辑结 (顺序存储) (链式存储)
构:线性
表
L
a
a
1
1
L
a
1
每个结点除了存放数据
a
a
2 每个结点中只 元素外,还要存储指向
2
a
a 存放数据元素 2 下一个节点的指针
3
a a
3 4
a
4
NULL
a
4
a
3
优点:可随机存取,存储密度高 优点:不要求大片连续空间,改变容量方便
缺点:要求大片连续空间,改变容量不方便 缺点:不可随机存取,要耗费一定空间存放指针
王道考研/CSKAOYAN.COM用代码定义一个单链表
单链表
结点
(链式存储)
数据域
L
a
1
指针域
struct LNode * p = (struct LNode *) malloc(sizeof(struct LNode));
a
2 结点
增加一个新的结点:在内存中申请一个结
a
点所需空间,并用指针 p 指向这个结点
4
NULL
a typedef 关键字 —— 数据类型重命名
3
typedef <数据类型> <别名>
p
等价
王道考研/CSKAOYAN.COM用代码定义一个单链表
单链表
结点
(链式存储)
L
a
1
struct LNode * p = (struct LNode *) malloc(sizeof(struct LNode));
a
2 结点
增加一个新的结点:在内存中申请一个结
a
点所需空间,并用指针 p 指向这个结点
4
NULL
a typedef 关键字 —— 数据类型重命名
3
typedef <数据类型> <别名>
p
typedef struct LNode LNode;
LNode * p = (LNode *) malloc(sizeof(LNode));
王道考研/CSKAOYAN.COM用代码定义一个单链表
单链表
(链式存储)
L
a
1
a
2
a
4
NULL
typedef struct LNode LNode;
a typedef struct LNode *LinkList;
3
要表示一个单链表时,只需声明一个头指针 L ,指向单链表的第一个结
点
或: 代码可读性更强
王道考研/CSKAOYAN.COM用代码定义一个单链表
单链表
(链式存储)
L
a
1
a
2 强调这是一
强调返回的
个单链表
是一个结点
a
4
NULL
a
3
强调这是一个单链表 ——使用 LinkList
强调这是一个结点 ——使用 LNode *
王道考研/CSKAOYAN.COM用代码定义一个单链表
强调这是一个单链表 ——使用 LinkList
强调这是一个结点 ——使用 LNode *
王道考研/CSKAOYAN.COM不带头结点的单链表
内存
防止脏数据
注意,此处
并没有创建
一个结点
头指针 L NULL
或:
王道考研/CSKAOYAN.COM带头结点的单链表
内存
头结点不
存储数据
data
next NULL
头指针 L
王道考研/CSKAOYAN.COM不带头结点 带头结点
V.S.
不带头
带头
带头结点,写代码更
方便,用过都说好
不带头结点,写代码更麻烦
data
对第一个数据结点和后续数据结点的
next NULL
处理需要用不同的代码逻辑
对空表和非空表的处理需要用不同的
代码逻辑
头指针 L NULL 头指针 L
王道考研/CSKAOYAN.COM知识回顾与重要考点
头结点不存数据,
只是为了操作方便
王道考研/CSKAOYAN.COM