Programming Forums > Application Development > C++

maybesomeday · Jan 14th, 2005, 9:56 AM

For a piece of coursework I am going to use hash tables. I have decdied to try and learn them by just writing a small program to enter data into a hash table and then print out the last thing that was entered. But it is the entry into the hash that is most important. Here is the code I have written:

(Toggle Plain Text)

 #include <stdio.h>
 #include <stdlib.h>
 
 
 /*defien structure and types*/
 
 typedef struct list
 {
     char word[50];
     struct list *next;
 }LIST;
 
 typedef LIST *P_LIST;
 
 P_LIST hash_table[5];
 
 
 P_LIST insert(char string[],P_LIST head);
 int hash(char word[]);
 
 
 
 int main ()
 {   
      int h, i;
      P_LIST output;
      char keyword[50], input[50];
      
       for (i=0; i < 7; i++)
       {   
       printf ("Enter word to put in hash table: ");
      scanf ("%s", &keyword);
       h = hash(input);
       output = hash_table[h]; 
       output = insert(input,output);
       }    
       
       printf("%s", output -> word);
       
   }    
 
 /*Finds a key value for the word*/
 
 int hash(char word[])
 {
     {   
     int i = 0;
     unsigned sum = 1;
     unsigned key;
     while (word[i] != '\0')
     {
         sum = sum * word[i];
         i++;
     }
     key = sum % 5;        
     return key;
     }          
 }  
 
 /*Inserts into the list pointed to by the hed parameter*/
 
  P_LIST insert(char string[],P_LIST head)
 {
     P_LIST node;
     node = malloc(sizeof(LIST));
     node -> next = head;
     head = node;
     strcpy (node -> word, string);
     return head;
 }

Is this the right way to enter stuff into a hash table or am I doing it wrong?

Dizzutch · Jan 14th, 2005, 10:18 AM

if you have a has table of size [PRIME] you want to insert the value at value % [PRIME], if that space is already taken, you'll insert the value in the next available space. This is a very simple form of hashing called a Seperate Chaining Hash Table. ex.

(Toggle Plain Text)

order of entry 3, 5, 9, 2, 7

0 7
1
2 9
3 3
4 2
5 5
6

DoubleHasing Hash tables use a second Hash function to determine the second location in case the first location is already filled. this function can be anything you want, as long as it results in a number between 0 and [PRIME]. Hope this helps

Diz

maybesomeday · Jan 14th, 2005, 10:57 AM

I know about that other mehod but i have to know about and use the direct chaining approach for my course as well, so I was just wondering if the above code managed to insert the words in at the correct points

Dizzutch · Jan 14th, 2005, 6:51 PM

i don;t know, run it and try, if you follow the algorithm it should.

Jan 14th, 2005, 9:56 AM	#1
maybesomeday Newbie Join Date: Dec 2004 Posts: 9 Rep Power: 0	Hash tables For a piece of coursework I am going to use hash tables. I have decdied to try and learn them by just writing a small program to enter data into a hash table and then print out the last thing that was entered. But it is the entry into the hash that is most important. Here is the code I have written: (Toggle Plain Text) #include <stdio.h> #include <stdlib.h> /defien structure and types/ typedef struct list { char word[50]; struct list next; }LIST; typedef LIST P_LIST; P_LIST hash_table[5]; P_LIST insert(char string[],P_LIST head); int hash(char word[]); int main () { int h, i; P_LIST output; char keyword[50], input[50]; for (i=0; i < 7; i++) { printf ("Enter word to put in hash table: "); scanf ("%s", &keyword); h = hash(input); output = hash_table[h]; output = insert(input,output); } printf("%s", output -> word); } /Finds a key value for the word/ int hash(char word[]) { { int i = 0; unsigned sum = 1; unsigned key; while (word[i] != '\0') { sum = sum * word[i]; i++; } key = sum % 5; return key; } } /Inserts into the list pointed to by the hed parameter/ P_LIST insert(char string[],P_LIST head) { P_LIST node; node = malloc(sizeof(LIST)); node -> next = head; head = node; strcpy (node -> word, string); return head; } #include <stdio.h> #include <stdlib.h> /defien structure and types/ typedef struct list { char word[50]; struct list next; }LIST; typedef LIST P_LIST; P_LIST hash_table[5]; P_LIST insert(char string[],P_LIST head); int hash(char word[]); int main () { int h, i; P_LIST output; char keyword[50], input[50]; for (i=0; i < 7; i++) { printf ("Enter word to put in hash table: "); scanf ("%s", &keyword); h = hash(input); output = hash_table[h]; output = insert(input,output); } printf("%s", output -> word); } /Finds a key value for the word/ int hash(char word[]) { { int i = 0; unsigned sum = 1; unsigned key; while (word[i] != '\0') { sum = sum * word[i]; i++; } key = sum % 5; return key; } } /Inserts into the list pointed to by the hed parameter/ P_LIST insert(char string[],P_LIST head) { P_LIST node; node = malloc(sizeof(LIST)); node -> next = head; head = node; strcpy (node -> word, string); return head; } Is this the right way to enter stuff into a hash table or am I doing it wrong? Last edited by big_k105; Jan 14th, 2005 at 9:58 AM. Reason: turned the /code/ tags into [code] tags

Jan 14th, 2005, 10:18 AM	#2
Dizzutch Professional Programmer Join Date: Dec 2004 Location: Worcester, MA Posts: 441 Rep Power: 4	if you have a has table of size [PRIME] you want to insert the value at value % [PRIME], if that space is already taken, you'll insert the value in the next available space. This is a very simple form of hashing called a Seperate Chaining Hash Table. ex. (Toggle Plain Text) order of entry 3, 5, 9, 2, 7 0 7 1 2 9 3 3 4 2 5 5 6 order of entry 3, 5, 9, 2, 7 0 7 1 2 9 3 3 4 2 5 5 6 DoubleHasing Hash tables use a second Hash function to determine the second location in case the first location is already filled. this function can be anything you want, as long as it results in a number between 0 and [PRIME]. Hope this helps Diz __________________ naked pictures of you \| PFO F@H stats Last edited by Dizzutch; Jan 14th, 2005 at 10:20 AM. Reason: typos

Jan 14th, 2005, 6:51 PM	#4
Dizzutch Professional Programmer Join Date: Dec 2004 Location: Worcester, MA Posts: 441 Rep Power: 4	i don;t know, run it and try, if you follow the algorithm it should. __________________ naked pictures of you \| PFO F@H stats

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Jan 14th, 2005, 10:57 AM	#3
maybesomeday Newbie Join Date: Dec 2004 Posts: 9 Rep Power: 0	I know about that other mehod but i have to know about and use the direct chaining approach for my course as well, so I was just wondering if the above code managed to insert the words in at the correct points

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)