A D T   H e a p

Beispielprogramm 3:   Priority Queue




PROGRAM  heap_anwendung_3;{
~~~~~~~~~~~~~~~~~~~~~~~~~~~
Anwendungsbeispiel "Priority-Queue", HMO, Warendorf, Juni 1988 / Dez.1994

Verwenden Sie den ADT Heap für ein Programm, das den Heap als "priority queue"
benutzt. Es soll stark vereinfacht die Zuteilung von Bausparverträgen simuliert
werden. Zuerst werden Namen und Bewertungszahlen (10..1000) eingegeben und in
einen Heap eingefügt. Dann läuft das Programm in einer Schleife, wobei in einer
Phase immer folgendes abläuft:
- es können weitere Namen und Bewertungszahlen eingegeben werden,
- die Zuteilung wird veranlaßt, das heißt die ersten 3 Namen mit den besten
  Bewertungszahlen werden ausgegeben,
- alle noch vorhanden Einträge werden in der Bewertung um 100 Punkte erhöht.
Benutzen Sie die Arraystruktur, um alle Einträge in der Bewertung zu erhöhen.
Ändert sich durch eine solche Aktion die Heapstruktur ?}

USES Crt;

CONST     n_heap         = 1000;    {max. Heapgröße}
TYPE      inhalt_heap    = RECORD   {Inhalt der Heapknoten incl. Bewertung}
                             wert: Integer;
                             name: String[10]
                           END;

FUNCTION  kleinergleich (b,a: inhalt_heap): Boolean;
BEGIN     kleinergleich:=(b.wert<=a.wert)  END;

FUNCTION  groessergleich (b,a: inhalt_heap): Boolean;
BEGIN     groessergleich:=(b.wert>=a.wert)  END;

{$I HPADT.PAS}

VAR  heap : heap_typ;
     b    : inhalt_heap;
     c    : Char;
     i    : Integer;

  {1}
  PROCEDURE zuteilen (VAR h: heap_typ);
  VAR i: Integer;
      e: inhalt_heap;
  BEGIN
    Writeln('Zuteilung: ');
    i:=1;
    WHILE (i<=3) AND NOT empty_heap(h) DO
    BEGIN
      best_heap(h,e);  delbest_heap(h);
      Writeln(e.name:15,e.wert:10);  i:=i+1
    END
  END;

  {2}
  PROCEDURE erhoehen (VAR h: heap_typ);
  VAR i: Integer;
  BEGIN
    FOR i:=1 TO count_heap(h) DO
      h.feld[i].wert := h.feld[i].wert + 100
  END;

BEGIN
  Writeln('BEISPIEL 3 zum ADT HEAP :  Zuteilung eines Bausparvertrages');
  Writeln('~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~');
  create_heap (heap,max_heap);
  REPEAT
    Writeln;
    Write('Bausparen:   A(nzeigen  E(infügen  Z(uteilen  Q(uit  ');
    REPEAT c:=Upcase(Readkey);
    UNTIL c IN ['A','Z','E','Q']; Writeln(c); Writeln;
    CASE c OF
      'E': IF full_heap(heap)
           THEN Writeln(#7)
           ELSE BEGIN
             Write('Name des Bausparers : '); Readln(b.name);
             Write('Bewertungszahl      : '); Readln(b.wert);
             in_heap (heap,b)
           END;
      'A': IF NOT empty_heap(heap)
           THEN FOR i:=1 TO count_heap(heap) DO
              writeln(i:3,'  ',heap.feld[i].name:10,' ',heap.feld[i].wert);
      'Z': BEGIN zuteilen (heap); erhoehen (heap) END
    END
  UNTIL c='Q'
END.




HTML-Texte: Heapoperationen Heapsort Priority Queue Branch & Bound ADT Heap HAUPTTEXT
Paket mit Pascal-Dateien laden: HeapPac.Zip   (39 K)

zur Informatik-Leitseite


© HMO, Neubearbeitung Januar 1998