home *** CD-ROM | disk | FTP | other *** search
/ Turbo Toolbox / Turbo_Toolbox.iso / 1987 / 11 / hash.pas < prev    next >
Encoding:
Pascal/Delphi Source File  |  1987-09-03  |  3.9 KB  |  102 lines
  1. (*                                HASH.PAS
  2.    Erlaeuterung zur lexikalischen Analyse. Implementierung der Symbol-
  3.    tabelle des Scanners durch Hashing mit Kollisionsaufloesung mit Ver-
  4.    kettung. Es werden Symbole von der Tastatur eingelesen und in der
  5.    Reihenfolge ihres Auftretens in eine Hashtabelle eingetragen.
  6.    Config.: ATARI ST & Pascal ST Plus,  MS-DOS & Turbo Pascal              *)
  7. PROGRAM hash;
  8. CONST
  9.   maxidlength=8; zeilenmax=23; tablestart=4; maxentries=18; hashmax=9;
  10. TYPE
  11.   Str80      = STRING[80];
  12.   kollision  = ^kliste;
  13.   kliste     = RECORD  na : Str80; next : kollision;  END;
  14.   hashvektor = ARRAY[0..hashmax] OF kollision;
  15. VAR
  16.   i, j, hashindex: INTEGER;  na: Str80; hash: hashvektor;
  17.  
  18. PROCEDURE DrawLine;
  19. VAR i: INTEGER;
  20. BEGIN  FOR i := 1 TO 80 DO Write('-');  END;
  21.  
  22. PROCEDURE DrawColumn (x, y: INTEGER);
  23. BEGIN
  24.   WHILE y <= zeilenmax DO BEGIN GotoXY(x,y); Write('!'); y := y+1; END;
  25. END;
  26.  
  27.                                            (* Operationen auf Hashtabelle: *)
  28. PROCEDURE Init;
  29. VAR i: INTEGER;
  30. BEGIN  FOR i := 0 TO hashmax DO hash[i] := NIL  END;
  31.  
  32.                                 (* 'pos' gibt den Hashindex h(na) zurueck: *)
  33. FUNCTION Insert (VAR na: Str80; VAR Pos: INTEGER): BOOLEAN;
  34.   FUNCTION h (na: Str80): INTEGER;                         (* Hashfunktion *)
  35.   BEGIN h := (Ord(na[1])+Ord(na[Length(na)])) MOD (hashmax+1); END;
  36.  
  37.      (* fuegt n in die Kollisionsliste l ein, falls n noch nicht in l ent-
  38.         halten ist. Insertlist = true wenn in l eingefuegt wurde:          *)
  39.   FUNCTION InsertList (VAR n: Str80; VAR l: kollision): BOOLEAN;
  40.   VAR l1: kollision;
  41.   BEGIN
  42.     IF l = NIL THEN BEGIN                (* n wird in die Liste eingefuegt *)
  43.        New(l1);  l1^.na := n; l1^.next := NIL; l := l1; InsertList := TRUE;
  44.       END
  45.     ELSE IF l^.na = n THEN
  46.       InsertList := FALSE                  (* n ist in l bereits enthalten *)
  47.     ELSE
  48.       InsertList := InsertList(n,l^.next)   (* suche Rest der Liste nach n *)
  49.   END;
  50.  
  51. BEGIN (* Insert *)
  52.   Pos := h(na);  Insert := InsertList(na,hash[Pos]);             (* klar ! *)
  53. END;
  54.  
  55.                          (* gibt die Laenge der Kollisionsliste l zurueck: *)
  56. FUNCTION ListLen (l: kollision): INTEGER;
  57. BEGIN
  58.   IF l = NIL THEN ListLen := 0 ELSE ListLen := ListLen(l^.next)+1;
  59. END;
  60.  
  61. PROCEDURE Menue;         (* zeichnet die Symboltabelle auf den Bildschirm: *)
  62. VAR i: INTEGER;  f: TEXT;  c: CHAR;  s: Str80;
  63. BEGIN
  64.   ClrScr;  WriteLn('Hashing mit Kollisionsaufloesung durch Verkettung');
  65.   GotoXY(1,25); Write('Ende mit Bezeichner "ende", Eingabe max. 7 Zeichen');
  66.   GotoXY(1,tablestart);  DrawLine;
  67.   FOR i := 1 TO 10 DO DrawColumn(i*maxidlength,tablestart+1);
  68.   GotoXY(1,zeilenmax);  DrawLine;  GotoXY(1,tablestart-1);
  69.   FOR i := 0 TO 8 DO Write(' ':4,i,' ':3);
  70.   Write(' ':4,'9'); (* <-- sonst wandert der Cursor automatisch in die
  71.                      naechste Zeile und scrollt die Tabelle um 1 nach oben *)
  72. END;
  73.  
  74. (* traegt den Bezeichner n in der Bildschirmtabelle bei Hashindex 'index'
  75.    ein. n ist dabei der 'ith_entry'-Eintrag in der Kollisionsliste mit dem
  76.    zugehoerigen Index 'index':                                             *)
  77. PROCEDURE ShowId (VAR n: Str80; index, ith_entry: INTEGER);
  78. VAR i: INTEGER;  c: CHAR;
  79.   PROCEDURE Wait (l: INTEGER);  BEGIN  WHILE l > 0 DO l := l-1  END;
  80. BEGIN
  81.   IF ith_entry > maxentries THEN BEGIN
  82.     GotoXY(0,25); Write('Symboltabellen-Ueberlauf, breche ab... ');
  83.     n := 'ende';
  84.    END
  85.   ELSE
  86.     FOR i := 1 TO 5 DO BEGIN
  87.       IF Odd(i) THEN NormVideo ELSE LowVideo;
  88.       GotoXY(index*maxidlength+1,tablestart+ith_entry);
  89.       IF Length(n) >= maxidlength THEN n[0] := Chr(maxidlength-1);
  90.       Write(n);  Wait(30000);
  91.     END;
  92. END;
  93.  
  94. BEGIN
  95.   Menue;  Init;  na := '';
  96.   WHILE na <> 'ende' DO BEGIN
  97.     GotoXY(1,zeilenmax+1); ClrEol; Write('Bezeichner : '); ReadLn(na);
  98.     IF Insert(na,hashindex) THEN
  99.       ShowId(na,hashindex,ListLen(hash[hashindex]));
  100.   END;
  101. END.
  102.