小结

映射（字典）是关联形式的内存结构。
跳表是可以提供 \$O(log n)\$ 搜索的链表。
八叉树可以高效地精简表示图片时所需的颜色数量。
基于文本的模式匹配是很多应用领域常见的问题。
简单的模式匹配效率很低。
DFA 图易于使用，但不易构建。
KMP 图既易于使用，也易于构建。

讨论题

跳表的名字从何而来？
比较跳表与完全平衡的二叉搜索树。你能画图描述这两个概念么？
如果跳表中所有塔的高度都为 1，意味着什么？
给定 20 个键，是否可能有塔的高度达到 20？
选择一张图片，运行 OctTree 的量化程序。尝试设置不同的最大树高与最终的色彩数。
解释为什么 OctTree 节点的计算顺序是从最高有效位到最低有效位。
插入 (174, 145, 229) 和 (92, 145, 85) 两种颜色后，画出 OctTree 从顶层到第 5 层的节点。
画出模式 ATC 的 DFA 图。
计算模式 ATC 的不匹配链接。
为模式 ATCCAT 创建 KMP 图。

编程练习

实现 ArrayList 类的下列方法，并分析它们的性能。
- del：删除列表中给定位置上的元素。
- pop：实现弹出方法，包括带参数和不带参数两个版本。
- index：在 ArrayList 中搜索给定的值。若找到，返回它在列表中的位置，否则返回 -1。
- 让 ArrayList 可迭代。
Python 列表支持连接和重复。让 ArrayList 支持 + 和 * 运算。
为跳表实现 delete 方法。可以假设键存在。
为跳表实现方法，让映射支持下列操作。
- __contains__() 返回一个布尔值，用于说明键是否存在于映射中。
- keys() 返回映射中键的列表。
- values() 返回映射中值的列表。
为跳表实现 __getItem__ 方法和 __setItem__ 方法。
修改 OctTree 类，使用更高效的数据结构记录叶子节点，以改善 reduce 方法的性能。
为 OctTree 类增加两个方法，一个用于将量化图片写入磁盘文件，另一个用于以你所写的格式读取文件。
有些版本的量化算法会查看某个节点的子节点总数，并用这一信息决定精简哪些节点。修改 OctTree 的实现，在精简树时使用这个方法选择节点。
实现一个简单的模式匹配器，用于定位模式在文本中出现的所有位置。
修改第 7 章中的图实现，以支持对 KMP 图的表示。使用 mismatchLinks 写一个方法，根据模式创建完整的 KMP 图。有了图后，写一个程序，对这个 KMP 图运行任意文本，返回匹配是否存在。