Algorithmen und |
3. Übung - abzugeben am 9. 11. 1999 in Ihrer Übungsgruppe
DEFINITION OF MODULE Graph; TYPE Graph*=RECORD vertexn-: INTEGER; (* Anzahl Knoten im Graphen *) edgen-: INTEGER; (* Anzahl Kanten im Graphen *) END; (*record*) PROCEDURE (VAR g:Graph)Init*(v:INTEGER); (* v=Anzahl der Knoten im Graphen *) PROCEDURE (VAR g:Graph)CleanUp*(); (* Freigabe des Graphen = Freigabe des dynamisch allokierten Speicherplatzes *) PROCEDURE (VAR g:Graph)SetEdge*(x,y:INTEGER); (* Kante x,y in den ungerichteten Graphen aufnehmen *) PROCEDURE (VAR g:Graph)PrGraph*(); (* Ausgabe der Adjazenzmatrix für den Test *) PROCEDURE (VAR g:Graph)Warshall*(VAR res:Graph); (* Anwenden des Algorithmus von Warshall auf den Graphen g; Ergebnis in res *) END Graph;
Anmerkungen:
Ein einfachster Testtreiber (ohne jegliche eigenständige Überprüfungen) könnte z.B. wie folgt aussehen:
MODULE GraphTst;
IMPORT Graph, In, Out;
PROCEDURE ProgMain*;
VAR g1, g2: Graph.GraphT;
x,y: INTEGER;
code: CHAR;
BEGIN (*ProgMain*)
REPEAT
In.Echo(FALSE);
In.Prompt("?/1/2/3/4/5/E: "); In.Char(code); code:=CAP(code);
In.Echo(TRUE);
IF ~In.Done THEN code:="E" END; (*if*)
CASE code OF
"0", "H", "?":
Out.String("(?) HILFE der Befehlscodes: ?=Hilfe / 1=Init / 2=Kante / 3=Adjazenzmatrix / 4=Warshall / 5=Loeschen / E=Ende")
| "1", "I":
Out.String("(1) INIT Graph: "); In.Prompt("Anzahl Knoten="); In.Int(x);
g1.Init(x)
| "2", "K":
Out.String("(2) KANTE einfuegen: ");
In.Prompt("Knoten 1= "); In.Int(x); Out.String(" ");
In.Prompt("Knoten 2= "); In.Int(y);
g1.SetEdge(x,y)
| "3", "A", "M":
Out.F2("(3) ADJAZENZMATRIX ausgeben: (Anzahl Knoten=# Anzahl Kanten=#)$",
g1.vertexn, g1.edgen);
g1.PrGraph
| "4", "W":
Out.String("(4) WARSHALL auf Graph ausfuehren: "); Out.Ln;
g1.Warshall(g2);
g2.PrGraph;
g2.CleanUp
| "5", "L":
Out.String("(5) Loeschen Graph");
g1.CleanUp
| "6", "E":
Out.String("(6) ENDE des Tests");
ELSE
Out.String("(x) FEHLER!!! Befehlscodes: ?=Hilfe / 1=Init / 2=Kante / 3=Adjazenzmatrix / 4=Warshall / 5=Loeschen / E=Ende")
END; (*case*)
Out.Ln
UNTIL ~In.Done OR (code="E") OR (code="6")
END ProgMain;
END GraphTst.
Damit Sie das Modul Graph nicht vollständig neu schreiben müssen, hier kurz ein Codefragment
(als unverbindlicher Vorschlag) dazu:
MODULE Graph;
IMPORT Out;
TYPE GraphT*=RECORD
vertexn-: INTEGER;
edgen-: INTEGER;
a: POINTER TO ARRAY OF ARRAY OF BOOLEAN
END; (*record*)
PROCEDURE (VAR g:GraphT)Init*(v:INTEGER);
VAR i,j:INTEGER;
BEGIN (*Init*)
ASSERT(v>0);
ASSERT(g.a=NIL);
NEW(g.a,v,v); ASSERT(g.a#NIL);
g.edgen:=0;
g.vertexn:=v;
FOR i:=0 TO v-1 DO
FOR j:=0 TO v-1 DO
g.a[i,j]:=FALSE
END (*for*)
END (*for*)
END Init;
PROCEDURE (VAR g:GraphT)CleanUp*();
BEGIN (*CleanUp*)
ASSERT(g.a#NIL);
DISPOSE(g.a); g.a:=NIL;
g.edgen:=0;
g.vertexn:=0;
END CleanUp;
PROCEDURE (VAR g:GraphT)SetEdge*(x,y:INTEGER);
BEGIN (*SetEdge*)
...
END SetEdge;
PROCEDURE (VAR g:GraphT)PrGraph*();
VAR z,s:INTEGER;
BEGIN (*PrGraph*)
ASSERT(g.a#NIL);
Out.String(" ");
FOR s:=0 TO g.vertexn-1 DO Out.Int(s,3) END; (*for*)
FOR z:=0 TO g.vertexn-1 DO
Out.Ln; Out.Int(z,3); Out.String(": ");
FOR s:=0 TO g.vertexn-1 DO
Out.String(" ");
IF(g.a[z,s]) THEN Out.Char("*") ELSE Out.Char(".") END (*if*)
END (*for*)
END; (*for*)
Out.Ln
END PrGraph;
PROCEDURE (VAR g:GraphT)Warshall*(VAR res:GraphT);
...
BEGIN (*Warshall*)
...
END Warshall;
END Graph.
(Denken Sie auch daran, daß wir Assertions in diesen Beispielen zur Kennzeichnung von
Sonderfällen verwenden, die wir hier softwaretechnisch nicht behandeln, da wir uns auf die
Algorithmen konzentrieren wollen.)