Корзины можно рассматривать как разновидность хэширования. Числа в каждой из корзин будут храниться в виде упорядоченного связанного списка. Поскольку распределение чисел однородно, в каждом из списков окажется в среднем по одному элементу.
В листинге 13.20 приведены внутренние данные класса IntSetBins.
Листинг 13.20. Внутренние данные класса IntSetBins
private
int п, bins, maxval ; struct node { int va1 : node *next.
node(int v. node *p) { val = v, next = p; }}:
node **bin , *sentinel ;
Конструктор в листинге 13.21 выделяет массив корзин и элемент-маркер с большим значением, а затем инициализирует все корзины указателями на этот маркер.
IntSetBins(maxelements, pmaxva1) bins = maxelements maxval = pmaxval bin = new node*[bins] sentinel = new node(maxval, 0) for i = [0. bins) bin[i] = sentinel n = 0
Функция insert должна помещать целое число t в соответствующую корзину. Очевидное отображение с помощью функции t * bins / maxval может привести к арифметическому переполнению (и сложностям при отладке, как я могу засвидетельствовать по собственному печальному опыту). Поэтому в нашей программе мы воспользуемся более безопасным отображением.
Опубликовал vovan666
April 17 2013 00:03:38 ·
0 Комментариев ·
3252 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
