笔试数据结构选填题

目录

卡特兰数Catalan：出栈序列/二叉树数

树

二叉树

N0=1+N2

哈夫曼树（最优二叉树）Huffman

度m的哈夫曼树只有度为0和m的结点：Nm=(n-1)/(m-1)

平衡二叉树AVL

Nh表示深度为h最少结点数，则N0=0，N1=1，N2=2，Nh=Nh-1+Nh-2+1

最小生成树

图

最短路径

模式匹配

BF模式匹配：最坏T(n)=O(m*n)，实际 接近O(m+n)

KMP模式匹配：O(m+n)

完整见：前端笔试常考设计模式，操作系统，数据结构，ACM模板，经典算法，正则表达式，常用方法_前端考试模板_参宿7的博客-CSDN博客

卡特兰数Catalan：出栈序列/二叉树数

一个栈的进栈序列为1，2，3，...，n，有多少个不同的出栈序列：

合法的出栈序列的数量=出栈序列的总数-非法序列的数量

∵先序+中序 可 唯一 确定 一棵二叉树

  其关系 就如 入栈序列+出栈序列 可 唯一 确定 一个 栈

∴先序 确定 二叉树个数，即先序 确定 中序个数，

NLR确定LNR，LN、NL相当于压栈，R相当于进了立即出

∴h(n)=Catalan卡特兰数= 

树

二叉树

N0=1+N2

哈夫曼树（最优二叉树）Huffman

度m的哈夫曼树只有度为0和m的结点：Nm=(n-1)/(m-1)

平衡二叉树AVL

Nh表示深度为h最少结点数，则N0=0，N1=1，N2=2，Nh=Nh-1+Nh-2+1

最小生成树

1.  定义：连通，无向带权 图 的生成树，权值之和最小的
2. 唯一：当任意环中边的权值相异，则最小生成树唯一

	普里姆Prim算法	克鲁斯卡Kruskal算法
共同	基于贪心算法
特点	从顶点开始扩展最小生成树	按权递增次序，选择不构成环的边

图

最短路径

	Dijkstra算法	Floyd算法
问题	单源最短路径（单起源到各个顶点的最短距离，从源点的临近点开始）	各个顶点之间的最短路径

模式匹配

主串S，长n，模式串T，长m。T在S中首次出现的位置

BF/朴素模式匹配：最坏T(n)=O(m*n)，实际 接近O(m+n)

KMP模式匹配：O(m+n)

1. next[j]：T的第j个字符失配于S中的第i个字符，需要用T的第next[j]个字符与S中的第i个字符 比较

abcdeabf（f失配，第next[j]=3个字符c比较）T起点开始，和失配点结束的最大公共前缀

1. next[1]=0：i++;
2. next[2]=1，next[j]：i不变;

 模式匹配过程：

1. S中第i个char，T中第j个char
2. j指向 失配点/ j=m（全部匹配成功） 为 一趟

虽KMP的T(n)=O(m+n)，

但实际中BF的T(n)接近O(m+n)，

∴至今采用

只有T中有很多部分匹配，KMP才明显快