We read every piece of feedback, and take your input very seriously.
To see all available qualifiers, see our documentation.
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
https://oi-wiki.org/search/dlx/
first 数组指向的元素并不特殊,不是像图中那样,在边界充当哨兵。
first
应该把 first[] 指向某个图中的元素,且链表的指针不应指向它。
first[]
另外,文中「双向十字链表」的描述,很容易让读者(比如我自己)认为指针必须按照物理顺序来指(即向右的指针只能指向右边的下一个元素,或者右边没有元素时,指向左起第一个元素,等等),于是在阅读代码时感到很困惑,因为代码中指针并没有按照物理顺序来指。事实上在 DLX 中只要能遍历到行 / 列的所有元素即可,它们间的相对顺序对算法没有影响。建议在文中说明一下。
The text was updated successfully, but these errors were encountered:
这个是实现的问题吗,听起来像是双向循环链表的两种不同实现(有哨兵/无哨兵)
Sorry, something went wrong.
first 数组指向的元素并不特殊,不是像图中那样,在边界充当哨兵。 应该把 first[] 指向某个图中的元素,且链表的指针不应指向它。 这个是实现的问题吗,听起来像是双向循环链表的两种不同实现(有哨兵/无哨兵)
DLX 的双向循环链表在横向不需要哨兵,因为在算法中并不涉及判断是否是到达左右边界之类的操作,如果硬加的话不仅没用,还要手动跳过。
从实现上说,无论是 原始论文 还是本文的实现均不带哨兵,头指针指向的是该行的某一个值。(我建议使用原始论文中的图替换这张图。)
因此图上横向的哨兵应该是绘图错误,应该删掉。
我是这一篇文章的主要编辑者,是我的问题。这个地方的 first 数组并不应该作为链表中的一个元素,而应该作为一个指示符。事实上,first[x] 和 x 所在那一行的第一个元素应该是 等价的。 我正在修复这个问题。
first[x]
x
Successfully merging a pull request may close this issue.
请选择:
我正在访问这个页面
https://oi-wiki.org/search/dlx/
我发现页面有这样的问题
first
数组指向的元素并不特殊,不是像图中那样,在边界充当哨兵。应该把
first[]
指向某个图中的元素,且链表的指针不应指向它。另外,文中「双向十字链表」的描述,很容易让读者(比如我自己)认为指针必须按照物理顺序来指(即向右的指针只能指向右边的下一个元素,或者右边没有元素时,指向左起第一个元素,等等),于是在阅读代码时感到很困惑,因为代码中指针并没有按照物理顺序来指。事实上在 DLX 中只要能遍历到行 / 列的所有元素即可,它们间的相对顺序对算法没有影响。建议在文中说明一下。
The text was updated successfully, but these errors were encountered: