数算期中整理

整理了一些 ppt 上和复习过程中觉得自己不够扎实的

其实压中了几个题,可惜还是疏忽了…… 算法填空竟然 CE 了。

没看到那个栈中元素是指针。。

  1. 判断序列是否是出栈序列
  2. 中缀表达式转后缀表达式
  3. 栈 队列 互相模拟

编辑距离
kmp
N个节点的树有多少种
试证明,在具有n(n>=1)个结点的k叉树中,有n(k-1)+1个指针是空的。
出栈序列计数 卡特兰数
通配符匹配
N0 = N2+1
堆是一颗完全二叉树节点的层次序列
带权并查集 扩展 kmp kmp 的应用 kmp 自动机
堆 P120
已知二叉树的先序序列和中序序列,可以唯一确定一棵二叉树
image

https://wenku.baidu.com/view/ec8f638dbb68a98271fefafe.html
https://wenku.baidu.com/view/aa6845d30029bd64793e2c2e.html
image
要减一

k叉哈夫曼树 (n-1)%(k-1)==0 否则补虚拟节点
书上的 kmp 板子

非递归 dfs
image

两个队列模拟栈
队列、栈、堆与数据结构的存储结构无关
在一个具有n个结点的有序单链表中插入一个新结点并仍保持其有序的时间复杂度为 O(N)
表达式求值,和栈顶运算符优先级相同的话也要弹出(比如减号会把加号弹出

BST 的删除 P118

image

出栈序列计数:1/(n+1) *C(2n,n)种

image
image

堆向下调整的时候是把小的儿子换上来

image

队列模拟栈 每一时刻ab只有一个为空
image