Использование динамически выделяемой памяти

6.1 Адресация оперативной памяти.
Указатели и операции над ними
Минимальная адресуемая единица памяти большинства современных процессоров – байт. Байты памяти нумеруют, начиная с нуля.
Размещаемая в памяти компьютера информация: числовые и текстовые данные, а также машинные коды программы - обычно имеют размер более 1 байта, т.е. занимают в памяти некоторое количество байтов.
0
1
2
3
4
Физический адрес
Аф – номер байта оперативной памяти.
Адрес первого (младшего) байта.
Объем занимаемой памяти, т.е. количество байтов в памяти.

Относительная адресация памяти или адресация по схеме "База + смещение"
Аф = Аб + Асм,
где Аб – адрес базы – адрес, относительно которого считают
остальные адреса;
Асм – смещение – разность физического и базового адресов.
Адресация по схеме "База + смещение" обеспечивает "перемещаемость" программ и данных в памяти, т.е. загрузку в разные места оперативной памяти в зависимости от того, какой участок памяти свобод.
Указатель – тип данных, используемый для хранения смещений.
В памяти занимает 4 байта, адресует сегмент размером V = 232 = 4 Гб.
При сегментной модели памяти базовый адрес = адрес сегмента.
0
1
2
3
4
Aб
Aсм
Аоб
A'б
Aсм
А'об

Типизированные и нетипизированные указатели
Различают указатели:
типизированные – адресующие данные конкретного типа;
нетипизированные – не связанные с данными определенного типа.
Объявление типизированного указателя:
Объявление нетипизированного указателя: pointer
Примеры:
а) Type tpi=^integer;
Var pi:tpi;
или
Var pi: ^integer;
б) Var p:pointer;
в) Type pp = ^percon;
percon = record
name: string:
next: pp;
end;
г) Var r:^integer = nil;

Операции присваивания и получения адреса
1. Присваивание. Допускается присваивать указателю только значение того же или неопределенного типа.
Пример:
Var p1,p2: ^integer;
p3: ^real;
p: pointer;...
{допустимые операции}
p1:=p2; p:=p3; p1:=p; p1:=nil; p:=nil; ...
{недопустимые операции}
p3:=p2; p1:=p3;
2. Получение адреса. Результат операции – указатель типа pointer – может присвоен любому указателю.
Пример:
Var i:integer;
pi: ^integer;
... pi:=@i;
pi
i

Операции доступа и отношения
3. Доступ к данным по указателю (операция разыменования). Полученное значение имеет тип, совпадающий с базовым типом данных указателя.
Нетипизированные указатели разыменовывать нельзя.
Примеры:
j:=pi^;
pi^:= pi^+2;
4. Операции отношения: проверка равенства (=) и
неравенства (< >).
Примеры:
sign := p1 = p2;
if p1<>nil then ...
pi
i

Подпрограммы, работающие с указателями
1. Функция ADDR(x): pointer – возвращает адрес объекта x, в качестве которого может быть указано имя переменной, функции, процедуры.
Пример:
Data:=Addr(NodeNumber); ↔ Data:= @NodeNumber;
2. Функция Assigned(const P): Boolean – проверяет присвоено ли значение указателю (true – если присвоено).
Пример:
if Assigned (P) then Writeln ('You won''t see this');
3. Функция Ptr(Address: Integer): Pointer – преобразует число в указатель.
Пример:
p:=Ptr(a);

6.2 Динамическое распределение памяти
Управление выделением и освобождением памяти осуществляется посредством специальных процедур и функций:
1. Процедура New(var P: ^<тип>) – выделяет память для размещения переменной, размер определяется типом указателя.
2. Процедура Dispose(var P: ^<тип>) – освобождает выделенную память.
Пример:
Var pi:^integer;...
if Assigned(pi) then ... {false}
New(pi);
pi^:=5;
Dispose(pi);
if Assigned(pi) then ... {true}
...
pi
∅
5

Подпрограммы динамического распределения (2)
3. Процедура GetMem(var P: Pointer; Size: Integer) – выделяет указанное количество памяти и помещает ее адрес в указатель.
4. Процедура FreeMem(var P: Pointer[; Size: Integer]) – освобождает выделенную память.
5. Функция SizeOf(X): Integer – возвращает размер переменной в байтах.
Пример:
Var Buffer: ^array[1..100] of byte;
...
GetMem(Buffer,SizeOf(Buffer));
Buffer^[1]:=125;
...
FreeMem(Buffer,sizeof(Buffer));…

Динамическая матрица

Программа
Program Ex6_1;
{$APPTYPE CONSOLE}
Uses SysUtils;
Var i,j,n,m:word; s:single;
ptrstr:array[1..10000] of pointer;
Type tpsingle=^single;
{Функция вычисления адреса}
Function AddrR(i,j:word):tpsingle;
begin
AddrR:=Ptr(Integer(ptrstr[i])+(j-1)*SizeOf(single));
end;

