datetime:2022-04-09 17:46
author:nzb
数据结构与算法
绪论
基本概念
数据
数据元素、数据项
数据对象、数据结构
数据类型、抽象数据类型（ADT）
数据结构三要素
逻辑结构
集合
线性结构
树形结构
图状结构（网状结构）
物理结构（存储结构）
顺序存储
物理内存中是连续的非顺序存储
物理内存中是分散的链式存储
索引存储
散列存储
数据的运算
学习建议
- 概念多，比较无聊。抓大放小，重要的是形成框架，不必纠结细节概念。
算法
程序 = 数据结构 + 算法
数据结构是要处理的信息
算法是处理信息的步骤
算法的五个特性
有穷性
有穷时间内能执行完算法是有穷的
程序可以是无穷的
确定性
相同的输入只会产生相同的输出可行性
可以用已有的基本操作实现算法输入
丢给算法处理的数据输出
算法处理的结果
“好”算法的特质
正确性
能正确解决问题可读性
对算法的描述能让其他人也看得懂健壮性
算法能处理一些异常状况高效率与低储存量需求
即算法执行省时、省内存
时间复杂度、空间复杂度
时间复杂度和空间复杂度
时间和空间增长的趋势时间复杂度
时间开销与问题规模 n 之间的关系如何计算
找到一个基本操作（最深层循环）
分析该基本操作的执行次数 x 与问题规模 n 的关系 x = f(n)
x 的数量级 O (x) 就是算法时间复杂度 T(n)
大 O 表示法（Big O）：，T (n) = O ( f(n) )
T(n)：算法的渐进时间复杂度 f(n)：代码执行次数 O：正比例关系
常用技巧
加法法则：O (f(n)) + O(g(n)) = O (max(f(n),g(n)))
乘法法则：O(f(n)) x O(g(n)) = O(f(n) x g(n))
记忆技巧：常对幂指阶
常见的时间复杂度量级
x 轴：输入问题的量级；y 轴：时间的复杂度
O (1)
O (logN)
- 设想需要 K 次循环 i 就会大于等于 n；则2^k = n；k = log2n
O (n)
解释
int i =1：执行一次
i<=n；i++；x++：各执行3次
所以复杂度：O (1 + 3N) = O (N)；因为 Big O 计算的是 N 接近于无限大的情况下，所以常量 1 和 倍数 3 都没意义了
O (nlogN)
O (n^2)
因为 n 趋近于无限大，所以 n 相对于 n ^2 就是一个常量
O (nm)
三种复杂度
最坏时间复杂度
考虑输入数据“最好”的情况平均时间复杂度
考虑所有输入数据都等概率出现的情况最好时间复杂度
考虑输入数据“最好”的情况
空间复杂度
空间开销（内存开销）与问题规模 n 之间的关系如何计算
普通程序
找到所占空间大小与问题规模相关的变量
分析所占空间 x 与问题规模 n 的关系 x = f(n)
x 的数量级 O (x) 就是算法空间复杂度 S(n)
递归程序
找到递归调用的深度 x 与问题规模 n 的关系 x = f(n)
x 的数量级 O (x) 就是算法空间复杂度 S(n)
注：有的算法各层函数所需的存储空间不同，分析方法略有区别
常用技巧
加法法则：O (f(n)) + O(g(n)) = O (max(f(n),g(n)))
乘法法则：O(f(n)) x O(g(n)) = O(f(n) x g(n))
记忆技巧：常对幂指阶
O (1)
需要的空间是一个常数量
O (n)
经过 for 循环，数组里面就会有值，如果往数组里面添加越多的数据，则需要更多的空间内存等
O (n^2)
- 矩阵（二维数组）
其他复杂度指标
线性表
- 定义
逻辑结构
值的注意的特性
数据元素同类型、有限、有序重要术语
表长、空表
表头、表尾
前驱、后继
数据元素的位序（从 1 开始）
类似索引
基本操作
运算创销、增删改查（所有数据结构适用的记忆思路）
判空、判长、打印输出（还可以根据实际需求增加其他基本操作）
其他值的注意的点
理解什么时候要传入参数的引用“&”
值传递还是引用传递函数命名要有可读性
存储/物理结构
顺序表（顺序存储）
存储结构
逻辑上相邻的数据元素物理上也相邻实现方式
静态分配
使用“静态数组”实现
大小一旦确定就无法改变
动态分配
使用“动态数组”实现
顺序表存满时，可再用 malloc 动态扩展顺序表的最大容量
需要将数据元素复制到新的存储区域，并用 free 函数释放原区域
特点
随机访问
能在 O(1) 时间内找到第 i 个元素存储密度高
扩展容量不方便
插入、删除元素不方便
基本操作
插入
插入位置之后的元素都要后移
时间复杂度
最好 O(1)
插入末尾，数据不动最坏 O (n)
插入表头，数据后移平均 O(n)
删除
删除位置之后的元素都要前移
时间复杂度
最好 O(1)
删除末尾，数据不动最坏 O (n)
删除表头，数据前移平均 O(n)
查找
按位查找
获取表 L 中第 i 个位置的元素的值
用数组下标即可得到第 i 个元素 L.data[i - 1]
时间复杂度
最好、最坏、平均时间复杂度都是 O(1)
按值查找
在顺序表 L 中查找第一个元素值等于 e 的元素，并返回其位序
从第一个元素开始依次往后检索
时间复杂度
最好 O(1)
第一个位置最坏 O(n)
最坏一个位置平均 O(n)
每个位置的概率相同
代码要点
注意位序 i 和数组下标的区别
位序是第几个元素，从 1 开始，下标是从 0 开始判断位序 i 的合法性
链表（链式存储）
单链表
定义
用“链式存储”（存储结构）实现了“线性结构”（逻辑结构）
一个结点存储一个数据元素
各结点间先后关系用一个指针表示
两种实现
不带头结点
空表判断：L == NULL，写代码不方便带头结点
空表判断：L -> next == NULL，写代码方便 头指针 L 加上下一个结点不带数据只带下一个结点的指针域
基本操作
插入
按位序插入
循环遍历找到第 i -1 的节点，然后插入带头结点
当前指针指向，从 0 开始，表示第几个节点不带头结点
当前指针指向，从 1 开始，表示第几个节点
指定结点的后插操作
- 在 p 结点后插入元素 e
- s 为插入的结点
- s -> data = e
- s-> next = p->next
- p->next = s
指定结点的前插操作
知道头指针
依次遍历找到 p 结点，然后插入即可，时间复杂度 O(n)不知道头指针
- 在 p 结点后插入元素 e
- s 为插入的结点
- s -> next = p -> next
- s -> data = p -> data
- p -> data = e
- p -> next = s
删除
按位序删除
和插入操作类似指定结点的删除
- 删除指定结点 p
- 需要改变前驱结点的 next 指针
- 方法1：传入头指针，循环找 p 的前驱结点
- 方法2：类似结点前插入
- p -> data = p -> next -> data
- p -> next = p -> next -> next
- 指定结点是最后一个结点时，需要特殊处理，因为q -> next = NULL，没有 data
查找
注意带头和不带头以及最后一个结点（就是 p 指针为 NULL）按位查找
注意与“顺序表”对比
单链表不具备“随机访问”的特性，只能依次扫描
按值查找
求单链表长度
Key
三种基本操作的时间复杂度都是 O(n)
注意边界条件的处理
建立
尾插法
头插法
链表的逆置
双链表
初始化
头结点的 prior、next 都指向 NULL插入（后插）
注意新插入结点、前驱结点、后继结点的指针修改
边界情况：新插入结点在最后一个位置，需特殊处理
删除（后删）
注意删除结点的前驱结点、后继结点的指针修改
边界情况：如果被删除结点是最后一个数据结点，需特殊处理
遍历
从一个给定结点开始，向后遍历、向前遍历的实现（循环的终止条件）
链表不具备随机存取特性，查找操作只能通过顺序遍历实现
循环链表
循环单链表
- 判断循环单链表是否为空：L -> next == L
- 判断结点 p 是否为循环单链表的表尾结点：p -> next == L，p指针下一个是否指向头指针
循环双链表
- 判断循环双链表是否为空：L -> next == L
- 判断结点 p 是否为循环双链表的表尾结点：p -> next == L，p指针下一个是否指向头指针
静态链表
用数组的方式实现的链表
优点：增、删操作不需要大量移动元素
缺点：不能随机存取，只能从头结点开始依次往后查找；容量固定不可变
适用场景
不支持指针的低级语言
数据元素数量固定不变的场景（如操作系统的文件分配表 FAT）
使用
随机存取就是直接存取，可以通过下标直接访问的那种数据结构，与存储位置无关，例如数组。
非随机存取就是顺序存取了，不能通过下标访问了，只能按照存储顺序存取，与存储位置有关，例如链表。
栈（Stack）
定义
一种操作受限的线性表，只能在栈顶插入、删除
特性：后进先出（FIFO）
术语：栈顶、栈底、空栈
基本操作
创、销
增、删（元素进栈、出栈，只能在栈顶操作）
增
删
查（获得栈顶元素，但不删除）
判空
S.top = -1 栈顶指针为-1
顺序栈
顺序存储
用静态数组实现 ，并需要记录栈顶指针基本操作
- 创、增、删、查
- 销：清空、回收 只需要 top = -1
- 都是 O(1) 时间复杂度
两种实现
初始化 top = -1
指向栈顶元素入栈
- S.data[++S.top] = x
- 是先栈顶指针加一后赋值，不能先赋值在加一，这样会覆盖元素
出栈
- x = S.data[S.top--]
- 是先赋值后栈顶指针减一
获得栈顶元素
x = S.data[S.top]栈空/满栈条件？
到达栈顶：s.top = MaxSize -1
初始化 top = 0
指向栈顶元素的后一位，接下来可以插入元素的位置入栈
- S.data[S.top++] = x
- 先赋值在加一
出栈
- x = S.data[--S.top]]
- 是先栈顶指针减一后赋值
获得栈顶元素
x = S.data[S.top-1]栈空/满栈条件？
到达栈顶：s.top = MaxSize
共享栈
两个栈共享同一片内存空间，两个栈从两边往中间增长
初始化
0 号栈栈顶指针初始时 top0 = -1；1 号栈栈顶指针初始时 top1 = MaxSize栈满条件
top0 + 1 = top1
链栈
跟单链表类似，只是只能在头部操作用链式方式实现的栈
两种实现方式
带头结点
不带头结点（推荐）
基本操作
创（初始化）
增（进栈）
删（出栈）
查（获取栈顶元素）
如何判空、判满？
栈的应用
括号匹配
依次扫描所有字符，遇到左括号入栈，遇到右括号则弹出栈顶元素检查是否匹配
匹配失败情况
左括号单身
栈非空右括号单身
栈已空左右括号不匹配
表达式求值
概念
运算符、操作数、界限符三种表达式
中缀表达式（人算）
运算符在操作数中间后缀表达式（机算，常用）
运算符在操作数后面 一个中缀表达式可以对应多个后缀、前缀表达式前缀表达式（机算，不常用）
运算符在操作数前面
后缀表达式
中缀转后缀
按“左优先”原则确定运算符的运算次序
一个中缀表达式只对应一个后缀表达式（确保算法的“确定性”）根据上面确定的次序，依次将各个运算符和与之相邻的两个操作数按 <左操作数 右操作数 运算符> 的规则合体
后缀转中缀
从左往右扫描，每遇到一个运算符，就 将 <左操作数 右操作数 运算符>变为 (左操作数 运算符 右操作数)的形式计算
从左往右扫描，遇到操作数入栈，遇到运算符则弹出两个栈顶元素运算后入栈（注意：先弹出的元素是“右操作数”）
前缀表达式
中缀转前缀
按“右优先”原则确定运算符的运算次序
根据上面确定的次序，依次将各个运算符和与之相邻的两个操作数按 < 运算符 左操作数 右操作数> 的规则合体
计算
从右往左扫描，遇到操作数入栈，遇到运算符则弹出两个栈顶元素运算后入栈（注意：先弹出的元素是“左操作数”）
递归
栈中的每一个元素对应内存中的一块区域里面的数据不跟其他元素冲突
队列
定义
一种操作受限的线性表，只能在队尾插入、在队头删除
特性：先进先出（FIFO）
术语：队头、队尾、空队列、队头元素、队尾元素
基本操作
创、销
增、删（入队、出队、只能在规定的一段进行）
查（获得队头元素，但不删除）
判空
队列的顺序实现
实现思路
用静态数组存放数据 元素，设置队头/队尾（front、rear）指针
循环队列：用模运算（取余）将存储空间在逻辑上变为“环状”
Q.rear = (Q.rear + 1) % MaxSize
重要考点
如何初始化、入队、出队
如何判空、判满
如何计算队列的长度
分析思路
确定 front、rear 指针的指向
rear 指向队尾元素后一个位置
rear 指向队尾元素
确定判空判满的方法
牺牲一个存储单元
增加 size 变量记录队列长度
增加 tag = 0/1 用于标记最近的一次操作是出队/入队
队列的链式实现
区别
带头结点
不带头结点
基本操作
创（初始化）
增（入队）
注意第一个元素入队删（出队）
注意 最后一个元出队查（获取队头元素）
判空
判满？不存在的，可以无限加（内存足够）
队列变种
双端队列
允许从两端插入、两端删除的队列输入受限的双端队列
允许从两端删除、从一端插入的队列输出受限的双端队列
允许从两端插入、从一端删除的队列
队列应用
树的层次遍历
图的广度优先遍历
操作系统的应用
CPU资源的分配：多个进程运行（浏览器、QQ、微信）
打印数据缓冲区
特殊矩阵压缩存储
对称矩阵
特点
对方阵中的任意一个元素，有 a(i,j) = a(j,i)压缩
只存储主对角线 + 下三角区（或主对角线 + 上三角区）
三角矩阵
特点
上三角区全为常数（下三角矩阵）；或下三角区全为常数（上三角矩阵）压缩
按行优先/列优先规则依次存储非 常量区域，并在最后一个位置存放常量 c
三对角矩阵（带状矩阵）
特点
当 |i - j| > 1时，有 a (i,j) = 0（1 <= i, j<=n）压缩
按行优先/列优先规则依次存储带状区域
稀疏矩阵
特点
非零元素个数远小于零元素个数压缩
只存储非零元素顺序存储
顺序存储三元组（行，列，值）链式存储
十字链表法
串
字符串
定义
串，即字符串（string）是由零个或多个字符组成的有限序列
术语：串长、空串、空格串、子串、主串、字符在主串中的位置、子串在主串中的位置
串 V.S 线性表
串的数据对象限定为字符集
串的基本操作大多以“子串”为操作对象
基本操作
定位操作
比较操作
字符集编码
每个字符在计算机中对应一个二进制数，比较字符的大小其实就是比较二进制数的大小存储结构
顺序存储和链式存储跟线性表一样顺序存储
静态数组
动态数组
链式存储
可让每个结点存多个字符，没有字符的位置使用“#” 或 “\0”补足静态数组
基本操作
求子串
串的比较
求串在主串中的位置
子串匹配算法
朴素模式匹配算法
串的模式匹配：在主串中找到与模式串相同的子串，并返回其所在的位置
朴素模式匹配算法（简单模式匹配算法）思想
将主串中与模式串长度相同的子串搞出来，挨个与模式串对比
当子串与模式串某个对应字符不匹配时，就立即放弃当前子串，转而检索下一个子串
若模式串长度为 m，主串长度为 n，则直到匹配成功/匹配失败最多需要（n - m + 1）* m次比较
最坏时间复杂度：O(nm)
最坏情况：每个子串的前 m- 1个字符都和模式串匹配，只有第 m 个字符不匹配
比较好的情况：每个子串的第 1 个字符就与模式串不匹配
KMP 算法
粗劣分析算法性能
KMP 算法优化
二者比较
朴素模式匹配算法的缺点：当某些子串与模式串能部分匹配时，主串的扫描指针 i 经常回溯，导致时间开销增加。最坏时间复杂度 O(nm)
KMP 算法：当子串和模式串不匹配时，主串指针 i 不回溯，模式串指针 j = next[j]
如果不会经常出现子串与模式串部分匹配的时候，KMP 算法性能也不会比朴素算法好多少算法平均时间复杂度：O(n + m)
next 数组手算方法：当第 j 个字符匹配失败，由前 1~j - 1 个字符组成的串记为 S，则：next[j] = S 的最长相等前后缀长度 + 1
特别的：next[1] = 0, next[2] = 1
链表和数组的区别
数组静态分配内存，链表动态分配内存；
数组在内存中连续，链表不连续是分散的；
数组元素在栈区，链表元素在堆区；
数组利用下标定位，时间复杂度为O(1)，链表定位元素时间复杂度O(n)；
链表也没有下标的概念，只能通过头节点指针，从每一个节点，依次往下找，因为下个节点的位置信息只能通过上个节点知晓。数组插入或删除元素的时间复杂度O(n)，链表的时间复杂度O(1)。
链表只需要知道操作位置的指针
树与二叉树
定义
树（Tree）是 n（n>=0)个结点的有限集。n=0 时称为空树。在任意一颗非空树中：
1）有且仅有一个特定的称为根（Root）的结点；
2）当 n>1 时，其余结点可分为 m(m>0) 个互不相交的有限集T1、T2、......、Tn，其中每一个集合本身又是一棵树，并且称为根的子树。
此外，树的定义还需要强调以下两点：
1）n>0 时根结点是唯一的，不可能存在多个根结点，数据结构中的树只能有一个根结点。
2）m>0 时，子树的个数没有限制，但它们一定是互不相交的。
示例树：
结点的度
一个结点拥有的子树数目称为结点的度。叶子节点的度为 0 。
叶子节点：没有子节点的节点所有节点中的最大的度称为树的 度，树中的节点树即为树中所有节点的度之和加一：即：树中的节点树 = 树中所有节点的度之和 + 1
结点关系
结点子树的根结点为该结点的孩子结点。相应该结点称为孩子结点的双亲结点。
上图中，A 为 B 的双亲结点，B 为 A 的孩子结点。
同一个双亲结点的孩子结点之间互称兄弟结点。
上图中，结点 B 与结点 C 互为兄弟结点。
结点层次和树的深度
从根开始定义起，根为第一层，根的孩子为第二层，以此类推。
树中结点的最大层次数称为树的深度或高度。上图所示树的深度为4。
二叉树
定义
二叉树是 n(n>=0) 个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树组成。
二叉树特点
1）每个结点最多有两颗子树，所以二叉树中不存在度大于2的结点。
2）左子树和右子树是有顺序的，次序不能任意颠倒。
3）即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。
4）非空二叉树只有一个根节点。
二叉树性质
1）在二叉树的第 i 层上最多有 2^(i-1) 个节点 。（i>=1）
2）二叉树中如果深度为 k ,那么最多有 2^k-1个节点。(k>=1）
3）n0 = n2 + 1： 度为0的节点（叶子节点）总是比度为 2 的节点多一个。
n0 表示度数为 0 的节点数，n2 表示度数为2的节点数。4）在完全二叉树中，具有n个节点的完全二叉树的深度为[log2n]+1，其中[log2n]是向下取整。
具有 n 个节点的二叉树的深度至少为 [log2n]+1，其中 [log2n] 是向下取整。5）若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点有如下特性：
(1) 若 i=1，则该结点是二叉树的根，无双亲, 否则，编号为 [i/2] 的结点为其双亲结点;
(2) 若 2i>n，则该结点无左子树， 否则，编号为 2i 的结点为其左子树结点；
(3) 若 2i+1>n，则该结点无右子树， 否则，编号为 2i+1 的结点为其右子树结点。
斜树
斜树：所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树。
满二叉树
满二叉树：在一棵二叉树中。如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。
满二叉树的特点有：
1）第 k 层上有 2 ^ (k - 1) 个节点。
2）深度为 m 的满二叉树有 2 ^m - 1个节点
3）非叶子结点的度一定是2。
完全二叉树
完全二叉树：对一颗具有 n 个结点的二叉树按层编号，如果编号为 i(1<=i<=n) 的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树。
除最后一层外，每一层的节点数都达到了最大值，在最后一层上只缺少右边的若干个节点。
满二叉树一定是完全二叉树，但反过来不一定成立。
二叉树的存储结构
顺序存储
二叉树的顺序存储结构就是使用一维数组存储二叉树中的结点，并且结点的存储位置，就是数组的下标索引。
二叉树为完全二叉树
一棵完全二叉树采用顺序存储方式，当二叉树为完全二叉树时，结点数刚好填满数组。
二叉树不为完全二叉树
其中浅色结点表示结点不存在，其中，∧表示数组中此位置没有存储结点。此时可以发现，顺序存储结构中已经出现了空间浪费的情况。
右斜树
对于这种右斜树极端情况，采用顺序存储的方式是十分浪费空间的。
因此，顺序存储一般适用于完全二叉树。
二叉链表
链式存储：由二叉树定义可知，二叉树的每个结点最多有两个子节点。因此，可以将结点数据结构定义为一个数据和两个指针域。
采用一种链表结构存储二叉树，这种链表称为二叉链表。
二叉树遍历
二叉树的遍历一个重点考查的知识点。定义
二叉树的遍历：是指从二叉树的根结点出发，按照某种次序依次访问二叉树中的所有结点，使得每个结点被访问一次，且仅被访问一次。
二叉树的访问次序可以分为四种
前序遍历
中序遍历
后序遍历
层序遍历
前序遍历
根 - 左 - 右前序遍历通俗的说就是从二叉树的根结点出发，当第一次到达结点时就输出结点数据，按照先向左在向右的方向访问。
上图所示二叉树的前序遍历输出为：ABDHIEJCFG
中序遍历
左 - 根 - 右中序遍历就是从二叉树的根结点出发，当第二次到达结点时就输出结点数据，按照先向左在向右的方向访问。
上图所示二叉树的前序遍历输出为：HDIBJEAFCG
后序遍历
左 - 右 - 根后序遍历就是从二叉树的根结点出发，当第三次到达结点时就输出结点数据，按照先向左在向右的方向访问。
上图所示二叉树的前序遍历输出为：HIDJEBFGCA
层次遍历
- 层次遍历就是按照树的层次自上而下的遍历二叉树。针对上图所示二叉树的层次遍历结果为：ABCDEFGHIJ
遍历常考考点
1）已知前序遍历序列和中序遍历序列，确定一棵二叉树。
例题：若一棵二叉树的前序遍历为ABCDEF，中序遍历为CBAEDF，请画出这棵二叉树。
分析：前序遍历第一个输出结点为根结点，故A为根结点。早中序遍历中根结点处于左右子树结点中间，故结点A的左子树中结点有CB，右子树中结点有EDF。
按照同样的分析方法，对A的左右子树进行划分，最后得出二叉树的形态如下图所示
2）已知后序遍历序列和中序遍历序列，确定一棵二叉树。
- 后序遍历中最后访问的为根结点，因此可以按照上述同样的方法，找到根结点后分成两棵子树，进而继续找到子树的根结点，一步步确定二叉树的形态。
注：已知前序遍历序列和后序遍历序列，不可以唯一确定一棵二叉树。
