数据结构

base C++

1、栈

1.1、应用

1.1.1、后缀表达式计算表达式的值：

顺序扫描表达式的每一项，然后根据他的类型做如下相应操作：如果该项是操作数，则将其压入栈中，如果该项是操作符/，则连续从栈中推出两个操作数Y和X，形成运算指令XY，并将计算结果重新压入栈中。

1.1.2、将中缀表示转换为后缀表示：

操作符ch	#	（	*，/，%	+，-	）
isp（in stack	0	1	5	3	6
icp（in coming	0	6	4	2	1

算法：

结束符#进栈，读入中缀表达式字符流的首字符ch；
重复执行以下步骤，知道ch=‘#’，同时栈顶的操作符也是‘#’
1. 若ch是操作数直接输出，读入下一个字符
2. 若ch是操作符，判断ch的优先级icp和当前位于栈顶的操作符op的优先级isp：
  1. 若icp(ch) > isp(op)，ch进栈，读入下一个字符
  2. 若icp(ch) < isp(op)，退栈并输出
  3. 若icp(ch) == isp(op)，退栈但不输出，若退出的是‘（’读入下一字符
输出序列为后缀表达式

1.1.3、回溯法求解迷宫：

递归

栈

深搜求解：

2、队列

优先队列

双端队列

2.1、应用

2.1.1、打印杨辉三角

2.1.2、电路布线

3、数组、串与广义表

3.1、稀疏矩阵

3.1.1、稀疏矩阵的转置

3.2、字符串

3.2.1、字符串的模式匹配：KMP算法。==实现一下！！！==

4、树

4.1、二叉树

4.1.1、二叉树遍历的应用

后序遍历：计算树的高度

前序遍历：

复制一棵树
判断两颗二叉树是否相等。
将二叉树的二叉链表以广义表的形式打印出来

4.1.2、二叉树遍历的非递归算法

==实现一下！！（前序、后序、层次遍历）==

4.1.3、二叉树的计数

具有n个节点的不同的二叉树有多少种？

递推式：

$\begin{matrix}b_0 = 1, && n = 0 \\ b_n = \sum_{i=0}^{n-1} b_i * b_{n-i-1}, && n > 0\end{matrix}$

求解结果：（catalan数）

$b_n = \frac{1}{n+1} C_{2n}^n = \frac{1}{n+1} \frac{(2n)!}{n!* n!}$

4.2、线索二叉树

to do：

==脑壳疼！先跳过！p213-p220==

4.3、树与森林

4.3.1、树与森林的互相转换

4.3.2、树与森林的遍历

5、字典

6、散列

Q：Hashmap的实现机理？

7、搜索

7.1、二叉搜索树

7.2、二叉平衡树

AVL树的旋转、插入、删除

*7.3、扩展树

7.4、红黑树

特征：

根结点和所有外部节点的颜色是黑色
从根结点到外部结点的途中没有连续两个结点的颜色是红色
所有从根到外部结点的路径上都有相同数目的黑色结点

8、图

重连通分量？

8.1、遍历

深搜、广搜

8.2、最小生成树

Prim、Kruskal

8.3、最短路径

Dijkstra、Floyd

8.4、AOV网络

拓扑排序

9、排序

性能评估

方法	时间复杂度	空间复杂度	稳定性	数据比较次数	数据移动次数
冒泡	$O(n^2)$	$O(1)$	是
插入		$O(1)$	是	$\frac{n^2}{4}$	$\frac{n^2}{4}$
选择		$O(1)$	否
希尔	$O(nlogn)$	$O(1)$	否
快速		$O(log_2n)$	否
堆排		$O(1)$	否
归并		$O(n)$	是
分配