UE Algorithmen 2 - Uebung 6

Übungen zu Algorithmen und Datenstrukturen 2 WS 98/99

6. Übung - abzugeben am 17. 11. 1998 in Ihrer Übungsgruppe

6.a.1 Theorie

Gegeben: Eine konsekutive und eine einfach verkettete Liste. Stellen sie diese Konzepte bei der Durchführung der folgenden Operationen gegenüber:

Einfügen an der Position insPos mit 0<insPos<nrOfElems; insPos=0
Löschen an der Position delPos mit 0<delPos<nrOfElems; delPos=0
Suche nach einem Element (sortierte und unsortierte Listen)

Geben Sie für jeden Fall die möglichen Abbruchkriterien an.

6.a.2 Theorie

Gegeben ist eine doppelt verkettete Liste, deren erster und letzter Knoten vom Kopf aus direkt erreichbar sind. Stellen Sie die Listenstruktur und die Zeigermanipulationen graphisch und als Codefragment dar:

Einfügen: des vordersten, hintersten, einzigen sowie eines beliebigen Elementes der Liste
Löschen: des vordersten, hintersten, einzigen sowie eines beliebigen Elementes der Liste

Was fällt Ihnen dabei auf?

6.b Programm

Implementieren Sie ein Modul mit folgender Interface Definition bzw. Implementationshilfe:

DEFINITION OF MODULE Stack;
  CONST BLKS=??; (* e.g. 5 = number of elements per stack element *)
  TYPE
    ElemT* = LONGINT; (* data element type *)
    StElemT = RECORD (* stack element type *)
      a: ARRAY BLKS OF ElemT; (* data elems per stack elems *)
      next: ...; (* next stack element *)
    END;
    NodeT = POINTER TO StElemT;
    StackT*=RECORD ... END;

  PROCEDURE (VAR st:StackT) Init*();
  PROCEDURE (VAR st:StackT) CleanUp*();
  PROCEDURE (VAR st:StackT) Push*(elem:ElemT);
  PROCEDURE (VAR st:StackT) Pop*():ElemT;
  PROCEDURE (VAR st:StackT) Empty*():BOOLEAN;
  PROCEDURE (VAR st:StackT) NrOfElems*():LONGINT;
  PROCEDURE (VAR st:StackT) Dump*(); (* dump blockwise *)
END Stack.

Anmerkungen:

Besprechung der geforderten Funktionen erfolgt in der Übung
Sicherheitsabfragen nicht vergessen (HALT, ASSERT)

6.c Diskussion

Welche Vorteile bringen Sentinels / Dummies am Beginn/Ende einer einfach verketteten Liste?
Vergleichen Sie den Stack in 6.b mit einem klassischen (dynamischen) Stack. Welches Modell erscheint Ihnen günstiger?
Überlegen Sie sich Strategien, sowie deren Vor- und Nachteile, zur Implementierung selbstorganisierender linearer Listen.
Was ist bei der Konkatenation zweier Listen (verkettet/konsekutiv) zu beachten?

Last modified: hoermanseder@fim.uni-linz.ac.at 98-11-09