定义和基本操作

线性表定义

线性表（Linear List）是 L 数据结构 中的一种基本结构。它是 零个或多个数据元素的有限序列。通常，线性表 中的 数据元素 之间是 有序的，它们之间存在着 前驱和后继的关系。

$$L = (a_1, a_2, \cdots, a_i, a_{i+1}, \cdots, a_n)$$

特点：

• 个数有限
• 表中元素数据类型都相同，每个元素占有 相同大小的存储空间
• 仅讨论 元素间的逻辑关系，表中元素有 先后顺序

顺序表和链表

线性表分为顺序存储结构（又称 顺序表）和链式存储结构（又称为 链表）。

顺序表中的元素存储地址是 连续的（存储在栈中），而链表的元素存储地址是 非连续的（存储在堆中），元素节点中除了存储数据元素之外还存储相邻元素的地址信息。顺序表中数据之间的 逻辑关系 和 物理关系 是一致的，链表中数据元素的逻辑关系和物理关系并不一定一致。

上图中左边为顺序表，右边为链表。顺序表在内存中的地址是连续的，各个元素的下标之间是有规律可循的，通过一个已知下标的元素可以找到顺序表中任意一个其它元素。但是链式表中的元素在内存中的地址是不连续的，所以链式表中的每个元素除了要保存数据信息外，还要保存下一个元素的内存地址，以便形成线性关系。

操作

线性表中的操作包含以下类型，顺序表 和 链表 会各自使用不同的方案实现这些操作：

• 初始化 (InitList): 创建一个 空的线性表。
• 插入 (Insert): 在线性表的 指定位置 插入一个 新的元素。
• 删除 (Delete): 删除线性表中的 指定位置的元素。
• 查找 (LocateElem): 根据 给定的条件 查找线性表中的 元素。
• 获取元素 (GetElem): 获取线性表中 指定位置的元素。
• 设置元素 (SetElem): 修改线性表中 指定位置的元素 的 值。
• 长度 (Length): 返回线性表中的 元素数量。
• 判空 (IsEmpty): 判断线性表是否 为空。
• 清空 (ClearList): 清除线性表中的 所有元素。
• 遍历 (Traverse): 对线性表中的 每个元素 执行 某种操作。