|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
第004讲:线性表(顺序存储)
知识点回顾:
0. 本节视频
1. 线性表的概念
线性表(List),是最常用且最简单的一种数据结构,它是具有零个或多个数据元素的有限序列。
如果用数学的语言来定义,通常我们会将线性表记为 $L = (a_{1}, a_{2}, \dots, a_{i-1}, a_{i}, a_{i+1}, \dots, a_{n})$ 这么一个式子。
其中,a_{1} 是唯一的第一个数据元素,也称为表头元素,a_{n} 则是唯一的最后一个元素,又称为表尾元素。
除第一个元素之外的每一个元素,有且仅有一个直接前驱(比如 a_{i} 的直接前驱是 a_{i-1})。
同样的道理,除最后一个元素之外的每一个元素,也会有一个直接后继(正如 a_{i} 的直接后继是 a_{i+1})。
2. 有关线性表概念的考点
- 有限性:线性表是零个或多个数据元素的有限序列。也就是说,一个线性表中的元素数量是有限的。
- 有序性:线性表中的元素是有序的,每个元素都有一个唯一的前驱和后继(除了第一个元素没有前驱,最后一个元素没有后继)
- 线性结构:也就是说,线性表的数据元素之间必须是呈现一对一的关系。
3. 抽象数据类型
抽象数据类型(Abstract Data Type,简称 ADT)其实是一种对数据和操作的封装,它只描述了数据和操作的特性,而不涉及具体的实现方法。
简单地说,ADT 就像是一件家用电器的使用手册,它会告诉你这个东西有哪些功能,以及如何操作,但它不需要告诉你这些功能背后到底是如何实现的。
线性表的 ADT:
- ADT List {
- 数据对象:$D = { a_{i} | a_{i} \in ElemSet, i = 1, 2, \dots, n, n ≥ 0}$
-
- 数据关系:$R1 = { <a_{i-1}, a_{i} > | a_{i-1}, a_{i} \in D, i = 2, \dots, n}$
-
- 基本操作:
- InitList(*L)
- 操作结果:构造一个空的线性表 L
- ListEmpty(L)
- 操作结果:判断线性表是否为空
- ListLength(L)
- 操作结果:返回线性表 L 中数据元素的个数
- GetElem(L, i, *e)
- 操作结果:获取 L 中第 i 个数据元素的值,并通过 e 返回
- LocateElem(L, e)
- 操作结果:在线性表 L 中查找数据元素 e 的位置
- ListInsert(*L, i, e)
- 操作结果:在线性表 L 中第 i 个位置上插入新的数据元素 e
- ListDelete(*L, i, *e)
- 操作结果:删除线性表 L 中第 i 个数据元素,并用 e 返回其值
- ClearList(*L)
- 操作结果:清空线性表 L
- DestroyList(*L)
- 操作结果:销毁线性表 L
- } ADT List
复制代码
数据对象:$D = { a_{i} | a_{i} \in ElemSet, i = 1, 2, \dots, n, n ≥ 0}$
定义数据对象 D 为一个元素集合,其中每个元素 $a_{i}$ 都属于一个叫 ElemSet 的元素集,通常这个元素集会被假定为一个通用集合。
在具体实现时,ElemSet 可以被指定为特定的类型,比如整数、浮点数、字符串、或者更复杂的结构等。
但在 ADT 的定义层面,ElemSet 是抽象的,它可以代表任何可能的元素集合。
然后,i 就是元素的位置,从 1 开始,表示第一个元素,n 是线性表的长度。
数据关系:$R1 = { <a_{i-1}, a_{i} > | a_{i-1}, a_{i} \in D, i = 2, \dots, n}$
定义一个数据关系 R1,它表示线性表中相邻元素之间的顺序关系。
$<a_{i-1}, a_{i}>$ 表示一个有序对(cordered pair),强调了元素之间的顺序,也就是 $a_{i-1}$,必须是在 $a_{i}$ 之前的。
基本操作
基本操作的具体实现,要取决于采用哪种存储结构,存储结构不同,算法的实现肯定也大相径庭。
那么线性表有两种不同的存储方式:顺序存储(也就是我们 C 语言中的数组),和链式存储(包括单链表、双链表、循环链表这些)。
4. 顺序存储
对于顺序存储结构来讲,假设线性表的每个数据元素需要占用 s 个存储单元,那么线性表中第 i+1 个数据元素的存储位置,和第 i 个数据元素的存储位置将满足以下关系:
$LOC(a_{i+1}) = LOC(a_{i}) + s$
因此,线性表的第 i 个数据元素 $a_{i}$ 的存储位置为:
$LOC(a_{i}) = LOC(a_{1}) + (i-1) * s$
不难看出,顺序存储结构可以通过直接寻址访问任何元素,这就意味着访问第 i 个元素的时间复杂度是 O(1),即常数时间。
5. 顺序存储的基本操作
定义部分:
- #define MAX_SIZE 100 // 定义线性表的最大长度
- typedef int ElemType; // 定义元素类型
- // 定义顺序线性表的结构
- typedef struct {
- ElemType data[MAX_SIZE]; // 用数组存储
- int length; // 线性表当前长度
- } SqList;
复制代码
初始化线性表:
- // 初始化线性表
- void InitList(SqList *L) {
- L->length = 0;
- }
复制代码
判断线性表是否为空:
- // 判断线性表是否为空
- bool ListEmpty(SqList L) {
- return L.length == 0;
- }
复制代码
获取线性表的长度:
- // 返回线性表的长度
- int ListLength(SqList L) {
- return L.length;
- }
复制代码
获取线性表中第 i 个数据元素的值:
- // 获取线性表中第 i 个数据元素的值
- bool GetElem(SqList L, int i, ElemType *e) {
- if (L.length == 0 || i < 1 || i > L.length)
- return false;
-
- *e = L.data[i - 1];
- return true;
- }
复制代码
在线性表 L 中查找数据元素 e 的位置:
- // 在线性表 L 中查找数据元素 e 的位置
- int LocateElem(SqList L, ElemType e) {
- for (int i = 0; i < L.length; i++) {
- if (L.data[i] == e)
- return i + 1;
- }
- return 0;
- }
复制代码
在线性表 L 的第 i 个位置上,插入数据元素 e:
- // 在线性表 L 中第 i 个位置上插入新的数据元素 e
- bool ListInsert(SqList *L, int i, ElemType e) {
- if (i < 1 || i > L->length + 1 || L->length == MAX_SIZE)
- return false;
- for (int j = L->length; j >= i; j--) {
- L->data[j] = L->data[j - 1];
- }
- L->data[i - 1] = e;
- L->length++;
- return true;
- }
复制代码
删除线性表中的元素:
- // 删除线性表 L 中第 i 个数据元素,并用 e 返回其值
- bool ListDelete(SqList *L, int i, ElemType *e) {
- if (L->length == 0 || i < 1 || i > L->length)
- return false;
- *e = L->data[i - 1];
- for (int j = i; j < L->length; j++) {
- L->data[j - 1] = L->data[j];
- }
- L->length--;
- return true;
- }
复制代码
清空线性表:
- // 清空线性表 L
- void ClearList(SqList *L) {
- L->length = 0;
- }
复制代码
销毁线性表:
- // 销毁线性表 L
- void DestroyList(SqList *L) {
- // 由于这里使用的是静态数组,实际上并不需要进行销毁操作
- // 如果使用动态数组,则需要释放内存
- // free(L->data);
- L->length = 0;
- }
复制代码
6. 顺序存储相关操作的动画演示及源代码
很重要,建议保存 -> https://fishc.com.cn/thread-239016-1-1.html
7. 思维导图
|
|