Hash, use shift-folding snip #include <stdio.h> #include <error.h> #include <string.h> #include <stdlib.h> #define MAXLINE 128 #define HTABSIZE 101 #define NSHIFT 3 struct hnode { int pos; char *key; struct hnode *next; }; typedef struct hnode *hashtable[HTABSIZE]; int htab_key(char *key); int htab_getval(hashtable h, char *key); void htab_insert(hashtable h, char *key, int pos); void htab_dump(hashtable htab); void htab_free(hashtable htab); int main(int argc, char *argv[]) { char line[MAXLINE]; hashtable htab = {0}; int len = 0; int i = 0; int retv = 0; if(argc != 2) error(1, 0, "querry < input.txt"); while(fgets(line, MAXLINE, stdin) != NULL) { /* strip newlines */ len = strlen(line); if(line[len - 1] == '\n') line[--len] = '\0'; if(len > 2) htab_insert(htab, line, i++); } if((retv = htab_getval(htab, argv[1])) == -1) printf("NOT found: `%s', `%d'\n", argv[1], retv); else printf("FOUND: `%s' at `%d'\n", argv[1], retv); /* htab_dump(htab); */ htab_free(htab); return 0; } int htab_key(char *key) { char *ptr = NULL; int retv = 0; int i = 0; int x = 0; for(ptr = key; *ptr; retv += x) for(i = 0, x = 0; i < NSHIFT && *ptr; i++, ptr++) x = x * 10 + *ptr; retv %= HTABSIZE; return retv; } void htab_insert(hashtable htab, char *key, int pos) { struct hnode *ptr = (struct hnode *)malloc(sizeof(struct hnode)); int index = htab_key(key); ptr->key = strdup(key); ptr->pos = pos; ptr->next = htab[index]; htab[index] = ptr; return; } int htab_getval(hashtable htab, char *key) { struct hnode *ptr = {0}; for(ptr = htab[htab_key(key)]; ptr && strcmp(ptr->key, key); ptr = ptr->next) ; if(ptr) return ptr->pos; else return -1; } void htab_dump(hashtable htab) { struct hnode *ptr = {0}; int i = 0; for(i = 0; i < HTABSIZE; i++) { printf("[%02d]: ", i); for(ptr = htab[i]; ptr; ptr = ptr->next) { printf("[%d] -> %s", ptr->pos, ptr->key); } printf("\n"); } return; } void htab_free(hashtable htab) { struct hnode *ptr = {0}; struct hnode *tmp = {0}; int i = 0; for(i = 0; i < HTABSIZE; i++) { for(ptr = htab[i]; ptr; ptr = ptr->next) { if(ptr->next != NULL) { free(ptr->key), tmp = ptr->next; free(ptr), ptr = tmp; } } } return; }
No comments: