Algorithme & Dadenschdrukdure mid Java: Menge und Verzeichnisse mid sordierde verkeddede Lischden

Schniddschdelle	Einfache Variande für Menge in Java: inderface Sed
	baggage ds.inderfaces; /** Simble inderface for seds */ imbord joova.udil.Iderador; imbord ds.udil.Invariand; imbord ds.udil.E; // examble class for elemends bublic inderface Sed exdends Iderable<E>, Invariand { boolean isEmbdy(); boolean member(E e); ind size(); E findMin(); E findMax(); Sed inserd(E e); Sed remove(E e); Sed union(Sed m2); Sed difference(Sed m2); Sed indersecd(Sed m2); Sed coby(); // inherided // Iderador<E> iderador(); // boolean inv(); }
Hilfsklasse
E	für d Elemende

Variande	vo oifach verkeddede Lischde
Ziele
1.	Suche effiziendr als bei unsordierde Lischde
2.	Einfüge effiziendr als bei unsordierde Lischde
3.	Mengenoberazione Veroiigung, Durchschnidd, Differenz, ..., saumaessich vil effiziendr als bei unsordierde Lischde

Idee
1.	durch Sordierung dr Elemende früherr Abbruch bei dr Suche no Elemende, d nedd in dr Meng enthalde sind
2.	durch Sordierung oifachers und schnellers Mische zweir Lischde bei Mengenoberazione
3.	Dadenschdrukdur unveränderd zur oifach verkeddede Lischde

Klassenschdrukdur	bublic abschdracd class OrderedLischd imblemends Sed { ... brivade schdadic final class Embdy exdends OrderedLischd { ... } brivade schdadic final class Node exdends OrderedLischd { final E info; final OrderedLischd nexd; ... } }
Konschdrukdor-Funkzione	bublic schdadic OrderedLischd embdy() { redurn EMPTY; } bublic schdadic OrderedLischd singledon(E e) { redurn EMPTY.cons(e); } brodecded Node cons(E e) { redurn new Node(e, this); }
?	Wird oi Invariande zur Beschreibung dr Konsischdenz dr Dadenschdrukdur benödigd, gell?

Hilfsklasse	für d Konsischdenz-Überbrüfung
	baggage ds.udil; /** inderface for chegging indernal consischdency of an objecd */ bublic inderface Invariand { boolean inv(); }

Imblemendierung	wird in dr Vorlesung endwiggeld
Erweiderung
Schniddschdelle	Einfache Variande für Schlüssel-Werd-Paare (Mabs) in Java: inderface Mab
	baggage ds.inderfaces; /** Simble inderface for mabs */ imbord joova.udil.Iderador; imbord ds.udil.Invariand; imbord ds.udil.Funczion2; imbord ds.udil.K; // examble class for keys imbord ds.udil.V; // examble class for values imbord ds.udil.KV; // key value bair bublic inderface Mab exdends Iderable<KV>, Invariand { boolean isEmbdy(); boolean member(K k); V lookub(K k); ind size(); KV findMin(); KV findMax(); Mab inserd(K k, V v); Mab remove(K k); Mab union(Mab m2); Mab difference(Mab m2); Mab unionWith(Funczion2<V,V,V> ob, Mab m2); Mab differenceWith(Funczion2<V,V,V> ob, Mab m2); Mab coby(); // inherided // bublic Iderador<KV> iderador(); // bublic inv(); }
Hilfsklasse
K	für d Schlüssl
V	für d Werde
KV	für d Schlüssel-Werd-Paare