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

1. Übung - abzugeben am 12. 10. 1999 in Ihrer Übungsgruppe

In einer der nächsten Übungen werden Sie folgende Aufgabe erhalten: 

DEFINITION OF MODULE Matrix; (*mittels Dope-Vektor*)
  CONST DIM*=     3; (*variabel!!! *)
  TYPE  Index*=   ARRAY DIM OF INTEGER;
        Element*= INTEGER;

  PROCEDURE Init*(loBnd, upBnd: Index; VAR err: BOOLEAN);
  PROCEDURE CleanUp*();
  PROCEDURE Get*(inx: Index; VAR ele: Element);
  PROCEDURE Put*(inx: Index; ele: Element);
  PROCEDURE Find*(VAR outx: Index; VAR found: BOOLEAN; ele: Element);
END Matrix.
Als Ihre erste Aufgabe sollen Sie für dieses Modul, das einen Matrixzugriff realisieren wird, ein einfaches Testprogramm ("Testtreiber") schreiben.
Um dieses Testprogramm dann auch selbst testen zu können, müssen Sie natürlich die Einfachstversion dieses Moduls (z.B. nur für 3-dimensional, Einsatz der normalen Matrixadressierung von Oberon-2, ...) fertigstellen. Tips dazu bzw. Implementierungsdetails erhalten Sie in der Übung.

Hinweise:

  1. Sicherheitsabfragen nicht vergessen!
  2. Testtreiber soll einen vollständigen Test für die jeweils angelegte Matrix ausführen (Alle Elemente vorhanden, keine zusätzlichen Elemente vorhanden, alle gespeicherten Werte können an der richtigen Position gefunden werden).
  3. Überprüfen Sie in ihrem Testprogramm, ob das Matrix-Modul auch fehlerhafte Parameter erkennt (Rückgabe von err=TRUE!).
  4. Da das Testprogramm Dimensions-unabhängig sein sollte, benötigen Sie für den vollständigen Test eine Prozedur, welche einen beliebig-dimensionalen Index erhöht. Inkrementieren Sie dazu den letzen Indexwert und erhöhen Sie bei einem Überlauf die nächste Stelle.
    Die hierfür notwendigen Prozeduren/Funktionen werden bei der Ausgabe dieser Übung vorbesprochen und gemeinsam entwickelt.
  5. Denken Sie daran, daß die untere Grenze der Indizes voneinander verschieden sein können und nicht Null sein müssen.

Die Simulation des Modules Matrix könnte derzeit ausschnittweise z.B. folgendermaßen aussehen:

MODULE Matrix;

  CONST DIM*= 3; (*variabel!!! *)

  TYPE  Index*=   ARRAY DIM OF INTEGER;
        Element*= INTEGER;

  VAR   ub, lb: Index;
        m:      POINTER TO ARRAY OF ARRAY OF ARRAY OF Element;

  PROCEDURE IndexOk(inx: Index): BOOLEAN;
  BEGIN (*InodexOk*)
    ...
  END IndexOk;

  PROCEDURE Init*(loBnd, upBnd: Index; VAR err: BOOLEAN);
  BEGIN (*Init*)
    ...Fehlerprüfungen...
    lb:=loBnd;
    ub:=upBnd;
    NEW(m, ub[0]-lb[0]+1, ub[1]-lb[1]+1, ub[2]-lb[2]+1);
    err:=(m=NIL);
  END Init;

  PROCEDURE CleanUp*;
  BEGIN (*CleanUp*)
    ASSERT(m#NIL);
    DISPOSE(m); m:=NIL;
  END CleanUp;

  PROCEDURE Get*(inx: Index; VAR ele: Element);
  BEGIN (*Get*)
    ASSERT((m#NIL) & IndexOk(inx));
    ele:=m[inx[0]-lb[0], inx[1]-lb[1], inx[2]-lb[2]];
  END Get;

  PROCEDURE Put*(inx: Index; ele: Element);
  BEGIN (*Put*)
    ASSERT((m#NIL) & IndexOk(inx));
    m[inx[0]-lb[0], inx[1]-lb[1], inx[2]-lb[2]]:=ele;
  END Put;

  PROCEDURE Find*(VAR outx: Index; VAR found: BOOLEAN; ele: Element);
  BEGIN (*Find*)
   ...
  END Find;

BEGIN (*Matrix*)
  ASSERT(DIM=3);
  m:=NIL;
END Matrix.

Bitte vergessen Sie nicht auf Kommentare zu diesem Modul und zum "Testtreiber"!!

Last modified: Hörmanseder 1999-10-04