# 线性表的定义和特点

# 定义

1. 线性表（Linear List）是具有相同特征的数据元素的一个有限序列
2. 由 n 个元素（节点）$a_1$，$a_2$，...$a_n$ 组成的有限序列
   1. 其中数据元素个数 n 定义为表的长度
   2. 当 n=0 时称为空表
   3. 将非空的线性表（n>0）记作：（$a_1$，$a_2$，...$a_n$）
   4. 这里的数据元素$a_i$ 只是一个抽象的符号，其具体含义在不同的情况下可以不同

# 特点

1. 同一线性表中的元素具有相同特征
2. 数据元素之间的关系是线性关系
3. 在非空的线性表中，有且仅有一个开始节点，它没有直接前驱，而仅有一个直接后继
4. 有且仅有一个终端节点，它没有直接后继，而仅有一个直接前驱
5. 其余的内部节点都有且只有一个直接前驱和一个直接后继

# 线性表的类型定义

# InitList(&L)（initiazation List）

1. 操作结果：构造一个空的线性表 L

# DestroyList(&L)

1. 初始条件：线性表 L 已经存在
2. 操作结果：销毁线性表 L

# ClearList(&L)

1. 初始条件：线性表 L 已经存在
2. 操作结果：将线性表 L 重置为空表

# ListEmpty(L)

1. 初始条件：线性表 L 已经存在
2. 操作结果：若线性表 L 为空，则返回 true，否则返回 false

# ListLength(L)

1. 初始条件：线性表 L 已经存在
2. 操作结果：返回线性表 L 中的数据元素个数

# GetElem(L,i,&e)

1. 初始条件：线性表 L 已经存在，$1\leq i\leq ListLength(L)$
2. 操作结果：用 e 返回线性表 L 中第 i 个数据元素的值

# LocateElem(L,e,compare())

1. 初始条件：线性表 L 已经存在，compare () 是数组元素判定函数
2. 操作结果：返回 L 中第一个与 e 满足 compare () 的数据元素的位序，若这样的元素不存在则返回值为 0

# PriorElem(L,cur_e,&pre_e)

1. 初始条件：线性表 L 已经存在
2. 操作结果：若 cur_e 是 L 中的数据元素，且不是第一个，则用 pre_e 返回它的前驱，否则操作失败，pre_e 无意义

# NextElem(L,cur_e,&next_e)

1. 初始条件：线性表 L 已经存在
2. 操作结果：若 cur_e 是 L 中的数据元素，且不是最后一个，则用 next_e 返回它的后继，否则操作失败，next_e 无意义

# ListInsert(&L,i,e)

1. 初始条件：线性表 L 已经存在，$1\leq i\leq ListLength(L)+1$
2. 操作结果：在 L 的第 i 个位置之前插入新的数据元素 e，L 的长度加 1

# ListDelete(&L,i,&e)

1. 初始条件：线性表 L 已经存在，$1\leq i\leq ListLength(L)$
2. 操作结果：删除 L 的第 i 个数据元素，并用 e 返回其值，L 的长度减 1

# ListTraverse(&L,visited())

1. 初始条件：线性表 L 已经存在
2. 操作结果：一次对线性表中每个元素调用 visited ()

# 线性表的存储结构

# 线性表的顺序存储表示

1. 线性表的顺序存储称为顺序存储结构或者顺序映像
2. 顺序存储定义：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构
3. 顺序表的特点：以物理位置相邻表示逻辑关系，任一元素均可随机存取

# 顺序表的查找算法分析

1. 平均查找长度 ASL（Average Search Length）
   1. 为了确定记录在表中位置，需要与给定值进行比较的关键字的个数的期望值叫做算法的平均查找长度
   2. 每个记录的查找概率相等，公式：$ASL_{ss}=\sum_{i=1}^{n} P_iC_i=\frac{1}{n} \sum_{i=1}^{n} = \frac{n+1}{2}$
2. 时间复杂度
   1. 查找、插入、删除算法的平均时间负责都为$O(n)$
3. 空间复杂度
   1. 顺序表操作算法的空间复杂度：$S(n)=O(1)$
4. 优点
   1. 存储密度大
   2. 可以随机存取表中任一元素
5. 缺点
   1. 在插入、删除某一元素时，需要移动大量元素
   2. 浪费存储空间
   3. 属于静态存储形式，数据元素的个数不能自由扩充

# 线性表的链式存储表示

# 相关概念

1. 链式存储结构：节点在存储器的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻
2. 线性表的链式存储表示又称为非顺序存储或链式映像
3. 用一组物理位置任意的存储单元来存放线性表的数据元素
4. 这组存储单元既可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上
5. 链表中的元素的逻辑次序和物理次序不一定相同

# 术语

1. 节点：数据元素的存储映像，由数据域和指针域两部分组成
2. 链表：n 个节点由指针链组成一个链表，它是线性表链式存储映像，称为线性表的链式存储结构
3. 单链表：节点只有一个指针域的链表，称为单链表或线性链表
4. 双链表：节点有两个指针域的链表，称为双链表
5. 循环链表：首尾相接的链表称为循环链表
6. 头指针：是指向链表中第一个节点的指针
7. 首元节点：是链表中存放第一个数据元素的节点
8. 头节点：是在链表的首元节点之前附设的一个节点

# 单链表（带头节点）

# 单链表示意图

单链表由表头唯一确定，因此单链表可以用头指针的名字来命名头指针名是 L，则把链表称为表 L

# 单链表常见操作

1. 单链表的初始化：
   1. 生成新节点作头节点，用头指针 L 指向头节点
   2. 将头节点的指针域置空
2. 判断链表是否为空：
   1. 空表：链表中无元素，判断头节点指针域是否为空
3. 单链表的销毁：
   1. 从头指针开始，依次释放所有节点
4. 清空链表：
   1. 链表仍然存在，称为空链表
   2. 依次释放所有节点，并将头节点指针域设置为空
5. 求单链表的表长
   1. 从首元节点开始，依次计数所有节点
6. 取第 i 个元素值
   1. 从链表头指针出发，顺着链域 next 逐个节点往下搜索，直至搜索到第 i 个节点为止
7. 按值查找
   1. 从链表头指针除法，判断当前节点的值是否相等，不相等则指针后移
8. 插入
   1. 在第 i 个节点前插入值为 e 的新节点
   2. 找到第 i 个节点的前一个节点，在后面执行插入操作
9. 删除
   1. 把第 i 个节点进行删除
   2. 找到第 i 个节点前一个节点，让前一个节点的指针域修改为后一个节点的地址

# 时间效率分析

1. 查找：因线性链表只能顺序存取，即查找时要从头指针开始，查找的时间复杂度为$O(n)$
2. 插入和删除：因为线性表链表不需要移动元素，只要修改指针，一般情况下复杂度为$O(1)$，但是，如果删除之前需要进行查找当前删除位置，所以所耗时间为$O(n)$

# 头插法

1. 从一个空表开始，重复读入数据
2. 生成新节点，将读入数据存放在新节点的数据域中
3. 从最后一个节点开始，依次将各节点插入到链表的前端

# 尾插法

1. 从一个空表 L 开始，将新节点逐个插入到链表的尾部，尾指针 r 指向链表的尾节点
2. 初始时 r 和 L 均指向头节点，每读入一个数据元素则申请一个新节点，将新节点插入到尾节点后，r 指向新节点

# 循环链表

# 定义

1. 循环链表：一种头尾相接的链表（即表的最后一个节点的指针域指向头节点，整个链表形成一个环）

2. 优点：从任意一个节点出发均可找到表中其他节点

3. 空表：头节点的指针域指向当前节点

# 双向链表

# 定义

1. 双向链表：在单链表的每个节点里再加一个指向其直接前驱的指针域 prior，这样链表中就形成了有两个方向不同的链，故称为双向链表

# 顺序表和链表比较

# 链式存储的优缺点

1. 优点：
   1. 节点空间可以动态申请和释放
   2. 数据元素的逻辑次序靠节点的指针来表示，插入和删除时不需要移动数据元素
2. 缺点：
   1. 存储密度小，每个节点的指针域需额外占用存储空间，当每个节点的数据域所占字节不多时，指针域所占存储空间的比重显得很大
   2. 链式存储结构是非随机存储，对任一节点的操作都要从头指针依指针链查找到该节点，这增加了算法的复杂度

# 顺序表和链表的比较

	顺序表	链表
存储空间（空间）	预先分配，会导致空间闲置或溢出现象	动态分配，不会出现存储空间闲置或者溢出
存储密度（空间）	不用为表示节点间的逻辑关系而增加额外的存储开销，存储密度等于 1	需要借助指针来体现元素间的逻辑关系，存储密度小于 1
存取元素（时间）	随机存取，按位置访问元素的时间复杂度为$O(1)$	随机存取，按位置访问元素时间复杂度为$O(n)$
插入、删除（时间）	平均移动约表中一半的元素，时间复杂度为$O(n)$	不需要移动元素，确认插入、删除位置后，时间复杂度为$O(1)$
适用情况	1. 表长变化不大，且能事先确定变化的范围 2. 很少进行插入或者删除操作，经常按元素位置序号访问数据元素	1. 长度变化较大 2. 频繁进行插入或者删除操作