Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <string.h>
- #include <stdlib.h>
- #include <ctype.h>
- #include "util.h"
- #define N 65536
- struct NODE {
- char *line;
- int count;
- struct NODE *next;
- };
- typedef struct NODE NODE;
- struct WORD {
- char *word;
- int count;
- };
- typedef struct WORD WORD;
- /*unsigned int HashLy(const char *str, const int count)
- {
- unsigned int hash = 0;
- for(int i = 0; i < count; i++) {
- hash = (hash * 1664525) + (unsigned char)(str[i]) + 1013904223;
- hash %= N;
- }
- return hash;
- }*/
- unsigned int HashRs(const char *str, const int count)
- {
- static const unsigned int b = 378551;
- unsigned int a = 63689;
- unsigned int hash = 0;
- for (int i = 0; i < count; i++)
- {
- hash = hash*a + (unsigned char)(str[i]);
- a *= b;
- }
- hash %= 65536;
- return hash;
- }
- NODE *create_node(WORD cur_word)
- {
- NODE *tmp = malloc(sizeof(NODE));
- tmp->line = malloc(sizeof(char)*(cur_word.count + 1));
- memcpy(tmp->line,cur_word.word,cur_word.count);
- tmp->line[cur_word.count] = '\0';
- tmp->next = NULL;
- tmp->count = 1;
- return tmp;
- }
- void add_word(NODE **table,WORD cur_word)
- {
- int key = HashRs(cur_word.word,cur_word.count);
- if (table[key] == NULL)
- {
- table[key] = create_node(cur_word);
- }
- else
- {
- NODE *list = table[key];
- while (list->next != NULL)
- {
- if (strncmp(list->line,cur_word.word,cur_word.count) == 0 && list->line[cur_word.count] == '\0')
- {
- list->count++;
- return;
- }
- else list = list->next;
- }
- list->next = create_node(cur_word);
- }
- }
- char *getword(char *string,WORD *cur_word)
- {
- cur_word->word = string;
- cur_word->count = 0;
- char *pointer = string;
- int c;
- for (int i = 0; string[i] != '\0'; i++) {
- if ((c = isalnum(*pointer)) != 0)
- {
- pointer++;
- cur_word->count++;
- }
- else {
- if (cur_word->count == 0) {
- pointer++;
- cur_word->word++;
- }
- else return pointer;
- }
- }
- return NULL;
- }
- /*char *getword(char *string,WORD *cur_word)
- {
- cur_word->word = string;
- cur_word->count = 0;
- for (int i = 0; string[i] != '\0'; i++) {
- if (isalnum(&string[i]) == 0) {
- if ((cur_word->count = &string[i] - cur_word->word) != 0) {
- return &string[i];
- } else {
- cur_word->word = &string[i + 1];
- }
- }
- }
- return NULL;
- } */
- int free_list(NODE *start)
- {
- NODE *i = start;
- NODE *next = NULL;
- for (; i != NULL; i = next) {
- next = i->next;
- free(i->line);
- free(i);
- }
- return 0;
- }
- void free_table(NODE **table)
- {
- for (long long int i = 0; i < N; i++)
- {
- if (table[i] != NULL)
- {
- free_list(table[i]);
- }
- }
- }
- void print_list(NODE *start)
- {
- NODE *lst;
- lst = start;
- while (lst->next != NULL){
- printf("%4d %s\n",lst->count,lst->line);
- lst = lst->next;
- }
- }
- void print_table(NODE **table)
- {
- for (long long int i = 0; i < N; i++)
- {
- if (table[i] != NULL)
- {
- print_list(table[i]);
- }
- }
- }
- int main()
- {
- WORD cur_word;
- NODE **table = malloc(sizeof(*table)*N);
- for (long long int i = 0; i < N; i++)
- {
- table[i] = NULL;
- }
- char *string;
- string = getline_unlim();
- while (string != NULL && !feof(stdin))
- {
- string = convert(string);
- char *tmp = string;
- while (tmp = getword(tmp,&cur_word))
- {
- add_word(table,cur_word);
- }
- string = getline_unlim();
- }
- if (string != NULL)
- {
- string = convert(string);
- char *tmp = string;
- while (tmp = getword(tmp,&cur_word))
- {
- add_word(table,cur_word);
- }
- }
- printf("\n");
- print_table(table);
- free_table(table);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement