home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / comp / lang / c / 19007 < prev    next >
Encoding:
Internet Message Format  |  1992-12-30  |  3.3 KB
  1. Path: sparky!uunet!zaphod.mps.ohio-state.edu!usc!usc!not-for-mail
  2. From: aniekan@skat.usc.edu (Aniekan Akpaffiong)
  3. Newsgroups: comp.lang.c
  4. Subject: A chained hash table would be nice.
  5. Date: 29 Dec 1992 21:53:48 -0800
  6. Organization: University of Southern California, Los Angeles, CA
  7. Lines: 67
  8. Distribution: world
  9. Message-ID: <1hrdhcINN4t6@skat.usc.edu>
  10. NNTP-Posting-Host: skat.usc.edu
  11.  
  12. Needed: A hash table code that does collision resolution by chaining.
  13.  
  14. I would like some code that given a very large dictionary of words, will
  15. allow me to find a word quickly and inexpensively.
  16.  
  17. I'm attempting to write a program that will generate a crossword puzzle.
  18. (That's alright go ahead and laugh.)
  19.  
  20. Anyway, I'm now able to create only relatively small puzzles.  One of
  21. the problems with my program is in the way it searches the dictionary
  22. file for the next word to try.  Brute force doesn't seem to work. :-)
  23.  
  24. I would like to read the words into a chained hash table. If I come to
  25. a point in the puzzle that requires that I try a 3 letter word with an
  26. "a" already in the first position I can use "a__" as the key and then
  27. try the words in the chain, one by one.  The hash table might look
  28. something like this: 
  29.  
  30.    Key      Word1    Word2           Wordn
  31.    _____    ______   ______          ______   
  32.    |   |    |    |   |    |          |    |   
  33.    |a__|----|abe |---|ace |--- ... --|aye |
  34.    |   |    |    |   |    |          |    |   
  35.    -----    ------   ------         ------   
  36.      |
  37.      |
  38.    ______    ______   ______          ______   
  39.    |    |    |    |   |    |          |    |   
  40.    |__c_|----|arch|---|each|--- ... --|zact|
  41.    |    |    |    |   |    |          |    |   
  42.    ------    ------   ------          ------   
  43.      |
  44.      |
  45.    _______    _______   _______          _______   
  46.    |     |    |     |   |     |          |     |   
  47.    |____z|----|aaaaz|---|knutz|--- ... --|pizaz|
  48.    |     |    |     |   |     |          |     |   
  49.    -------    -------   -------          -------   
  50.  
  51. I would also like to include, as keys, words with 2 letters filled in,
  52. and those with 3 letters, etc etc.  At the extreme I could include as
  53. keys, words with all but one of the positions filled in:
  54.  
  55.    ___________    ___________
  56.    |         |    |         |
  57.    |erron_ous|----|erroneous|-->NULL
  58.    |         |    |         |
  59.    -----------    -----------
  60.  
  61. This will mean that the worst case limit on the number of keys needed
  62. will be huge.  At this point however, I am willing to err on the side
  63. of more speed. Also at look of them will point to NULL, is there an
  64. easy way to delete these before hand, or even not to generate them at
  65. all? 
  66.  
  67. At this point I would very much appreciate some code.  If you have
  68. code for the above lying around :-) or can point me to it I will be
  69. grateful.
  70.  
  71. If you have a better (faster) way of looking up words please share it
  72. with me.  Again, if you have it please point me to some code.  I'm not
  73. a programmer and need all the help I can get. :-)
  74. _____________________________________________________________________________
  75. INTERNET:aniekan@usc.edu     ||"Since Before Your Sun Burnt Hot In Space And
  76. UNIX Consulting              || Before Your Race Was Born, I Have Awaited...
  77. Univ. of Southern California || A Question!"          -- Guardian Of Forever
  78. _____________________________________________________________________________
  79.