Программирование на Turbo Pascal

Секция инициализации содержит те действия, которые должны выполняться когда наш модуль подключается к программе, то есть до того как начнёт работать сама программа. Модуль graph, например устанавливает в секции инициализации значения по умолчанию цвета линий и фона, стиль линий, стиль заливки т.п.

При сохранении модуля ему нужно дать такое же имя, как и после unit в тексте модуля. Имена файлов, содержащих модули, должны иметь расширение
«pas», также как и программы.

В случаях, когда несколько модулей содержат объекты с одинаковыми именами, обращаться к ним нужно с указанием имени модуля. Пусть, например, модули unit1 и unit2 содержат процедуры с одинаковыми именами proc1, тогда обращаться к ним следует так: unit1.proc1; и unit2.proc2; .

Преимущества модулей:

1. Средства, взятые из модулей позволяют не повторять в программах одни и те же фрагменты.

2. Переменные, процедуры и другие объекты можно скрыть в секции реализации, если их необдуманное выполнение может испортить программу.

3. Модули компилируются отдельно от главной программы, поэтому при компиляции всей программы обрабатывается только главная программа.

(меньшие затраты времени при отладке программ). Это особенно важно для больших программ.

4. Большая программа становится более понятной, если разные её части расположить в разных модулях, в соответствии с их назначением.

12. Динамические переменные

Все известные нам на данный момент переменные являются статическими, это означает, что память под них выделяется один раз при запуске программы, и в течение всего времени её работы переменные занимают отведённые им участки. Иногда такой подход может оказаться невыгодным. Например, при хранении табличных данных в виде массива, приходится заводить массив большого размера, поскольку заранее неизвестно, сколько строк содержится в таблице. В результате часть памяти, занятая под массив, не используется. В подобных задачах хотелось бы использовать столько памяти, сколько необходимо в каждый конкретный момент времени, то есть распределять память динамически.

В Турбо Паскале есть возможность создания динамических переменных (то есть таких, которые можно заводить и уничтожать во время работы программы по мере необходимости). Для этого в программе объявляют не саму переменную нужного нам типа, а указатель на эту переменную, например: var p: ^real; здесь p - имя переменной-указателя; знак "^" показывает, что p является не обычной переменной, а указателем; real - тип той переменной, на которую указывает p. Переменная p представляет собой не что иное как адрес того места в памяти, где будет храниться сама динамическая переменная (в нашем случае число типа real).

Для всех динамических переменных в памяти отводится пространство, называемое динамической областью, или кучей. Перед тем как пользоваться динамической переменной, требуется выделить для неё место в куче. Это делается с помощью процедуры New, например:

New(p);

В результате такого действия в куче выделено место под переменную типа real, обратиться к ней можно, записав p^, например p^:=123.5.

Если потребуется изменить значение указателя, например, заставить его указывать на другую переменную, то старую переменную следует уничтожить, то есть объявить занимаемую старой переменной память свободной. Если этого не сделать, то при изменении указателя сама переменная станет мусором (место в памяти объявлено занятым, а получить к нему доступ уже невозможно). Уничтожение динамической переменной выполняется процедурой Dispose: Dispose(p);

Рассмотрим теперь операции, которые можно выполнять над указателями.

1. Присваивание. Указателю можно присваивать значение другого указателя такого же типа, а также значение nil, которое означает «ни на что не указывает». В указатель можно также положить адрес какой-либо переменной, например: p:=Addr(a); или p:=@a; хотя необходимость в этом возникает редко.

2. Сравнение. Два указателя можно сравнивать только на равенство (или неравенство). Можно сравнивать указатель с nil, с адресами переменных.

С динамическими переменными можно выполнять все действия, разрешённые для статических переменных, например: if p^ >= q^ then p^ := q^;

Рассмотрим теперь несколько искусственный пример использования динамических переменных: пусть требуется сложить два числа, не используя статических переменных: var pa,pb: ^real; begin new(pa); new(pb); write('Введите a: '); readln(pa^); write('Введите b: '); readln(pb^); writeln('a+b=',pa^+pb^); dispose(pa); dispose(pb); readln; end.

