Posted By

jaircazarin on 10/15/08


Tagged

Algorithms Microsoft-Interview


Versions (?)

Who likes this?

3 people have marked this snippet as a favorite

jaircazarin
sergeizen
skammer


String Hash Table


 / Published in: C
 

Implement a hash table for strings

  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  

You need to login to post a comment.