Динмаческая память – это оперативная память ПК, выделяемая программе при ее выполенние за вычетом сигмента данных, стека и тела программы. Размер динамической памяти по умолчанию определяеться все доступной паматью ПК. Динамическа память – это фактически единественная возможность обработки массивов большой размерности, многие задачи трудно или невозможно решить, без использования динмаческой памяти. Оперативная память ПК, представляет собой совокупность байтов, каждый из который имеет сво й номер(адрес), что дает возможность обрашаться к любому байту памяти. Указатель это переменная значением которой являеться адрес. При описание типизированного указателя, необходимо сообшить компилятору адреса переменных какого типа он может хранить.
Var <имя_указателя>:^<тип адресуемой переменной>
При этом существуют универсальные нетепизированные указатели, которые могут хранить адрес переменой любого типа:
Var <имя_указателя>: Pointer;
Переменная ссылочного типа, вводиться обычным образом;
Type
TArr1=Array[1..100] of integer;
Ref_Arr:^TArr1;
Var
p:^Integer;
q:^real;
RMass:Ref_Arr;
Связь указателя с объектом
| указатель |
| объект |
Существует Nil, который не связывает никакой объект. При описании ссылочной переменной, она не указывает ни на какой объект, и даже не имеет значение Nil. Таким образом описание указателя вводит в употребление переменную, но не определяет никакого программного объекта на который будет указываеть, значение ссылочной пременной. Для пораждения динамического объекта служит процедура New(указатель) в которой задаеться указатель сопостовляемая порождаемому динамическому объекту. Обратим внимание на то, что этому объекту не присваиваеться какое – либо значение, т.е процедура New для динамического объекта играет туже роль,что и описание для статического объекта. Для того, чтобы извлечь значение хранящиеся по некоторому адресу используеться унарная операция «^ » – разименование. <имя_указателя>^;
Var
p:^integer;
…
new(p);
p^:=123;
Переменная с указателем, может использоваться в любых конструкциях языка, где допустимо использование переменных данного типа.
Операции над указателями
Допускаеться только «:=» и две операции сравнения: = && <>
v=e; где е ссылочное выражение, которая задает ссылочное значение того – же типа, что и переменная v. В качестве ссылочного выражения,могут использоваться: Nill, ссылочная переменная и ссылочная функция(значением которой являеться ссылка), для указателей действует более жесткие требование к совместимости типов, чем к обычным выражений. В операции присваивания, могут фигурировать только указатели на переменные одинаковых типов. Так на пример:
Var
p:^integer;
q:^byte;
p:=q; – Это будет ошибкой;
Обойти эти ограничения позволяет универсальность нетипизированного указателя
t:Poniter;
t:=q; p:=t;
Var
p,d:^integer;
…
New(p);
New(d);
p^:=3;
d^=5;
p:=d;
d:=Nil;
В данном примере после p:=d; на динамический объект со значением 3 не укзаывает не одна ссылка, т.е он стал не доступным для программы. Допусткаються две операции сравнения. Так как значение этого типа – это адреса соответствующих объектов. То операции сравнения не имеют смысла, так как позволили бы определить, какой из объектов ближе или концу памяти, что для программиста похуй. Два значения ссылочного типа равны если они Nil или указывают на один и тот же динамический объект. Во всех остальных случаях имеет место неравенство.
Уничтожение указателей
Процедура Dispose(p) освобождает память, от объекта на который ссылаеться переменная «р». При этом значения указателя являеться неопределенным. Процедура Dispose(p) удаляет сам динамический объект, но не указатель на него. Стандартные процедуры, New and Dispose позволяют динамически пораждать и убивать объекты, что дает возможность более эфективно испльзовать оперативную память.
Dispose(p) – уничтожает обьект, на который ссылается p. Но к этому времени d указывает на тот же динамический обьект. Возьникает конфликтная ситуация.
Динамические структуры данных
Линейный список: В этом случаее каждому элементу, нужно сопоставить ссылку на следующий элемент
Type TEL={некоторй тип}
Ref=^Node;
Node=Record
Inf:TEL;
Next:Ref;
end;
Var
First,p:Ref;
Обрашаем внимание на то, что при описании Ref используеться описание которое, описываеться позже. Это ед. в паслке исключение сделано для возможности организации динамических структур. Информационное поле Inf может содержать любую информацию произвольной структуры, которая определяеться типом TEL. Графически список можно представить в виде
| * |
| Inf 1 |
| Next |
| Inf 2 |
| Next |
При описании любой динамической структуры данных главное определить возможные операции над ее элементами. Так элементами линейного списка выполняються следуюшие элементарные операции:
1) включение элемента в список
2) удаление
3) поиск
При написание процедур реализуюших основные операции над списками будем предпологать наличие приведенных ранее описание типов. Короче смотри выше.
Включение нового эллемента, после эллемента со ссылкой Р.
Procedure In_Spi(NewInf:TEL; R:Ref);
Var
p:Ref;
Begin
new(p);
p^.inf=NewInf;
p^.next:=R^.next;
R^.next:=p;
end;
Удаление эллемента из списка:
Procedure Del_Spi(R:Ref);
Var
p:ref;
Begin
p:=R^.next;
R^.next:=p^.next;
dispose(p);
end;
Вывjд списка на экран:
Procedure Out_Spi(R:Ref);
Var
p:ref;
Begin
write(‘List<’);
p:=R;
while p<>Nil do
Begin
write(p^.Inf:4);
p:=p^.next;
end;
writeln(‘>’);
end;
В качестве примера приведем формирование списка целых чисел тип элемента TEL=integer; признак завершения ввода 0.
First:=nil;
write(‘ – >’);readln(x);
if x<>0 then
Begin
new(q);
q^.inf:=x;
q^.next:=nil;
first:=q;
write(‘ – >’);Readln(x);
while x<>0 do
Begin
In_Spi(x,q);
q:=q^.next;
write(‘ – >’);
readln(x);
end;
end;
Процедуру поиска элемента я легко сделаю сам.
Procedure (find:TEL);
Var
p:Ref;
find:TEL;
Begin
p:=First;
while (p<>nill) or (p^.inf<>find) do
Begin
find:=p^.inf;
p:=p^.next;
end;
end;
Двунаправленный список
Принцип реализации такой – же как и для линейного списка. При этом описании элемента естественно будет должна входить ссылка не только на следуюший элемент но и на предыдуший.
| * |
| Inf 1 |
| Next |
| Inf 2 |
| Next |
| Pred |
| Pred |
В программирование двунаправленные списка обошают так: в поле next последнего эллемента помешают ссылку на первый элеемент, а в поле pred первого элемента помешаем ссылку на последний элеемент. Такие списки носят имя Кольцова Ю.В. и называються колцевыми. Процедуры включения, удаления, ввывода я без труда сделаю сам.
Очередь и стек
Наиболее часто встречаються линейные списки, в которых доступ к элементам производиться только к первому или последнему эллементу.
Очередь – это линейный список в котором все включения производиться на одном конце а исключения на другом – это принцип FIFO.
Стек – это линейный список в которм все включения и исключения производиться на одном конце – это принцип LIFO
Над этими структурами данных определены операции включения, удаления, и проверка на пустоту.
Принципы организации этих структур очень похожи. Подробно остановимся на стеке. В силу того что очередь и стек – это линейные списки тип данных в примера будем использовать прежний TEL.
//задача на лекции\примеры задача на стек
Поскольку при решении задачи может использоваться несколько разных стеков, то процедура вставки должна иметь два параметра: вносимый эллемент и ссылка на стек.
Дек(DEQUE) – это Кнут ввел понятие усложненный очереди. Двух концевая очередь. В каждый момент времени у Дека как первый так и последний эллемент при чем добовлять и удалять эллементы можно и в начале и в конце дека. Таким образом дек – это симметричная двухсторонняя очередь.
Деревья
К более сложным структурам относяться деревья. Существует несколько способов изображения структуры дерева однако чаще всего используеться «естественное» поисание. Когда есть корень, ветви и листья. При этом деревья принято рисовать вверх. Особую роль играет двоичные(бинарные) деревья, в которой из каждой вершины выходи не более два ребра. Знакомые примеры двоичных деревьев: гениологическое дерево, схема турнира и т.п. Деревья синтасического разбора строяться компиляторами во время синтасического анализа программы.
Type TEL=integer;
Ptree=^Ttree;
Ttree=record
inf:TEL;
left,right:Ptree;
end;