home *** CD-ROM | disk | FTP | other *** search
/ Programmer 7500 / MAX_PROGRAMMERS.iso / PASCAL / HASH.ZIP / LIST.6 < prev    next >
Encoding:
Text File  |  1993-01-04  |  3.5 KB  |  93 lines
  1. Program Search_With_Chaining;
  2.  
  3.    Const
  4.       max_TAB_entry = 60;  {last TAB entry number}
  5.       number_TAB_entries = 61; {the number of entries in TAB}
  6.  
  7.    Type
  8.       tab_pointer = ^tab_entry;  {define a pointer to tab_entry (below)}
  9.       string4 = string[4];
  10.       tab_entry = record       {define an entry of TAB}
  11.          KEY_field: string4;   {holds KEY for this entry}
  12.          CHAIN: tab_pointer;    {pointer to next entry with same hash value}
  13.       end;
  14.  
  15.    Var
  16.       found: boolean;  {set true by Search if KEY is found}
  17.       index: tab_pointer; {pointer to the current TAB entry being examined}
  18.       KEY: string4;  {name to be found or entered}
  19.       i: integer;  {for FOR loop use}
  20.       node: array[ 0 .. max_TAB_entry ] of tab_pointer; {heads for each chain}
  21.  
  22.    Procedure Search( KEY: string4 );
  23.  
  24.       Function h( KEY: string4 ): integer;
  25.          Type
  26.             KEY_types = (char_KEY, integer_KEY);
  27.             KEY_overlay = record
  28.                case KEY_types of
  29.                   char_KEY:    ( KEY_in_characters: string4 );
  30.                   integer_KEY: ( dummy: byte; {takes up room for string size}
  31.                                  integer_KEY_1: integer; {first 2 bytes of KEY}
  32.                                  integer_KEY_2: integer; {last 2 bytes of KEY}
  33.                                 );
  34.             end;
  35.  
  36.          Var
  37.             KEY_record: KEY_overlay;
  38.          begin {hash}
  39.          with KEY_record do
  40.             begin
  41.                KEY_in_characters := '    '; {clean out in case KEY < 4 chars}
  42.                KEY_in_characters := KEY;
  43.                h := ( integer_KEY_1 xor integer_KEY_2 ) mod number_TAB_entries;
  44.             end;
  45.          end; {hash}
  46.       Var
  47.          hash: integer;  {holds the hash value the current KEY}
  48.          last_index: tab_pointer; {points to the last entry examined}
  49.  
  50.       Begin {Search}
  51.          found := false;
  52.          hash := h( KEY ); {go hash KEY}
  53.          index := node[ hash ];
  54.          if index = nil then {this is the first KEY with this hash value}
  55.             begin
  56.                new( index );  {create an entry for it}
  57.                node[ hash ] :=  index; {and set node to point to it}
  58.                index^.CHAIN := nil; {mark this entry as the end of the chain}
  59.                index^.KEY_field :=  KEY; {enter KEY into TAB entry}
  60.             end
  61.          else {there are entries with this hash value - search them}
  62.             begin
  63.                while ( index <> nil ) and not found  do
  64.                    begin
  65.                       if index^.KEY_field = KEY then {found it}
  66.                          found := true
  67.                       else {point to next entry with this hash value}
  68.                          begin
  69.                             last_index  := index; {point to the LAST entry}
  70.                             index := index^.CHAIN;
  71.                          end;
  72.                    end;
  73.                 if not found then {create a new entry}
  74.                    begin
  75.                       new( last_index^.chain );
  76.                       index := last_index^.chain; {and point to it with index}
  77.                       index^.CHAIN := nil; {mark this entry as end of chain}
  78.                       index^.KEY_field := KEY; {enter KEY into TAB entry}
  79.                    end;
  80.             end;
  81.       end; {Search}
  82.    Begin {Search_With_Chaining}
  83.  
  84.       for i:=0 to max_TAB_entry do node[i]:=nil; {set nodes to point nowhere}
  85.  
  86.  
  87.               {User Code Goes Here}
  88.  
  89.  
  90.    End. {Search_With_Chaining}
  91.  
  92.  
  93.