Данная страница содержит подробное описание процесса решения типового задания на обработку динамических структур данных, а также примеры решения заданий на добавление элемента к динамической структуре, удаление элемента из динамической структуры, на обработку двусвязных и циклических динамических структур.

Анализ существующей динамической структуры: Dynamic2

В заданиях группы Dynamic мы встречаемся с двумя новыми видами данных: это динамические структуры, реализованные в виде цепочек связанных друг с другом записей типа TNode, и указатели типа PNode на записи TNode. В языках C и C++ записи оформляются в виде структур (типов данных struct). Типы TNode и PNode не являются стандартными типами библиотеки C или C++; они определены в задачнике Programming Taskbook, а точнее, в подключаемом файле pt4.h.

Особенности, связанные с использованием этих новых типов данных, рассмотрим на примере задания Dynamic2.

Dynamic2°. Дан адрес P₁ записи типа TNode. Эта запись связана полем Next со следующей записью того же типа, она, в свою очередь, — со следующей, и так далее до записи, поле Next которой равно NULL (таким образом, возникает цепочка связанных записей). Вывести значения полей Data для всех элементов цепочки, длину цепочки (т. е. число ее элементов) и адрес ее последнего элемента.

Создание программы-заготовки и знакомство с заданием

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

[C/C++]

void Solve()
{
    Task("Dynamic2");
}

Аналогичным образом выглядит функция Solve из файла Dynamic2.c, входящего в проект для языка C.

После запуска программы на экране появится окно задачника. На рисунке приводится вид окна в режиме с динамической компоновкой, появившемся в версии 4.11 задачника.

Это окно содержит в качестве исходных и результирующих данных новые элементы: динамические структуры и указатели.

Начнем с описания того, как отображается на экране динамическая структура. Для ее вывода используются две экранные строки; в первой строке отображаются имена указателей, связанных с данной структурой, а во второй — содержимое элементов этой структуры, т. е. значения их полей Data и способ связи между ними. Вся информация о динамической структуре отображается бирюзовым цветом (подобно информации об элементах файлов). Рассмотрим в качестве примера динамическую структуру, указанную на рисунке:

 P₁
 75 - 65 - 22 - 26 - 10 >NULL

Этот текст означает, что структура состоит из 5 элементов, причем ее первый элемент имеет поле Data, равное 75, и связан с помощью своего поля Next со вторым элементом, поле Data которого равно 65, и так далее до последнего, пятого элемента, поле Data которого равно 10, а поле Next равно NULL, т. е. нулевому адресу, что является признаком завершения структуры. Таким образом, текст, описывающий данную динамическую структуру, является упрощенным вариантом следующей схемы:

Примечание. Для возможности использования макроса NULL в программах на языке C к ним надо подключить заголовочный файл <stddef.h>. Однако в программах, выполняющих задания из электронного задачника, это делать необязательно, так как к ним этот заголовочный файл подключается автоматически.

Так как эта структура указана в разделе исходных данных, следовательно, после инициализации задания она уже существует и размещается в некоторой области динамической памяти (подобно тому, как исходные файлы после инициализации задания размещаются в каталоге учащегося). Как получить доступ к существующей динамической структуре? Здесь также уместна аналогия с файлами. Для доступа к внешнему файлу необходимо знать его имя, и в любом задании на обработку файлов имена исходных файлов входят в набор исходных данных. Для доступа к данным, размещенным в динамической памяти, необходимо знать их адрес, поэтому в любом задании на обработку динамических структур в набор исходных данных входят указатели, содержащие адреса этих структур.

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

P₁ = ptr

Здесь текст «P₁ =» является комментарием и выделяется, как обычный комментарий, светло-серым цветом, а текст «ptr» означает, что этот элемент исходных данных является указателем, который надо ввести в программу с помощью функции GetP. Для языка C++ можно также использовать функцию GetNode или поток ввода pt.

Примечание. Может возникнуть вопрос: почему вместо условного текста «ptr» не отображается «настоящее» значение указателя (т. е. некоторый четырехбайтный адрес)? Это связано с тем, что, даже выведя это значение на экран, мы не сможем определить, с какими данными связан этот адрес, поэтому подобная информация на экране будет излишней.

