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

Содержание

Слайд 2

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

Гергель В.П., профессор , директор института ИТММ

Практическая работа 1:

Методы программирования -

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

Учебный курс:

Слайд 3

Содержание

Анализ задачи
Понятие множества
Операции над элементами
Теоретико-множественные операции
Проектирование
Конкретизация (допущения и

Содержание Анализ задачи Понятие множества Операции над элементами Теоретико-множественные операции Проектирование Конкретизация
ограничения)
Понятие характеристического вектора
Представление вектора в виде битовой строки
Формирование битовой строки в виде массива
Битовой формат элемента массива
Выделение базового класса для реализации битовых строк
Реализация

из 13

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

ИТММ ННГУ, 2002-2015

Слайд 4

из 13

Множество – набор элементов
Для множества определены операции:
проверка

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

ИТММ ННГУ, 2002-2015

1. Анализ задачи

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

Слайд 5

из 13

ИТММ ННГУ, 2002-2015

2. Проектирование …

Конкретизация (допущения и ограничения):
элементы множества

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

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

Слайд 6

из 13

ИТММ ННГУ, 2002-2015

α=(α1 α2… αn)

Множество

Представление

Представление

Представление

2. Проектирование …

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

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

Слайд 7

из 13

Нумерация бит в битовой строке – слева направо,
Нумерация

из 13 Нумерация бит в битовой строке – слева направо, Нумерация элементов
элементов в массиве – слева направо, биты элемента – справа налево
Байты двухбайтового элемента располагаются в ОП в обратном порядке (сначала байт с младшими битами, затем байт со старшими битами) – поддержка отображения на аппаратном уровне
⮲При реализации целесообразно выделить базовый класс TBitField, обеспечивающий представление битовых строк:
последовательность разработки
создание стандартного класса

ИТММ ННГУ, 2002-2015

2. Проектирование

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

Слайд 8

из 13

ИТММ ННГУ, 2002-2015

3. Реализация

Контрольный пример: программа, приложение

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

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

Слайд 9

Стадии программной разработки (анализ, проектирование, реализация, доказательство правильности)
Поэтапная разработка программ (иерархия и

Стадии программной разработки (анализ, проектирование, реализация, доказательство правильности) Поэтапная разработка программ (иерархия
наследование)
Стиль программирования

из 13

Заключение

ИТММ ННГУ, 2002-2015

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

Слайд 10

Расширение набора операций для множества
Реализация с использованием шаблонов

из 13

Вопросы для обсуждения

ИТММ

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

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

Слайд 11

Завершение разработки класса TBitField
Реализация класса TSet
Реализация класса TSet с использованием шаблонов
Реализация класса

Завершение разработки класса TBitField Реализация класса TSet Реализация класса TSet с использованием
TSet через наследование TBitField

из 13

Темы занятий для самостоятельной работы

ИТММ ННГУ, 2002-2015

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

Слайд 12

Разработка структуры хранения для матриц специального типа

из 13

Следующая тема

ИТММ ННГУ, 2002-2015

Структуры

Разработка структуры хранения для матриц специального типа из 13 Следующая тема ИТММ
хранения множества
Имя файла: Структуры-хранения-множества.pptx
Количество просмотров: 30
Количество скачиваний: 0