串

串的定义

主串：包含子串的串

子串：串中任意连续的字符组成的子序列

串的存储结构

串的顺序存储

串的链式存储

存储密度低，即用一个字节存储想要的信息，用四个字节存储辅助信息

存储密度高，每个结点存多个字符，不一定如下图的只包含四个字符，可以更多

朴素模式匹配算法

字符串模式匹配：在主串中找到与模式串相同的子串，并返回其位置

使用字符串基本操作

主串长度为n，模式串（进行匹配的串）长度为m，将主串中所有长度为m的子串依次与模式串对比，直到找到一个完全匹配的子串，或者所有子串都不匹配为止

最多对比n-m+1个子串

使用数组下标

每次对比i与j对应的字符是否相等，如上图在第六个位置不匹配

若匹配失败，主串指针i指向下一个子串的第一个位置，模式串指针j回到模式串的第一个位置

每次重新匹配新子串时

1
2

i = i - j + 2;
j = 1;

代码如下

KMP算法

由于暴力算法经常回溯时间开销大

要理解模式串在移动，主串不移动

在不匹配的位置前划一到分割线，模式串向右移，直到与主串对的上或者完全跨过分界线
具体操作见求next数组

代码思想，利用一个next数组

如果不匹配则改变j的值，通过j的位置在next数组来匹配应该如何修改j

next数组只与模式串有关，和主串无关

KMP代码

求next数组

在不匹配的位置前划一到分割线，模式串向右移，直到与主串对的上或者完全跨过分界线

next[1]：一定为0，j=0,i++,j++
next[2]：一定为1，让模式串向右滑动一位
剩下的需要计算

另一个例子

求nextval数组

对于模式串 abaabc

next数组为

当j指向3时匹配失败，即a与主串不匹配，此时j应指向1，但是1的字符仍是a，此时进行匹配也一定是失败的，j指向5时同理

优化方法

当j指向3时不匹配，此时j修改为1，j指向1还是a一定不匹配，此时j修改为0

当j指向5时不匹配，此时j修改为2，j指向2还是b一定不匹配，此时j修改为1

nextval数组为

next[1]：一定为0，j=0,i++,j++

例题1：

例题2：

树

树的常考性质

1. 结点数=总度数+1

2. 度为m的树与m叉树的区别

度为m的树：至少有一个节点度为m

m叉树：可能所有节点的度都小于m

3. 度为m的树（或m叉树）第i层至多有$m^{i-1}$个节点

4. 高为h的m叉树至多有$\frac {m^h-1}{m-1}$个结点

5. 高度为h的m叉树至少有h个结点，

6. 高度为h度为m的树至少有h+m-1个节点

特殊的二叉树

满二叉树

完全二叉树

二叉排序树

平衡二叉树

二叉树常考性质

1. 非空二叉树中度为0、1、2的结点数分别为$n_0、n_1、n_2$则$n_0=n_2+1$

即度为0的结点比度为2的结点个数多一个

$n=n_0+n_1+n_2=n_1+2n_2+1$

2. 二叉树第i层至多有$2^{i-1}$个结点

3. 高为h的m叉树至多有$2^h-1$个结点

完全二叉树常考性质

二叉树存储结构

二叉树顺序存储

二叉树链式存储

二叉树的先中后序遍历

普通方法

例题1：

画图快速求遍历序列

先序遍历代码

中序遍历代码

后序序遍历代码

二叉树的层次遍历

由遍历序列构造二叉树

其他方法类同

线索二叉树

中序线索二叉树

先序线索二叉树

后序线索二叉树

二叉树的线索化

树的存储结构

树和二叉树的转化

对于二叉树，记住左边结点是孩子结点，右边结点是兄弟结点

森林和二叉树的转化

先将每一个树转化为二叉树，再将每个树的根节点视为平级的兄弟结点

树和森林的遍历

树的遍历

深度优先遍历（先根遍历与后根遍历）

先根遍历：直接对树先根遍历
树的先根遍历等同于转化为二叉树先根遍历

后根遍历：直接对树后根遍历
树的后根遍历等同于转化为二叉树中根遍历

广度优先遍历（层次遍历）

树的层序遍历与二叉树步骤相同

森林的遍历

森林先根遍历

森林先根遍历等同于从左到右对每个树进行先根遍历

森林先根遍历等同于转化为二叉树进行先根遍历

森林后根遍历

森林后根遍历等同于从左到右对每个树后根遍历

森林后根遍历等同于转化为二叉树中序遍历

哈夫曼树和哈夫曼编码

WPL

注意只计算叶子节点的WPL

定义

哈夫曼树构造方法

例题1：

哈夫曼编码

通过构造哈夫曼树来找到最少的内容大小即找到WPL

每个字符都需要处在叶子节点来构造哈夫曼树
构造过程：每个字符都带有自己的权值，构造完成哈夫曼树后，左0右1来确定每个字符的编码

图

图的基本概念

图的定义

顶点的度、出度、入度

顶点—顶点的关系描述

连通图与强连通图

连通分量

强连通分量

生成树

生成森林

先求出连通分量

再求生成树，所有生成树的集合就是生成森林

边的权、带权图、带权网

邻接矩阵

表示方法

求各顶点度、入度、出度

邻接矩阵法存储带权图（网）

邻接矩阵法性质

邻接表法

有向图与无向图区别

