9. Инициализация вектора data[0..п-1] может быть проведена с помощью сигнатуры, хранящейся в двух дополнительных n-элементных векторах from и to, и целого числа top. Если элемент data [i] проинициал изирован, то from[i]<top и to [from [i] ] =i. Поэтому from представляет собой простую сигнатуру, a to и top гарантируют, что случайное содержимое from до инициализации не будет воспринято как сигнатура. Свободные участки data сбрасываются так, как это показано на рисунке.
data:
Переменная top изначально имеет нулевое значение. Первый доступ к элементу i осуществляется следующим кодом:
f г от[л] = top t о [ t о р ] = i datа[1] = О top+ +
Эта задача и ее решение взяты из упражнения 2.12 книги Ахо, Хошсрофта и Ульмана «Разработка и анализ компьютерных алгоритмов» (Aho, Hopcroft abd Ullman, Design and Analysis of Computer Algorithms, Addison Wesley, 1974). Она сочетает индексацию с хитрой схемой составления сигнатур. Программа может использоваться для матриц так же, как и для векторов.
10. Магазин размещал бумажные формы заказов в массив корзин 10x10, используя два последних знака телефонного номера заказчика в качестве индекса хэширования. При заказе форма помещалась в соответствующую телефонному номеру корзину. Когда покупатель прибывал за покупкой, продавец последовательно просматривал заказы в соответствующей корзине — это классическая схема «открытого хэширования с разрешением коллизий с помощью последовательного поиска».
Последние две цифры телефонного номера распределены по покупателям практически случайным образом, поэтому дают отличную функцию хэширования, тогда как первые две цифры дали бы совершенно ужасную функцию — почему? В некоторых муниципалитетах используется аналогичная схема ведения записей в журналах.
Опубликовал vovan666
April 17 2013 00:06:17 ·
0 Комментариев ·
3985 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
