在 C 中使用哈希表实现符号表

Question

我正在尝试实现一个简单的符号表，该表根据字符串的哈希值将字符串存储在哈希表中。我的程序中的哈希表是指向链表的指针数组。我们有 6 个对应于每个哈希值的链表。

问题是，尽管程序运行，但它会在每次迭代中用新字符串替换旧字符串。

我的代码是..

struct node{
    char *string;
    struct node *next;
};
struct node *hashtable[6];
int calchash(char *arr);
main()
    {
    char *line, a='n';
    int val, i;
            do{
            printf("Enter string:n");
            scanf("%s", line);
            struct node *current;
            struct node *q= (struct node*)malloc(sizeof(struct node));
            q->string = line;
            q->next = NULL;
            val= calchash(line);
            if(hashtable[val] == NULL)
                    {
                    hashtable[val] = q;
                    current =q;}
            else{
                    current->next = q;
                    current = q;
                    }
            printf("Node createdn");
    for(i=0; i<6; i++)
            { printf("Hash value %d :n", i);
            if(hashtable[i]==NULL)
                    {printf("No STRINGS!nn");}
            else
                    {struct node *t = hashtable[i];
                    while(t != NULL)
                            {printf("%s n", t->string);
                            t = t->next;}
                    printf("nn");
                   }
            }
    printf("CONTINUE(y/n):n");
    scanf(" %c", &a);
    }while(a!='n');
    }
int calchash(char *arr)
    {int i=0, ascii;
    int sum=0;
    while(arr[i] != '')
            {ascii = arr[i];
            if(ascii>=48 && ascii<=57)
                    {
                    sum+= 2*ascii;}
            else
                    {sum=sum+ ascii;}
            i++;
            }
    return ((sum*17+5)%6);
    }

输出为：输入字符串：az9

已创建节点

哈希值 0 ：没有字符串！

哈希值 1 ：没有字符串！

哈希值 2 ：az9

哈希值 3 ：没有字符串！

哈希值 4 ：没有字符串！

哈希值 5 ：没有字符串！

继续（是/否）：y

输入字符串：Az9

已创建节点

哈希值 0 ：没有字符串！

哈希值 1 ：没有字符串！

哈希值 2 ：Az9

哈希值 3 ：没有字符串！

哈希值 4 ：Az9

哈希值 5 ：没有字符串！

继续（是/否）：n

有人可以告诉我需要哪些更改才能在哈希值 9 下保留以前的 az2 字符串???

Answer 1

if(hashtable[val] == NULL) {
    hashtable[val] = q;
    current =q;
} else {
    current->next = q;
    current = q;
}

应替换为：

q->next = hashtable[val];
hashtable[val] = q;
// no need for current

此外，通过任何未初始化的指针写入都是 UB，请先分配足够的空间。任何事情都可能发生...

Answer 2

这怎么不会立即崩溃？ line和hashtable都不会初始化。

您需要复制字符串以进入每个哈希节点，可能带有strdup . 目前，所有节点都指向与line相同的字符串缓冲区，因此当您将新字符串读入line时，所有节点都将看到它。 这就是必须为每个节点复制字符串的原因。 我想知道缓冲区在哪里结束，因为你从未初始化过line......

另外，什么是current？ 它是循环的本地，似乎没有必要。 您应该将新节点链接到存储桶的头部，这样就不需要检查存储桶是否为空。

插入

也不会检查字符串是否已存在，因此您将插入重复项。