4. Teil
Daß all die Theorie aus den vorhergehenden Abschnitten auch praktischen Nutzen bringt, das soll hier mit einem Literaturstellen-Programm gezeigt werden. Das Programm ist einmal in Basic und einmal in Pascal geschrieben. Ein gutes Beispiel dafür, daß ein und derselbe Algorithmus sehr verschieden formuliert werden kann. Der Vergleich der beiden Programme kann vielleicht zeigen, daß modernes Basic zwar im Stil sehr hinter Pascal zurückliegt, in der Wirksamkeit aber durchaus mithalten kann.

Die Eingabeprozedur wird von der Einfügungsprozedur aufgerufen. Für jedes neue eingegebene Schlüsselwort (Keyword) ergeben sich grundsätzlich drei Möglichkeiten:
  1. Das Keyword ist schon eingetragen. Dann wird nur ein Literatureintrag vorgenommen.
  2. Das Keyword ist noch nicht in der Tabelle. Dann erfolgt ein Neueintrag in Tabelle und Liste.
  3. Die Tabelle oder die Liste sind voll. Dann muß eine Fehlermeldung ausgegeben werden.

Beim ersten Punkt ergibt sich eine weitere Unterscheidung:
  1. Die Berechnung des Index führt auf das richtige Keyword.
  2. Die Indexberechnung führt auf ein anderes Keyword. Dann tritt die weiter vorn beschriebene Kollision auf.

Für das Einfügen und die Suche wird die Hash-Funktion benötigt, die in Tabelle 13 definiert ist.

Tabelle 13: Die Hash-Funktion als Suchkriterium
FUNCTION HASH (X : KEYWORD) : INTEGER;
  VAR I : 1..5;
      H : INTEGER;
  BEGIN  H := 0;
  FOR I := 1 TO 5 DO
      H := (H * 10 + ORD(X[I]));
  HASH := H MOD N;
  END;

Da der Schlüssel keine Integerzahl ist, muß die Hash-Funktion über die Ordnungsrelation der Buchstaben und Ziffern berechnet werden. (Dabei genügt es, die ersten 5 Buchstaben auszuwerten.) Zum Beispiel ergibt das Schlüsselwort FUNKSCHAU und 21 Leerzeichen einen Funktionswert von 851, wenn der ASCII-Code zugrunde liegt.
Bei der folgenden Einfügungsprozedur muß kontrolliert werden, ob die Hash-Tabelle oder die Liste voll ist. Wenn dieser Fall auftritt, muß das Programm mit geänderten Konstanten N oder LENGTH neu übersetzt werden. Denken Sie auch daran, die Tabelle um 20% größer als nötig zu machen, um vernünftige Suchzeiten zu erhalten. Die Prozedur hat drei Parameter, den Schlüssel und die unter diesem Schlüssel einzutragende Heft- und Seitennummer (Tabelle 14).

Tabelle 14: Die Einfügungs-Prozedur
PROCEDURE INSERT (KEY : KEYWORD; HEFT, SEITE : INTEGER);
  VAR GEFUNDEN : BOOLEAN;
      MARKE,INDEX : 0..N;
      ZEIGER : 0..LENGTH
  BEGIN
  GEFUNDEN := FALSE;
  INDEX := HASH (KEY); MARKE := INDEX;
  REPEAT
    (* SUCHE NACH KEY IN DER TABELLE *)
    IF TAB[INDEX].KEY = BLANK30 THEN
      BEGIN (* NEUEINTRAG *)
      GEFUNDEN := TRUE;
    TAB[INDEX].KEY := KEY;
    TAB[INDEX].START := DATAPOINTER;(* ERSTER FREIER PLATZ *)
    LIST[DATAPOINTER,1] := HEFT;
    LIST[DATAPOINTER,2] := SEITE;
    LIST[DATAPOINTER,3) := 0; (* KEIN NACHFOLGER *)
    DATAPOINTER := DATAPOINTER + 1 (* WEITERSCHALTEN *)
    END
  ELSE
    IF TAB[INDEX].KEY = KEY THEN
       BEGIN (* AUF ANHIEB GETROFFEN *)
       GEFUNDEN := TRUE;
       ZEIGER := TAB[INDEX].START; (* ERSTER EINTRAG *)
       (* SUCHEN BIS ZUM ENDE DER EINTRÄGE ZU DIESEM SCHLÜSSELWORT,
          ALSO LIST [....,3]= 0 *)
       WHILE LIST[ZEIGER,3]<> 0 DO
         ZEIGER := LIST[ZEIGER,3];
         LIST[ZEIGER,3] := DATAPOINTER; (* EINTRAGEN *)
         LIST[DATAPOINTER,1] := HEFT;
         LIST[DATAPOINTER,2] := SEITE;
         LIST[DATAPOINTER,3] := 0;
         DATAPOINTER := DATAPOINTER + 1;
         END
    ELSE
         BEGIN (* PECH GEHABT, ZIRKULÄR SUCHEN! MARKE
                  MARKIERT DEN AUSGANGSPUNKT DER SUCHE *)
         IF INDEX = N THEN INDEX := 0 ELSE INDEX := INDEX + 1;
         IF INDEX = MARKE THEN
            BEGIN (* EINMAL DURCH, KEIN PLATZ *)
            WRITELN ('--TABLE OVERFLOW--');
            GEFUNDEN := TRUE (* FÜR ABBRUCH *);
            END;
         END;
