1. Набираем команду codeby webinar. Набираем команду для организации и проведения вебинаров. Подробнее ...

    Скрыть объявление
  2. Требуются разработчики и тестеры для проекта codebyOS. Требования для участия в проекте: Знание принципов работы ОС на базе Linux; Знание Bash; Крайне желательное знание CPP, Python, Lua; Навыки системного администрирования. Подробнее ...

    Скрыть объявление
  3. Получи 30.000 рублей. Для получения денег необходимо принять участие в конкурсе авторов codeby. С условиями и призами можно ознакомиться на этой странице ...

    Внимание! Регистрация авторов на конкурс закрыта.

    Скрыть объявление

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

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

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

    Репутация:
    0
    Использую хеш-функцию:

    Код:
    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];
    Используя этот метод разрешения коллизии нужно реализовать следующие функции: добавление, удаление, поиск.
    Ну я понимаю, что можно сделать это в массиве или в списке, но как сделать в массиве списков не знаю. Как хотя бы туда вообще элементы-то добавить???
     
  2. sdriver

    sdriver Гость

    Репутация:
    0
Загрузка...
Статус темы:
Закрыта.

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