Create c a program that stores words in a Hash Table and then searches for the w

Question

Create c a program that stores words in a Hash Table and then searches for the words.

Requirements
You will keep track of words that are 20 or fewer characters long. The nodes that you will create as structs will contain an array of char of length 21 and a pointer to the next node. Call this struct WordNode.

In main, declare an array variable to contain your hash table. Let the array buckets contain pointers to WordNodes. The size of the array is 11.

Create a loop that gets one word at a time from the user until they enter "." as the only thing on the input line.

Each time you get a word, pass the word as a parameter to a hash function. This hash function must call the djb2 function (from the sample code below and change the parameter to work with chars rather than unsigned chars) and then use the Division Method to return a value between 0 and 10 (inclusive) as a hash value. Use this returned hash value to determine which bucket should contain the word. Then add the word to the bucket as described in lecture. Make sure that your linked lists are sorted linked lists, sorted in ascending order (e.g. "alpha" would occur before "theta"). They do not have to have a tail or prev pointers but they can if you want (the tail pointer would now have to be in the bucket along with the head pointer).

Once the user is done entering words, set up a separate loop to get input for words to search for. Then search for the words in the hash table by determining the appropriate bucket and searching the linked list found there (if there is one). Every time you do a comparison in your search, use printf() (or cout) to display the word you are comparing your search word against. When you find the word, use printf() to display "Success!". If you don't find the word, use printf() to display "Not there!". This will continue in a loop until the user enters "." as the only thing on the input line.

You should comment as normal.

Call your primary source file mini3.c. Put your linked list code into linkedList.c (or linkedList.h if you use a class). Put your djb2 and hash functions into djb2.c. Put any other code into your already-existing mini3.c. You can create any .h files you need in order to support this but do not create any other .c files.

this is the hash function djb2 (Created by Dan Bernstein)
unsigned long hash(unsigned char *str)
{
unsigned long hash = 5381;
int c = 0;
while ((c = *str++) != ‘’)
hash = ((hash << 5) + hash) + c;
return hash;
}

no extra files or functions are neee

Explanation / Answer

Here is your code. You can modify this code as per your requirement.

/*********************************/

/*
============================================================================
Name        : hashC.c
Author      :
Version     :
Copyright   : Your copyright notice
Description : Hello World in C, Ansi-style
============================================================================
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct WordNodes{
   char word[21];
   struct WordNodes* next;
}WordNodes;

unsigned long hash(char *str)
{
   unsigned long hash = 0;
   int c = 0;
   while ((c = *str++) != '')
   hash = hash + c;
   return hash%11;   //return index 0 to 10
}
//Create a node
WordNodes* createNode(char* value){
   WordNodes* ptr=(WordNodes*)malloc(sizeof(WordNodes));
   strcpy(ptr->word,value);
   ptr->next=NULL;
   return ptr;
}

//Insert in linkedlist
void insertSorted(WordNodes** head,char* value){
   if(*head==NULL){
       *head=createNode(value);
       return;
   }
   WordNodes* ptr=*head;
   if(value<ptr->word){
       WordNodes* tmp=createNode(value);
       tmp->next=ptr;
       *head=tmp;
   }
   else{
       while(ptr->next!=NULL){
           if(value>ptr->next->word)
           ptr=ptr->next;
           else
               break;
       }
       WordNodes* tmp=createNode(value);
       tmp->next=ptr->next;
       ptr->next=tmp;
   }

}
//Search function
int search(WordNodes* head,char* value)
{
   if(head==NULL)
       return 0;
   WordNodes* ptr=head;
   while(ptr!=NULL){
       if(!strcmp(value,ptr->word))//COMPARE THE STRING
           return 1;
       ptr=ptr->next;

   }
   return 0;
}

void printList(WordNodes* head){
   WordNodes* ptr=head;
   while(ptr){
       printf("%s->",ptr->word);
       ptr=ptr->next;
   }
   printf(" ");
}
int main(void) {
   char word[21];
   int index;
   WordNodes* arrbuck[11]={NULL};
   while(1)
   {
   printf("Enter a word: ");
   fgets(word,21,stdin);
   if(word[0]=='.')
       break;
   char* ptr=strtok(word," ");   //REMOVE THE
   index=hash(ptr);   //get index 0 to 10
   insertSorted(&arrbuck[index],ptr);   //insert in list
   }
   int i;
   for(i=0;i<10;i++)
   printList(arrbuck[i]);
   while(1)
   {
   printf("Enter a word to search: ");
   fgets(word,21,stdin);
   if(word[0]=='.')
       break;
   char* ptr=strtok(word," ");
   index=hash(ptr);
   if(search(arrbuck[index],ptr))   //check if search found
       printf("Success ");
   else
       printf("Not there ");
   }
   return EXIT_SUCCESS;
}

/*****************************/output

Enter a word: Tanmay
Enter a word: Kanti
Enter a word: Biswas
Enter a word: Tamil
Enter a word: Karnataka
Enter a word: Bangalore
Enter a word: Kolkata
Enter a word: .

Biswas->
Tanmay->

Bangalore->

Kolkata->
Kanti->Tamil->Karnataka->

Enter a word to search: Tamil
Success
Enter a word to search: Kanti
Success
Enter a word to search: Kunti
Not there
Enter a word to search: Karnataka
Success
Enter a word to search: .

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.