Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


3. Elementare Datenstrukturen



Übungen

  1. Schreiben Sie ein Programm zum Ausfüllen eines zweidimensionalen Feldes mit booleschen Werten, wobei a[i,j] gleich wahr (true) gesetzt werden soll, wenn der größte gemeinsame Teiler von i und j den Wert 1 hat, und andernfalls gleich falsch (false).
  2. Implementieren Sie eine Prozedur movenexttofront(t: link) für eine verkettete Liste, die den Knoten, der Nachfolger des Knotens ist, auf den t zeigt, an den Anfang der Liste verschiebt. (Abbildung 3.3 ist ein Beispiel hierfür für den Spezialfall, daß t auf den vorletzten Knoten in der Liste zeigt.)
  3. Implementieren Sie eine Prozedur exchange(t,u: link) für eine verkettete Liste, welche die Positionen der Knoten, auf die t und u zeigen, vertauscht.
  4. Schreiben Sie ein Programm zur Lösung des Problems des Josephus unter Verwendung eines Feldes anstatt einer verketteten Liste.
  5. Schreiben Sie Prozeduren für das Einfügen und Entfernen in einer doppelt verketteten Liste.
  6. Schreiben Sie Prozeduren zur Implementation von Stapeln mittels verketteter Listen, jedoch unter Verwendung von parallelen Feldern.
  7. Geben Sie den Inhalt des Stapels nach jeder Operation in der Folge E A S * Y * * Q U E * * * S T * * * I * O N an. Hierbei bedeutet ein Buchstabe »Ablegen« (des Buchstaben), und »*« bedeutet »Entnehmen«.
  8. Geben Sie den Inhalt der Schlange nach jeder Operation in der Folge E A S * Y * * Q U E * * * S T * * * I * O N an. Hierbei bedeutet ein Buchstabe »Setzen« (des Buchstaben), und »*« bedeutet »Holen«.
  9. Geben Sie eine Folge der Aufrufe von listinitialize, deletenext und insertafter an, welche die Abbildung 3.5 erzeugt haben könnte.
  10. Implementieren Sie die grundlegenden Operationen für eine Schlange unter Verwendung einer verketteten Liste.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]