c-链式哈希表的问题

Question

我在弄清楚如何正确执行此操作时遇到了重大困难。直到不久，输出仍然充满了错误。我设法修复了其中的大部分，但仍然留下了两个，很可能还有一堆逻辑错误。

我的哈希算法也有问题，所以我用简单的临时代码替换了它。正确的说明是：

要使用的哈希函数是h(k)=m(k·A mod 1)，其中A=(√5−1)/2，k·A mod 1返回k·A的小数部分。

我认为我没有正确地实现它。

这是代码：

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define TABLE_SIZE 8
typedef struct stItem item;
struct stItem {
int key;
item *next;
};
void init(item * H[]) {
int i = 0;
for (i; i < TABLE_SIZE; i++)
H[i] = NULL;
}
int h(int k) {
// this does not work at all, currently using testcode
/*
int m = TABLE_SIZE;
int A = ( sqrt(5.0) - 1) / 2;
return m * (k * A % 1);
*/
return k % TABLE_SIZE;
}
void insert(int key, item * H[]) {
int keyHashed = h(key);
if (H[keyHashed] == NULL) {
item * temp = malloc(sizeof(item));
temp->key = key;
temp->next = NULL;
H[keyHashed] = temp;
free(temp);
}
else {
item * temp = malloc(sizeof(item));
temp->next = H[keyHashed]->next;
while (temp != NULL) {
temp = temp->next;
}
temp->key = key;
temp->next = NULL;
}
}
int search(int key, item * H[]) {
int keyHashed = h(key);
if (H[keyHashed] == NULL)
return -1;
else if (H[keyHashed]->key != key) {
item * temp = malloc(sizeof(item));
temp->next = H[keyHashed]->next;
while (temp->key != key && temp != NULL)
temp = temp->next;
if (temp->key == key) {
free(temp);
return keyHashed;
}
else {
free(temp);
return -1;
}
}
else
return keyHashed;
}
void printHash(item * H[]) {
printf("Table size: %d", TABLE_SIZE);
int i = 0;
for (i; i < TABLE_SIZE; i++) {
if (H[i] != NULL) {
printf("i: %d          key: %d",i,H[i]->key);
if (H[i]->next != NULL) {
item * temp = malloc(sizeof(item));
temp->next = H[i]->next;
while (temp != NULL) {
printf(" -> %d", temp->key);
}
printf("n");
}
else
printf("n");
}
}
}
void test() {
// a)
int array[7] = {111,10112,1113,5568,63,1342,21231};
item *h[TABLE_SIZE];
init(h);
int i = 0;
for (i; i < 7; i++)
insert(array[i], h);

// b)
printHash(h);

// c)
printf("Search result for 1: %d", search(1, h));
printf("Search result for 10112: %d", search(10112, h));
printf("Search result for 1113: %d", search(1113, h));
printf("Search result for 5568: %d", search(5568, h));
printf("Search result for 337: %d", search(337, h));
}
int main() {
test();
}

编辑：多亏了user3386109的修复，代码现在编译时没有任何错误，但实际情况是，命令提示符弹出时没有显示任何内容，也没有发生任何事情。它也不关闭。即使等了几分钟也不会。

编辑2：经过更多的测试，它似乎挂断了插入函数。test()中的for循环之后不执行任何操作。

如果我在测试函数中把这个printf("init done %d", h[1]);添加到init()之后，我得到的是"init done 0"而不是"init doe NULL"，这可能是问题之一吗？

Answer 1

结构定义格式错误。我建议使用以下

typedef struct stItem item; 
struct stItem {
int key;
item *next;
};