UNTIL GEFUNDEN;
IF DATAPOINTER = LENGTH THEN
   WRITELN ('--LIST OVERFLOW--');
END;
 (* TABLE OV.:
          N VERGROESSERN,
        LIST OV.:
          LENGTH VERGR. *)

Bei der Suchprozedur Tabelle 15 gibt es nur zwei Möglichkeiten der Abfrage in der Prozedur. Entweder der Schlüssel steht in der Tabelle oder es muß zirkulär weitergesucht werden. Bei der zirkulären Suche wird abgebrochen, wenn der Schlüssel gefunden oder das ganze Feld erfolglos durchsucht wurde. Auch hier wird eine Variable MARKE verwendet, um den Anfangspunkt der Suche festzuhalten. Im übrigen ist das Verfahren das gleiche wie in der Einfügungsprozedur, es tritt nur der Ausdruck der Literaturverweise an die Stelle der Eingabe.

Tabelle 15: Suche nach dem Schlüsselwort
PROCEDURE SEARCH (KEY : KEYWORD (* DANACH WIRD GESUCHT *));
  VAR INDEX,MARKE : 0..N;
      ZEIGER,K:0...LENGTH;
      GEFUNDEN:BOOLEAN;
  BEGIN
  GEFUNDEN := FALSE; K := 0;

  INDEX := HASH (KEY); MARKE := INDEX;
  REPEAT
    IF TAB[INDEX].KEY = KEY THEN
      BEGIN (* AUF ANHIEB GEFUNDEN *)
      GEFUNDEN := TRUE;
      WRITELN (' ':3,KEY);
      (* LISTENEINTRÄGE AUSGEBEN *)
      ZEIGER := TAB[INDEX].START;
      REPEAT
        WRITE (' ':3,LIST[ZEIGER,1]:3,'/',LIST[ZEIGER,2]:4);
        K:=K+1;
        IF K MOD 6=0 THEN WRITELN;
        ZEIGER := LIST[ZEIGER,3];
      UNTIL ZEIGER = 0;
      IF K MOD 6 <> 0 THEN WRITELN; (* ZEILE ABSCHLIESSEN *)
      END
    ELSE
      BEGIN (* ZIRKULÄR WEITERSUCHEN *)
      IF INDEX = N THEN INDEX := 0 ELSE INDEX := INDEX + 1;
      IF INDEX = MARKE THEN
        BEGIN
        GEFUNDEN := TRUE (* STOPPER *);
        WRITELN ('--',KEY,'NOT FOUND--');
        END;
      END;
  UNTIL GEFUNDEN;
  END;

PROCEDURE ENTER;
  VAR KEY : KEYWORD;
      HEFT,SEITE : INTEGER;
  BEGIN
  WRITELN ('PLEASE ENTER: KEY,ISSUE,PAGE');
  WRITELN('FINISH WITH $');
  REPEAT
    GETLINE (KEY,HEFT,SEITE);
    IF KEY[1] <> '$'THEN
      INSERT (KEY,HEFT,SEITE);
  UNTIL KEY[1] = '$';
  END;

PROCEDURE QUESTION;
  VAR KEY : KEYWORD;
      I : 0..30;
  BEGIN
  WRITELN ('PLEASE ENTER KEY');
  I := 0;
  KEY := BLANK30;
  WHILE NOT EOLN AND (I<30) DO
    BEGIN I := I + 1; READ (KEY[I]) END;
  SEARCH (KEY);
  END;

Als letztes kommt nun LISTTABLE an die Reihe (Tabelle 16). Da TAB ja auch etliche Leerpositionen besitzt, müssen zuerst die gültigen Schlüsselworte herausgesucht werden. Danach werden diese Schlüsselworte sortiert, wozu der Algorithmus des linearen Einfügens Verwendung findet. Da die Schlüssel auch gleichzeitig die Informationen darstellen, wird der vereinfachte Algorithmus gleich in diese Prozedur eingefügt. Damit bei einer mehrfachen Ausgabe der Liste nicht die Sortierung wiederholt werden muß, fragt die Prozedur nach der Anzahl der Ausgaben.

