А. Цветкова - Информатика и информационные технологии
15. Модули. Виды модулей
Модуль(UNIT) в Pascal – это особым образом оформленная библиотека подпрограмм. Модуль, в отличие от программы, не может быть запущен на выполнение самостоятельно, он может только участвовать в построении программ и других модулей.
Модуль в Pascal представляет собой отдельно хранимую и независимо компилируемую программную единицу.
Все программные элементы модуля можно разбить на две части:
1) программные элементы, предназначенные для использования другими программами или модулями, такие элементы называют видимыми вне модуля;
2) программные элементы, необходимые только для работы самого модуля, их называют невидимыми (или скрытыми).
unit <имя модуля>; {заголовок модуля}
interface
{описание видимых программных элементов модуля}
implementation
{описание скрытых программных элементов модуля}
begin
{операторы инициализации элементов модуля}
end.
Для обращения к переменной, описанной в модуле, необходимо применить составное имя, состоящее из имени модуля и имени переменной, разделенных точкой.
Рекурсивное использование модулей запрещено. Перечислим, какие бывают виды модулей.
1. Модуль SYSTEM.
Модуль SYSTEM реализует поддерживающие подпрограммы нижнего уровня для всех встроенных средств, таких как ввод-вывод, работа со строками, операции с плавающей точкой и динамическое распределение памяти.
2. Модуль DOS.
Модуль Dos реализует многочисленные процедуры и функции Pascal, которые эквивалентны наиболее часто используемым вызовам DOS, как, например, GetTime, SetTime, DiskSize и так далее.
3. Модуль CRT.
Модуль CRT реализует ряд мощных программ, предоставляющих полную возможность управления средствами компьютера РС, такими, как управление режимом экрана, расширенные коды клавиатуры, цвета, окна и звуковые сигналы.
4. Модуль GRAPH.
С помощью процедур и функций, входящих в этот модуль, можно создавать различные графические изображения на экране.
5. Модуль OVERLAY.
Модуль OVERLAY позволяет уменьшить требования к памяти программы DOS реального режима.
16. Ссылочный тип данных. Динамическая память. Динамические переменные. Работа с динамической памятью
Статической переменной (статически размещенной) называется описанная явным образом в программе переменная, обращение к ней осуществляется по имени. Место в памяти для размещения статических переменных определяется при компиляции программы. В отличие от таких статических переменных в программах, написанных на языке Pascal, могут быть созданы динамические переменные. Основное свойство динамических переменных заключается в том, что они создаются, и память для них выделяется во время выполнения программы.
Размещаются динамические переменные в динамической области памяти (heap-области). Динамическая переменная не указывается явно в описаниях переменных, и к ней нельзя обратиться по имени. Доступ к таким переменным осуществляется с помощью указателей и ссылок.
Cсылочный тип (указатель) определяет множество значений, которые указывают на динамические переменные определенного типа, называемого базовым типом. Переменная ссылочного типа содержит адрес динамической переменной в памяти. Если базовый тип является еще не описанным идентификатором, то он должен быть описан в той же самой части описания типов, что и тип-указатель.
Зарезервированное слово nil обозначает константу со значением указателя, которая ни на что не указывает.
Приведем пример описания динамических переменных.
var p1, p2: ^real;
p3, p4: ^integer;
…
Процедуры и функции работы с динамической памятью
1. Процедура New{var p: Pointer).
Выделяет место в динамической области памяти для размещения динамической переменной p", и ее адрес присваивает указателю p.
2. Процедура Dispose(var p: Pointer).
Освобождает участок памяти, выделенный для размещения динамической переменной процедурой New, и значение указателя p становится неопределенным.
3. Процедура GetMem(var p: Pointer; size: Word).
Выделяет участок памяти в heap-области, присваивает адрес его начала указателю p, размер участка в байтах задается параметром size.
4. Процедура FreeMem(varp: Pointer; size: Word).
Освобождает участок памяти, адрес начала которого определен указателем p, а размер – параметром size. Значение указателя p становится неопределенным.
5. Процедура Mark{var p: Pointer) записывает в указатель p адрес начала участка свободной динамической памяти на момент ее вызова.
6. Процедура Release(var p: Pointer) освобождает участок динамической памяти, начиная с адреса, записанного в указатель p процедурой Mark, т. е. очищает ту динамическую память, которая была занята после вызова процедуры Mark.
7. Функция MaxAvail: Longint возвращает длину в байтах самого длинного свободного участка динамической памяти.
8. Функция MemAvail: Longint возвращает полный объем свободной динамической памяти в байтах.
9. Вспомогательная функция SizeOf(X):Word возвращает объем в байтах, занимаемый X, причем X может быть либо именем переменной любого типа, либо именем типа.
17. Абстрактные структуры данных
Структурированные типы данных, такие как массивы, множества, записи, представляют собой статические структуры, так как их размеры неизменны в течение всего времени выполнения программы.
Часто требуется, чтобы структуры данных меняли свои размеры в ходе решения задачи. Такие структуры данных называются динамическими. К ним относятся стеки, очереди, списки, деревья и др.
Описание динамических структур с помощью массивов, записей и файлов приводит к неэкономному использованию памяти ЭВМ и увеличивает время решения задач.
Каждая компонента любой динамической структуры представляет собой запись, содержащую, по крайней мере, два поля: одно поле типа «указатель», а второе – для размещения данных. В общем случае запись может содержать не один, а несколько указателей и несколько полей данных. Поле данных может быть переменной, массивом, множеством или записью.
Если в указующей части содержится адрес одного элемента списка, то список называется однонаправленным (или односвязным). Если же он содержит две компоненты, то двусвязным. Над списками можно проводить различные операции, например:
1) добавление элемента к списку;
2) удаление элемента из списка с заданным ключом;
3) поиск элемента с заданным значением ключевого поля;
4) сортировка элементов списка;
5) деление списка на два и более списков;
6) объединение двух и более списков в один;
7) другие операции.
Однако, как правило, необходимости во всех операциях при решении различных задач не возникает. Поэтому в зависимости от основных операций, которые необходимо применить, существуют различные виды списков. Наиболее популярные из них – это стек и очередь.
18. Стеки
Стеком называется динамическая структура данных, добавление компоненты в которую и исключение компоненты из которой производится из одного конца, называемого вершиной стека. Стек работает по принципу LIFO(Last-In, First-Out) – «Поступивший последним, обслуживается первым».
Обычно над стеками выполняется три операции:
1) начальное формирование стека (запись первой компоненты);
2) добавление компоненты в стек;
3) выборка компоненты (удаление).
Для формирования стека и работы с ним необходимо иметь две переменные типа «указатель», первая из которых определяет вершину стека, а вторая – вспомогательная.
Пример. Составить программу, которая формирует стек, добавляет в него произвольное количество компонент, а затем читает все компоненты.
Program STACK;
uses Crt;
type
Alfa = String[10];
PComp = ^Comp;
Comp = Record
sD: Alfa;
pNext: PComp
end;
var
pTop: PComp;
sC: Alfa;
Procedure CreateStack(var pTop: PComp; var sC: Alfa);
begin
New(pTop);
pTop^.pNext:= NIL;
pTop^.sD:= sC;
end;
Procedure AddComp(var pTop: PComp; var sC: Alfa);
var pAux: PComp;
begin
NEW(pAux);
pAux^.pNext:= pTop;
pTop:= pAux;
pTop^.sD:= sC;
end;
Procedure DelComp(var pTop: PComp; var sC: ALFA);
begin
sC:= pTop^.sD;
pTop:= pTop^.pNext;
end;
begin
Clrscr;
writeln( ВВЕДИ СТРОКУ );
readln(sC);
CreateStack(pTop, sC);
repeat
writeln( ВВЕДИ СТРОКУ );
readln(sC);
AddComp(pTop, sC);
until sC = 'END';
19. Очереди
Очередью называется динамическая структура данных, добавление компоненты в которую производится в один конец, а выборка осуществляется с другого конца. Очередь работает по принципу FIFO (First-In, First-Out) – «Поступивший первым, обслуживается первым».
Пример. Составить программу, которая формирует очередь, добавляет в нее произвольное количество компонент, а затем читает все компоненты.
Program QUEUE;
uses Crt;
type
Alfa = String[10];
PComp = ^Comp;
Comp = record
sD: Alfa;
pNext: PComp;
end;
var
pBegin, pEnd: PComp;
sC: Alfa;
Procedure CreateQueue(var pBegin,pEnd: PComp; var
sC: Alfa);
begin
New(pBegin);
pBegin^.pNext:= NIL;
pBegin^.sD:= sC;
pEnd:= pBegin;
end;
Procedure AddQueue(var pEnd: PComp; var sC:
Alfa);
var pAux: PComp;
begin
New(pAux);
pAux^.pNext:= NIL;
pEnd^.pNext:= pAux;
pEnd:= pAux;
pEnd^.sD:= sC;
end;
Procedure DelQueue(var pBegin: PComp; var sC:
