710 lines
43 KiB
HTML
710 lines
43 KiB
HTML
<html>
|
||
|
||
<head>
|
||
<object type="application/x-oleobject" classid="clsid:1e2a7bd0-dab9-11d0-b93a-00c04fc99f9e">
|
||
<param name="Keyword" value="">
|
||
</object>
|
||
<meta http-equiv="Content-Type" content="text/html; charset=windows-1251">
|
||
<title></title>
|
||
<link rel="StyleSheet" href="../../default.css">
|
||
</head>
|
||
|
||
<body>
|
||
<H1>Модуль PT4TaskMakerNET: дополнительные компоненты</H1>
|
||
<hr>
|
||
|
||
<p>Если процедура имеет необязательные параметры, то
|
||
в списке параметров они заключаются в квадратные скобки.
|
||
</p>
|
||
|
||
<a name="File"></a><h2>Процедуры для включения в задание файлов</h2>
|
||
|
||
<p>В конструкторе учебных заданий PT4TaskMaker предусмотрена возможность включения в каждое учебное задание (в
|
||
качестве исходных или результирующих данных) до 10 файлов. Кроме текстовых
|
||
файлов в заданиях можно использовать
|
||
двоичные файлы, все элементы которых имеют один и тот же тип (целочисленный, вещественный, символьный, строковый).
|
||
Каждый файл должен содержать не более 999 элементов (для текстовых файлов элементами считаются файловые строки);
|
||
в случае, если файл содержит более 999 элементов, элементы с номерами, превышающими 999, в окне задачника не отображаются.
|
||
Для корректного
|
||
отображения на экране, а также для правильной проверки результирующих файлов
|
||
необходимо, чтобы строки в двоичных строковых и текстовых файлах
|
||
и text состояли из не более чем 70 символов.</p>
|
||
<p>Все процедуры, связанные с определением файловых данных, следует вызывать после
|
||
вызова процедуры <a href="tmaker_proc1.html#CreateTask">CreateTask</a>.</p>
|
||
<p>Файлы должны создаваться в текущем каталоге, поэтому при задании их имен не следует указывать имя диска и путь.
|
||
Рекомендуется снабжать имена всех файлов,
|
||
используемых в заданиях, расширением .tst.
|
||
</p>
|
||
<p>Все данные из файла, как правило, нельзя одновременно отобразить в окне задачника, поэтому для файловых
|
||
элементов предусмотрена возможность <i>прокрутки</i>. Для двоичных файлов прокрутка
|
||
выполняется в горизонтальном направлении, а для текстовых файлов — в вертикальном.
|
||
</p>
|
||
<a name="DataFile"></a><hr noshade size="1">
|
||
<pre><b>procedure</b> DataFileN(FileName: string; Y, W: integer);
|
||
<b>procedure</b> DataFileR(FileName: string; Y, W: integer);
|
||
<b>procedure</b> DataFileC(FileName: string; Y, W: integer);
|
||
<b>procedure</b> DataFileS(FileName: string; Y, W: integer);
|
||
<b>procedure</b> DataFileT(FileName: string; Y1, Y2: integer);
|
||
</pre>
|
||
<p>Процедуры группы DataFile с именами, завершающимися символами N, R, C, S, позволяют включить в задание в качестве
|
||
исходного файла один двоичный файл с элементами целочисленного, вещественного, символьного и строкового типа
|
||
соответственно. Процедура DataFileT позволяет включить в задание в качестве исходного файла один текстовый файл.
|
||
К моменту вызова процедуры файл, включаемый в
|
||
задание, должен быть создан, заполнен исходными данными и закрыт. Имя этого
|
||
файла передается параметром FileName. </p>
|
||
<p>Два последних параметра имеют разный смысл для процедур, обрабатывающих
|
||
двоичные файлы, и для процедуры DataFileT, обрабатывающей
|
||
текстовые файлы. Для процедур, связанных с двоичными файлами, параметр
|
||
Y указывает номер экранной строки в области исходных данных, в
|
||
которой будут отображаться элементы данного файла, а параметр W
|
||
указывает количество позиций, отводимых под отображение <i>одного</i> элемента файла.
|
||
Если фактическая длина элемента файла оказывается меньше параметра W,
|
||
то изображение элемента дополняется пробелами (пробелы добавляются слева для числовых данных
|
||
и справа для символьных); если длина элемента файла
|
||
окажется больше значения W, то в конце поля, выделенного для его
|
||
вывода, будет указан символ «*» (звездочка) красного цвета.
|
||
При определении
|
||
параметра W необходимо предусматривать дополнительные позиции для пробелов,
|
||
служащих разделителями элементов, а в случае строковых и символьных
|
||
файлов — для апострофов, автоматически добавляемых к каждому элементу при его
|
||
отображении на экране. Способ отображения вещественных чисел устанавливается,
|
||
как и для обычных исходных данных, процедурой <a href="tmaker_proc1.html#SetPrecision">SetPrecision</a>;
|
||
по умолчанию вещественные числа отображаются в формате с фиксированной
|
||
точкой и двумя знаками в дробной части. Количество элементов, отображаемых на
|
||
экране, определяется автоматически так, чтобы заполнить по возможности всю
|
||
экранную строку. Никакие другие исходные данные на этой
|
||
строке размещать нельзя.</p>
|
||
<p>Для процедуры DataFileT параметры Y1
|
||
и Y2 определяют соответственно номер первой и последней экранной
|
||
строки той части области исходных данных, которая отводится под отображение
|
||
текстового файла. На каждой экранной строке размещается одна строка из
|
||
текстового файла.</p>
|
||
<p>Параметры Y, Y1, Y2 должны принимать
|
||
значения от 1 до 5 (Y и Y1 могут также принимать
|
||
значение 0; этот случай описан в конце данного раздела); значение Y1
|
||
не должно превышать значение Y2. Параметр W должен лежать в
|
||
диапазоне 1–72.</p>
|
||
<p>При наличии нескольких исходных файлов вызов соответствующих процедур группы
|
||
DataFile может проводиться в любом порядке, независимо от порядка
|
||
расположения этих файлов на экране. При попытке размещения двух файлов на одной
|
||
экранной строке выводится сообщение об ошибке. Вызовы процедур группы DataFile
|
||
могут проводиться как до, так и после вызовов процедур группы
|
||
Data, определяющих «обычные», не файловые исходные данные.</p>
|
||
<p>Вызов процедур группы DataFile не влияет на содержимое
|
||
включаемых в задание файлов. Он лишь приводит к копированию этого содержимого в
|
||
специальный буфер в оперативной памяти. Созданная копия используется для
|
||
отображения содержимого файла на экране; это позволяет просматривать начальное
|
||
содержимое исходного файла и после его преобразования (или даже удаления) в
|
||
ходе решения задания.</p>
|
||
<p>Поскольку при различных тестовых испытаниях учебного задания желательно не
|
||
только изменять содержимое исходных файлов, но также и предлагать для обработки
|
||
файлы с различными именами, возникает опасность «засорения» диска файлами,
|
||
созданными при предыдущих при предыдущих тестовых испытаниях. Для того чтобы этого не
|
||
произошло, в задачнике предусмотрено автоматическое удаление при завершении
|
||
тестового испытания всех файлов, включенных в задание с помощью процедур группы
|
||
DataFile. Заметим, что это удаление производится и в случае
|
||
аварийного завершения программы, выполняющей учебное задание. Если же исходный
|
||
файл был удален самой программой, выполняющей задание, то задачник не будет
|
||
пытаться удалить этот файл еще раз.</p>
|
||
<p>Иногда (хотя и весьма редко — см., например, задание File4) при решении задания не требуется отображать
|
||
содержимое исходного файла на экране. В этом случае в соответствующей процедуре
|
||
группы DataFile параметр Y или Y1
|
||
надо положить равным 0. Если исходный файл не требуется ни отображать на экране,
|
||
ни удалять после завершения тестового испытания, то в вызове процедуры группы DataFile
|
||
нет необходимости.</p>
|
||
<p>Следует заметить, что формат <i>двоичных строковых файлов</i> является различным для разных
|
||
языков программирования. В конструкторе предполагается, что подготовленный для включения в задание
|
||
двоичный строковый файл имеет формат языка Pascal; в дальнейшем сам задачник выполняет автоматическое
|
||
преобразование данного файла к формату того языка, на котором выполняется задание.
|
||
При реализации задания в конструкторе для среды PascalABC.NET
|
||
достаточно описать двоичный строковый файл как file of ShortString.
|
||
</p>
|
||
<p>Пример реализации
|
||
задания на обработку двоичных строковых файлов для различных языков программирования приводится в разделе
|
||
«<a href="tmaker_samples.html">Примеры</a>».
|
||
</p>
|
||
|
||
<a name="ResultFile"></a><hr noshade size="1">
|
||
<pre><b>procedure</b> ResultFileN(FileName: string; Y, W: integer);
|
||
<b>procedure</b> ResultFileR(FileName: string; Y, W: integer);
|
||
<b>procedure</b> ResultFileC(FileName: string; Y, W: integer);
|
||
<b>procedure</b> ResultFileS(FileName: string; Y, W: integer);
|
||
<b>procedure</b> ResultFileT(FileName: string; Y1, Y2: integer);
|
||
</pre>
|
||
<p>Процедуры группы ResultFile с именами, завершающимися символами N, R, C,
|
||
S, позволяют включить в задание в качестве
|
||
результирующего файла
|
||
один двоичный файл с элементами целочисленного, вещественного, символьного и строкового типа
|
||
соответственно. Процедура ResultFileT позволяет включить в задание в качестве результирующего
|
||
файла один текстовый файл.
|
||
К моменту вызова процедуры файл, включаемый в
|
||
задание, должен быть создан, заполнен контрольными данными и закрыт. Под
|
||
контрольными данными понимаются, как обычно, данные, которые должны содержаться
|
||
в результирующем файле в случае правильного решения задания.</p>
|
||
<p>Смысл параметров процедур группы ResultFile совпадает со смыслом
|
||
соответствующих параметров процедур группы DataFile, за исключением
|
||
того, что теперь номера экранных строк Y, Y1, Y2
|
||
относятся к области результирующих данных. Ограничения на параметры для процедур
|
||
группы ResultFile накладываются те же, что и для процедур группы
|
||
DataFile.</p>
|
||
<p>В результате выполнения процедуры из группы ResultFile
|
||
содержимое указанного контрольного файла будет скопировано в специальный буфер в
|
||
оперативной памяти, после чего контрольный файл будет <i>автоматически удален с
|
||
диска</i>. В дальнейшем, при выполнении задания, файл с таким же именем должен быть
|
||
создан и заполнен требуемыми данными программой самого учащегося. Контрольные
|
||
данные, записанные в оперативную память процедурой из группы ResultFile,
|
||
используются при проверке правильности содержимого результирующего файла (созданного
|
||
в ходе выполнения задания). Кроме того, эти контрольные данные могут выводиться
|
||
на экран в качестве примера правильного решения. Имя файла и другие параметры,
|
||
указанные в процедуре ResultFile, будут также использоваться для
|
||
поиска и отображения на экране результирующего файла, созданного при выполнении
|
||
задания. Все результирующие файлы, созданные в ходе решения задания,
|
||
автоматически удаляются с диска при завершении программы. Подобное удаление производится и при аварийном завершении
|
||
программы; если же результирующий файл не создан, то попытка его удалить не
|
||
производится.</p>
|
||
<p>Как и в случае процедур группы DataFile, отображение некоторых
|
||
результирующих файлов можно отключить, положив в соответствующих процедурах
|
||
ResultFile значения параметров Y или
|
||
Y1 равными 0 (см., например, задание File1). Это, естественно, не отменит сравнения содержимого
|
||
результирующих файлов с контрольными данными и удаления результирующих файлов
|
||
при завершении программы. </p>
|
||
<p>При определении <i>двоичных строковых</i> файлов результатов необходимо следовать тем же
|
||
правилам, что и при определении исходных двоичных строковых файлов (см. завершающую часть
|
||
описания процедур <a href="#DataFile">группы DataFile</a>).
|
||
</p>
|
||
|
||
<a name="Dynamic"></a><h2>Процедуры для включения в задание указателей и динамических структур данных</h2>
|
||
|
||
<p>В учебные задания можно включать указатели только одного определенного в
|
||
задачнике типа:</p>
|
||
<hr noshade size="1">
|
||
<pre><b>type</b>
|
||
PNode = ^TNode;
|
||
TNode = <b>record</b>
|
||
Data : integer;
|
||
Next : PNode;
|
||
Prev : PNode;
|
||
Left: PNode;
|
||
Right: PNode;
|
||
Parent: PNode;
|
||
<b>end</b>;
|
||
</pre>
|
||
<p>Этот тип позволяет формировать одно- и двусвязные линейные динамические структуры
|
||
(при этом используются поля связи Next и Prev), бинарные деревья и деревья общего вида (при этом используются поля связи Left и Right),
|
||
а также бинарные деревья с обратной связью (при этом используются поля связи Left, Right и Parent).
|
||
Поскольку значение адреса, хранящегося в указателе, не представляет интереса (и, кроме того,
|
||
может изменяться при каждом тестовом запуске программы), на экране отображается
|
||
не оно, а условное обозначение указателя «ptr», снабженное <i>обязательным</i>
|
||
комментарием, например, <code>P<sub>1</sub> = ptr</code>, <code>P<sub>X</sub> = ptr</code> и т. д.
|
||
В задании можно использовать до 36 различных указателей, которым присваиваются номера от
|
||
0 до 35. Указатели с номерами от 0 до 9 имеют комментарии с цифровым индексом
|
||
(P<sub>0</sub>–P<sub>9</sub>), а указатели с номерами от 10 до 35 — с буквенным
|
||
(P<sub>A</sub>–P<sub>Z</sub>).
|
||
Если некоторый указатель имеет нулевое значение, то вместо текста «ptr» отображается
|
||
текст «nil» (или аналогичный текст с обозначением нулевого указателя, соответствующего текущему
|
||
языку программирования), например, <code>P<sub>1</sub> = nil</code> для языка Pascal,
|
||
<code>P<sub>1</sub> = NULL</code> для языка C++. Комментарии к указателям также
|
||
используются при отображении на экране динамических структур, если они содержат элементы,
|
||
с которыми связаны данные указатели.
|
||
</p>
|
||
|
||
<a name="SetPointer"></a><hr noshade size="1">
|
||
<pre><b>procedure</b> SetPointer(NP: integer; P: PNode);
|
||
</pre>
|
||
<p>Эта процедура позволяет определить в учебном задании указатель с номером
|
||
NP (значение этого указателя при инициализации задания будет равно P,
|
||
однако при <i>выполнении</i> задания оно может измениться). Все прочие процедуры,
|
||
связанные с этим указателем и описываемые далее, используют не его конкретное значение, а номер
|
||
NP.</p>
|
||
<p>Номер NP должен лежать в диапазоне от 0 до 35; он указывается в обязательном
|
||
комментарии к данному указателю (см. выше). Если процедура SetPointer
|
||
для указателя с номером NP не вызвана, то указатель с этим номером будет иметь нулевое значение.</p>
|
||
|
||
<a name="DataP"></a><a name="ResultP"></a><hr noshade size="1">
|
||
<pre><b>procedure</b> DataP(<b>[</b>Cmt: string;<b>]</b> NP: integer; X, Y: integer);
|
||
<b>procedure</b> ResultP(<b>[</b>Cmt: string;<b>]</b> NP: integer; X, Y: integer);
|
||
</pre>
|
||
<p>Процедуры DataP и ResultP помещают указатель с номером NP в список исходных или,
|
||
соответственно, результирующих данных учебного задания и отображают его на
|
||
экране. При отображении на экране указатель снабжается обязательным комментарием
|
||
вида P<sub>#</sub> =, где в качестве символа # указывается символ, связываемый
|
||
с указателем (для NP от 0 до 9 — соответствующая цифра, для NP от 10 до 35 —
|
||
заглавная латинская буква от A до Z). Само значение указателя на экран не выводится;
|
||
вместо него указывается одно из двух условных обозначений: ptr для
|
||
ненулевого указателя и nil для нулевого указателя. Как и прочие
|
||
элементы данных, указатель может снабжаться дополнительным комментарием Cmt,
|
||
который приписывается слева к обязательному (например, вызов
|
||
процедуры с параметрами Cmt = 'Адрес начала стека: ' и NP = 6
|
||
приведет к выводу на экран следующей строки: <code>Адрес начала стека: P<sub>6</sub> = ptr</code>).
|
||
В дополнительном комментарии Cmt можно использовать <a href="tmaker_format.html"><i>управляющие последовательности</i></a>.
|
||
В процедурах DataP и ResultP задается также экранная позиция, начиная с
|
||
которой элемент данных выводится в соответствующую экранную область. Параметр Y
|
||
определяет номер строки (от 1 до 5), параметр X — позицию в строке (от 1 до 78;
|
||
как обычно, требуется, чтобы элемент данных вместе с комментарием полностью
|
||
умещался на строке).</p>
|
||
<p>Варианты данных процедур, в которых параметр Cmt отсутствует, добавлены в версию 4.11 конструктора.
|
||
</p>
|
||
|
||
|
||
<a name="DataList"></a><hr noshade size="1">
|
||
<pre><b>procedure</b> DataList(NP: integer; X, Y: integer);
|
||
<b>procedure</b> ResultList(NP: integer; X, Y: integer);
|
||
</pre>
|
||
<p>Процедуры DataList и ResultList предназначены для помещения структуры типа «одно- или двусвязный линейный динамический
|
||
список» в набор исходных или, соответственно, результирующих данных, а также для
|
||
вывода этой структуры на экран. Параметр NP задает номер указателя (предварительно
|
||
определенный процедурой <a href="#SetPointer">SetPointer</a>), который указывает на <i>начало</i>
|
||
данного списка, т. е. на его первый элемент. Если соответствующий указатель
|
||
является нулевым, то список считается пустым. Пустой список на экране не отображается.</p>
|
||
<p>
|
||
Непустой динамический список отображается на двух
|
||
экранных строках; первая строка содержит имена указателей, входящих в задание и
|
||
связанных с данным списком (они задаются процедурой <a href="#ShowPointer">ShowPointer</a>),
|
||
во второй строке — значения элементов списка (точнее, их полей Data целого типа)
|
||
и виды связи между элементами.</p>
|
||
<p>Если память для элемента результирующего списка должна быть выделена программой учащегося,
|
||
то значение его поля Data на экране обрамляется точками (например, <code>.23.</code>).
|
||
Если в исходной динамической структуре требуется разрушить один или несколько элементов, то эти элементы выделяются более бледным цветом,
|
||
а в случае, если программа учащегося не освободит память, занимаемую этими элементами, они будут выделены красным цветом.
|
||
Наконец, если в списке, преобразованном программой учащегося, элементы располагаются не на требуемых местах,
|
||
то они заключаются в скобки (например, <code>(23)</code>), а если элемент списка содержит ошибочную ссылку Next, то она помечается
|
||
двумя красными звездочками (например <code>46 - <font color="red">**</font></code>). Красные звездочки указываются в конце списка также в случае, если
|
||
его длина превышает максимально допустимую.
|
||
Специальные обозначения используются также для <i>циклических списков</i> (см. <a href="#Example3">пример 3</a>).</p>
|
||
<p>
|
||
Элемент данных типа «линейный список» должен содержать не более 14 элементов типа TNode,
|
||
причем значения их полей Data должны лежать в диапазоне от –9 до 99, поскольку для каждого поля Data
|
||
отводится по <i>две</i> экранные позиции. Для большей наглядности рекомендуется использовать числа из диапазона 10–99,
|
||
резервируя однозначные и отрицательные числа для особых элементов (например, барьерного элемента циклического списка —
|
||
см. задание Dynamic70).
|
||
Если значение элемента списка не умещается в поле вывода, то в его последней экранной позиции выводится
|
||
красная звездочка — признак ошибки.
|
||
</p>
|
||
<p>
|
||
Для отображения списка как двусвязного необходимо, чтобы в его элементах были определены поля связи Next и Prev;
|
||
в этом случае связи между соседними элементами списка обозначаются двойными линиями: «<code>=</code>». Если в задании
|
||
требуется использовать односвязный список, то для его элементов надо определить поле связи Next, а для полей Prev
|
||
следует указать значение, <i>не связанное</i> с
|
||
элементами этого списка (например, адрес какой-либо глобальной переменной типа TNode).
|
||
Связи между элементами односвязных списков обозначаются одинарными линиями: «<code>-</code>».
|
||
</p>
|
||
<p>Вызов процедуры DataList или ResultList
|
||
приводит к тому, что соответствующий список становится <i>текущей динамической структурой</i>
|
||
для данного задания. Все последующие вызовы процедур <a href="#ShowPointer">ShowPointer</a>,
|
||
<a href="#SetNewNode">SetNewNode</a> и <a href="#SetDisposedNode">SetDisposedNode</a> будут влиять на
|
||
эту текущую структуру.
|
||
</p>
|
||
|
||
<hr noshade size="1">
|
||
<pre><b>procedure</b> DataBinTree(NP, X, Y1, Y2: integer);
|
||
<b>procedure</b> ResultBinTree(NP, X, Y1, Y2: integer);
|
||
<b>procedure</b> DataTree(NP, X, Y1, Y2: integer);
|
||
<b>procedure</b> ResultTree(NP, X, Y1, Y2: integer);
|
||
</pre>
|
||
<p>Эти процедуры предназначены для включения в задание <i>бинарных деревьев</i> и <a href="#Tree"><i>деревьев общего вида</i></a>
|
||
(называемых также <i>деревьями с произвольным ветвлением</i>) в качестве исходных (DataBinTree и DataTree)
|
||
или результирующих (ResultBinTree и ResultTree) данных. Для деревьев общего вида используется
|
||
представление «левая дочерняя вершина — правая сестра» («left child — right sibling»).
|
||
Как и для процедур DataList и ResultList, описанных выше,
|
||
первым параметром этих процедур является <i>номер</i> указателя типа PNode, ранее определенного с помощью процедуры SetPointer.
|
||
В данном случае этот указатель должен указывать на <i>корень</i> добавляемого в задание дерева; если он является
|
||
нулевым указателем, то дерево считается пустым и не отображается на экране.
|
||
В отличие от процедур, связанных с линейными списками, для отображения дерева можно (и рекомендуется) выделять на экране <i>более двух строк</i>;
|
||
номера начальной и конечной экранной строки задаются параметрами Y1 и Y2 соответственно.
|
||
В отличие от других «прокручиваемых» данных (а именно типизированных и текстовых файлов),
|
||
дерево может не занимать выделенные для него строки по всей ширине: параметр X показывает, начиная с какой позиции экранных
|
||
строк будет отображаться дерево и связанная с ним информация. Следует отметить, что использовать для других целей можно
|
||
только <i>левую часть</i> строки, связанной с деревом; все позиции строки, начиная с позиции X, будут использоваться для отображения дерева.
|
||
</p>
|
||
<p>Вызов любой из описываемых процедур
|
||
приводит к тому, что соответствующее дерево становится <i>текущей динамической структурой</i>
|
||
для данного задания. Все последующие вызовы процедур <a href="#ShowPointer">ShowPointer</a>,
|
||
<a href="#SetNewNode">SetNewNode</a> и <a href="#SetDisposedNode">SetDisposedNode</a> будут влиять на
|
||
эту текущую структуру.
|
||
</p>
|
||
<p>При отображении дерева используются обозначения, аналогичные тем, которые применяются при отображении линейных динамических структур.
|
||
В частности, в качестве вершины изображается значение ее поля Data, причем для вывода этого значения выделяются две экранные позиции
|
||
(если двух позиций недостаточно, например, в случае значения 234, то на второй из выделенных позиций изображается красная звездочка:
|
||
<code>2<font color="red">*</font></code>).
|
||
В качестве обозначения связей между вершинами используются одинарные и двойные линии («<code>-</code>» и «<code>=</code>»);
|
||
двойные линии, как и для линейных списков, означают,
|
||
что связь между вершинами является двусторонней (так называемые <i>деревья с обратной связью</i> — см. <a href="#Example6">пример 6</a>).
|
||
Обратная связь обеспечивается полем Parent; ее можно использовать только для бинарных деревьев.
|
||
</p>
|
||
<a name="Tree"></a><p>Для деревьев предусмотрены два варианта отображения. Первый вариант предназначен для отображения
|
||
бинарного дерева; он применяется для деревьев, включенных в задание процедурами DataBinTree и ResultBinTree.
|
||
В этом варианте обе дочерние вершины располагаются ниже родительской вершины (на следующем уровне — см.
|
||
<a href="#Example5">примеры 5 и 6</a>).
|
||
Второй вариант предназначен для отображения <i>дерева общего вида</i> (вершины которого могут содержать более двух дочерних вершин);
|
||
он применяется для деревьев, включенных в задание процедурами DataTree
|
||
и ResultTree. В этом варианте вершина, определяемая полем Left вершины P, как обычно, располагается ниже и левее вершины P
|
||
и задает ее первую (левую) дочернюю вершину, а вершина, определяемая полем Right, моделирует
|
||
следующую вершину-«<i>сестру</i>» вершины P и поэтому располагается <i>на том же уровне</i>, что и вершина P.
|
||
Такой способ отображения деревьев позволяет, в частности, легко определить глубину дерева общего вида и номер уровня для любой его
|
||
вершины (см. <a href="#Example7">пример 7</a>).
|
||
</p>
|
||
<p>Перечислим другие обозначения, имеющие тот же смысл, что и для линейных структур:
|
||
</p>
|
||
<ul><li> если вершина дерева должна быть создана в программе учащегося, то данная вершина
|
||
выделяется слева и справа точками, например, <code>.23.</code> (для
|
||
этого используется процедура <a href="#SetNewNode">SetNewNode</a>);
|
||
<li> если в дереве, преобразованном программой учащегося, существующие вершины располагаются не на своих местах, то они заключаются в скобки:
|
||
<code>(23)</code>;
|
||
<li> если в исходном дереве требуется разрушить одну или несколько вершин, то эти вершины выделяются более бледным цветом
|
||
(а в случае, если программа учащегося не освободит память, занимаемую этими вершинами, они будут выделены красным цветом);
|
||
<li> если переход по ссылке Left или Right для данной вершины дерева невозможен,
|
||
то, как и в случае линейных структур, это отмечается красными звездочками, которые, однако, изображаются не рядом с данной вершиной,
|
||
а ниже вершины (что подчеркивает тот факт, что ошибка возникла при попытке перехода на следующий уровень дерева).
|
||
</ul>
|
||
<p>Для деревьев, в отличие от линейных структур, нулевые поля связи не отображаются. Если поле Left или Right
|
||
равно нулевому указателю, то на изображении дерева у соответствующей вершины просто отсутствует левая или правая связь.
|
||
</p>
|
||
<p>Максимальное число вершин в дереве равно 18; это объясняется тем, что каждая вершина занимает 4 позиции экранной строки и,
|
||
кроме того, 4 начальных позиции отводятся под дополнительную информацию (номера уровней дерева). Поэтому, с учетом того,
|
||
что ширина экранной строки равна 78, вписать в нее можно только дерево с не более чем 18 вершинами.
|
||
Впрочем, в заданиях рекомендуется использовать не более 16 вершин, начиная вывод дерева с 11 экранной позиции;
|
||
это дает возможность использовать левую часть строк для отображения других данных, например, указателей, связанных с данным деревом.
|
||
</p>
|
||
<p>Количество уровней дерева ограничивается только количеством его вершин и, таким образом, может достигать 18.
|
||
В соответствии с общепринятой практикой, уровни дерева нумеруются от 0. Номер уровня отображается в левой части области,
|
||
отведенной под изображение дерева; он выделяется цветом и отделяется от изображения дерева двоеточием.
|
||
</p>
|
||
<p>Если количество уровней превышает число экранных строк, выделенных для отображения дерева, то для дерева
|
||
становится возможной <i>прокрутка</i>, подобная прокрутке файловых данных
|
||
(точнее, данных из текстовых файлов, поскольку для деревьев, как и для текстовых файлов, прокрутка выполняется в вертикальном направлении).
|
||
На возможность прокрутки указывают дополнительные символы, которые изображаются слева от номера уровня.
|
||
Символ «стрелка вверх», расположенный на первой экранной строке, отведенной для отображения дерева,
|
||
означает, что изображение дерева можно пролистать вверх, а символ «стрелка вниз»,
|
||
расположенный на последней экранной строке, отведенной для отображения дерева, означает, что изображение дерева можно пролистать вниз
|
||
(см. <a href="#Example8">пример 8</a>). В режиме окна с динамической компоновкой
|
||
все деревья отображаются полностью, поэтому отдельная прокрутка для них не требуется.
|
||
</p>
|
||
<p>Обычно первая строка, отводимая под изображение дерева, содержит его корень и помечается слева числом 0 (нулевой уровень дерева).
|
||
Единственная ситуация, когда это правило нарушается, связана с ошибочным формированием бинарного дерева с обратной связью в случае,
|
||
если поле Parent корня не содержит значение nil. В этой ситуации перед строкой с изображением
|
||
корня дерева помещается еще одна строка, в которой над корнем изображается красная звездочка — признак ошибки.
|
||
</p>
|
||
<p>Изображение дерева может также содержать строки, расположенные ниже последнего уровня; эти строки могут потребоваться
|
||
для вывода имен указателей, связанных с вершинами-листьями, расположенными на последнем уровне,
|
||
а также для вывода звездочек, отмечающих ошибочные ссылки Left или Right для вершин,
|
||
расположенных на последнем уровне дерева. Заметим, что ссылка считается ошибочной в двух случаях:<p>
|
||
<ul><li>если она содержит неверный адрес,
|
||
<li>если она ссылается на вершину, которую нельзя отобразить, поскольку для этой вершины не предусмотрено экранного места.
|
||
</ul>
|
||
<p>В частности, звездочки обязательно будут выведены при попытке отобразить на экране дерево с количеством вершин, превышающим 18.
|
||
</p>
|
||
|
||
<p>
|
||
Приведем примеры изображений линейных списков и деревьев. В этих примерах предполагается, что
|
||
в качестве текущего языка задачника выбран язык Pascal;
|
||
для других языков вместо nil используются обозначения нулевых указателей
|
||
или <i>нулевых объектов</i> — (см. описание процедуры <a href="#SetObjectStyle">SetObjectStyle</a>), соответствующие этим языкам.</p>
|
||
<p><a name="Example1"></a><b>Пример 1</b>
|
||
</p>
|
||
<pre>P<sub>1</sub>
|
||
24 - 23 >nil
|
||
</pre>
|
||
<p>
|
||
Первый элемент данного списка связан с указателем P<sub>1</sub>;
|
||
список содержит два элемента и является <i>односвязным</i>: на это указывает символ «–»
|
||
между элементами, означающий, что поле Next первого элемента (со значением 24) указывает на второй элемент (со значением 23).
|
||
Поле Next второго элемента равно nil.
|
||
</p>
|
||
<p><a name="Example2"></a><b>Пример 2</b>
|
||
</p>
|
||
<pre> P<sub>1</sub> P<sub>2</sub>
|
||
nil< 14 = 23 = 34 >nil
|
||
</pre>
|
||
<p>
|
||
Данный список является двусвязным (двойная связь, использующая оба поля связи — Next и Prev, —
|
||
обозначается знаком «=»), причем в задании с этим списком связаны два указателя:
|
||
P<sub>1</sub> указывает на его первый, а P<sub>2</sub> — на его последний элемент.
|
||
</p>
|
||
<p><a name="Example3"></a><b>Пример 3</b>
|
||
</p>
|
||
<pre> P<sub>0</sub>
|
||
<< = 15 - 23 = 34 = >>
|
||
</pre>
|
||
<p>
|
||
Данный список является двусвязным <i>циклическим</i> списком (на его цикличность указывают символы
|
||
«<<» и «>>»), однако одна из его связей отсутствует.
|
||
А именно, элемент 23 (на который указывает указатель P<sub>0</sub>) не связан с предыдущим элементом 15,
|
||
т. е. поле Prev элемента 23 содержит ошибочное значение (например, равно nil).
|
||
При правильно разработанном задании подобная ситуация может возникнуть только для ошибочных списков, созданных
|
||
в программе учащегося.
|
||
Заметим, что связь в другом направлении (от 15 к 23) имеется, т. е. поле Next элемента 15 указывает на элемент 23.
|
||
</p>
|
||
<p><a name="Example4"></a><b>Пример 4</b>
|
||
</p>
|
||
<pre>P<sub>X</sub>P<sub>Y</sub>
|
||
95 - 63 -.34.- >>
|
||
</pre>
|
||
<p>
|
||
Данный список является односвязным циклическим списком. Он имеет две особенности.
|
||
Во-первых, на элемент 95 указывают сразу два указателя (P<sub>X</sub> и P<sub>Y</sub>),
|
||
и, во-вторых, элемент 34 должен быть размещен в памяти процедурой New при <i>выполнении</i> задания
|
||
(на это указывают обрамляющие его точки). Подобные элементы, естественно, могут содержаться только в <i>результирующих</i> списках.
|
||
Они определяются с помощью процедуры <a href="#SetNewNode">SetNewNode</a>.
|
||
</p>
|
||
|
||
<p><a name="Example5"></a><b>Пример 5</b>
|
||
</p>
|
||
<p><img border="0" src="images\pt4make1.png"></p>
|
||
<p>Так выглядит на экране бинарное дерево глубины 4. С корнем этого дерева (поле Data которого равно 96)
|
||
связан указатель P<sub>1</sub>.
|
||
</p>
|
||
<p><a name="Example6"></a><b>Пример 6</b>
|
||
</p>
|
||
<p><img border="0" src="images\pt4make2.png"></p>
|
||
<p>Так выглядит на экране бинарное дерево с обратной связью (номера уровней на данной иллюстрации не указаны).
|
||
</p>
|
||
<p><a name="Example7"></a><b>Пример 7</b>
|
||
</p>
|
||
<p><img border="0" src="images\pt4make3.png"></p>
|
||
<p>Так выглядит на экране дерево общего вида (номера уровней и имена связанных с деревом указателей на данной иллюстрации не указаны).
|
||
В данном случае корень дерева 13 имеет три непосредственных потомка: вершины 71, 73 и 29. Напомним, что в дереве общего вида
|
||
поле Left определяет первую (левую) дочернюю вершину, а поле Right — очередную (правую) вершину-<i>сестру</i>.
|
||
</p>
|
||
<p><a name="Example8"></a><b>Пример 8</b>
|
||
</p>
|
||
<p><img border="0" src="images\pt4make4.png"></p>
|
||
<p>Так выглядит на экране бинарное дерево с включенным режимом прокрутки. Дополнительной особенностью этого дерева является наличие точек
|
||
около каждой его вершины. Это означает, что данное дерево является результирующим, причем память для всех его вершин должна быть
|
||
выделена в программе учащегося.
|
||
</p>
|
||
|
||
|
||
<a name="ShowPointer"></a><hr noshade size="1">
|
||
<pre><b>procedure</b> ShowPointer(NP: integer);
|
||
</pre>
|
||
<p>Процедура обеспечивает отображение указателя с номером NP при выводе текущего
|
||
линейного списка или дерева. Например, ее вызов вида ShowPointer(1) обеспечил отображение указателя
|
||
P<sub>1</sub> в <a href="#Example1">примерах 1, 2</a> <a href="#Example5">и 5</a>. Если указатель номер NP
|
||
является нулевым, то вызов
|
||
процедуры ShowPointer игнорируется без вывода сообщения об ошибке. Если
|
||
указатель с номером NP не является нулевым и не связан ни с одним из элементов
|
||
списка, то выводится сообщение об ошибке. </p>
|
||
<p>С одним элементом списка или дерева можно связать не более двух указателей
|
||
(исключение составляет последний элемент списка, с которым можно связать не более трех указателей).
|
||
Порядок вызова процедур ShowPointer для одного и того же элемента списка
|
||
является произвольным; при отображении указателей, связанных с одним и тем же
|
||
элементом, они выводятся в отсортированном порядке (например, <code>P<sub>3</sub>P<sub>6</sub></code>).
|
||
В случае списков имена указателей отображаются <i>над</i> элементом, и при наличии нескольких указателей на один элемент
|
||
их имена располагаются слева направо. В случае деревьев имена указателей располагаются <i>под</i> элементом,
|
||
и при наличии нескольких указателей на один элемент их имена располагаются одно под другим.
|
||
Если количество указателей, связываемых процедурами ShowPointer с данным элементом списка,
|
||
превосходит максимально допустимое (например, с последним элементом связывается
|
||
четыре различных указателя), то список связанных указателей дополняется символом
|
||
ошибки — звездочкой (например, <code>P<sub>1</sub>P<sub>2</sub>P<sub>3</sub>*</code>).
|
||
Если с элементом бинарного дерева связывается более двух указателей, то под вторым указателем изображается еще один указатель вида <code>P*</code>.
|
||
Символ ошибки <code>*</code> выделяется красным цветом.</p>
|
||
<p>
|
||
Если указатель надо связать с элементом списка или дерева, помеченным точками (см. <a href="#Example8">пример 8</a>),
|
||
то вызов процедуры ShowPointer для данного указателя надо выполнить <i>до того</i>, как для соответствующего элемента
|
||
списка или дерева будет вызвана процедура SetNewNode (в противном случае при вызове
|
||
процедуры ShowPointer будет выведено сообщение об ошибке вида «Не найден элемент с адресом P1»).
|
||
</p>
|
||
<a name="SetNewNode"></a><hr noshade size="1">
|
||
<p>[Pascal]
|
||
</p>
|
||
<pre>procedure SetNewNode(NNode: integer);
|
||
</pre>
|
||
<p>[C++]</p>
|
||
<pre>void SetNewNode(int NNode);
|
||
</pre>
|
||
<p>Процедура определяет для текущего списка элемент с номером NNode (нумерация ведется от 1)
|
||
как элемент, который требуется разместить в памяти с помощью процедуры New <i>в ходе выполнения задания</i> (подобные
|
||
элементы выделяются в списке с помощью обрамляющих точек — см. <a href="#Example4">пример 4</a>).
|
||
Она также позволяет аналогичным образом выделить элемент текущего дерева (см. <a href="#Example8">пример 8</a>);
|
||
при этом предполагается, что
|
||
элементы дерева нумеруются в <i>префиксном</i> порядке (в частности, корень дерева всегда имеет номер 1; по поводу префиксного
|
||
порядка см. задание Tree13).
|
||
</p>
|
||
<p>Данная
|
||
процедура может применяться только к <i>результирующим</i> спискам и деревьям (для определения которых используются процедуры
|
||
группы Result: ResultList, ResultBinTree, ResultTree). Если
|
||
результирующий список или дерево не содержит элемента с номером NNode, то
|
||
выводится сообщение об ошибке.</p>
|
||
<p>В случае, если указатель на элемент номер NNode
|
||
требуется отобразить на экране,
|
||
вызов соответствующей процедуры ShowPointer необходимо выполнить до вызова процедуры SetNewNode. </p>
|
||
<p>Если при выполнении задания учащийся будет выделять память (процедурой New для языка Pascal или аналогичными средствами для других языков)
|
||
для тех элементов результирующего списка или дерева, для которых это не
|
||
предусмотрено заданием, то соответствующие элементы в результирующем списке (дереве) будут обрамлены
|
||
точками, что приведет к сообщению «Ошибочное решение».</p>
|
||
|
||
<a name="SetDisposedNode"></a><hr noshade size="1">
|
||
<pre><b>procedure</b> SetDisposedNode(NNode: integer);
|
||
</pre>
|
||
<p>Процедура определяет для текущего списка или дерева элемент с номером NNode (нумерация
|
||
ведется от 1, элементы дерева нумеруются в префиксном порядке), который требуется удалить из динамической памяти в ходе
|
||
выполнения задания.
|
||
Данная процедура может применятся только к исходным спискам и деревьям (для определения которых используются процедуры
|
||
группы Data: DataList, DataBinTree, DataTree).
|
||
Если исходный список или дерево не содержит элемента с номером NNode, то
|
||
выводится сообщение об ошибке. </p>
|
||
<p>Элементы, помечаемые с помощью процедуры SetDisposedNode, выделяются на экране цветом меньшей яркости.
|
||
Если они не удаляются из памяти в ходе
|
||
выполнения задания, то их цвет изменяется на красный и выводится соответствующее
|
||
сообщение об ошибке.</p>
|
||
|
||
|
||
<a name="SetObjectStyle"></a><hr noshade size="1">
|
||
<pre><b>procedure</b> SetObjectStyle;
|
||
</pre>
|
||
<p>Данная процедура устанавливает «объектный стиль» для динамических структур и связанных с ними ссылок
|
||
при выполнении задания в среде PascalABC.NET.
|
||
Она должна вызываться при формировании заданий, ориентированных на использование не записей TNode и связанных с ними указателей PNode,
|
||
а <i>объектов</i> класса Node (данный класс определен
|
||
в вариантах задачника для языков платформы .NET и, в частности, для языка PascalABC.NET).
|
||
</p>
|
||
<p>При разработке заданий класс Node <i>не используется</i>. Даже если разрабатываемая группа заданий ориентирована
|
||
на его применение, сами задания надо создавать с помощью записей TNode, указателей PNode и описанных выше процедур.
|
||
Однако для <i>решения</i> подобных задач на языках платформы .NET, а также на языках Python и Java, вместо записей и связанных с ними указателей
|
||
надо применять объекты класса Node. Среди языков, поддерживаемых версией 4.11 задачника, имеется единственный
|
||
язык, позволяющий использовать как указатели, так и объекты:
|
||
это язык PascalABC.NET. Именно поэтому для данного языка
|
||
предусмотрена процедура SetObjectStyle (в прочих языках, использующих объекты Node, <i>настройка объектного стиля в заданиях
|
||
на обработку динамических структур выполняется автоматически</i>).
|
||
</p>
|
||
<p>Создавая задания на обработку динамических структур для языка PascalABC.NET,
|
||
разработчик должен указать учащемуся требуемый способ решения,
|
||
используя соответствующие термины в формулировке задания («запись» или «объект», «указатель»
|
||
или «ссылка» и т. п.), а также настроив,
|
||
при необходимости, вывод динамических структур на «объектный стиль», вызвав процедуру SetObjectStyle
|
||
(по умолчанию применяется «стиль указателей», подробно
|
||
описанный выше). Процедура SetObjectStyle должна быть вызвана после процедуры CreateTask
|
||
(необходимо также, чтобы ее вызов
|
||
располагался <i>перед</i> вызовами любых процедур, обеспечивающих добавление к заданию
|
||
динамических структур и связанных с ними указателей). В результате ее вызова изменяется отображение этих элементов данных, а именно:
|
||
</p>
|
||
<ul>
|
||
<li> вместо текста ptr для непустого указателя указывается текст Node (т. е. имя непустого <i>объекта</i> типа Node);
|
||
<li> в стандартном комментарии к указателю вместо буквы P указывается буква A, например,
|
||
<code>A<sub>1</sub> = Node</code> (эту особенность
|
||
следует учитывать в формулировке задания, используя в ней вместо имен указателей P<sub>1</sub>, P<sub>2</sub>
|
||
и т. д. имена <i>объектов</i> A<sub>1</sub>, A<sub>2</sub> и т. д.).
|
||
</ul>
|
||
<p>Аналогичные изменения (символа P на символ A) выполняются и при отображении указателей,
|
||
связанных с динамическими структурами. Например,
|
||
односвязный список, приведенный в <a href="#Example1">примере 1</a>, при установке объектного стиля будет иметь следующий вид:
|
||
</p>
|
||
<pre>A<sub>1</sub>
|
||
24 - 23 >nil
|
||
</pre>
|
||
<p>Слово nil осталось неизменным, так как в PascalABC.NET оно применяется для обозначения как нулевых указателей, так и
|
||
«пустых» объектов. При использовании других языков платформы .NET обозначения «пустых» объектов
|
||
соответствующим образом корректируются; так, для языка C# применяется обозначение null, а для языка VB.NET —
|
||
обозначение Noth (от слова Nothing).
|
||
</p>
|
||
<p>Заметим, что объектный стиль используется в базовых группах ObjDyn и ObjTree, имеющихся в варианте задачника для системы PascalABC.NET.
|
||
Эти группы с содержательной точки зрения полностью аналогичны группам Dynamic и Tree, ориентированным на применение указателей.
|
||
</p>
|
||
|
||
<a name="MPI"></a><h2>Процедуры для разработки заданий по параллельному MPI-программированию</h2>
|
||
|
||
<p>Процедуры, описанные в настоящем разделе, связаны с разработкой заданий по параллельному программированию и
|
||
доступны в конструкторе учебных заданий, начиная с версии 4.9 задачника Programming Taskbook.
|
||
Подробное описание этих процедур приводится в соответствующем
|
||
разделе описания задачника <b>Programming Taskbook for MPI</b>.
|
||
</p>
|
||
|
||
<hr noshade size="1">
|
||
<pre><b>procedure</b> CreateTask(<b>[</b>SubgroupName: string;<b>]</b> var ProcessCount: integer);
|
||
</pre>
|
||
<p>Данные перегруженные варианты процедуры CreateTask
|
||
предназначены для инициализации задания по параллельному
|
||
программированию. От исходных вариантов процедуры CreateTask их
|
||
отличает наличие параметра ProcessCount. Параметр SubgroupName имеет
|
||
тот же смысл, что и для исходных вариантов процедуры: он определяет
|
||
заголовок <i>подгруппы</i>, в которую включается задание, если
|
||
разрабатываемую группу заданий целесообразно разбить на подгруппы.
|
||
Если параметр SubgroupName является пустой строкой или отсутствует, то
|
||
задание не связывается с какой-либо подгруппой.
|
||
</p>
|
||
<p>Параметр ProcessCount определяет количество процессов при выполнении задания в параллельном режиме.
|
||
Допускается использовать от 2 до 36 процессов. При определении параметра ProcessCount желательно применять датчик
|
||
случайных чисел; это позволит протестировать предложенный алгоритм решения при различном количестве процессов
|
||
параллельного приложения.
|
||
</p>
|
||
<p>Если параметр ProcessCount меньше или равен 1, то для инициализации задания используется соответствующий вариант
|
||
процедуры CreateTask без данного параметра (при этом выходное значение
|
||
параметра ProcessCount полагается равным 1, а задание выполняется в обычном, «непараллельном»
|
||
режиме).
|
||
</p>
|
||
<p>Если параметр ProcessCount превосходит 36, то в окне задачника
|
||
выводится сообщение об ошибке.
|
||
</p>
|
||
<p>Способ использования параметра ProcessCount при инициализации задания по параллельному программированию
|
||
зависит от того, какую «роль» играет программа, вызвавшая
|
||
процедуру CreateTask с параметром ProcessCount (см. таблицу).
|
||
</p>
|
||
|
||
<table border=1 cellpadding=5 cellspacing=0 width=98% align=center bgcolor=#FFFFFF>
|
||
<tr>
|
||
<td align=center><b>«Роль» программы</b>
|
||
</td>
|
||
<td align=center><b>Входное значение параметра ProcessCount</b>
|
||
</td><td align=center><b>Выходное значение параметра ProcessCount</b>
|
||
</td>
|
||
</tr>
|
||
<tr>
|
||
<td>Непараллельная программа-загрузчик, обеспечивающая запуск параллельного варианта программы
|
||
</td>
|
||
<td>Используется (определяет число процессов при запуске параллельного варианта программы)
|
||
</td>
|
||
<td>Всегда равно 0
|
||
</td>
|
||
</tr>
|
||
<tr>
|
||
<td>Главный процесс параллельной программы (процесс ранга 0)
|
||
</td>
|
||
<td>Не используется
|
||
</td>
|
||
<td>Равно числу процессов в параллельной программе; используется при формировании входных и выходных данных
|
||
</td>
|
||
</tr>
|
||
<tr>
|
||
<td>Подчиненный процесс параллельной программы
|
||
</td>
|
||
<td>Не используется
|
||
</td>
|
||
<td>Всегда равно 0
|
||
</td>
|
||
</tr>
|
||
<tr>
|
||
<td>Непараллельная программа, обеспечивающая демонстрационный запуск учебного задания
|
||
</td>
|
||
<td>Используется
|
||
</td>
|
||
<td>Всегда равно входному значению; используется при формировании входных и выходных данных
|
||
</td>
|
||
</tr>
|
||
</table>
|
||
|
||
<hr noshade size="1">
|
||
<pre><b>procedure</b> SetProcess(ProcessRank: integer);
|
||
</pre>
|
||
<p>Данная процедура устанавливает в качестве <i>текущего
|
||
процесса</i> параллельного приложения процесс ранга ProcessRank. Все
|
||
<i>числовые</i> исходные и контрольные данные связываются с текущим
|
||
процессом. До первого вызова данной процедуры текущим процессом
|
||
считается процесс ранга 0. Процедуру можно вызывать несколько раз с
|
||
одним и тем же параметром (например, первый раз процесс делается
|
||
текущим при определении связанных с ним исходных данных, а второй раз
|
||
— при определении его контрольных данных).
|
||
</p>
|
||
<p>Параметр ProcessRank должен принимать значения в диапазоне от 0
|
||
до N – 1, где N — количество процессов,
|
||
возвращаемое параметром ProcessCount процедуры CreateTask. При
|
||
нарушении этого условия выводится сообщение об ошибке
|
||
«<i>Параметр процедуры SetProcess находится вне диапазона
|
||
0..N–1, где N — количество используемых
|
||
процессов</i>».
|
||
</p>
|
||
|
||
</body>
|
||
|
||
</html>
|
||
|