Lecture 3：线性表的定义与基本操作

3.1 线性表的基本概念

3.1.1 线性表的特点

核心特点

• 线性表是最基本、最常见的一种线性结构。
• 它强调的是元素之间存在“一对一”的前后关系。

五个特点

• 1. 表中元素个数有限；
• 2. 表中元素具有逻辑上的顺序性，元素之间有先后次序；
• 3. 表中元素都是数据元素，每个元素都是单个元素；
• 4. 表中元素的数据类型相同；在教材的定长元素、顺序存储模型中，每个存储单元占用相同大小的空间；
• 5. 表中元素具有抽象性，只讨论元素之间的逻辑关系，不讨论元素具体表示什么内容。

解释

• “有限”说明线性表不是无限序列。
• “有序”说明每个元素在表中有确定位置。
• “类型相同”规定了线性表的元素类型；顺序表要按地址公式快速定位，还需元素在存储中等长且连续。对于变长编码或指针所指向的变长对象，不能只凭“同类型”推出实际数据都占相同字节数。
• “抽象性”说明线性表只关心结构关系，不关心元素是学生、数字还是字符。

3.1.2 线性表的定义

定义：#线性表

描述： 线性表是具有相同数据类型的 $n(n\ge 0)$ 个数据元素的有限序列，其中 $n$ 为表长。当 $n=0$ 时，线性表是空表。

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

解释

• $L$：线性表的名称。
• $a_i$：线性表中的第 $i$ 个元素。
• $n$：线性表的长度，也叫表长。
• 当 $n=0$ 时： $$ L=() $$ 此时称为空表。

表头和表尾

• $a_1$ 是表头元素。
• $a_n$ 是表尾元素。

前驱和后继

• 除第一个元素外，每个元素有且仅有一个直接前驱。
• 除最后一个元素外，每个元素有且仅有一个直接后继。

注意

• 线性表中的位序从 1 开始。
• 数组下标通常从 0 开始。
• 因此第 $i$ 个元素在线性表中的位序是 $i$，但如果用数组实现，它常常存放在下标 $i-1$ 的位置。

例子

• 线性表： $$ L=(10,20,30,40) $$
• 表长： $$ n=4 $$
• 第 1 个元素是 $10$。
• 第 3 个元素是 $30$。
• 第 3 个元素若用数组保存，通常对应数组下标 $2$。

3.2 线性表的基本操作

核心

• 线性表的基本操作是后续顺序表、链表代码题的基础。
• 考试中经常通过这些操作来考查：
  • 参数含义；
  • 位序合法性；
  • 插入删除边界；
  • 时间复杂度。

3.2.1 初始化

定义：#InitList

描述： InitList(&L) 用于把线性表 $L$ 初始化为空表，并建立实现所需的初始状态；是否分配内存取决于具体存储实现。

解释

• &L 表示需要修改线性表本身。
• 初始化后，线性表通常处于空表状态。
• 静态顺序表通常只需把表长设为 0；动态顺序表或带头结点链表才需要在初始化时申请相应空间。

3.2.2 销毁

定义：#DestroyList

描述： DestroyList(&L) 用于销毁线性表，并释放线性表 $L$ 所占用的内存空间。

解释

• 销毁操作不仅是清空元素，还要释放占用空间。
• 对动态分配的线性表尤其重要。

3.2.3 插入

定义：#ListInsert

描述： ListInsert(&L, i, e) 表示在表 $L$ 中第 $i$ 个位置插入指定元素 $e$。

解释

• 插入位置 $i$ 是线性表位序，不是数组下标。
• 从逻辑上看，插入后原第 $i$ 个元素及其后续元素的位序依次加 1；顺序表实现通常要将这些元素在数组中后移，链表在定位插入位置后主要调整链接，不必整体搬移后续元素。
• 合法插入位置通常为： $$ 1\le i\le L.length+1 $$
• 当 $i=L.length+1$ 时，表示在表尾插入。

3.2.4 删除

定义：#ListDelete

描述： ListDelete(&L, i, &e) 表示删除表 $L$ 中第 $i$ 个位置的元素，并用 $e$ 返回被删除元素的值。

解释

• &e 的作用是把删除的元素“带回来”。
• 删除位置 $i$ 必须是已有元素的位置。
• 合法删除位置通常为： $$ 1\le i\le L.length $$

3.2.5 按值查找

定义：#LocateElem

描述： LocateElem(L, e) 表示在表 $L$ 中查找具有给定关键字值 $e$ 的元素。

解释

• 这是按“元素值”查找。
• 查找结果通常是元素位序或元素位置。
• 如果表中不存在该元素，则返回失败标志。

3.2.6 按位查找

定义：#GetElem

描述： GetElem(L, i) 表示获取表 $L$ 中第 $i$ 个位置的元素值。

解释

• 这是按“位序”查找。
• 位序 $i$ 从 1 开始。
• 若顺序表支持随机访问，按位查找可以很快。

3.3 线性表的其他常用操作

常用操作表

解释

• Length(L) 关注表中有多少个元素。
• PrintList(L) 关注按逻辑顺序输出所有元素。
• Empty(L) 关注线性表当前是否为空。

3.4 操作分类总结

按功能分类

按是否修改线性表分类

• 会修改线性表：
  • InitList(&L)；
  • DestroyList(&L)；
  • ListInsert(&L,i,e)；
  • ListDelete(&L,i,&e)。
• 不一定修改线性表：
  • LocateElem(L,e)；
  • GetElem(L,i)；
  • Length(L)；
  • PrintList(L)；
  • Empty(L)。

相关知识

• 科目导航：数据结构导航
• 阅读顺序：上一篇：算法和算法评价 · 下一篇：线性表的顺序实现
• 关联专题：顺序表代码

3.5 本节复盘

必须掌握

• 线性表的定义： $$ L=(a_1,a_2,\cdots,a_i,a_{i+1},\cdots,a_n) $$
• 表长 $n$ 可以为 0。
• $n=0$ 时，线性表是空表。
• 第一个元素是表头元素，最后一个元素是表尾元素。
• 除第一个元素外，每个元素有且仅有一个直接前驱。
• 除最后一个元素外，每个元素有且仅有一个直接后继。

易错点

• 位序从 1 开始，数组下标从 0 开始。
• 插入位置可以是 $L.length+1$，表示表尾插入。
• 删除位置不能是 $L.length+1$，因为这个位置没有已有元素。
• ListDelete(&L,i,&e) 中的 e 用来返回被删除元素。

做题抓手

• 看到 i，先判断它是位序还是数组下标。
• 看到插入，检查：
  • $1\le i\le L.length+1$；
  • 表是否已满。
• 看到删除，检查：
  • $1\le i\le L.length$；
  • 是否需要返回删除值。