Хэш-таблица с линейным зондированием

Question

Я пишу хеш-таблицу с линейным зондированием, но моя программа имеет ошибку. Моя задача - записать количество вхождений каждого слова в текст. Например, мой файл содержит следующие слова:

lol lol lol a c d 

Выход является:

(Но d не должно быть 2!) Это происходит, когда SIZE_OF_TABLE 10. И когда SIZE_OF_TABLE является 2 программа не работает. Правда результат должен быть:

lol = 3, a = 1, c = 1, d = 1. 

Мой код:

#include <stdio.h> 
#include <string.h> 
#include <stdlib.h> 
#include <assert.h> 

#define MAX 10 
#define SIZE_OF_TABLE 10 
#define MAX_STRING 256 
#define THAT_OCCUP 0 

struct HT{ 
    int amount; 
    int occup;//occupancy 
    char string[MAX_STRING]; 
}; 

unsigned int long hash(const char *str); 
struct HT* init(int size); 
struct HT* reHT(struct HT* table,int* size,char* word, int* occup); 
struct HT* put(struct HT* table,char* word, int* size,int* occup); 
int take(struct HT* table,char* word, int* size); 



unsigned int long hash(const char *str) // hash function 
{ 
    int long hash = 5381; 
    int c = 0; 

    while (c == *str++) 
     hash = ((hash << 5) + hash) + c; /* hash * 33 + c */ 

    return hash; 
} 

struct HT* init(int size) // create a hash table 
{ 
    struct HT* table = (struct HT*)calloc(sizeof(struct HT*),size); 
    int i = 0; 

    if (size < 1) 
     return NULL; 

    if(NULL == table) 
     return NULL; 

    for (i = 0; i < size; ++i) 
    { 
     table[i].amount = 0; 
     table[i].occup = 1; 
    } 

    return table; 
} 
struct HT* reHT(struct HT* table,int* size,char* word, int* occup) //rehash 
{ 
    assert(table); 
    assert(word); 
    assert(size); 
    assert(occup); 

    table = (struct HT*)calloc(sizeof(struct HT*),(*size)*MAX); 
    int i = 0; 

    while (i < (*size)/MAX) 
    { 
     table = put(table, table[i].string, size, occup); 
     i++; 
    } 
    return table; 
} 

struct HT* put(struct HT* table,char* word, int* size,int* occup) 
{ 
    assert(table); 
    assert(word); 
    assert(size); 
    assert(occup); 

    int i = 0; 

    i = hash(word) % (*size); 

    if ((*occup) > ((*size)/2)) 
     table = reHT(table, size, word, occup); 


    if(1 == table[i].occup) // if free put it 
    { 
     strcpy(table[i].string,word); 
     table[i].amount++; 
     table[i].occup = -1; 
     (*occup)++; 
    } 

    else if (-1 == table[i].occup && strstr(table[i].string,word)) // if place isnt free and it is a similar world just increase amount 
     table[i].amount++; 

    else if (-1 == table[i].occup && !strstr(table[i].string,word)) // if place isnt free and it the words arent similar then use linear probing 
    { 
     i++; 
     while(1) 
     { 
      i = (i + 1) % (*size); 
      if(table[i].occup == 1) 
      { 
       strcpy(table[i].string,word); 
       table[i].amount++; 
       table[i].occup = -1; 
       (*occup)++; 
       break; 
      } 
      else if (-1 == table[i].occup && strstr(table[i].string,word)) 
      { 
       table[i].amount++; 
       break; 
      } 
     } 

     i = 0; // go to start and do the same thing 

     while(1) 
     { 
      if(1 == table[i].occup) 
      { 
       strcpy(table[i].string,word); 
       table[i].amount++; 
       table[i].occup = -1; 
       (*occup)++; 
       break; 
      } 

      else if (strstr(table[i].string,word) && table[i].occup == -1) 
      { 
       table[i].amount++; 
       break; 
      } 

      i++; 
     } 
    } 

    return table; 
} 


int take(struct HT* table,char* word, int* size) // take amount 
{ 
    assert(size); 
    assert(word); 
    assert(table); 

    int i = 0; 

    i = hash(word) % (*size); 

    while(i < (*size)) 
    { 
     if(strstr(table[i].string, word)) 
      return table[i].amount; 
     i++; 
    } 

    i = 0; 

    while(i < (*size)) 
    { 
     if(strstr(table[i].string, word)) 
      return table[i].amount; 
     i++; 
    } 

    return 0; 
} 

int main(int argc, char *argv[]) 
{ 
    FILE* file = fopen("text.txt","r"); 
    struct HT* table = NULL; 
    char string[256] = {0}; 

    int size = SIZE_OF_TABLE; 
    int occup = THAT_OCCUP; 

    if (NULL == file) 
     return -1; 

    table = init(size); //create hash 

    if (NULL == table) 
     return - 1; 

    while(1 == fscanf(file, "%s", string)) // put words to hash table 
    { 
     table = put(table,string,&size,&occup); 
    } 

    printf("HASH_TABLE IS READY!!!!11111\n"); 
    printf("Enter WORDS!!!1111\n"); 

    while(1) 
    { 
     scanf("%s",string); 
     if(strstr(string,"END")) // if you want to stop just enter "END" 
      break; 
     printf(" KOLI4ESTVO!! = %d\n", take(table, string, &size)); 
    } 

    free(table); 
    return 0; 
} 

