______________________________________________________________

Hauptprogramm Aufgaben 8.1/.2
___________
Quelltext:

MODULE Main;

IMPORT IO,Schlange;

VAR Wahl : CHAR;
VAR x : INTEGER;
VAR wahr : BOOLEAN;

(*********************************************************************)
(* Hauptprogramm zu Aufgabe 8,                                       *)
(* Fuegt Elemente zu einer Liste hinzu, oder entfernt diese.         *)
(*  Aufrufe:                                                         *)
(* -> enqueue                                                        *)
(* -> dequeue -> empty                                               *)
(* -> empty                                                          *)
(*********************************************************************)

BEGIN

  LOOP
    IF Wahl= '4' THEN EXIT; END; (* Beenden bei Benutzerwahl *)

    IO.Put("\n[1] Enqueue\n");
    IO.Put("[2] Dequeue\n");
    IO.Put("[3] Empty\n");
    IO.Put("[4] Beenden des Programms\n");

    Wahl:= IO.GetChar();
    EVAL IO.GetLine();

    (**Ereignisbehandlung**)
    (* Wenn '1', dann Wert einlesen und Element hinzufuegen. *)
    (* Wenn '2', dann Element entfernen und Wert ausgeben.   *)
    (* Wenn '3', dann pruefen ob leer, entsprechenden Text.  *)
    CASE Wahl OF
    | '1' =>

      (* Wiederhole bis Erfolg: neues Element einlesen *)
      LOOP
        IO.Put("\nBitte geben sie das neue Element ein: ");
        TRY
          x:= IO.GetInt();
          EVAL IO.GetLine();
          EXIT
        EXCEPT
          | IO.Error => IO.Put("Ungueltiger Wert.\n");
            EVAL IO.GetLine();
        END;
      END; (*LOOP*)

      (* Versuche Element in Schlange einzufuegen, abbrechen bei Fehler *)
      TRY
        Schlange.enqueue(x);IO.Put("\n");
      EXCEPT
        | Schlange.NoCapacity => IO.Put("\nDie Schlange ist bereits voll!\n")
      END;

    | '2' =>

      (* Versuche Element aus Schlange zu entfernen, abbrechen bei Fehler *)
      TRY
        x:= Schlange.dequeue();
        IO.Put("\nDas entfernte Element lautet: ");
        IO.PutInt(x);
        IO.Put("\n");
      EXCEPT
        | Schlange.QueueEmpty => IO.Put("\nDie Schlange ist Leer!\n")
      END;

    | '3' =>

      (* Prfe: Schlange leer?, entsprechende Textausgabe *)
       wahr:= Schlange.empty();
       IF wahr THEN IO.Put("\nSchlange ist Leer\n");
       ELSE IO.Put("\nSchlange enthaelt Elemente\n");
       END;

    ELSE
    END; (*CASE*)

  END; (*LOOP*)

END Main.

Aufgabe 8.1
___________
Quelltext:

MODULE Schlange;
IMPORT IO;

VAR queue : T;
VAR a,i : INTEGER;

(*-------------------------------------------------------------------*)
(* Prozedur enqueue, liest Argument: x, keine Rueckgabewerte, fuegt  *)
(* x in das Array ein.                                               *)
(*-------------------------------------------------------------------*)

PROCEDURE enqueue(x : INTEGER)
RAISES {NoCapacity} =

BEGIN

  IF queue[0]=n THEN RAISE NoCapacity END; (*queue[0] enthaelt Laenge*)

  (*Einfuegen*)
  queue[n-queue[0]]:= x;
  INC(queue[0]);

  (* Ausgabe *)
  FOR i:= 1 TO queue[0] DO
    IO.PutInt(queue[n-i+1]);IO.Put(" ");
  END;

END enqueue;

(*-------------------------------------------------------------------*)
(* Prozedur dequeue, keine Argumente, entfernt 1 Element aus dem     *)
(* Array und liefert dieses zurueck.                                 *)
(*  Aufrufe:                                                         *)
(* dequeue -> empty                                                  *)
(*-------------------------------------------------------------------*)

PROCEDURE dequeue() : INTEGER
RAISES {QueueEmpty} =

BEGIN

  IF empty() THEN RAISE QueueEmpty END;

  a:= queue[n];
  DEC(queue[0]);

  IF n>1 THEN
    i:= n;
    WHILE i>1 DO
      DEC(i);
      queue[i+1]:= queue[i];
    END;
  END;

  queue[1]:= 0;

  RETURN a;

END dequeue;

(*-------------------------------------------------------------------*)
(* Prozedur empty, keine Argumente, liefert WAHR, falls das Array    *)
(* keine Elemente enthaelt.                                          *)
(*-------------------------------------------------------------------*)


