Anagram Solver C

Question

I am totally new to C so I am having troubles with hash table and linked list. I am making an anagram solver. There are many examples I found online but each person has done it differently and rather complicated so I'm really confused now.

I'm pretty okay with the most of the implementation of the program. But I'm actually stuck at the very beginning.

So I need to create a hash table where in each entry, the key is an int and the value is a linked list of words.

The way I get the key, or the hash value, is by converting a word to a number. For example, A is 1, B is 2, C is 3, AB is 3, BC is 5, ABC is 6, and so on. I guess the words should be case insensitive to make things easier.

Below is the code I'm working on. I'm pretty sure is not in the correct syntax. Right now I'm just working on the structure of the table.

typedef struct Entry {
   int key;
   char *word;
   Entry *next;
} Entry;

typedef struct HashTable {
   int size; 
   Entry *entry; 
} HashTable;

// initialize table
HashTable* create(int size) {
   HashTable *table = (HashTable *)malloc(sizeof(HashTable));
   table->entry = (Entry *)malloc(sizeof(Entry) * size);
   table->size = size;

   int i;
   for (i = 0; i < size; i++) {
      table->entry[i].key = 0; // All entries to be 0
   }

   return table;
}

// hash the word
int getHash(char *word)
{
   // How do I implement a loop here
}

void insert(HashTable *table, int key, char *word) {
   int hash = getHash(word);
   int i = 0;

   // if key has already existed, find and add to linked list
   while(table->entry[hash].key != 0 && (i < table->size)) {
      if(table->entry[hash].key == key) {
         table->entry[hash].word = word;
         return; /*  */
      }

      //hash = (hash + 1); // I'm also stuck with incrementing the hash value 
      i++; // increment loop index 
   }

   // if key does not exist, find a '0 slot', and store the key and value
   if(table->entry[hash].key == 0) {
      table->entry[hash].key = key;
      table->entry[hash].word = word;
   }
}

[Obligatory warning about casting the result of malloc in C](http://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc). — Paul R, Jul 06 '15 at 13:19
Why do you pass a `key` to `insert()`? Isn't the hash supposed to act as the key? Also, if you want to do hash-chaining, you probably need to walk along the `.next`-pointers of your liked list. — EOF, Jul 06 '15 at 13:27
I'd change `HashTable* create(int size) {` to `HashTable* create(size_t size) {`, or at the very least: `HashTable* create(unsigned int size) {`. You can't allocate `-1 sizeof *table`, passing a signed int doesn't make much sense if you look at it like that. on how to implement the hash: do a google search for the DJB2 and/or FNV-1a algorithms — Elias Van Ootegem, Jul 06 '15 at 13:39
For details about various hash algorithms [see here](http://programmers.stackexchange.com/a/145633), it's worth the read. The answer is quite comprehensive and does explain what the pro's and cons are of various algorithms nicely — Elias Van Ootegem, Jul 06 '15 at 13:41

Shreevardhan · Answer 1 · 2015-07-06T15:37:52.113

I would suggest start from a rather simple way to find anagrams of a word from text.

int anagrams(char * word, char * text) {
    int bin[256] = { 0 }, m = 0, found = 0, len = 0, c, i;
    for (i = 0; word[i]; i++, bin[c]--, len++) {
        c = word[i];
        if(bin[c] == 0) m++;
    }
    for (i = 0; text[i]; i++) {
        c = text[i];
        if (bin[c] == 0) m++;
        if (bin[c] == -1) m--;
        bin[c]++;
        if (i >= len) {
            c = text[i - len];
            if (bin[c] == 0) m++;
            if (bin[c] == 1) m--;
            bin[c]--;
        }
        if (m == 0) found++;
    }
    return found;
}

Anagram Solver C

1 Answers1