Answer 1

Когда я составил свой код в первый раз, я только получил два предупреждения - что argc и argv к main() были неиспользованными. Это хорошо сделано - несколько программ, представленных на SO, компилируются, что чисто.

Я создал файл text.txt, содержащий:

lol 
abracadabra 
a 
a 
d 
d 
d 
a 
d 
c 

Когда я запустил программу, оснащенную достаточно, чтобы напечатать какую-то информацию, как она идет (и изменен, чтобы прекратить чисто на EOF), я получил:

$ ./ht 
Adding [lol] 
Adding [abracadabra] 
Adding [a] 
Adding [a] 
Adding [d] 
Adding [d] 
Adding [d] 
Adding [a] 
Adding [d] 
Adding [c] 
HASH_TABLE IS READY!!!!11111 
Enter WORDS!!!1111 
c 
KOLI4ESTVO!! [c] = 9 
d 
KOLI4ESTVO!! [d] = 9 
a 
KOLI4ESTVO!! [a] = 9 
lol 
KOLI4ESTVO!! [lol] = 1 
abracadabra 
KOLI4ESTVO!! [abracadabra] = 9 
$ 

Это странно; Я не создал столько записей ни одного слова. При запуске в valgrind, есть много проблем:

==98849== Invalid write of size 4 
==98849== at 0x100001173: init (ht.c:49) 
==98849== by 0x1000019A9: main (ht.c:188) 
==98849== Address 0x10080b588 is 120 bytes inside an unallocated block of size 2,736 in arena "client" 
==98849== 
==98849== Invalid write of size 4 
==98849== at 0x100001180: init (ht.c:50) 
==98849== by 0x1000019A9: main (ht.c:188) 
==98849== Address 0x10080b58c is 124 bytes inside an unallocated block of size 2,736 in arena "client" 
==98849== 
Adding [lol] 
==98849== Invalid read of size 4 
==98849== at 0x1000015C9: put (ht.c:89) 
==98849== by 0x1000019F1: main (ht.c:196) 
==98849== Address 0x10080b58c is 124 bytes inside an unallocated block of size 2,736 in arena "client" 
==98849== 
==98849== Invalid write of size 1 
==98849== at 0x1003FE3A0: _platform_memmove$VARIANT$Nehalem (in /usr/lib/system/libsystem_platform.dylib) 
==98849== by 0x1001B4113: strcpy (in /usr/lib/system/libsystem_c.dylib) 
==98849== by 0x10000175A: put (ht.c:91) 
==98849== by 0x1000019F1: main (ht.c:196) 
==98849== Address 0x10080b590 is 128 bytes inside an unallocated block of size 2,736 in arena "client" 
==98849== 
==98849== Invalid write of size 4 
==98849== at 0x10000175B: put (ht.c:93) 
==98849== by 0x1000019F1: main (ht.c:196) 
==98849== Address 0x10080b58c is 124 bytes inside an unallocated block of size 2,736 in arena "client" 
==98849== 
…and a whole lot more in a similar vein… 

Быстрый взгляд на init() показывает некоторые проблемы:

struct HT* init(int size) // create a hash table 
{ 
    struct HT* table = (struct HT*)calloc(sizeof(struct HT*),size); 
    int i = 0; 

    if (size < 1) 
     return NULL; 

    if(NULL == table) 
     return NULL; 

    for (i = 0; i < size; ++i) 
    { 
     table[i].amount = 0; 
     table[i].occup = 1; 
    } 

Вы выделяемые массив size указателей, но вы пытаетесь использовать как будто вы выделили массив из size записей struct HT.

Как минимум, вам нужно написать:

struct HT *table = (struct HT *)calloc(sizeof(*table), size); 

Это выделяет массив структур, а не массив указателей.

Исправление, устраняющее ошибки valgrind. Выход еще не правильно, хотя:

$ ./ht 
Adding [lol] 
Adding [abracadabra] 
Adding [a] 
Adding [a] 
Adding [d] 
Adding [d] 
Adding [d] 
Adding [a] 
Adding [d] 
Adding [c] 
HASH_TABLE IS READY!!!!11111 
Enter WORDS!!!1111 
a 
KOLI4ESTVO!! [a] = 9 
lol 
KOLI4ESTVO!! [lol] = 1 
abracadabra 
KOLI4ESTVO!! [abracadabra] = 9 
b 
KOLI4ESTVO!! [b] = 9 
c 
KOLI4ESTVO!! [c] = 9 
d 
KOLI4ESTVO!! [d] = 9 
e 
KOLI4ESTVO!! [e] = 0 
antimony 
KOLI4ESTVO!! [antimony] = 0 
$ 

Я думаю, что я установил, что 9 не случайно, учитывая, что есть 10 строк в файле данных. Когда я уменьшил данные до 6 линий, с помощью всего лишь a повторных, а выход был:

$ ./ht 
Adding [lol] 
Adding [abracadabra] 
Adding [a] 
Adding [d] 
Adding [a] 
Adding [c] 
HASH_TABLE IS READY!!!!11111 
Enter WORDS!!!1111 
a 
KOLI4ESTVO!! [a] = 5 
d 
KOLI4ESTVO!! [d] = 5 
c 
KOLI4ESTVO!! [c] = 5 
abracadabra 
KOLI4ESTVO!! [abracadabra] = 5 
lol 
KOLI4ESTVO!! [lol] = 1 
$ 

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

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