Einführung Algorithmen und Datenstrukturen

exemplarische Lösung der Aufgaben WS 02/03 von Markus Durzinsky. Zurück zur Algodat Hauptseite.

09. Übungsblatt

Aufgabe 41 - SimpleList - different elements

Zum Testen erstellen wir eine Liste, fügen ein paar Elemente hinzu und prüfen mittels contains, ob die Element, die hinzugefügt wurden auch noch drin sind.


  SimpleList list = new SimpleList();
  list.insertFirst(new Integer(5));
  list.insertFirst(new Integer(7));
  list.insertFirst(new Integer(9));
  System.out.println(list.toString());
  System.out.println("Liste enthaelt \"5\" "
    +(list.contains(new Integer(5))?"":"nicht"));
  System.out.println("Liste enthaelt \"6\" "
    +(list.contains(new Integer(6))?"":"nicht"));
  System.out.println("Es sind "
    +(list.allElementsDifferent()?"":"nicht ")+"alle Elemente verschieden");
  list.insertFirst(new Integer(7));
  System.out.println(list.toString());
  System.out.println("Nun sind "
    +(list.allElementsDifferent()?"":"nicht ")+"alle Elemente verschieden");

Die Ausgabe bestätigt die Richtigkeit der Algorithmen:


  SimpleList[9,7,5]
  Liste enthaelt "5" 
  Liste enthaelt "6" nicht
  Es sind alle Elemente verschieden
  SimpleList[7,9,7,5]
  Nun sind nicht alle Elemente verschieden

Die in SimpleList enthaltene toString()-Methode sieht so aus:


  public String toString() {
    String s = "";
    if (isEmpty()) s += "empty";
    else for (ListPosition pos = first;  pos != null;  pos = pos.getNext()) {
      s += pos.element().toString();
      if (pos.getNext() != null) {
        s += ",";
      }
    }
    return "SimpleList["+s+"]";
  }

Diese Methode wird auch in den folgenden Aufgaben hilfreich sein.

Aufgabe 42 - SimpleList - filter

Die Methode filter liefert ein neues Objekt der Klasse SimpleList zurück, welches als erstes erstellt werden muss. In diese Liste werden alle Elemente der eigenen Liste eingefügt, die folgende Bedingungen erfüllen:

  1. das Element muss eine Instanz der Klase Integer sein.

  2. der Wert des Integer-Objektes muss durch 5 teilbar sein


  public SimpleList filter() {
    SimpleList list = new SimpleList();
    for (ListPosition pos = first;  pos != null;  pos = pos.getNext()) {
      if (pos.element() instanceof Integer) {
        if (((Integer)pos.element()).intValue() % 5 == 0) {
          list.insertLast(pos.element());
        }
      }
    }
    return list;
  }

Zum Testen der ganzen Geschichte erweitern wir einfach das Beispiel aus Aufgabe 41 um folgende Zeilen:


  list.insertLast("ein String");
  list.insertLast(new Float(5));
  list.insertLast(new Integer(1084685));
  System.out.println(list);
  SimpleList filtered = list.filter();
  System.out.println(filtered);

Die Ausgabe


  SimpleList[7,9,7,5,ein String,5.0,1084685]
  SimpleList[5,1084685]

sollte auf dem Bildschirm erscheinen.

