- •Программирование и алгоритмические языки. Курс за второй семестр. Абстрактные типы данных.
- •Задача о раскраске.
- •Перечисление последовательностей фиксированной длины.
- •Var I:tСтраны; c:tЦвет;
- •Два взгляда на диаграммы – графы и автоматы.
- •Деревья
- •Как сократить перебор с возвратом. Перечисление последовательностей переменной длины
- •Словарный порядок на последовательностях произвольной длины
- •Статическая реализация стеков.
- •Очереди. Статическая реализация.
- •Статическая реализация деревьев.
- •Автоматы как структуры данных
- •Статическая реализация графов. Проблема фрагментации памяти. Списочные структуры.
- •Общая схема реализации автомата как списка.
- •Обработка кучи.
- •Динамическая реализация абстрактных типов ссылками. Ссылочные типы Паскаля.
- •Ссылочные типы Паскаля. Синтаксис типов.
- •Объявление списочной структуры в Паскале.
- •Реализация стеков.
- •Реализация очередей.
- •Основные операции над списками.
- •Обработка деревьев. Деревья выражений.
- •Поиск атома.
- •Различные объединения типов. Записи типов с вариантами.
- •Создание дерева. Перевод из префиксной записи. Представление записи.
- •Анализ алгоритма вычисления. Дерево как последовательность ветвей.
- •Задача синтаксического анализа.
- •Графы-выражения.
- •Раздельное описание абстрактных типов. Модульное программирование.
- •Проблема с кратным использованием модулей.
- •Деревья как структуры данных.
- •Деревья поиска.
- •Поиск в дереве поиска.
- •Включение в дерево поиска.
- •Другие обходы дерева. Обход в ширину.
- •Рекурсивные процедуры и функции. Примеры применения.
- •Поиск в дереве.
- •Проблемы с семантикой рекурсии.
- •Введение в машинно-ориентированное (ссылочное) программирование. Оператор Goto.
- •Создание новых структурных операторов.
- •Формальная семантика goto и неструктурных программ.
- •Мини-Паскаль.
- •Представление сложных типов. Адресная арифметика.
- •Проблемы реализации ввода-вывода. Идея буферизации.
- •Реализация процедур read и write.
- •Реализация структур управления.
- •Путь наверх. Реализация процедур-подпрограмм.
- •Передача параметров.
- •Сохранение и восстановление значений. Соглашение о связях.
- •Введение в теоретическое программирование. Границы программирования. Принципиальная и практическая неразрешимость.
- •О формальной спецификации. Мир задачи как автомат.
- •Процедуры как функции на множестве состояний. Процедуры как преобразователи предикатов.
- •Универсальные методы решения задач.
Раздельное описание абстрактных типов. Модульное программирование.
Технологичное программирование предполагает определение абстрактных типов, важных для решения широкого круга задач, повторное использование. Такое использование можно осуществить копированием фрагментов программ, относящихся к определённым абстрактным типам. Такое решение порождает серьёзные проблемы их согласования при редактировании.
Паскаль предлагает более эффективное решение – выделить определение типов в отдельный (и даже отдельно проверяемый и транслируемый) файл или модуль. Фактически модуль представляет собой совокупность областей описания, относящихся к определённым типам. Но, в отличие от областей описания, в модуле чётко различаются интерфейс пользователя модуля (interface; перечень объявлений данных и операций над ними) и реализация (список их определений).
unit {имя модуля}; {заголовок}
В Дельфи имя модуля обязано совпадать с именем файла с расширением *.pas, содержащего текст этого модуля.
Interface {Объявление языковых объектов, констант, типов, процедур и функций, редко – переменных, доступных для пользователей модулей, то есть программ, включавших в свои определения предложение uses}
Объявление констант, типов и переменных совпадает со знакомым. Объявление процедур и функций содержит только их заголовок.
Implementation {Определение процедур и функций в знакомом виде, объявление в интерфейсе, а также, возможно, и других языковых объектов, нужных для этого. В отличие от объектов интерфейса последние недоступны пользователю модуля (скрытые или инкапсулированные), в отличие от функций интерфейса, который наследуется пользователем.}
Программа, которая ссылается на модуль, ведёт себя точно так же, как программа, содержащая описание этого модуля.
[initialization] – перечень операторов, относящихся к инициализации или созданию объекта абстрактного типа.
[finalization] – последовательность операторов, относящихся к уничтожению объекта данного типа.
Программа, которая хочет получить доступ к интерфейсу модуля, содержит опцию uses.
Uses <логическое имя модуля> in <физическое имя модуля>
Unit stackunit;
Interface
Procedure Destroy(var top:pComponent);
Procedure Create(var top:pComponent);
Procedure Push(var top:pComponent;x:tInfo);
Implementation
{Определение процедур push, pop, empty, create, destroy}
Модули могут использовать друг друга. Типы можно описать либо в самом модуле, либо в используемом. Интерфейс и реализация могут ссылаться на разные модули.
type pComponent=^tComponent;
tComponent=record
info:tInfo;
next:pComponent;
end;
Определение типа tInfo естественно выделить в определённый модуль, поскольку понятие стека логически не зависит от типа входящих в него элементов.
Проблема с кратным использованием модулей.
Концепция модульного программирования предполагает создание уже не одной программы (текстового файла), а проекта – иерархически связанной совокупности модулей.
unit unit
program uses
з
unit unit
Объекты в разных модулях могут называться одинаково, что порождает конфликт имён.