邻接矩阵与邻接表区别

十字链表存储有向图

十字链表只能用于存储有向图

顺着绿色线路：找到指定顶点的所有出边
顺着橙色线路：找到指定顶点的所有入边

邻接多重表存储无向图

邻接多重表只能用于存储无向图

图的广度优先遍历（BFS）

树VS图

代码实现

利用与树的层次遍历相同思想的——队列

例题1：

例题2：

非连通图的广度优先遍历

广度优先生成树

广度优先生成森林

图的深度优先遍历（DFS）

类比树的先根遍历

实现过程

利用与树的先根遍历相同思想的——递归和栈

非连通图的深度优先遍历

深度优先生成树

深度优先生成森林

最小生成树

要求背景

性质

1. 最小生成树可能有多个，但是边的权值之和总是唯一且最小的
2. 最小生成树的边数=顶点数-1.砍掉一边不连通，增加一边出线回路
3. 如果一个连通图本身就是一个树，其最小生成树就是其本身
4. 只有连通图才有生成树，非连通图只有生成森林

Prim算法

从某一个顶点开始构建最小生成树

可以有不同的最小生成树，但是边的权值之和总是唯一且最小的

Prim算法实现思想

Kruskal算法

从一个权值最小的边构造最小生成树

Kruskal算法实现思想

最短路径问题

要求背景

单源最短路径：BFS算法（无权图）

无权图可以视为一种特殊的带权图，每条边权值都为1

如何使用数组信息

单源最短路径：Dijkstra算法（带权图且权值非负、无权图）

如何使用数组信息

各顶点间的最短路径：Floyd算法（带权图且非负权值回路、无权图）

核心代码

可解决Dijkstra解决不了的负权图

有向无环图（DAG）

拓扑排序（基于DAG）

AOV网

拓朴排序定义及实现

一定是有向无环图

关键路径

AOE网

关键路径定义

如何求关键路径

https://www.bilibili.com/video/BV1EQ4y1v7iV/?spm_id_from=333.337.search-card.all.click&vd_source=c3a97ce560782e2efc0a1c39a73bc81b

查找

查找算法评价指标

ASL

查找成功

查找失败

顺序查找

顺序查找又叫线性查找，通常用于线性表

从头到尾或者从后往前依次查找

代码实现

带哨兵查找代码

顺序查找效率分析

折半查找

算法思想

又称二分查找，仅适用于有序的顺序表（递增或递减）

首位分别由low、high指针，每次通过找到mid中间指针来判断所查找的目标大于还是小于mid指针所指元素。

如果目标元素＞mid元素，令low=mid+1
如果目标元素＜mid元素，令high=mid-1

最后判断mid元素是否等于目标元素

查找成功

查找失败

实现代码

折半查找判定树

实现思路

右子树结点数-左子树结点数=0或1

折半查找判定树性质

折半查找判定树一定是平衡二叉树

满足二叉排序树的定义

分块查找

算法思想

在索引表中确定所查元素所属的分块（可顺序、可折半）
然后在块内顺序查找

另一个例子

当查找第九个元素时，由于30的范围只有6-8，所以查找失败

折半查找找索引

索引表直接包含目标关键字

索引表不直接包含目标关键字

查找失败

二叉排序树

定义

即中根遍历得到的序列是有序的

二叉排序树的查找

非递归

查找成功

查找失败

递归

二叉排序树的插入

二叉排序树的构造

不同序列所构造的二叉排序树也可能不同

二叉树的删除

删除结点为叶子结点

删除结点只有一颗左子树或右子树

例题1：

例题2：

删除结点有左右两棵子树

通过直接后继

通过直接前驱

平衡二叉树

定义

平衡（排序）二叉树的插入

插入后保持二叉排序树特性不变

最重要的是找到最小不平衡子树

不同的最小不平衡子树调整情况

LL（右旋）

RR（左旋）

LR（先左旋再右旋）

RL（先右旋再左旋）

练习

例题1：

例题2：

例题3：

平衡二叉（排序）树的删除

删除结点保持二叉排序树特性不变

与插入类同

具体操作步骤

练习

例题1：

例题2：

例题3：

例题4：

不平衡仍然存在，继续②

例题5：

改为对前驱节点的删除

子树顶替

例题6：

改为对后继结点的删除

1. 选择最右边的是孙子

2. 选择最左边的是孙子

散列查找

散列表（哈希表）

特点：数据元素的关键字与其存储地址直接相关

同义词与冲突

处理冲突的方方法

拉链法

之前是通过数组来存放数据元素，现在改为数组里保存一个指针指向数据元素

开放定址法

散列查找

先通过对元素取余得到数组所在位置，然后对所在位置的链表进行查找

查找长度：在查找运算中需要对比关键字的次数成为查找长度

查找成功

查找失败

常见的散列函数

除留余数法

直接定址法

数字分析法

平方取中法

排序

插入排序

直接插入排序

代码

折半插入排序

代码

冒泡排序

一趟趟经过排序后知道某一趟没有发生交换时停止

代码

快速排序

根据序列中两个元素关键字的比较结果来对换这两个记录在序列中的位置

省略步骤……

49的位置已经确定了，不用再管了，此时分别对49左右两个表进行快排

最后经过一次次的快排

代码

简单选择排序

每一趟在代排序元素中选取关键字最小（或最大）的元素加入有序子序列

代码