Решатель анаграмм C

Я совершенно новичок в C, поэтому у меня проблемы с хэш-таблицей и связанным списком. Я делаю решатель анаграмм. Есть много примеров, которые я нашел в Интернете, но каждый человек сделал это по-своему и довольно сложно, поэтому сейчас я действительно запутался.

Меня вполне устраивает большая часть реализации программы. Но на самом деле я застрял в самом начале.

Поэтому мне нужно создать хеш-таблицу, в которой в каждой записи ключ представляет собой целое число, а значение представляет собой связанный список слов.

Я получаю ключ или хеш-значение путем преобразования слова в число. Например, A равно 1, B равно 2, C равно 3, AB равно 3, BC равно 5, ABC равно 6 и так далее. Я думаю, что слова должны быть нечувствительны к регистру, чтобы упростить задачу.

Ниже приведен код, над которым я работаю. Я почти уверен, что это неправильный синтаксис. Сейчас я просто работаю над структурой таблицы.

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;
   }
}

person PTN    schedule 06.07.2015    source источник
comment
Почему вы чувствуете необходимость увеличивать значение хеш-функции?   -  person EOF    schedule 06.07.2015
comment
Хм хороший момент. Мне нужно только увеличить i.   -  person PTN    schedule 06.07.2015
comment
Почему вы передаете key insert()? Разве хэш не должен действовать как ключ? Кроме того, если вы хотите сделать хеш-цепочку, вам, вероятно, придется пройтись по .next-указателям вашего любимого списка.   -  person EOF    schedule 06.07.2015
comment
Я бы изменил HashTable* create(int size) { на HashTable* create(size_t size) { или, по крайней мере, на HashTable* create(unsigned int size) {. Вы не можете выделить -1 sizeof *table, передача подписанного целого числа не имеет особого смысла, если вы посмотрите на это так. о том, как реализовать хэш: поищите в Google алгоритмы DJB2 и/или FNV-1a.   -  person Elias Van Ootegem    schedule 06.07.2015
comment
Подробнее о различных алгоритмах хеширования см. здесь, это стоит прочесть. Ответ довольно исчерпывающий и хорошо объясняет плюсы и минусы различных алгоритмов.   -  person Elias Van Ootegem    schedule 06.07.2015
comment
Вы также забыли задать вопрос.   -  person WhozCraig    schedule 06.07.2015


Ответы (1)


Я бы предложил начать с довольно простого способа найти anagrams из word из 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;
}
person Shreevardhan    schedule 06.07.2015