Блог

РЕДАКТИРОВАТЬ: я обновил функцию инициализации (код обновлен) для использования malloc, и ошибка сегментации исчезла. Однако сейчас я не получаю выходных данных от функции print table. Далее обновлен код в соответствии с предложениями. Похоже, сейчас это работает.

Я следил за K amp; R (новичок в C) для C и попытался написать хеш-таблицу, используя их пример в разделе 6.7 (с небольшими изменениями)

Код приведен ниже-

 #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 != ''; 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("%st%sn", 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;
}
  

Это приводит к ошибке сегментации, и я понятия не имею, что может быть не так, поскольку в хеш-таблице 101 элемент пространства.

Был бы признателен за любую помощь в отладке проблемы…

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

Заранее спасибо

Исходный код K amp; R предполагает глобальную таблицу. В вашем случае вы пытаетесь выделить его локально, но вы не можете вернуть указатель на локальную переменную (ну, вы можете, но поведение не определено). Вместо этого вам нужно выделить память, используя malloc / или даже лучше, calloc в этом случае:

 listptr * init_table()
{
    listptr *table = calloc(HASHSIZE, sizeof *table);
    return 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 функции лучше сохранить ее так, чтобы она всегда возвращала unsigned int (или size_t !) и выполняла вычисление по модулю вне этой функции. Кроме того, char может быть подписанным или неподписанным; вы, скорее всего, захотите использовать unsigned char s.

Т.е.

 size_t hash (char *s)
{
    size_t hashval;

    for (hashval=0; *s != ''; s  )
        hashval = *(unsigned char*)s   31 * hashval;

    return hashval;
}
  

и

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