Aufgabe 43 - SimpleList - iterator

  1. Zuerst muss die innere Klasse ListIerator die Eigenschaft current von Typ ListPosition besitzen. Da es sich um eine innere Klasse handelt kann direkt auf die Eigenschaften von SimpleList zugegriffen werden, also auf first. Mit diesem Wert wird current im constructor initialisiert. Meine Implementierung von SimpleList stimmt aber nicht ganz mit der aus der Vorlesung überein (kein head bzw. tail Element). Deshalb sehen die beiden Methoden auch anders aus. current zeigt bei mit immer auf das aktuelle Element (was heist current wohl auf deutsch?), wogegen es nach Aufgabenstellung auf das Element davor zeigen sollte. Die Methode next() gibt demnach nicht den Inhalt des Nachfolgers, sondern den Inhalt von current zurück. Wir sind am Ende der Liste, wenn current den Wert null hat.

    
      public class SimpleList {
        ...
        private class ListIterator implements Iterator {
    
          private ListPosition current;
    
          public ListIterator() {
            current = first;
          }
    
          public boolean hasNext() {
            return current != null;
          }
    
          public Object next() {
            if (current == null) {
              return null;
            }
            Object o = current.element();
            current = current.getNext();
            return o;
          }
    
          public void remove() {
            throw new UnsupportedOperationException();
          }
    
        } // class ListIterator
      } // class SimpleList

    Das interface Iterator ist schon in der Java API enthalten (im Paket java.util). Dieses interface enthält aber noch die Methode remove(), die implementiert werden muss. Da unser Iterator diese Methode aber nicht unterstützen soll, geben wir eine Fehlermeldung aus. Es ist sicher sinnvoll eine Möglichkeit zu schaffen, den Iterator auch benutzen zu können. Dazu wird diese Methode der Klasse SimpleList hinzugefügt:

    
      public Iterator elements() {
        return new ListIterator();
      }
  2. Das hinzufügen aller Elemente einer Liste zu einer anderen Liste ist unter Verwendung des Iterators einfach:

    
      public void append(SimpleList list) {
        for (Iterator iter = list.elements();  iter.hasNext(); ) {
          insertLast(iter.next()));
        }
      }
  3. Für den Testrahmen erweitern wir das Beispiel aus Ausgabe 41/42 nochmals um:

    
      System.out.println(list);
      System.out.println(filtered);
      list.append(filtered);
      System.out.println(list);

    und erhalten die Ausgabe:

    
      SimpleList[7,9,7,5,ein String,5.0,1084685]
      SimpleList[5,1084685]
      SimpleList[7,9,7,5,ein String,5.0,1084685,5,1084685]

Aufgabe 44 - merge sort

Merge SortEs wäre doch sicherlich sinnvoll den in der vorherigen Aufgabe entwickelten ListIterator für diese Aufgabe zu verwenden. Aber mich fragt ja keiner, dann eben mit Vector. Diese Klasse befindet sich im Paket java.util und muss deshalb importiert werden.
Als erstes muss man sich die Funktionsweise von merge sort vorstellen. Am Anfang liegen zwei geordnette Felder a und b vor. Ist das erste Element von a kleiner als das von b wird es zu x hinzugefügt, ansonsten das andere. Die aktuelle Position (in dem Feld des kleineren Elements) rückt dann um eins weiter. Dies geschieht solange, bis eines der beiden Felder vollständig abgearbeitet wurde. Dann kann nämlich nicht mehr verglichen werden. Es muss nur noch der Rest des anderen Feldes hinzugefügt werden.

  public static Vector merge(Vector a, Vector b) {
    Vector x = new Vector();
    int pos1 = 0, pos2 = 0;
    while (pos1 < a.size() && pos2 < b.size()) {
      Comparable c1 = (Comparable)a.elementAt(pos1);
      Comparable c2 = (Comparable)b.elementAt(pos2);
      if (c1.compareTo(c2) < 0) {
        x.addElement(c1);
        pos1++;
      } else {
        x.addElement(c2);
        pos2++;
      }
    }
    while (pos1 < a.size()) {
      x.addElement(a.elementAt(pos1++));
    }
    while (pos2 < b.size()) {
      x.addElement(b.elementAt(pos2++));
    }
    return x;
  }
