Глава 10 . Указатели и Динамическая память

§ Динамическая память

§ Типизированные и нетипизированные указатели

§ Процедуры работы с указателями

§ Использование динамической памяти для размещения данных большого объема

§ Динамические структуры

§ Создание и работа со списком

 

 

Билет 39. Динамическая память. Размещение данных в динамической памяти.

 

 

ДИНАМИЧЕСКАЯ ПАМЯТЬ, УКАЗАТЕЛИ

В Delphi Рascal есть средства, которые позволяют использовать динамическую память (heap-область, куча) под размещение данных большой размерности, при организации динамических структур и для других целей. При этом происходит динамическое размещение данных, что означает использование области динамической памяти непосредственно во время работы (при динамическом размещении заранее не известен ни тип, ни количество размещаемых данных). Средство управления динамической памятью – указатели.

Билет 40.Указатели. Типизированные и нетипизированные указатели. Процедуры работы с указателями.

 

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

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

Var PInt: ^Integer; PReal: ^Real;

Нетипизированные указатели (указатели) хранят просто адреса, которые не связаны с данными конкретных типов:

Var P: Pointer;

Nil – «нулевой» адрес.

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

• прикладная программа запрашивает у системы фрагмент памяти определенного размера;

• если в вычислительной машине есть свободная память требуемого объема, то система выделяет этот фрагмент;

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

• прикладная программа получает указатель;

• прикладная программа размещает данные в выделенной области, начиная с указанного адреса;

• по окончании работы с этими данными прикладная программа обязана сообщить системе о том, что выделенная область памяти может быть снова получена системой, иначе говоря, освободить выделенный фрагмент.

 

 

Билет 41. Динамическая память. Использование динамической памяти для размещения данных большого объема. Динамические структуры.

 

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

New(Var <типизированный указатель>);

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

Var

PInt: ^Integer;

PReal: ^Real;	{New – функция}
Begin	Type TyPInt: ^Integer;
New(PInt);	Var PInt: TyPInt;…
New(PReal);	PInt:= New(TyPInt);…

PInt^:= 2;

PReal^:= 2*pi;

Динам. память

число

Integer

–

байта

число

R

eal

–

байт

Статич

. память

PInt

(4

байта)

–

адрес

P

R

eal

(4

байта)

–

адрес

New

PReal^:= Sqr(PReal^) + PInt^ - 1; End.

После процедуры New в куче можно разместить значение соответствующего типа. Используется значок ^ – разыменование указателя.

Передавать значения между указателями можно в том случае, если они связаны с одним и тем же типом данных (либо один из них – нетипизированный указатель или "нулевой адрес" Nil).

Type

TType = (red, green, blue);

PType = ^TType; Var

P1,P2: PType;

PInt: ^Integer; P: Pointer;

Begin

New(P1); New(P2);

P1^:= red; P2^:= green; P1:= P2;...

PInt:= P; P:= P1; P2:= Nil;

Writeln(Cardinal(P1)); End.

При выполнении операции присваивания теряется участок памяти, на который ссылался указатель, стоящий слева от оператора присваивания. Это типичный случай создания "мусора" (garbage) в динамической памяти.

Процедура

Dispose(<типизированный указатель>);

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

При работе с нетипизированными указателями, в основном, используются другие процедуры:

GetMem(Var P: Pointer, Size: Word)

{резервирование памяти}

FreeMem(P: Pointer, Size: Word)

{освобождение памяти}

где Р – нетипизированный указатель, Size – размер в байтах требуемой или освобождаемой части кучи.

Использование процедур GetMem/FreeMem (как и вообще вся работа с динамической памятью) требует особой осторожности и соблюдения правила: освобождать нужно ровно столько памяти, сколько ее было зарезервировано, иименно с того адреса, с которого она была зарезервирована.

РАЗМЕЩЕНИЕ ДАННЫХ БОЛЬШОГО ОБЪЕМА В ДИНАМИЧЕСКОЙ ПАМЯТИ

Type Dim100x200 = array [1..100,1..200] of Real;

Целесообразно «большие» массивы размещать в динамической памяти.

Type

Dim100 = array [1..100] of Real;

{строка-массив размером 800 байт}

Dim100Ptr = ^Dim100;

{ указатель на строку размером 4 байта }

Dim100x200 = array [1..200] of Dim100Ptr

