我正在尝试在Java中实现Knuth的Dancing Links算法。
根据Knuth，如果x是一个节点，我可以通过C中的以下操作完全解除一个节点的链接:
L[R[x]]<-L[x]
R[L[x]]<-R[x]
并通过:
恢复未链接L[R[x]]<-x
R[L[x]]<-x
我在主方法中做错了什么?
如何在Java中实现解链接和还原?
这是我的主要方法:
///////////////
DoublyLinkedList newList = new DoublyLinkedList();
for (int i = 0; i < 81; i++) {
HashSet<Integer> set = new HashSet<Integer>();
set.add(i);
newList.addFirst(set);
}
newList.displayList();
// start at 69
newList.getAt(12).displayNode();
//HOW TO IMPLEMENT UNLINK?
//newList.getAt(12).previous() = newList.getAt(12).next().previous().previous();
//newList.getAt(12).next() = newList.getAt(12).previous().next().next();
newList.displayList();
//HOW TO IMPLEMENT REVERT UNLINK?
//newList.getAt(12) = newList.getAt(12).next().previous();
//newList.getAt(12) = newList.getAt(12).previous().next();
System.out.println();
///////////////
这是DoublyLinkedList类:
public class DoublyLinkedList<T> {
public Node<T> first = null;
public Node<T> last = null;
static class Node<T> {
private T data;
private Node<T> next;
private Node<T> prev;
public Node(T data) {
this.data = data;
}
public Node<T> get() {
return this;
}
public Node<T> set(Node<T> node) {
return node;
}
public Node<T> next() {
return next;
}
public Node<T> previous() {
return prev;
}
public void displayNode() {
System.out.print(data + " ");
}
@Override
public String toString() {
return data.toString();
}
}
public void addFirst(T data) {
Node<T> newNode = new Node<T>(data);
if (isEmpty()) {
newNode.next = null;
newNode.prev = null;
first = newNode;
last = newNode;
} else {
first.prev = newNode;
newNode.next = first;
newNode.prev = null;
first = newNode;
}
}
public Node<T> getAt(int index) {
Node<T> current = first;
int i = 1;
while (i < index) {
current = current.next;
i++;
}
return current;
}
public boolean isEmpty() {
return (first == null);
}
public void displayList() {
Node<T> current = first;
while (current != null) {
current.displayNode();
current = current.next;
}
System.out.println();
}
public void removeFirst() {
if (!isEmpty()) {
Node<T> temp = first;
if (first.next == null) {
first = null;
last = null;
} else {
first = first.next;
first.prev = null;
}
System.out.println(temp.toString() + " is popped from the list");
}
}
public void removeLast() {
Node<T> temp = last;
if (!isEmpty()) {
if (first.next == null) {
first = null;
last = null;
} else {
last = last.prev;
last.next = null;
}
}
System.out.println(temp.toString() + " is popped from the list");
}
}
我不熟悉Knuth的Dancing Links算法，但我发现这篇文章让它变得非常清楚。我发现下面这段非常有用:
Knuth利用了双链表的基本原理。当从列表中删除对象时，只需要两个操作:
x.getRight()。setLeft(x.getLeft())
x.getLeft()。setRight(> x.getRight())然而，当将对象放回列表时，所有需要做的是反向操作。
x.getRight()。setLeft(x)
x.getLeft()。setRight(x)就是这样需要把对象放回去的是对象本身，因为对象仍然指向列表中的元素。除非x的指针是修改后，此操作非常简单。
为了实现它，我添加了链接/解除链接的setter。看到评论:
import java.util.HashSet;
public class DoublyLinkedList<T> {
public Node<T> first = null;
public Node<T> last = null;
static class Node<T> {
private T data;
private Node<T> next;
private Node<T> prev;
public Node(T data) {
this.data = data;
}
public Node<T> get() {
return this;
}
public Node<T> set(Node<T> node) {
return node;
}
public Node<T> next() {
return next;
}
//add a setter
public void setNext(Node<T> node) {
next = node;
}
public Node<T> previous() {
return prev;
}
//add a setter
public void setPrevious(Node<T> node) {
prev = node;
}
public void displayNode() {
System.out.print(data + " ");
}
@Override
public String toString() {
return data.toString();
}
}
public void addFirst(T data) {
Node<T> newNode = new Node<T>(data);
if (isEmpty()) {
newNode.next = null;
newNode.prev = null;
first = newNode;
last = newNode;
} else {
first.prev = newNode;
newNode.next = first;
newNode.prev = null;
first = newNode;
}
}
public Node<T> getAt(int index) {
Node<T> current = first;
int i = 1;
while (i < index) {
current = current.next;
i++;
}
return current;
}
public boolean isEmpty() {
return (first == null);
}
public void displayList() {
Node<T> current = first;
while (current != null) {
current.displayNode();
current = current.next;
}
System.out.println();
}
public void removeFirst() {
if (!isEmpty()) {
Node<T> temp = first;
if (first.next == null) {
first = null;
last = null;
} else {
first = first.next;
first.prev = null;
}
System.out.println(temp.toString() + " is popped from the list");
}
}
public void removeLast() {
Node<T> temp = last;
if (!isEmpty()) {
if (first.next == null) {
first = null;
last = null;
} else {
last = last.prev;
last.next = null;
}
}
System.out.println(temp.toString() + " is popped from the list");
}
public static void main(String[] args) {
///////////////
DoublyLinkedList newList = new DoublyLinkedList();
for (int i = 0; i < 81; i++) {
HashSet<Integer> set = new HashSet<Integer>();
set.add(i);
newList.addFirst(set);
}
newList.displayList();
// start at 69
Node node = newList.getAt(12);
node.displayNode(); System.out.println();
//HOW TO IMPLEMENT UNLINK?
node.previous().setNext(node.next);
node.next().setPrevious(node.previous());
//The 2 statements above are equivalent to
//Node p = node.previous();
//Node n = node.next();
//p.setNext(n);
//n.setPrevious(p);
newList.displayList();
//HOW TO IMPLEMENT REVERT UNLINK?
node.previous().setNext(node);
node.next().setPrevious(node);
newList.displayList(); System.out.println();
///////////////
}
}