数据结构考研，数据结构考研真题
【CSDN 编者按】说到算法和数据结构每个程序员应该都很了解。近日，从事 AI+ 开发工具工作的 Austin Z. Henley发布了他的第三篇热门帖子，总结道每个程序员都应该尝试具有挑战性的算法和数据结构。
原文链接：https://austinhenley.com/blog/challengingalgorithms.html
作者 | Austin Z. Henley 译者 | 禾木木
出品 | CSDN（ID：CSDNnews）
此前，Austin Z. Henley 发布了两篇“每个程序员都应该尝试具有挑战性的项目”。文中列出了每个程序员都应该去尝试的项目，包括文本编辑器、太空入侵者游戏、 BASIC 编译器、一个小型的操作系统、一个电子表格、一个视频游戏控制台模拟器、光线追踪器、键值存储 Web API 、Web 浏览器和股票交易机器人。这两篇文章在网络上爆红，一个月内浏览量超过 10 万次。
继这两篇后，Austin Z. Henley 又发布了他的第三篇内容，在文章中列出了程序员应该尝试的有趣的算法和数据结构：
拓扑序列
递归下降解析
Myers 差分算法
Bloom filter
Piece table
伸展树
拓扑序列
拓扑排序简单讲就是在可求拓扑序列的有向无回路图（有向无环图）中求取拓扑序列的排序算法。常见的场景包括确定构建系统的任务顺序、电子表格中单元格的评估顺序、学生每学期毕业应上哪些课，以及各种调度问题。
Austin Z. Henley 曾在 Tennessee 大学任教时使用它来重新排列图表，使其更易于阅读。
拓扑排序：https://en.wikipedia.org/wiki/Topological_sorting
拓扑排序交互式可视化：https://www.cs.usfca.edu/~galles/visualization/TopoSortDFS.html
递归下降解析
这一次，就像打开了一种超能力！
如果你需要摄取递归数据格式或编写编程语言，这是最适合的工具。轻松地编出语法，并将每个语法规则映射到代码函数中。
感觉就像它自己在编码一样。
你可以在几个小时内用它制作一个简单的编译器。
Teeny Tiny 编译器：https://austinhenley.com/blog/teenytinycompiler2.html
制作翻译：https://amzn.to/3HT015y
递归下降解析器：https://en.wikipedia.org/wiki/Recursive_descent_parser
Myers 差分算法
处理字符串通常是一项非常常见的编程任务，但作者通常是通过暴力强制来解决需要计算的任何问题。程序员们都学过 Levenshtein 距离，但是如果需要以一种合理的方式显示两个字符串之间的差异呢？
其中，Git 用于显示差分的默认算法是 Myers 差分算法。
Myers 差分算法：https://blog.jcoglan.com/2017/02/12/the-myers-diff-algorithm-part-1/
代码和交互式可视化：https://blog.robertelder.org/diff-algorithm/
Bloom filter
布隆过滤器（ Bloom filter）可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。
它实际上只对大规模的问题有帮助，例如当你需要一个非常大的哈希表时，它则是对概率数据结构的一个很好的介绍。在内存很小的情况下，它可以告诉你表中是否存在某个项目，否则它只能告诉该项是否存在。
Bloom filter：https://en.wikipedia.org/wiki/Bloom_filter
操作 Bloom filter：https://onatm.dev/2020/08/10/let-s-implement-a-bloom-filter/
示例：https://llimllib.github.io/bloomfilter-tutorial/
Piece table
当 Austin Z. Henley 第一次尝试制作文本编辑器时，便将所有文本存储在一个数组中。但这会导致性能问题（例如，当用户在任何地方插入文本而不是结尾时）。几年后，在一次实习面试中被问到如何实现一个高性能文本缓冲区。
他也会考虑该使用什么。有一些不同的方案需要权衡：rope, gap buffer, 或是 piece table。使用 piece table，可以跟踪对文本执行的编辑，而仅仅不是只保留生成的文本。它使许多其他功能变得很简单（例如，撤销支持和增量保存）。
不过，piece table 只对文本编辑器有用。只要有可以任意修改的大数据缓冲区时，就可以使用它。
Piece table：https://en.wikipedia.org/wiki/Piece_table
VS Code 的文本缓冲区：https://code.visualstudio.com/blogs/2018/03/23/text-buffer-reimplementation
Piece table：https://darrenburns.net/posts/piece-table/
伸展树
那么自我优化的数据结构怎么样呢？
伸展树是一种二叉树，它倾向于将最近访问的元素靠近根，并且这样做不需要维护任何额外的元数据。每次访问一个元素时，它都会被移动到根目录。
这是一个带有内置缓存的树，实现起来非常简单！
伸展树互动可视化：https://www.cs.usfca.edu/~galles/visualization/SplayTree.html
伸展树：https://en.wikipedia.org/wiki/Splay_tree
TypeScript 中的实现：https://github.com/w8r/splay-tree
如果你还知道哪些更有趣的算法或是数据结构，可以在评论区留言呦。
https://austinhenley.com/blog/challengingalgorithms.html
https://austinhenley.com/blog/challengingprojects.html
https://austinhenley.com/blog/morechallengingprojects.html
数据结构考研(数据结构考研参考)
