Verlaufsprotokoll

In diesem Kurs ist die Entwicklung einer universellen Bibliothek (``Unit'') geplant, auf der schließlich ein beliebiges Programm zur Verwaltung von Daten (z.B. eine Auswertung und Tabellierung von Sportereignissen) aufsetzen soll. Nachdem in der Jahrgangsstufe 11 vor allem die Sprachelemente von Pascal an kleineren Programm-Beispielen erlernt wurde, steht dabei nun das Design der Datenstrukturen und Algorithmen im Vordergrund, die in der Bibliothek implementiert werden sollen.
In dieser Doppelstunde wird nun zunächst die Struktur einer einfach verketteten Liste betrachtet und der Vorgang des Einfügens und Löschens untersucht.
Die Schüler hatten die Hausaufgabe, sich über Listen im Buch zu informieren. Beim Warten auf den Lehrer ist das Verständnis dieser Inhalte bei einigen Schülern Gesprächstoff; die Unterhaltung verstummt allerdings, als der Lehrer am Gangende auftaucht.
In der Klasse erläutert der Lehrer zunächst kurz das Konzept einer Liste und weist darauf hin, daß eine Liste aus Sicht des Rechners eine ``normale Sache'' ist, da viele Programme mit internen Listen arbeiten. z.B. seien in einem Textverarbeitungsprogramm die Zeilen als verkettete Listen verwaltbar. Der Lehrer weist nun auf das Unterrichtsziel hin, eine Unit zu erstellen und fragt, wodurch sich diese Unit auszeichne. Ein aufgerufener Schüler erwähnt die Eigenschaft, daß der Benutzer der Unit lediglich das wissen muß, worauf er Zugriff hat. Dies werde durch die Prozedur-Kopf-Deklarationen festgelegt. Der Lehrer ergänzt, es handle sich dabei um eine Vereinbarung zwischen Anwendungsprogrammierer und Bibliotheksprogrammierer, deren Inhalt klar sein müsse.
Es wird nun eine Folie aufgelegt, die das Entfernen eines Elements aus einer verketteten Liste darstellt (Abb. 1).

 

Abbildung: Skizze am Whiteboard zum Entfernen eines Elements

Nach kurzer Betrachtung und Erläuterung der Skizze stellt der Lehrer die Frage, was mit dem entfernten Listenelement noch geschehen muß. Nach dem Hinweis eines Schülers auf die Notwendigkeit der Entfernung des Objekts aus dem Speicher mittels dispose ergibt sich das Problem, daß nach dem Entfernen aus der Liste das Objekt nicht mehr referenzierbar ist soweit nicht ein zweiter Zeiger eingesetzt wird. Auf die Frage eines Schülers, warum in der Skizze kein Zeiger vom entfernten Element auf das Nachfolgerelement eingezeichnet ist, antwortet der Lehrer, daß der Zeiger zwar vorhanden sei, seine Existenz jedoch aufgrund der fehlenden Zugriffsmöglichkeit keine Rolle spiele.
Der Lehrer weist nun auf einige Sonderfälle hin, die beim Entfernen aus einer Liste vorliegen können: Was passiert beim Löschen des ersten und letzten Listenelements bzw. bei dem Entfernen aus einer leeren Liste? Nachdem die Schüler auf die einzelnen Fragestellungen geantwortet haben, erwähnt der Lehrer die Wichtigkeit der Miteinbeziehung der Sonderfälle in die Implementation. Nach dieser Diskussion fordert der Lehrer die Schüler auf, die Skizze abzuzeichnen und die diskutierten Problemfälle stichwortartig festzuhalten. Während des Abzeichnens weist der Lehrer auf die zu langsame Arbeitsweise seiner Schüler und den dadurch entstehenden Verzug zu seiner Unterrichtsplanung hin.

Nachdem die Folie abgezeichnet ist, wird eine neue Folie (Abb. 2) aufgelegt, die das Einfügen in eine verkettete Liste graphisch darstellt. Der Lehrer erklärt die Skizze kurz und weist auf die Reihenfolge der Zeigerinitialisierung beim Einfügen hin: Zunächst muß der Zeiger auf Nachfolger in das neue Element kopiert werden, dann erst darf der Vorgänger auf das neue Element als Nachfolger verweisen. Es werden nun am Whiteboard die Datenstrukturen und Prozedurköpfe für Listen und Listenoperationen angeschrieben:

 

Abbildung: Skizze am Whiteboard zum Einfügen eines Elements

TYPE 	tzeiger = ^tknoten
	
	tknoten = RECORD
		    inhalt   : tinhalt;
		    naechster: tzeiger;
		  END;

