Jiayu Lab
← 返回学习笔记

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

408 学习笔记：Lecture 3：线性表的定义与基本操作。保留原有知识内容、公式与图示；有对应原件时提供查看和下载入口。

408 计算机记录日期约 7 分钟阅读
408数据结构
查看原始 PDF 下载原件
本页目录

3.1 线性表的基本概念

3.1.1 线性表的特点

核心特点

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

五个特点

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

解释

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

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) 求表长 返回线性表 $L$ 中数据元素的个数
PrintList(L) 输出操作 按前后顺序输出线性表 $L$ 的所有元素值
Empty(L) 判空操作 若 $L$ 为空表，则返回 true，否则返回 false

解释

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

3.4 操作分类总结

按功能分类

类型 操作 作用
创建/销毁 InitList、DestroyList 管理线性表生命周期
增删 ListInsert、ListDelete 改变线性表内容和长度
查找 LocateElem、GetElem 获取元素位置或元素值
辅助 Length、PrintList、Empty 获取状态或输出内容

按是否修改线性表分类

  • 会修改线性表：
    • 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$；
    • 是否需要返回删除值。