Итак, слово «ptr» в разделе исходных или результирующих данных означает, что соответствующий элемент данных является указателем, причем непустым (для пустого указателя используется слово «NULL»). Определить, с каким элементом динамической структуры данных связан непустой указатель, можно по экранной информации об этой динамической структуре. Разумеется, при чтении указателя (например, с помощью функции GetP) программа учащегося получит «настоящий» адрес, с помощью которого она сможет обратиться к исходной динамической структуре.

Аналогично, создав (или преобразовав) некоторую динамическую структуру, программа учащегося должна передать задачнику некоторый адрес, связанный в этой структурой (используя функцию PutP (для языка C++ можно также использовать поток вывода pt). Зная этот адрес, задачник сможет проверить правильность созданной структуры.

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

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

Приведем вначале неполное решение задачи, выводящее все необходимые данные, кроме указателя на последний элемент. Это решение можно использовать как для языка C, так и для языка C++, так как в нем применяются функции ввода-вывода, доступные для обоих этих языков.

[C/C++]

Task("Dynamic2");
int n = 0;
PNode p1;
GetP(&p1);
while (p1 != NULL)
{
    PutN(p1->Data);
    n++;
    p1 = p1->Next;
}
PutN(n);

После запуска программы можно убедиться, что все числовые результирующие данные определены правильно, однако из-за того, что не выведен указатель на последний элемент, решение признано ошибочным с диагностикой «Выведены не все результирующие данные».

Добавим в конец полученного решения вызов функции PutP:

[C/C++]

PutP(p1);

После запуска нового варианта программы все требуемые данные будут выведены, однако результирующее значение указателя будет равно NULL. Это связано с тем, что после завершения цикла while в переменной p1 содержится нулевой указатель, а не указатель на последний элемент динамической структуры.

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

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

[C/C++]

Task("Dynamic2");
int n = 0;
PNode p1, p2;
GetP(&p1);
while (p1 != NULL)
{
    PutN(p1->Data);
    n++;
    p2 = p1;
    p1 = p1->Next;
  }
PutN(n);
PutP(p2);

Проверив программу на трех тестовых наборах, мы получим сообщение «Задание выполнено!».

Заметим, что вместо макроса NULL для обозначения нулевого указателя можно использовать обычную константу 0. Таким образом, заголовок цикла while можно записать в следующем виде:

while (p1 != 0)

Более того, учитывая, что ненулевой указатель в C и C++ может интерпретироваться как логическое значение «истина», а нулевой указатель — как логическое значение «ложь», заголовок цикла можно записать еще более кратко:

while (p1)

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

В современных версиях C++ вместо макроса NULL рекомендуется использовать специальное ключевое слово nullptr.

Добавление элемента к динамической структуре: Dynamic3

Рассмотрим задание Dynamic3, связанное с добавлением элемента к динамической структуре-стеку.

Dynamic3°. Дано число D и указатель P₁ на вершину непустого стека. Добавить элемент со значением D в стек и вывести адрес P₂ новой вершины стека.

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

При ознакомительном запуске этого задания мы обнаружим новое обозначение в тексте, описывающем динамическую структуру, а именно — точки, обрамляющие первый элемент результирующего стека (на рисунке так выделен элемент 57).

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

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

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

[C/C++]

Task("Dynamic3");
int d;
PNode p1;
GetN(&d);
GetP(&p1);
PutP(p1);

В результате, если исходный стек содержал, к примеру, четыре элемента со значениями 12, 24, 74 и 49, полученный стек будет отображен на экране следующим образом:

 P₂
(12)-(24)-(74)-(49)>NULL

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

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

Для получения правильного решения задания Dynamic3 необходимо явно выделить память для нового элемента, используя функцию malloc (или, для языка C++, операцию new), и заполнить поля этого элемента, связав его с текущей вершиной стека (в результате сам этот элемент станет новой вершиной, адрес которой и следует вывести):

[C/C++]

Task("Dynamic3");
int d;
PNode p1;
GetN(&d);
GetP(&p1);
PNode p2 = (PNode)malloc(sizeof(TNode));
p2->Data = d;
p2->Next = p1;
PutP(p2);

Проверив программу на пяти тестовых наборах, мы получим сообщение «Задание выполнено!».

Стандартная функция malloc определена в заголовочном файле <stdlib.h>, однако этот файл не требуется подключаться к программе директивой #include, так как такая директива уже указана в подключаемом файле pt4.h.

Заметим также, что преобразование результата, возвращаемого функцией malloc, к типу PNode, требуется только в программе на языке C++. Впрочем, для этого языка более удобным вариантом выделения памяти является использование операции new:

[C++]

PNode p2 = new TNode;

Решение на языке C++ можно сделать еще более кратким, если вначале создать новый узел, а затем ввести исходные данные в поля созданного узла и при этом использовать поток ввода pt:

[C++]

Task("Dynamic3");
PNode p2 = new TNode;
pt >> p2->Data >> p2->Next;
pt << p2;

Аналогичным образом можно сократить и решение для языка C:

[C]

Task("Dynamic3");
PNode p2 = malloc(sizeof(TNode));
GetN(&p2->Data);
GetP(&p2->Next);
PutP(p2);

Удаление элемента из динамической структуры: Dynamic5

Рассмотрим задание Dynamic5, связанное с удалением элемента из динамической структуры.

Dynamic5°. Дан указатель P₁ на вершину непустого стека. Извлечь из стека первый (верхний) элемент и вывести его значение D, а также адрес P₂ новой вершины стека. Если после извлечения элемента стек окажется пустым, то положить P₂ = NULL. После извлечения элемента из стека освободить память, занимаемую этим элементом.

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

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

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

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

[C/C++]

Task("Dynamic5");
PNode p1;
GetP(&p1);
PutN(p1->Data);
PutP(p1->Next);

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

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

Для получения правильного решения достаточно добавить в конец функции Solve вызов функции DeleteNode (данная функция описана в файлах pt4.c и pt4.cpp):

[C/C++]

DeleteNode(p1);

Начиная с версии задачника 4.11, для языка C++ вместо функции DeleteNode можно использовать стандартный оператор освобождения памяти delete:

[C++]

delete p1;

Проверив исправленную программу на пяти тестовых наборах, мы получим сообщение «Задание выполнено!».

Двусвязные динамические структуры: Dynamic30

Особенности работы с двусвязными динамическими структурами рассмотрим на примере задания Dynamic30.

Dynamic30°. Дан указатель P₁ на начало непустой цепочки элементов-записей типа TNode, связанных между собой с помощью поля Next. Используя поле Prev записи TNode, преобразовать исходную (односвязную) цепочку в двусвязную, в которой каждый элемент связан не только с последующим элементом (с помощью поля Next), но и с предыдущим (с помощью поля Prev). Поле Prev первого элемента положить равным NULL. Вывести указатель на последний элемент преобразованной цепочки.

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

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

 P₁
 35 - 11 - 36 - 39 - 56 >NULL

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

                          P₂
NULL< 35 = 11 = 36 = 39 = 56 >NULL

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

Решение задачи

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

[C/C++]

Task("Dynamic30");
PNode p1, p2 = NULL;
GetP(&p1);
while (p1 != NULL)
{
    p1->Prev = p2;
    p2 = p1;
    p1 = p1->Next;
}
PutP(p2);

Проверив программу на пяти тестовых наборах, мы получим сообщение «Задание выполнено!».

Циклические динамические структуры: Dynamic55

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

Dynamic55°. Дан указатель P₁ на первый элемент непустого двусвязного списка. Преобразовать список в циклический, связав его последний элемент с помощью поля Next с первым, а первый элемент с помощью поля Prev — с последним, и вывести указатель на элемент, который был последним элементом исходного списка.

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

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

      P₁
NULL< 19 = 94 = 51 = 41 = 55 >NULL

                          P₂
 << = 19 = 94 = 51 = 41 = 55 = >>

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

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

Решение задачи

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

[C/C++]

Task("Dynamic55");
PNode p1, p2;
GetP(&p1);
p2 = p1;
while (p2->Next != NULL)
    p2 = p2->Next;
p2->Next = p1;
PutP(p2);

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

                P₂
NULL< 38 = 24 = 91 - >>

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

[C/C++]

p1->Prev = p2;

Проверив исправленную программу на трех тестовых наборах, мы получим сообщение «Задание выполнено!».

Разработка сайта:
М. Э. Абрамян, В. Н. Брагилевский

Последнее обновление:
01.01.2024