基本概念

基本概念

线性表

线性表(Linear List)是具有相同数据类型的 n 个数据元素的有限序列,记作 L=(a1,a2,…,an)L=(a_1, a_2, \ldots, a_n)。

  • 特点:有唯一的第一个元素 a1a_1 和最后一个元素 ana_n,除首尾外每个元素有且仅有一个前驱和一个后继
  • 元素个数 n 称为线性表的长度,n=0 时称为空表
线性表

点击“执行一步”观察算法状态变化。

存储结构对比

存储方式地址连续支持随机访问插入/删除效率空间利用率
顺序表是是低低
链表否否高高
  • 顺序表:用一组地址连续的存储单元依次存放线性表元素,逻辑相邻即物理相邻。
  • 链表:每个结点包含数据域和指针域,通过指针连接,逻辑相邻不一定物理相邻。

习题

习题 1

线性表的特点是( )

A. 元素个数固定不变 B. 除首尾外每个元素有且仅有一个前驱和一个后继 C. 存储地址必须连续 D. 所有元素类型可以不同

线性表前驱与后继逻辑结构

解题思路:

本题考查线性表的逻辑特征。判断时要把“线性表这种抽象逻辑结构”与“顺序表这种具体存储结构”区分开,逐一比对四个选项对元素个数、前驱后继、存储连续性和元素类型的描述。

详细步骤:

  1. 线性表是 nn(n≥0n \ge 0)个相同类型数据元素组成的有限序列,其核心特征是除首尾外每个元素有且仅有一个直接前驱和一个直接后继。
  2. 选项 A“元素个数固定不变”错误,线性表长度可变;选项 C“存储地址必须连续”是顺序表的特征,不是线性表的必要特征。
  3. 选项 D“所有元素类型可以不同”错误,线性表要求所有元素类型相同。
  4. 只有选项 B 与线性表的定义完全吻合。

最终答案:

B。

习题 2

简述线性表的定义和主要特点。

线性表有序序列逻辑结构

解题思路:

本题考查线性表的定义。答题时按“元素个数与类型—唯一首尾—前驱后继关系”三个层次把定义拆开,再点明这种一对一关系正是“线性”二字的由来。

详细步骤:

  1. 从元素个数与类型看:线性表是由 nn(n≥0n \ge 0)个相同类型数据元素组成的有限序列。
  2. 从首尾看:表中存在唯一的首元素与尾元素;n=0n = 0 时为空表。
  3. 从关系看:除首尾外每个元素有且仅有一个前驱和一个后继,元素之间构成一对一的线性关系。

最终答案:

线性表是 n(n≥0)个相同类型数据元素的有序序列,有唯一首尾,除首尾外每个元素有且仅有一个前驱和一个后继,元素间是一对一的线性关系。

习题 3

顺序表和链表各自的优缺点是什么?

顺序表链表存储结构时间复杂度

解题思路:

本题考查顺序表与链表的优缺点对比。答题时按“随机访问能力—插入删除代价—空间利用方式”三条主线分别评述两种存储结构,再归纳出各自适用的场景。

详细步骤:

  1. 顺序表的优点:存储空间连续,支持随机访问,查找快(O(1)O(1)),存储密度高;缺点:插入或删除需移动大量元素(O(n)O(n)),且需预分配空间,空间利用率低。
  2. 链表的优点:插入或删除只需修改指针(定位后 O(1)O(1)),空间按需分配、利用率高;缺点:不支持随机访问,查找慢(O(n)O(n)),每个结点需额外存储指针,存储密度低。
  3. 对比结论:需要频繁按下标随机访问、且结构规模相对稳定时选顺序表;需要频繁在已知位置插入删除时选链表。

最终答案:

顺序表:优点——支持随机访问、查找快(O(1)O(1))、存储密度高;缺点——插入/删除需移动大量元素(O(n)O(n))、空间利用率低(需要预分配)。链表:优点——插入/删除快(O(1)O(1),定位后)、空间按需分配、利用率高;缺点——不支持随机访问、查找慢(O(n)O(n))、每个结点需额外存储指针、存储密度低。

发现内容有问题?

告诉我们哪里需要改进。