Пытаясь написать HASH TABLE на C, я здесь правильно делаю? - PullRequest
Новая
       13

Пытаясь написать HASH TABLE на C, я здесь правильно делаю?

0 голосов
/ 20 октября 2011

Итак, у меня уже есть хеш-функция.

У меня есть объектная структура: 

OBJKT 
{
   OBJKT *o_hash_next;
   OBJKT *o_hash_prev;
   ... bunch of other stuff
}

У меня также есть хеш-массив, объявленный в заголовочном файле: OBJKT * hash_tbl [hsize];

Метод, который должен добавить данный OBJKT к хешу, принимает ключ хеша и OBJKT, который мы добавляем.

Так что я не уверен, что делаю правильно: 

void insert_in_hash(int hashindex, OBJKT *thisObject)
{
   *thisObject->o_hash_next = *hash_tbl[hashindex];
   *hash_tbl[hashindex]->o_hash_prev=*thisObject;
   *hash_tbl[hashindex] = *thisObject;
}

Это кажется правильным? Я пытаюсь установить предыдущий / следующий указатели, а затем добавить thisObject в хеш.

Ответы [ 2 ]

0 голосов
/ 20 октября 2011

Уже поздно, и я немного устал, но то, что я вижу, это дополнительная разыменование.

Первое: OBJKT *hash_tbl[] - это уже массив указателей на связанные списки.
Поэтому, когда вам нужен заголовок списка, вы просто используете hash_tbl[index], это даст вам указатель, который должен бытьприсвоено вам thisObject->o_hash_next, что тоже указатель.НЕ разыскивать.*thisObject->o_hash_next = *hash_tbl[hashindex] копирует значение с одного адреса на другой, и это не то, что вы хотите, я предполагаю.То же самое относится и к предыдущему указателю.

Ваше решение может выглядеть следующим образом: 

void insert_in_hash(int hashindex, OBJKT *thisObject)
{
    thisObject->o_hash_next          = hash_tbl[hashindex];
    hash_tbl[hashindex]->o_hash_prev = thisObject;
    thisObject->o_hash_prev          = NULL; // Don't forget to NULL if not in use
}

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

В любом случае, как я уже сказал, уже поздно, и у меня не было времени протестировать мой код, но вот полезная ссылка на учебное пособие по связанному списку: Учебное пособие по связанному списку C / C ++

Редактировать
Вы должны держать заголовок списка, как вы это делали в своем коде: hash_tbl[hashindex] = thisObject.Смотрите комментарии ниже

0 голосов
/ 20 октября 2011

выглядит примерно так. Для хеш-таблицы вам необязательно нужен двусвязный список.

Не забудьте обнулить ваш hash_tbl для начала.

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

Обновление

Судя по комментариям неисследованных (эти чертовы "*" символы), оно, вероятно, должно выглядеть так: 

void insert_in_hash(int hashindex, OBJKT *thisObject)
{
   thisObject->o_hash_next = hash_tbl[hashindex];
   thisObject->o_hash_prev = NULL;
   hash_tbl[hashindex]->o_hash_prev=thisObject;
   hash_tbl[hashindex] = thisObject;
}
...