Здравствуйте, gosic, Вы писали:
G>Использую хеш-функцию:
G>const int n = 10; //кол-во требуемых адресов
G>int seredina_kvadrata (int key)
G>{
G> int k=0,x=0;
G> x = key * key;
G> int y=x;
G> do{
G> y=y/10;
G> k++;
G> } while (y>=1);
G> k=k/2;
G> x=x/pow(10,k);
G> x=x % n;
G> return x;
G>}
G>т.е. принцип такой:
G>При хешировании методом середины квадратов ключ сначала умножается сам на себя и в качестве адреса выбирается столько цифр из середины результата, какова требуемая длина адреса.
Весьма неоптимальный способ. Он
красиво и наглядно работает для десятичной арифметики, но для двоичной
... к тому же вещественные числа возникают по ходу дела (функция pow).
G>Теперь мне нужно разрешить коллизии (коллизией называется ситуация, когда двум различным значениям данных по функции хеширования назначается один и тот же хеш-адрес) с помощью метода цепочек:
G>способ состоит в том, чтобы поддерживать m связанных списков, по одному на каждый возможный хеш-адрес. Таким образом, каждый список будет содержать все элементы данных с ключами-синонимами, преобразуемыми в один хеш-адрес. Кроме того, необходимо иметь последовательность из m указателей на начало каждого из m списков.
G>Т.е. нужно иметь массив списков. Пусть:
G>G>struct list{
G>int i;
G>list *next;
G>};
G>// а в main будет так
G>list m[10];
Такое представление неудачно, поскольку в массиве хранятся первые узлы списков. Как ты выполнишь удаление такого корневого узла?
Лучше уж хранить указатели:
list* hashtable[n]; // раз ты ввёл константу "размер таблицы", то и используй её
G>Используя этот метод разрешения коллизии нужно реализовать следующие функции: добавление, удаление, поиск.
G>Ну я понимаю, что можно сделать это в массиве или в списке, но как сделать в массиве списков не знаю. Как хотя бы туда вообще элементы-то добавлять?
Сперва вычисляешь хеш для значения. h = seredina_kvadrata(i)
Затем берёшь соответствующую ячейку таблицы. hashtable[h]
И ищешь/добавляешь/удаляешь элемент "i" в этом списке.
Для односвязных списков удобно применять такой приём: держать указатель на указатель на элемент.
list** find(list** root, int i)
{
list** where = root;
while(*where != NULL && (*where)->i != i)
where = &((*where)->next); // переходим к указателю на следующий элемент, хранимому в текущем элементе
return where;
}
void insert(list** where, int i)
{
list* node = new list; node->i = i; node->next = *where;
*where = node; // вот зачем нам указатель на указатель!
}
void remove(list** where)
{
assert(*where != NULL); // удаляем существующий элемент
list* node = *where;
*where = node->next; // и здесь
delete node;
}
void remove_all(list** root)
{
while(*root != NULL)
remove(root);
}
Передавать в эти функции в качестве root надо, естественно, &(hashtable[h])
... << RSDN@Home 1.2.0 alpha rev. 655>>
Перекуём баги на фичи!
