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

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