链表

• 单链表

• 双链表

基本没有正式用到的知识。像模拟的数据结构。

以 0 为 头节点， 1为尾节点。模拟实现即可。

• 循环链表

栈

先进后出

• 典例：表达式求值(acw 3302)

队列

先进先出

单调栈

维护一个单调的栈。每次弹栈时记录需要的信息

• 模板

• 例题

单调队列

维护一个单调的队列，记录信息，队首超出范围（或不符合当前要求）则弹出。

• 例题

kmp

字符串匹配。求串s在t中出现的次数。

记录一个 $pi[i]$ 表示以 $i$ 为节点的串，前缀后缀相等的最大长度。

将s和t拼接起来，如果 $pi[i] == n$ （n为s串长度）则证明出现了一次，ans++；

并查集

fa[i] 表示i节点的父节点。

压缩路径，按秩合并，带权并查集等常用思想。代码简单，难在灵活应用

堆

待补习，暂时用优先队列代替。

hash表

进制哈希。

• 使用自然溢出是否有必要模质数？

• 是否有必要加一个小质数防止被卡？

无特殊需求（如前缀和等）时，其实可以加。（但没啥很大意义）

trie

• 字典树用边表示字母

• 有相同前缀的单词公用前缀节点，那我们可以的得出每个节点最多有26个子节点（在单词只包含小写字母的情况下）

• 整棵树的根节点是空的。为什么呢？便于插入和查找，这将会在后面解释。

• 每个单词结束的时候用一个特殊字符表示，图中用的 $x$ ，那么从根节点到任意一个 $x$ 所经过的边的所有字母表示一个单词。

• 有关异或：用01串建trie树，边为0或1。