Sketch ofD&A4.md

##串-《数据结构与算法》6.8 有限长度的字符序列，即限定数据元素为字符的线性表
两个串相等当且仅当

两个串的长度相等
每个对应位置的字符相同

###串匹配 已知目标串T 和模式串P，模式匹配就是要在目标串T 中找到一个与模式串P 相等的子串 Brute-Force 布鲁特福斯算法

最坏情况下的时间复杂度为O(n×m)  

KMP 算法 ☆一定要好好看啊╮(╯▽╰)╭
当模式P 不匹配时，尽量向右移动最大距离，避免重复
预处理函数Next

void Next(char *P) 
{
	int m = strlen(P); // 模式串P 的长度
	N[0] = 0; // 位置0 处的部分匹配串长度为0
	int i = 1; j = 0; // 初始化比较位置
	while(i < m) 
	{
		if(P[i] == P[j])  // 已经匹配了j+1 个字符
		{			
			N[i] = j+1; // 部分匹配串长度加1
			i++; j++;  // 比较位置各加1
		}
		else if( j > 0) j = N[j-1]; // 移动：用部分匹配串对齐
		else f N[i++] = 0;g //j 在串头时部分匹配串长度为0
	}
}

KMP 算法的时间复杂度为O(m + n)
Boyer-Moore 算法
将模式串P 与主串T 的子序列进行反向比较
若P 包含c，则移动P 使c 在P 中的最后一次出现P[l] 对准T[i]
否则，移动P 使P[0] 对准T[i+1]
最坏情况下，算法的时间复杂度为O(n × m + s)

##树
树是由n≥0 个结点组成的集合，有一个根（Root）结点，它只有直接后继，无直接前驱
除根以外的其它结点划分为m > 0 个不相交的有限集合，每个集合又是一棵树，并称之为根的子树
####与树相关的概念较多，在此不赘述，但请认真了解 ###二叉树 二叉树是k = 2 的k 叉树
二叉树有五种不同形态

具有n 个结点的完全二叉树的深度为log2 (n + 1)
完全二叉树不一定是满的！
二叉树的链式存储

数据域：存放数据  
指针域：存放指向左子树和右子树的指针

typedef struct tnode 
{
	ElemType data;
	struct tnode *lchild;
	struct tnode *rchild;
} TreeNode;

二叉树遍历——访问根结点的时机选择
先序遍历：V - L - R
中序遍历：L - V - R
后序遍历：L - R - V
以上三种用递归来实现
层序遍历 用队列来实现
二叉树的建立
由二叉树的先序序列和中序序列可唯一地确定一棵二叉树
###Huffman 树与编码 树的路径长度：从树根到所有叶子结点的路径长度之和
在所有路径相同的二叉树中带权路径长度最小的树称为Huffman树或最优二叉树
构造 参考离散（贪心算法）
Huffman 编码
平均编码长度最短 满足前缀编码的性质（任一字符编码都不是其它字符编码的前缀）
二叉搜索树
在二叉搜索树上可以高效地进行查找

##图 图定义为G = (V,E)
V 是一个有限集合
E 是V 中元素的有序（或无序）二元组，即{<v,w> |v,w ∈ V; v ≠w}

某些图的边具有与它相关的数, 称为权，这种带权的图叫做网络

路径长度是路径上边的数目  
路径序列中没有重复出现的顶点称为简单路径  
路径的起点和终点相同（v = v*）称为回路或环  
除了v 之外，其余顶点不重复出现的回路称为简单回路

无向图
在无向图中，如果从顶点v 到顶点w 有路径，则称v 和w 是连通的
对于图中任意两个顶点v都是连通的，则称G 是连通图 无向图的极大连通子图称为连通分量
有向图
在有向图中，如果对于每一对vi，vj ，从vi 到vj 和从vj 到vi 都存在路径，则称G 为强连通图
有向图的极大强连通子图称为有向图的强连通分量

