【数据结构】二、线性表

2.1. 定义与特点

定义

? 具有相同数据类型的 \(n(n\geq0)\) 个数据元素的有限序列。\(n\) 是表长，当 \(n=0\) 时该线性表是一个空表。若用 \(L\) 表示线性表，一般表示为：
\[ L=(a_1,a_2,...,a_i,a_{i+1},a_n) \]
特点

• 元素个数有限
• 元素具有逻辑上的顺序，有先后次序
• 元素都是数据元素，每个元素都是单个元素
• 元素数据类型都相同，每个元素的存储空间都相同
• 元素具有抽象性，仅讨论元素间的逻辑关系，不讨论元素的具体意义

操作

1. 初始化表
2. 求表长
3. 按值查找位
4. 按位查找值
5. 插入元素
6. 删除元素
7. 输出元素
8. 空值判断
9. 销毁操作

2.2. 线性表的顺序表示——顺序表

定义

? 用一组地址连续的储存单元依次存储线性表中的数据元素，逻辑上相邻的两个元素在物理位置上也相邻。

特点

• 随机访问，通过首地址和元素序号即可在时间 \(O(1)\) 内找到指定元素
• 存储密度高，每个节点值存储数据元素
• 元素逻辑相邻则物理相邻，插入和删除操作需要移动大量元素

基本操作

2.3. 线性表达链式表示——链表

意义

? 由于顺序表的插入删除需要移动大量元素，影响效率，由此引入链表（链式存储）。

定义

? 通过一组任意的存储单元来存储线性表中的数据元素。每个链表节点一般由【数据 | 指针】这样的结构构成，指针用于记录下一个或上一个链表节点的内存地址，从而达到连接的效果。

特点

• 附加的指针域消耗空间
• 非随机存取，查找某点时需要从表头开始遍历

构造

? 每一个链表必然有一个 \(头指针\) 来指向链表的第一个节点，该节点如果不用来存储数据（或者存储链表长度），则称为头节点。头节点的指针指向第一个有意义的数据节点。

? 引入头结点的优点：

• 由于开始节点的地址被放在头节点的指针里，所以在链表的开始节点上的操作和其他位置一样，无需特殊处理。
• 无论链表是否为空，头指针都要指向一个头节点，而非空指针，这样就把空表和非空表的处理统一起来了。

基本操作

2.4. 顺序表与链表的比较

选择

1. 存储

   长度可预测 顺序表 更合适，长度不可预测 链表 更合适

2. 运算

   插入删除操作频繁则 链表 更合适，读写操作频繁的 顺序表 更合适

3. 环境

   顺序表在大多数语言中都可实现，链表基于指针，最好是c和c++。（当然高级语言有那种不限制元素类型和数量的表结构！比如python的list和Java的array）

2.5. 代码实现

过于简单，懒得写了~！（遁~~~

（编辑：ASP站长网）