- •Программирование и алгоритмические языки. Курс за второй семестр. Абстрактные типы данных.
- •Задача о раскраске.
- •Перечисление последовательностей фиксированной длины.
- •Var I:tСтраны; c:tЦвет;
- •Два взгляда на диаграммы – графы и автоматы.
- •Деревья
- •Как сократить перебор с возвратом. Перечисление последовательностей переменной длины
- •Словарный порядок на последовательностях произвольной длины
- •Статическая реализация стеков.
- •Очереди. Статическая реализация.
- •Статическая реализация деревьев.
- •Автоматы как структуры данных
- •Статическая реализация графов. Проблема фрагментации памяти. Списочные структуры.
- •Общая схема реализации автомата как списка.
- •Обработка кучи.
- •Динамическая реализация абстрактных типов ссылками. Ссылочные типы Паскаля.
- •Ссылочные типы Паскаля. Синтаксис типов.
- •Объявление списочной структуры в Паскале.
- •Реализация стеков.
- •Реализация очередей.
- •Основные операции над списками.
- •Обработка деревьев. Деревья выражений.
- •Поиск атома.
- •Различные объединения типов. Записи типов с вариантами.
- •Создание дерева. Перевод из префиксной записи. Представление записи.
- •Анализ алгоритма вычисления. Дерево как последовательность ветвей.
- •Задача синтаксического анализа.
- •Графы-выражения.
- •Раздельное описание абстрактных типов. Модульное программирование.
- •Проблема с кратным использованием модулей.
- •Деревья как структуры данных.
- •Деревья поиска.
- •Поиск в дереве поиска.
- •Включение в дерево поиска.
- •Другие обходы дерева. Обход в ширину.
- •Рекурсивные процедуры и функции. Примеры применения.
- •Поиск в дереве.
- •Проблемы с семантикой рекурсии.
- •Введение в машинно-ориентированное (ссылочное) программирование. Оператор Goto.
- •Создание новых структурных операторов.
- •Формальная семантика goto и неструктурных программ.
- •Мини-Паскаль.
- •Представление сложных типов. Адресная арифметика.
- •Проблемы реализации ввода-вывода. Идея буферизации.
- •Реализация процедур read и write.
- •Реализация структур управления.
- •Путь наверх. Реализация процедур-подпрограмм.
- •Передача параметров.
- •Сохранение и восстановление значений. Соглашение о связях.
- •Введение в теоретическое программирование. Границы программирования. Принципиальная и практическая неразрешимость.
- •О формальной спецификации. Мир задачи как автомат.
- •Процедуры как функции на множестве состояний. Процедуры как преобразователи предикатов.
- •Универсальные методы решения задач.
Поиск атома.
Черновик.
pt found:=false;
-
1 while not found do begin
if not терм(pt^.left) then pt:=pt^.left
else if not терм(pt^.right) then
-
1 pt:=pt^.right else
found:=true;
-
1
Начинать каждый раз с корня неэффективно. Нужно искать ближайший к вычисленному атом. Всё прекрасно, если в дереве есть обратная ссылка на родителей. В нашем представлении их нет. Как вернуться к предыдущей вершине? Сохранять ссылки на предыдущую, а затем возвращаться к последней сохранённой.
Begin
pt:=root;
found:=false;
while not found do
begin
if not терм(pt^.left) then
begin
push(stack,pt);
pt:=pt^.left;
end;
else if not терм(pt^.right) then
begin
push(stack,pt);
pt:=pt^.right;
end
else found:=true;
pt^.info:=AtomVal(pt);
dispose(pt^.left);
dispose(pt^.right);
end;
pop(stack,pt);
end;
{Каждый раз начинаем с последней сохранённой вершины}
До начала цикла (инициализация стека):
create(stack);
push(stack,root);
Условия окончания цикла:
not терм(root);
not empty(stack);
Упражнения:
-
Решить задачу вычисления в случае, когда в дереве хранится ссылка на родителей.
-
То же самое, но вершины содержат только ссылки на родителей.
Дерево задаётся списком листьев.
Подзадача: вычислить значения атомов.
function AtomVal(pt:pNode):integer;
var arg1,arg2:integer;
begin
arg1:=TermVal(pt^.left);
arg2:=TermVal(pt^.right);
case pt^.info of
‘+’: AtomVal:=arg1+arg2;
‘*‘: AtomVal:=arg1*arg2;
‘/’: AtomVal:=arg1/arg2;
‘-‘: AtomVal:=arg1-arg2;
end;
end;
Вернёмся здесь к вопросу об определении типа Info. Сначала он char, затем должен содержать значения типа integer. Типом поля Info по нашему алгоритму должно служить объединение типов. Мы должны не только хранить в этом поле значеня разных типов, но и уметь определять, какого типа значение там хранится в текущий момент. Это помеченное объединение.
function TermVal(pt:pNode):integer;
begin
if {тип Info=integer} then TermVal:=pt^.info
else if pt^.info in [‘0’..’9’] then TermVal:=ord(pt^.info)-ord(0)
else TermVal:=VarVal[pt^.info];
Очевидный вариант определения типа tInfo – запись.
record
это integer:boolean;
CharInfo:char;
IntInfo:integer;
end;
Этот вариант хорош, если мы не хотим фактически уничтожать дерево. Условие “этоInteger=true” означает, что это выражение уже вычислено. Но если мы хотим уничтожить дерево, то такое определение типа неэффективно. Паскаль предлагает более эффективное решение.