PROCEDURE empty() : BOOLEAN =

BEGIN

  IF queue[0]= 0 THEN RETURN TRUE
  ELSE RETURN FALSE END;

END empty;

BEGIN

END Schlange.

Testlauf:

[1] Enqueue
[2] Dequeue
[3] Empty
[4] Beenden des Programms
1

Bitte geben sie das neue Element ein: 5
5

[1] Enqueue
[2] Dequeue
[3] Empty
[4] Beenden des Programms
1

Bitte geben sie das neue Element ein: 7
5 7

[1] Enqueue
[2] Dequeue
[3] Empty
[4] Beenden des Programms
3

Schlange enthaelt Elemente

[1] Enqueue
[2] Dequeue
[3] Empty
[4] Beenden des Programms
1

Bitte geben sie das neue Element ein: 10
5 7 10

[1] Enqueue
[2] Dequeue
[3] Empty
[4] Beenden des Programms
1

Bitte geben sie das neue Element ein: 20
5 7 10 20

[1] Enqueue
[2] Dequeue
[3] Empty
[4] Beenden des Programms
1

Bitte geben sie das neue Element ein: 30
5 7 10 20 30

[1] Enqueue
[2] Dequeue
[3] Empty
[4] Beenden des Programms
1

Bitte geben sie das neue Element ein: 2

Die Schlange ist bereits voll!

[1] Enqueue
[2] Dequeue
[3] Empty
[4] Beenden des Programms
2

Das entfernte Element lautet: 5

[1] Enqueue
[2] Dequeue
[3] Empty
[4] Beenden des Programms
1

Bitte geben sie das neue Element ein: 8
7 10 20 30 8

[1] Enqueue
[2] Dequeue
[3] Empty
[4] Beenden des Programms
2

Das entfernte Element lautet: 7

[1] Enqueue
[2] Dequeue
[3] Empty
[4] Beenden des Programms
2

Das entfernte Element lautet: 10

[1] Enqueue
[2] Dequeue
[3] Empty
[4] Beenden des Programms
2

Das entfernte Element lautet: 20

[1] Enqueue
[2] Dequeue
[3] Empty
[4] Beenden des Programms
2

Das entfernte Element lautet: 30

[1] Enqueue
[2] Dequeue
[3] Empty
[4] Beenden des Programms
2

Das entfernte Element lautet: 8

[1] Enqueue
[2] Dequeue
[3] Empty
[4] Beenden des Programms
3

Schlange ist Leer

[1] Enqueue
[2] Dequeue
[3] Empty
[4] Beenden des Programms
1

Bitte geben sie das neue Element ein: -1
-1

[1] Enqueue
[2] Dequeue
[3] Empty
[4] Beenden des Programms
4

Testlaufende.

Aufgabe 8.2
___________
Quelltext:

MODULE SchlangeRef;

VAR element, neuesElement : REF ELEMENT;
VAR header, lastElement : REF ELEMENT;
VAR a : INTEGER;

(*-------------------------------------------------------------------*)
(* Prozedur enqueue, liest Argument: x, keine Rueckgabewerte, fuegt  *)
(* x in die Liste ein.                                               *)
(*-------------------------------------------------------------------*)

PROCEDURE enqueue(x : INTEGER)
RAISES {NoCapacity} =

BEGIN

  IF lastElement= NIL THEN lastElement:= header END;

  (*Einfuegen*)
  neuesElement:= NEW(T);
  neuesElement^.this:= x;
  IF header#NIL THEN
    lastElement^.next:= neuesElement;
  ELSE header:= neuesElement; END;
  lastElement:= neuesElement;

END enqueue;

(*-------------------------------------------------------------------*)
(* Prozedur dequeue, keine Argumente, entfernt 1 Element aus der     *)
(* Liste und liefert dieses zurueck.                                 *)
(*  Aufrufe:                                                         *)
(* dequeue -> empty                                                  *)
(*-------------------------------------------------------------------*)

PROCEDURE dequeue() : INTEGER
RAISES {QueueEmpty} =

BEGIN

  IF empty() THEN RAISE QueueEmpty END;

  (*Wertuebergabe*)
  element := header;
  a:= element^.this;

  header:= element^.next; (*Loeschen*)
  
  RETURN a;

END dequeue;

(*-------------------------------------------------------------------*)
(* Prozedur empty, keine Argumente, liefert WAHR, falls die Liste    *)
(* keine Elemente enthaelt.                                          *)
(*-------------------------------------------------------------------*)

PROCEDURE empty() : BOOLEAN =

BEGIN

  IF header = NIL THEN RETURN TRUE
  ELSE RETURN FALSE
  END;

END empty;

BEGIN

END SchlangeRef.

Testlauf:

