线性表与顺序表

线性表是逻辑结构，顺序表和链表是它的两种存储结构。 教材在 2.1.1 的注意框里专门强调「两者属于不同层面的概念，不要混淆」。选择题考的是顺序表的几个平均移动次数和「随机存取」的含义；分值大头在算法设计题，教材【命题追踪】列了顺序表的应用 2010、2011、2018、2020 四道。

机制

2.1.1 线性表的定义

线性表是具有相同数据类型的 个数据元素的有限序列。 为表长， 时为空表。 是唯一的「第一个」元素，称为表头元素； 是唯一的「最后一个」元素，称为表尾元素。除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继。

线性表的五个特点：

1. 元素个数有限。
2. 元素具有逻辑上的顺序性，有先后次序。
3. 元素都是数据元素，每个元素都是单个元素。
4. 元素的数据类型都相同，即每个元素占有相同大小的存储空间。
5. 元素具有抽象性：只讨论元素间的逻辑关系，不考虑元素究竟表示什么内容。

2.1.2 基本操作

InitList、Length、LocateElem（按值查找）、GetElem（按位查找）、ListInsert、ListDelete、PrintList、Empty、DestroyList。基本操作的实现取决于采用哪种存储结构。& 表示 C++ 的引用调用。

2.2.1 顺序表的定义

顺序表用一组地址连续的存储单元依次存储线性表中的数据元素，逻辑顺序与物理顺序相同。第 个元素的地址为每个元素的地址与起始地址相差一个与位序成正比的常数，所以任一元素都可以随机存取。 称为元素 的位序。

口径差异：位序从 1 起，下标从 0 起

教材注意框原话：「线性表中元素的位序是从 1 开始的，而数组中元素的下标是从 0 开始的。」 所以 ListInsert 判断位置合法用 i>L.length+1（位序），移动元素的 for 循环却用 L.length（下标）。写算法题时，位序 的元素是 data[i-1]。

静态分配：数组大小事先固定，空间占满后再加入新数据就会溢出。动态分配：空间占满后另开辟一块更大的空间，把原表的元素全部拷贝过去。

边界辨析：

教材注意框：「动态分配并不是链式存储，它同样属于顺序存储结构，物理结构没有变化，依然是随机存取方式，只是分配的空间大小可以在运行时动态决定。」

优点	缺点
随机访问：通过首地址和元素序号在 时间内找到指定元素	插入和删除需要移动大量元素
存储密度高：每个结点只存储数据元素	需要一段连续的存储空间，不够灵活

2.2.2 插入、删除与按值查找

操作	合法范围	移动 / 比较次数	最好	最坏	平均
插入到第 个位置		后移 个	表尾	表头，移 个	，
删除第 个元素		前移 个	表尾	表头，移 个	，
按值查找	—	比较 次	表头	表尾或不存在，比较 次	，
按序号查找		—	—	—

两个平均值的推导（等概率）：

插入有 个位置，删除只有 个位置，所以两个平均值不相等。

边界

说法	判断	说明
「线性表是一种存储结构」	❌	是逻辑结构；顺序表、链表才是存储结构
「由 个实数组成的集合是线性表」	❌	集合的元素没有前驱后继关系。由 100 个字符组成的序列才是
「所有整数组成的序列是线性表」	❌	元素个数必须有限
「线性表中每个元素都有一个前驱和一个后继」	❌	表头无前驱，表尾无后继；只有一个元素时两者都没有
「线性表的顺序存储结构是顺序存取的存储结构」	❌	是随机存取的存储结构。存取方式指读写方式
「顺序表与一维数组的逻辑结构相同」	❌	一维数组还可以表示栈、队列、树等其他逻辑结构；且数组元素可以不连续存放
「随机存取指查找值为 的元素与 无关」	❌	指访问序号为 的元素的时间与 无关
「顺序表占用的空间与元素的存放顺序有关」	❌	只与表长、元素类型（及结构体各字段的类型）有关
「动态分配的顺序表是链式存储」	❌	仍是顺序存储，仍可随机存取
「插入的合法位置是 」	❌	是 ，第 个位置即表尾追加
「删除第 个元素要移动 个」	❌	移动 个； 是插入的
「插入、删除的平均移动次数都是 」	❌	插入 ，删除
「扩容时申请 个连续空间即可」	❌	要申请 个连续空间，再把原来 个元素复制过去
「顺序存储的有序表可以 按值查找」	❌	按值查找最少 （折半）； 的只有按序号获取

错题复盘：存取方式与存储结构（2.2.3 第 3 题）

线性表的顺序存储结构是一种随机存取的存储结构。答案解析说「本题易误选选项 B」（顺序存取的存储结构）。 名字里的「顺序」说的是存储：逻辑相邻则物理相邻；「随机」说的是存取：根据起始地址加元素序号，一步定位任意元素。两个词描述的不是同一件事。

错题复盘：2023 顺序存储的有序表， 的操作

四个选项：查找指定值、插入指定值、删除第 个、获取第 个。答案是获取第 个元素。 「有序」只把按值查找降到 ，插入和删除仍要移动元素，为 。只有按序号随机访问是 。

错题复盘：哪些操作在顺序表上更快（2.2.3 第 9 题）

三个操作：输出第 个元素、交换第 3 个与第 4 个元素、顺序输出全部元素。答案是前两个。 交换两个元素在顺序表上只需 3 次赋值；链表要先找到两个结点的前驱，再断链重接。顺序输出全部元素两者都是 ，没有差别。

考点

• 线性表是逻辑结构，五个特点里「有限」「相同类型」最常考。
• 位序从 1 起、下标从 0 起；插入的合法范围 。
• 平均移动次数：插入 ，删除 ；按值查找平均比较 。
• 随机存取 ≠ 顺序存取；动态分配仍是顺序存储。
• 算法设计题：顺序表是历年大题的主力，模板见代码附录。

链接

• 🏠 返回总览：数据结构第 1~4 章总览
• ⬅️ 上一章：1.2 算法和算法评价
• ➡️ 下一节：2.3.1~2.3.2 单链表
• 🔗 顺序表与链表的四维对比：速查：顺序表与链表
• 🔗 顺序表的统考大题：2010 循环左移 · 2011 两序列中位数 · 2013 主元素 · 2018 未出现的最小正整数 · 2020 三元组最小距离
• 🔗 顺序表的基础题：删除所有值为 x 的元素 · 有序表去重与合并 · 二分查找
• 📖 名词库：第 1~4 章名词库