c2b_default

Objektorientierte Programmierung OOP

KE6 Algorithmus und Datenstrukturen

KE6 Algorithmus und Datenstrukturen

106
5.0 (1)
S. H.
Lernen
S. H.
Diese Lernkarten behandeln fortgeschrittene Konzepte der objektorientierten Programmierung (OOP) auf Universitätsniveau, mit Fokus auf Datenstrukturen wie Bäume und Listen. Sie erklären Methoden zur Suche und Manipulation von Knoten, Elementen und Feldern, sowie die Implementierung von Suchstrategien wie Breiten- und Tiefensuche. Die Karteikarten sind besonders nützlich für Studierende der Informatik, die ihre Kenntnisse in der Programmierung vertiefen und praktische Anwendungen von OOP-Konzepten verstehen möchten.
Karten
106
Lernende
8
Sprache
Deutsch
Kategorie
Informatik
Stufe
Universität
Erstellt / Aktualisiert
15.01.2013 / 18.05.2022
  • 1  / 106

Lernkarten

Was passiert, wenn die Methode summeRekursiv() mit negativen Werten aufgerufen wird? Wie kann dieses Problem gelöst werden?

 

Es tritt ein StackOverflowError auf. Um dies zu verhindern, kann bei negativen Werten entweder eineIllegalArgumentException geworfen oder die Abfrage n == 0 durch n <= 0 ersetzt werden.

 

 

