在我的词法分析器生成器中，我使用 McNaughton 和 Yamada 算法构建 NFA，其属性之一是从 I 到 J，在 J 位置用 char 标记。
因此，NFA 的每个节点都可以简单地表示为下一个可能状态的列表。
哪种数据结构最适合存储此类数据？它必须为所有可能的状态提供快速查找并使用更少的空间，但插入时间并不那么重要。
最佳答案
我的理解是，您想要对图形进行编码，其中节点是状态，边是转移，并且每条边都标有字符。对吗？
枯燥但实用的答案是为每个状态创建一个对象，并在该对象中的一些小结构中对转换进行编码。
最简单的是一个数组，由字符代码索引:它尽可能快，但不是天生的空间效率。您可以通过使用一种偏移量、截断数组来提高空间效率:仅存储数组中包含转换的部分，以及该部分的开始和结束索引。在其中查找字符时，检查其代码是否在范围内；如果不是，则将其视为空边(或返回起始状态的边或其他)，如果是，则获取索引处的元素(字符代码 - 开始)。这有意义吗？
一个更复杂的选项是一个小哈希表，它会更紧凑但速度稍慢。我会建议封闭散列，因为冲突列表会占用太多内存；线性探测应该足够了。您可以考虑使用完美散列(查找)，这需要花费大量时间来生成表格，但随后会提供无冲突查找。不过，生成过程相当复杂。
一个聪明的方法是同时使用数组和哈希表，并根据边的数量选择一个或另一个:如果压缩数组超过，比如说，三分之一满，则使用它，但如果不是，使用哈希表。
现在，您可以做一些更激进的事情，那就是使用数组，但将它们重叠 - 如果它们稀疏，它们就会有很多洞，如果您很聪明，您可以安排它们以便每个数组中的条目与其他数组中的孔对齐。这将为您提供快速查找，而且还具有出色的内存效率。您将需要一些方案来区分查找何时找到某些东西以及何时找到一个空槽以及其他状态的转换，但我相信您能想到一些东西。
关于data-structures - NFA 表示的数据结构，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4570890/