разрешение коллизий
От: gosic  
Дата: 11.10.06 13:10
Оценка:
Использую хеш-функцию:


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];




Используя этот метод разрешения коллизии нужно реализовать следующие функции: добавление, удаление, поиск.
Ну я понимаю, что можно сделать это в массиве или в списке, но как сделать в массиве списков не знаю. Как хотя бы туда вообще элементы-то добавлять?
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.