Java：如何实现 Dancing Links 算法（使用 DoublyLinkedLists）？

Question

我正在尝试用 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();

      ///////////////

这是 DoubleLinkedList 类：

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");
  }
}

Answer 1

我不熟悉 Knuth 的 Dancing Links 算法，但找到了这篇文章使它变得非常清晰。特别是我发现这非常有帮助：

\n\n

\n

Knuth 利用了双向链表的基本原理。\n 从列表中删除对象时，只需要两个操作：

\n\n

x.getRight().setLeft( x.getLeft() )
\n x.getLeft().setRight(> x.getRight() )

\n\n

但是，当将对象放回列表中时，只需执行相反的操作即可。

\n\n

x.getRight().setLeft( x )
\n x.getLeft().setRight( x )

\n\n

放回对象所需的只是对象本身，因为对象仍然指向列表中的元素。除非 x\xe2\x80\x99s 指针被改变，否则这个操作非常简单。

\n

\n\n

\n为了实现它，我添加了用于链接/取消链接的设置器。查看评论：\n

\n\n

import java.util.HashSet;\n\npublic class DoublyLinkedList<T> {\n\n      public Node<T> first = null;\n      public Node<T> last = null;\n\n      static class Node<T> {\n        private T data;\n        private Node<T> next;\n        private Node<T> prev;\n\n        public Node(T data) {\n          this.data = data;\n        }\n\n        public Node<T> get() {\n          return this;\n        }\n\n        public Node<T> set(Node<T> node) {\n          return node;\n        }\n\n        public Node<T> next() {\n          return next;\n        }\n\n        //add a setter\n        public  void setNext(Node<T> node) {\n              next = node;\n        }\n        public Node<T> previous() {\n          return prev;\n        }\n\n        //add a setter\n        public  void setPrevious(Node<T> node) {\n              prev = node;\n        }\n\n        public void displayNode() {\n          System.out.print(data + " ");\n        }\n\n        @Override\n        public String toString() {\n          return data.toString();\n        }\n      }\n\n      public void addFirst(T data) {\n        Node<T> newNode = new Node<T>(data);\n\n        if (isEmpty()) {\n          newNode.next = null;\n          newNode.prev = null;\n          first = newNode;\n          last = newNode;\n\n        } else {\n          first.prev = newNode;\n          newNode.next = first;\n          newNode.prev = null;\n          first = newNode;\n        }\n      }\n\n      public Node<T> getAt(int index) {\n        Node<T> current = first;\n        int i = 1;\n        while (i < index) {\n          current = current.next;\n          i++;\n        }\n        return current;\n      }\n\n      public boolean isEmpty() {\n        return (first == null);\n      }\n\n      public void displayList() {\n        Node<T> current = first;\n        while (current != null) {\n          current.displayNode();\n          current = current.next;\n        }\n        System.out.println();\n      }\n\n      public void removeFirst() {\n        if (!isEmpty()) {\n          Node<T> temp = first;\n\n          if (first.next == null) {\n            first = null;\n            last = null;\n          } else {\n            first = first.next;\n            first.prev = null;\n          }\n          System.out.println(temp.toString() + " is popped from the list");\n        }\n      }\n\n      public void removeLast() {\n        Node<T> temp = last;\n\n        if (!isEmpty()) {\n\n          if (first.next == null) {\n            first = null;\n            last = null;\n          } else {\n            last = last.prev;\n            last.next = null;\n          }\n        }\n        System.out.println(temp.toString() + " is popped from the list");\n      }\n\n      public static void main(String[] args) {\n\n          ///////////////\n\n          DoublyLinkedList newList = new DoublyLinkedList();\n\n          for (int i = 0; i < 81; i++) {\n\n              HashSet<Integer> set = new HashSet<Integer>();\n              set.add(i);\n              newList.addFirst(set);\n          }\n\n          newList.displayList();\n\n          // start at 69\n          Node node = newList.getAt(12);\n          node.displayNode(); System.out.println();\n\n          //HOW TO IMPLEMENT UNLINK?\n          node.previous().setNext(node.next);\n          node.next().setPrevious(node.previous());\n\n          //The 2 statements above are equivalent to\n          //Node p = node.previous();\n          //Node n = node.next();\n          //p.setNext(n);\n          //n.setPrevious(p);\n\n          newList.displayList();\n\n          //HOW TO IMPLEMENT REVERT UNLINK?\n          node.previous().setNext(node);\n          node.next().setPrevious(node);\n\n          newList.displayList(); System.out.println();\n\n          ///////////////\n      }\n    }\n

\n