/
n-dimens
/
pascalabcnet
Обзор
Документация
Войти
/
n-dimens
/
pascalabcnet
Код
Запросы
0
Задачи
Вики
Пакеты
0
Релизы
0
Аналитика
Безопасность
master
PABCNetHelp/ForEducation/CheckedTasks/ctpointer.html
535 строк
31 KB
samuraiGH
adding working-tree-encoding attribute (#3325)
07 ноя 2025, 16:12
Не верифицирован
07 ноя 2025, 16:12
cf1fd29
Код
Авторство
О чём код?
<html> <head> <meta http-equiv="Content-Type" content="text/html; charset=windows-1251"> <title></title> <link rel="StyleSheet" href="../../default.css"> </head> <body> <H1>Задания на указатели и динамические структуры данных</H1> <hr> <H2>Пример 1. Анализ существующей динамической структуры</H2> <hr> <p>В заданиях группы Dynamic мы встречаемся с двумя новыми видами данных: это <i>динамические структуры</i>, реализованные в виде цепочек связанных друг с другом записей типа <code>TNode</code>, и <i>указатели</i> типа <code>PNode</code> на записи <code>TNode</code>: <code>PNode = ^TNode</code>. Типы <code>TNode</code> и <code>PNode</code> не являются стандартными типами языка Паскаль; они определены в задачнике Programming Taskbook следующим образом (приводятся только те поля записи <code>TNode</code>, которые используются при выполнении заданий группы Dynamic):</p> <blockquote> <code><pre> <b>type</b> PNode = ^TNode; TNode = <b>record</b> Data: integer; Next: PNode; Prev: PNode; . . . <b>end</b>; </pre></code> </blockquote> <p>На примере задания Dynamic2 рассмотрим особенности, связанные с использованием этих новых типов данных.</p> <hr> <h3>Создание программы-заготовки и знакомство с заданием</h3> <p>Программа-заготовка для задания Dynamic2, созданная с помощью команды меню «Модули | Создать шаблон программы», кнопки <img border="0" src="gif/Load.gif" width="16" height="17"> или клавиатурной комбинации <b>Shift+Ctrl+L</b>, имеет следующий вид:</p> <blockquote> <code><pre> <b>uses</b> PT4; <b>begin</b> Task('Dynamic2'); <b>end</b>. </pre></code> </blockquote> <p>После запуска данной программы на экране появится <a href="../PT4/window.html">окно задачника</a>:</p> <blockquote> <img border="0" src="gif/Dynamic2-1.png"> </blockquote> <p>Это окно содержит в качестве исходных и результирующих данных новые элементы: динамические структуры и указатели.</p> <p>Начнем с описания того, как отображается на экране <i>динамическая структура</i>. Для ее вывода используются две экранные строки; в первой строке отображаются имена указателей, связанных с данной структурой, а во второй — содержимое элементов этой структуры, то есть значения их полей <code>Data</code> и способ связи между ними. Вся информация о динамической структуре отображается бирюзовым цветом (подобно информации об элементах файлов).</p> <p>Рассмотрим в качестве примера динамическую структуру, указанную на рисунке:</p> <blockquote> <code><pre> P<sub>1</sub> 75 - 65 - 22 - 26 - 10 >nil </pre></code> </blockquote> <p>Этот текст означает, что структура состоит из 5 элементов, причем ее первый элемент имеет поле <code>Data</code>, равное 75, и связан с помощью своего поля <code>Next</code> со вторым элементом, поле <code>Data</code> которого равно 65, и так далее до последнего, пятого элемента, поле <code>Data</code> которого равно 10, а поле <code>Next</code> равно <code>nil</code>, что является признаком завершения структуры. Таким образом, текст, описывающий данную динамическую структуру, является максимально упрощенным вариантом следующей схемы:</p> <blockquote> <img border="0" src="gif/Dynamic2-2.png"> </blockquote> <p>Поскольку эта структура указана в разделе исходных данных, следовательно, после инициализации задания она <i>уже существует</i> и размещается в некоторой области динамической памяти (подобно тому, как исходные файлы после инициализации задания размещаются в каталоге учащегося).</p> <p>Как получить доступ к этой существующей динамической структуре? Здесь также уместна аналогия с файлами. Для доступа к внешнему файлу необходимо знать его <i>имя</i>, и в любом задании на обработку файлов имена исходных файлов входят в набор исходных данных. Для доступа к данным, размещенным в динамической памяти, необходимо знать их <i>адрес</i>, и поэтому в любом задании на обработку динамических структур в набор исходных данных входят <i>указатели</i>, содержащие адреса этих структур.</p> <p>Из текста, описывающего динамическую структуру, видно, что на ее первый элемент указывает указатель с именем <code>P<sub>1</sub></code>, который также содержится в наборе исходных данных. Описание этого указателя имеет вид</p> <blockquote> <code><pre> P<sub>1</sub> = ptr </pre></code> </blockquote> <p>Здесь текст <code>P<sub>1</sub> =</code> является <i>комментарием</i> и выделяется, как обычный комментарий, светло-серым цветом, а текст <code>ptr</code> означает, что этот элемент исходных данных является <i>указателем</i>, который надо ввести в программу с помощью процедуры ввода <code>read</code>.</p> <p><b>Замечание.</b> Может возникнуть вопрос: почему вместо условного текста «ptr» не отображается «настоящее» значение указателя (то есть некоторый четырехбайтный адрес)? Это связано с тем, что, даже выведя это значение на экран, мы не сможем определить, с какими данными связан этот адрес, поэтому подобная информация на экране будет излишней.</p> <p>Итак, слово <code>ptr</code> в разделе исходных или результирующих данных означает, что соответствующий элемент данных является <i>указателем</i>, причем непустым (для пустого указателя используется слово <code><b>nil</b></code>). Определить, с каким элементом динамической структуры данных связан непустой указатель, можно по экранной информации об этой динамической структуре. Разумеется, при чтении указателя программа учащегося получит «настоящий» адрес, с помощью которого она сможет обратиться к исходной динамической структуре.</p> <p>Аналогично, создав (или преобразовав) некоторую динамическую структуру, программа учащегося должна передать задачнику некоторый адрес, связанный в этой структурой (используя процедуру вывода <code>write</code>). Зная этот адрес, задачник сможет проверить правильность созданной структуры.</p> <hr> <h3>Приступаем к решению</h3> <p>Вернемся к заданию Dynamic2. В нем не требуется ни создавать, ни преобразовывать исходную структуру данных; ее необходимо лишь проанализировать, а именно, определить значения всех ее элементов, подсчитать количество элементов и, кроме того, вывести указатель на последний элемент этой структуры.</p> <p>Приведем вначале неполное решение задачи, выводящее все необходимые данные, кроме указателя на последний элемент:</p> <blockquote> <code><pre> <b>uses</b> PT4; <b>var</b> p1: PNode; n: integer; <b>begin</b> Task('Dynamic2'); read(p1); n := 0; <b>while</b> p1 <> nil <b>do</b> <b>begin</b> write(p1^.Data); n := n + 1; p1 := p1^.Next; <b>end</b>; write(n); <b>end</b>. </pre></code> </blockquote> <p>После запуска программы можно убедиться, что все числовые результирующие данные найдены правильно, однако из-за того, что не выведен указатель на последний элемент, решение признано ошибочным с диагностикой «<i>Выведены не все результирующие данные</i>»:</p> <blockquote> <img border="0" src="gif/Dynamic2-3.png"> </blockquote> <p>Добавим в конец программы оператор</p> <blockquote> <code><pre> write(p1); </pre></code> </blockquote> <p>После запуска нового варианта программы все требуемые данные будут выведены, однако результирующее значение указателя будет равно <code>nil</code>. Это связано с тем, что после завершения цикла <code><b>while</b></code> в переменной <code>p1</code> содержится <i>нулевой указатель</i>, а не указатель на последний элемент динамической структуры:</p> <blockquote> <img border="0" src="gif/Dynamic2-4.png"> </blockquote> <hr> <h3>Правильное решение</h3> <p>Для того чтобы получить правильное решение, опишем вспомогательную переменную <code>p2</code>, в которой будем сохранять адрес элемента, <i>предшествующего</i> элементу с адресом <code>p1</code>. После завершения цикла <code><b>while</b></code> в этой переменной будет храниться адрес последнего элемента динамической структуры:</p> <blockquote><code><pre> <b>uses</b> PT4; <b>var</b> p1,p2: PNode; n: integer; <b>begin</b> Task('Dynamic2'); read(p1); n := 0; <b>while</b> p1 <> nil <b>do</b> <b>begin</b> write(p1^.Data); n := n + 1; p2 := p1; { сохраняем адрес текущего элемента } p1 := p1^.Next; { и переходим к следующему элементу } <b>end</b>; write(n, p2); <b>end</b>. </pre></code></blockquote> <p>Запустив эту программу три раза, мы получим сообщение «<i>Задание выполнено!</i>»:</p> <blockquote> <img border="0" src="gif/Dynamic2-5.png"> </blockquote> <hr> <H2>Пример 2. Добавление элемента к динамической структуре</H2> <hr> <h3>Знакомство с заданием</h3> <p>Рассмотрим простейшее задание, связанное с добавлением элемента к динамической структуре-стеку: Dynamic3.</p> <p>При ознакомительном запуске этого задания мы обнаружим новое обозначение в тексте, описывающем результирующий стек, а именно, точки, обрамляющие первый элемент стека:</p> <blockquote> <img border="0" src="gif/Dynamic3-1.png"> </blockquote> <p>Точки обозначают элементы динамической структуры, память для которых <i>должна быть выделена программой учащегося</i> (в отличие от тех элементов, которые размещаются в памяти самим задачником).</p> <hr> <h3>Приступаем к решению</h3> <p>Что произойдет, если динамическая структура будет создана с ошибками? Для того чтобы это выяснить, вернем в программе, решающей задание Dynamic3, указатель на прежнюю вершину стека, не добавляя к ней новый элемент:</p> <blockquote><code><pre> <b>uses</b> PT4; <b>var</b> d: integer; p1: PNode; <b>begin</b> Task('Dynamic3'); read(d, p1); write(p1); <b>end</b>. </pre></code></blockquote> <p>После запуска данной программы окно задачника примет вид:</p> <blockquote> <img border="0" src="gif/Dynamic3-2.png"> </blockquote> <p>Скобки вокруг каждого элемента результирующего стека означают, что эти элементы созданы самим задачником, но <i>располагаются не на тех позициях, на которых они должны находиться при правильном решении</i>. Действительно, тот элемент, который в решении является первым, должен (после добавления нового элемента) оказаться вторым и т. д. Итак, наличие скобок в тексте результирующей динамической структуры означает, что ее элементы располагаются не в том порядке, который требуется.</p> <hr> <h3>Правильное решение</h3> <p>Для получения правильного решения задания Dynamic3 необходимо явно выделить память для нового элемента, используя процедуру <code>New</code>, и заполнить поля этого элемента, связав его с текущей вершиной стека (в результате сам этот элемент станет новой вершиной, адрес которой и следует вывести):</p> <blockquote><code><pre> <b>uses</b> PT4; <b>var</b> d: integer; p1, p2: PNode; <b>begin</b> Task('Dynamic3'); read(d, p1); New(p2); p2^.Data := D; p2^.Next := p1; write(p2); <b>end</b>. </pre></code></blockquote> <p>Приведем вид окна задачника при первом запуске этой программы:</p> <blockquote> <img border="0" src="gif/Dynamic3-3.png"> </blockquote> <hr> <H2>Пример 3. Удаление элемента из динамической структуры</H2> <hr> <h3>Знакомство с заданием</h3> <p>Рассмотрим простейшее задание на удаление элемента из динамической структуры — Dynamic5. В нем требуется удалить из стека вершину и вернуть указатель на новую вершину, то есть на элемент, расположенный непосредственно за удаленным.</p> <p>Особенность заданий на удаление элементов из динамических структур заключается в том, что удаляемый элемент необходимо не только «отсоединить» от исходной динамической структуры, но и полностью «уничтожить», то есть <i>освободить память, занимаемую этим элементом</i>.</p> <p>Для того чтобы напомнить учащемуся о необходимости уничтожения некоторых элементов исходной динамической структуры, эти элементы выделяются на экране синим цветом меньшей яркости, чем обычные элементы (на рисунке таким способом выделен элемент 15):</p> <blockquote> <img border="0" src="gif/Dynamic5-1.png"> </blockquote> <hr> <h3>Приступаем к решению</h3> <p>Вначале приведем неправильный вариант решения, в котором не освобождается память, занимаемая удаленным из стека элементом:</p> <blockquote><code><pre> <b>uses</b> PT4; <b>var</b> p1: PNode; <b>begin</b> Task('Dynamic5'); read(p1); write(p1^.Data, p1^.Next); <b>end</b>. </pre></code></blockquote> <p>Несмотря на то что все результирующие данные будут совпадать с контрольными (то есть текст в разделах «Полученные результаты» и «Пример верного решения» будет одинаковым), на информационной панели появится сообщение об ошибке «<i>Не освобождена динамическая память</i>», а в разделе исходных данных будет выделен красным цветом тот элемент, который требовалось удалить:</p> <blockquote> <img border="0" src="gif/Dynamic5-2.png"> </blockquote> <hr> <h3>Правильное решение</h3> <p>Для получения правильного решения достаточно добавить в конец программы оператор вызова процедуры <code>Dispose</code>, освобождающий память, на которую указывает указатель <code>p1</code>:</p> <blockquote><code><pre> <b>uses</b> PT4; <b>var</b> p1: PNode; <b>begin</b> Task('Dynamic5'); read(p1); write(p1^.Data, p1^.Next); Dispose(p1); <b>end</b>. </pre></code></blockquote> <p>Приведем вид окна задачника при первом запуске этой программы:</p> <blockquote> <img border="0" src="gif/Dynamic5-3.png"> </blockquote> <hr> <H2>Пример 4. Двусвязные динамические структуры</H2> <hr> <h3>Знакомство с заданием</h3> <p>Особенности работы с двусвязными динамическими структурами рассмотрим на примере задания Dynamic30, в котором требуется преобразовать исходную односвязную структуру в двусвязную. Запустив программу-заготовку, созданную для этого задания, мы увидим в области исходных данных информацию об «обычной» односвязной структуре, подобной рассмотренным в предыдущих примерах:</p> <blockquote> <img border="0" src="gif/Dynamic30-1.png"> </blockquote> <p>Динамическая структура, приведенная в разделе результатов, имеет две особенности: во-первых, ее элементы связаны символом <code>=</code>, а во-вторых, перед первым элементом присутствует текст <code>nil<</code>.</p> <p>Это означает, что результирующая структура является <i>двусвязной</i>, то есть каждый ее элемент связан не только с последующим элементом (с помощью поля <code>Next</code>, как в односвязной структуре), но и с предыдущим элементом (с помощью нового поля <code>Prev</code>), а поле <code>Prev</code> первого элемента имеет значение <code>nil</code>:</p> <blockquote> <img border="0" src="gif/Dynamic30-2.png"> </blockquote> <hr> <h3>Приступаем к решению</h3> <p>Для преобразования исходной односвязной структуры в двусвязную необходимо задать правильные значения для полей <code>Prev</code> всех элементов структуры, перебирая в цикле пары соседних элементов:</p> <blockquote><code><pre> <b>uses</b> PT4; <b>var</b> p1, p: PNode; <b>begin</b> Task('Dynamic30'); read(p1); p := p1^.Next; <b>while</b> p <> nil <b>do</b> <b>begin</b> p^.Prev := p1; p1 := p1^.Next; p := p^.Next; <b>end</b>; write(p1); <i>{ вывод указателя на последний элемент }</i> <b>end</b>. </pre></code></blockquote> <p>В этой программе мы определили поля <code>Prev</code> для всех элементов, кроме первого. Поэтому решение будет считаться ошибочным (обратите внимание на то, что перед первым элементом полученного списка отсутствует текст <code>nil<</code>):</p> <blockquote> <img border="0" src="gif/Dynamic30-3.png"> </blockquote> <p><b>Замечание.</b> При анализе ошибочного решения часто оказывается полезным и специальное обозначение «<code>=</code>» для двойной связи. Предположим, например, что информация о результирующей двусвязной структуре, созданной программой, имеет вид:</p> <blockquote><code><pre> P<sub>2</sub> nil< 33 = 64 - 78 = 12 = 51 >nil </pre></code></blockquote> <p>Это означает, что между вторым и третьим элементом структуры имеется не двойная, а <i>одинарная</i> связь (поле <code>Next</code> второго элемента содержит адрес третьего элемента, а поле <code>Prev</code> третьего элемента <i>не содержит</i> адрес второго).</p> <hr> <h3>Правильное решение</h3> <p>Для получения правильного решения достаточно добавить в программу перед циклом <code>while</code> следующий оператор:</p> <blockquote><code><pre> p1^.Prev := nil; </pre></code></blockquote> <p>Приведем вид окна задачника при первом запуске исправленной программы:</p> <blockquote> <img border="0" src="gif/Dynamic30-4.png"> </blockquote> <p><b>Замечание.</b> Для задания Dynamic30 возможен более короткий вариант решения, в котором не требуется особо обрабатывать первый элемент списка: </p> <blockquote><code><pre> <b>uses</b> PT4; <b>var</b> p1, p: PNode; <b>begin</b> Task('Dynamic30'); p := nil; read(p1); <b>while</b> p1 <> nil <b>do</b> <b>begin</b> p1^.Prev := p; p := p1; p1 := p1^.Next; <b>end</b>; write(p); <b>end</b>. </pre></code></blockquote> <hr> <H2>Пример 5. Циклические динамические структуры</H2> <hr> <h3>Знакомство с заданием</h3> <p>Динамическая структура называется <i>циклической</i>, если она замкнута в «кольцо», то есть ее последний элемент связан полем <code>Next</code> с первым (в случае двусвязной структуры требуется также, чтобы ее первый элемент был связан полем <code>Prev</code> с последним элементом). Простейшим заданием на циклические структуры является Dynamic55, в котором требуется преобразовать обычный двусвязный список в циклический.</p> <p>Запустив программу-заготовку для этого задания, мы увидим на экране изображение двух динамических структур, причем исходная структура является «обычным» двусвязным списком, а результирующая структура — циклическим двусвязным списком:</p> <blockquote> <img border="0" src="gif/Dynamic55-1.png"> </blockquote> <p>Обозначения <code><< =</code> и <code>= >></code> позволяют отличить циклический список от обычного (напомним, что у обычного двусвязного списка поле <code>Prev</code> первого элемента и поле <code>Next</code> последнего элемента равны <code><b>nil</b></code>).</p> <p>Таким образом, экранный текст, описывающий циклический двусвязный список, является упрощенным вариантом следующей схемы:</p> <blockquote> <img border="0" src="gif/Dynamic55-2.png"> </blockquote> <hr> <h3>Приступаем к решению</h3> <p>Для решения задания Dynamic55 достаточно найти последний элемент исходного списка и связать его с первым элементом:</p> <blockquote><code><pre> <b>uses</b> PT4; <b>var</b> p1, p2: PNode; <b>begin</b> Task('Dynamic55'); read(p1); p2 := p1; <b>while</b> p2^.Next <> <b>nil</b> <b>do</b> p2 := p2^.Next; p2^.Next := p1; write(p2); <b>end</b>. </pre></code></blockquote> <p>В данном варианте решения мы «забыли» о том, что надо связать не только последний элемент с первым, но и первый с последним (поскольку наш список — двусвязный). Поэтому решение оказалось ошибочным (обратите внимание на то, что после последнего элемента полученного списка изображена одинарная, а не двойная черта):</p> <blockquote> <img border="0" src="gif/Dynamic55-3.png"> </blockquote> <hr> <h3>Правильное решение</h3> <p>Для получения правильного решения достаточно добавить в программу перед процедурой вывода <code>write</code> следующий оператор:</p> <blockquote><code><pre> p1^.Prev := p2; </pre></code></blockquote> <p>Приведем вид окна задачника при первом запуске исправленной программы:</p> <blockquote> <img border="0" src="gif/Dynamic55-4.png"> </blockquote> <hr> <h3>Просмотр результатов выполнения заданий</h3> <p>Щелкнув мышью на метке «Результаты (F2)», расположенной в правом верхнем углу окна задачника, или нажав клавишу <b>F2</b>, мы можем вывести на экран <i>окно результатов</i>, в котором будет перечислены все наши попытки решения задачи:</p> <blockquote><code><pre> 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 Ознакомительный запуск. Dynamic3 a08/09 13:24 Ошибочное решение. Dynamic3 a08/09 13:28 Задание выполнено! Dynamic5 a08/09 13:29 Ознакомительный запуск. Dynamic5 a08/09 13:30 Не освобождена динамическая память. Dynamic5 a08/09 13:31 Задание выполнено! Dynamic30 a08/09 13:34 Ознакомительный запуск. Dynamic30 a08/09 13:42 Ошибочное решение. Dynamic30 a08/09 13:43 Задание выполнено! Dynamic55 a08/09 13:54 Ознакомительный запуск. Dynamic55 a08/09 13:57 Ошибочное решение. Dynamic55 a08/09 13:58 Задание выполнено! </pre></code></blockquote> <p>Для закрытия окна результатов достаточно нажать клавишу <b>Esc</b>. Окно результатов можно отобразить на экране и после закрытия окна задачника и возврата в среду PascalABC.NET. Для этого надо использовать команду меню «Модули | Просмотреть результаты», кнопку <img border="0" src="gif/Results.gif" width="16" height="17"> или клавиатурную комбинацию <b>Shift+Ctrl+R</b>. </p> </body> </html>