Структуры и алгоритмы обработки данных


Методы разрешения коллизий - часть 3


Данное состояние в процессе поиска интерпретируется, как занято, а в процессе записи как свободно.

Сформулируем алгоритмы вставки поиска и удаления для хеш-таблицы, имеющей три состояния элементов.

Вставка

  1. i = 0
  2. a = h(key) + i*c
  3. Если t(a) = свободно или t(a) = удалено, то t(a) = key, записать элемент, стоп элемент добавлен

  4. i = i + 1, перейти к шагу 2

Удаление

  • i = 0
  • a = h(key) + i*c
  • Если t(a) = key, то t(a) =удалено, стоп элемент удален

  • Если t(a) = свободно, то стоп элемент не найден

  • i = i + 1, перейти к шагу 2

Поиск

  • i = 0
  • a = h(key) + i*c
  • Если t(a) = key, то стоп элемент найден

  • Если t(a) = свободно, то стоп элемент не найден

  • i = i + 1, перейти к шагу 2

Алгоритм поиска для хеш-таблицы, имеющей три состояния, практически не отличается от алгоритма поиска без учета удалений. Разница заключается в том, что при организации самой таблицы необходимо отмечать свободные и удаленные элементы. Это можно сделать, зарезервировав два значения ключевого поля. Другой вариант реализации может предусматривать введение дополнительного поля, в котором фиксируется состояние элемента. Длина такого поля может составлять всего два бита, что вполне достаточно для фиксации одного из трех состояний. На языке TurboPascal данное поле удобно описать типом Byte или Char.




Начало  Назад  Вперед



Книжный магазин