线性表的定义

🎯 考点权重：[选择题高频/概念辨析] - [逻辑结构与物理结构的区别、位序与下标的对应]

核心概念

定义要点：

• 逻辑结构：具有相同数据类型的 $n$ ($n \ge 0$) 个数据元素的有限序列。
• 表长属性：$n$ 为表长，当 $n=0$ 时称为空表。

理解要点： 线性表是一种逻辑结构（抽象的排队关系），而顺序表和链表是其存储结构（物理上的实现方式）。核心特征是一对一的相邻关系：除第一个和最后一个元素外，每个元素有且仅有一个直接前驱和一个直接后继。

关键技术

实现原理： 线性表的定义在代码层面体现为结构体的设计。 确定元素类型 ElemType -> 确定存储方式（顺序/链式） -> 定义结构体 struct

代码实现： 408 考试中，线性表的定义通常涉及两种主要形式（此处展示最基础的定义）：

// 1. 顺序表定义（静态分配）
#define MaxSize 50          // 定义最大长度
typedef struct {
    int data[MaxSize];      // 存放元素的数组（假设元素为int）
    int length;             // 当前线性表的长度
} SqList;

// 2. 单链表结点定义
typedef struct LNode {
    int data;               // 数据域
    struct LNode *next;     // 指针域，指向后继结点
} LNode, *LinkList;         // LinkList 等价于 LNode*

技术要点：

• 类型一致性：线性表中所有元素的数据类型必须相同，这意味着每个元素占用相同大小的存储空间。
• 有限性：线性表必须由有限个元素组成，不能是无穷的。

考试重点

时间复杂度： 此处特指存取方式带来的复杂度差异（定义决定了操作上限）：

• 顺序存储：支持随机存取，按位查找时间复杂度为 $O(1)$。
• 链式存储：支持顺序存取，按位查找时间复杂度为 $O(n)$。

对比分析：

常见陷阱

❌ 错误理解：线性表就是顺序表。 ✅ 正确理解：线性表是逻辑概念，顺序表是线性表的一种物理实现（另一种是链表）。

❌ 错误理解：线性表中元素可以类型不同。 ✅ 正确理解：必须相同，否则无法通过统一的步长（sizeof）进行访问或管理。

❌ 代码陷阱：混淆位序（Rank）和下标（Index）。 ✅ 正确写法：

• 位序：第 $i$ 个元素，逻辑上指 $a_i$，范围 $1 \le i \le n$。
• 下标：代码访问 data[i-1]，范围 $0 \le index \le n-1$。
• 考试技巧：题目若未特殊说明，提到"第 i 个"通常指位序，写代码时记得 i-1。