0x18 总结与练习

在本章中，我们探讨了程序设计以及算法实现中可能用到的一些基本数据结构，如栈、队列、链表（邻接表结构）、Trie、二叉堆以及与Hash、字符串相关的问题。通过对这些数据结构的理解和分析，读者对于上一章中学到的各种算法思想也应该有了更加深入的体会。对于这两章的内容，希望读者能够仔细思考各种模型的每个细节，主动寻找和归纳基本算法与基本数据结构之间的结合点。

如果读者认真阅读并实现了这两章的每一个算法、数据结构以及每一道例题，那么读者应该已经初步迈进了算法领域的大门，能够使用较为贴切的术语与其他探索者进行思维碰撞和交流，能够循着正确的方向独立提出一个问题或是扩展一个解答，而不是敲着死记硬背的模板，做着一知半解的试题。从下一章起，读者将会开始被当作专业人士对待，一些面向初学者的解释和过于细节的代码实现可能不再会出现于各个知识点和题解中。因此，建议读者先花一些时间，回顾一遍前两章所学内容和所做习题，检查一遍知识点列表，最好能够辅以网络上各大题库中更多题目的训练。

本章知识点

栈

栈的基本实现，使用数组和栈顶位置变量模拟一个栈

栈的灵活应用，例如使用辅助栈保存额外信息、对顶栈等

表达式计算，后缀表达式、中缀转后缀、中缀表达式递归求值

单调栈

队列

一般队列、双端队列、循环队列的基本实现

单调队列，理解使用单调性处理问题的思想

链表与邻接表

双向链表的实现与操作，以及数组模拟链表

邻接表结构，图和树的邻接表存储与遍历

Hash

Hash表，使用邻接表结构实现开散列法

字符串 Hash，前缀与区间 Hash 值、二分法的结合

字符串

KMP 模式匹配算法，next 数组的灵活运用

最小表示法，循环同构问题

Trie

Trie的插入、检索等基本操作

Trie与xor问题

二叉堆

二叉堆的基本操作及其实现，Insert、GetTop、Extract、Remove等

二叉堆的灵活应用，与贪心算法相结合，数据结构间“建立映射”的思想

$k$ 叉Huffman树与Huffman编码

$\spadesuit$ 练习

1. 完成本章中所有例题的代码实现

2.括号画家

Candela是一名漫画家，她有一个奇特的爱好，就是在纸上画括号。这一天，刚刚起床的Candela画了一排括号序列，其中包含小括号（）、中括号[]和大括号{}，总长度为 $N$ 。这排随意绘制的括号序列显得杂乱无章，于是Candela定义了什么样的括号序列是美观的：

(1) 空的括号序列是美观的；
(2) 若括号序列 $A$ 是美观的，则括号序列 $(A), [A], \{A\}$ 也是美观的；
(3) 若括号序列 $A$ 、 $B$ 都是美观的，则括号序列 $AB$ 也是美观的。

例如[08]O是美观的括号序列，而 $)\{0\} []$ （则不是。

现在Candela想在她绘制的括号序列中，找出其中连续的一段，满足这段子序列是美观的，并且长度尽量大。你能帮帮她吗？

题目测试数据与标程参见配套光盘，提示：栈

1. 表达式计算 4

题目地址：TYVJ1043，提示：栈/中缀表达式计算

1. City Game

题目地址：POJ1964/CODEVS2491，提示：单调栈

1. Sliding Window

题目地址：POJ2823，提示：单调队列

6.内存分配

题目地址：POJ1193/NOI1999，提示：链表/二叉堆

7.Matrix

题目地址：BZOJ2351，提示：Hash

8. Necklace

题目地址：BZOJ1398/VIJOS1382，提示：字符串/最小表示法

9. Milking Grid

题目地址：POJ2185，提示：字符串/KMP模式匹配

10. Phone List

题目地址：POJ3630，提示：Trie

11. Black Box

题目地址：POJ1442，提示：二叉堆

12.生日礼物

题目地址：BZOJ2288，提示：二叉堆/链表/贪心