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

Тема в разделе "MS Visual C++", создана пользователем -, 11 окт 2006.

Статус темы:
Закрыта.
  1. Гость

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

    Код (Text):
    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 списков.

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

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

    sdriver Гость

Загрузка...
Статус темы:
Закрыта.

Поделиться этой страницей