Кроме описанных указателей существуют ещё так называемые нетипизированные указатели (тип pointer), которые могут служить указателями на переменные любых типов, однако необходимость в них возникает редко, поэтому рассматривать их подробно мы не будем.

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

Вернёмся теперь к вопросу об экономии памяти при хранении табличных данных. С использованием указателей можно отказаться от массива и использовать динамические структуры. Самой простой из них является список, который схематично изображается так:

Прямоугольники на этой схеме - динамические переменные типа запись, Data
- поле (или поля), содержащие полезную информацию (например фамилии и номера телефонов), поле, которое изображено ниже Data - это указатель на следующую запись. Переменная List также является указателем на запись.
Жирная точка в поле «следующий элемент» в самой последней записи означает, что там лежит значение nil, чтобы показать, что эта запись - последняя в списке.

Для описания списка на Паскале достаточно описать тип указателя на запись и тип самой записи. Выглядит всё это так: type tItemPtr = ^tItem; {указатель на элемент} tItem = record

Data: tData; {полезные данные}

Next: tItemPtr; {указатель на следующий элемент списка} end;

В первой строке этого объявления бросается в глаза использование неопределённого типа tItem. Такое исключение из правил в Турбо Паскале сделано умышленно, в противном случае не было бы возможности строить списки и другие связанные структуры из динамических переменных.

Объявить сам список можно как указатель на элемент: var List : tItemPtr; пока наш список пуст, в List следует положить значение nil. При создании первого элемента будем выполнять действия New(List); List^.Next:=nil.

В списках всегда хранится ровно столько элементов, сколько нужно; если какой-либо элемент данных потерял свою ценность, то его всегда можно удалить из списка; если появились новые данные, то можно добавить новый элемент.

Напишем теперь модуль для работы со списками. В нём содержатся процедуры первоначальной подготовки списка; добавления элемента в начало списка; удаления элемента, следующего за указанным; нахождения элемента с заданным номером; подсчета элементов и очистки списка.

14. Динамические переменные: другие виды списков, стек и очередь

1. Другие виды списков

Кроме рассмотренных списков возможны более сложные варианты, связанные с наличием двух дополнительных свойств:

1. Двунаправленность списка. В каждом элементе таких списков есть не только указатель на следующий элемент, но и на предыдущий. Такая организация может оказаться полезной при добавлении или удалении элемента, предшествующего указанному.

2. Замкнутость списка. Поле next в последнем элементе указывает на первый элемент. Иначе такие списки называются кольцевыми. Этот вид позволяет упростить процедуру удаления элемента списка и другие операции.

2. Стек и очередь

Стеком называется такой способ хранения данных, при котором элемент, записанный в хранилище данных, последним всегда извлекается первым
- дисциплина LIFO ( «last in - first out»). При извлечении элемента происходит его удаление со стека.

Рассмотрим простейший пример использования стека. Предположим, что имеется строка, состоящая из одних лишь открывающих и закрывающих скобок.
Требуется определить, является ли она правильным скобочным выражением (то есть для каждой открывающей скобки должна найтись закрывающая). Заведём массив и переменную для хранения номера последнего значимого элемента в массиве (то есть вершины стека), в который при проходе по строке будем складывать все открывающиеся скобки (с увеличением номера вершины на 1), а при встрече с закрывающей будем удалять соответствующую открывающую (попросту уменьшать номер вершины стека). Если окажется, что «пришла» закрывающая скобка, а стек пуст (то есть номер вершины равен 0), то выражение ошибочно. Это же можно сказать и в случае, когда строка закончилась, а стек не пуст.

Очевидно, что для реализации такого стека массив использовать не обязательно, достаточно хранить в некоторой переменной лишь число открывающих скобок. При поступлении закрывающей скобки из этой переменной вычитается 1. Ошибка возникает, если значение переменной стало отрицательным, или при достижении конца строки оно не равно нулю.

Для данных более сложного вида стек можно организовать с помощью однонаправленного некольцевого списка. Чтобы положить элемент в стек, нужно добавить его в начало списка, чтобы извлечь со стека (получить данные первого элемента, после чего удалить его из списка).

