在散列 table 中安装键值时出现分段错误

Question

编辑：我已经更新了 init 函数（代码已更新）以使用 malloc 并且分段错误消失了。但是我现在没有从 print table 函数中得到任何输出。根据建议进一步更新代码。现在好像可以用了。

我一直在关注 C 的 K&R（C 初学者），并尝试使用他们在第 6.7 节中的示例（稍作修改）编写散列table

代码如下-

#include <stdio.h>
#include <string.h>
#include "hashtable.h"

#define HASHSIZE 101


listptr * init_table()
{
    listptr *hashtab = (listptr *) calloc(HASHSIZE, sizeof(*hashtab));
    return hashtab;
}

unsigned hash (char *s)
{
    unsigned hashval;

    for (hashval=0; *s != '[=11=]'; s++)
        hashval = *s + 31 * hashval;

    return hashval % HASHSIZE;
}

listptr lookup (listptr * hashtab, char *s)
{
    listptr np;

    for (np = hashtab[hash(s)]; np!=NULL; np = np->next)
        if (strcmp(s, np->name) == 0)
            return np;
    return NULL;
}

listptr install(listptr * hashtab, char *name, char * defn)
{
    listptr np;

    unsigned hashval;

    if((np = lookup(hashtab, name)) == NULL) {
        np = (listptr) malloc(sizeof(*np));
        if (np==NULL || (np->name = strdup(name))==NULL)
            return NULL;

        hashval = hash(name);
        np->next = hashtab[hashval];
        hashtab[hashval] = np;
    }
    else
    {
        free((void*) np->defn);
    }
    if ((np->defn = strdup(defn)) == NULL)
        return NULL;

    return np;
}

void printtable(listptr * table, int len)
{
    listptr p;
    int i =0;
    while (i < len) {
        if (table[i] != NULL) {
            for (p = table[i];p!=NULL;p=p->next) {
                printf("%s\t%s\n", p->name, p->defn);
            }
        }
        i++;
    }
}

hashtable.h 包含 -

#ifndef HDR
#define HDR

#include <stdlib.h>

typedef struct nlist *listptr;

typedef struct nlist {
    listptr next;
    char *name;
    char *defn;
} Hashtablebucket;

listptr * init_table();
listptr lookup(listptr *, char *);
listptr install (listptr *, char *, char *);
void printtable(listptr *, int );

#endif

在main.c我有-

#include <stdio.h>
#include <string.h>
#include "hashtable.h"

int main()
{
    listptr * table = init_table();


    install(table, "key1", "value1");
    install(table, "key2", "value2");
    install(table, "key3", "value3");

    printtable(table, 101);

    return 0;
}

这会导致分段错误，我不知道会出现什么问题，因为散列 table 具有 space.

的 101 个元素

如果能帮助解决问题，我们将不胜感激...

编辑：上面的代码根本没有输出。有人可以帮忙调试吗？

提前致谢

Answer 1

原始 K&R 代码采用全局 table。在您的情况下，您尝试在本地分配它，但您不能 return 指向局部变量的指针（好吧，您可以，但行为未定义）。相反，您需要使用 malloc/ 或更好的方式分配内存，在这种情况下为 calloc：

listptr * init_table()
{
    listptr *table = calloc(HASHSIZE, sizeof *table);
    return table;
}

最好为散列 table 创建一个结构，这样您就可以拥有不同大小的 table：

struct hashtable {
    size_t n_slots;
    listptr *slots;
};

struct hashtable *init_table(size_t n_slots) {
    struct hashtable *tbl = malloc(sizeof *tbl);
    tbl->n_slots = n_slots;
    tbl->slots = calloc(n_slots, sizeof *(tbl->slots));
    return tbl;
}

对于 hash 函数，最好保留它，使其 return 始终是 unsigned int（或 size_t！），并在外部进行取模那个功能。另外，char 可以是有符号的也可以是无符号的；您很可能想使用 unsigned chars.

即

size_t hash (char *s)
{
    size_t hashval;

    for (hashval=0; *s != '[=12=]'; s++)
        hashval = *(unsigned char*)s + 31 * hashval;

    return hashval;
}

和

hashval = hash(name) % tbl->n_slots;

在散列 table 中安装键值时出现分段错误

Segmentation fault when installing key value in hash table

c

hashtable

segmentation-fault