Java: Wie implementiert man den Dancing Links Algorithmus (mit DoublyLinkedLists)?

Question

Ich versuche Knuths Dancing Links Algorithmus in Java zu implementieren.

Nach Knuth, wenn x ein Knoten ist, kann ich total einen Knoten durch die folgenden Operationen in C entkoppeln:

L[R[x]]<-L[x] 
R[L[x]]<-R[x] 

Und die Entkettung zufällt von:

L[R[x]]<-x 
R[L[x]]<-x 

Was ich bin Falsch in meiner Hauptmethode zu tun?

Wie implementieren Sie das Aufheben der Verknüpfung und das Zurücksetzen in Java?

Hier ist meine Hauptmethode:

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

     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(); 

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

Hier ist die DoublyLinkedList Klasse:

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

Ich bin nicht vertraut mit Knuths Tanzen Verbindungen Algorithmus, fand aber this article, die es ruhig deutlich gemacht. Insbesondere fand ich das sehr hilfreich:

Knuth nutzt ein Grundprinzip doppelt verknüpfter Listen. Wenn ein Objekt aus einer Liste zu entfernen, sind nur zwei Operationen erforderlich:..

x.getRight() SetLeft (x.getLeft())
x.getLeft() Setright (> x.getRight())

Wenn jedoch das Objekt wieder in die Liste eingefügt wird, müssen alle die umgekehrte Operation ausführen.

x.getRight(). SetLeft (x)
x.getLeft(). Setright (x)

Alle, die es benötigt, um das Objekt zu setzen ist das Objekt selbst, weil das Objekt noch zeigt auf Elemente innerhalb der Liste. Wenn die Zeiger von x nicht geändert sind, ist diese Operation sehr einfach.

zu ihrer Umsetzung habe ich Setter für die Verknüpfung/Entkettung. Siehe Anmerkungen:

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(); 

      /////////////// 
     } 
    }