Подсчет кластеров в хэш-сетте в c - PullRequest
Новая
       18

Подсчет кластеров в хэш-сетте в c

1 голос
/ 02 марта 2011

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

 void printClusterStats (hashset_ref hashset) {
   int **clusters = (int**)calloc (hashset->length, sizeof(int));
   assert (clusters);
   int ct = 0;
   // i traverses hashset->array
   // ct adds up words in each cluster
   // this loop screws up vvv
   for ( int i = 0; i < hashset->length; ++i) {
      if (hashset->array[i] == NULL) {
         clusters[ct] += 1;
         ct = 0;
      }else {
        ct += 1; 
      }
   }
   clusters[ct] +=1;  //catch an ending cluster

   printf("%10d words in the hash set\n", hashset->load);
   printf("%10d length of the hash array\n", hashset->length);
   for ( int i = 0; i < hashset->length; i++){
      if (clusters[i] == 0) continue;
      else{
         printf("%10d clusters of size %3d\n", clusters[i], i);
      }
   }
   free(clusters);
}

Вывод этой функции выглядит следующим образом: 

        26 words in the hash set
        63 length of the hash array
        96 clusters of size   0
        32 clusters of size   1
        16 clusters of size   2
         4 clusters of size   4
         4 clusters of size   6
       305 clusters of size  33
-703256008 clusters of size  34
-703256008 clusters of size  35

Для моего входного хэш-набора в массиве содержится 26 слов длиной 63 слова.Однако счет как-то сбивается.

РЕДАКТИРОВАТЬ: я подсчитал кластеры вручную и обнаружил, что каждый счет в 4 раза больше, чем должно быть.Что это значит?

Ответы [ 2 ]

2 голосов
/ 02 марта 2011

Эта строка создает массив указателей на int 

int **clusters = (int**)calloc (hashset->length, sizeof(int));

, а не массив int, который вам действительно нужен, если вы храните число кластеров 

int *clusters = (int*)calloc (hashset->length, sizeof(int));

Следовательно, когда высделайте clusters[ct] += 1;, это будет рассматриваться как арифметика указателей, и каждый раз добавляйте 4 к числу кластеров, так как вы находитесь в системе с 4-байтовыми указателями.

0 голосов
/ 02 марта 2011 
int **clusters = (int**)calloc (hashset->length, sizeof(int));

Должно быть 

int *clusters = (int*)calloc (hashset->length, sizeof(int));

Я еще не очень компетентен в c, поэтому не могу объяснить, почему это решило мою проблему. Но вот вам, если вам было любопытно!

Вот правильный вывод 

26 words in the hash set
63 length of the hash array
24 clusters of size   0
 8 clusters of size   1
 4 clusters of size   2
 1 clusters of size   4
 1 clusters of size   6
...