{ массив указателей размером 800 байт }

Var

D: Dim100x200; I,J: Byte;

Begin for I:= 1 to 200 do New(D[i]);

… D[I]^[J]:= 0.5; {I = 1..200, J = 1..100} End.

Х1

Х2

Х3

...

ХN-1

ХN

Билет 42. Создание и работа со списком.

 

ДИНАМИЧЕСКИЕ СТРУКТУРЫ

• Список – упорядоченный набор элементов одного типа. Размер списка может изменяться. Элемент

списка (любой динамической

данные, и адресной, где хранятся указатели на соседние элементы.

? Пусто

структуры) состоит из двух частей: ДобавитьУдалить информационной, содержащей? Поиск

• Очередь – список, в один конец которого элементы добавляются, а

из другого изымаются. Очередь – это Добавить

Х1

Х2

...

ХN

Удалить

Х

Х

...

Х

N

Добавить

? Пусто

устройство FIFO (First In, First Out). Удалить

• Стек – список, в один конец которого элементы добавляются, и из него же изымаются. Стек – это устройство LIFO (Last In, First Out).

ДИНАМИЧЕСКИЕ СТРУКТУРЫ

•

? Поиск

Удалить

узел

Удалить

дугу

Добавить

узел

Граф – структура, состоящая из узлов и дуг, каждая дуга направлена от одного узла к другому.

•

Корневой

узел

Дерево – направленный граф, у которого имеется корневой узел, не имеющий дуг, входящих в него; в каждый узел входит одна дуга; в каждый узел можно попасть из корневого за несколько шагов.

 

 

СОЗДАНИЕ ЛИНЕЙНОГО ОДНОСВЯЗНОГО СПИСКА

Type

PMemberType = ^MemberType;

MemberType = record

Name: String;

Phone: Word; Next: PMemberType end;

Var

First, Member: PMemberType;

Указатель на тип MemberType описан до того, как описан сам тип MemberType. В Delphi Рascal такое предварительное использование идентификатора типа разрешено только при создании указателя на этот тип.

В запись MemberType включено поле Next, которое представляет собой указатель на запись MemberType. Это есть ссылка на соседний элемент списка.

СОЗДАНИЕ ЛИНЕЙНОГО ОДНОСВЯЗНОГО СПИСКА

Begin Member:= Nil; {неопределенный указатель – показывает, что память для Member не выделена}

for I:= 1 to 4 do

Begin

New(First); ¹

First^.Next:= Member;

First^.Name:= '...';

Next 2 (Адрес 1)

Phone 2

Name 2

Next 1 (Nil)

Phone 1

Name 1

First^.Phone:=...;

Member:= First; Y XKsG6kPj2UA6S0ARl942XBn42L7czEGFiGyx9UwGThRgUVxe5JhZP/I7DZtYKQnhkKGBOsYu0zqU NTkMM98Ri7f3vcMosq+07XGUcNfq2yR51A4blg81drSqqTxsjs7A64jj8i59HtaH/er0tX14+1yn ZMz11bR8AhVpiudj+MEXdCiEaeePbINqDUiR+DvFu5+L2v1tXeT6P3vxDQAA//8DAFBLAQItABQA BgAIAAAAIQC2gziS/gAAAOEBAAATAAAAAAAAAAAAAAAAAAAAAABbQ29udGVudF9UeXBlc10ueG1s UEsBAi0AFAAGAAgAAAAhADj9If/WAAAAlAEAAAsAAAAAAAAAAAAAAAAALwEAAF9yZWxzLy5yZWxz UEsBAi0AFAAGAAgAAAAhAJ8LS7acAgAA1QYAAA4AAAAAAAAAAAAAAAAALgIAAGRycy9lMm9Eb2Mu eG1sUEsBAi0AFAAGAAgAAAAhANwuQxPYAAAAAwEAAA8AAAAAAAAAAAAAAAAA9gQAAGRycy9kb3du cmV2LnhtbFBLBQYAAAAABAAEAPMAAAD7BQAAAAA= "> end;

End. ³