Zum Testen erstellt man einfach zwei Vektoren, fügt ein paar (sortierte) Integer-Objekte hinzu und übergibt das Ganze an merge.

  Vector a = new Vector();
  for (int i = 0;  i < 5;  i++) a.addElement(new Integer(new int[]{1,3,4,4,9}[i]));
  Vector b = new Vector();
  for (int i = 0;  i < 7;  i++) b.addElement(new Integer(new int[]{0,1,2,3,5,6,9}[i]));
  System.out.println("a="+a);
  System.out.println("b="+b);
  System.out.println("x="+merge(a, b));
Die Ausgabe entspricht dem Beispiel in der Abbildung:

  a=[1, 3, 4, 4, 9]
  b=[0, 1, 2, 3, 5, 6, 9]
  x=[0, 1, 1, 2, 3, 3, 4, 4, 5, 6, 9, 9]

Aufgabe 45 - selection sort

  1. Auch bei dieser Aufgabe hätte sich eine Liste besser gemacht. Nachdem ein Element ausgewählt wurde muss es gelöscht werden. Man könnte den Rest des Feldes um eins nach vorn schieben (der Algorithmus sieht dann fast so aus wie bubble sort) oder man überschreibt die Elemente mit null. Dann muss das Sortierverfahren immer testen, ob ein Element des Feldes null ist.
    Der Algorithmus erstellt erst ein neues Feld gleicher Länge in das die jeweils kleinsten Elemente von a der Reihe nach eingetragen werden. Um nun das kleinste Element zu suchen nehmen wir an, dass das erste auch das kleinste ist. Finden wir im Feld eines das kleiner ist, ändert sich die Position entsprechend. Die neue Position ist auch dann das Minimum, wenn das vorherige Minimum null war.
    
      public static Comparable[] selectionSort(Comparable[] a) {
        Comparable[] x = new Comparable[a.length];
        for (int pos = 0;  pos < a.length;  pos++) {
          int min = 0;
          for (int i = 1;  i < a.length;  i++) {
            if (a[min] == null) {
              min = i;
            } else if (a[i] != null && a[i].compareTo(a[min]) < 0) {
              min = i;
            }
          }
          x[pos] = a[min];
          a[min] = null;
        }
        return x;
      }
  2. Wie sollte nun die compareTo-Methode für Namen aussehen? Als erstes wird nach dem Familiennamen sortiert. Eine entsprechende compareTo-Methode ist in der Klasse String enthalten. Wenn die Familiennamen gleich sind, wird nach dem Vornamen sortiert. Ein Blick auf Aufgabenteil c zeigt, dass man es auch genau so machen sollte.
    
      public class Student implements Comparable {
    
        protected String firstname, surname;
    
        public Student(String s, String f) {
          surname = s;  firstname = f;
        }
    
        public String getFirstName() { return firstname; }
    
        public String getSurname() { return surname; }
    
        public int compareTo(Student stud) {
          int i = surname.compareTo(stud.surname);
          if (i != 0) return i;
          return firstname.compareTo(stud.firstname);
        }
    
        public int compareTo(Object o) {
          return compareTo((Student)o);
        }
    
        public String toString() {
          return surname+", "+firstname;
        }
    
      }
  3. Erst "erstellen" wir 5 Studenten :-)
    
      Comparable[] c = new Comparable[5];
      c[0] = new Student("Müller", "Peter");
      c[1] = new Student("Schmidt", "Katrin");
      c[2] = new Student("Meier", "Klaus");
      c[3] = new Student("Schulze", "Martin");
      c[4] = new Student("Schmidt", "Kar-Heinz");
    diese werden sortiert
    
      c = selectionSort(c);
    und schliesslich ausgegeben
    
      for (int i = 0;  i < c.length;  i++)
        System.out.println(c[i]);
    Das sortierte Feld:
    
      Meier, Klaus
      Müller, Peter
      Schmidt, Karl-Heinz
      Schmidt, Katrin
      Schulze, Martin
      

Erstellt von Markus Durzinsky, aktualisiert 12. Januar 2003
Für Fragen, Probleme oder Anregungen stehe ich gerne zur Verfügung