Implementieren Sie eine Methode fakultaetIterativ    (int n), die iterativ die Fakultät berechnet und eine MethodefakultaetRekursiv(int n), die die Fakultät rekursiv berechnet. Die Methoden sollen dabei nur Werte  akzeptieren.

 

  int fakultaetIterativ(int n) {        // ungültige Werte abfangen        if (n < 0) {            throw new IllegalArgumentException();        }        // Ergebnis initialisieren        int erg = 1;        for (int i = 2; i <= n; i++) {            erg *= i;        }        return erg;    }    int fakultaetRekursiv(int n) {        // ungültige Werte abfangen        if (n < 0) {            throw new IllegalArgumentException();        }        // Basisfall        if (n == 0) {            return 1;        }        // rekursiver Aufruf        return n * fakultaetRekursiv(n - 1);    }

Begründen Sie, warum die Lösung für fakultaetRekursiv() konvergiert.

 

 

 

In jedem Schritt wird n um eins verringert. Somit nähert sich n immer weiter an den Basisfall 0 an.

 

 

Schreiben Sie die Methode double power(int p, int n), die für zwei ganze Zahlen  und  rekursiv den Wert  berechnet. Testen Sie Ihr Programm und vergleichen Sie es mit der Lösung von Selbsttestaufgabe 14.1-2, die eine iterative Variante aufzeigt.

 

 

public double power(int p, int n) {        if (n < 0) {            return 1.0 / power(p, -n);        }        if (n == 0) {            return 1;        }        return p * power(p, n - 1);    }

Melde dich an, um Bilder anzusehen.

Berechnen Sie alle Fibonacci-Zahlen bis und schreiben Sie die passenen Methode.

0, 1, 1, 2, 3, 5, 8, 13, 21

 

    long fibRekursiv(int n) {        if (n < 0) {            throw new IllegalArgumentException();        }        // Basisfall: n ist 0 oder 1        if (n == 0 || n == 1) {            return n;        }        // sonst: rekursiver Aufruf        return fibRekursiv(n - 1) + fibRekursiv(n - 2);    }
 

 

Implementieren Sie eine iterative Lösung für die Berechnung der Fibonacci-Zahlen in der Methode long fibIterativ(int n).

 

    long fibIterativ(int n) {        if (n < 0) {            throw new IllegalArgumentException();        }        // Basisfall: n ist 0 oder 1        if (n == 0 || n == 1) {            return n;        }        // die ersten beiden Zahlen        int a = 0; // fib(0)        int b = 1; // fib(1)        // berechne die nächsten Zahlen        for (int i = 2; i <= n; i++) {            // fib(i) = fib(i - 1) + fib(i - 2);            int temp = a + b;            // Werte für nächste Berechnung            // speichern            a = b;            b = temp;        }        return b;     }
Melde dich an, um Bilder anzusehen.

Implementieren Sie eine Methode long zufallszahl(int n), die rekursiv f(n) berechnet. Implementieren Sie außerdem eine Methode void gebeZufallszahlenAus(), die die Pseudozufallszahlen f(5) bis einschließlich f(30) ausgibt.

  long zufallszahl(int n) {

        // Basisfall n < 3        if (n < 3) {            return n + 1;        }        // rekursive Aufrufe        long f1 = zufallszahl(n - 1);        long f2 = zufallszahl(n - 2);        long f3 = zufallszahl(n - 3);        // berechne Ergebnis        return 1 + (((f1 - f2) * f3) % 100);    }    void gebeZufallszahlenAus() {        for (int i = 5; i < 30; i++) {            System.out.println(zufallszahl(i));        }    }

Ein Palindrom ist ein Wort, dass sowohl vorwärts als auch rückwärts gelesen das gleiche ist.

Implementieren Sie die Methode boolean istPalindromIterativ (String s), die iterativ prüft ob es sich bei der Zeichenkette um ein Palindrom handelt.

 

    boolean istPalindromIterativ(String s) {        int laenge = s.length();        // betrachte erste Haelfte des Wortes        for (int i = 0; i < s.length() / 2; i++) {            // und prüfe ob korrespondierendes            // Zeichen identisch ist            if (s.charAt(i) != s.charAt(laenge - 1 - i)) {                return false;            }        }        // alle Zeichen passen        return true;    }

Der Begriff Palindrom lässt sich auch rekursiv definieren. Ein Wort aus einem oder keinen Zeichen ist immer ein Palindrom. Ein längeres Wort ist dann ein Palindrom, wenn der erste und letzte Buchstabe identisch sind und der Rest der Zeichenkette, also ohne den ersten und letzten Buchstaben, auch ein Palindrom ist.

Implementieren Sie die Methode boolean istPalindromRekursiv (String s), die mit Hilfe der rekursiven Definition prüft, ob es sich bei der Zeichenkette um ein Palindrom handelt.

 

    boolean istPalindromRekursiv(String s) {        // Basisfall        if (s.length() <= 1) {            return true;        }        // erstes und letztes Zeichen vergleichen        if (s.charAt(0) != s.charAt(s.length() - 1)) {            return false;        }        return istPalindromRekursiv(s.substring(                                        1, s.length() - 1));    }

Führen Sie auf dem folgenden Feld eine binäre und eine lineare Suche nach dem Element 38 aus. Wie viele Vergleiche benötigen Sie, bis Sie das Element gefunden haben?

int[] y = {3, 7, 14, 16, 18, 22, 27, 29, 30, 34, 38, 40, 50};

 

 

Bei der linearen Suche sind genau 11 Vergleiche nötig, bis der Wert gefunden wird.

Bei der binären Suche werden die folgenden Schritte und Vergleiche durchgeführt: start =  0 und ende = 12 => mitte =  6 => Vergleich mit 27     start =  7 und ende = 12 => mitte =  9 => Vergleich mit 34     start = 10 und ende = 12 => mitte = 11 => Vergleich mit 40     start = 10 und ende = 10 => Basisfall  => Vergleich mit 38

Es finden insgesamt 4 Vergleiche mit den Werten 27, 34, 40 und 38 statt.

Ergänzen Sie die Klasse Binaersucher um eine Methode boolean istEnthalten(String s, String[] feld), die mit Hilfe einer binären Suche prüft, ob die Zeichenkette in dem Feld enthalten ist. Sie können sich dabei Hilfsmethoden definieren. Hilfsmethoden sollten nach dem Geheimnisprinzip gekapselt sein.

 

// wir gehen von einem sortierten Feld aus    boolean istEnthalten(String s, String[] feld,                                            int start, int ende) {        // Basisfall: Bereich enthält maximal 2 Elemente        if (ende - start <= 1) {            return feld[start].equals(s) || feld[ende].equals(s);        }        // sonst: rekursive Aufteilung        // Mitte bestimmen        int mitte = start + (ende - start) / 2;        System.out.println(mitte + " " + feld[mitte]);        if (feld[mitte].equals(s)) {            // wert gefunden            return true;        }        if (feld[mitte].compareTo(s) > 0) {            // in linker Hälfte suchen            return istEnthalten(s, feld, start, mitte - 1);        } else {            // in rechter Hälfte suchen            return istEnthalten(s, feld, mitte + 1, ende);        }    }

Melde dich an, um Bilder anzusehen.

Quicksort Teil 1:

Für das Sortieren von Feldern gibt es beispielsweise den Algorithmus Quicksort. Bei diesem Verfahren wird zufällig ein Element des Feldes als sogenanntes Pivotelement ausgewählt. Anschließend werden die Elemente des Feldes aufgeteilt. In dem einen Teil befinden sich alle Elemente, die kleiner als das Pivotelement sind und im anderen alle, die größer als das Pivotelement sind. Anschließend werden beide Teile wiederum mit dem gleichen Verfahren aufgeteilt. Bei Teilen mit maximal zwei Elementen kann die Sortierung dann direkt vorgenommen werden. Anschließend ist das gesamte Feld sortiert.Abb.  34-6 veranschaulicht dieses Verfahren.

 

void quicksort(int[] feld, int start, int ende) {        // Basisfall: leeres Feld        if (ende < start) {            return;                    }        // Basisfall: maximal 2 Elemente,        if (ende - start <= 1) {            // wenn nötig die beiden Werte vertauschen            if (feld[start] > feld[ende]) {                int temp = feld[start];                feld[start] = feld[ende];                feld[ende] = temp;            }            return;        }        // Feld aufteilen        int grenze = aufteilen(feld, start, ende);        // linken Teil (ohne Pivot) Sortieren        quicksort(feld, start, grenze - 1);        // rechten Teil (ohne Pivot) Sortieren        quicksort(feld, grenze + 1, ende);    }

 

Quicksort Teil 2

 

// teilt die Elemente auf und liefert die// Position des Pivotelements zurückint aufteilen(int[] feld, int start, int ende) {    // Index von links    int l = start + 1;    // Index von rechts    int r = ende;     // Pivotelement    int pivot = feld[start];    // Umsortierung    while (l < r) {        // erstes Element größer als Pivot finden        while(feld[l] <= pivot && l < r) {            l++;        }
        // erstes Element kleiner als Pivot finden        while(feld[r] > pivot && l < r) {            r--;        }        // Elemente vertauschen        int temp = feld[l];        feld[l] = feld[r];        feld[r] = temp;                    }    // Indizes haben sich getroffen    // prüfen ob Grenze korrekt    if(feld[l] > pivot) {        // Grenze anpassen        l--;    }    // Grenze gefunden, Pivot entsprechend vertauschen    feld[start] = feld[l];    feld[l] = pivot;      return l;}

Versuchen Sie, die einzelnen Schritte in der Implementierung mit Hilfe des folgenden Beispielaufrufs nachzuvollziehen.

int[] x = {12,2,6,1,8,34,10,7,20};quicksort(feld, 0, feld.length - 1);
Melde dich an, um Bilder anzusehen.

Antwort siehe Abl.

Ein weiteres rekursives Sortierverfahren ist das „Sortieren durch Verschmelzen“ (engl. merge sort). Bei diesem Verfahren wird im Gegensatz zu Quicksort nicht beim Aufteilen sortiert, sondern erst wieder beim Zusammenfügen. Das Feld wird in zwei möglichst gleich große Hälften aufgeteilt, die nach dem gleichen Verfahren sortiert werden. Die beiden sortierten Teilfelder werden nun zu einer sortierten Gesamtliste vereint, indem die beiden ersten Elemente verglichen und das kleinere aus seinem Teil entnommen und in das Zielfeld übernommen wird. Das wird solange fortgesetzt, bis beide Teilfelder leer sind. Abb.  34-9 veranschaulicht die Aufteilung und Verschmelzung der Felder.

Melde dich an, um Bilder anzusehen.

Sortieren durch Verschmelzen (merge sort)

Versuchen Sie, das folgende Feld mit Hilfe des Algorithmus „Sortieren durch Verschmelzen“ von Hand zu sortieren.

int[] x = {12,2,6,1,8,34,10,7,20};
Melde dich an, um Bilder anzusehen.

Sortieren eines Beispielfeldes mit Sortieren durch Verschmelzen

Was zeichnet lineare Datenstrukturen aus?

Lineare Datenstrukturen  zeichnen sich dadurch aus, dass die Elemente oder Knoten der Datenkollektion in einer Folge angeordnet sind. 

Wie nennt man den Informationstragenden Bestandteil eines Elements, in einer linearen Datenstruktur?

Den informationstragenden Bestandteil eines Elements nennen wir Eintrag. Eine lineare Datenstruktur kann auch leer sein. Einzelne Einträge können mehrfach in einer linearen Datenstruktur vorkommen.

Nennen Sie typische lineare Datenstrukturen und deren charakteristischen Eigenschaften.

Als typische lineare Datenstrukturen sind Felder bekannt.  Charakteristisch für Felder ist der wahlfreie Zugriff (engl. random access), den wir auf die einzelnen Feldelemente haben. Beim wahlfreien Zugriff ist jedes beliebige Element einer Kollektion mit dem gleichen Aufwand (z. B. Zugriffszeit) erreichbar.

Welche Zugriffs Möglichkeiten gibt es bei linearen Datenstrukturen?

 

Die Elemente einer linearen Datenstruktur können entweder durch einen wahlfreien Zugriff oder durch einen sequenziellen Zugriff (engl. sequential access) erreicht werden. Beim sequenziellen Zugriff wird auf die Elemente einer Kollektion in einer vorbestimmten, geordneten Abfolge zugegriffen, so dass der Aufwand für verschiedene Elemente einer Kollektion variiert.

Welche lineare Datenstrukturen gibt es noch, neben dem Feld?

Weitere linearen Datenstrukturen sind der Stapel (engl. stack) und die Warteschlange (engl. queue). Sie erlauben keinen wahlfreien, sondern nur einen sequenziellen Zugriff.

Welche charakteristische Eigenschaft hat die Datenstruktur Stapel?

Charakteristisch für die Datenstruktur Stapel ist, dass immer das zuletzt hinzugefügte Element als erstes vom Stapel entnommen werden muss. Diese Eigenschaft ist unter dem Namen Last In First Out (LIFO) bekannt.

Nach welchen Zugriffsverfahren arbeitet die Datenstruktur Warteschlange?

Die Warteschlange hingegen arbeitet nach dem „First In First Out“-Prinzip (FIFO). Es kann immer das Element aus der Warteschlange entnommen werden, das als erstes eingefügt worden ist, sich also schon am längsten in der Warteschlange befindet.

Welche Nachteile haben Felder, neben den vielen Vorteilen wie einfache Werte oder Objektreferenzen zu organisieren und der wahlfreien Zugriffs Möglichkeiten? 

Das die Größe eines Feldes bei seiner Erzeugung festgelegt wird und während der Lebensdauer eines Feldobjekts nicht mehr geändert werden kann.

Mit welcher Struktur können wir z.B. Listen von Rechnungen einfach wachsen lassen, indem wir am Ende oder vor den Anfang der Liste oder aber an beliebiger Stelle zwischen zwei vorhandenen Elementen ein neues hinzufügen, und wir können die Liste schrumpfen lassen, indem wir einfach ein Element streichen.

Ein Abbild dieser Struktur in Programmen ist die verkettete Liste (engl. linked list). Eine verkettete Liste ist die einfachste Form einer Sammlung von Datenobjekten, denen eine lineare Ordnung aufgeprägt ist.

Welche Eigenschaften haben verkettet Listen?

Listen sind dynamische Datenstrukturen, die folgende  Eigenschaften haben:

1. Die einzelnen Knoten (engl. node) oder Elemente der Liste sind geordnet.

2. Listen können beliebig lang werden.

3. Listen können auch leer sein.

4. Man kann Knoten aus einer Liste löschen oder neue Knoten hinzufügen, ohne die  bisherigen Knoten umordnen zu müssen.

Auf was müssen Sie bei verketteten Listen noch achten?

Eine Liste verwendet Speicherplatz im Verhältnis zur Anzahl ihrer aktuellen Knoten. Auf die Listenknoten kann nur sequenziell zugegriffen werden. Listen verwendet man besser für Datenkollektionen, deren Größe man nicht vorherbestimmen kann und die sich häufig ändern.

Definieren Sie Verkettete Liste.

Eine einfach verkettete Liste ist eine (möglicherweise leere) Menge von Knoten, wobei jeder Knoten einen Eintrag und einen Verweis auf den nächsten Knoten enthält.

Der erste Knoten einer Liste wird Kopf (engl. head), der letzte wird Schwanz (engl. tail) genannt. Der Verweis des letzten Elements hat, außer bei einer zirkulären Liste, den Wert null.

Wo für stehen die Attribute entry und next?

 

public class ListNode {     

       private int entry;    

       private ListNode next;

}

Melde dich an, um Bilder anzusehen.

Das Attribut entry dient zur Speicherung des Eintrags, der in unserer Knoten-Implementierung vom Typ int ist. Das Attribut next stellt eine Referenz auf den nachfolgenden Listenknoten dar und zeigt schematisch einen Knoten mit einem Eintrag und einer Referenz auf einen weiteren Knoten.

Erstellen Sie für die verkettet Liste, eine Klasse ListNode inkl. einer Methode für die Ausgabe des Listeneintrag.

public class ListNode {    private int entry;    private ListNode next;        public ListNode(int value) {        this(value, null);    }        public ListNode(int value, ListNode nextNode) {        this.entry = value;        this.next = nextNode;    }        public void setEntry(int value) {        this.entry = value;    }        public void setNext(ListNode nextNode) {        this.next = nextNode;    }        public int getEntry() {        return this.entry;    }    public ListNode getNext() {        return this.next;    }
 public void print() {        System.out.print(this.entry);    }}
 

Erstellen Sie den ersten Entwurf für die LinkedList Methode, die wir im laufe weiter entwickeln werden.

 

public class LinkedList {    private ListNode head;
    public LinkedList() {        this.head = null;    }    public void add(int value) {        ListNode newNode = new ListNode(value, this.head);        this.head = newNode;    }}

Melde dich an, um Bilder anzusehen.

Ein Objekt der Klasse LinkedList hat als einziges Attribut einen Listenkopf head vom Typ ListNode. Nach der Erzeugung eines LinkedList-Objekts enthält dieses noch keine Knoten, so dass der Listenkopf head eine null-Referenz darstellt. Die Abbildung zeigt schematisch eine leere Liste.

Geben Sie das weitere vorgehen der add Methode an.

Melde dich an, um Bilder anzusehen.

Wir können  eine verkettete Liste durch das sukzessive Einfügen von Knoten am Anfang der Liste aufbauen. Die Methode add()

1. erzeugt einen neuen Listenknoten,

2. trägt den Wert des Eintrags ein,

3. lässt das next-Attribut dieses Knotens auf den Kopf der Liste zeigen und

4. setzt den Kopf der Liste auf den neu erzeugten Listenknoten.

 

Melde dich an, um Bilder anzusehen.

Die Abbildung zeigt das Einfügen eines Knotens am Anfang einer nicht-leeren Liste. Das Attribut head verweist immer auf den ersten Knoten der Liste. Um eine Liste mit zwei Einträgen zu erhalten, gehen wir wie folgt vor:

Melde dich an, um Bilder anzusehen.

LinkedList liste = new LinkedList(); // 1

liste.add(47);                       // 2    

liste.add(11);                       // 3

Ergänzen die verkettete Liste um die Methode size(), damit Sie die länge der Liste ermitteln können.

public int size() {
         ListNode current = this.head;
         int count = 0;
         while (current != null) {
             count++;
             current = current.getNext();
         }
     return count;
}

Die Methode size() zeigt eine typisches Muster, um über eine verkettete Liste zu iterieren. Solange nicht das Ende der Liste erreicht ist (current != null), wird eine Aktion auf den betrachteten Knoten (current) angewendet, und anschließend der nächste Knoten (current.getNext()) aufgesucht.

Wird die Methode size() auf unsere oben erstellte zweielementige Liste angewendet, so verweist die lokale Variablecurrent zunächst auf den Listenkopf (der das Element 11 enthält) und hangelt sich im ersten Durchlauf der while-Schleife zum zweiten Listenknoten (der das Element 47 enthält) vor. Dessen null-Referenz übernimmt sie im zweiten Durchlauf derwhile-Schleife, worauf diese beendet wird.

Formulieren Sie die Methode size() mit Hilfe einer for-Schleife.

 

 public int size() {        int count = 0;        for (ListNode current = this.head; current != null;             current = current.getNext()) {            count++;        }        return count;    }

Erstellen Sie eine einfache Methode, die die Liste nach einem bestlmmten Wert durchsucht.

public boolean contains(int value) {        ListNode current = this.head;        while (current != null) {            if (current.getEntry() == value) {                return true;            }            current = current.getNext();        }        return false;    }

Überlegen sie, ob Listen auch für die binäre Suche geeignet sind.

Die binäre Suche setzt zunächst eine Ordnung unter den zu durchsuchenden Elementen voraus. Selbst auf einer sortierten Liste lässt sie sich jedoch nicht effizient implementieren, da Listen auf sequenziellem Zugriff beruhen. Die binäre Suche auf linearen Datenstrukturen erfordert wahlfreien Zugriff.

Schreiben Sie eine Methode sum(), die iterativ die Einträge der Listenknoten aufsummiert und die Summe zurückgibt.

 public int sum() {        ListNode current = this.head;        int sum = 0;        while (current != null) {            sum += current.getEntry();            current = current.getNext();        }        return sum;    }

Wir implementieren nun die Methode size() erneut, diesmal rekursiv:

public int size() {        return size(this.head);    }
    private int size(ListNode node) {    // 1        if (node == null) {              // 2            return 0;                    // 3        }                                // 4        return size(node.getNext()) + 1; // 5    }

Beachten Sie das Zusammenspiel der öffentlichen und der privaten size()-Methoden. Die öffentliche Methode ruft mit dem Listenkopf die private Methode auf, die rekursiv die eigentliche Arbeit erledigt. Dieses Muster ist uns im Zusammenhang mit rekursiven Methoden bereits bekannt und wird uns auch bei rekursiven Datenstrukturen oft begegnen.

Schreiben Sie ein Methodenpaar sum(), das die Einträge in den Listenknoten rekursiv aufsummiert:

public int sum() {

        return sum(this.head);    }    private int sum(ListNode node) {        if (node == null) {            return 0;        }        return node.getEntry() + sum(node.getNext());    }

Lernen