Knuth跳舞链接算法的数据结构

Question

我很抱歉,如果我的问题听起来很愚蠢,因为我的数据结构理解不是很好.

我一直在阅读Knuth的Dancing Links算法,并且非常了解它基本上是如何工作的.提到跳舞链接的数据结构可视化看起来像一个包含列和行的表,每个单元格连接到它们的上,下,左和右单元格.我还读到在这个算法中使用循环双链表.

我想知道的是,如何将双链表放入带有列和行的表中？

据我所知,大多数双链表只有2个指针(向上和向下),这是否意味着我必须制作我自己的自定义链表,它有4个指针(向上,向下,向左和向右)？或者还有其他方法吗？

提前致谢.

Answer 1

该算法对每一行和每一列使用一个双向链表，而不仅仅是一个列表。

这篇关于使用跳舞链接来解决数独的文章有一个很好的图片。

至少在本文的代码中，行确实表示为同一节点中的左右指针，列表示为上下指针，或多或少如您所描述的那样，因此列表是互连的。