Advanced Search

String Hash Table

/ Published in: C
Save to your folder(s)
Implement a hash table for strings

Expand | Embed | Plain Text

Copy this code and paste it in your HTML 
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<string.h>
  4. #define NHASH 29989 //Use a prime number!
  5. #define MULT 31
  6.  
  7. struct node
  8. {
  9. 	char *word;
  10. 	int count;
  11. 	struct node * next;
  12. } node;
  13.  
  14. typedef struct node Node;
  15.  
  16. Node *bin[NHASH];
  17.  
  18. unsigned int hash(char *p)
  19. {
  20. 	unsigned int h = 0;
  21. 	for(; *p; p++)
  22. 		h = MULT * h + *p;
  23. 	return h % NHASH;
  24. }
  25.  
  26. void incword(char *s)
  27. {
  28. 	Node * p;
  29. 	int h = hash(s);
  30. 	for(p = bin[h]; p!= NULL; p = p->next)
  31. 	{
  32. 		if(strcmp(s, p->word) == 0)
  33. 		{
  34. 			(p->count)++;
  35. 			return;
  36. 		}
  37. 	}
  38. 	p = (Node *)malloc(sizeof(node));
  39. 	if(!p)
  40. 		return;
  41. 	p->count = 1;
  42. 	p->word = (char *)malloc(strlen(s)+1);
  43. 	strcpy(p->word, s);
  44. 	p->next = bin[h];
  45. 	bin[h] = p;
  46. }
  47.  
  48. int main()
  49. {
  50. 	char buf[100];
  51. 	for (int i=0; i<NHASH; i++)
  52. 		bin[i] = NULL;
  53. 	while(scanf("%s", buf) == 1)
  54. 		incword(buf);
  55. 	for (int i = 0; i < NHASH; i++)
  56. 		for (Node * p = bin[i]; p != NULL; p = p->next)
  57. 			printf("%s %d\n", p->word, p->count);
  58. 	return 0;
  59. }

Report this snippet


Comments

RSS Icon Subscribe to comments

You need to login to post a comment.