Edytuj: Zaktualizowałem funkcję init (zaktualizowany kod), aby użyć Malloc, a błąd segmentacji zniknął. Jednak nie dostaję teraz wyjścia z funkcji tabeli druku. Ponadto zaktualizowano kod zgodnie z sugestiami. Wydaje się teraz pracować.

Przestrzegałem K & R (początkujący w c) dla C i próbowałem pisać hashtable przy użyciu ich przykładu w sekcji 6.7 (z kilkoma modyfikacjami)

Kod jest poniżej

#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 != '\0'; 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 zawiera -

#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

W Main.C mam -

#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;
}

Powoduje to błąd segmentacji i nie mam pojęcia, co może być nie tak, ponieważ hashtable ma 101 elementów przestrzeni.

Doceniłoby jakąkolwiek pomoc w debugowaniu problemu ...

Edytuj: Wraz z powyższym kodem nie ma wyjścia. Czy ktoś mógłby pomóc w debugowaniu?

Z góry dziękuję

-1
g0d 4 październik 2020, 17:09

1 odpowiedź

Najlepsza odpowiedź

Oryginalny kod K & Amp; R zakłada globalną tabelę. W twoim przypadku próbujesz przydzielić go lokalnie, ale nie można zwrócić wskaźnika do zmiennej lokalnej (cóż, możesz, ale zachowanie jest niezdefiniowane). Zamiast tego musisz przydzielić pamięć za pomocą malloc / lub nawet lepszego, calloc w tym przypadku:

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

Korzystnie byłoby wykonanie tabeli Hash struktury , dzięki czemu możesz mieć tabele różnych rozmiarów:

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;
}

Funkcja hash, lepiej jest zachować ją tak, że zwróci unsigned int (lub size_t!) Zawsze i wykonaj modulo poza tym funkcją. Również char może być podpisany lub niepodpisany; Najprawdopodobniej chcesz użyć unsigned char s.

To znaczy.

size_t hash (char *s)
{
    size_t hashval;

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

    return hashval;
}

I

hashval = hash(name) % tbl->n_slots;
2
Antti Haapala 4 październik 2020, 15:52