Структуры хранения множества

Структуры хранения множества
Гергель В.П., профессор ,
директор института ИТММ
Практическая работа 1:
Методы программирования - 2
Учебный курс:

Содержание
Анализ задачи
Понятие множества
Операции над элементами
Теоретико-множественные операции
Проектирование
Конкретизация (допущения и ограничения)
Понятие характеристического вектора
Представление вектора в виде битовой строки
Формирование битовой строки в виде массива
Битовой формат элемента массива
Выделение базового класса для реализации битовых
строк
Реализация
из 13
Структуры хранения множества
ИТММ ННГУ, 2002-2015

из 13
Множество – набор элементов
Для множества определены операции:
проверка наличия элемента a∈A
добавление элемента A+a
удаление элемента A -a
Теоретико-множественные операции
объединение A∪B
пересечение A∩B
вычитание A\B
Универс U – множество всех элементов
ИТММ ННГУ, 2002-2015
1. Анализ задачи
Структуры хранения множества

из 13
ИТММ ННГУ, 2002-2015
2. Проектирование …
Конкретизация (допущения и ограничения):
элементы множества проиндексированы (каждому элементу соответствует уникальный индекс)
множество индексов элементов составляют
непрерывный диапазон целых значений
Тогда любое множество A⊂U может быть описано характеристическим вектором
α=(α1 α2… αn),
Структуры хранения множества

из 13
ИТММ ННГУ, 2002-2015
α=(α1 α2… αn)
Множество
Представление
Представление
Представление
2. Проектирование …
Структуры хранения множества

из 13
Нумерация бит в битовой строке – слева направо,
Нумерация элементов в массиве – слева направо,
биты элемента – справа налево
Байты двухбайтового элемента располагаются в ОП в обратном порядке (сначала байт с младшими битами, затем байт со старшими битами) – поддержка отображения на аппаратном уровне
⮲При реализации целесообразно выделить базовый
класс TBitField, обеспечивающий представление
битовых строк:
последовательность разработки
создание стандартного класса
ИТММ ННГУ, 2002-2015
2. Проектирование
Структуры хранения множества

из 13
ИТММ ННГУ, 2002-2015
3. Реализация
Контрольный пример: программа, приложение
Структуры хранения множества

Стадии программной разработки (анализ, проектирование, реализация, доказательство правильности)
Поэтапная разработка программ (иерархия и наследование)
Стиль программирования
из 13
Заключение
ИТММ ННГУ, 2002-2015
Структуры хранения множества

Расширение набора операций для множества
Реализация с использованием шаблонов
из 13
Вопросы для обсуждения
ИТММ ННГУ, 2002-2015
Структуры хранения множества

Завершение разработки класса TBitField
Реализация класса TSet
Реализация класса TSet с использованием шаблонов
Реализация класса TSet через наследование TBitField
из 13
Темы занятий для самостоятельной работы
ИТММ ННГУ, 2002-2015
Структуры хранения множества

Разработка структуры хранения для матриц специального типа
из 13
Следующая тема
ИТММ ННГУ, 2002-2015
Структуры хранения множества