home *** CD-ROM | disk | FTP | other *** search
/ Turbo Toolbox / Turbo_Toolbox.iso / spezial / 07 / trie / trie.mod < prev    next >
Encoding:
Text File  |  1989-02-22  |  2.9 KB  |  106 lines
  1. MODULE Trie;
  2. (* M.Holzherr, April 88, MacMETH2.4, MacReflex
  3.    Erprobung einer Datenstruktur zur Speicherung
  4.    eines Woerterbuchs. Alle ueber die Tastatur
  5.    eingebenen Worte werden in einem Trie gespeichert.
  6.    Eingabeschlusszeichen ist ein ".". Anschliessend werden
  7.    alle gefundenenWorte alphabetisch geordnet aufgelistet. *)
  8.  
  9. FROM InOut IMPORT Write, Read, WriteString, WriteLn ;
  10. FROM Storage IMPORT ALLOCATE;   
  11.  
  12. TYPE TRIE = POINTER TO NODE;     (* Zeiger auf 
  13.                                     Woerterbuchknoten      *)
  14.      NODE = RECORD
  15.               Char : CHAR;            
  16.               wordEnd : BOOLEAN; (* TRUE = Wortende hier   *)   
  17.               v, h    : TRIE     (* v-ertikal, h-orizontal *)  
  18.             END;
  19.             
  20.             
  21. VAR  ch, Ch : CHAR;  (* Ch = CAP(ch) *)              
  22.             
  23. (* -1---- insert liest ein Wort buchstabenweise und
  24.           fuegt es in das Woerterbuch ein, falls es nicht
  25.           schon eingetragen ist. Beim Aufruf muss der erste
  26.           Buchstabe des Wortes schon gelesen sein   ------ *)
  27. PROCEDURE insert( VAR p : TRIE (* in/out *) ); 
  28.  
  29.   (* -1-1-- make erzeugt  neuen Knoten -- *)
  30.   PROCEDURE make( VAR p : TRIE (* out *) );
  31.   BEGIN
  32.     ALLOCATE( p, SIZE( NODE) ); 
  33.     WITH p^ DO 
  34.       Char:= Ch; wordEnd:= FALSE; v:= NIL; h:= NIL 
  35.     END;
  36.   END make;
  37.   
  38.   (* -1-2-- readAndInsertNextChar liest und verarbeitet 
  39.             das naechste Zeichen                     ---- *)
  40.   PROCEDURE readAndInsertNextChar;
  41.   BEGIN
  42.      Read(ch); Write(ch); Ch:= CAP(ch);
  43.     IF (Ch >= 'A') & (Ch <= 'Z') THEN
  44.       insert(p^.v)
  45.     ELSE p^.wordEnd:= TRUE
  46.     END;
  47.   END readAndInsertNextChar;
  48.  
  49.  
  50.   VAR q : TRIE;
  51. BEGIN
  52.   IF p = NIL THEN
  53.     make(p);
  54.     readAndInsertNextChar;
  55.   ELSIF p^.Char > Ch THEN
  56.     make(q); q^.h:= p; p:= q;
  57.     readAndInsertNextChar;
  58.   ELSIF p^.Char < Ch THEN
  59.     insert(p^.h)
  60.   ELSE 
  61.     readAndInsertNextChar;
  62.   END
  63. END insert;
  64.  
  65.  
  66.  
  67. (* -2-- printTrie schreibt das Woerterbuch alphabetisch
  68.         geordnet, zeilenweise auf das Ausgabemedium  -- *)
  69.   VAR S : ARRAY[0..100] OF CHAR; 
  70.    (* S[0...level] = Wortteil *)
  71. PROCEDURE printTrie( p : TRIE; level : INTEGER );
  72.   VAR i : INTEGER;
  73. BEGIN
  74.   IF p <> NIL THEN
  75.     S[level]:= p^.Char;
  76.     IF p^.wordEnd THEN
  77.       FOR i:= 0 TO level DO Write(S[i]) END; WriteLn;
  78.     END;
  79.     printTrie(p^.v, level + 1);
  80.     printTrie(p^.h, level    );
  81.   END
  82. END printTrie;
  83.  
  84.   VAR t : TRIE;
  85. BEGIN (* Trie. Test mit Tastatureingabe  *)
  86.   t:= NIL; 
  87.   WriteString('Beliebig viele Worte eingeben (keine Umlaute)');
  88.   WriteString(' Abschluss durch Eingabe von  "." ');
  89.   WriteLn; WriteLn;      
  90.   REPEAT
  91.     Read(ch); Write(ch); Ch:= CAP(ch);
  92.     IF (Ch >= 'A') & (Ch <= 'Z') THEN
  93.       insert(t)
  94.     END
  95.   UNTIL ch = "."; 
  96.   WriteLn; WriteLn; printTrie(t, 0);
  97.   Read(ch)
  98. END Trie. 
  99.          
  100.   
  101.  
  102.  
  103.    
  104.                  
  105.                                    
  106.