[1] Enqueue
[2] Dequeue
[3] Empty
[4] Beenden des Programms
1

Bitte geben sie das neue Element ein: 5


[1] Enqueue
[2] Dequeue
[3] Empty
[4] Beenden des Programms
1

Bitte geben sie das neue Element ein: 7


[1] Enqueue
[2] Dequeue
[3] Empty
[4] Beenden des Programms
3

Schlange enthaelt Elemente

[1] Enqueue
[2] Dequeue
[3] Empty
[4] Beenden des Programms
1

Bitte geben sie das neue Element ein: 10


[1] Enqueue
[2] Dequeue
[3] Empty
[4] Beenden des Programms
1

Bitte geben sie das neue Element ein: 20


[1] Enqueue
[2] Dequeue
[3] Empty
[4] Beenden des Programms
1

Bitte geben sie das neue Element ein: 30


[1] Enqueue
[2] Dequeue
[3] Empty
[4] Beenden des Programms
1

Bitte geben sie das neue Element ein: 2


[1] Enqueue
[2] Dequeue
[3] Empty
[4] Beenden des Programms
2

Das entfernte Element lautet: 5

[1] Enqueue
[2] Dequeue
[3] Empty
[4] Beenden des Programms
1

Bitte geben sie das neue Element ein: 8


[1] Enqueue
[2] Dequeue
[3] Empty
[4] Beenden des Programms
2

Das entfernte Element lautet: 7

[1] Enqueue
[2] Dequeue
[3] Empty
[4] Beenden des Programms
2

Das entfernte Element lautet: 10

[1] Enqueue
[2] Dequeue
[3] Empty
[4] Beenden des Programms
2

Das entfernte Element lautet: 20

[1] Enqueue
[2] Dequeue
[3] Empty
[4] Beenden des Programms
2

Das entfernte Element lautet: 30

[1] Enqueue
[2] Dequeue
[3] Empty
[4] Beenden des Programms
2

Das entfernte Element lautet: 2

[1] Enqueue
[2] Dequeue
[3] Empty
[4] Beenden des Programms
3

Schlange enthaelt Elemente

[1] Enqueue
[2] Dequeue
[3] Empty
[4] Beenden des Programms
1

Bitte geben sie das neue Element ein: -1


[1] Enqueue
[2] Dequeue
[3] Empty
[4] Beenden des Programms
4

Testlaufende.

Aufgabe 8.3
___________
Lsungstext:

Der klare Vorteil einer Implementierung als Array ist anscheinend
die Lesbarkeit des Programmcodes. Allein das Einfgen eines
Elementes in eine lineare Liste gestaltet sich vergleichsweise
unbersichtlich. Da die Anzahl der Anweisungen hier wesentlich
grer, die Anweisungen selbst auerdem wesentlich komplexer sind.
Dies ist jedoch eine sehr individuelle Betrachtungsweise.
Ein Vorteil linearer Listen ist vor allem die Geschwindigkeit bei
greren Listen. Das Verschieben aller Elemente nimmt hier fr
gewhnlich sehr viel mehr Zeit in Anspruch. Im Gegenzug bentigt
eine lineare Liste aber auch ungefhr doppelt soviel Speicher wie
ein Array mit der selben Anzahl Elemente.
Allerdings mu hierfr das Array vorher explizit dimensioniert
werden. Dies kann sich in einigen Situationen schwierig gestalten,
wenn zum Beispiel erst zur Laufzeit die Lnge der Schlange ent-
schieden werden soll. Z.B. wenn fr einen Drucker die Anzahl der
mglichen Druckauftrge speicher- oder vielleicht seitenabhngig
sein soll. Andererseits, kann in manchen Situationen eben dies
auch unntig sein. So kann die Gre eines Speicherblocks als
fest angenommen werden. Wrde man die darin zu speichernden
Elemente in einer Liste ablegen, so wre ihre Gre dennoch stets
gleich. Unter Umstnden mchte man auch auf diese Weise sicher-
gehen, da eine Liste eine bestimmte Maximallnge nicht ber-
schreitet und diese auf dieser Lnge sogar vorinitialisieren.
Zumal es auch von Vorteil sein kann, gerade auf Multitasking-
fhigen Systemen, Speicher auf diese Weise vor Programmstart
explizit zu reservieren, um nicht spter nachfordern zu mssen,
da sonst die Mglichkeit besteht, da eben dieser pltzlich nicht
mehr vorhanden ist. Auerdem ist auch die Reservierung von Speicher
unter Umstnden ein Zeitfaktor.
Abhnging vom Kontext lt sich folglich die Rechenzeit oder
Speicherbelegung, durch eine lineare Liste, oder ein Array
optimieren. Was man letztendlich verwendet, bleibt aber letzten-
endes Geschmackssache.

Protokollende.