欧拉路径是遍历图中每条边且只访问一次的路径
终点回到起点的欧拉路径是欧拉回路
###图的存储
邻接矩阵表示
图的邻接矩阵表示需要与v^2 成比例的存储空间
网络的邻接矩阵表示：如果将邻接矩阵中元素改为边的权值，邻接矩阵可以用来表示网络

空间复杂度O(|V|^2)
边插入操作O(1)
边删除操作O(1)
判边存在操作O(1)
图的迭代器
	访问某一个顶点的邻接顶点O(|V|)
	访问所有顶点的邻接顶点O(|V|^2)

邻接表表示
采用一个链表数组来表示图
每个链表头结点为图的顶点
同一个顶点发出的边链接在同一个链表中

无向图的邻接表表示需要(|V| + 2|E|) 个链表结点
最坏情况时间复杂度分析

空间复杂度O(|V| + c|E|)
边插入操作O(1)
边删除操作O(|V|)
判边存在操作O(|V|)
图的迭代器
	访问某一个顶点的邻接顶点O(|V|)
	访问所有顶点的邻接顶点O(|V|+ |E|)

对于稠密图，适于采用邻接矩阵表示
对于稀疏图，适于采用邻接表来表示
###图的遍历 深度优先搜索
广度优先搜索
##最小生成树 生成树，包含图中全部n 个顶点，但只有n -1 条边

最小生成树对于给定的加权无向连通图，最小生 成树是一棵生成树，并且其权（所有 边的权值之和）不会大于其它任何生 成树的权 KRUSKAL 算法

对图中所有边按权值进行排序  
令最小生成树的边集为空  
从图中取出权值最小的一条边  
	如果这条边与最小生成树中的边能构成环，则舍弃  
	否则，将这条边加入最小生成树  
重复上述过程，直至将|V|-1 条边加入最小生成树

Kruskal 算法的时间复杂度为O(|E| log|E|)
Kruskal 算法对于稀疏图是好的选择

PRIM 算法

初始最小生成树是一个空集  
首先从图G 中任取一个结点a 加入最小生成树，找出当前非最小生成树的顶点与当前最小生成树直接相连的所有边
取出最短边，把它和非最小生成树顶点b 加入最小生成树，更新边序列
重复上述过程，直到最小生成树包括G 中所有结点

Prim 算法的时间复杂度是O（|V|^2)
对于稠密图，Prim 的邻接矩阵实现是首选方法
###最短路径
单源最短路径：给定一个起始顶点s，找出从s 到图中其它各顶点的最短路径，即最短路径树
全源最短路径：找出连接图中各对顶点的最短路径

Dijkstra 算法 -单源最短路径

初始化点集S = {0}，V 为顶点集
确定各顶点到源点的最短距离
从V\S 中找出距源点s 最近的结点v
	更新S，使S = S + {v}
	更新各点到源点的距离
重复步骤3，直至S = V

Dijkstra 算法的时间复杂度为O(|V|^2)

全源最短路径
对图中每个顶点使用Dijkstra 算法
or
Floyd 算法

初始化|V|×|V| 的矩阵D0 为图的边值矩阵
对k = 0~n-1进行如下迭代
	Dk[i][j] =min{Dk-1[i][j],Dk-1[i][k]+Dk-1[k][j]}
|V|×|V| 即为从顶点i 到顶点j 的最短路径长度，这条路径不经过编号大于k 的顶点
最后得到的就是全源最短路径矩阵

Floyd 算法可以在与O(|V|^3)的时间内计算出一个网中的所有最短路径
编者按：这四种算法似乎比较重要，好好看。前三个本质上为贪心，最后一个为动态规划
##二分图 (这部分介绍了但算法没细讲，或者我没认真听(╯‵□′)╯︵┻━┻)
二分图是满足如下性质的图：
顶点集合V 分割为两个子 集V1 和V2，且满 足V1∪V2 = V 和V1 \ V2 = ∅;
边集E 中的每条边e 的两个端点必 须在不同的顶点集内
二分图匹配
匈牙利算法的复杂度为O（n^4)
加权二分图的匹配
稳定婚姻问题...