Проблема выделения памяти в HashTable

Question

Пожалуйста, не закрывайте это, говоря дубликат вопроса . Я сделал важное изменение, чтобы не вводить людей в заблуждение, я представил эти более четкие коды.

Пожалуйста, помогите мне решить эту проблему выделения памяти. Я работаю над HashTable, и это то, что у меня есть (только частичные коды)

main.c

HashTablePtr hash;
hash = createHashTable(10);
insert(hash, "hello");
insert(hash, "world");

HashTable.c

    HashTablePtr createHashTable(unsigned int capacity){
    HashTablePtr hash;
    hash = (HashTablePtr) malloc(sizeof(HashTablePtr));
    hash->size = 0;
    hash->capacity = capacity;          
    hash->list = (ListPtr *)calloc(capacity, sizeof(List)); /*NO MEMORY ALLOCATION HERE*/
    return hash;

list.h

typedef struct list List;
typedef struct list * ListPtr;

struct list {
    int size;
    NodePtr head;
    NodePtr tail;
};
...
...

HashTable.h

    typedef struct hashtable * HashTablePtr;
    typedef struct hashtable HashTable;
    struct hashtable {
        unsigned int capacity;
        unsigned int size;
        ListPtr *list;
        unsigned int (*makeHash)(unsigned int, void *);
    };
...
...

Когда я запускаю свой отладчик (отладчик Netbeans C / C ++, я не вижу выделенной памяти для hash-> list. В приведенном выше примере я пытаюсь сделать его массивом из 10 списков.

Пожалуйста, помогите мне решить эту проблему.

Я не такой эксперт в Си, если это поможет.

Answer 1

Одна хорошая идиома, которую вы также можете использовать, например:

hash = (HashTablePtr) malloc(sizeof(*hash));

Не жестко кодируя какие-либо типы в распределении, возможность путаницы значительно уменьшается.

Обратите внимание, что здесь хеш не разыменовывается - sizeof () всегда вычисляется во время компиляции, поэтому компилятор просто выясняет, какой тип * хэш / будет / иметь, и получает его размер.

Answer 2

Эта строка

hash = (HashTablePtr) malloc(sizeof(HashTablePtr));

следует читать

hash = (HashTablePtr) malloc(sizeof(HashTable));

Я также предлагаю вам следовать совету, который был дан вам в предыдущем посте, и НЕ скрывать указатели с помощью typedef'ing. Просто используйте List *

[Всякий раз, когда вы видите оператор alloc, тип, который вы назначаете, является указателем, а тип, который вы выделяете, должен иметь тип (а не указатель на тип)]

Answer 3

В этой строке:

hash->list = (ListPtr *)calloc(capacity, sizeof(List));

Функция calloc выделит некоторую память для List, а затем вернет указатель на выделенную память, который будет List* (или эквивалентен ListPtr из-за typedef.)

В коде указатель затем приводится к (ListPtr*), который на самом деле будет List**, который не является ожидаемым типом List*. Поэтому измените ListPtr* на ListPtr и посмотрите, исправит ли это эту строку.

Редактировать

Как отметили в комментариях Лейз и Клатзацт, тип Hashtable.list равен ListPtr* или List**:

struct hashtable {
    ...
    ListPtr *list;

Это может быть причиной того, что попытка присвоить тип ListPtr, возвращенный и приведенный из calloc, приведет к ошибке компилятора. Вместо того, чтобы хранить указатель на указатель списка в Hashtable, он должен просто содержать указатель на список:

struct hashtable {
    ...
    ListPtr list;

Это должно устранить ошибку компилятора, так как тип Hashtable.list и typecast оба будут ListPtr.

Answer 4

Лично я не большой поклонник использования typedefs, особенно когда вы новичок. Я думаю, что это может быть отчасти то, что вас смущает. Вам лучше избегать таких вещей, как:

typedef struct hashtable * HashTablePtr;

Использование многих typedefs затруднит чтение вашего кода, так как вам нужно будет постоянно искать то, на что они ссылаются.

Основная проблема заключается в том, что вы выделяете память для размера указателя хеш-таблицы / списка, а не для размера их уважаемых структур. Я думаю, что код ниже показывает это хорошо. Вы также захотите проверить, сработали ли ваши распределения. Если malloc, calloc, realloc. и т.д. терпят неудачу, они возвращают NULL. Если это произойдет, и вы не проверите этот случай, вы получите ошибку segfault, и ваша программа потерпит крах.

Также следуйте стандарту c99 и поместите все объявления переменных в начало функции.

c99 std

Руководство пользователя malloc

struct hashtable *
createHashTable(unsigned int capacity){
    struct hashtable *hash;
    struct list *mylist;

    /* You want to allocate size of the hash structure not the size of a pointer. */
    hash = malloc(sizeof(struct hashtable)); 
    // always make sure if the allocation worked.
    if(hash == NULL){
        fprintf(stderr, "Could not allocate hashtable\n");
        return NULL;
    }

    hash->size = 0;
    hash->capacity = capacity;

    /* Unless you need the memory to be zero'd I would just use malloc here
     * mylist = calloc(capacity, sizeof(struct list)); */
    mylist = malloc(capacity * sizeof(struct list));
    if(mylist == NULL){
        fprintf(stderr, "Could not allocate list\n");
        free(hash); /* free our memory and handle the error*/
        return NULL;
    }

    mylist->head = NULL;
    mylist->size = 0;
    mylist->tail = NULL;    
    hash->list = mylist;

    return hash;
}

Также не забудьте освободить свой список, прежде чем освободить свою хеш-таблицу:

free(myhash->list);
free(myhash);