Использование динамического выделения памяти при программировании на языке Turbo Pascal 7.0

23

Размещено на http://www.allbest.ru/

Использование динамического выделения памяти при программировании на языке Turbo Pascal 7.0

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

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

Длина сегмента определяется архитектурой процессора 8086 и составляет 64 Килобайта (65536 байт), что может вызвать определённые трудности при описании и обработке больших массивов данных.

С другой стороны объём стандартной памяти - 640 Килобайт. Выход - использовать динамическую память. Динамическая память - это оперативная память ЭВМ, предоставляемая Турбо-Паскалевой программе при её работе, за вычетом сегмента данных (64 К), стека (обычно 16 К) и собственно тела программы. По умолчанию размер динамической памяти определяется всей доступной памятью ЭВМ и, как правило, составляет не менее 200 - 300 Кбайт.

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

1. обработке больших массивов данных;

2. разработке САПР;

3. временном запоминании данных при работе с графическими и звуковыми средствами ЭВМ.

Размещение статических переменных в памяти осуществляется компилятором в процессе компиляции.

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

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

Турбо-Паскаль представляет средство управления динамической памятью: указатели. Указатель - это переменная, которая в хранит качестве своего значения адрес байта памяти.

В 8086 адреса задаются совокупностью двух шестнадцатиразрядных слов - сегмента и смещения.

Сегмент - участок памяти, имеющий максимальную длину 64 К и начинающийся к физического адреса, кратного 16 (то есть 0, 16, 32, 48 и т.д.).

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

Фрагмент памяти в 16 байт называется параграфом.

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

Таким образом любой указатель по своей внутренней структуре представляет собой совокупность двух слов (типа Word), трактуемых как сегмент и смещение. Указатель адресует лишь первый байт типа данных.

Справка: процессор 8086. 8086 имеет 16 - битовые регистры, всего 14 штук, из них:

· 12 - регистры данных и адресов;

· 1 - указатель команд (регистр адреса команды);

· 1 - регистр состояния (регистр флагов).

Регистры данных и адресов делятся на три группы:

· регистр данных;

· регистр указателей и индексов;

· регистр сегментов.

Процессор 8086 всегда генерирует 20-ти бытовые адреса за счёт добавления 16-ти битового смещения к содержимому регистра, умноженному на 16: физический адрес = смещение + 16 * регистр сегмента.

Вместо умножения на 16 содержимое регистра сегмента используется так, как если бы оно имело четыре дополнительных нулевых бита:

пусть:

смещение = 10H

регистр сегмента = 2000H

тогда:

0000 0000 0001 0000 (смещение)

0010 0000 0000 0000 (0000) (номер блока)

0010 0000 0000 0001 0000 (физический адрес)

физический адрес = 20010H

У 8086 адрес ячейки задаётся номером блока и смещением, что обусловлено тем, что команды 8086 и её данные должны располагаться в разных частях памяти (в разных сегментах). Если требуется адресоваться к данным, то потребуется адресация блока памяти, с которого начинается сегмент данных (из регистра сегмента данных) и позиция желаемой ячейки в этом сегменте (смещение). В дополнение к области памяти 1 Мбайт, 8086 может адресоваться к внешним устройствам через 65536 (64 К) портов ввода-вывода. Имеются специальные команды ввода-вывода, позволяющие иметь непосредственный доступ к первым 256 (от 0 до 255) портам. Другие команды позволяют получить косвенный доступ к порту с помощью занесения идентифицирующего его номера (0 - 65535) в определенный регистр данных. Подобно ячейке памяти любой порт может быть 8 или 16- битовым. Распределение памяти IBM PC.

· 16 - старших байт - команды начальной загрузки системы.

· Первые 1024 ячейки - вектора прерываний.

Типы прерываний.

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

8086 может распознать 256 различных прерываний, каждому из них однозначно соответствует код типа (целое число от 0 до 255). Код используется в качестве указателя ячейки в области памяти с младшими адресами (область векторов прерываний).

2. Указатели

Операционная система 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 - имя переменной любого типа, в том числе процедурного.

Переменные типа указатель не могут быть элементами списка ввода - вывода.

3. Динамические переменные

Статической переменной (статически размещенной) называется описанная явным образом в программе переменная, обращение к ней осуществляется по имени.

Место в памяти для размещения статических переменных определяется при компиляции программы.

В отличие от таких статических переменных в программах, написанных на языке ПАСКАЛЬ, могут быть созданы динамические переменные.

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

Размещаются динамические переменные в динамической области памяти (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:

Аналогично, процедура New(p2) обеспечит выделение участка памяти, адрес которого будет записан в p2:

После выполнения операторов присваивания

p1^:=2; p2^:=4;

в выделенные участки памяти будут записаны значения 2 и 4 соответственно:

В результате выполнения оператора присваивания

p1^:=p2^;

в участок памяти, на который ссылается указатель p1, будет записано значение 4:

После выполнения оператора присваивания p2:=p1;

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



Переменные 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

Выделение и освобождение динамической памяти.

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

Физически куча располагается в старших адресах, сразу за программой.

Указатель на начало кучи храниться в предопределенной переменной HeapOrg, конец - FreePtr, текущую границу незанятой динамической памяти указывает указатель HeapPtr. Для выделения памяти под любую переменную используется процедура New. Единственным параметром является типизированный указатель:

Var

I,J: ^Integer;

R: ^Real;

Begin

New(I); {под I выделяется область памяти,}

{адрес первого байта этой области помещается в I}

End.

После выполнения этого фрагмента указатель I приобретёт значение, которое перед этим имел указатель кучи HeapPtr, а HeapPtr увеличится на два (т.к. он типа Integer); New(R) - вызовет смещение указателя на 6 байт.

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

I^:= 2; R^:= 2*Pi;

Допустима запись: R^:= Sqr (R^) + I^ - 17; Но недопустима запись: R:= Sqr (R^) + I^ - 17; так как указателю R нельзя присвоить значение вещественного выражения.

Возврат динамической памяти обратно в кучу осуществляется оператором Dispose: Dispose(R); Dispose(I); - вернут в кучу, ранее забранные 8 байт. Dispose(Ptr) не изменяет значения указателя Ptr, а лишь возвращает в кучу память, связанную с этим указателем. Однако повторное применение процедуры к “свободному” указателю приведет к возникновению ошибки времени исполнения.

Чтобы указать, что указатель свободен, нужно использовать зарезервированное слово Nil. К указателям можно применять операции отношения, в том числе и сравнения с Nil:

Const

P:^Real = Nil;

. . . . . . . .

Begin

If P = Nil then

New (P);

. . . . . . . .

Dispose(P);

P:= Nil;

End.

Использование указателей, которым не присвоено значение процедурой New или каким-либо другим способом, никак не контролируется системой и может привести к непредсказуемым результатам.

Многократное чередование New и Dispose приводит к “ячеистой” структуре кучи. Дело в том, что все операции с кучей выполняется под управлением особой программы, которая ведёт учёт всех свободных фрагментов в куче.

При выполнении оператора New( ) эта программа отыскивает минимальный свободный фрагмент, в котором может разместиться требуемая переменная.

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

Можно освободить целый фрагмент кучи следующим образом:

1. Перед началом выделения динамической памяти значения указателя HeapPtr запоминается в переменной-указателе с помощью процедуры Mark.

2. Выполнение программы.

3. Освобождение фрагмента кучи от заполненного адреса до конца динамической памяти с использованием процедуры Release.

4. Var

5. P, P1, P2, P3, P4, P5: ^Integer;

6. Begin

7. New(P1);

8. New(P2);

9. New(P3);

10. New(P4);

11. New(P5);

12. Mark(P);

13. . . . . . . .

14. Release (P);

15. End.

В этом примере процедурой Mark(P) в указатель P было помещено текущее значение HeapPtr, однако память под переменную не резервировалась. Вызов Release уничтожает список свободных фрагментов в куче, созданных Dispose, поэтому совместное применение этих процедур не рекомендуется.

Для работы с нетипизированными указателями используются также процедуры GetMem(P, Size) и FreeMem(P, Size) - резервирование и освобождение памяти. P - нетипизированный указатель, Size - размер.

За одно обращение к куче процедурой GetMem можно зарезервировать до 65521 байт. Освобождать нужно ровно столько памяти, сколько было зарезервировано, и именно с того адреса, с которого память была зарезервирована, иначе программа не будет работать и завершаться корректно !!!

Примеры использования указателей.

Динамическая память - 200..300 Кбайт. Нужно разместить массив 100 * 200 типа Extended. Требуется 100 * 200 * 10 = 200000 байт. Пробуем:

Var

i,j: Integer;

PtrArr: Array[1..100, 1..200] of ^Extended.

Begin

. . . . . .

For i:= 1 to 100 do

For j:= 1 to 200 do

New (PtrArr [i,j]);

. . . . . .

End.

Теперь к любому элементу можно обратиться: PtrArr[i,j]^:=...; Но длина внутреннего представления указателей 4 байта, поэтому потребуется ещё 100*200*4 = 80000 байт, что превышает размер сегмента (65536 байт), доступный для статического размещения данных. Можно было бы работать с адресной арифметикой (арифметикой над указателями), то есть не создавать массив указателей, а вычислять адрес элемента непосредственно перед обращением к нему.

Однако в Турбо-Паскале над указателями не определены никакие операции, кроме присваивания и отношения.

Но задачу решить можно: Seg(x) - возвращает сегментную часть адреса. Ofs(x) - возвращает смещение. x - любая переменная, в том числе и та, на которую указывает указатель. Далее с помощью Ptr(Seg, Ofs: Word): Pointer можно создать значение указателя, совместимое с указателем любого типа.

Таким образом, сначала с помощью GetMem забираем из кучи несколько фрагментов подходящей длины (не более 65521). Удобно по строкам 200 * 100 = 20000 байт.

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

Var

i,j: Integer;

PtrStr: Array [1..100] of Pointer;

Pr: ^Extended;

Const

SizeOfExt = 10;

Begin

For i:= 1 to 100 do

GetMem (PtrStr[i], SizeOfExt*200);

. . . . . . . . . . . . . . . .

Pr:= Ptr(Seg(PtrStr[i]^), Ofs(PtrStr[i]^) + (j - 1) * SizeOfExt); {Обращение к элементу матрицы [i,j]}

End;

далее работаем с Pr^:=. . . и т.д.

Полезно ввести две вспомогательных функции GetExt и PutExt. Каждая из них будет обращаться к функции вычисления адреса AddrE.

Program Demo;

Const

SizeOfExt = 10;

N = 100;

M = 200;

Type

ExtPoint = ^Extended;

Var

i,j: Integer;

PtrStr: Array[1..N] of Pointer;

S: Extended;

Function AddrE(i,j: Word): ExtPoint;

Begin

AddrE:= Ptr(Seg(PtrStr[i]^), Ofs(PtrStr[i]^) + (j - 1) * SizeOfExt);

End;

Function GetExt(i,j: Integer): Extended;

Begin

GetExt:= AddrE(i,j)^;

End;

Procedure PutExt(i,j: Integer; X: Extended);

Begin

AddrE(i,j)^:= X;

End;

Begin {main}

Randomize;

For i:=1 to N do

Begin

GetMem (PtrStr[i], M*SizeOfExt);

For i:= 1 to m do

PutExt(i, j, Random(255));

End;

S:= 0;

For i:= 1 to N do

For j:= 1 to M do

S:= S + GetExt(i,j);

WriteLn(S/(N*M));

End.

Мы предполагали, что каждая строка размещается в куче с начала границы параграфа и смещение каждого указателя PtrStr ровно 0. В действительности при последовательных обращениях к GetMem начало очередного фрагмента следует за концом предыдущего и может не попасть на границу сегмента. В результате при размещении фрагментов максимальной длины (65521 байт) может возникнуть переполнение при вычислении смещения последнего байта.

4. Динамические структуры данных

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

Часто требуется, чтобы структуры данных меняли свои размеры в ходе решения задачи. Такие структуры данных называются динамическими, к ним относятся стеки, очереди, списки, деревья и другие. Описание динамических структур с помощью массивов, записей и файлов приводит к неэкономному использованию памяти ЭВМ и увеличивает время решения задач.

Каждая компонента любой динамической структуры представляет собой запись, содержащую по крайней мере два поля: одно поле типа указатель, а второе - для размещения данных.

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

Для дальнейшего рассмотрения представим отдельную компоненту в виде:

где поле p - указатель; поле D - данные.

Описание этой компоненты дадим следующим образом:

type

Pointer = ^Comp;

Comp = record

D:T;

pNext:Pointer

end;

здесь T - тип данных. Рассмотрим основные правила работы с динамическими структурами данных типа стек, очередь и список, базируясь на приведенное описание компоненты.

5. Стеки

стек программа ссылка динамический

Стеком называется динамическая структура данных, добавление компоненты в которую и исключение компоненты из которой производится из одного конца, называемого вершиной стека.

Стек работает по принципу LIFO (Last-In, First-Out) - поступивший последним, обслуживается первым.

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

1. начальное формирование стека (запись первой компоненты);

2. добавление компоненты в стек;

3. выборка компоненты (удаление).

Для формирования стека и работы с ним необходимо иметь две переменные типа указатель, первая из которых определяет вершину стека, а вторая - вспомогательная.

Пусть описание этих переменных имеет вид:

var pTop, pAux: Pointer;

где pTop - указатель вершины стека;

pAux - вспомогательный указатель.

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

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

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

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

Рассмотрим процесс выборки компонент из стека. Пусть к моменту начала выборки стек содержит три компоненты:

Первый оператор или группа операторов осуществляет чтение данных из компоненты - вершины стека. Второй оператор изменяет значение указателя вершины стека:

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

Пример. Составить программу, которая формирует стек, добавляет в него произвольное количество компонент, а затем читает все компоненты и выводит их на экран дисплея, В качестве данных взять строку символов. Ввод данных - с клавиатуры дисплея, признак конца ввода - строка символов END.

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';

writeln('****** ВЫВОД РЕЗУЛЬТАТОВ ******');

repeat

DelComp(pTop,sC);

writeln(sC);

until pTop = NIL

end.

Размещено на Allbest.ru