type T=<тип>;
var p:=^T;
…………….
new(p);
…………….
dispose(p);
_________________
getmem (p, sizeof(T));
……………..
freemem (p, sizeof(T));
В общем случае getmem и freemem дают большую свободу действий по сравнению с new и dispose, т.к. позволяют работать без привязки к конкретному типу переменных:
type zap=record
x,y:integer;
end;
st=string [20];
var p:pointer;
begin getmem (p,100); zap(p^).x:=124; zap(p^).y:=47; ………………
real(p^):=0.213; ……………….
st (p^):= ‘Привет’; ……………….
freemem(p,100);
| Вопрос №38.Процедуры mark и release.Пр-ры dispose/freemem освобождают участок того же размера, кот. был выделен пр-рами new/getmem. Эти участки могут исп-ся для хранения дин. переменных. Однако в ряде версий Pascal с-ма не выполняет автоматических действй по поиску и объединению разрозненных фрагментов памяти в одну непрерывную область. Пр-ры mark и release были разработаны для более эффективного размещения дин. переменных и устранения фрагментации памяти.mark(p1);p1 – перем. типа указательmark присваивает параметру р1 адрес начала свободной области дин. памяти. Помеченная область с пом. new/getmem исп-ся для размещения дин. переменных. Когда данные дин. переменные окажутся ненужными, занимаемую ими память можно освободить: release(p1).release освобождает память, начиная с адреса, полученного в рез-те выполнения последней пр-ры mark, значение р1=nil. |
Параметр пр-ры mark нельзя исп-ть в кач-ве параметра пр-ры new/getmem и его нельзя изменять до использования в проге release.
Возможна вложенность пр-р mark, тогда каждой mark соответствует своя release.
☻Пример:
var p1,p2:^integer;
………………
mark(p1); ……………… new(p); new(q); ……………… mark(p2);
new(x); ……………… release(p2);……………… release(p1);
!!! В одной и той же проге не рекомендуется исп-ть одновременно dispose/freemem и mark/release.
Вопрос №39.
Динамические цепочки. Объявление. Алгоритм формирования цепочки.
Д. цеп. – аналог строк текущей длины.
Эл-ты строки можно размещать в памяти произвольно, если каждый эл-т снабдить явным указанием места, где находится след. эл-т. В этом случае каждый эл-т строки должен состоять из двух полей: в одном – символ строки, в другом – адрес след. эл-та. Каждая такая пара полей наз. звеном. Ссылки сцепляют звенья в единую цепочку. Такой способ представления упорядоченной послед-сти эл-тов наз. сцеплением. Оно применяется для представления дин. структур любой сложности. Тело звена – информац. часть, справочная часть звена – адрес звена (след., пред., и т.д.).
Для представления звена цепочки необход. исп-ть запись их 2-х полей.
type adr=^zveno;
zveno=record
element:char;
adrsled:adr;
end;
Последнее звено цепочки должно быть снабжено ссылкой nil. Для работы с цепочкой должна исп-ся ссылка на 1-е звено
varadr1:adr;
1-й элемент
adr1
Для удобства работы с цепочкой в нее включается заглавное (нулевое) звено. В поле adrsled заглав. звена содержится адрес первого звена цепочки.
☻Пример (формирование цепочки):
type -//-;
varadr1, adrzv:adr; {adr1 – адрес 1-го звена, adrzv – адрес текущего звена}
simv:char;
begin
new(adr1);
adrzv:=adr1;
adrzv^.adrsled:=nil; {при формировании цепочки текущее звено всегда явл. последним}
read(simv);
while simv<>’.’ do
begin
{1} new(adrzv^.adrsled);
{2} adrzv:=adrzv^.adrsled;
{3} adrzv^.element:=simv;
{4} adrzv^.adrsled:=nil;
{5} read(simv);
end;
Алгоритм формирования цепочки (в примере):
1. Отвести область памяти для очередного звена. Его адрес занести в адресную часть текущего звена.
2. Новое звено сделать текущим звеном.
3. В поле element текущ. звена занести прочитанный символ.
4. В адресную часть текущ. звена занести nil.
5. Прочитать очередной символ и перейти к п.1.
Вопрос №40.
Операции, определенные над динамическими цепочками.
Над цепочкой опред. 3 операции:
1. Поиск эл-тов в цепочке.
2. Вставка эл-тов в произвольное место в цепочке.
3. Удаление заданного эл-та.
¬ Для перехода от одного звена цепочки к след. необход. в цикле выполнять оператор: adrzv:=adrzv^.adrsled. Этот оператор аналогичен i:=i+1 для обычных статических цепочек.
…………………
adrzv:=adr1;
k:=0;
read(bukva);
while adrzv^.adrsled<>nil do
begin
adrzv:=adrzv^.adrsled;
if adrzv^.element=bukva then k:=k+1;
end;
® Удаляемый эл-т задается ссылкой на пред. звено, при этом учитывается, что если какое-либо звено сущ-ет, но на него нет ссылки из другого звена, то оно не доступно
Для исключения эл-та из строки необходимо изменить ссылку у предшествующего ему эл-та. В кач-ве новой ссылки у этого эл-та необход. принять ссылку из исключаемого эл-та.
adrzv^.adrsled:=adrzv^.adrsled^.adrsled.
procedure Del (zv:adr);
var a:adr;
begin
a:=zv^.adrsled;
zv^.adrsled:=zv^.adrsled^.adrsled;
dispose(a);
end;
Вставка основывается на объединении отдельных звеньев в единую цепочку.
Алгоритм вставки:
1. Создать новую дин. переменную типа zveno.
2. В поле element этой переменной занести вставляемый эл-т.
3. В поле adrsled этой переменной занести ссылку, взятую из поля adrsled пред. звена.
4. В поле adrsled пред. звена занести адрес вставляемого звена.
procedure Insert (zv:adr; el:char);
var q:adr;
begin
{1} new(q);
{2} q^.element:=el;
{3} q^.adrsled:=zv^.adrsled;
{4} zv^.adrsled:=q;
end;
Дин. цепочка явл. частным случаем линейного однонаправленного списка. В цепочке информационными эл-тами явл. символы (char). В общем случае информац. эл-тами могут быть значения любого типа. Принцип организации информац. эл-тов в список тот же.
typeadres1=^zveno1;
zveno1=record
adrsled:adres1;
element:<тип_эл-та_списка>;
end;
Вопрос №41.
Двунаправленные списки. Объявление. Способы организации колец. Формирование кольца (по первому способу).
Недостатки линейного однонаправленного списка: по нему можно двигаться только в одном направлении (от начала к концу).
2-направл. списки позволяют двигаться по списку в любом направлении. Каждое звено 2-нопраленного списка списка содержат 2 поля ссылочного типа: на последнее и на предыдущее звено.
Структура опред. следующим описанием.
Объявление.
Type
Adr2=^Zveno2;
Zveno2 = Record
Adrcled: Adr2;
Adrpred: Adr2;
Element: <Тип_элемента_списка>;
End;
Кольцевые списки.
(1 способ) На осн. 2-направленного списка могут быть организованы 2-направленные кольцевые списки.
В кольц. списке значение поля Adrcled последнего звена – ссылка на начальное звено, а Adrpred начального звена – ссылка на последнее звено.
(2 способ) заглавное звено не включают в кольцо.
Достоинство: проще реализуется вставка нового звена, как в начало списка, так и в конец.
Недостатки: 1 способа: при циклических обработках, элементы списка необходимо проверять: не является ли очередное звено заглавным звеном.
У 2 способа данный недостаток отсутствует, но труднее реализовать добавление звена в конец списка.
Над 2-направленными списками определены операции: поиск элемена в списке, вставка и удаление.
Вопрос №43.
Операции, определенные над двунаправленными кольцевыми списками. Примеры (для 1-го способа организации колец).
1)Встака эл-та
Алгоритм – порождение нового звена;
- занесение вставленного элемента в информационное поле порожденного звена.
1) записать в поле Аdrcled ссылки на след эл-т из звена предшествующему вставляемому;
2) занести в Аdrpred ссылки на предшеств.эл-т из звена следующ. вставляемому;
3) занести в Аdrpred след. за вставл. звено ссылки на вставляемое звено;
4) в Аdrpred предшествующего звена ссылки на вставляемое звено;
Procedure Vstsv
(Elem: <Тип_элемента>)
{1} New (Q);
{2} Q^.Element:=Elem;
{3} Q^.Adrcled:=PredZV^.Adrcled;
{4} Q^.Adrpred:=PredZV;
{5} PredZV^.Adrcled^. Adrpred:=Q;
{6} PredZV^.Adrcled:=Q;
End;
Создание 2-направленного кольцевого списка с заглавным звеном.
Для создания кольцевого списка, после создания любого звена, список нужно закольцевать.
Var
Ring: Adr2; (адрес заглавного звена)
Bykva: Char;
Begin
New(Ring);
Ring^.Adrcled:=Ring;
Ring^.Adrpred:=Ring;
While Bykva< >’.’do
begin
Vstav(Bykva, Ring^.Adrcled);
Read(Bykva);
End.
Удаление элемента.
1. занес. в Аdrpred след. за удаляемым звеном ссылку на предшествующий удаляемому звену;
2. в Аdrcled предшеств. удаляемому звену ссылки на след. за удаляемым звеном;
3. уничтожение удаляемого звена.
{1} Adrzv^.Adrcled^. Аdrpred:=Ydzv^. Аdrpred;
{2} Ydzv^. Аdrpred^. Аdrcled:= Ydzv^. Аdrcled;
{3} Dispose(Ydzv);
Поиск элемента.
Аналогичен поиску элементов в цепочке, но в кольцевом списке формально нет последнего элемента.
Q:=P^. Аdrcled; (Р-адрес заглавного звена)
While (P< >Q) and not B do (Q-адрестекущегозвена)
Вопрос №45.
Очередь FIFO. Объявление. Операции, определенные над очередью FIFO. Организация очереди FIFO.
Очередь (FIFO).
Для организации такой очереди исп-ся 2 ссыл. переменные типа
adr1:Left – указывает на начало очереди;
adr2:Right - указывает на конец очереди.
Добавление осуществляется в соответствии со значением right. Затем это значение изменяется и указывает на последний занесенный эл-т.
Выборка осуществляется в соответствии со значением Left. Затем изменяется и указывает на след. эл-т очереди. Если в очереди всего 1 эл-т, то Right=Left. Обычно это исп-ся как прзнак окончания очереди при выборе.