Динамические структуры данных

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

Содержание
Глава 1. Структура действия и структуры данных
1.3. Динамические структуры данных
Преобразование структур данных в процессе вычислений
Понятие динамической структуры. Примеры
1.4. Динамические структуры и структуры хранения
Общая структура хранения элементов и программы реализации отношения включения.
Практическая работа 3: Реализация стека
Сравнение линейных и динамических структур
Проблема эффективного использования памяти.
Практическая работа 4: Реализация очереди
Использование нескольких структур и необходимость динамического распределения памяти. Задача реализации двух стеков
Вопросы для обсуждения
ИТММ ННГУ, 2002-2019
Динамические структуры данных
3 из 22

из 22
ИТММ ННГУ, 2002-2019
1. Преобразование структур данных
в процессе вычислений...
Структуры данных являются операндами
операций обработки
Результаты вычислений также являются структурами, модель которых может как совпадать, так и отличаться от структуры исходных данных
Пример: Произведение векторов
Динамические структуры данных
1.3. Динамические структуры данных…

5 из 22
ИТММ ННГУ, 2002-2019
Пример 1.4. Организация последовательного вызова подпрограмм
Стек адресов возврата Для возврата в точку вызова необходимо запоминать адрес возврата
При завершении вызываемой подпрограммы для возврата используется последний запомненный адрес
В ходе вызова подпрограмм количество запоминаемых адресов постоянно изменяется (увеличивается при вызове очередной подпрограммы и уменьшается после завершения работы текущей подпрограммы)
Динамические структуры данных
1.3. Динамические структуры данных…
1. Преобразование структур данных
в процессе вычислений...

из 22
Отличительная особенность – структура исходных и результирующих данных являются близкими
Выполним анализ рассмотренного примера
Текущий набор адресов – линейная структура Sn=(a1 a2 … an )
Пусть T – операция исключения последнего адреса. Тогда
T(a1 a2 … an an+1 ) = (a1 a2 … an )
Пусть P – операция добавления нового адреса. Тогда
P(an+1; (a1 a2 … an )) = (a1 a2 … an an+1 )
Орграф результата является подорграфом орграфа
операнда или включает его
ИТММ ННГУ, 2002-2019
Динамические структуры данных
1.3. Динамические структуры данных…
1. Преобразование структур данных
в процессе вычислений...

Si состояние стека
с i значениями
Последовательное применение операций T и P позволяет получить набор состояний стека адресов
Мы имеем множество M элементов, у которых есть имена и значения
Si⊂Si+1, т.е. элементы связаны отношением включения подграфов
ИТММ ННГУ, 2002-2019
Динамические структуры данных
7 из 22
1.3. Динамические структуры данных…
1. Преобразование структур данных
в процессе вычислений...

Пусть:
P1 - отношение следования, порождаемое операцией вставки,
P2 - отношение следования, порождаемое операцией исключения.
Тогда стек есть структура
S=(Mi,P1, P2),
в которой
- каждый элемент – структура,
- в любой момент существует только один
конкретный элемент из M,
- элементы частично упорядочены по включению.
ИТММ ННГУ, 2002-2019
Динамические структуры данных
8 из 22
1.3. Динамические структуры данных…
1. Преобразование структур данных
в процессе вычислений

2. Понятие динамической структуры
Определение 1.9. Динамическая структура есть математическая структура, которой соответствует частично-упорядоченное (по включению) базовое множество M, элементы которого являются структурами данных. При этом отношения включения индуцируются операциями преобразования структуры данных.
Пример 1.5. Очередь (вставка в конец очереди, исключение из начала – дисциплина FIFO – first in, first out)
Пример 1.6. Дек (dequeue – double ended queue) – вставка и исключение для начала и конца дека – дисциплина FOLIFOLO – first or last in, first or last out)
ИТММ ННГУ, 2002-2019
Динамические структуры данных
9 из 22
1.3. Динамические структуры данных

В каждый текущий момент времени в памяти хранится только один элемент базисного множества
Для преобразования текущего элемента к следующему должны быть разработаны программы поддержки динамической структуры
Структура хранения текущего элемента должна иметь достаточно общий характер, достаточный для представления любых элементов базисного множества структуры
ИТММ ННГУ, 2002-2019
Динамические структуры данных
10 из 22
1.4. Динамические структуры и структуры хранения…
1. Общая структура хранения элементов и программы реализации отношения включения

Практическая работа 3: Реализация стека
ИТММ ННГУ, 2002-2019
Динамические структуры данных
11 из 22
1.4. Динамические структуры и структуры хранения…
1. Пример разработки структуры хранения

Определение1.10. Программы, реализующие отношение включения, называются средствами поддержания динамической структуры
ИТММ ННГУ, 2002-2019
Динамические структуры данных
12 из 22
2. Сравнение линейных и динамических структур
1.4. Динамические структуры и структуры хранения…

При использовании стека может возникнуть ситуация
исчерпания памяти для хранения значений – ограничение
реализации теоретически неограниченного стека
Невозможность использования стека из-за переполнения
возникает только в момент полного использования всей
выделенной для стека памяти
Определение 1.11. Для оценки эффективности использования памяти введем показатель Emem, определяемый как отношение объема используемой памяти к общему размеру выделенной памяти.
ИТММ ННГУ, 2002-2019
Динамические структуры данных
13 из 22
3. Проблема эффективного использования памяти…
1.4. Динамические структуры и структуры хранения…

3. Проблема эффективного использования памяти
Практическая работа 4: Реализация очереди
ИТММ ННГУ, 2002-2019
Динамические структуры данных
14 из 22
1.4. Динамические структуры и структуры хранения…

Пример 1.7. Стек для хранения фиксированного количества последних записанных значений
Стек подобного вида может быть использован, например, для запоминания данных, достаточных для восстановления текущего состояния программы перед выполнением очередной операции обработки (для реализации процедуры типа операции отмены в редакторе текстов). При реализации данного механизма обычно фиксируется максимальная глубина отката; при заполнении памяти из стека удается наиболее старая записанная информация.
Наиболее простой способ реализации такого стека – использование кольцевого буфера (при заполнении стека следующий для использования по кольцу элемент памяти содержит подлежащее удалению значение данных)
Как реализовать процедуру
отмены операции отката ?
ИТММ ННГУ, 2002-2019
Динамические структуры данных
15 из 22
1.4. Динамические структуры и структуры хранения…
4. Использование нескольких структур и необходимость динамического распределения памяти

Пример 1.8. Задача использования двух стеков
При использовании двух стеков может возникнуть ситуация переполнения одного стека, в то время как в другом стеке свободная память может еще присутствовать – эффективность использования памяти в этом случае не будет являться максимально-возможной
Возможное решение проблемы – использование общей памяти для этих стеков, в которой один стек будет "расти" слева направо, второй стек – справа налево.
При таком подходе свободная память является обшей и ситуация переполнения стеков возникает только при полном исчерпании памяти
ИТММ ННГУ, 2002-2019
Динамические структуры данных
16 из 22
1.4. Динамические структуры и структуры хранения…
4. Использование нескольких структур и необходимость динамического распределения памяти…

Определение 1.13. Распределение памяти до начала процесса вычислений называется статическим. Распределение памяти в ходе выполнения программы называется динамическим распределением памяти.
Как распределить память для большего, чем 2, количества стеков ?
ИТММ ННГУ, 2002-2019
Динамические структуры данных
17 из 22
1.4. Динамические структуры и структуры хранения
4. Использование нескольких структур и необходимость динамического распределения памяти

Понятие динамической структуры данных
Необходимость разработки общей структуры хранения для элементов базисного множества
Необходимость программной реализации отношения включения
Отличительные особенности линейных и динамических структур
Структура хранения в виде кольцевого буфера
Статическое и динамическое распределение памяти
Примеры реализации динамических структур: стеки и очереди
Программирование с защитой от ошибок
ИТММ ННГУ, 2002-2019
Динамические структуры данных
18 из 22
Заключение

Классификация видов структур данных: линейные, динамические…
Проблема разных типов значений для элементов базисных множеств
Принципы программирования с защитой от ошибок (накладные расходы, увеличение объема программирования, существующие подходы…)
Достоинства и недостатки динамического распределения памяти
ИТММ ННГУ, 2002-2019
Динамические структуры данных
19 из 22
Вопросы для обсуждения

Реализация стеков и очередей с использованием шаблонов
Разработка программы для вычисления арифметического выражения в постфиксной записи
ИТММ ННГУ, 2002-2019
Динамические структуры данных
20 из 22
Темы заданий для самостоятельной работы

Динамическое распределение памяти
ИТММ ННГУ, 2002-2019
Динамические структуры данных
21 из 22
Следующая тема