- •Программирование и алгоритмические языки. Курс за второй семестр. Абстрактные типы данных.
- •Задача о раскраске.
- •Перечисление последовательностей фиксированной длины.
- •Var I:tСтраны; c:tЦвет;
- •Два взгляда на диаграммы – графы и автоматы.
- •Деревья
- •Как сократить перебор с возвратом. Перечисление последовательностей переменной длины
- •Словарный порядок на последовательностях произвольной длины
- •Статическая реализация стеков.
- •Очереди. Статическая реализация.
- •Статическая реализация деревьев.
- •Автоматы как структуры данных
- •Статическая реализация графов. Проблема фрагментации памяти. Списочные структуры.
- •Общая схема реализации автомата как списка.
- •Обработка кучи.
- •Динамическая реализация абстрактных типов ссылками. Ссылочные типы Паскаля.
- •Ссылочные типы Паскаля. Синтаксис типов.
- •Объявление списочной структуры в Паскале.
- •Реализация стеков.
- •Реализация очередей.
- •Основные операции над списками.
- •Обработка деревьев. Деревья выражений.
- •Поиск атома.
- •Различные объединения типов. Записи типов с вариантами.
- •Создание дерева. Перевод из префиксной записи. Представление записи.
- •Анализ алгоритма вычисления. Дерево как последовательность ветвей.
- •Задача синтаксического анализа.
- •Графы-выражения.
- •Раздельное описание абстрактных типов. Модульное программирование.
- •Проблема с кратным использованием модулей.
- •Деревья как структуры данных.
- •Деревья поиска.
- •Поиск в дереве поиска.
- •Включение в дерево поиска.
- •Другие обходы дерева. Обход в ширину.
- •Рекурсивные процедуры и функции. Примеры применения.
- •Поиск в дереве.
- •Проблемы с семантикой рекурсии.
- •Введение в машинно-ориентированное (ссылочное) программирование. Оператор Goto.
- •Создание новых структурных операторов.
- •Формальная семантика goto и неструктурных программ.
- •Мини-Паскаль.
- •Представление сложных типов. Адресная арифметика.
- •Проблемы реализации ввода-вывода. Идея буферизации.
- •Реализация процедур read и write.
- •Реализация структур управления.
- •Путь наверх. Реализация процедур-подпрограмм.
- •Передача параметров.
- •Сохранение и восстановление значений. Соглашение о связях.
- •Введение в теоретическое программирование. Границы программирования. Принципиальная и практическая неразрешимость.
- •О формальной спецификации. Мир задачи как автомат.
- •Процедуры как функции на множестве состояний. Процедуры как преобразователи предикатов.
- •Универсальные методы решения задач.
Обработка кучи.
Нас интересует лишь возможность доставлять и класть в кучу указатели, индексы свободных компонент. С логической точки зрения для этого подходят стек или очередь.
HeapHead
ai ai+1
ai+2
Эффективное решение – связать свободные компоненты в список.
{Инициализация кучи}
procedure InitHeap(list:tList);
{Связать все компоненты от 1 до nMax}
begin
with list do
begin
for ptr:=1 to nMax do content[ptr].next:=succ(ptr);
content[nMax].next:=; {Признак конца стека}
end;
end;
procedure GetHeap(var list:tList;NewPtr:tIndex);
{Взять указатель на свободную компоненту из кучи}
begin
with list do
begin
NewPtr:=HeapHead;
HeapHead:=content[HeapHead].next;
end;
end;
procedure PutHeap(var list:tList;Ptr:tIndex);
{Кладёт элемент в кучу}
begin
with list do
begin
content[Ptr].next:=HeapHead;
HeapHead:=Ptr;
end;
end;
Упражнение. Реализовать вставку и удаление из обработанного и двусвязного списка.
Динамическая реализация абстрактных типов ссылками. Ссылочные типы Паскаля.
Статическая реализация абстрактных типов страдает недостатками как с точки зрения логики, так и эффективности реализации. С точки зрения логики - нахождение ограничений на размер используемых структур данных. Расход памяти также неэффективен – запрашиваемых ресурсов больше, чем используемых.
Мы явно предпочли бы сосредоточиться на логике решения задачи, не замечая конечности памяти и автоматизировать технические проблемы распределения памяти (вроде обработки кучи).
Ссылочные типы обеспечивают мощный и гибкий аппарат конструирования абстрактных типов, но иногда слишком мощный и далёкий от логики решаемых нами задач.
указатели
Пример.
члены последовательности
указатели на следующий член
Имена как значения:
Имя Отчество Наиль Раисович
Наиль Раисович
Имена – специфический тип данных.
a[i]:=b[j]
-
имя значение
Основные из них – разыменование – по переменной определить её имя (не значение, как обычно).
Пример: Как тебя зовут?
Косвенная ссылка: определить значение имени, являющегося значением данной переменной.
Ссылочные типы Паскаля. Синтаксис типов.
Синтаксис:
p1: ^T, где T – произвольный тип
p2: ^integer; ^char;
Множество значений: множество всех имён-указателей на значение соответствующего типа.
Реализация: стандартным именем-значением является его номер, адрес в линейно-упорядоченной области памяти.
Единственной стандартной константой, общей для ссылочных типов, является константа nil – фиктивное значение, обозначающее отсутствие указателя.
Основные операции: разыменование и косвенная ссылка.
@x – разыменование – указатель (адрес) на переменную x.
Если x:integer, то p^:integer;
p^ - косвенная ссылка (значение той переменной, имя (адрес) которой хранится в p).
p:=x – ошибка несогласования типов.
x:=0;
p:=@x;
p^:=1;
write(x);
Мы получили 2 имени одного и того же значения.
Пример: Что выведет следующая программа? Единицу.
p^:=1 x:=1;
write(x);
Вывод: использование ссылок грозит побочными эффектами.
Нет никакого смысла связывать переменные ссылочного типа с уже имеющимися переменными. В стандарте отсутствует.
Истинное преимущество ссылок – возможность определять новые переменные динамически в ходе выполнения программ. До сих пор мы определяли переменные до выполнения программы в области var.
p:^T;
Процедура New(p) ссылочного типа порождает новую переменную типа T и кладёт её стандартное имя (адрес) в P. В результате получаем новую переменную типа Т с уникальным пользовательским именем p^.
Реализация: см. GetNewPtr (предыдущая лекция). (см. GetHeap)
Процедура Dispose(p) имеет обратный эффект – уничтожает, возвращает в кучу переменную с именем p^. Значение p становится неопределённым. В отличие от массивов, никакой контроль за семантикой не производится автоматически.
Реализация: см. PutHeap.
Замечание: никаких других функций над ссылочными типами в стандартном Паскале нет, в частности не разрешены арифметические операции над адресами..
Наличие процедуры New лежит в основе моделирования динамических типов данных. Можно порождать не только переменные известных типов, но и переменные, компонентами которых служат ссылки.
New