Similar presentations:
Структуры хранения множества
1.
НИЖЕГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМ. Н.И. ЛОБАЧЕВСКОГОИНСТИТУТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ, МАТЕМАТИКИ И МЕХАНИКИ
Учебный курс
МЕТОДЫ ПРОГРАММИРОВАНИЯ - 2
2.
Нижегородский государственный университет им. Н.И. ЛобачевскогоИнститут информационных технологий, математики и механики
Учебный курс:
Методы программирования - 2
Практическая работа 1:
Структуры хранения множества
Гергель В.П., профессор ,
директор института ИТММ
3.
СодержаниеАнализ задачи
• Понятие множества
• Операции над элементами
• Теоретико-множественные операции
Проектирование
• Конкретизация (допущения и ограничения)
• Понятие характеристического вектора
• Представление вектора в виде битовой строки
• Формирование битовой строки в виде массива
• Битовой формат элемента массива
• Выделение базового класса для реализации битовых
строк
Реализация
ИТММ ННГУ,
2002-2015
Структуры хранения множества
3 из 13
4.
1. Анализ задачиМножество – набор элементов
Для множества определены операции:
- проверка наличия элемента a A
- добавление элемента
A+a
- удаление элемента
A -a
Теоретико-множественные операции
- объединение A B
- пересечение A B
- вычитание
A\B
Универс U – множество всех элементов
ИТММ ННГУ,
2002-2015
Структуры хранения множества
4 из 13
5.
2. Проектирование …Конкретизация (допущения и ограничения):
- элементы множества проиндексированы (каждому
элементу соответствует уникальный индекс)
- множество индексов элементов составляют
непрерывный диапазон целых значений
Тогда любое множество A U может быть описано
характеристическим вектором
=( 1 2… n),
i=
ИТММ ННГУ,
2002-2015
i =1 i A
i =0, иначе
Структуры хранения множества
5 из 13
6.
2. Проектирование …=( 1 2… n)
Множество
Представление
Битовая строка
0
1
2
n
Представление
Массив битовых
элементов
0
1
15
1
m
0
Представление
Оперативная
память (обратный
порядок хранения)
ИТММ ННГУ,
2002-2015
0
7
1
2m
0
Структуры хранения множества
6 из 13
7.
2. ПроектированиеНумерация бит в битовой строке – слева направо,
Нумерация элементов в массиве – слева направо,
биты элемента – справа налево
Байты двухбайтового элемента располагаются в ОП в
обратном порядке (сначала байт с младшими битами, затем
байт со старшими битами) – поддержка отображения на
аппаратном уровне
При реализации целесообразно выделить базовый
класс TBitField, обеспечивающий представление
битовых строк:
- последовательность разработки
- создание стандартного класса
ИТММ ННГУ,
2002-2015
Структуры хранения множества
7 из 13
8.
3. РеализацияБитовые строки
TBitField
1
1
Множества
TSet
Контрольный пример: программа, приложение
ИТММ ННГУ,
2002-2015
Структуры хранения множества
8 из 13
9.
Заключение• Стадии программной разработки (анализ, проектирование,
реализация, доказательство правильности)
• Поэтапная разработка программ (иерархия и наследование)
• Стиль программирования
ИТММ ННГУ,
2002-2015
Структуры хранения множества
9 из 13
10.
Вопросы для обсуждения• Расширение набора операций для множества
• Реализация с использованием шаблонов
ИТММ ННГУ,
2002-2015
Структуры хранения множества
10 из 13
11.
Темы занятий для самостоятельной работыЗавершение разработки класса TBitField
Реализация класса TSet
Реализация класса TSet с использованием шаблонов
Реализация класса TSet через наследование TBitField
ИТММ ННГУ,
2002-2015
Структуры хранения множества
11 из 13
12.
Следующая тема• Разработка структуры хранения для матриц
специального типа
ИТММ ННГУ,
2002-2015
Структуры хранения множества
12 из 13
13.
КонтактыНижегородский государственный университет
им. Н.И. Лобачевского (www.unn.ru)
Институт информационных технологий, математики
и механики (www.itmm.unn.ru)
603950, Нижний Новгород, пр. Гагарина, 23,
р.т.: (831) 462-33-56,
Гергель Виктор Павлович
(http://www.software.unn.ru/?dir=17)
E-mail: [email protected]
ИТММ ННГУ,
2002-2015
Структуры хранения множества
13 из 13