Программа (2)
Begin
Randomize;
WriteLn('Input n,m'); ReadLn(n,m);
for i:=1 to n do begin
GetMem(ptrstr[i],m*sizeof(single));
for j:=1 to m do AddrR(i,j)^:=Random;
end;
s:=0;
for i:=1 to n do
for j:=1 to m do s:=s+AddrR(i,j)^;
WriteLn('Summa =',s:15:10);
WriteLn('Middle value =',s/(n*m):15:10);
for i:=1 to n do FreeMem(ptrstr[i],m*SizeOf(single));
ReadLn;
End.

6.3 Динамические структуры данных
Структуры данных
Последовательные
Древовидные
Сетевые
Вектор
Стек
Дек
Бинарные деревья
Сортированные
Бинарные деревья
Динамические линейные структуры
1. Очередь – структура данных, реализующая: добавление – в конец, а удаление – из начала.
2. Стек – структура данных, реализующая: добав-ление и удаление с одной стороны.
3. Дек – структура данных, реализующая: добав-ление и удаление с двух сторон.
Очередь
Строка
Запись
Матрица

Списки
Список – способ организации данных, предполагающий использова-ние указателей для определения следующего элемента.
Элемент списка состоит из двух частей: информационной и адресной.
Информационная часть содержит поля данных.
Адресная – включает от одного до n указателей, содержащих адреса следующих элементов. Количество связей, между соседними элементами списка определяет его связность: односвязные, двусвязные, n-связные.
Списки
Линейные
Древовидные
N-связные
Кольцевые

Виды списков
Линейный односвязный
Кольцевой односвязный
Линейный двусвязный
Кольцевой двусвязный
Сетевой n-связный

Примеры описания элементов списка
Односвязный список:
Type pe = ^element; {тип указателя}
element = record
name: string[16]; {информационное поле 1}
telefon:string[7]; {информационное поле 2}
p: pe; {адресное поле}
end;
Двусвязный список:
Type pe = ^element; {тип указателя}
element = record
name: string[16]; {информационное поле 1}
telefon:string[7]; {информационное поле 2}
prev: pe; {адресное поле «предыдущий»}
next: pe; {адресное поле «следующий»}
end;

6.4 Односвязные списки
Аналогично одномерным массивам реализуют последовательность элементов. Однако в отличие от одномерных массивов позволяют:
работать с произвольным количеством элементов, добавляя и удаляя их по мере необходимости;
осуществлять вставку и удаление записей, не перемещая остальных элементов последовательности;
но
не допускают прямого обращения к элементу по индексу;
требуют больше памяти для размещения.

Объявление типа элемента и переменных
Описание типа элемента:
Type tpel=^element; {тип «указатель на элемент»} element=record
num:integer; {число}
p:tpel; {указатель на следующий элемент}
end;
Описание переменной – указателя списка и несколько переменных-указателей в статической памяти:
Var first, {адрес первого элемента}
n,f,q:tpel; {вспомогательные указатели}
Исходное состояние – «список пуст»:
first:=nil;
first
∅
n
f
q

Добавление элементов к списку
1 Добавление элемента к пустому списку:
new(first);
first ^.num:=5;
first ^.p:=nil;
2 Добавление элемента перед первым (по типу стека):
new(q);
q^.num:=4;
q^.p:=first;
first:=q;
3 Добавление элемента после первого (по типу очереди):
new(q);
q^.num:=4;
q^.p:=nil;
first^.p:=q;
first
∅
5
∅
first
5
∅
q
4
first
5
∅
q
4
∅

«Стек» записей
Program Ex6_2;
{$APPTYPE CONSOLE}
Uses SysUtils;
Type point=^zap;
zap=record
det:string[10];
diam:real;
p:point;
end;
Var r,q,f:point; a:zap;
c:integer;
Begin new(r);
r^.p:=nil;
Writeln('Input name, diam');
Readln(r^.det,r^.diam);
det diam p
zap
det diam p
a
r
q
f
r
det diam p
∅
Гайка
10

Создание списка по типу стека
ReadLn(a.det);
while a.det<>'end' do
begin Readln(a.diam);
q:=r;
new(r); r^.det:=a.det;
r^.diam:=a.diam;
r^.p:=q;
ReadLn(a.det);
end;
r
det diam p
det diam p
a
Гайка
10
r
det diam p
q
∅
Шайба
3
Болт

Вывод полученного списка
q:=r;
if q=nil then WriteLn('No records')
else
while q<>nil do
begin
WriteLn(q^.det:11,q^.diam:5:1);
q:=q^.p;
end;
r
det diam p
Болт
3
det diam p
∅
Гайка
10
q
∅

Варианты удаления элементов
first
5
q
4
8
∅
first
5
4
8
first
5
4
8
∅
f
8
∅
q
q
f
∅

Удаление записей
q:=r;
c:=0;
repeat
if q^.diam<1 then
if c=0 then
begin r:=r^.p; dispose(q); q:=r
end
else
begin q:=q^.p;
dispose(f^.p); f^.p:=q
end
else
begin f:=q;
q:=q^.p;
c:=1
end;
until q=nil;
r
q
r
q
f

