Лекции по Turbo Pascal 7.0 (Лекции электронная версия), страница 7

чисел не более 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; ¦ *--¦---¬ ¦ ¦ ----¦--* ¦

L=====- ¦ ¦=====¦<--- L=====-

pTop L-->¦ *--¦-¬ pAux

L=====- ¦

¦

г=====¬ ¦

¦ D1 ¦ ¦

¦=====¦ ¦

¦ NIL ¦<-

L=====-

г=====¬ г=====¬

pTop^.D:=D2; ¦ *--¦---¬ ¦ D2 ¦

L=====- ¦ ¦=====¦

pTop L-->¦ *--¦-¬

L=====- ¦

¦

г=====¬ ¦

¦ D1 ¦ ¦

¦=====¦ ¦

¦ NIL ¦<-

L=====-

Добавление последующих компонент производится аналогично.

Рассмотрим процесс выборки компонент из стека. Пусть к моменту на-

чала выборки стек содержит три компоненты:

г=====¬ г=====¬

¦ *--¦---¬ ¦ D3 ¦

L=====- ¦ ¦=====¦

pTop L-->¦ *--¦-¬

L=====- ¦

¦

г=====¬ ¦

¦ D2 ¦ ¦

¦=====¦ ¦

--¦--* ¦<-

¦ L=====-

¦

¦ г=====¬

¦ ¦ D1 ¦

¦ ¦=====¦

L>¦ NIL ¦

L=====-

Первый оператор или группа операторов осуществляет чтение данных

из компоненты - вершины стека. Второй оператор изменяет значение ука-

зателя вершины стека:

г=====¬ г=====¬

D3:=pTop^.D; ¦ *--¦---¬ ¦ D3 ¦

pTop:=pTop^.pNext; L=====- ¦ ¦=====¦

pTop ¦ ¦ ¦

¦ L=====-

¦

¦ г=====¬

¦ ¦ D2 ¦

¦ ¦=====¦

L-->¦ *--¦-¬

L=====- ¦

¦

г=====¬ ¦

¦ D1 ¦ ¦

¦=====¦ ¦

¦ NIL ¦<-

L=====-

Как видно из рисунка, при чтении компонента удаляется из стека.

Пример. Составить программу, которая формирует стек, добавляет в

него произвольное количество компонент, а затем читает все компоненты

и выводит их на экран дисплея, В качестве данных взять строку симво-

лов. Ввод данных - с клавиатуры дисплея, признак конца ввода - строка

символов END.

Program STACK;

uses Crt;

type

Alfa= String[10];

PComp= ^Comp;