Любая реализация стека должна содержать следующие процедуры и функции: procedure InitStack - инициализация стека; procedure Push(d: tData) - положить элемент в стек; procedure Pop(var d: tData) - извлечь элемент с вершины стека; function NotEmpty: boolean - проверка стека на пустоту;

Очередь отличается от стека тем, что последний пришедший в неё элемент будет извлечён последним, а первый - первым («FIFO»). С помощью списков её можно организовать следующим образом: будем хранить не только указатель на «голову» списка, но и на «хвост»; добавлять будем в «хвост», а извлекать - из «головы».

Любая реализация очереди (не обязательно с помощью списков) должна
«уметь» выполнять такие действия: procedure InitQueue - инициализация очереди; procedure AddQueue(d: tData) - поставить элемент в очередь; procedure SubQueue(var d: tData) - извлечь элемент из очереди; function NotEmpty: boolean - проверка очереди на пустоту;

15. Деревья и поиск в деревьях

Деревьями называются структуры данных следующего вида:

Элементы дерева называются вершинами. Вершина Tree^ называется корнем дерева, а всё множество вершин, связанных с некоторой вершиной с помощью одного из указателей называется поддеревом. Вершины, у которых все указатели равны nil, иногда называют листьями.

Подробнее мы рассмотрим вариант двоичного дерева, то есть такого, в котором каждая вершина имеет два поддерева (любое из них может оказаться пустым). Такие деревья оказываются очень удобными для решения задачи поиска, когда ключи для наших данных (например фамилии при поиске телефонных номеров) можно сравнивать на "=", "". В каждую вершину дерева заносится элемент данных, причём делается это таким образом, чтобы для любой вершины все ключи данных (или сами данные в простейшем случае) из левого поддерева были меньше ключа этой вершины, а все ключи из правого - больше. Выполнения такого требования можно достигнуть при последовательном добавлении элементов (то есть построении дерева, начиная с «нуля», точнее с nil).

При описанном построении дерева поиск оказывается довольно простым делом: сначала мы сравниваем искомый ключ с ключом корня дерева. Если эти два ключа совпадают, то элемент найден, в противном случае выполняем поиск в левом поддереве, иначе - в правом, далее в выбранном поддереве вновь выполняем сравнение его корня с искомым ключом, и т. д. Этот процесс закончится либо когда мы нашли ключ, либо когда очередное поддерево оказалось пустым (это означает, что такой ключ в дереве отсутствует).

Для реализации двоичного дерева сначала рассмотрим его описание на
Паскале: type tNodePtr = ^tNode; {указатель на вершину} tNode = record data: tMyData; left,right: tNodePtr; end; tTree = tNodePtr; {для доступа к дереву достаточно хранить указатель на его корень}

Под данными (tMyData) будем понимать запись, состоящую из ключа, необходимого для сравнений, и собственно данных: type tMyData = record key: tKey; data: tData; end;

Для того чтобы реализовать действия с двоичным дерево, нам понадобятся так называемые рекурсивные процедуры. Функция или процедура называется рекурсивной, если она вызывает сама себя. Такой вариант рекурсии называется прямым. Кроме того, бывает и косвенная рекурсия, когда одна процедура вызывает другую, а та в свою очередь вызывает первую.

В качестве примера рассмотрим функцию для вычисления факториала, в которой мы заменим цикл (или итерацию) рекурсией. Её идея проста: если аргумент равен нулю, то возвращаем значение 1, в противном случае возвращаем значение аргумента, умноженное на факториал (то есть ту же функцию) от числа, на единицу меньшего. На Паскале всё это будет выглядеть следующим образом: function factorial(x: byte): longint; begin if x=0 then factorial:=1 else factorial:=x*factorial(x-1); end;

Подобным образом можно применить рекурсию для вычисления n-го числа
Фибоначчи, хотя этот способ требует много лишних действий: function fib(n: integer): integer; begin if n

16. Достоинства и недостатки, интересные факты