- •1.Классификация структур данных
- •2.Операции над структурами
- •3. Структурность данных и технологии программирования
- •4. Целочисленные типы
- •5. Вещественные типы
- •6. Битовые типы
- •7. Логический тип
- •10. Интервальный тип
- •11. Указатели
- •8. Символьный тип
- •9. Перечислимый тип
- •12. Массивы
- •13. Свободные массивы
- •14. Треугольные и разреженные матрицы
- •15. Множества
- •16. Записи
- •17. Абстрактный тип данных «Список»
- •18. Методы реализации списков
- •19. Двунаправленные списки
- •20. Абстрактный тип данных «Стек»
- •21. Методы реализации стеков
- •22. Применение стеков при разработке приложений
- •23. Абстрактный тип данных «Очередь»
- •24. Методы реализации очередей
- •25. Абстрактный тип данных «Дек». Методы реализации
- •26. Строки: логическая структура, операции и представление в памяти
- •27. Деревья. Их обходы
- •28. Помеченные деревья и деревья выражений
- •29. Абстрактный тип данных «Дерево»
- •30. Методы реализации деревьев
- •31. Двоичные деревья. Методы их представления
- •32. Коды Хаффмана
- •33. Абстрактный тип данных «Множество»
- •34. Абстрактный тип данных с операторами множеств
- •35. Методы реализации абстрактного типа данных «Множество»
- •36. Словари. Методы их реализации
- •37. Структуры данных основанные на хеш-таблицах
- •38. Оценка эффективности хеш-функций
- •39. Очереди с приоритетами. Методы их реализации
- •40. Реализация очереди с приоритетами частично упорядоченными деревьями
- •41. Деревья двоичного поиска. Методы их реализации
- •42. Нагруженные деревья. Методы их реализации
- •43. Реализация множеств посредством сбалансированных 2-3 деревьев
- •45. Задача наибольшей общей подпоследовательности
- •44. Множества с операторами merge и find. Методы их реализации
- •46. Сбалансированные и несбалансированные деревья поиска
- •48. Методы представления графов
- •49. Внешняя сортировка. Основные характеристики сортировок методом слияний
- •50. Алгоритм прямого слияния
- •51. Алгоритм естественного слияния
- •52. Сбалансированное многопутевое слияние
- •53. Многофазная сортировка
- •54. Хранение данных в файлах
- •55. Внешние деревья поиска
36. Словари. Методы их реализации
Применение множеств при разработке алгоритмов не всегда требует таких мощных операторов, как операторы объединения и пересечения. Часто достаточно только хранить в множестве "текущие" объекты с периодической вставкой или удалением некоторых из них. Время от времени также возникает необходимость узнать, присутствует ли конкретный элемент в данном множестве.
Абстрактный тип множеств с операторами INSERT, DELETE и MEMBER называется DICTIONARY (Словарь).
Мы также включим оператор MAKENULL в набор операторов словаря - он потребуется при реализации АТД для инициализации структур данных.
Реализация
Словари можно представить посредством сортированных или несортированных связанных списков.
Другая возможная реализация словарей использует двоичные векторы, предполагая, что элементы данного множества являются целыми числами 1, ..., N для некоторого N или элементы множества можно сопоставить с таким множеством целых чисел.
Третья возможная реализация словарей использует массив фиксированной длины с указателем на последнюю заполненную ячейку этого массива. Эта реализация выполнима, если мы точно знаем, что размер множества не превысит заданную длину массива.
37. Структуры данных основанные на хеш-таблицах
Существует еще один полезный и широко используемый метод реализации словарей, который называется хешированием.
Мы рассмотрим две различные формы хеширования.
Одна из них называется открытым, или внешним, хешированием (частный случай расширенного хеширования) и позволяет хранить множества в потенциально бесконечном пространстве, снимая тем самым ограничения на размер множеств.
Другая называется закрытым, или внутренним или прямым, хешированием и использует ограниченное пространство для хранения данных, ограничивая таким образом размер множеств.
38. Оценка эффективности хеш-функций
Хеширование — преобразование входного массива данных произвольной длины в выходную битовую строку фиксированной длины. Такие преобразования также называются хеш-функциями или функциями свёртки, а их результаты называют хешем, хеш-кодом. Примеры алгоритмов хеширования: CRC, MD4, Tiger.
Общей идеей методов хэширования является применение к значению ключа некоторой функции свертки (хеш-функции), вырабатывающей значение меньшего размера. В самом простом, классическом, случае, свертка значения ключа используется затем для доступа к записи в структурах данных, как адрес в таблице, содержащей ключи и записи.
Основными требованиями к хэш-функции являются:
– уменьшение возможности подбора ключа в случае применения хеш-функции в
криптографии;
– равномерное распределение значения свертки в случае применения хеш-функции в структурах данных;
– генерация последовательностей чисел, которые невозможно отличить от случайных, используемых в имитационном моделировании.
Процедура оценки эффективности алгоритмов хеширования включает ряд задач, в том числе:
– определение временной сложности алгоритма;
– расчет вероятности возникновения коллизий;
– оценка возможности подбора ключа (для алгоритмов, применяемых в криптографии).
