/******************************************************************************************* * AdressenListeBBaum.java * * Uebungen zur VL PI1, WS99/2000, Prof. Effelsberg, Blatt9 Aufgabe 2 * * Implementiert eine (einfache) Adressverwaltung mit Batch-Verarbeitung * * Als zugrundliegende Datenstruktur wird ein Binaerbaum verwendet * * (w) Christian Dengler, Tutor Gruppe 6 * *******************************************************************************************/ import java.util.StringTokenizer; import java.io.*; /******************************************************************************************* * Klasse AdressElement * * Diese Klasse dient zum Speichern einer einzelen Adresse und wurde mit einigen * * Modifikation von Blatt 7 Aufgabe 1 uebernommen * *******************************************************************************************/ class AdressElement { private String name; private String strasse; private String ort; private final int anzahlFelder; private final String felder[]; // Namen der Felder public AdressElement() { this.name = ""; this.strasse = ""; this.ort = ""; this.anzahlFelder = 3; this.felder = new String[this.anzahlFelder]; this.felder[0] = "Name"; this.felder[1] = "Strasse"; this.felder[2] = "Ort"; } public void setzeAdresse( String name, String strasse, String ort ) { this.name = name; this.strasse = strasse; this.ort = ort; } public int liesAnzahlFelder() { return this.anzahlFelder; } public String toString() { String s = name + ";" + strasse + ";" + ort; return s; } // Ergaenzte Methoden um einzelne Adressparameter auszulesen public String liesName() { return this.name; } public String liesStrasse() { return this.strasse; } public String liesOrt() { return this.ort; } } /******************************************************************************************* * Klasse BaumElement * * Repräsentiert einen Knoten im verwendeten Binaerbaum * *******************************************************************************************/ class BaumElement { public BaumElement linkesKind = null; //Verkettung mit den public BaumElement rechtesKind = null; //nachfolgenden Elementen public AdressElement adresse = null; //Adressdaten } /******************************************************************************************* * Klasse AdressenListeBBaum * * Startklasse des Programms, implementiert die eigentliche Verwaltung auf Binarbaumbasis * *******************************************************************************************/ public class AdressenListeBBaum { private static BaumElement wurzel = null; //Sortiertes Einfuegen einer neuen Adresse in den Baum private static void Einfuegen(String name, String strasse, String ort) { BaumElement neuerKnoten = new BaumElement(); //einen neuen Knoten erzeugen neuerKnoten.adresse = new AdressElement(); //ebenso zugehoerige Adresse neuerKnoten.adresse.setzeAdresse(name, strasse, ort); //Adresse zuweisen boolean fertig = false; boolean linksrum = false; //zum merken der Richtung von der man vom Vorgaenger kam BaumElement aktPos = wurzel; BaumElement vorherPos = wurzel; if (wurzel == null) { // Baum leer? fertig = true; wurzel = neuerKnoten; //neuen Knoten als Wurzel einfuegen } while (!fertig) { //neuer Knoten noch nicht eingefuegt if (aktPos == null) { //freier Platz an einem Blatt? if (linksrum) vorherPos.linkesKind = neuerKnoten; else vorherPos.rechtesKind = neuerKnoten; //dort einhaengen break; //Schleife verlassen } if (name.compareTo(aktPos.adresse.liesName()) <= 0) { //lexikographisch <= linksrum = true; vorherPos = aktPos; //merke die alte Pos aktPos = aktPos.linkesKind; //gehe nach links } else { //lexikographisch > linksrum = false; vorherPos = aktPos; //merke die alte Pos aktPos = aktPos.rechtesKind; //gehe nach rechts } } //while } //Einfuegen //gibt die Adressliste in aufsteigender Reihenfolge aus //Aufruf mit wurzel als Parameter //in-order Durchforstung, d.h. Ausgabe eines Elements steht zwischen linken und rechtem Abstieg private static void Ausgabe(BaumElement startKnoten) { if ( (startKnoten == wurzel) && (wurzel == null) ) { //Fall leerer Baum System.out.println("LEER"); return; } if (startKnoten.linkesKind != null) Ausgabe(startKnoten.linkesKind); System.out.println(startKnoten.adresse.toString()); if (startKnoten.rechtesKind != null) Ausgabe(startKnoten.rechtesKind); } //sucht Adressen anhand eines vorgegebenen Namens //mehrfach vorkommende Namen werden auch mehrfach gefunden private static void Suche(String name) { int anzahlGefunden = 0; //zaelt passende Eintraege BaumElement aktPos = wurzel; while (aktPos != null) { //solange durch Baum hangeln, bis an Blatt if (name.equals(aktPos.adresse.liesName())) { //Name passt? System.out.println(aktPos.adresse.toString()); anzahlGefunden++; } if (name.compareTo(aktPos.adresse.liesName()) <= 0) //lexikographisch <= aktPos = aktPos.linkesKind; //dann gehe links else aktPos = aktPos.rechtesKind; //ansonsten rechts } //while if (anzahlGefunden == 0) System.out.println("LEER"); //Name nicht gefunden } //Loescht Adressen mit vorgegebenem Namen //mehrfach vorkommende Namen werden alle geloescht private static void Loesche(String name) { BaumElement loeschElement = wurzel; //Ref. fuer zu loeschendes Element BaumElement vorgElement = wurzel; //Ref. fuer dessen Vorgaenger boolean linksrum = false; //merke Richtung von Vorg. zum LoeschElement BaumElement linkerTeilbaum = null; //Ref. auf linken Teilbaum des LoeschElements BaumElement rechterTeilbaum = null; //Ref. auf rechten Teilbaum des LoeschElements BaumElement hilfsRef = null; //Ref. zum durchhangeln while (loeschElement != null) { //Baum durchsuchen if (name.equals(loeschElement.adresse.liesName())){ //LoeschElement gefunden? linkerTeilbaum = loeschElement.linkesKind; //linken und rechten rechterTeilbaum = loeschElement.rechtesKind; //Teilbaum merken if (rechterTeilbaum != null) { //rechter Teilbaum vorhanden? hilfsRef = rechterTeilbaum; while (hilfsRef.linkesKind != null) //suche Blatt ganz unten links im hilfsRef = hilfsRef.linkesKind; //rechten Teilbaum hilfsRef.linkesKind = linkerTeilbaum; //und haenge dort linken Teilbaum an hilfsRef = rechterTeilbaum; } else hilfsRef = linkerTeilbaum; //falls kein rechter Teilbaum if (loeschElement == wurzel) wurzel = hilfsRef; //setze wurzel neu, wenn wurzel geloescht wird else { if (linksrum) vorgElement.linkesKind = hilfsRef; //Zeiger umbiegen und somit else vorgElement.rechtesKind = hilfsRef; //Ref. auf LoeschElement fallen lassen } //->wird später vom Garbage-Collector elimiert loeschElement = hilfsRef; //Ref. zum weitersuchen restaurieren continue; //nächste Schleifen-Iteration } //if (name.equals... if (name.compareTo(loeschElement.adresse.liesName()) <= 0) { //lexikographisch <= vorgElement = loeschElement; loeschElement = loeschElement.linkesKind; //gehe nach links linksrum = true; } else { //lexikographisch > vorgElement = loeschElement; loeschElement = loeschElement.rechtesKind; //gehe nach rechts linksrum = false; } } //while } public static void main(String[] args) { //Lese Name der Kommandodatei von Kommandozeile final String filename; try { filename = args[0]; } catch (IndexOutOfBoundsException ioobe) { //keine Kommandodatei angeben System.out.println("Keine Kommandodatei!"); return; } //Oeffne Kommandodatei FileReader fr; BufferedReader in; try { fr = new FileReader(filename); in = new BufferedReader(fr); } catch (FileNotFoundException fnfe) { //Datei nicht gefunden System.out.println("Kommandodatei " + filename + " nicht gefunden!"); return; } try { StringTokenizer st; String zeile; while ( ( zeile = in.readLine() ) != null) { //noch Kommandos vorhanden? st = new StringTokenizer(zeile); int anzTokens = st.countTokens(); //Anzahl der Tokens in dieser Zeile String[] tokens = new String[anzTokens]; for (int i = 0; i < anzTokens; i++) { //Tokens einlesen tokens[i] = st.nextToken(); } //Kommandos ausfuehren if (tokens[0].equals("add")) Einfuegen(tokens[1], tokens[2], tokens[3]); if (tokens[0].equals("print")) Ausgabe(wurzel); if (tokens[0].equals("search")) Suche(tokens[1]); if (tokens[0].equals("delete")) Loesche(tokens[1]); } //while } //try catch (IOException ioe) { System.out.println(ioe.getMessage()); return; } } //main }