homedukeAlgorithmen & Datenstrukturen mit Java: Mengen und Verzeichnisse mit sortierten verketteten Listen Prof. Dr. Uwe Schmidt FH Wedel
Kapitelübersicht
Listen mit einfach verketteten RingenInhaltsverzeichnisVerzeichnisse mit binären Suchbäumen
Beispielklasse für Mengen als verkettete Listen

Mengen und Verzeichnisse mit sortierten verketteten Listen

weiter
weiter

Schnittstelle
Einfache Variante für Mengen in Java: interface Set
 
package ds.interfaces;
 
/** Simple interface for sets */
 
import java.util.Iterator;
 
import ds.util.Invariant;
 
import ds.util.E;  // example class for elements
 
public
    interface Set
    extends Iterable<E>,
            Invariant {
 
    boolean isEmpty();
    boolean member(E e);
    int     size();
    E       findMin();
    E       findMax();
    Set     insert(E e);
    Set     remove(E e);
    Set     union(Set m2);
    Set     difference(Set m2);
    Set     intersect(Set m2);
    Set     copy();
 
    // inherited
 
    // Iterator<E> iterator();
    // boolean inv();
}
Hilfsklassen
E
für die Elemente
weiter
Variante
von einfach verketteten Listen
Ziele
1.
Suche effizienter als bei unsortierten Listen
2.
Einfügen effizienter als bei unsortierten Listen
3.
Mengenoperationen Vereinigung, Durchschnitt, Differenz, ..., sehr viel effizienter als bei unsortierten Listen
weiter
Idee
1.
durch Sortierung der Elemente früherer Abbruch bei der Suche nach Elementen, die nicht in der Menge enthalten sind
2.
durch Sortierung einfacheres und schnelleres Mischen zweier Listen bei Mengenoperationen
3.
Datenstruktur unverändert zur einfach verketteten Liste
weiter
Klassenstruktur
public abstract
    class OrderedList
    implements Set {
 
    ...
 
    private static final
        class Empty
        extends OrderedList {
        ...
    }
 
    private static final
        class Node
        extends OrderedList {
 
        final E           info;
        final OrderedList next;
        ...
    }
}
Konstruktor-Funktionen
public
  static OrderedList empty() {
    return
        EMPTY;
}
 
public static
  OrderedList singleton(E e) {
    return
        EMPTY.cons(e);
}
 
protected
    Node cons(E e) {
    return
        new Node(e, this);
}
?
Wird eine Invariante zur Beschreibung der Konsistenz der Datenstruktur benötigt?
weiter
Hilfsklasse
für die Konsistenz-Überprüfung
 
package ds.util;
 
/** interface for checking internal consistency
    of an object
*/
public interface Invariant {
    boolean inv();
}
weiter
Implementierung
wird in der Vorlesung entwickelt
Erweiterung
Schnittstelle
Einfache Variante für Schlüssel-Wert-Paare (Maps) in Java: interface Map
 
package ds.interfaces;
 
/** Simple interface for maps
 */
 
import java.util.Iterator;
 
import ds.util.Invariant;
import ds.util.Function2;
 
import ds.util.K;  // example class for keys
import ds.util.V;  // example class for values
import ds.util.KV; // key value pair
 
public
    interface Map
    extends Iterable<KV>,
            Invariant {
 
    boolean isEmpty();
    boolean member(K k);
    V       lookup(K k);
    int     size();
    KV      findMin();
    KV      findMax();
    Map     insert(K k, V v);
    Map     remove(K k);
    Map     union(Map m2);
    Map     difference(Map m2);
    Map     unionWith(Function2<V,V,V> op, Map m2);
    Map     differenceWith(Function2<V,V,V> op, Map m2);
    Map     copy();
 
    // inherited
 
    // public Iterator<KV> iterator();
    // public inv();
}
Hilfsklassen
K
für die Schlüssel
V
für die Werte
KV
für die Schlüssel-Wert-Paare
weiter
SeitenanfangKapitelübersicht
Listen mit einfach verketteten RingenInhaltsverzeichnisVerzeichnisse mit binären Suchbäumen
Beispielklasse für Mengen als verkettete Listen
Letzte Änderung: 20.11.2015
© Prof. Dr. Uwe Schmidt
Prof. Dr. Uwe Schmidt FH Wedel