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

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

Приступаем к решению

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

uses PT4;

var

p1, p: PNode;

begin

Task('Dynamic30');

read(p1);

p := p1^.Next;

while p <> nil do

begin

p^.Prev := p1;

p1 := p1^.Next;

p := p^.Next;

end;

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

end.

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

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

P2

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

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

Правильное решение

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

p1^.Prev := nil;

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

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

uses PT4;

var

p1, p: PNode;

begin

Task('Dynamic30');

p := nil;

read(p1);

while p1 <> nil do

begin

p1^.Prev := p;

p := p1;

p1 := p1^.Next;

end;

write(p);

end.

Пример 5. Циклические динамические структуры

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

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

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

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

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

Приступаем к решению

Для решения задания Dynamic55 достаточно найти последний элемент исходного списка и связать его с первым элементом:

uses PT4;

var

p1, p2: PNode;

begin

Task('Dynamic55');

read(p1);

p2 := p1;

while p2^.Next <> nil do

p2 := p2^.Next;

p2^.Next := p1;

write(p2);

end.

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

Правильное решение

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

p1^.Prev := p2;

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

Просмотр результатов выполнения заданий

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

Dynamic2 a08/09 13:11 Ознакомительный запуск.

Dynamic2 a08/09 13:15 Выведены не все результирующие данные.

Dynamic2 a08/09 13:17 Ошибочное решение.

Dynamic2 a08/09 13:20 Задание выполнено!

Dynamic3 a08/09 13:21 Ознакомительный запуск.