Файл: Лекции(ЯВУ)-Паскаль.doc

По способу распределения памяти данных в программах делятся на статические и динамические. Данные статической структуры – это данные, размещение которых в памяти ЭВМ и взаимосвязи между элементами остаются неизменными во время выполнения программы в области их действия. К данным статической структуры относятся переменные базовых типов, массивы, записи, множества, объявляемые в программе, как локальные, так и глобальные.

Данные динамической структуры – это данные, которые могут размещаться в памяти ЭВМ и удаляться из памяти во время выполнения программы с помощью системных процедур, таких как NewиDispose.

Динамические структуры данных бывают двух видов:

несвязанные динамические данные;
связанные динамические данные.

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

10.2. Объявление и создание динамических структур данных. Указатели

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

При объявлении динамической переменной в разделе описаний указывается не сама переменная, а указатель (ссылка) на нее, следующим образом:

<имя указателя>: ^ <тип указателя>;

Такое объявление называется объявлением типизированного указателя.

Например,

VarP: ^char; {указатель на переменную типаchar}

Указатель – это переменная, значением которой является адрес другой переменной заданного в объявлении указателя типа.

Рассмотрим пример использования указателя типа char. Указатель объявляется с помощью операции разыменования (^). Использование имени указателя в программе означает обращение к адресу ячейки памяти. Чтобы обратиться к содержимому ячейки, на которую ссылается указатель, требуется после имени указателя поставить символ ‘^’.

P^ - содержимое ячейки, адрес которой является значением указателяP.

P: ^ char P^

Адрес‘*’

Выделение и освобождение памяти под динамические переменные выполняются стандартными процедурами New,Dispose,GetMem,FreeMem,MarkиRelease, соответственно, где

ProcedureNew(Varp:pointer); размещает динамическую переменную и возвращает ее адрес как значение указателяp;
ProcedureDispose(Varp:pointer); уничтожает динамическую переменную;
ProcedureGetMem(Varp:pointer;Size:word); размещает динамическую переменную указанного размера и возвращает ее адрес как значение указателяp;
ProcedureFreeMem(Varp:pointer;Size:word); уничтожает динамическую переменную указанного размера;
ProcedureMark(Varp:pointer); размещает динамическую переменную и возвращает ее адрес как значение указателяp; эта переменная уничтожается с помощью процедурыRelease;
ProcedureRelease(Varp); уничтожает динамическую переменную указанного размера.

Описатель pointerиспользуется для объявления нетипизированного указателя, который совместим с указателями любого типа.

Операции над указателями

Переменная типа «указатель» может находиться в трех состояниях:

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

В неопределенном состоянии указатель бывает в начале работы программы до размещения переменной в памяти ЭВМ и присвоения указателю конкретного адреса или значения nil.

Над указателями можно выполнять следующие операции:

Объявление.

Type PInt = ^integer;

Var a,b: Pint;

Указатели a,bнаходятся в неопределенном состоянии.

Выделение памяти под переменную.

Type PInt = ^integer;

Var a,b: Pint;

………………………….

New(a); New(b);

Указатели a,bпринимают значения адресов распределенной под неименованные переменные памяти. Обращение к этим переменным осуществляется с помощью операции косвенной адресации;a^,b^ – значения динамически размещенных переменных.

Присвоение указателю значения адреса нединамической переменной.

Var

P: ^char;

P1: ^char;

ch: char;

…………….

P:=@ch; { @ - операция определения адреса }

…………….

New(P1); …..P:=P1; {присвоение указателю значения другого указателя }

Присвоение указателю значения возможно двумя способами:

с помощью операции @ определения адреса другой переменной;
с помощью присвоения указателю значения другого указателя.

Занесение информации по адресу, хранимому в переменной типа «указатель» a^:=^b; илиa^:=2;

Освобождение памяти.

Dispose(a);

Указатель aпереходит в неопределенное состояние. Различие между состояниемnilи неопределенным состоянием состоит в следующем. Если два указателяp1 иp2 имеют значениеnil, то результат операции сравненияp1=p2 естьtrue. Если указателиp1 иp2 находятся в неопределенном состоянии, то их невозможно сравнивать.

С помощью указателей можно работать со связанными и несвязанными динамическими структурами данных. Динамические свойства несвязанных динамических данных выражаются в том, что они могут “появляться” и “исчезать” во время работы программы.

Связанные, динамические данные характеризуются тем, что при размещении в памяти элементы таких данных связываются с помощью указателей. Рассмотрим в качестве примера механизм связывания элементов линейного списка.

Программа создания и обработки линейного списка

Линейный список – это структура данных, представляющая собой последовательность компонент, связанных между собой адресами, как показано на рис. 1.

