线性表
| 线性表 | |
|---|---|
| 术语名称 | 线性表 |
| 英语名称 | list |
| 别名 | linear list, 表, 列表 |
线性表(list)，有时也简称表，是一种数据的逻辑结构，其中含有零至多个相同特性数据元素的有限序列。 非严谨场合下，线性表经常被使用数组代指。
注：一般英语文献只使用 list ，修饰词 linear 是特殊区别与其他类型的表时才会用的。因此本文将 list 作为主要英语翻译。
线性表中的表(list)指含多个相同元素，而线性(linear)指逻辑上其中仅含有元素，不含有其他由元素进一步构成的内部结构。
定义
逻辑结构
线性表(list)是一种逻辑结构。 其中含有零至多个数据对象，称为元素(element)。其中所有元素逻辑上按顺序排列。
相关术语
线性表中的元素应该有同一种特性，或者说同一种逻辑类型，称为线性表的基类型(base type)。
线性表中的元素是确定的、有限的，其数目称为线性表的长度(length)或大小(size)。若一个线性表的长度为 0 ，即其中不含有任何元素，称这个线性表是空表(empty list)或称其是空的(empty)或其是空(nil)。
线性表的元素有顺序，其中顺序上处于前方的一端称为头部/前端(front)，后方的一端称为尾部/后端(rear/back)。 位于头部的元素是一个头部元素/首元素，除首元素外，每个元素都一一对应于一个前趋元素(preceder)； 位于尾部的元素是一个尾部元素/尾元素，除尾元素外，每个元素都一一对应于一个后继元素(succeeder)。
元素在线性表中的序号称为索引(index)或下标(subscript)。出于一般形式化表示的习惯，本章节中元素的下标从 1 开始计数。 对元素而言， [math]\displaystyle{ n }[/math] 个元素的线性表中，元素下标分别为 [math]\displaystyle{ 1, 2, \cdots, n }[/math] 。 方便起见，当说明元素前后的位置时，我们将下标为 [math]\displaystyle{ n }[/math] 的元素前的位置也标记为 [math]\displaystyle{ n }[/math] ，并将最后一个元素之后的位置记为 [math]\displaystyle{ n+1 }[/math] 。 注意当下标不从 1 开始时，这些数字都会随之变化。
ADT
记以集合 [math]\displaystyle{ E }[/math] 中元素构成的线性表的集合为 [math]\displaystyle{ L }[/math] ，空表为 [math]\displaystyle{ \mathrm{nil} }[/math] ， 并记非空线性表集合为 [math]\displaystyle{ L^* = L\setminus\{\mathrm{nil}\} }[/math] 。 为区分线性表中重复出现的相同元素，记已经在线性表中的元素为多重集 [math]\displaystyle{ P }[/math] ，其元素可以视为 [math]\displaystyle{ E\times \mathbb{N}^* }[/math] 中的元素。
则线性表中的或数据对象为：
[math]\displaystyle{ D = \{a_i \mid a_i \in E, i=1,2,\dots,n, n\geq 0\} }[/math]
逻辑形式上约定数据关系为：
前趋后继关系： [math]\displaystyle{ R_1 = \{\langle a_i,a_i+1\rangle\mid i=1,2,\dots,n,n\geq 0\} }[/math]
线性表的操作可以形式化为以下纯函数：
- 整体
Create[math]\displaystyle{ \varnothing\to \{\mathrm{nil}\} }[/math] ：获得一张空表。Length/Size[math]\displaystyle{ L \to \mathbb{N}; D \mapsto n }[/math] ：获得表的长度/大小。也定义empty[math]\displaystyle{ L\to \mathbb{B} }[/math] 获得表是否为空。Clear[math]\displaystyle{ \varnothing\to \{\mathrm{nil}\} }[/math] ：获得一张空表。
- 顺序相关
Pred[math]\displaystyle{ L\times P \to P }[/math] ：获得指定元素（位置）的前趋元素。Succ[math]\displaystyle{ L\times P \to P }[/math] ：获得指定元素（位置）的后继元素。
- 指定位置
GetElement[math]\displaystyle{ L \times \{i\in\mathbb{N}^*|i\leq n\} \to L; (D, i) \mapsto a_i }[/math] ：获得指定位置的元素。InsertElement[math]\displaystyle{ L \times \{i\in\mathbb{N}^*|i\leq n+1\} \to L }[/math] ：在指定位置插入元素。通常不是纯函数，直接修改参数内部状态。RemoveElement[math]\displaystyle{ L \times \{i\in\mathbb{N}^*|i\leq n\} \to L }[/math] ：在指定位置插入元素。通常不是纯函数，直接修改参数内部状态。
- 头尾位置
Front[math]\displaystyle{ L^* \to P; D \mapsto a_1 }[/math] ：获得首元素，相当于 [math]\displaystyle{ \mathrm{GetElement}(l, 0) }[/math] 。Rear[math]\displaystyle{ L^* \to P; D \mapsto a_n }[/math] ：获得尾元素，相当于 [math]\displaystyle{ \mathrm{GetElement}(l, \mathrm{Size}(l)) }[/math] 。InsertFront[math]\displaystyle{ L \times \{i\in\mathbb{N}^*|i\leq n+1\} \to L }[/math] ：在首元素前插入元素，相当于 [math]\displaystyle{ \mathrm{InsertElement}(l, 1) }[/math] 。通常不是纯函数，直接修改参数内部状态。RemoveFront[math]\displaystyle{ L \times \{i\in\mathbb{N}^*|i\leq n\} \to L }[/math] ：在指定位置插入元素，相当于 [math]\displaystyle{ \mathrm{RemoveElement}(l, 1) }[/math] 。通常不是纯函数，直接修改参数内部状态。InsertRear[math]\displaystyle{ L \times \{i\in\mathbb{N}^*|i\leq n+1\} \to L }[/math] ：在指定位置插入元素，相当于 [math]\displaystyle{ \mathrm{InsertElement}(l, \mathrm{Size}(l)+1) }[/math] 。通常不是纯函数，直接修改参数内部状态。RemoveRear[math]\displaystyle{ L \times \{i\in\mathbb{N}^*|i\leq n\} \to L }[/math] ：在指定位置插入元素，相当于 [math]\displaystyle{ \mathrm{RemoveElement}(l, \mathrm{Size}(l)) }[/math] 。通常不是纯函数，直接修改参数内部状态。
- 单子操作
ForEach[math]\displaystyle{ L \times P }[/math] ：在每个元素上执行指定函数。通常不是纯函数。Find[math]\displaystyle{ L \times \mathbb{B}^P \to P }[/math] ：寻找第一个满足谓词的元素。Map[math]\displaystyle{ L \times R^P \to L_R; (\{(a_i,i)\},f) \mapsto \{(f(a_i,i),i)\} }[/math] ：对每个元素进行映射，并得到其像按原顺序构成的集合。
线性表作为最常见的逻辑结构，很多算法都会依赖于线性表，如果都写作其 ADT 的一部分会因为操作太多难以描述。 这些算法往往可以描述为对容器中关联位置的运算和读取，可以通过迭代器模式解耦，不继续列在这里。
纯函数刻画
函数式编程中，以上线性表操作可以被刻画为以下四种纯函数的组合：
- [math]\displaystyle{ \mathrm{nil}: \varnothing\to L }[/math] ：从空元组到空列表。
- [math]\displaystyle{ \mathrm{cons}: E\times L \to L }[/math] ：从首元素和后续列表拼接。
- [math]\displaystyle{ \mathrm{first}: L \to E }[/math] ：从列表得到首元素。
- [math]\displaystyle{ \mathrm{rest}: L \to L }[/math] ：从列表得到首元素后的列表。
且满足公理 [math]\displaystyle{ \mathrm{first}(\mathrm{cons}(e,l)) = e }[/math] 和 [math]\displaystyle{ \mathrm{rest}(\mathrm{cons}(e,l)) = l }[/math]。
具体数据结构
线性表是一种逻辑结构，根据存储结构的不同可以存在多种具体的数据结构。
只使用链式存储结构的线性表，称为链表，如单向链表和双向链表。
此外，也存在混合使用两种存储结构的数据结构：内存整体上为链式，但是每个结点中是顺序的结构称为块状链表，内存整体上连续，但是每个结点中用链式连接的结构称为自由链表。跳表也可以视为一种增加了额外结构的线性表。