在哈希集中计算集群

我正在尝试调试哈希集实现（对于学校作业）。碰撞正在通过线性探测进行管理，我需要为调试例程计算给定大小的簇的数量。我的工作这件事：在哈希集中计算集群

// really just hoping that a 50+ cluster doesn't occur 
int clusters[50]; 
int count = 0; 
for (int i=0; i < hashset->dim; i++) { 
    if (hashset->array[i] != NULL) { 
     count++; 
    } else { 
     if (count == 0) continue; 
     if (clusters[count] == NULL) clusters[count] = 0; 
     clusters[count]++; 
     count = 0; 
    } 
} 
for (int i=1; i < 50; i++) { 
    if (clusters[i] != NULL && clusters[i] != 0) 
     printf("%d clusters of size %d\n", clusters[i], i); 
}

似乎是有道理的，但是当我运行它，我得到...

25143 entries in hashset 
50286 dimension of the hash array 
4585 clusters of size 1 
2134 clusters of size 2 
1102 clusters of size 3 
696 clusters of size 4 
388 clusters of size 5 
264 clusters of size 6 
173 clusters of size 7 
104 clusters of size 8 
89 clusters of size 9 
51 clusters of size 10 
46 clusters of size 11 
35 clusters of size 12 
26 clusters of size 13 
22 clusters of size 14 
17 clusters of size 15 
134553327 clusters of size 16 
134634407 clusters of size 17 
112 clusters of size 18 
6 clusters of size 19 
134553324 clusters of size 20 
134634399 clusters of size 21 
107 clusters of size 22 
3 clusters of size 23 
2 clusters of size 24 
134634401 clusters of size 25 
107 clusters of size 26 
134107784 clusters of size 27 
134556210 clusters of size 28 
[... more nonsense]

所以最初它似乎给理智的输出..大量的集群，但无论。我的想法是，这种太大的数字实际上应该是0--它们是实际上并不存在的集群，但由于某种原因仍然被打印出来。我只是不知道为什么...

来源

2010-02-26 Pete

这里是一个简短的C程序：

#include <stdio.h> 
int main() { 
    char buf[20]; 
    for (int i = 0; i < 20; i++) { 
    printf("%d ", buf[i]); 
    } 
    printf("\n"); return 0; 
}

仔细想想它应该当你运行它来打印。

每次运行它时都会打印相同的东西吗？
在每台机器上运行它？下面

剧透：

(spoiler padding) 













.

这里是我看到它打印了一个运行：0 0 0 0 0 0 0 0 -128 5 64 0 0 0 0 0 -16 -60 -55 31

同样的错误折磨了我们的计划，但它可能是更容易在我看到的。

来源

2010-02-26 08:39:01

你写

他们这实际上不存在但出于某些原因仍然得到印刷

你隐含假设元素clusters[i]不群如果您未分配给它，则存在。但这是而不是是真的。无论您是否为其分配值，clusters阵列中的每个值都一直存在。如果你没有指定一个已知值，这个值是不可预知的，可能是134634399.所以，如果你想让所有clusters中的元素都可以预测，你需要做什么？

C'S内存模型的这种误解导致了下面的代码（从你的问题摘录）：

int clusters[50]; 
/* ... */ 
for (int i=1; i < 50; i++) { 
    if (clusters[i] != NULL && clusters[i] != 0) 
     printf("%d clusters of size %d\n", clusters[i], i); 
}

什么是测试clusters[i] != NULL的目的是什么？您正试图决定是否已将我所省略的循环设置为clusters[i]，但是根据NULL进行测试无法做到这一点。 clusters的元素不是某种类型的指针，它们是原始的4字节整数值。他们总是有一定的价值，但除非你设置他们的东西，这个值是不可预知的。

来源

2010-02-28 04:59:33

在哈希集中计算集群

回答

相关问题