数据结构（三）——线性表
线性结构特点：在数据元素的有限集中，除了第一个元素无直接前驱，最后一个元素无直接后续以外，每个数据元素有且只有一个前驱元素和直接后续元素
线性表及抽象数据类型
1. 线性表定义
线性表（linear list） ）是n个类型相同数据元素的有限序列，通常记作（a 0 , a 1 , …a i-1 , a i , a i+1 …,a n-1 ）。相邻元素存在序偶关系
2. 线性表的抽象数据类型
ADT List{
} ADT List
定义了11 种操作
线性表的顺序存储与实现
线性表的顺序存储是用一组地址连续的存储单元依次存储线性表的数据元素
顺序存储的特点 以数据元素在机内存储地址相邻来表示线性表中数据元素之间的逻辑关系。——数组实现
- 插入操作
时间复杂度分析：平均情况的运行时间
假设在数组下标[0,n]范围内任何一个位置i处插入数据元素的概率是相等的。
假设Ci是在数组下标为i的位置插入数据元素时需要移动数据元素的次数，ci = n-i
此时在数组下标i处插入一个数据元素需要移动数据元素的平均次数为 - 删除操作
线性表的链式存储与实现
链式存储：用指针将存储线性表中数据元素依次串联，需要在每个单元中设置指针来表示表中元素的逻辑关系，增加额外的存储空间开销。
1. 单链表：至少两个域，一个域用于数据元素的存储，另一个域指向其他单元的指针
尾结点特征时next引用为空
注意：单链表中只能通过前驱节点找到后续节点（无前驱指针域——双向链表）
- 单链表中插入节点：在已知某个特定节点引用的基础上在后面插入一个新的节点。（分为表头、表尾以及链表中间插入节点的过程）
2.双向链表
2. 插入操作
3. 删除操作
线性表的单链表实现
1. 使用单链表实现
添加头结点：不存储任何实质的数据对象，next域指向0号元素所在的节点，
三个成员变量
时间复杂度整理(有问题)
| 操作 | 双向链表/单链表 |
|---|---|
| getSize()、isEmpty() | O(1) |
| getPreNode(Object e) | Θ(n) |
| 插入/删除 | Θ(n) |
| replace(int i Object e) | Θ(n) |
两种实现比较
1.基于时间比较
| 线性表操作 | 顺序存储 /链式存储 |
|---|---|
| 查找:基于序号 | Θ(1)/需要从投机诶的那开始查找：O（n） |
| 查找：基于元素查找 | 都需要从序号为0的元素开始查找：Θ(n) |
| 插入（基于元素） | 顺序查找定位相应元素 / 链式存储只需要在定位元素基础上移动指针 |
| 插入（基于序号） | 顺序存储需要移动一半元素/链式不能直接定位，也需要移动一般元素 |
- 基于空间的比较
| 存储结构 | 存储空间 |
|---|---|
| 顺序存储 | 预先静态分配 |
| 链式存储 | 动态分配 |