Информ. Поле1

Адрес 2-го элемента

Информ. Поле2

Адрес 3-го элемента

………..

Информ. Поле n-1

Адрес n-го элемента

Информ. Поле n

nil

Рис. 10.1.

На рис. 10.1 используются следующие обозначения:

PN– адрес первого элемента списка, который запоминается для работы со списком при его создании;

nil- признак последнего элемента списка.

Над линейными списками выполняются следующие операции:

создание пустого списка;
последовательный просмотр списка и поиск заданного элемента;
добавление нового элемента в упорядоченный список;
добавление элемента в конец списка;
добавление элемента в начало списка;
удаление заданного элемента из списка.

В программе на языке Паскаль элемент линейного списка объявляется с помощью типа «запись» следующего вида:

Туре TElem=recodrd

Inf:integer; {информационное поле}

Next:TPtr{ поле связи (адрес следующего элемента списка) }

End;

TPtr– тип «указатель», который объявляется следующим образом:

Type TPtr=^ TElem;

Указательный тип используется для определения переменных, значением которых являются адреса размещенных в памяти переменных, тип которых совпадает с типом указателя. Для размещения в памяти элементов списка используется стандартная процедура динамического распределения памяти; в языке Паскаль эта процедура имеет имя New. Для удаления элемента из списка служит стандартная процедура освобождения памятиDispose. Адресное поле последнего элемента списка содержит значениеnil, специальный, пустой адрес, который является признаком конца списка.

Пример программы создания и обработки линейного списка.

program Project2;

{$APPTYPE CONSOLE}

uses

Windows;

type TPtr=^TElem;

TElem=record

Inf:integer;

Next:TPtr;

end;

Var Beg: TPtr; Value: integer; Rejim: byte;

Procedure Init_list(Var P: TPtr);

Begin P:=nil; end;

Procedure Add_list(Var P: TPtr);

Var PT,TPR,Prev:TPtr; Prizn: byte;

begin

write('Input Value: '); read(Value);

if P=nil then begin New(TPR); P:=TPR;

TPR^.Inf:=Value; TPR^.Next:=nil;

write('First element of list is created - ',Value);

end

else begin PT:=P; PREV:=nil; Prizn:=0;

while PT<>nil do

begin if Value<PT^.Inf then begin

if PREV=nil then begin

New(TPR); P:=TPR; TPR^.Inf:=Value;

TPR^.Next:=PT;

write('Element ',Value,' added before first element'); end

else begin

New(TPR); PREV^.Next:=TPR; TPR^.Inf:=Value;

TPR^.Next:=PT;

Write('Element ',Value, ' is added between two other elements ');

end;

Prizn:=1; break;

end;

PREV:=PT; PT:=PT^.Next;

end;

if Prizn=0 then begin

New(TPR); TPR^.Inf:=Value;

TPR^.Next:=nil; PREV^.Next:=TPR;

write('Element ',Value, ' is added after last element');

end; end;

end;

Procedure Del_Elem(Var P: TPtr);

Var

PT,TPR,Prev:TPtr; Prizn: byte;

begin

if P=nil then write('list is empty!!!')

else begin write('Input value: '); read(Value);

PT:=P; PREV:=nil; Prizn:=0;

while PT<>nil do begin

writeln(PT^.Inf);

if Value=PT^.Inf then begin

if PREV<>nil then begin

PREV^.Next:=PT^.Next; Prizn:=1;

write('Element is deleted '); break;

end

else begin P:=PT^.Next; Prizn:=1;

write('Element is deleted '); break;

end;

Dispose(PT);

end;

PREV:=PT; PT:=PT^.Next;

end;

if Prizn=0 then write('Element is not founded ' );

end;

Procedure Display_list(P: TPtr);

Var

PT:TPtr; i: byte;

begin

i:=0; PT:=P;

if P=nil then begin write('list is empty!!!'); exit; end;

Writeln; write(' List =[');

while PT<>nil do

begin i:=i+1;

write(PT^.Inf,' '); PT:=PT^.Next;

end;

write(']'); write(' Number of elements = ',i);

end;

begin

while True do

begin

writeln;

write('0 -- Exit; '); write('1 -- Create; '); write('2 -- Display; ');

write('3 -- Add; '); writeln('4 -- Delete; '); writeln('Input option (0 -- 4)');

readln(Rejim);

case(Rejim) of

0: begin readln; exit; end;

1: Init_list(Beg);

2: Display_list(Beg);

3: Add_list(Beg);

4: Del_Elem(Beg)

else write('Error!!! ')

end; end; end.

Результаты работы программы.