- •Программирование и алгоритмические языки. Курс за второй семестр. Абстрактные типы данных.
- •Задача о раскраске.
- •Перечисление последовательностей фиксированной длины.
- •Var I:tСтраны; c:tЦвет;
- •Два взгляда на диаграммы – графы и автоматы.
- •Деревья
- •Как сократить перебор с возвратом. Перечисление последовательностей переменной длины
- •Словарный порядок на последовательностях произвольной длины
- •Статическая реализация стеков.
- •Очереди. Статическая реализация.
- •Статическая реализация деревьев.
- •Автоматы как структуры данных
- •Статическая реализация графов. Проблема фрагментации памяти. Списочные структуры.
- •Общая схема реализации автомата как списка.
- •Обработка кучи.
- •Динамическая реализация абстрактных типов ссылками. Ссылочные типы Паскаля.
- •Ссылочные типы Паскаля. Синтаксис типов.
- •Объявление списочной структуры в Паскале.
- •Реализация стеков.
- •Реализация очередей.
- •Основные операции над списками.
- •Обработка деревьев. Деревья выражений.
- •Поиск атома.
- •Различные объединения типов. Записи типов с вариантами.
- •Создание дерева. Перевод из префиксной записи. Представление записи.
- •Анализ алгоритма вычисления. Дерево как последовательность ветвей.
- •Задача синтаксического анализа.
- •Графы-выражения.
- •Раздельное описание абстрактных типов. Модульное программирование.
- •Проблема с кратным использованием модулей.
- •Деревья как структуры данных.
- •Деревья поиска.
- •Поиск в дереве поиска.
- •Включение в дерево поиска.
- •Другие обходы дерева. Обход в ширину.
- •Рекурсивные процедуры и функции. Примеры применения.
- •Поиск в дереве.
- •Проблемы с семантикой рекурсии.
- •Введение в машинно-ориентированное (ссылочное) программирование. Оператор Goto.
- •Создание новых структурных операторов.
- •Формальная семантика goto и неструктурных программ.
- •Мини-Паскаль.
- •Представление сложных типов. Адресная арифметика.
- •Проблемы реализации ввода-вывода. Идея буферизации.
- •Реализация процедур read и write.
- •Реализация структур управления.
- •Путь наверх. Реализация процедур-подпрограмм.
- •Передача параметров.
- •Сохранение и восстановление значений. Соглашение о связях.
- •Введение в теоретическое программирование. Границы программирования. Принципиальная и практическая неразрешимость.
- •О формальной спецификации. Мир задачи как автомат.
- •Процедуры как функции на множестве состояний. Процедуры как преобразователи предикатов.
- •Универсальные методы решения задач.
Включение в дерево поиска.
Включим 13 в дерево.
procedure Vstavka(var root:pNode;x:tInfo);
var found:boolean;
pt, ptpred:pNode;
begin
pt:=root;
found:=false;
while not found and (pt<>nil) do
begin
if pt^.info=x then found:=true
else if x>pt^.info then pt:=pt^.right
else pt:=pt^.left;
end;
if not found then
begin
new(ptpred);
ptpred^.info:=pt^.info;
if x<pred^.info then pred:=pt^.left
else pred:=pt^.right;
end;
end;
Аналогична задаче поиска, но сохраняет ссылку на предыдущую вершину ptpred:pNode. Как только pt=nil – ptpred – ссылка на вершину, после которой надо вставить данное значение.
Завести дополнительную ссылку ptpred, указывающую на последнюю пройденную вершину.
ptpred:=pt;
Когда pt=nil ptpred указывает на нужный элемент, то есть ptpred указывает на вершину, после которой нужно вставить вершину.
Упражнение: завершить реализацию вставки в дерево поиска. Построить дерево поиска.
Тривиальное решение: создать из первого элемента входной последовательности корень, затем, пока не кончилась входная последовательность, включать очередной элемент в построенное к этому шагу дерево.
К сожалению, предыдущее решение не строит сбалансированное дерево. Вставка с сохранением сбалансированности – сложная задача (в этом случае используются специальные типы деревьев). Хотя задача построения сбалансированного дерева не столь сложна:
1) Найти среднее значение во входной последовательности и сделать его корнем дерева.
2) Сделать то же для всех элементов, меньших корня (левое поддерево) и больших корня (правое поддерево).
Формулировка алгоритма рекурсивная. (см. Рекурсия)
Другие обходы дерева. Обход в ширину.
Есть задачи, в которых порядок обхода важен. В задаче о вычислении нижние вершины должны быть обработаны раньше, чем верхние.
Л П
К<Л<П Л П К - корень КЛП-обход
Порядок обработки: корень, левая ветка, правая ветка.
ЛПК-обход – задача о вычислении (ПЛК).
Обход КЛП даёт самую простую спецификацию обхода дерева.
1) КЛП – наиболее важный (см. Рекурсия).
2) Обходы “в ширину”, то есть такие порядки, в которых последовательности одинаковой длины соседствуют друг с другом (сгруппированы).
Задача. Найти в дереве вхождение заданного значения от ближайшего корня.
Procedure Поиск_в_ширину (root:pNode;x:tInfo;var found:boolean;var pt:pNode);
var level:{последовательность вершин одного уровня};
Л П
Л П
Begin
found:=false;
put(level,root);
while not empty(level) {не кончились уровни} and not found do
begin
{искать на текущем уровне нужные значения}
{обеспечить доступ на следующий уровень}
while not empty(level) {кончились вершины текущего уровня} and not found do
begin
get(level,pt);
{достать текущую вершину уровня}
if pt^.info=x then found:=true
else begin
if pt^.left<>nil then put(newlevel,pt^.left);
if pt^.right<>nil then put(newlevel,pt^.right);
end;
end;
level:=newlevel; newlevel:=nil;
end;
end;
Структура tLevel – последовательность (динамическая) с двумя операциями – get и put и проверка пустоты. В данном случае неважно, стек это или очередь.
Другой вариант того же алгоритма:
uses Queue;
var q:tQueue;
begin
put(q,root);
found:=false;
{q содержит ссылки на все не пройденные вершины списка}
while not empty(q) and not found do
begin
get(q,pt);
if pt^.info=x then found:=true
else begin
if pt^.left<>nil then put(q,pt^.left);
if pt^.right<>nil then put(q,pt^.right);
end;
end;
end;
Это непременно очередь. Потомки текущей вершины должны обрабатываться после всех вершин текущего уровня.