e vphcqwbqQ+PZQDpLQBGX3jZcGfjYvtzMQYWIbLH1TAZOFGBRXF7kmFk/8jsNm1gpCeGQoYE6xi7T OpQ1OQwz3xGLt/e9wyiyr7TtcZRw1+rbJHnUDhuWDzV2tKqpPGyOzsDriOPyLn0e1of96vS1fXj7 XKdkzPXVtHwCFWmK52P4wRd0KIRp549sg2oNSJH4O8W7n4va/W1d5Po/e/ENAAD//wMAUEsBAi0A FAAGAAgAAAAhALaDOJL+AAAA4QEAABMAAAAAAAAAAAAAAAAAAAAAAFtDb250ZW50X1R5cGVzXS54 bWxQSwECLQAUAAYACAAAACEAOP0h/9YAAACUAQAACwAAAAAAAAAAAAAAAAAvAQAAX3JlbHMvLnJl bHNQSwECLQAUAAYACAAAACEALmAbN54CAADVBgAADgAAAAAAAAAAAAAAAAAuAgAAZHJzL2Uyb0Rv Yy54bWxQSwECLQAUAAYACAAAACEA3C5DE9gAAAADAQAADwAAAAAAAAAAAAAAAAD4BAAAZHJzL2Rv d25yZXYueG1sUEsFBgAAAAAEAAQA8wAAAP0FAAAAAA== ">

Next 4 (Адрес 3)

Phone 4

Name 4

Next 3 (Адрес 2)

Phone 3

Name 3

e vphcqwbqQ+PZQDpLQBGX3jZcGfjYvtzMQYWIbLH1TAZOFGBRXF7kmFk/8jsNm1gpCeGQoYE6xi7T OpQ1OQwz3xGLt/e9wyiyr7TtcZRw1+rbJHnUDhuWDzV2tKqpPGyOzsDriOPyLn0e1of96vS1fXj7 XKdkzPXVtHwCFWmK52P4wRd0KIRp549sg2oNSJH4O8W7n4va/W1d5Po/e/ENAAD//wMAUEsBAi0A FAAGAAgAAAAhALaDOJL+AAAA4QEAABMAAAAAAAAAAAAAAAAAAAAAAFtDb250ZW50X1R5cGVzXS54 bWxQSwECLQAUAAYACAAAACEAOP0h/9YAAACUAQAACwAAAAAAAAAAAAAAAAAvAQAAX3JlbHMvLnJl bHNQSwECLQAUAAYACAAAACEAY9ZgT54CAADVBgAADgAAAAAAAAAAAAAAAAAuAgAAZHJzL2Uyb0Rv Yy54bWxQSwECLQAUAAYACAAAACEA3C5DE9gAAAADAQAADwAAAAAAAAAAAAAAAAD4BAAAZHJzL2Rv d25yZXYueG1sUEsFBgAAAAAEAAQA8wAAAP0FAAAAAA== ">

Member e vphcqwbqQ+PZQDpLQBGX3jZcGfjYvtzMQYWIbLH1TAZOFGBRXF7kmFk/8jsNm1gpCeGQoYE6xi7T OpQ1OQwz3xGLt/e9wyiyr7TtcZRw1+rbJHnUDhuWDzV2tKqpPGyOzsDriOPyLn0e1of96vS1fXj7 XKdkzPXVtHwCFWmK52P4wRd0KIRp549sg2oNSJH4O8W7n4va/W1d5Po/e/ENAAD//wMAUEsBAi0A FAAGAAgAAAAhALaDOJL+AAAA4QEAABMAAAAAAAAAAAAAAAAAAAAAAFtDb250ZW50X1R5cGVzXS54 bWxQSwECLQAUAAYACAAAACEAOP0h/9YAAACUAQAACwAAAAAAAAAAAAAAAAAvAQAAX3JlbHMvLnJl bHNQSwECLQAUAAYACAAAACEAo+l1K54CAADVBgAADgAAAAAAAAAAAAAAAAAuAgAAZHJzL2Uyb0Rv Yy54bWxQSwECLQAUAAYACAAAACEA3C5DE9gAAAADAQAADwAAAAAAAAAAAAAAAAD4BAAAZHJzL2Rv d25yZXYueG1sUEsFBgAAAAAEAAQA8wAAAP0FAAAAAA== ">

УНИЧТОЖЕНИЕ СПИСКА

while Member <> Nil do begin

Element:= Member^.Next;

Dispose(Member);

Member:= Element end;

