Advertisement
Guest User

выфвфы

a guest
Oct 28th, 2016
60
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 3.87 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <stdlib.h>
  4. #include <ctype.h>
  5. #include "util.h"
  6.  
  7. #define N 65536
  8.  
  9. struct NODE {
  10.         char *line;
  11.         int count;
  12.         struct NODE *next;
  13. };
  14. typedef struct NODE NODE;
  15.  
  16. struct WORD {
  17.         char *word;
  18.         int count;
  19. };
  20. typedef struct WORD WORD;
  21.  
  22. /*unsigned int HashLy(const char *str, const int count)
  23. {
  24.     unsigned int hash = 0;
  25.     for(int i = 0; i < count; i++) {
  26.     hash = (hash * 1664525) + (unsigned char)(str[i]) + 1013904223;
  27.         hash %= N;
  28.     }
  29.     return hash;
  30. }*/
  31.  
  32. unsigned int HashRs(const char *str, const int count)
  33. {
  34.     static const unsigned int b = 378551;
  35.     unsigned int a = 63689;
  36.     unsigned int hash = 0;
  37.     for (int i = 0; i < count; i++)
  38.     {
  39.     hash = hash*a + (unsigned char)(str[i]);
  40.     a *= b;
  41.     }
  42.     hash %= 65536;
  43.     return hash;
  44.  
  45. }
  46.  
  47. NODE *create_node(WORD cur_word)
  48. {
  49.     NODE *tmp = malloc(sizeof(NODE));
  50.     tmp->line = malloc(sizeof(char)*(cur_word.count + 1));
  51.     memcpy(tmp->line,cur_word.word,cur_word.count);
  52.     tmp->line[cur_word.count] = '\0';
  53.     tmp->next = NULL;
  54.     tmp->count = 1;
  55.     return tmp;
  56. }
  57.  
  58. void add_word(NODE **table,WORD cur_word)
  59. {
  60.     int key = HashRs(cur_word.word,cur_word.count);
  61.     if (table[key] == NULL)
  62.     {
  63.     table[key] = create_node(cur_word);
  64.     }
  65.     else
  66.     {
  67.     NODE *list = table[key];
  68.     while (list->next != NULL)
  69.     {
  70.         if (strncmp(list->line,cur_word.word,cur_word.count) == 0 && list->line[cur_word.count] == '\0')
  71.         {
  72.         list->count++;
  73.             return;
  74.         }
  75.         else list = list->next;
  76.     }
  77.     list->next = create_node(cur_word);
  78.     }
  79. }
  80.  
  81. char *getword(char *string,WORD *cur_word)
  82. {
  83.     cur_word->word = string;
  84.     cur_word->count = 0;
  85.     char *pointer = string;
  86.     int c;
  87.     for (int i = 0; string[i] != '\0'; i++) {
  88.     if ((c = isalnum(*pointer)) != 0)
  89.             {
  90.         pointer++;
  91.         cur_word->count++;
  92.             }
  93.     else {
  94.         if (cur_word->count == 0) {
  95.         pointer++;
  96.         cur_word->word++;
  97.         }
  98.         else return pointer;
  99.         }  
  100.     }
  101.     return NULL;    
  102. }
  103.  
  104. /*char *getword(char *string,WORD *cur_word)
  105. {
  106.     cur_word->word = string;
  107.     cur_word->count = 0;
  108.     for (int i = 0; string[i] != '\0'; i++) {
  109.     if (isalnum(&string[i]) == 0) {
  110.         if ((cur_word->count = &string[i] - cur_word->word) != 0) {
  111.         return &string[i];
  112.         } else {
  113.         cur_word->word = &string[i + 1];
  114.         }
  115.         }  
  116.     }
  117.     return NULL;
  118. } */
  119.  
  120. int free_list(NODE *start)
  121. {
  122.     NODE *i = start;
  123.     NODE *next = NULL;
  124.     for (; i != NULL; i = next) {
  125.         next = i->next;
  126.         free(i->line);
  127.         free(i);
  128.     }
  129.     return 0;
  130. }
  131.  
  132. void free_table(NODE **table)
  133. {
  134.     for (long long int i = 0; i < N; i++)
  135.     {
  136.         if (table[i] != NULL)
  137.         {
  138.             free_list(table[i]);
  139.         }
  140.     }
  141. }
  142.  
  143.  
  144. void print_list(NODE *start)
  145. {
  146.     NODE *lst;
  147.     lst = start;
  148.     while (lst->next != NULL){
  149.             printf("%4d %s\n",lst->count,lst->line);
  150.             lst = lst->next;
  151.     }
  152. }
  153.  
  154. void print_table(NODE **table)
  155. {
  156.     for (long long int i = 0; i < N; i++)
  157.     {
  158.     if (table[i] != NULL)
  159.     {
  160.         print_list(table[i]);
  161.     }
  162.     }
  163. }
  164.  
  165. int main()
  166. {  
  167.     WORD cur_word;
  168.     NODE **table = malloc(sizeof(*table)*N);
  169.     for (long long int i = 0; i < N; i++)
  170.     {
  171.         table[i] = NULL;
  172.     }
  173.     char *string;
  174.     string = getline_unlim();
  175.     while (string != NULL && !feof(stdin))
  176.     {
  177.         string = convert(string);
  178.         char *tmp = string;
  179.     while (tmp = getword(tmp,&cur_word))
  180.     {
  181.         add_word(table,cur_word);
  182.     }
  183.     string = getline_unlim();
  184.     }
  185.     if (string != NULL)
  186.     {
  187.     string = convert(string);
  188.         char *tmp = string;
  189.         while (tmp = getword(tmp,&cur_word))
  190.         {
  191.      
  192.             add_word(table,cur_word);
  193.         }
  194.  
  195.     }
  196.     printf("\n");
  197.     print_table(table);
  198.     free_table(table);
  199.     return 0;
  200. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement