W Cat - Описание языка PascalABC.NET

Особенность заданий на удаление элементов из динамических структур заключается в том, что удаляемый элемент необходимо не только отсоединить" от исходной динамической структуры, но и полностью "уничтожить", то есть освободить память, занимаемую этим элементом .

Для того чтобы напомнить учащемуся о необходимости уничтожения некоторых элементов исходной динамической структуры, эти элементы выделяются на экране синим цветом меньшей яркости, чем обычные элементы (на рисунке таким способом выделен элемент 15):

Вначале приведем неправильный вариант решения, в котором не освобождается память, занимаемая удаленным из стека элементом:

usesPT4;

varp1: PNode;

begin

Task('Dynamic5');

read(p1);

write(p1^.Data, p1^.Next);

end.

Несмотря на то что все результирующие данные будут совпадать с контрольными (то есть текст в разделах Полученные результаты" и "Пример верного решения" будет одинаковым), на информационной панели появится сообщение об ошибке " Не освобождена динамическая память ", а в разделе исходных данных будет выделен красным цветом тот элемент, который требовалось удалить:

Для получения правильного решения достаточно добавить в конец программы оператор вызова процедуры Dispose, освобождающий память, на которую указывает указатель p1:

usesPT4;

varp1: PNode;

begin

Task('Dynamic5');

read(p1);

write(p1^.Data, p1^.Next);

Dispose(p1);

end.

Приведем вид окна задачника при первом запуске этой программы:

Знакомство с заданием

Особенности работы с двусвязными динамическими структурами рассмотрим на примере задания Dynamic30, в котором требуется преобразовать исходную односвязную структуру в двусвязную. Запустив программу-заготовку, созданную для этого задания, мы увидим в области исходных данных информацию об обычной" односвязной структуре, подобной рассмотренным в предыдущих примерах:

Динамическая структура, приведенная в разделе результатов, имеет две особенности: во-первых, ее элементы связаны символом =, а во-вторых, перед первым элементом присутствует текст nil<.

Это означает, что результирующая структура является двусвязной , то есть каждый ее элемент связан не только с последующим элементом (с помощью поля Next, как в односвязной структуре), но и с предыдущим элементом (с помощью нового поля Prev), а поле Prev первого элемента имеет значение nil:

Для преобразования исходной односвязной структуры в двусвязную необходимо задать правильные значения для полей Prev всех элементов структуры, перебирая в цикле пары соседних элементов:

usesPT4;

var

p1, p: PNode;

begin

Task('Dynamic30');

read(p1);

p := p1^.Next;

whilep <> nil do

begin

p^.Prev := p1;

p1 := p1^.Next;

p := p^.Next;

end;

write(p1); { вывод указателя на последний элемент }

end.

В этой программе мы определили поля Prev для всех элементов, кроме первого. Поэтому решение будет считаться ошибочным (обратите внимание на то, что перед первым элементом полученного списка отсутствует текст nil<):

Замечание.При анализе ошибочного решения часто оказывается полезным и специальное обозначение =" для двойной связи. Предположим, например, что информация о результирующей двусвязной структуре, созданной программой, имеет вид:

P 2

nil< 33 = 64 - 78 = 12 = 51 nil

Это означает, что между вторым и третьим элементом структуры имеется не двойная, а одинарная связь (поле Next второго элемента содержит адрес третьего элемента, а поле Prev третьего элемента не содержит адрес второго).

Для получения правильного решения достаточно добавить в программу перед циклом while следующий оператор:

p1^.Prev := nil;

Приведем вид окна задачника при первом запуске исправленной программы:

Замечание.Для задания Dynamic30 возможен более короткий вариант решения, в котором не требуется особо обрабатывать первый элемент списка:

usesPT4;

var

p1, p: PNode;

begin

Task('Dynamic30');

p := nil;

read(p1);

whilep1 <> nil do

begin

p1^.Prev := p;

p := p1;

p1 := p1^.Next;

end;

write(p);

end.

Знакомство с заданием

Динамическая структура называется циклической , если она замкнута в кольцо", то есть ее последний элемент связан полем Next с первым (в случае двусвязной структуры требуется также, чтобы ее первый элемент был связан полем Prev с последним элементом). Простейшим заданием на циклические структуры является Dynamic55, в котором требуется преобразовать обычный двусвязный список в циклический.

Запустив программу-заготовку для этого задания, мы увидим на экране изображение двух динамических структур, причем исходная структура является обычным" двусвязным списком, а результирующая структура -- циклическим двусвязным списком:

Обозначения << = и = >> позволяют отличить циклический список от обычного (напомним, что у обычного двусвязного списка поле Prev первого элемента и поле Next последнего элемента равны nil).

Таким образом, экранный текст, описывающий циклический двусвязный список, является упрощенным вариантом следующей схемы: