当前位置：首页 > backend >正文

#数据结构----2.1线性表

backend 2025/9/5 16:40:38

在数据结构的学习中，线性表是最基础、最核心的结构之一 —— 它是后续栈、队列、链表等复杂结构的 “基石”。今天从 “是什么”（定义）到 “怎么用”（基本操作），彻底搞懂线性表的核心逻辑。

一、先明确：数据结构的三要素

在聊线性表之前，必须先记住数据结构的核心三要素，这是理解所有结构的前提：

逻辑结构：数据元素之间的 “关系”（比如线性表的 “前后顺序”）；

数据的运算：对数据元素能做的操作（比如增、删、改、查）；

存储结构（物理结构）：数据在内存中的 “存放方式”（比如数组、链表）。

关键提醒：存储结构不同，运算的实现方式也不同（比如数组实现和链表实现的 “插入” 操作，底层逻辑完全不一样），但今天我们先聚焦 “逻辑结构” 和 “运算”。

二、线性表的定义：到底什么是线性表？

线性表是具有相同数据类型的 n（n≥0）个数据元素的有限序列，用 L 命名时可表示为：

( L = (a_1, a_2, …, a_i, a_{i+1}, …, a_n) )

我们拆解这个定义里的关键信息，再结合例子理解会更透彻：

1. 定义的 3 个核心特性

同类型：所有元素的数据类型必须一致（比如全是整数、全是学生信息）；
有限性：元素个数 n 是有限的（不存在无限个元素的线性表）；
有序性：元素之间有明确的 “前后顺序”（a₁ 在 a₂ 前面，a₂ 在 a₃ 前面，不能乱序）。

2. 几个必须分清的术语

术语	含义
表长	线性表中元素的个数 n（n=0 时为空表）
表头元素	第一个元素 a₁
表尾元素	最后一个元素 aₙ
直接前驱	除 a₁ 外，每个元素 aᵢ 前面的那个元素（即 aᵢ₋₁）
直接后继	除 aₙ 外，每个元素 aᵢ 后面的那个元素（即 aᵢ₊₁）
位序	元素在表中的 “位置编号”（从 1 开始！和数组下标从 0 开始形成区别）

3. 举个例子：哪些是线性表？

例 1：所有整数按递增顺序排列（1,2,3,4,…100）—— 同类型（整数）、有限（100 个）、有序（递增），是线性表；
例 2：学生信息表（如下表）—— 同类型（学生信息）、有限（10 条记录）、有序（按学号排序），是线性表；

学号	姓名	专业
1120112100	张三	挖掘机
1120112101	李四	挖掘机
1120112102	王玉玉	数据挖掘

例 3：学习计划列表（学习《C 语言》→ 学习《数据结构》→ 学习《架构师》）—— 同类型（学习任务）、有限、有序，也是线性表。

三、线性表的基本操作：从 “创” 到 “销” 全流程

为什么要定义基本操作？核心原因有两个：

团队协作：封装好的操作能让其他人直接用，不用重复理解底层逻辑；
减少错误：常用操作写成函数，避免重复编码导致的 bug。

线性表的操作可以按 “生命周期” 和 “功能” 分为 4 类，我们逐个拆解（重点关注 “是否需要传引用 &”）：

1. 创销类：线性表的 “出生” 与 “消亡”

这两类操作是线性表的基础 —— 从 “无” 到 “有”，再从 “有” 到 “无”。

InitList (&L)：初始化表

功能：构造一个空的线性表 L，并为其分配内存空间。

为什么传 &L？因为要修改 L 本身（给它分配内存、设置表长为 0），需要把修改结果 “带回来”。

DestroyList (&L)：销毁表

功能：销毁线性表 L，并释放它占用的内存空间（避免内存泄漏）。

为什么传 &L？因为要释放 L 指向的内存，修改 L 的状态（比如让 L 指向 NULL），需要带回报错结果。

2. 增删类：改变线性表的 “长度”

这两类操作会修改线性表的元素个数，是高频操作。

ListInsert (&L, i, e)：插入元素

功能：在表 L 的第 i 个位置，插入新元素 e（插入后表长 +1）。

传参说明：&L（要修改表的结构）、i（插入位置，需满足 1≤i≤表长 + 1）、e（要插入的元素）。

ListDelete (&L, i, &e)：删除元素

功能：删除表 L 第 i 个位置的元素，并用 e 保存被删除元素的值（删除后表长 -1）。

为什么 &e？因为要把 “被删除的元素值” 带回来（比如用户需要知道删了什么）。

3. 改查类：定位元素（“改” 的前提是 “查”）

“查” 是 “改” 的基础 —— 要修改元素，必须先找到它的位置或值。

GetElem (L, i)：按位查找

功能：获取表 L 第 i 个位置的元素值（i 需满足 1≤i≤表长）。

为什么不传 &L？因为只是 “读取” 元素，没有修改表的结构或内容，不需要带回结果。

LocateElem (L, e)：按值查找

功能：在表 L 中查找 “值等于 e” 的元素，返回它的位序（若找不到返回 0 或 NULL）。

同理，仅读取，不传 &L。

4. 其他常用操作：辅助功能

这些操作是对线性表的 “补充查询”，高频且实用：

Length (L)：求表长：返回表 L 中元素的个数 n；
PrintList (L)：输出表：按前后顺序打印所有元素（比如打印学生信息表）；
Empty (L)：判空：若表 L 为空（n=0）返回 true，否则返回 false。

关键考点：什么时候传引用 “&”？

当对参数的修改结果需要 “带回来” 时，必须传引用（或指针）。

比如：

不传 & 的情况：调用 test(x) 后，x 的值在主函数中不变（修改只在 test 内部生效）；

#include<stdio.h>
void test(int x){x=1024;printf("test函数内部 x=%d\n",x);
}
int main(){int x=1;printf("调用test前 x=%d\n",x);test(x);printf("调用test后x=%d\n",x);
}

传 & 的情况：调用 test(&x) 后，x 的值在主函数中会被修改（修改结果带回来了）。

#include<stdio.h>
void test(int & x){x=1024;printf("test函数内部 x=%d\n",x);
}
int main(){int x=1;printf("调用test前 x=%d\n",x);test(x);printf("调用test后x=%d\n",x);
}