Ошибка указателя сегмента, хотя я неправильно выделен - PullRequest
Новая
       26

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

0 голосов
/ 08 марта 2019

Я не понимаю, почему в моей программе происходит сбой сегмента в этой строке: if ((**table->table).link == NULL){ Кажется, у меня есть неправильно распределенная память, и я попытался посмотреть на нее с помощью gdb. *table->table был доступен и не NULL, но **table->table не был доступен. Определение hash_t: 

struct table_s  {   
    struct node_s **table;
    size_t bins;    
    size_t size;
};

typedef struct table_s *hash_t;

void set(hash_t table, char *key, int value){
    unsigned int hashnum = hash(key)%table->bins;
    printf("%d \n", hashnum);
    unsigned int i;
    for (i = 0; i<hashnum; i++){
        (table->table)++;
    }
    if (*(table->table) == NULL){
        struct node_s n = {key, value, NULL};
        struct node_s *np = &n;
        *(table->table) = malloc(sizeof(struct node_s));
        *(table->table) = np;
    }else{
        while ( *(table->table) != NULL){
        if ((**table->table).link == NULL){
            struct node_s n = {key, value, NULL};
            struct node_s *np = &n;
            (**table->table).link = malloc(sizeof(struct node_s));
            (**table->table).link = np;
            break;
        }else if (strcmp((**table->table).key, key) == 0){
            break;
        }
            *table->table = (**(table->table)).link;
        }
        if (table->size/table->bins > 1){
            rehash(table);
        }
    }
}

Я звоню по телефону отсюда 

  for (int i = 0; i < trials; i++) {
     int sample = rand() % max_num;
     sprintf(key, "%d", sample);
     set(table, key, sample);
  }

1 Ответ

0 голосов
/ 08 марта 2019

Ваша хеш-таблица работает следующим образом: у вас есть bins корзин, и каждая корзина представляет собой связанный список пар ключ / значение.Все элементы в корзине имеют одинаковый хэш-код по модулю количества корзин.

Возможно, вы создали таблицу бинов, когда создали или инициализировали хэш-таблицу, что-то вроде этого: 

table->table = malloc(table->bins * sizeof(*table->table);

for (size_t i = 0; i < table->bins; i++) table->table[i] = NULL;

Теперь, почему элемент table имеет две звезды?

  • «Внутренняя» звезда означает, что таблица хранит указатели на узлы, а не на сами узлы.

  • «Внешний» запуск - это указатель на выделенную память.Если бы ваша хеш-таблица имела фиксированный размер, например всегда с 256 бинами, вы можете определить ее следующим образом: 

    struct node_s *table[256];

    Если вы передадите этот массив, он станет (или «распадется на»)указатель на его первый элемент, struct node_s **, точно так же, как массив, полученный из malloc.

  • Вы получаете доступ к содержимому l´bins через связанные списки и заголовок связанного спискаi - это table->table[i].

У вашего кода другие проблемы:

  • Чего вы хотели достичь с помощью (table->table)++?Это сделает дескриптор выделенной памяти не первым элементом, а следующим.После выполнения этого времени хеш-памяти *table->table теперь будет на правильном узле, но вы потеряете исходный дескриптор, который вы должны сохранить, потому что вы должны передать его free позже, когда очистите свою хеш-таблицу.Не теряйте ручку для выделенной памяти!Вместо этого используйте другой локальный указатель.

  • Вы создаете локальный узел n, а затем делаете ссылку в своем связанном списке с указателем на этот узел.Но узел n исчезнет после того, как вы выйдете из функции, и ссылка будет «устаревшей»: она будет указывать на недействительную память.Вы также должны создать память для узла с malloc.

. Простая реализация вашей таблицы has может быть такой: 

void set(hash_t table, char *key, int value)
{
    unsigned int hashnum = hash(key) % table->bins;

    // create (uninitialised) new node
    struct node_s *nnew = malloc(sizeof(*nnew));

    // initialise new node, point it to old head
    nnew->key = strdup(key);
    nnew->value = value;
    nnew->link = table->table[hashnum];

    // make the new node the new head
    table->table[hashnum] = nnew;
}

Это делает новый узелглава связанного списка.Это не идеально, потому что если вы перезаписываете элементы, будут найдены новые (что хорошо), но старые все еще будут в таблице (что не хорошо).Но это, как говорится, оставлено читателю в качестве упражнения.

(Функция strdup не является стандартной, но широко доступна. Она также создает новую память, которую вы должны освободить позже, ноэто гарантирует, что строка «живет» (все еще действует) после того, как вы завершили хеш-таблицу.)

Пожалуйста, не указывайте, сколько звездочек в коде.Если одной звезды слишком мало, она находится в hash_t, где вы указали тип указателя.

...