Глава 10. УКАЗАТЕЛИ И ДИНАМИЧЕСКАЯ ПАМЯТЬ Распределение памяти для выполняемого кода программы Динамическая память Указатели Типизированные и нетипизированные указатели Процедуры работы с указателями Использование динамической памяти для размещения данных большого объема Организация динамических структур.

2 Гл. 10. УКАЗАТЕЛИ И ДИНАМИЧЕСКАЯ ПАМЯТЬ Выделение памяти для кода программы Адресное пространство памяти компью- тера, к которому имеет доступ програм- ма, созданная с помощью Тurbo Рascal, не превышает 640 К ( байт) – нижняя память MS-DOS. Оверлеи – это такой способ исполь- зования оперативной памяти, при котором в один и тот же участок памяти, называемый оверлейным буфером, по- переменно, по мере надобности, загру- жаются различные оверлейные (пере- крывающиеся) модули. При этом все оверлейные модули в готовом виде хра- нятся на диске, а в оперативной памяти находится лишь один активный, и, воз- можно, небольшое число неактивных. Оставшаяся область памяти (как пра- вило, не менее Кбайт) называ- ется динамической памятью (heap- областью, или кучей). Префикс сегмента программы (256 байт) Код основного блока ( 64 K) Код последнего модуля ( 64 K)... Код первого модуля ( 64 K) Сегмент данных ( 64 K) Заполненная часть стека Свободная часть стека Стек (64 К) Оверлейный буфер Динамическая память (куча)

3 Гл. 10. УКАЗАТЕЛИ И ДИНАМИЧЕСКАЯ ПАМЯТЬ В Тurbo Рascal есть средства, которые позволяют использовать динамическую память под размещение данных большой размерности, превышающих 64 К и не вмещающихся в сегмент данных, а также при организации динамических структур и для других целей. При этом происходит динамическое размещение данных, что означает использование области динамической памяти непосредственно во время работы (при динамическом размещении заранее не известен ни тип, ни количество размещаемых данных). Средство управления динамической памятью – указатели. Указатели Указатель – это переменная, которая в качестве своего значения содержит адрес байта памяти (совокупность двух слов типа Word, трактуемых как сегмент и смещение). Размер указателя равен 4 байтам. Типизированный указатель (ссылка) связывается с некоторым типом данных. Для объявления типизированного указателя используется значок ^, который помещается перед соответствующим типом: VarPInt : ^Integer;PReal : ^Real; Нетипизированные указатели (указатели) хранят просто адреса, которые не связаны с данными конкретных типов: VarP : Pointer;

4 Гл. 10. УКАЗАТЕЛИ И ДИНАМИЧЕСКАЯ ПАМЯТЬ Динамическое распределение памяти происходит следующим образом: прикладная программа запрашивает у системы фрагмент памяти определенного размера; если в вычислительной машине есть свободная память требуемого объема, то система выделяет этот фрагмент; система передает прикладной программе указатель на эту непрерывную область в памяти; прикладная программа получает указатель; прикладная программа размещает данные в выделенной области, начиная с указанного адреса; по окончании работы с этими данными прикладная программа обязана сообщить системе о том, что выделенная область памяти может быть снова получена системой, иначе говоря, освободить выделенный фрагмент. свободная память Динамическая память HeapOrg HeapPtr HeapEnd Начало кучи хранится в стандартной переменной HeapOrg, а конец – в переменной HeapEnd (указатели). На текущую границу незанятой динамической памяти указывает переменная HeapPtr.

5 Гл. 10. УКАЗАТЕЛИ И ДИНАМИЧЕСКАЯ ПАМЯТЬ Память под динамически размещаемую переменную во время работы программы выделяется процедурой (функцией) NEW. Процедура New(Var ); возвращает адрес выделенного участка памяти через параметр-переменную. Размер участка памяти определяется базовым типом указателя. Var PInt : ^Integer; PReal : ^Real; Begin New(PInt); {PInt = HeapPtr} New(PReal); {PReal = HeapPtr} PInt^ := 2; PReal^ := 2*pi; PReal^ := Sqr(PReal^) + PInt^ - 1; End. После того, как указатель приобрел некоторое значение - адрес памяти, по этому адресу можно разместить любое значение соответствующего типа. Для доступа к данным, которые хранятся по этому адресу, необходимо за именем указателя поставить значок ^.

6 Гл. 10. УКАЗАТЕЛИ И ДИНАМИЧЕСКАЯ ПАМЯТЬ 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; End. Передавать значения между указателями можно в том случае, если они связаны с одним и тем же типом данных (либо один из них - нетипизированный указатель или "нулевой адрес" Nil ) При выполнении операции присваивания теряется участок памяти, на который ссылался указатель стоящий слева от оператора присваивания. Это типичный случай создания "мусора" (garbage) в динамической памяти.

7 Гл. 10. УКАЗАТЕЛИ И ДИНАМИЧЕСКАЯ ПАМЯТЬ Процедура Dispose( ); освобождает память по адресу, хранящемуся в указателе. При этом не изменяется значение указателя HeapPtr – текущей границы незанятой динамической памяти. Поэтому чередование обращений к процедурам New и Dispose обычно приводит к фрагментации памяти – память разбивается на небольшие фрагменты с чередованием свободных и занятых участков. При работе с нетипизированными указателями, в основном, используются другие процедуры: GetMem(Var P : Pointer, Size : Word) {резервирование памяти} FreeMem(P : Pointer, Size : Word) {освобождение памяти} где Р – нетипизированный указатель, Size – размер в байтах требуемой или освобождаемой части кучи. Использование процедур GetMem/FreeMem (как и вообще вся работа с динамической памятью) требует особой осторожности и соблюдения правила: освобождать нужно ровно столько памяти, сколько ее было зарезервировано, и именно с того адреса, с которого она была зарезервирована.

8 Гл. 10. УКАЗАТЕЛИ И ДИНАМИЧЕСКАЯ ПАМЯТЬ Использование динамической памяти для размещения данных большого объема Type Dim100x200 = array [1..100,1..200] of Real; Статически переменная такого типа не может быть объявлена. Для размещения в динамической памяти нужно организовать так, чтобы массив "распался" на части, не превышающие 64 К. Type Dim100 = array [1..100] of Real; {строка-массив размером 600 байт} 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 = , J = } End.

9 Гл. 10. УКАЗАТЕЛИ И ДИНАМИЧЕСКАЯ ПАМЯТЬ Динамические структуры Список – упорядоченный набор элементов одного типа. Размер списка может изменяться. Элемент списка (любой динамической структуры) состо- ит из двух частей: информационной, содержащей данные, и адресной, где хранятся указатели на следующие элементы. Очередь – упорядоченный список, в один конец которого элементы добавляются, а из другого изымаются. Очередь – это устройство FIFO (First In, First Out). Стек – упорядоченный список, в один конец которого элементы добавляются, и из него же изымаются. Стек – это устройство LIFO (Last In, First Out). Х1Х1 Х2Х2 Х3Х3...ХNХN ДобавитьУдалить ? Поиск Х N-1 Удалить Х1Х1 Х2Х2...ХNХN Добавить Удалить Х1Х1 Х2Х2...ХNХN Добавить ? Пусто

10 Гл. 10. УКАЗАТЕЛИ И ДИНАМИЧЕСКАЯ ПАМЯТЬ Граф – структура, состоящая из узлов и дуг, каждая дуга направлена от одного узла к другому. ? Поиск Удалить узел Удалить дугу Добавить узел Дерево – направленный граф, у которого имеется корневой узел, не имеющий дуг, входящих в него; в каждый узел входит не более одной дуги; в каждый узел можно попасть из корневого за несколько шагов. Корневой узел

11 Гл. 10. УКАЗАТЕЛИ И ДИНАМИЧЕСКАЯ ПАМЯТЬ Создание и работа с линейным односвязным списком Type PMemberType = ^MemberType; MemberType = record Name : String; Phone : Word; Next : PMemberType end; Var First, Member : PMemberType; Указатель на тип MemberType описан до того, как описан сам тип MemberType. В Тurbo Рascal такое предварительное использование идентификатора типа разрешено только при создании указателя на этот тип. В запись MemberType включено поле Next, которое представляет собой указатель на запись MemberType. Это есть ссылка на соседний элемент списка.

12 Гл. 10. УКАЗАТЕЛИ И ДИНАМИЧЕСКАЯ ПАМЯТЬ Begin Member := Nil; {неопределенный указатель – показывает, что память для Member не выделена} for I := 1 to 4 do begin New(First); First^.Next := Member; First^.Name := '...'; First^.Phone :=...; Member := First; end; End. Создание списка: Name 4 Phone 4 Next 4 (Адрес 3) Name 3 Phone 3 Next 3 (Адрес 2) Name 2 Phone 2 Next 2 (Адрес 1) Name 1 Phone 1 Next 1 (Nil) Member

13 Гл. 10. УКАЗАТЕЛИ И ДИНАМИЧЕСКАЯ ПАМЯТЬ while Member Nil do begin Element := Member^.Next; Dispose(Member); Member := Element end; Уничтожение списка: Перед удалением необходимо запомнить ссылку на следующий элемент (в буфер Element), т.к. в противном случае вся информация об оставшемся куске списка будет утеряна. Следует использовать цикл while…do, т.к. заранее не известно число повторений и кроме того список может быть пустым.

14 Гл. 10. УКАЗАТЕЛИ И ДИНАМИЧЕСКАЯ ПАМЯТЬ NewElement^.Next := Element^.Next; NewElement^.Name := '...'; NewElement^.Phone :=...; Element^.Next := NewElement; Добавление нового элемента после элемента Element, предварительно найденного по некоторому признаку: Предполагается, что NewElement имеет тип PMemberType, и был заранее создан процедурой New. Name Phone NextName Phone Next i Element Name Phone Next NewElement Для удобства поиска нужного элемента це- лесообразно формиро- вать список в отсорти- рованном (по некото- рому полю) виде.