定义和基本操作
线性表可分为顺序表和链表,本节讨论线性表的定义和操作。
线性表定义
线性表(Linear List)是 L 数据结构 中的一种基本结构。它是 零个或多个数据元素的有限序列。通常,线性表 中的 数据元素 之间是 有序的,它们之间存在着 前驱和后继的关系。
$$L = (a_1, a_2, \cdots, a_i, a_{i+1}, \cdots, a_n)$$
特点:
- 个数有限
- 表中元素数据类型都相同,每个元素占有 相同大小的存储空间
- 仅讨论 元素间的逻辑关系,表中元素有 先后顺序
顺序表和链表
线性表分为顺序存储结构(又称 顺序表)和链式存储结构(又称为 链表)。
顺序表中的元素存储地址是 连续的(存储在栈中),而链表的元素存储地址是 非连续的(存储在堆中),元素节点中除了存储数据元素之外还存储相邻元素的地址信息。顺序表中数据之间的 逻辑关系 和 物理关系 是一致的,链表中数据元素的逻辑关系和物理关系并不一定一致。
上图中左边为顺序表,右边为链表。顺序表在内存中的地址是连续的,各个元素的下标之间是有规律可循的,通过一个已知下标的元素可以找到顺序表中任意一个其它元素。但是链式表中的元素在内存中的地址是不连续的,所以链式表中的每个元素除了要保存数据信息外,还要保存下一个元素的内存地址,以便形成线性关系。
操作
- 初始化 (
InitList
): 创建一个 空的线性表。 - 插入 (
Insert
): 在 线性表 的 指定位置 插入一个 新的元素。 - 删除 (
Delete
): 删除 线性表 中的 指定位置的元素。 - 查找 (
LocateElem
): 根据 给定的条件 查找 线性表 中的 元素。 - 获取元素 (
GetElem
): 获取 线性表 中 指定位置的元素。 - 设置元素 (
SetElem
): 修改 线性表 中 指定位置的元素 的 值。 - 长度 (
Length
): 返回 线性表 中的 元素数量。 - 判空 (
IsEmpty
): 判断 线性表 是否 为空。 - 清空 (
ClearList
): 清除 线性表 中的 所有元素。 - 遍历 (
Traverse
): 对 线性表 中的 每个元素 执行 某种操作。