Вывод результата и освобождение памяти
q:=r;
if q=nil then WriteLn('No records')
else while q<>nil do
begin
WriteLn(r^.det:11,r^.diam:5:1);
r:=r^.p;
dispose(q);
q=r;
end;
ReadLn;
End.
r
q
∅

Кольцевой список
1 2 3 4 5
Program Ex6_3;
{$APPTYPE CONSOLE}
Uses SysUtils;
Var y:integer;
Function Play(n,m:integer):integer;
Type child_ptr=^child;
child=record
name:integer;
p:child_ptr;
end;
Var First,Next,Pass:child_ptr;
j,k:integer;
1
3
2
4
5
first

Создание списка
begin { Создание списка }
new(First);
First^.name:=1;
Pass:=First;
for k:=2 to N do
begin new(Next);
Next^.name:=k;
Pass^.p:=Next;
Pass:=Next;
end;
Pass^.p:=First; {Замыкание круга}
1
2
5
First
Pass
Next
3
4

Проход по кольцу n-1 раз
Pass:=First;
for k:=n downto 2 do
begin
for j:=1 to m-1 do
begin
Next:=Pass;
Pass:=Pass^.p;
end;
1
2
5
First
Pass
Next
3
4

Удаление m-го элемента. Основная программа
WriteLn(Pass^.name);
Next^.p:=Pass^.p;
dispose(Pass);
Pass:=Next^.p;
end;
{Возврат результата}
Play:=Pass^.name; dispose(Pass);
end;
1
2
5
First
Pass
Next
3
4
Begin
y:=Play(5,7);
WriteLn('Result =',y:2);
ReadLn;
End.

6.5 Бинарные сортированные деревья
В математике бинарным деревом называют конечное множество вершин, которое либо пусто, либо состоит из корня и не более чем двух непересекающихся бинарных деревьев, называемых левым и правым поддеревьями данного корня.
Вершины, из которых не выходит ни одной ветви, называют листьями
Сортированные бинарные деревья, строятся по правилу: ключевое поле левого поддерева должно содержать значение меньше, чем в корне, а ключевое поле правого поддерева – значение больше или равное значению в корне.

Построение бинарного дерева
Рассмотрим последовательность целых чисел: {5, 2, 8, 7, 2, 9, 1, 5}
Пример. Разработать программу сортировки последовательности чисел с использованием бинарного дерева.
5
2
8
7
2
9
1
5

Описание элемента древовидного списка
Program Ex6_4;
{$APPTYPE CONSOLE}
Uses SysUtils;
Const lim=100;
Type top_ptr=^top;
top=record
value:integer;
left,right:top_ptr; end;
Var next_number:integer;
r,pass:top_ptr;
Основная
программа
Add1/Add2
Tree1/Tree2
Схема структурная ПО
1 – нерекурсивный вариант;
2 – рекурсивный вариант -

Основная программа
Begin WriteLn('Input numbers (End - 1000)');
r:=nil;
Read(next_number);
while next_number<>1000 do begin new(pass);
with pass^ do
begin value:=next_number;
left:=nil; right:=nil;
end;
Add1(r,pass);
Read(next_number)
end;
ReadLn;
WriteLn('Result:');
Tree1(r); ReadLn;
End.
pass
∅
∅
∅
r
5

Нерекурсивная процедура построения дерева
Procedure Add1(Var r:top_ptr; pass:top_ptr);
Var next,succ:top_ptr;
Begin if r=nil then r:=pass else
begin succ:=r;
while succ<>nil do
begin next:=succ;
if pass^.value
succ:=succ^.left
else succ:=succ^.right;
end;
if pass^.value
next^.left:=pass
else next^.right:=pass;
end;
End;
5
∅
r
pass
∅
∅
5
r
succ
∅
∅
2
pass
∅
∅
next
∅

Рекурсивная процедура построения дерева
Procedure Add2(Var r:top_ptr; pass:top_ptr);
begin
if r=nil then r:=pass
else if (pass^.value
Add2(r^.left,pass)
else Add2(r^.right,pass);
end;

Нерекурсивная процедура обхода дерева
Procedure Tree1(r:top_ptr);
var pass:top_ptr;
mem_top:record
nom:0..lim;
adres:array[1..lim] of top_ptr;
end; begin pass:=r;

Нерекурсивная процедура обхода дерева (2)
with mem_top do
begin nom:=0;
while (pass<>nil) or (nom<>0) do
if pass<>nil then
begin
if nom=lim then
begin Writeln(′Error lim'); exit;
end;
nom:=nom+1;
adres[nom]:=pass;
pass:=pass^.left;
end
else begin pass:=adres[nom];
nom:=nom-1;
writeln(pass^.value);
pass:=pass^.right;
end;
end;
end;
5
2
8
7
2
9
1
5

Рекурсивная процедура обхода дерева
Procedure Tree2(r:top_ptr);
begin
if r<>nil then
begin
Tree2(r^.left);
Write(r^.value:4);
Tree2(r^.right); end;
end;
Кроме этого при работе с деревом необходимо предусмотреть процедуру освобождения памяти, занятой двоичных деревом.