Перед удалением необходимо запомнить ссылку на следующий элемент (в буфер Element), т.к. в противном случае вся информация об оставшемся куске списка будет утеряна. Следует использовать цикл while…do, т.к. заранее не известно число повторений, и кроме того список может быть пустым.

ДОБАВЛЕНИЕ НОВОГО ЭЛЕМЕНТА В СПИСОК

после элемента Element, предварительно найденного по некоторому признаку:

NewElement^.Next:= Element^.Next;

NewElement^.Name:= '...';

NewElement^.Phone:=...;

Element^.Next:= NewElement;

Предполагается, что NewElement имеет тип PMemberType, и был заранее создан

процедурой

New

.

Name

Phone

Next

i

Element

NewElement

Next

Phone

Name

Next

Phone

Name

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

Глава 11. ОБЪЕКТЫ

§ Описание классов, создание объектов

§ Ограничение доступа к полям и методам

§ Создание библиотек классов

§ Реализация принципа наследования

§ Полиморфизм

§ Раннее связывание

§ Позднее связывание, виртуальные методы

 

Билет 43. Объекты. Создание объекта.

 

ОПИСАНИЕ КЛАССА

Класс – это структурный тип данных, который включает описание полей данных, а также процедур и функций (методы), работающих с этими полями.

Type

PMouse = ^TMouse;

TMouse = object { class }

Visible: Boolean; {признак включен/выключен} Keys: Byte; { количество кнопок } сonstructor Init; {конструктор} destructor Done; {деструктор} procedure On; {включить указатель мыши} procedure Off; {выключить указатель мыши}

end;;

Метод Init создает и инициализирует объект – конструктор (описание начинается со слова constructor). Любой класс должен иметь как минимум один конструктор (если у класса есть виртуальные методы).

Обратным конструктору является метод уничтожения объекта Done – деструктор (описывается словом destructor). Класс не может иметь более одного деструктора.

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

СОЗДАНИЕ ОБЪЕКТА

Объект – это экземпляр класса (переменная типа object или class). Подобно записи, объект используется с префиксной частью в виде имени этого объекта.

Статический объект:

Var

Mouse: TMouse;

Begin

Mouse.Init;	{ инициализация объекта }
Mouse.On;	{ включить указатель мыши }

End.

Динамический объект: Var

Mouse: PMouse; {тип – указатель на TMouse}

Begin

New(Mouse,Init); { инициализация объекта } Mouse^.On; { включить указатель мыши }

...

Dispose(Mouse,Done); {уничтожить объект} End.

ОГРАНИЧЕНИЕ ДОСТУПА К ПОЛЯМ И МЕТОДАМ

if Mouse^.Keys > 0 then begin Mouse^.On;

...

Mouse^.Off; end;

Фрагмент ошибочен с точки зрения объектного подхода, поскольку нарушен принцип инкапсуляции. Получать информацию об объекте следует только при помощи операции селектора, т.е. специальным методом.

Билет 44. Объекты. Ограничение доступа к полям и методам.

 

 

ОГРАНИЧЕНИЕ ДОСТУПА К ПОЛЯМ И МЕТОДАМ

Type

PMouse = ^TMouse;

TMouse = object constructor Init; destructor Done; procedure On; procedure Off;

function GetKeys: Byte; {число кнопок у мыши} function IsVisible: Boolean; {видна мышь или нет}

Private

Visible: Boolean;

Keys: Byte; end;

Введены два метода-селектора GetKeys, IsVisible для определения состояния объекта.

Сами поля Visible и Keys убраны в специальную частную секцию private. Эта секция делает недоступными для непосредственного использования в программе поля и методы, расположенные в ней.

БИБЛИОТЕКИ КЛАССОВ

При создании библиотек классов они описываются в отдельных модулях, которые могут подключаться к основной программе для использования этих классов. Для соблюдения принципа инкапсуляции, класс описывают в разделе Interface, а его методы – в разделе Implementation, что позволяет "скрыть" внутреннее содержание методов.

Unit UMouse;

Interface {секция интерфейса}

Type

PMouse = ^TMouse;

TMouse = object constructor Init; destructor Done; procedure On; procedure Off; function GetKeys: Byte; function IsVisible: Boolean;

Private

Visible: Boolean;

Keys: Byte; end;

БИБЛИОТЕКИ КЛАССОВ

Implementation {секция реализации} constructor TMouse.Init; begin

... end;...