linear_list

线性表

考纲内容

1. 线性表的基本概念
2. 线性表的实现： 顺序存储、链式存储
3. 线性表的应用

注意

$\qquad$重点关注算法实现的时间复杂度

2.1 线性表的定义与基本操作

2.1.1 线性表的定义

$\qquad$定义： 线性表是具有相同数据类型的n个数据元素的有限序列（$n>=0$）, 其中n为表长，当n=0时，称为空表。复杂线性表中，数据元素可由多个数据项构成，此时数据元素成为记录，含有大量记录的线性表成为文件。

$ L = (a_1, a_2, \cdots, a_i, \cdots, a_n)$

$\qquad$$a_1$是唯一的表头元素， $a_n$是唯一的表尾元素。除第一个元素外，每个元素有且仅有一个直接前驱，除最后一个元素外，每个元素有且仅有一个直接后继。故线性表特征如下：

• 元素个数有限
• 元素具有逻辑上的独立性
• 元素都是数据元素
• 数据类型相同 -> 每个元素占用相同的存储空间
• 元素具有抽象性 -> 只考虑元素的逻辑关系，不考虑元素的具体内容

2.1.2 线性表的基本操作

InitList(&L) // 初始化一个空的线性表
Length(L) // 求线性表的长度
LocateElem(L, e) // 按值查找，返回元素e在线性表中的位置
GetElem(L, i) // 按位查找，返回第i个元素
ListInsert(&L, i, e) // 插入，在第i个位置插入元素e
ListDelete(&L, i, &e) // 删除，删除第i个位置的元素，并用e返回其值
PrintList(L) // 输出线性表
Empty(L) // 判断线性表是否为空
DestroyList(&L) // 销毁线性表

2.1.3 注意

$\qquad$线性表的位序从1开始，到n结束，而数组从0开始，n-1结束（超出范围则出现数组越界）
$\qquad$线性表的长度可以根据需要动态变化（怎么变看实现），而数组的长度是固定的。

2.2 线性表的顺序表示

2.2.1 顺序表定义

$\qquad$线性表的顺序存储又成顺序表。线性表的顺序存储又称顺序表。它是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。顺序表的特点是表中元素的逻辑顺序与其物理顺序相同。顺序表的存储结构如下：


$\qquad$顺序表中的任意一个数据元素都可以随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。通常用高级程序设计语言中的数组来描述线性表的顺序存储结构。
$\qquad$顺序表最主要的特点是随机访问,即通过首地址和元素序号可在时间O(1)内找到指定的元素。
$\qquad$顺序表的存储密度高，每个结点只存储数据元素。
$\qquad$顺序表逻辑上相邻的元素物理上也相邻，所以插入和删除操作需要移动大量元素

2.2.2 顺序表基本操作

1. 插入操作
   $\qquad$在顺序表的第i (1<=i<=L.length+l)个位置插入新元素e。若i的输入不合法，则返回false,表示插入失败；否则，将第i个元素及其后的所有元素依次往后移动一个位置，腾出一个空位置插入新元素e,顺序表长度增加1,插入成功，返回true。

• $\qquad$最好情况：在表尾插入(即 i = n+1),元素后移语句将不执行，时间复杂度为0(1)。
• $\qquad$最坏情况：在表头插入(即 i = 1),元素后移语句将执行n次，时间复杂度为0(n)。
• $\qquad$平均情况：假设$p_i$ ($p_i$ = $\frac{i}{n + i})$是在第i个位置上插入一个结点的概率，则在长度为n的线性表中插入一个结点时，所需移动结点的平均次数为 $\frac{n}{2}$
• $\qquad$故，插入算法的平均时间复杂度是O(n)

2. 删除操作
   $\qquad$删除顺序表中第i (1<=i<=L.length)个位置的元素，用引用变量e返回。若i的输入不合法，则返回false；否则，将被删元素赋给引用变量e,并将第i+1个元素及其后的所有元素依次往前移动一个位置，返回true。

• $\qquad$最好情况：删除表尾元素(即 i = n),无须移动元素，时间复杂度为O(1)
• $\qquad$最坏情况：删除表头元素(即i=1),需移动除表头元素外的所有元素，时间复杂度为O(n)
• $\qquad$平均情况：假设$p_i$ ($p_i$ = $\frac{i}{n})$是在第i个位置上删除一个结点的概率，则在长度为n的线性表中删除一个结点时，所需移动结点的平均次数为 $\frac{n-1}{2}$
• $\qquad$故，删除算法的平均时间复杂度是O(n)

3. 按值查找
   $\qquad$在顺序表L中查找第一个元素值等于e的元素，并返回其位序。

• 最好情况：查找的元素就在表头，仅需比较一次，时间复杂度为0(1)。
• 最坏情况：查找的元素在表尾(或不存在)时，需要比较n次，时间复杂度为。O(n)。
• 平均情况：假设$p_i$ ($p_i$ = $\frac{i}{n}$)是查找的元素在第i (1<=i<=L. length)个位置上的概率,则在长度为n的线性表中查找值为e的元素所需比较的平均次数为$\frac{n+1}{2}$
• $\qquad$故，查询算法的平均时间复杂度是O(n)

2.2.3 注意

$\qquad$顺序表的存储密度高，每个结点只存储数据元素。
$\qquad$顺序表需要连续的存储空间

2.2.4 易错点

$\qquad$ 为什么顺序表元素交换比链表高 ->链表顺序查询，并且要查询前序结点（如果可能换值就没有这个问题）

2.2.5 常见算法问题

1. 逆置顺序表O(n)
2. 元素交换
3. 元素查找 - 二分O(nlogn)/顺序O(n)/哈希(空间换时间)
4. 出现倒序/交换批量元素位置的，优先考虑顺序表逆置
5. 说白了无非增删改查

2.3 线性表的链式表示

2.3.1 单链表定义

$\qquad$线性表的链式存储又称单链表，它是指通过一组任意的存储单元来存储线性表中的数据元素(存储单元可以不连续)。对每个链表结点，除存放元素自身的信息外，还需要存放一个指向其后继的指针。分别称数据域和指针域。


$\qquad$单链表附加指针域，浪费存储空间，故存储密度较低。同时是非随机存取的存储结构，只能顺序存取，不能随机存取。
$\qquad$通常用头指针来标识一个单链表，如单链表Z,头指针为NULL时表示一个空表。此外， 为了操作上的方便，在单链表第一个结点之前附加一个结点，称为头结点。头结点的数据域可以不设任何信息，也可以记录表长等信息。头结点的指针域指向线性表的第一个元素结点。
$\qquad$单链表的第一个结点称为头结点，最后一个结点称为尾结点。尾结点的指针域指向NULL。
$\qquad$引入头结点的优点:
$\qquad$ 1. 使得所有结点的处理变得一致 ->方便运算实现
$\qquad$ 2. 空表和非空表的处理的到统一

2.3.2 单链表基本操作

2.3.3 双向链表

2.3.4 循环链表

2.3.5 静态链表

2.3.6 与顺序表的比较

2.3.7 注意

2.3.8 易错点

2.3.9 常见算法问题

---