线性表（顺序表，单链表，双链表，循环链表，静态链表）

1.线性表的定义

线性表是具有相同数据类型的n (n>=0）个数据元素的有限序列，其中n为表长，当n = 0时线性表是一个空表。
若用L命名线性表，则其一般表示为 $L= (a1, a2,... , a_i, a_{i+1}, ... , an)$

1.几个重要的概念

$a_i$ 是线性表中的“第i个”元素线性表中的位序
注意：位序从1开始，数组下标从0开始。
$a_1$ 是表头元素;
$a_n$ 是表尾元素。
除第一个元素外，每个元素有且仅有一个直接前驱;
除最后一个元素外，每个元素有且仅有一个直接后继.

2.逻辑结构

在这里插入图片描述

2.线性表的基本操作

“&”符号的作用：对参数的修改结果带回主函数。

①InitList(&L)：初始化表。构造一个空的线性表L，分配内存空间。
②DestroyList(&L)：销毁操作。销毁线性表，并释放线性表L所占用的内存空间。
③ListInsert(&L,i,e)：插入操作。在表L中的第i个位置上插入指定元素e.
④ListDelete(&L,i,&e)：删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。
⑤LocateElem(L,e)：按值查找操作。在表L中查找具有给定关键字值的元素。
⑥GetElem(L,i)：按位查找操作。获取表L中第i个位置的元素的值。
⑦Length(L)：求表长。返回线性表L的长度，即L中数据元素的个数。
⑧PrintList(L)：输出操作。按前后顺序输出线性表L的所有元素值。
⑨Empty(L)：判空操作。若L为空表，则返回true，否则返回false。

3.顺序表（线性表的顺序存储）

顺序表：用顺序存储的方式实现线性表。
顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。
顺序表的实现方式：静态分配和动态分配。

1.静态分配

存储空间是静态的。
使用“静态数组”实现，大小一旦确定就无法改变。

在这里插入图片描述

2.动态分配

C语言中提供malloc和free函数来动态申请和释放内存空间。
使用动态数组实现。

3.顺序表的特点

①随机访问，即可以在（O1）时间内找到第i个元素。
②存储密度高，每个节点只存储数据元素。
③拓展容量不方便（即便采用动态分配的方式实现，拓展长度的时间复杂度也比较高)
④插入、删除操作不方便，需要移动大量元素。

4.顺序表的基本操作

1.插入

在这里插入图片描述

①最好情况:新元素插入到表尾，不需要移动元素。
$i = n + 1$ ，循环0次;最好时间复杂度=O(1)
②最坏情况:新元素插入到表头，需要将原有的n个元素全都向后移动。
$i = 1$ ，循环n次;最坏时间复杂度= O(n);
③平均情况:假设新元素插入到任何一个位置的概率相同，
即 $length+1的概率都是p=\frac{1}{n+1}$
平均循环次数= $\frac{n(n+1)}{2}\frac{1}{n+1}=\frac{n}{2}$ ，平均时间复杂度= O(n)

2.删除

在这里插入图片描述

①最好情况：删除表尾元素，不需要移动其他元素。
i = n，循环0次;最好时间复杂度=O(1)
②最坏情况：删除表头元素，需要将后续的n-1个元素全都向前移动。
i = 1，循环n-1 次;最坏时间复杂度= O(n);
③平均情况：假设删除任何一个元素的概率相同，即 $i = 1, 2, 3, ..., l e n g t h$ 的概率都是 $=\frac{1}{n}$
平均循环次数 = $\frac{n(n-1)}{2}\frac{1}{n}=\frac{n-1}{2}$ ，平均时间复杂度= O(n)

3.查找

1.按位查找

GetElem(L,i)：按位查找操作。获取表L中第i个位置的元素的值。
由于顺序表的各个数据元素在内存中连续存放，因此可以根据起始地址和数据元素大小立即找到第i个元素：“随机存取”特性。
时间复杂度为O（1）

2.按值查找

LocateElem(L,e)：按值查找操作。在表L中查找具有给定关键字值的元素。
①最好情况:目标元素在表头，循环1次;最好时间复杂度=O(1)
②最坏情况:目标元素在表尾，循环n 次;最坏时间复杂度= O(n);
③平均情况:假设目标元素出现在任何一个位置的概率相同，都是 $\frac{1}{n}$ ，平均循环次数= $\frac{n(n+1)}{2}\frac{1}{n}=\frac{n+1}{2}$
平均时间复杂度= O(n)