这里是《算法竞赛入门经典》第六章-数据结构基础的笔记。
队、栈、链表等略。

内存池#

我比较喜欢用指针+动态内存分配来管理某些动态数据结构，比如树等。可以用内存池的方法管理内存，防止内存泄露。
一个简单的方式是，一般数据结构会有一个“节点”（node），这个就是要动态分配的对象。可以一开始申请一个比较大的node数组，并全部进行初始化，为内存池，再维护一个空闲空间表freelist，从这个表中获取空闲空间的内存。释放内存的时候统一释放最开始申请的node数组即可。

• 数据结构中申请新节点的时候，用 newnode() 从 freelist 中申请。具体就是从 freelist 中弹出一个空闲节点的指针来返回。
• 数据结构中删除节点，用 freenode()“释放”这个内存。具体就是把要删除的指针重新加入到freelist中。
• freelist可以简单的用 STL queue解决。

树与递归#

一个值得强调的点：题目中说以递归顺序给出一颗树的时候，会是先序。即根左右。如果有一边没有儿子，一般会给一个特殊标记告诉你那里没有儿子/子树。
在这样的输入下，可以实现很方便的边输入边递归处理。

输入与递归：天平#

输入一个树状天平，根据力矩相等原则判断是否平衡。天平左右两端各有一个物体，此物体可以是子天平。输入会分别给出两端物体/子天平的质量与距离。按照上面说的递归顺序给出。

类似的题目可以很容易递归处理，而且是边递归边输入，不需要建树。大抵是：如果在当前天平，读入左边物体，如果是子天平就递归左边的天平，计算左边总质量（用以计算左力矩）与左边天平是否平衡，如果是物体就直接计算左力矩。对右边进行同样处理，然后判断当前天平是否平衡。
类似的题目（尤其是递归地输入树）大致可以说成：

• 如果当前子树为空，返回。
• 递归处理左子树。
• 递归处理右子树。
• 递归处理完后，处理当前子树，返回。

很像后序遍历。
在一些特殊的非二叉树题目中，也可使用。

子树观念#

很多时候不要把儿子当儿子，而是一棵较为独立的子树，有利于问题的分解。上面已经体现了这一点，下面这一题强调。

深度为D的满二叉树，所有节点一次编号，在结点1处放一个小球，他会下落。每个分支结点上有开关，每次有小球落在这个分支结点上时，开关状态都会翻转。如果关，往左落，如果开则往右。初始全关。问第 I 个小球会落在哪个叶子。

可以用经典二叉堆的数组表示这个树，可以方便地找左儿子右儿子。
把每个分支结点都看成子树的根。如果小球是第奇数次来到这个子树，在这个分支结点上会往左走，否则往右走。
巧妙之处在于，如果在某分支结点的子树上，该球是第 I 个在此分支结点的，则会是向左走的第 (I+1)/2 个小球，向右走的第 I/2 个小球。即它如果往左走，在左子树上的“次数”就是 (I+1)/2.
可以找规律等。妙啊。

图#

DFS连通块#

就是普通DFS，不过在每访问到一个结点的时候标记当前结点属于哪个连通块的编号。

BFS最短路#

一般想到 Dijsktra。但是如果没有边权，只能“一步一步走”的话，可以化简为最简单的BFS，即把 Dijkstra 的优先队列直接用队列，每次弹出对首，每次压入下一层（经过判重，如果已经压入一会就永远不用再压入）的结点至队尾。

无权的BFS在状态空间搜索（在暴力求解中）中用的相当多。而很多路径问题有额外的限制，比如方向啊、转向啊等等，因而描述其位置状态的标志要多一些维度。
值得注意的是，在这种情况下最好把结点理解成状态，把图的“下一层”理解为当前状态的后继。

Abbott的复仇
输入一个迷宫，输入起点终点，找一条最短路。并且，迷宫中的每个结点，进入此结点的“方向”（北东南西）不同，允许做的转向（前进、左转、右转）也不同。

此题里位置状态需要用（（结点位置），进入结点的方向）来表示，因而“下一层”的状态后继除了边以外还受进入结点方向的影响。并且，进入结点的方向也必须添加到判重中来，必须全等才算重复。

倒叙BFS最短路#

从起点到终点求最短路，可能有多样的“最短”定义（比如有多个key等），这时候可以倒叙BFS。从终点往外BFS，实际上得到终点到所有其它点的最短距离（左右其它点到终点的最短距离），然后从起点开始走，每次走的时候，在起点链接的所有结点中，必须走最短距离-1的结点。而从这些结点中，可以用其它 Key 值寻找符合要求的最短路。

双向BFS#

有时候需要从起点、终点同时开始BFS。大致是从起点开始BFS一层，然后从终点开始BFS“倒退”一层，直到两个方向所确定的结点刚好互补。

拓扑排序#

有向图的拓扑排序，基于入度的拓扑排序算法。
拓扑排序可以用于有向图判环。如果拓扑排序失败则有有向环。
拓扑排序问题，大多难在如何建模为一个图的拓扑排序。
（之前在洛谷上见的一个和火车相关的题就是例子）

欧拉路径#

无向图欧拉：连通，如果所有结点度为偶，有欧拉回路；如果恰有两个奇，有欧拉路径。
有向图欧拉：弱连通，如果所有结点入度=出度，有欧拉回路；如果恰有一个节点入度=出度+1，另一个出度=入度+1，有欧拉有向路径。
可以DFS搜索欧拉路径（回路）。