Lösungsvorschläge

zu den Aufgaben im Kapitel 4

Aufgabe 4.1: Der KNP-Algorithmus kann verbessert werden, wenn in der Funktion nextTabelle die Zuweisung

next[tabIndex] = ruecksprung;

auf die etwas differenziertere Zuweisung

next[tabIndex] = 
   muster[tabIndex] != muster[ruecksprung] ?
   ruecksprung :
   next[ruecksprung];

ausgetauscht wird. Erklären Sie die Verbesserung und finden Sie Beispiele, bei denen sie zur Geltung kommt.

Lösung: fehlt noch

Aufgabe 4.2: Programmieren Sie das Einfügen und das lineare Suchen in einer sortierten Reihung (mit der Technik der „Markierung“) als Klasse mit folgender Spezifikation:

class SortierteReihung extends Reihung {
   public void einfuegen(final Element element); // ensures sammlung sortiert
   public int suchen(int suchSchluessel); // requires sammlung sortiert
     // ensures -1 <= return < sammlung.length;
}

Lösung:

public void einfuegen(final Element element) {
   // requires frei < sammlung.length
   sammlung[frei] = element; // Marke
   int platz = 0;
   while (sammlung[platz].schluessel < element.schluessel) // Abbruch bei frei
     platz++;
   for (int i = frei; i > platz; i--)
     sammlung[i] = sammlung[i-1]; // Verschieben nach oben
   sammlung[frei] = element;
}

public int suchen(int suchSchluessel) {
   // ensures -1 <= return < sammlung.length;
   // return -1, wenn nicht gefunden
   int index = 0;
   while (index<frei && sammlung[index].schluessel != suchSchluessel)
     index++;
   if (index == frei)
     index = -1; // nicht gefunden
   return index;
}

Aufgabe 4.3: Programmieren Sie das Löschen in einer sortierten Reihung:

class SortierteReihungLoeschbar extends SortierteReihung {
   void loeschen(int index); // requires 0 <= index < sammlung.length;
}

Wir gehen davon aus, dass der Index des zu löschenden Elements zuvor (z.B. durch suchen) ermittelt wurde. Was ist die Komplexität der Methode?

Lösung:

void loeschen(int index) { // requires 0 <= index < sammlung.length;
   for (int i = index; i < sammlung.length; i++)
     sammlung[i] = sammlung[i+1]; } // Verschieben nach unten

Aufgabe 4.4: Erweitern Sie die obige Implementierung HashTabelle mit den erwähnten Verbesserungen: Methoden kollisionen und naechstesSuchen (für Mehrfacheintragungen mit demselben Schlüssel) und einer Sondierungsfunktion

  index = (index + k*k) % inhalt.length;

wo k der Zähler für Sondierungsschritte ist.

Lösung:

public void eintragen(int schluessel, Object element) throws Voll {
   if (anzahl + 1 == inhalt.length)
     throw new Voll();
   else if (! vorhanden(schluessel)) {
     if (k > 0)
      kollisionen++;
     inhalt[index].schluessel = schluessel;
     inhalt[index].belegt = true;
     anzahl++; }
   inhalt[index].element = element; }
private int kollisionen = 0, k = 0;
public int kollisionen() {
   return kollisionen; }
public boolean vorhanden(int schluessel) {
   letzterSchluessel = schluessel;
   index = schluessel % inhalt.length;
   while (inhalt[index].belegt &&
      schluessel != inhalt[index].schluessel) {
     k++;
     index = index = (index + k*k) % inhalt.length; } // neue Sondierungsfunktion
   k = 0;
   return (schluessel == inhalt[index].schluessel); }

Aufgabe 4.5: Modifizieren Sie das lineare Suchen mit „Markierung“: Vereinfachen Sie die Abbruchbedingung der while-Schleife, nachdem Sie den gesuchten Schlüssel im Pseudo-Endknoten absetzen.

Lösung: fehlt noch

Aufgabe 4.6: Programmieren Sie den Algorithmus für suchen rekursiv.

Lösung:

private Knoten suchenRekursiv(int suchSchluessel, Knoten knoten) {
   try {
     return (knoten.wert == suchSchluessel) ? knoten :
      suchenRekursiv(suchSchluessel, knoten.verbindung);
   } catch (NullPointerException e) {
     return null; } } // nicht gefunden

public Knoten suchenRekursiv(int suchSchluessel) {
   return suchenRekursiv(suchSchluessel, aelteste); }

Aufgabe 4.7: Erläutern Sie, warum man in einer verketteten Liste nicht so „binär suchen“ kann wie in einer sortierten Reihung.

Lösung: Weil die „Mitte“ der Liste nicht zu finden ist, sie kann nicht „halbiert“ werden.

Aufgabe 4.8: Programmieren Sie das Einfügen und das lineare Suchen in einer sortierten verketteten Liste. Was ist der Vorteil gegenüber der unsortierten Liste?

Lösung: Der Vorteil ist, dass im negativen Fall die Suche früher aufhört.

Knoten suchen(int suchSchluessel) {
   Knoten knoten = anker;
   while (knoten != null && knoten.wert.schluessel < suchSchluessel)
     knoten = knoten.verbindung;
   return (knoten.wert.schluessel == suchSchluessel) ? knoten : null;   }