Der Lehrer weist nun auf das Problem der rekursiven Abhängigkeit für den Compiler hin: tzeiger verweist auf den Datentyp knoten, der jedoch erst weiter unten deklariert wird; gleichzeitig enthält der Record tknoten als Element einen tzeiger, die erste Deklaration stellt also eine FORWARD-Deklaration dar (wird hinter der Anweisung notiert).
Der Lehrer stellt daraufhin die Frage, was für das Einfügen weiterhin notwendig ist: Benötigt wird ein konstanter Zeiger auf den Anfang der Liste, der sich von dem Zeiger auf das aktuelle Element unterscheiden soll:

	tkliste = RECORD
		    anfang   : tzeiger;
		    aktuell  : tzeiger;
		  END;

Der Lehrer fordert die Schüler auf, den Inhalt der zweiten Folie und des Whiteboards zu notieren, bemängelt dabei erneut die große Dauer des Abzeichnens. Während des Abzeichnens stellt ein Schüler die Frage, was tinhalt sei. Der Lehrer antwortet, daß dies im Anwendungsprogramm festgelegt würde. Auf die Nachfrage, ob sich der angeschriebene Code dann ohne Fehler kompilieren ließe, antwortet der Lehrer nicht direkt, sondern verweist auf den praktischen Teil.
Der Vorgang des Abzeichnen reicht bis in die Pause.
Ein Schüler stellt nach der Pause eine weitere Frage: Was passiert mit den beiden Zeigern, wenn man auf den Anfang der Liste zugreift. Der Lehrer betont erneut, daß dies Implementationsdetails sind, die in der Implementationsphase irrelevant seien. Er erklärt daraufhin noch einmal kurz den Sinn der Vorgehensweise: Ziel soll es sein, die Spezifikation von der Implementation zu trennen, so daß erstere gemeinsam soweit erarbeitet werden muß, daß kleinere Teams sie implementieren können. Zielkriterium für die Spezifikation ist es daher, daß ein Team allein an Hand ihrer die geforderte Funktionalität implementiert. Der Lehrer konkretisiert dies daraufhin mit dem Hinweis, daß man bei der Vereinbarung ``pingelig'' sein müsse mit der Benennung von Funktionsnamen und Parametern sowie der Reihenfolge der Argumente. Er weist zudem darauf hin, daß die Spezifikation im Laufe ihrer Entwicklung weiteren Änderungen unterzogen sein werde. Als Beispiel nennt er mögliche Namenskonflikte zwischen fuege_ein-Prozeduren für Bäume und Listen.
Der Lehrer beginnt nun die Signaturen der Prozeduren an das Whiteboard zu schreiben, wobei er lediglich die Namen anschreibt und die Parameternamen mit Schülerhilfe erarbeitet:

erzeuge(VAR l: tliste);

Es werden zusätzlich die Vor- und Nachbedingungen der Prozeduren festgelegt. Ein Schüler vertritt dabei die Auffassung, Vorbedingung sei, daß die Liste existieren müsse, wird dabei aber von einem anderen Schüler unterbrochen, der das Gegenteil behauptet. Der Lehrer nimmt dies zum Anlaß, allgemeine Verhaltensregeln anzumahnen und läßt beide Schüler ihren Beitrag in geordneter Form wiederholen. Als Ergebnis hält er fest, daß es nicht immer eine richtige oder falsche Vereinbarung in der Spezifikation geben müßte, sondern oft mehrere Möglichkeiten bestünden.
Als Nachbedingungen wird festgehalten:

l.anfang  := NIL;
l.aktuell := NIL;

Es werden nun weitere Prozedursignaturen (tlw. unvollendet) angeschrieben:

fuege_ein_vor( VAR l : tliste; inhalt : tinhalt);

fuege_ein_nach(

fuege_ein_am_ende

loesche(VAR l : tliste;
suche( VAR l : tliste;

Die Prozedur suche entsteht dabei aus der Überlegung, daß die Prozedur loesche eine Festlegung des zu löschenden Elements benötigt. Beim Betrachten der Prozedur fuege_ein_nach schlägt ein Schüler vor, lediglich eine Einfügeoperation bereitzustellen, da die anderen durch den zusätzlichen Einsatz von suche ersetzbar seien. Ein anderer Schüler schlägt vor, doppelt verkettete Listen zu verwenden, was der Lehrer mit dem Hinweis auf zu hohen Verwaltungsaufwand und Speicherplatzverbrauch für ungünstig hält. Er schlägt vor, die Schnittstelle zunächst einmal zu formulieren und sie später erneut zu diskutieren. Der Pausengong unterbricht die Diskussion. Der Lehrer gibt als Hausaufgabe, die Spezifikation zu vervollständigen. Er erinnert erneut daran, daß die Spezifikation allein als Grundlage für die Implementation dienen soll.