codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
#include <sys/types.h> #include <sys/stat.h> #include <string.h> #include <stdlib.h> #include <ctype.h> #define HASHSIZE 311 #define MAXLINE 1024 typedef struct HashTableNode { char *sortedWord; char *word; struct HashTableNode* next; }hashtable; static hashtable *hashtab[HASHSIZE]; static FILE* open_file(char *filename); static int getline(char *s, int lim, FILE *fp); static char* getword(char *s, const char *sep); static int strcasecmp(char *s, char *t); static void sort_word(char *s); static unsigned int hash(char *s); static void insert(char *word); static hashtable* lookup(char *word); static void print_anagrams_imp(char *word); int print_anagrams(char *dict, char *word) { FILE *fp; char line[MAXLINE]; char *sep = "!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~\t \n"; /* open input dictionary */ fp = open_file(dict); if(fp == NULL) return 0; /* read line until EOF */ while(getline(line, sizeof(line), fp)) { char *p; /* read word until EOL */ for(p = getword(line, sep); p; p = getword(NULL, sep)) /* insert in hash table */ insert(p); } /* lookup the anagrams of given word in hash table and print them */ print_anagrams_imp(word); return 1; } static void print_anagrams_imp(char *word) { hashtable *p; char *sorted_word; sorted_word = strdup(word); sort_word(sorted_word); for(p = hashtab[hash(sorted_word)]; p; p = p->next) if(strcasecmp(sorted_word, p->sortedWord) == 0) printf("%s ", p->word); printf("\n\n"); } /* sorting using insertion sort */ static void sort_word(char *s) { char *p, *q, c; if(s == NULL || s[0] == '\0' || s[1] == '\0') return; /* move smallest character to left */ for(p = s+1, q = s; *p != '\0'; p++) if(tolower(*q) > tolower(*p)) q = p; /* swap q with s */ c = *s; *s = *q; *q = c; /* sort the word */ for(p = s+1; *p != '\0'; p++) { for(q = p-1, c = *p; tolower(*q) > tolower(c); q--) *(q+1) = *q; *(q+1) = c; } } static unsigned int hash(char *s) { unsigned hashval; for (hashval = 0; *s != '\0'; s++) hashval = tolower(*s) + 31 * hashval; return hashval % HASHSIZE; } static void insert(char *word) { hashtable *p; char *sorted_word; unsigned int val; if(lookup(word) == NULL) { sorted_word = strdup(word); sort_word(sorted_word); p = (hashtable*)malloc(sizeof(*p)); if(p == NULL) { printf("memory allocation error"); exit(1); } p->word = strdup(word); p->sortedWord = strdup(sorted_word); val = hash(sorted_word); p->next = hashtab[val]; hashtab[val] = p; free(sorted_word); } } static hashtable* lookup(char *word) { hashtable *p; char *sorted_word; sorted_word = strdup(word); sort_word(sorted_word); for(p = hashtab[hash(sorted_word)], free(sorted_word); p; p = p->next) if(strcasecmp(word, p->word) == 0) return p; return NULL; } static int strcasecmp(char *s, char *t) { for(; tolower(*s) == tolower(*t); s++, t++) { if(*s == '\0') return 0; } return *s - *t; } static FILE* open_file(char *filename) { struct _stat buffer; int status; FILE *fp; /* check file status */ status = _stat(filename, &buffer); /* file doesn't exist */ if(status != 0) return NULL; /* path specifies an ordinary file and the file has read permission */ if((buffer.st_mode & _S_IFREG) && (buffer.st_mode & _S_IREAD)) { /* file is empty */ if(buffer.st_size == 0) return NULL; /* open file in read mode */ fp = fopen(filename, "r"); if(fp == NULL) return NULL; return fp; } return NULL; } static int getline(char *s, int lim, FILE *fp) { int i; char c; for(i = 0; i < (lim-1) && (c = getc(fp)) != EOF && c != '\n'; i++) s[i] = c; if(c == '\n') s[i++] = c; s[i] = '\0'; return i; } static char* getword(char *s, const char *sep) { char *p, *tokenptr; /* static pointer pointing to the current position in s */ static char *currentp = NULL; /* if s is not NULL, point currentp to starting of NULL */ if(s != NULL) currentp = s; /* when the function is called for the first time and s is NULL, return NULL */ if(s == NULL && currentp == NULL) return NULL; /* bypass the initial seperator characters */ for(p = currentp; *p != '\0'; p++) { const char *sep_p; /* check if the character is seperator */ for(sep_p = sep; *sep_p != '\0'; sep_p++) { if(*sep_p == *p) break; } if(*sep_p == '\0') break; /* if character other then separator is found, break out of the loop */ } /* end of string is reached */ if(*p == '\0') { currentp = NULL; return NULL; } /* find the next seperator character */ for(tokenptr = p; *p != '\0'; p++) { const char *sep_p; for(sep_p = sep; *sep_p != '\0'; sep_p++) { if(*sep_p == *p) break; } if(*sep_p != '\0') break; /* if the character is separator then break out of loop */ } if(*p == '\0') currentp = p; else { currentp = p+1; *p = '\0'; } return tokenptr; }
Private
[
?
]
Run code
Submit