[ALGO 2 Homepage] Algorithmen und Datenstrukturen 2 WS 1999/2000

6. Übung - abzugeben am 29. 11. 1999 in Ihrer Übungsgruppe

6 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*=  INTEGER; (* data element type *)
        StElemT= RECORD  (* stack element type *)
                   data: ARRAY BLKS OF ElemT; (* data elements per stack element *)
                   next: ...; (* next stack element *)
                 END; (*record*)
        NodeT=   POINTER TO StElemT;
        StackT*= RECORD
                   ...
                 END; (*record*)

  PROCEDURE (VAR st:StackT) Init*();
  PROCEDURE (VAR st:StackT) CleanUp*(); (* clean the stack, think about versions with/without garbage collection *)
  PROCEDURE (VAR st:StackT) Push*(elem: ElemT);
  PROCEDURE (VAR st:StackT) Pop*(): ElemT; (* think about versions with/without garbage collection *)
  PROCEDURE (VAR st:StackT) Empty*(): BOOLEAN;
  PROCEDURE (VAR st:StackT) NrOfElems*(): INTEGER;
  PROCEDURE (VAR st:StackT) Dump*(); (* dump blockwise *)
END Stack.
Überlegen Sie dazu auch, wieviel Speicherplatz z.B. 30 Stacks mit insgesamt 2000 Elementen benötigen:
- "Normaler " Stack mit jeweils nur einem Element (ähnlich BLKS=1)
- BLKS=5
- BLKS=20
Bedenken Sie dabei auch die Fragmentierung.
Treffen Sie vernünftige Annahmen über den Platzbedarf der Werte ElemT, RECORDs, ...
Dokumentieren/beschreiben Sie die Überlegungen, wie Sie zu diesen Größenabschätzungen kommen!

Der einfachst gehaltene verfügbare Testtreiber ist als unverbindlicher Vorschlag bzw. Anregung zu verstehen. (Der Testtreiber ist für das Pow! System ausgelegt und bedarf in anderen Umgebungen eventuell einiger leichten Modifikationen.)

Last modified: Hörmanseder 1999-11-22