第2章 线性表

2.1 线性表的定义和特点

对于非空的线性表和线性结构，其特点是：

1. 存在唯一的一个被称作“第一个”的数据元素；
2. 存在唯一的一个被称作“最后一个”的数据元素
3. 除第一个以外，结构中的每个数据元素均只有一个前驱
4. 除最后一个以外，结构中的每个数据元素均只有一个后继

2.2 案例引入

2.3 线性表的类型定义

2.4 线性表的顺序表示和实现

2.4.1 线性表的顺序存储表示

线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素，这种表示也称作线性表的顺序存储结构或顺序映像。这种存储结构的线性表为顺序表

2.5 线性表的链式表示和实现

2.5.1 单链表的定义和表示

线性表链式存储结构的特点是：用一组任意的存储单元存储线性表的数据元素。结点包含两个域：存储数据元素信息的域称为数据域；存储直接后继存储位置的域称为指针域。指针域中存储的信息称作指针或链。n个结点链结一个链表，即为线性表

链表分为单链表、循环链表、双向链表

2.5.2 单链表基本操作的实现

2.5.3 循环链表

2.5.4 双向链表

2.6 顺序表和链表的比较

2.7 线性表的应用

2.8 案例分析和实现

2.9 小结

1. 线性表的逻辑结构特性是指数据元素之间存在着线性关系，在计算机中表示这种关系的两种不同的存储结构是顺序存储结构和链式存储结构，即顺序表和链表
2. 顺序表是随机存取结构，链表是顺序存取结构
3. 单链表、循环链表、双向链表的对比

易错点

• 线性表的顺序存储结构是一种随机存取的存储结构
• 引入头节点的优点：
  1. 由于第一个数据结点的位置存放在头结点的指针域中，因此在链表的第一个位置上的操作和在表的其他位置上的操作一致，无须进行特殊处理
  2. 无论链表是否为空，其头指针都是指向头结点的非空指针，因此空表和非空表的处理也就得到了统一

---

• Previous
  数据结构复习
• Next
  链表实现

---