Dancing links是一种能高效实现Knuth的X算法的技术,它可以使很多搜索问题得到极大的优化。
假设x是一个双向链表中的一个节点,L[x]表示X的前驱,R[x]表示x的后继,
则R[L[x]] = R[x], L[R[x]] = L[x]这一操作可以把x从链表中移除,这是众所周知的,
当然,一个细致的程序员还会用 L[x] = R[x] = x或 L[x] = R[x] = NULL这样的操作来清除x,
以免发生内存泄露,所以只有很少的程序员意识到,若不清除x则 R[L[x]] = x, L[R[x]] = x
这个操作可以把刚才移除的x恢复到之前的链表中,而这样的恢复功能在有些时候是很有用的,
例......
阅读全文