DINAMICO (Методичка С++)
Описание файла
Файл "DINAMICO" внутри архива находится в папке "METODY". Документ из архива "Методичка С++", который расположен в категории "". Всё это находится в предмете "информатика" из 2 семестр, которые можно найти в файловом архиве МГТУ им. Н.Э.Баумана. Не смотря на прямую связь этого архива с МГТУ им. Н.Э.Баумана, его также можно найти и в других разделах. Архив можно найти в разделе "книги и методические указания", в предмете "информатика" в общих файлах.
Онлайн просмотр документа "DINAMICO"
Текст из документа "DINAMICO"
15
Иванова Г.С., Ничушкина Т.Н.
Конспект лекций
по курсу "Алгоритмические языки и программирование".
Тема "Программирование с использованием динамической памяти".
До сих пор мы имели дело с переменными, которые размещаются в памяти согласно вполне определенным правилам, а именно, для локальных переменных, описанных в подпрограмме, память отводится при вызове подпрограммы; при выходе из нее эта память освобождается, а сами переменные прекращают свое существование. Глобальным переменным программы память отводится в начале ее выполнения; эти переменные существуют в течение всего периода работы программы. Иными словами, распределение памяти во всех случаях производится полностью автоматически и подчинено стековой дисциплине. Переменные, память под которые выделяется описанным образом, называются статическими .
Под эту категорию подпадают все переменные и константы, объявленные в Паскале и обозначенные идентификаторами. Это определяется статической структурой Паскаль - программы, обуславливающей расположение ее объектов в непрерывной области памяти длиной не более 64к, называемой сегментом данных, к которому примыкает стек размером 16к.
Однако, помимо привычной схемы, Паскаль дает возможность образовывать новые переменные в любой момент работы программы без учета ее статической структуры, сообразуясь с потребностями решаемой задачи. Точно также допускается уничтожение созданных переменных в произвольный момент выполнения. Переменные, созданием и уничтожением которых может явно управлять программист, называются динамическими. Память для таких переменных берется из свободной, называемой «кучей», размер которой составляет ~ 200 ~300к. Эта цифра получится, если из общей памяти вычесть размер, занятый системными компонентами и самой программой на Паскале.
Для более полного понимания механизма работы с динамическими переменными следует знать некоторые обстоятельства системного характера.
1.1 Адресация оперативной памяти. Указатели.
Наименьшей адресуемой единицей памяти ПЭВМ является байт. Для обращения к конкретному байту необходимо иметь адрес .
Здесь адрес конкретного байта определяется как А=Аб+смещение, где Аб - адрес сегмента. Физический адрес при этом определяется Аф=Аб*16+смещение.
Для формирования адреса в МП 80386 и выше используются 32 разряда, что составляет 2 слова типа word. Первое слово содержит адрес сегмента, второе - адрес смещения внутри сегмента.
Сегмент - это непрерывный участок памяти, имеющий длину 64к и начинающийся с адреса, кратного 16 ( 0,16,32,.....).
Смещение - это количество байт, которое нужно отступить от начала сегмента, чтобы определить конкретный адрес.
Параграф - фрагмент памяти длиной 16 байт.
Сегмент адресует память до параграфа, а смещение - до байта. Каждому сегменту соответствует отдельно адресуемая непрерывная область памяти. Сегменты могут следовать один за другим без промежутка, с некоторым интервалом или перекрывать друг друга.
В Паскале адрес байта памяти, состоящий из 2 - х слов типа word носит название указатель. Синтаксис определения указателя прост и описывается следующей диаграммой:
style="position: absolute; top: 0.44in; left: 1.7in" Реально значения указателей содержат адреса расположения в памяти конкретных значений базового типа.
Примеры объявления указателей представлены ниже:
VAR p1:^integer; {типизированный указатель или указатель целого типа}
p2:^real; {типизированный указатель или указатель вещественного типа}
p3:^char; {типизированный указатель или указатель символьного типа}
p: pointer; {нетипизированный указатель или указатель неопределенного типа}
Кроме объявления указателей - переменных , можно вводить так называемые ссылочные типы, то есть объявление типа указатель в разделе описания типов:
TYPE point1=^integer;{новый ссылочный тип - указатель на целое}
point2=^char; {новый ссылочный тип - указатель на символ}
VAR p1:point1; {переменная ссылочного типа point1}
p2:point2; { переменная ссылочного типа point2}
style="position: absolute; top: 0.14in; left: 1.98in" Указатели - единственное исключение из общего правила, согласно которому идентификаторы всех переменных и производных типов должны быть описаны перед использованием. В данном случае допускается описание вида:
TYPE ppointer = ^percon; {тип person еще не определен}
percon = record { определение типа person}
name: string: next: ppointer;
end;
Для указателей, которые «никуда не указывают», введено понятие «нулевой адрес», имеющий обозначение nil. Указатель nil считается константой, совместимой с любым типом указателя и его можно присваивать любому указателю.
Над значениями указателей возможны следующие операции:
1.Присваивание. Указателю присваивается значение другого указателя. Допускается присваивать указателю только значение того же или неопределенного типа. Например:
VAR p1,p2:^integer;
p3:^real;
p: pointer;
.Допустимые операции Недопустимые операции
p1:=p2; p:=p3; p1:=p3;
p1:=p; p1:=p; p3:=p2;
2. Доступ к переменной по указателю (операция разыменования). Чтобы получить доступ к переменной по указателю, необходимо после переменной - указателя поставить знак «^». При этом значение имеет тип, совпадающий с базовым типом указателя. Например:
p1^ - означает « переменная, на которую указывает p1». Так как p1 указатель на целое, то p1^ - -это значение целой, расположенной по адресу p1.Если написать
p1^:=2; то содержимое ячейки памяти, адресуемой указателем станет равным 2.
Чтобы изменить содержимое ячейки, необходимо выполнить следующую операцию:
p1^:=p^+2;
При этом содержимое ячейки изменится и станет равным 4.
3. Взятие указателя. Это унарная операция, которая строится из знака операции - символа @ (амперсанд) и одного операнда - переменной любого типа. Например, если имеется описание:
TYPE p =^integer;
VAR p1:p;
i: integer;
.....то последовательность операций
p1:=@i;
p1^:=2;
приведет к присвоению переменной i значения 2.
4. Отношения. Это бинарные операции сравнения указателей на равенство и неравенство. Операции проверяют, ссылаются ли два указателя на одну и ту же область памяти, и обозначаются обычным образом - знаком «= » и «<> ». Например:
sign:=p1=p2 { sign приобретает значение true или false в зависимости от значений указателей}
if p1<> nil then ...
Так как тип указателя может быть образован от любых типов, допустимо определение «указатель на указатель».
Если описать переменную pp1, используя предыдущий пример, следующим образом:
VAR pp1:^p1;
то в качестве своих возможных значений она получит множество указателей, ссылающихся на целые значения. Применив операцию
pp1:=@p1; мы получим связи, изображенные на схеме.
Для получения значения ячейки i, необходимо дважды применить операцию разыменывания. В нашем случае pp1^^ - имеет тип integer и равно 2.
-
Процедуры и функции, работающие с указателями.
Для работы с указателями в Паскале предусмотрены стандартные функции, облегчающие и упрощающие эту работу. Перечень функций представлен в таблице 1
Таблица 1.
№ | Вызов функции | Тип функции | Результат |
1. | ADDR(x} | pointer | Возвращает адрес аргумента. (имя пер., функции, процедуры). Аналогична операции - @. |
2. | SEG(x] | word | Возвращает адрес сегмента указанного объекта. |
3. | OFS(x) | word | Возвращает смещение адреса указанного объекта. |
4. | CSEG | word | Возвращает текущее значение регистра адреса программного сегмента - CS. |
5. | DSEG | word | Возвращает текущее значение регистра адреса сегмента данных - DS. |
6. | PTR(seg,ofs) | pointer | Возвращает значение указателя по заданным seg и ofs. |
7. | SIZEOF(x) | word | Возвращает длину указанного объекта в байтах. |
-
Управление динамической памятью.
Определяемые в примерах предыдущих разделов указатели, для простоты объяснения, содержали адреса некоторых статических объектов. Однако, основное назначение указателей - это адресация динамических объектов. Для динамических объектов программист заказывает память требуемого размера из динамической памяти. Вся динамическая память в Паскале рассматривается как подобная стеку структура, называемая «кучей». Физически «куча» располагается в старших адресах, сразу за областью, занимаемой программой. Схема распределения оперативной памяти представлена на рис.1.
style="position: absolute; top: 0.1in; left: 2.02in" Рис. 1.
На рисунке HeapOrg - указатель на начало динамической области
HeapEnd - указатель на конец динамической области
HeapPtr - указатель на текущее значение границы свободной динамической области
Заказать память требуемого объема из динамической области в Паскале можно несколькими способами.
1. Наиболее распространенный способ - использование процедуры или функции new. Вызов осуществляется следующим образом:
процедуры - NEW (<имя переменной ссылочного типа >);
<имя переменной ссылочного типа>:=NEW(<ссылочный тип >);
Примеры использования:
TYPE p = ^integer;
pa = ^real;
VAR pp : p;
ppa :pa;
.......................
new(pp); {динамическая область вся доступна pp = HeapOrg, HeapPtr=HeapOrg+2}
pp^ := 5; {по адресу заносим число 5 }
ppa: = new(pa); {в памяти уже есть число 5 типа integer, поэтому ppa=HeapOrg+2
HeapPtr=HeapPtr+6, так как тип указателя pa - real длиной 6 байт}
ppa^ :=35.5;
Память, выделенная под динамические переменные после использования должна быть освобождена. Для этой цели используется процедура освобождения памяти DISPOSE.
Процедура DISPOSE(<имя переменной ссылочного типа >)
Для переменных из предыдущего примера процедура вызывается так:
dispose(pp);
dispose(ppa);
При попытке применить процедуру к указателю, имеющему значение nil, возникает аварийная ситуация с выдачей сообщение об ошибке.
Чередование обращений NEW и DISPOSE может привести к фрагментации памяти. Для уменьшения этого явления можно использовать процедуры MARK и RELEASE.
MARK - запоминает значение в переменной указателе, определенном в качестве параметра.
RELEASE - освобождает весь фрагмент, начиная с адреса, зафиксированного в переменной указателе из процедуры MARK.
New(p1);
new(p2);
mark(p);
new(p3);
new(p4);
release(p);
Следует заметить, что совместное использование процедур Dispose и Release недопустимо.
-
Динамическую память можно выделять фрагментом указанного размера. Для этой цели в Паскале используется процедура GetMem (p,size).
Эта процедура запрашивает у системы память требуемого размера. Указанного в параметре size (запрашиваемый объем не должен превышать 64к) и помещает адрес выделенного системой фрагмента в переменную типа указатель с имеем p. После использования память обязательно нужно освободить процедурой FreeMem (p,size), которая по адресу указателя p освобождает фрагмент размером size.