Реферат: Основные понятия алгоритмического языка
последовательность блоков. Если файл содержит n блоков, то они нуме-
руются от 1 через 1 до n. Кроме того, вводится понятие условной гра-
ницы между блоками, при этом условная граница с номером 0 расположена
перед блоком с номером 1, граница с номером 1 расположена перед бло-
ком с номером 2 и, наконец, условная граница с номером n находится
после блока с номером n.
Реализация прямого доступа осуществляется с помощью функций и про-
цедур FileSize, FilePos, Seek и Truncate.
Функция FileSize( var f ): Longint возвращает количество блоков в
открытом файле f.
Функция FilePos( var f ): Longint возвращает текущую позицию в
файле f. Позиция в файле - это номер условной границы. Для только что
открытого файла текущей позицией будет граница с номером 0. Это зна-
чит, что можно записать или прочесть блок с номером 1. После чтения
или записи первого блока текущая позиция переместится на границу с
номером 1, и можно будет обращаться к ьлоку с номером 2. После проч-
тения последней записи значение FilePos равно значению FileSize.
Процедура Seek( var f; N: Longint) обеспечивает назначение текущей
позиции в файле (позиционирование). В параметре N должен быть задан
номер условной границы, предшествующей блоку, к которому будет произ-
водиться последующее обращение. Например, чтобы работать с блоком 4,
необходимо задать значение N, равное 3. Процедура Seek работает с от-
крытыми файлами.
Процедура Truncate( var f ) устанавливает в текущей позиции приз-
нак конца файла и удаляет (стирает) все последующие блоки.
Пример. Пусть на НМД имеется текстовый файл ID.DAT, который содер-
жит числовые значения действительного типа по два числа в каждой
строке - значения аргумента и функции соответственно. Количество пар
чисел не более 200. Составить программу, которая читает файл, значе-
ния аргумента и функции записывает в одномерные массивы, подсчитывает
их количество, выводит на экран дисплея и записывает в файл компо-
нентного типа RD.DAT.
Program F;
var
rArg, rF: Array[1..200] of Real;
inf: Text;
outf: File of Real;
n, l: Integer;
begin
Assign(inf,'ID.DAT');
Assign(outf,'RD.DAT');
Reset(inf);
Rewrite(outf);
n:=0;
while not EOF(inf) do
begin
n:=n+1;
ReadLn(inf,rArg[n],rF[n])
end;
for l:=1 to n do
begin
WriteLn(l:2,rArg[l]:8:2,rF[l]:8:2);
Write(outf,rArg[l], rF[l]);
end;
close(outf)
end.
35. У К А З А Т Е Л И.
Операционная система MS - DOS все адресуемое пространство делит на
сегменты. Сегмент - это участок памяти размером 64 К байт. Для зада-
ния адреса необходимо определить адрес начала сегмента и смещение от-
носительно начала сегмента.
В TURBO PASCAL определен адресный тип Pointer - указатель. Пере-
менные типа Pointer
var p: Pointer;
содержат адрес какого - либо элемента программы и занимают 4 байта,
при этом адрес хранится как два слова, одно из них определяет сег-
мент, второе - смещение.
Переменную типа указатель можно описать другим способом.
type NameType= ^T;
var p: NameType;
Здесь p - переменная типа указатель, связанная с типом Т с помощью
имени типа NameType. Описать переменную типа указатель можно непос-
редственно в разделе описания переменных:
var p: ^T;
Необходимо различать переменную типа указатель и переменную, на
которую этот указатель ссылается. Например если p - ссылка на пере-
менную типа Т, то p^ - обозначение этой самой переменной.
Для переменных типа указатель введено стандартное значение NIL,
которое означает, что указатель не ссылается ни к какому объекту.
Константа NIL используется для любых указателей.
Над указателями не определено никаких операций, кроме проверки на
равенство и неравенство.
Переменные типа указатель могут быть записаны в левой части опера-
тора присваивания, при этом в правой части может находиться либо
функция определения адреса Addr(X), либо выражение @ X, где @ - унар-
ная операция взятия адреса, X - имя переменной любого типа, в том
числе процедурного.
Переменные типа указатель не могут быть элементами списка ввода -
вывода.
36. Д И Н А М И Ч Е С К И Е П Е Р Е М Е Н Н Ы Е
Статической переменной (статически размещенной) называется описан-
ная явным образом в программе переменная, обращение к ней осуществля-
ется по имени. Место в памяти для размещения статических переменных
определяется при компиляции программы.
В отличие от таких статических переменных в программах, написанных
на языке ПАСКАЛЬ, могут быть созданы динамические переменные. Основ-
ное свойство динамических переменных заключается в том, что они соз-
даются и память для них выделяется во время выполнения программы.
Размещаются динамические переменные в динамической области памяти
(heap - области).
Динамическая переменная не указывается явно в описаниях переменных
и к ней нельзя обратиться по имени. Доступ к таким переменным осу-
ществляется с помощью указателей и ссылок.
Работа с динамической областью памяти в TURBO PASCAL реализуется с
помощью процедур и функций New, Dispose, GetMem, FreeMem, Mark,
Release, MaxAvail, MemAvail, SizeOf.
Процедура New( var p: Pointer ) выделяет место в динамической об-
ласти памяти для размещения динамической переменной p^ и ее адрес
присваивает указателю p.
Процедура Dispose( var p: Pointer ) освобождает участок памяти,
выделенный для размещения динамической переменной процедурой New, и
значение указателя p становится неопределенным.
Проуедура GetMem( var p: Pointer; size: Word ) выделяет участок
памяти в heap - области, присваивает адрес его начала указателю p,
размер участка в байтах задается параметром size.
Процедура FreeMem( var p: Pointer; size: Word ) освобождает учас-
ток памяти, адрес начала которого определен указателем p, а размер -
параметром size. Значение указателя p становится неопределенным.
Процедура Mark( var p: Pointer ) записывает в указатель p адрес
начала участка свободной динамической памяти на момент ее вызова.
Процедура Release( var p: Pointer ) освобождает участок динамичес-
кой памяти, начиная с адреса, записанного в указатель p процедурой
Mark, то-есть, очищает ту динамическую память, которая была занята
после вызова процедуры Mark.
Функция MaxAvail: Longint возвращает длину в байтах самого длинно-
го свободного участка динамической памяти.
Функция MemAvail: Longint полный объем свободной динамической па-
мяти в байтах.
Вспомогательная функция SizeOf( X ): Word возвращает объем в бай-
тах, занимаемый X, причем X может быть либо именем переменной любого
типа, либо именем типа.
Рассмотрим некоторые примеры работы с указателями.
var
p1, p2: ^Integer;
Здесь p1 и p2 - указатели или пременные ссылочного типа.
p1:=NIL; p2:=NIL;
После выполнения этих операторов присваивания указатели p1 и p2 не
будут ссылаться ни на какой конкретный объект.
New(p1); New(p2);
Процедура New(p1) выполняет следующие действия:
-в памяти ЭВМ выделяется участок для размещения величины целого
типа;
-адрес этого участка присваивается переменной p1:
г=====¬ г=====¬
¦ *--¦--------->¦ ¦
L=====- L=====-
p1 p1^
Аналогично, процедура New(p2) обеспечит выделение участка памяти,
адрес которого будет записан в p2:
г=====¬ г=====¬
¦ *--¦--------->¦ ¦
L=====- L=====-
p2 p2^
После выполнения операторов присваивания
p1^:=2; p2^:=4;
в выделенные участки памяти будут записаны значения 2 и 4 соответ-
ственно:
г=====¬ г=====¬
¦ *--¦--------->¦ 2 ¦
L=====- L=====-
p1 p1^
г=====¬ г=====¬
¦ *--¦--------->¦ 4 ¦
L=====- L=====-
p2 p2^
В результате выполнения оператора присваивания
p1^:=p2^;
в участок памяти, на который ссылается указатель p1, будет записано
значение 4:
г=====¬ г=====¬
¦ *--¦--------->¦ 4 ¦
L=====- L=====-
p1 p1^
г=====¬ г=====¬
¦ *--¦--------->¦ 4 ¦
L=====- L=====-
p2 p2^
После выполнения оператора присваивания
p2:=p1;
оба указателя будут содержать адрес первого участка памяти:
г=====¬ г=====¬
¦ *--¦--------->¦ 4 ¦
L=====- --->L=====-
p1 ¦ p1^ p2^
¦
г=====¬ ¦
¦ *--¦-------
L=====-
p2
Переменные p1^, p2^ являются динамическими, так как память для них
выделяется в процессе выполнения программы с помощью процедуры New.
Динамические переменные могут входить в состав выражений, напри-
мер:
p1^:=p1^+8; Write('p1^=',p1^:3);
Пример. В результате выполнения программы:
Program DemoPointer;
var p1,p2,p3:^Integer;
begin
p1:=NIL; p2:=NIL; p3:=NIL;
New(p1); New(p2); New(p3);
p1^:=2; p2^:=4;
p3^:=p1^+Sqr(p2^);
writeln('p1^=',p1^:3,' p2^=',p2^:3,' p3^=',p3^:3);
p1:=p2;
writeln('p1^=',p1^:3,' p2^=',p2^:3)
end.
на экран дисплея будут выведены результаты:
p1^= 2 p2^= 4 p3^= 18
p1^= 4 p2^= 4
37. Д И Н А М И Ч Е С К И Е С Т Р У К Т У Р Ы
Д А Н Н Ы Х
Структурированные типы данных, такие, как массивы, множества, за-
писи, представляют собой статические структуры, так как их размеры
неизменны в течение всего времени выполнения программы.
Часто требуется, чтобы структуры данных меняли свои размеры в ходе
решения задачи. Такие структуры данных называются динамическими, к
ним относятся стеки, очереди, списки, деревья и другие. Описание ди-
намических структур с помощью массивов, записей и файлов приводит к
неэкономному использованию памяти ЭВМ и увеличивает время решения за-
дач.
Каждая компонента любой динамической структуры представляет собой
запись, содержащую по крайней мере два поля: одно поле типа указа-
тель, а второе - для размещения данных. В общем случае запись может
содержать не один, а несколько укзателей и несколько полей данных.
Поле данных может быть переменной, массивом, множеством или записью.
Для дальнейшего рассмотрения представим отдельную компоненту в ви-
де:
г=====¬
¦ D ¦
¦=====¦
¦ p ¦
L=====-
где поле p - указатель;
поле D - данные.
Описание этой компоненты дадим следующим образом:
type
Pointer = ^Comp;
Comp = record
D:T;
pNext:Pointer
end;
здесь T - тип данных.
Рассмотрим основные правила работы с динамическими структурами
данных типа стек, очередь и список, базируясь на приведенное описание
компоненты.
38. С Т Е К И
Стеком называется динамическая структура данных, добавление компо-
ненты в которую и исключение компоненты из которой производится из
одного конца, называемого вершиной стека. Стек работает по принципу
LIFO (Last-In, First-Out) -
поступивший последним, обслуживается первым.
Обычно над стеками выполняется три операции:
-начальное формирование стека (запись первой компоненты);
-добавление компоненты в стек;
-выборка компоненты (удаление).
Для формирования стека и работы с ним необходимо иметь две пере-
менные типа указатель, первая из которых определяет вершину стека, а
вторая - вспомогательная. Пусть описание этих переменных имеет вид:
var pTop, pAux: Pointer;
где pTop - указатель вершины стека;
pAux - вспомогательный указатель.
Начальное формирование стека выполняется следующими операторами:
г=====¬ г=====¬
New(pTop); ¦ *--¦---¬ ¦ ¦
L=====- ¦ ¦=====¦
pTop L-->¦ ¦
L=====-
г=====¬ г=====¬
pTop^.pNext:=NIL; ¦ *--¦---¬ ¦ ¦
L=====- ¦ ¦=====¦
pTop L-->¦ NIL ¦
L=====-
г=====¬ г=====¬
pTop^.D:=D1; ¦ *--¦---¬ ¦ D1 ¦
L=====- ¦ ¦=====¦
pTop L-->¦ NIL ¦
L=====-
Последний оператор или группа операторов записывает содержимое
поля данных первой компоненты.
Добавление компоненты в стек призводится с использованием вспо-
могательного указателя:
г=====¬ г=====¬ г=====¬
New(pAux); ¦ *--¦---¬ ¦ ¦ ----¦--* ¦
L=====- ¦ ¦=====¦ ¦ L=====-
pTop ¦ ¦ ¦<--- pAux
¦ L=====-
¦
¦ г=====¬
¦ ¦ D1 ¦
¦ ¦=====¦
L-->¦ NIL ¦
L=====-
г=====¬ г=====¬ г=====¬
pAux^.pNext:=pTop; ¦ *--¦---¬ ¦ ¦ ----¦--* ¦
L=====- ¦ ¦=====¦<--- L=====-
pTop ¦ ¦ *--¦-¬ pAux
¦ L=====- ¦
¦ ¦
¦ г=====¬ ¦
¦ ¦ D1 ¦ ¦
¦ ¦=====¦ ¦
L-->¦ NIL ¦<-
L=====-
г=====¬ г=====¬ г=====¬
pTop:=pAux; ¦ *--¦---¬ ¦ ¦ ----¦--* ¦
