Заочная школа программирования

52

Заочная школа
программирования
Урок 19:
Динамические структуры

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

Указатели и указемые переменные
В программах языка Паскаль можно, например, с уже известными типами, использовать типы указателей. Тип указателя задается синтаксической диаграммой.

Таким образом, каждому типу $t$, стандартному или описанному в программе, можно сопоставить тип указателя $\uparrow t$. Значением типа $\uparrow t$ является указатель (или, что то же, ссылка-кара), указывающий на некоторое значение типа $t$.

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

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

Пусть неокоторая переменная $P$ (будем называть ее переменной-указателем) имеет тип $\uparrow t$. Вызов стандартной процедуры

new(P)

отведет в память место для нового *) значения типа $t$ и сделает значением переменной $P$ указатель на это новое значение, представляемое в программе в виде указемой переменной. Синтаксическая диаграмма указуемой переменной такова:

Перерыв мы можем окончательно определять, что такое переменная в языке Паскаль: это либо имя, описанное в разделе описания переменных, либо переменная с индексами, либо выборка поля, либо буферная переменная, либо, наконец, указуемая переменная.

Цепные списки
Приименим рассмотренные только что средства языка к простейшей форме диапазонских структур — цепному списку. Список этот есть последовательность записей одного и того же типа $t$; при этом одно из полей в этих записях имеет тип $\uparrow t$. Через это поле и происходит сцепление записей в спискок — каждый элемент содержит в нем указатель на следующий элемент списка. В последней записи списка это поле содержит указатель nil.

*)new по-англійски — «новый».

55

Рис. 3.
Склад
новая
105 48
112 55
893 11 nil

Рис. 4.
новая
переод
после
105 48
112 55
893 11 nil

Рис. 5.
новая
переод
после
105 48
112 55
200 13
nil

Рис. 6.
новая
переод
после
105 48
112 55
893 11 nil

nil
после
новая
200 13

Рис. 7.
переод
после
105 48
112 55
893 11
900 13 nil

nil
после
новая
Рис. 8.
105 48
112 55
893 11
900 13 nil

Рис. 9

55

56

Рис. 10.

лицо = record имяфамилия:
array [1..40] of char;
следующее: ↑ лицо
end;
пункт = record адрес, организация:
array [1..30] of char;
учащеся: ↑ лицо;
следующее: ↑ пункт
end;

В раздел описания переменных помещим теперь описание
структура: ↑ пункт;

Мы видим, что в каждой записи типа пункт имеются два указателя — типа ↑ пункт для связи со следующим пунктом и типа ↑ лицо для подсоединения списка лиц, приписанных к этому пункту.

Следующее операторы напечатают имена и фамилии всех учащихся с указанием на консультата-

цюннный пункт каждого (переменная пункты имеет тип ↑ пункт, переменная лиц — тип ↑ лицо):
пункты: = структура;
while пункты <> nil do
begin лица: = пункты ↑. учащиеся;
while лица <> nil do
begin
writeln (лица ↑. имяфамилия,
пункты ↑ адрес, пункты ↑
организация);
лица: = лица ↑. следующее
end;
пункты: = пункты ↑. следующее
end;

Задание 19.4. Написите проерамму, определяющую, сколько учащихся должны обращаться за конструкциями по адресу, указанному в списке конструкционных пунктов первым.

А. Рар

Московский текстильный институт
им. А. Н. Косыгина
(Начало см. на с. 51)

3. На какой выcite над поверхностью Земли силаяжести тела будет в два раза меньше, чем на поверхности Земли?
4. Тело массой m=0,5 кг помещено в воду на глубину h=2 м. За какое время тела всплывает на поверхности? Плотность вещества тела q_T=0,7 г/cm³. Плотность воды q_B=1 г/cm³.
5. Два одинаковых ледяных меторита летят настречу друг друга с равными скорости и при удалении обращаются в пар. Какова должа быть при этом минимальная скорость меторитов, если их температура перед столковением t=-20°С? Удельные теплокости льда и воды соответственно c_π=2100 Дж/(кг·К) и c_B=4190 Дж/(кг·К). Удельная теплота парообразования воды r=23·10⁵ Дж/кг. Удельная теплота плавления льда λ=3,35·10⁵ Дж/кг.
6. В закрытом сосуде находится газ под давлением p=5·10⁵ Pa. Какое давление устанавливается в сосуде, если после открытия крана 4/5 массы газа выйдет из сосуда? Процесс можно считать изготовлением.
7. Шары радиусами r₁=15 см и r₂=10 см заряжены до потенциальов φ₁=20 кВ и φ₂=40 кВ соответственно. Каким станет потенциаль после соприкосовения шаров? Какой заряд перейдет с одного шара на другой? Расмотрите случай, когда шары заряжены одномению.
8. К klemmам источника тока с внутренним сопротивлением r=10 Ом подключены два параллельно соединенных проводника, сопротивления которых R₁=10 Ом и R₂=2 Ом. Определите отношение токов, протекающих через первый проводник до и после обрыва в цепи второго проводника.
9. На столе лежит лист бумаги. Луч света, падающий на бумагу под углом α=45°, дает на ней светлое пятно. На сколько сместится это пятно, если на бумагу положить стеклянную пластину толщиной d=2 см? Показатель предломления стека n=1,5.
10. На каком расстоянии перед рассеивающей линзой с оптической силой D=-2 дтр надо поставить предмет, чтобы его минимое изобравнение получилось на середине расстояния между линзой и ее минимым фокусом?

Публикацию подготовили
М. Борис, И. Турчин