разрешение коллизий

  • Автор темы Guest
  • Дата начала
Статус
Закрыто для дальнейших ответов.
G

Guest

#1
Использую хеш-функцию:

Код:
const int n = 10; //кол-во требуемых адресов
int seredina_kvadrata (int key)
{
int k=0,x=0;
x = key * key;
int y=x;
do{ 
y=y/10;
k++;
} while (y>=1);
k=k/2;
x=x/pow(10,k);
x=x % n;
return x;
}
т.е. принцип такой:
При хешировании методом середины квадратов ключ сначала умножается сам на себя и в качестве адреса выбирается столько цифр из середины результата, какова требуемая длина адреса.
Теперь мне нужно разрешить коллизии (коллизией называется ситуация, когда двум различным значениям данных по функции хеширования назначается один и тот же хеш-адрес) с помощью метода цепочек:
способ состоит в том, чтобы поддерживать m связанных списков, по одному на каждый возможный хеш-адрес. Таким образом, каждый список будет содержать все элементы данных с ключами-синонимами, преобразуемыми в один хеш-адрес. Кроме того, необходимо иметь последовательность из m указателей на начало каждого из m списков.

Т.е. нужно иметь массив списков. Пусть:

Код:
struct list{
int i;
list *next;
};
// а в main будет так
list m[10];
Используя этот метод разрешения коллизии нужно реализовать следующие функции: добавление, удаление, поиск.
Ну я понимаю, что можно сделать это в массиве или в списке, но как сделать в массиве списков не знаю. Как хотя бы туда вообще элементы-то добавить???
 
Статус
Закрыто для дальнейших ответов.