定义和基本操作

了解线性表的概念，不会直接考察。还是会考察 顺序表 和 链表 这两种具体实现方案。

线性表定义

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

除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继。空表的长度为 $0$。

特点：

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

顺序表和链表

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

顺序表中的元素存储地址是 连续的，而链表的结点地址通常是 非连续的，结点中除了数据元素外还保存相邻结点的链接信息。顺序表中数据之间的 逻辑次序 由物理相邻关系体现，链表则由指针显式表达逻辑次序。

存储区域说明：顺序存储或链式存储描述的是数据结构的布局，不直接决定对象一定在进程的栈区还是堆区。局部数组、静态数组、动态数组和动态申请的链表结点可能位于不同存储区域，取决于具体声明和分配方式。

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

基本操作

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

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

逻辑位置、物理下标与边界

教材中的第 (i) 个元素通常采用 逻辑位置从 1 开始 的记法，而 C/C++ 数组下标从 0 开始。若顺序表 data 存储第 (i) 个逻辑元素，则对应 data[i - 1]；代码中混淆这两个编号会造成典型的越界错误。

对长度为 (n) 的线性表，插入位置应满足 (1\le i\le n+1)，因为允许在尾后形成新末尾；删除、取值和修改位置则应满足 (1\le i\le n)。空表允许初始化、判空和在第 1 个位置插入，但不允许删除或取值。顺序表还要判断容量是否已满，链表还要判断结点申请或前驱定位是否成功。

这些条件既是程序的输入合法性检查，也是算法正确性的前提：主流程写得再正确，若没有定义空表、首位和末位的行为，就不能称为完整的线性表操作。