目录
- 前言
- 一、线性表的链式表示和实现
- 1.1 线性表的表示
- 1.2 基本操作的实现
- 1.3 线性表的链式表示的优缺点
- 总结
前言
本篇文章主要介绍线性表的链式表示
一、线性表的链式表示和实现
1.1 线性表的表示
线性表的链式表示又称为链式存储结构或链式映像
链式存储定义：逻辑上相邻的数据元素在物理存储结构中不一定相邻
线性表的链式表示是用一组物理位置任意的存储单元来存放线性表的数据元素，这组存储单元可能是连续，也可能是不连续的，取决于操作系统的分配策略。
线性表的逻辑关系使用指针表示
线性表
(
a
,
b
,
c
,
d
)
(a,b,c,d)
(a,b,c,d)
链式存储
一个结点由数据域和指针域组成
数据域：数据元素本身本身信息，
指针域：存储其后继结点的存储地址
一般，称指向第一个结点的指针称为链表的头指针
一般，可以将链式存储结构简化如下图表示：
单链表是由头指针唯一确定，因此单链表可以用头指针的名字来命令。
与链式存储结构有关的术语
假设有一个线性表
(
a
1
,
a
2
,
⋯
,
a
n
)
(a_1,a_2,\cdots,a_n)
(a1,a2,⋯,an)，其链式存储结构如下：
头指针：指针链表的第一个结点的指针
首元结点：指链表中存储第一个数据元素
a
1
a_1
a1的结点
头结点：为了便于对链表的处理，在链表的首元结点之前附加的一个结点
假设一个线性表为
(
a
,
b
,
c
,
d
)
(a,b,c,d)
(a,b,c,d)
不带头结点的链式存储结构
带头结点的链式存储结构
讨论
- 如何表示空表
无头结点时，头指针为空时表示空表
有头结点时，当头结点的指针域为空时表示空表 - 在链表设置头节点的好处？
便于首元结点的处理
便于空表和非空表的处理
1.2 基本操作的实现
待续…
1.3 线性表的链式表示的优缺点
.待续…
总结
待续…
