From: aniekan@skat.usc.edu (Aniekan Akpaffiong)
Newsgroups: comp.lang.c
Subject: A chained hash table would be nice.
Date: 29 Dec 1992 21:53:48 -0800
Organization: University of Southern California, Los Angeles, CA
Distribution: world
NNTP-Posting-Host: skat.usc.edu

Needed: A hash table code that does collision resolution by chaining.

I would like some code that given a very large dictionary of words, will
allow me to find a word quickly and inexpensively.

I'm attempting to write a program that will generate a crossword puzzle.
(That's alright go ahead and laugh.)

Anyway, I'm now able to create only relatively small puzzles.  One of
the problems with my program is in the way it searches the dictionary
file for the next word to try.  Brute force doesn't seem to work. :-)

I would like to read the words into a chained hash table. If I come to
a point in the puzzle that requires that I try a 3 letter word with an
"a" already in the first position I can use "a__" as the key and then
try the words in the chain, one by one.  The hash table might look
something like this: 

   Key      Word1    Word2           Wordn
   _____    ______   ______          ______   
   |   |    |    |   |    |          |    |   
   |a__|----|abe |---|ace |--- ... --|aye |
   |   |    |    |   |    |          |    |   
   -----    ------   ------   	  ------   
     |
     |
   ______    ______   ______          ______   
   |    |    |    |   |    |          |    |   
   |__c_|----|arch|---|each|--- ... --|zact|
   |    |    |    |   |    |          |    |   
   ------    ------   ------          ------   
     |
     |
   _______    _______   _______          _______   
   |     |    |     |   |     |          |     |   
   |____z|----|aaaaz|---|knutz|--- ... --|pizaz|
   |     |    |     |   |     |          |     |   
   -------    -------   -------          -------   

I would also like to include, as keys, words with 2 letters filled in,
and those with 3 letters, etc etc.  At the extreme I could include as
keys, words with all but one of the positions filled in:

   ___________    ___________
   |         |    |         |
   |erron_ous|----|erroneous|-->NULL
   |         |    |         |
   -----------    -----------

This will mean that the worst case limit on the number of keys needed
will be huge.  At this point however, I am willing to err on the side
of more speed. Also at look of them will point to NULL, is there an
easy way to delete these before hand, or even not to generate them at
all? 

At this point I would very much appreciate some code.  If you have
code for the above lying around :-) or can point me to it I will be
grateful.

If you have a better (faster) way of looking up words please share it
with me.  Again, if you have it please point me to some code.  I'm not
a programmer and need all the help I can get. :-)
_____________________________________________________________________________
INTERNET:aniekan@usc.edu     ||"Since Before Your Sun Burnt Hot In Space And
UNIX Consulting              || Before Your Race Was Born, I Have Awaited...
Univ. of Southern California || A Question!"          -- Guardian Of Forever
_____________________________________________________________________________
Newsgroups: comp.lang.c,comp.lang.pascal