home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / lang / c / 16674 < prev    next >
Encoding:
Text File  |  1992-11-17  |  3.6 KB  |  100 lines
  1. Path: sparky!uunet!caen!spool.mu.edu!vms.csd.mu.edu!2644DANTICOJ
  2. From: 2644danticoj@vms.csd.mu.edu
  3. Newsgroups: comp.lang.c
  4. Subject: Can you program in C?
  5. Date: 17 Nov 1992 17:30:29 GMT
  6. Organization: Marquette University - Computer Services
  7. Lines: 88
  8. Message-ID: <00963BF4.675CEA80@vms.csd.mu.edu>
  9. Reply-To: 2644danticoj@vms.csd.mu.edu
  10. NNTP-Posting-Host: vmsd.csd.mu.edu
  11.  
  12. Greetings--
  13.  
  14. My name is Cetera and I am new to this network. I am anxiously awaiting
  15. graduating Marquette this December, but there is an obstacle in my way. I must
  16. first pass this math class in which I must program in C. I don't know this
  17. language, and now must write several programs before the end of the year. The
  18. course teaches data structures, which I have no problems understanding.
  19. However, all homework is programmed in C and because of an adminstrative
  20. loop-hole, I was enrolled in the class with no knowledge of the needed
  21. programming language. So, can you help me write these programs, thereby
  22. allowing me to graduate and go on to serve my country as an officer on a
  23. nuclear submarine? Please???? My future depends on it. By the way, I will be
  24. using a UNIX machine with a STUDSYS compiler. Help!!!!!!!!!!!!!!!!!!!!!
  25.  
  26. Problem statement
  27. *****************
  28.  
  29. Implement an open addressing hash table with a HASHSIZE of 17 and strings of 3
  30. (or more) characters as keys. You may use the following hash function or write
  31. you own:
  32.  
  33. typedef char *Key_type;
  34. #include <stdlib.h>
  35. #include "hash.h"
  36. /* Hash: calculate the hash value of s. */
  37. int Hash(Key_type s)
  38. {
  39.     int h=0;
  40.     while (*s)
  41.         h += *s++;
  42.         return abs(h % HASHSIZE);
  43. }
  44.  
  45. The file hash.h contains the following:
  46.  
  47. /* declarations for a chained hash table */
  48. #define HASHSIZE 997
  49. typedef char *Key_type;
  50. typedef struct item_tag {
  51.     Key_type key;
  52. } Item_type;
  53. typedef struct node_tag {
  54.     Item_type info;
  55.     struct node_tag *next;
  56. } Node_type;
  57. typedef Node_type *List_type;
  58. typedef List_type Hashtable_type[HASHSIZE];
  59.  
  60. ***************************************************************************
  61. ***************************************************************************
  62.  
  63. Problem 1
  64. *********
  65.  
  66. Implement an insert function using linear probing to resolve collisions.
  67.  
  68. Problem 2 
  69. *********
  70.  
  71. Implement a retrieve function using linear probing to resolve collisions.
  72.  
  73. Problem 3
  74. *********
  75.  
  76. Write a driver that will 1) initialize a hash table, 2) set up keys to insert
  77. and retrieve, 3) insert keys (be sure to illustrate collision), 4) retrieve
  78. keys (be sure to illustrate collision and a key not in the table). Inform the
  79. user of the progress of your testing by writing a stub that shows the contents
  80. of the keys in your hash table (just by walking down the array) when
  81. appropriate. There should be no user input. 
  82.  
  83. Extra Credit
  84. ************
  85.  
  86. Implement 2 different hash functions for the main part of the assignmant. Use 1
  87. for one  hash table and one for another. Insert the same keys and note the
  88. different locations that the two functions return. You may use the function
  89. above as one, the second would be of your own creation. Your driver should have
  90. 2 hash tables (one using one functino, the other using the other) or you can
  91. have 2 versions of the executable.  
  92.  
  93.  
  94. *****************************************************************************
  95. *****************************************************************************
  96. ******** Can you help? My graduation and future hang in the balance.*********
  97. *****************************************************************************
  98. ******************************************************* Cetera **************
  99. *****************************************************************************
  100.