Tabelle 16: Ausdruck der gesuchten Literaturstellen
PROCEDURE LISTTABLE;
  VAR KEYS : ARRAY [1..N] OF KEYWORD; (* FÜR SORTIEREN *)
      KEY : KEYWORD;
      I,J,K:0..N; ENDE : BOOLEAN;
  BEGIN
  (* ÜBERTRAGEN DER GÜLTIGEN KEYS *)
  K := 0;
  FOR I := 0 TO N DO
    IF TAB[I].KEY<>BLANK30 THEN
       BEGIN K := K + 1; KEYS[K] := TAB[I].KEY; END;
  (* SORTIEREN *)
  FOR I:=2 TO K DO (* K <= N *)
    BEGIN ENDE := FALSE;
    KEY := KEYS[I];
    J := I - 1;
    WHILE NOT ENDE AND (J > 0) DO
      IF KEY < KEYS[J]THEN
        BEGIN KEYS[J+1] := KEYS[J]; J := J - 1 END
      ELSE
        ENDE := TRUE;
    END (* SORTIEREN *);
  (* AUSGABE *)
  WRITELN ('HOW MANY COPIES DO YOU WANT');
  READ[I];
  REPEAT
    WRITELN (' ':25,'LITERATURSTELLEN');
    WRITELN (' ':25,'================');
    WRITELN; WRITELN; WRITELN;
    I := I - 1; (* ANZAHL KOPIEN RUNTERZÄHLEN *)
    FOR J := 1 TO K DO (* AUSGABE *)
        SEARCH(KEYS[J]);
  UNTIL I = 0;
END;

Wenn Sie das endgültige Programm sehen, werden Sie einige Abweichungen zu dem oben entwickelten sehen. Der Grund für die Abweichungen ist der verwendete Pascal-Compiler einer Großrechenanlage, der leicht vom Standard abweicht. So zeigt zum Beispiel der Schrägstrich hinter der Datei INPUT an, daß diese Datei der Tastatur des Terminals zugeordnet ist. Aus demselben Grund stehen auch die READLN-Anweisungen vor den eigentlichen Eingabeanweisungen. Lassen Sie sich von diesen Besonderheiten nicht beeindrucken. Die Basic-Version ist nach der Pascal-Version aufgelistet. Der verwendete Dialekt hat auch einige Besonderheiten. Es fehlt die ASC-Funktion, so daß zur Umwandlung des Strings etwas exotisch programmiert werden mußte. Die Zeilen 0570 bis 0600 einschließlich lassen sich durch die Zeile 
     0570 K9 = ASC (SUBSTR(X$,J,l))
ersetzen. Die verwendete Funktion SUBSTR ist identisch mit der Funktion MIDSTR.
Bei der Dateibehandlung wird eine Datei durch FILE#nr = name eröffnet, durch RESTORE#nr auf den Anfang zurückgesetzt und mit CLOSE#nr geschlossen. Die Funktion END#nr stellt fest, ob das Ende der Datei erreicht wurde. Alle anderen Programmteile dürften in jedem Basic-Dialekt laufen.
Damit ist unsere Betrachtung der Such- und Sortierverfahren mit einem sicher recht nützlichen und universellen Programmbeispiel abgeschlossen. Die eine oder andere Zeile kann man unter Berücksichtigung spezieller Pascal- und Basic-Dialekte sicher noch optimieren - im Vordergrund stand hier allerdings die Implementierbarkeit auf möglichst alle Computersysteme.

Literatur
  1. Jensen, K.; Wirth, N.: Pascal User Manual and Report. Springer-Verlag
  2. Wirth, N.: Algorithmen und Datenstrukturen. Teubner-Verlag
  3. Maurer, H.: Datenstrukturen und Programmierverfahren, Teubner-Verlag
  4. Knuth, D. E.: The Art of Computer Programming. Addison Wesley Public
  5. Hoare, C. A. R.: Quicksort. Computer Journal 5, No. 1 (1962)
  6. Haase, W.; Stucky, W.: Basic. BI-Verlag
  7. Feichtinger, H.: Basic für Mikrocomputer. Franzis-Verlag
  8. Plate, J.; Wittstock, P.: Pascal. Franzis-Verlag
[3. Teil] [Inhalt] [5. Teil]

Eingescanned von Werner Cirsovius
September 2002
© Franzis' Verlag