    7. СПОСОБЫ КОНСТРУИРОВАНИЯ ТИПОВ 93 

    7. Способы конструирования типов, объектов и исполнителей 
    Перечисление. Простейшим способом конструирования объектов является перечисление: 

    объекты: 
    А: перечисление (пн, вт, ср, чт, пт, сб, вс) 

    Перечисление — это способ конструирования объектов «из ничего»: мы явно 
перечисляем (откуда и название способа) все возможные состояния данного 
объекта. Например, описанный выше объект А может принимать ровно семь разных 
«обычных» значений (эти значения обозначаются словами пн, вт, ср, чт, пт, сб, 
вс). Кроме того, как и любой другой объект любого  упорядоченного типа, А может 
принимать три идеальных значения: —оо, +oo и неопр. Значения считаются 
упорядоченными в порядке их перечисления: 

    —оо < пн < вт < ср < чт < пт < сб < вс < +оо. 

    Можно, например, написать 

    А := пн 
    если А = вс то ... 
    если пн =< А =< пт то ... 

    Таким образом, «пн» для объекта А является таким же обозначением 
состояния, как и да для объекта типа да/нет или 1 для объекта типа число. 
    Для объекта, заданного перечислением, определены все стандартные операции 
с упорядоченным дискретным типом: присваивание, сравнения на равенство и 
неравенство, сравнения по порядку, операции следующий, предыдущий: 

    А := А.предыдущий 
    цикл пока А.следующий !=+oо выполнять ... 

    С помощью способов конструирования можно конструировать не только объекты 
некоторых новых типов, но и сами эти новые типы: 

    типы:
       день недели = перечисление (пн,вт,ср,чт,пт,сб,вс) 
    объекты: 
      А: день недели 

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

    ГЛ. I. НАЧАЛА ПРОГРАММИРОВАНИЯ 94 

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

    цикл для каждого х из типа Т 
    .  выполнять 
    .    (действия) 
    конец цикла 

    или 

    цикл для каждого х из типа Т 
    .  пока (условие) 
    .  выполнять 
    .   (действия) 
    конец цикла 

    Слово типа, показанное курсивом, можно не писать. Вместо слов "для каждого"
и "из" можно использовать значки "y" и "e" соответственно. Например, в 
фрагменте программы 

   цикл y А e день недели выполнять 
   . обработать (вх: А) 
   конец цикла 

программа «обработать» будет вызвана сначала при А = пн, затем при А = вт 
и т. д. до А = вс (всего семь раз). После окончания выполнения цикла объект А 
будет иметь значение неопр. 
    Элементы упорядоченного типа с конечным множеством значений можно 
перебрать и в обратном порядке. Для этого нужно после итератора «для каждого х 
из типа Т» написать служебное слово реверс (от англ, reverse — обратный, 
противоположный). Например, в фрагменте программы 

    цикл у А е день недели реверс выполнять 
    .  обработать (вх: А) 
    конец цикла 

программа «обработать» будет вызвана сначала при А = вс, затем при А = сб 
и т. д. до А = пн (всего семь раз). После окончания выполнения цикла объект А 
будет иметь значение неопр. 
    Отрезок. Способ конструирования отрезок позволяет ограничить множество 
состояний любого дискретного типа.  Например, запись 

    объекты: 
       х : 1..31 
       у : пн..пт 

означает, что объект х может принимать целые значения в диапазоне от 1 до 
31 включительно, а объект у — дни недели в диапазоне от пн до пт включительно. 
(Кроме этих «обычных> значений объекты х и у, как обычно, могут принимать 
идеальные значения — -oo, 

    7. СПОСОБЫ КОНСТРУИРОВАНИЯ ТИПОВ 95 
    
+оо и неопр. Над сконструированными таким образом объектами допустимы те 
же операции, что и над объектами исходного типа, из которого «вырезался» 
отрезок: над х допустимы те же операции, что и над целыми числами, а над у - 
те же, что и над объектами типа «день недели». Единственное ограничение 
состоит в том, что при изменении состояния объекта новое значение должно 
лежать в указанном диапазоне (если у = пт, то у.следующий = +оо). 
    Вместо конструирования конкретного объекта нового типа можно, как уже 
отмечалось выше, сначала сконструировать сам тип, а потом использовать 
объекты этого типа;	

    типы: 
      день месяца = 1..31	
      рабочий день =  пн..пт 
   объекты: 
     х : день месяца 
     у : рабочий день 

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

    цикл у х е день месяца выполнять  ... 
    цикл у х e день месяца реверс выполнять  ... 

    Кроме того, способом конструирования отрезок можно пользоваться и прямо в 
цикле для каждого: 

    цикл yх € l..31 выполнять  ... 
    цикл уу € пн..пт реверс выполнять ... 
    цикл yz € cб..BC выполнять  ... 

    Запись. Способ конструирования запись позволяет объединить несколько 
объектов в один, более сложный: 

    объекты: 
    дата1, дата2: запись   ( год    : Z+ 
                             месяц  : 1..12 
                             день   : 1..31 
                             день недели: день недели ) 

    Графически запись можно представлять в виде прямоугольника, разбитого на 
некоторое число меньших прямоугольников: 

    дата1: 
-------------------------------------
| год | месяц | день | день | недели |
-------------------------------------
|     |       |      |      |        |
--------------------------------------

    96	ГЛ.  1. НАЧАЛА ПРОГРАММИРОВАНИЯ 

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

    дата2.год := дата1.год + 100 
    если дата1.день = 31 то ... 
    если пн =< дата2.день недели =< пт то ... 

    Таким образом, запись является произвольным формальным объединением 
каких-то объектов. С каждым из этих объектов можно работать независимо. Кроме 
того, однако, допустимы некоторые операции над записью в целом: сравнение на 
равенство и неравенство, присваивание и передача в качестве параметра: 

    дата1 := дата2 
    если дата1 = дата2 то ... 
    обработать (вх: дата1, вых: дата2) 

    В качестве еще одного примера работы с записями приведем программу, 
которая находит пересечение двух отрезков на прямой: 

    программа отрезок (вх/вых: А) пересечь с отрезком (вх: В) 
    . дано: А, В : запись (начало, конец : R) | отрезки на прямой 
    . получить   : | в А пересечение отрезков А и В 
    . --------------
    . А.начало := максимум(А.начало, В.начало) 
    . А.конец  := минимум(А.конец, В.конец) 
    конец программы 

    Структуры. Прежде чем двигаться дальше, рассмотрим исполнителей стек, 
дек, очередь, список, последовательность, множество, нагруженное множество, 
вектор, матрица и динамический вектор, Каждый из этих исполнителей работает с 
конечной совокупностью некоторых объектов (элементов) одного и того же типа Е. 
Например, если тип Е = целое, то это значит, что исполнитель работает с 
какой-то совокупностью целых чисел; если Е = да/нет, то с совокупностью 
элементов типа да/нет и т. п. Между собой исполнители различаются тем, как 
именно они работают с элементами. Например, из стека элементы можно доставать 
только в порядке, обратном порядку помещения их в стек, а из очереди, 
наоборот, — только в том порядке, в котором элементы в очередь помещались. 
Далее мы будем называть эти совокупности элементов структурами и говорить о 
структуре стека или структуре очереди соответственно. 
    Все перечисленные выше структуры, за исключением вектора и матрицы, 
являются динамическими, т. е, число элементов в них 

    7. СПОСОБЫ КОНСТРУИРОВАНИЯ ТИПОВ	97

может изменяться  в процессе работы. Исполнитель, соответствующий любой 
динамической структуре, имеет предписания 
    2. сделать пустым 
    3. пуст/не пуст	: да/нет 

    где слово «пусто» означает структуру, не содержащую ни одного элемента. 

    Стек элементов типа Е. Система предписаний:

    1. начать работу 
    2. сделать стек пустым 
    3. стек пуст/стек не пуст	: да/нет 
    4. добавить элемент <вх : Е> в стек	
    5. взять элемент из стека в <вых : Е> 
    6. вершина стека	::Е   
    7. удалить вершину стека 
    8. кончить работу 

    Курсивом показаны части имени предписания, которые можно опускать. Таким 
образом, «Стек.добавить <Е>», «Стек.добавить элемент <Е) в стек», 
«Стек.добавить элемент <Е>» и «Стек.добавить <Е> в стек» означают одно и то 
же. Структура стека в целом уже 


    Рис.   7.1.   Стек 


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

    4    А. Г. Кушнирепко. Г. В. Лебедев" 
    98	ГЛ. 1. НАЧАЛА ПРОГРАММИРОВАНИЯ 

мает, либо вырабатывает значение типа Е. Как и всякое предписание, 
вырабатывающее значение, «вершину» можно использовать в выражениях и в 
качестве фактического входного параметра. Кроме того, однако, это предписание 
можно использовать и в левой части оператора присваивания и в качестве 
выходных и входно-выходных фактических параметров. Например, можно написать 
«Стек.вершина := 0» или «Стек.вершина := Стек.вершина + 1». 
    Таким образом, запись «Стек.вершина» можно рассматривать как обозначение 
для объекта-вершины стека. Заметим, что при этом используется или меняется 
только состояние вершины стека, а число элементов в стеке не изменяется. 
Естественно, что если в стеке нет "элементов, то предписания "«взять», 
«удалить» и «вершина» приводят к отказу. 
    Очередь элементов типа Е. Система предписаний: 

    1. начать работу 
    2. сделать очередь пустой 
    3. очередь пуста/очередь не пуста	: да/нет 
    4. добавить элемент <вх: Е> в конец очереди 
    5. взять элемент из начала очереди в <вых: Е> 
    6. начало очереди	::Е 
    7. удалить начало очереди 
    8. кончить работу 

    Если стек можно представлять себе в виде трубы с одним запаянным концом, 
то очередь — это труба с двумя открытыми концами, движение в которой, однако, 
возможно лишь в одном направлении (рис. 7.2). 

    
    Рис.  7.2. Очередь 


    Очередь является аналогом стека, с той лишь разницей, что добавление 
элементов производится в конец очереди (на рис. 7.2 справа), а взять, 
посмотреть, изменить или удалить можно лишь начало (на рис. 7.2 слева). 
    Дек элементов типа Е. Система предписаний: 

    1. начать работу 
    2. сделать дек пустым 
    3. дек пуст/дек не пуст	: да/нет 
    4. добавить элемент <вх: Е) в начало/конец дека 
    5. взять элемент из начала/конца дека в <вых : Е> 


    7. СПОСОБЫ КОНСТРУИРОВАНИЯ ТИПОВ 99 


    6. начало/конец дека	::Е 
    7. удалить начало/конец дека 
    8. кончить работу 

    Дек является симбиозом стека и очереди — это та же труба c двумя открытыми 
концами, с которой на сей раз можно работать с обоих концов (рис. 7.3). 
    Таким образом, если мы работаем с деком только с левого края («добавить в 
начало», «взять из начала», «начало», «удалить начало»), то фактически 
получается стек. Аналогично мы получим стек, если будем работать только с 
правого края (конца дека). Пользуясь 
    

    Рис.   7.3.   Дек 


предписаниями «добавить в конец» и «взять из начала», мы можем получить 
очередь, элементы которой будут продвигаться справа налево. С помощью 
противоположной пары предписаний можно получить очередь, элементы которой 
движутся слева направо. В целом же эта структура называется деком (сокращение 
от английского double ended queue — очередь с двумя концами). 
    Множёство элемеитов типа Е. Система предписаний: 

    1. начать работу 
    2. сделать множество пустым 
    3. множество пусто/множество не пусто	: да/не» 
    4. добавить элемент <вх : Е> в множество 
    5. удалить элемент <вх : Е> из множества 
    6. элемент <вх : Е> принадлежит множеству	: да/нет 
    7. взлть какой-нибудь элемент множества в <вых : Е> 
    8. кончить работу 

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

    100	ГЛ. 1. НАЧАЛА ПРОГРАММИРОВАНИЯ 

    Предписание «элемент <вх : Е>  принадлежит множеству»  берет состояние 
фактического параметра и проверяет, есть ли такой элемент в множестве. 
Множество при этом никак не меняется. 

   Нагруженное множество. 

   Система предписаний: 

    1. начать работу 
    2. сделать множество пустым 
    3. множество пусто/множество не пусто	 :да/нет 
    4. добавить элемент <вх : Е) в множество 
    5. удалить элемент <вх : Е) из множества 
    6. элемент <вх: Е> принадлежит множеству	: да/нет 
    7. взять какой нибудь элемент множества в (вых : Е> 
    8. нагрузка <вх : Е>	::Y
    9. кончить работу 

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

    М.нагрузка <вх : е} := у 

устанавливает нагрузку элемента е множества М в состояние у независимо от 
того, какова была нагрузка этого элемента раньше. Если в предписании 
«нагрузка» указан элемент, не принадлежащий множеству, то возникает ситуация 
отказ. После добавления элемента к множеству независимо от того, был уже такой 
элемент в множестве или нет, была ли у него нагрузка определена или нет, 
состояние одинаково — новый элемент принадлежит множеству и его нагрузка имеет 
состояние неопр. 
    Последовательность элементов типа Е. Система предписаний: 

    1. начать работу 
    2. сделать последовательность пустой 
    3. последовательность пуста/не пуста	: да/нет 
    4. добавить элемент <вх : Е> в конец последовательности 
    5. встать в начало последовательности 
    6. есть/нет непрочитанные элементы	: да/нет 
    7. прочесть очередной элемент последовательности в <вых: Е> 
    8. очередной элемент последовательности	::Е 
    9. Пропустить очередной элемент последовательности 
    10. кончить работу 

    Совокупность элементов, с которыми работает этот исполнитель, является 
линейно упорядоченной. Элементы последовательности в каждый момент времени 
разделены на две части — прочитанную и непрочитанную (рис, 7,4), 

    7. СПОСОБЫ КОНСТРУИРОВАНИЯ ТИПОВ 101 

    После предписаний «начать работу» и «сделать пустой» прочитанная и 
непрочитанная части последовательности пусты (не содержат ни одного элемента). 
По предписанию «добавить <вх : Е> в конец» элемент добавляется в конец 
последовательности (непрочитанная часть при этом увеличивается, а прочитанная 
не изменяется). 


    Рис.  7.4.  Последовательность 


    По предписанию «встать в начало» прочитанная часть делается пустой, а 
непрочитанная совпадает со всей последовательностью. Предписание «есть 
непрочитанные элементы» отвечает да, если в непрочитанной части есть элементы, 
и нет, если эта часть пуста. 
    Непрочитанная часть последовательности является аналогом очереди. 
Очередным элементом (аналог начала очереди) называется первый элемент 
непрочитанной чаcти. По предписаниям «прочесть» и «пропустить» (аналоги 
«взять» и «удалить» для начала очереди) очередной элемент перемещается из 
непрочитанной части в прочитанную (т. е. прочитанная часть увеличивается на 
этот элемент, непрочитанная уменьшается и очередным становится следующий 
элемент последовательности). 
    Л2-список элементов типа Е. Система предписаний: 

    1. начать работу 
    2. сделать список пустым 
    3. список пуст/список не пуст	: да/нет 
    4. установить указатель в начало/конец списка 
    5. указатель в начале/конце списка	: да/нет 
    6. передвинуть указатель списка вперед/назад 
    7. добавить элемент <вх : Е> до указателя/за указателем списка 
    8. взять элемент списка до указателя/за указателем в <вых : Е> 
    9. элемент списка до указателя/за указателем        ::Е 
    10. удалить элемент списка до указателя/за указателем 
    11. кончить работу 

    Л2-список — линейный двунаправленный список — можно представлять себе в 
виде перекидного календаря или своего рода бус из элементов типа Е (рис. 7.5). 
    Элементы списка линейно упорядочены. Положение перед первым элементом 
списка называется началом списка, положение за последним элементом называется 
концом списка. Кроме элементов в списке имеется еще указатель, который можно 
представлять себе 

    102	ГЛ. 1. НАЧАЛА ПРОГРАММИРОВАНИЯ» 

стрелочкой, расположенной в начале, в конце или между элементами списка (в 
перекидном календаре указатель — это место, на котором раскрыт календарь). 


    Рис.    7.5.   Л1-список 


    После предписаний «начать работу» и «сделать список пустым» список 
становится пустым, т. е. не содержит элементов. Для пустого списка понятия 
«начало» и «конец» существуют и совпадают, а указатель расположен одновременно  
и в начале, и в конце списка (рис. 7.6). 
    По  предписанию  «передвинуть  указатель вперед/назад» указатель смещается 
на один элемент соответственно вперед (от начала к концу списка) либо назад 
(от конца к началу). Если пользоваться только предписаниями 
«добавить»/«взять»/«элемент»/«удалить», а сам  указатель не двигать, то части 
списка до указателя и за указателем представляют собой полные аналоги стеков 
(рис. 7.7) 


    Рис.  7.6.   Пустой Л2-список 


    Рис. 7.7 


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

    Л1-список элементов типа Е. Система предписаний: 

    1. начать работу 
    2. сделать список пустым 
    3. список пуст/список не пуст	: да/нет 
    4. установить указатель в начало списка 
    5. указатель в конце списка	: да/нет 
    6. передвинуть указатель списка вперед 
    7. добавить элемент <вх: Е> за указателем списка 


    7. СПОСОБЫ КОНСТРУИРОВАНИЯ ТИПОВ 


    Рис. 7.8. Вектор с индексом типа 1..3 


    8. взять элемент списка за указателем в (вых: Е) 
    9. элемент списка за указателем	::Е 
    10. удалить элемент списка за указателем 
    11. кончить работу 

    Л1-список — линейный однонаправленный список — отличается ох Л2-списка тем, 
что он обеспечивает последовательный просмотр элементов списка только от 
начала к концу (встать в начало, пока не в конце передвинуть вперед). Передвинуть 
указатель назад нельзя. Кроме того, в  Л1-списке  работать   
(добавлять/брать/получать/менять/удалять элементы)  можно только за указателем, 
т. е. впереди по ходу движения. Образно говоря, в Л1-списке только одна «сторона» 
указателя является активной. 
    Вектор элементов типа Е с индексом типа И. Система предписаний: 

    1. начать работу 
    2. элемент вектора с индексом (вх: И)     ::Е 
    3. кончить работу 

    Вектор представлявяет собой совокупность элементов типа Е, «пронумерованную» 
значениями типа И (номер элемента называется его индексом). На рис. 7.8 
изображен вектор при И = 1 ..3. 
    Множество значений типа И должно быть конечно: тип И должен быть либо 
равен да/нет, либо задан перечислением, либо получен как отрезок из 
дискретного типа. Например, на рис. 7.9 изображен вектор при И = 
перечисление(пн, вт, ср, чт, пт, сб, вс). 


    Рис. 7.9. Вектор с индексом типа  «день недели» 


    После предписания «начать работу» все элементы вектора существуют и все 
имеют состояние неопр. С помощью предписания «элемент вектора с индексом <и>» 
можно работать с любым элементом вектора, используя его индекс. Если 
исполнитель имеет имя «вектор», то вместо «вектор.элемент вектора с индексом 
<и>» можно сокращенно писать «вектор(и)», Например, можно написать 

    вектор (пн) := Е 
    вектор (вс) := вектор (сб) и т. п. 

    
    104 ГЛ. 1. НАЧАЛА ПРОГРАММИРОВАНИЯ 


    Матрица элементов типа Б с индексами типа И1, И2. Система предписаний: 

    1. начать работу 
    2. элемент матрицы с индексами <вх:И1,И2>      ::Е 
    3. кончить работу 

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


    Рис  7.10. Матрица с индексами типа 1..2, 1..3 


надо не в виде линейной последовательности элементов, а в виде 
прямоугольной таблицы (рис. 7.10). 
    Динамический вектор элементов типа  Е. Система предписаний: 

    1. начать работу 
    2. сделать вектор пустым 
    3. вектор пуст/вектор не пуст : да/нет
    4. число элементов вектора    : Z+
    б. добавить элемент <вx: Е> в конец вектора 
    6. удалить элемент из конца вектора 
    7. элемент вектора с индексом <вх : И>	::Е 
    8. кончить работу 

    Динамический вектор отличается от обычного только тем, что 
    а) индекс у него меняется всегда от  1 до числа элементов в векторе; 
    б) число элементов в векторе может динамически (т. е. в процессе работы) 
изменяться. 
    После «начать работу», как и после «сделать вектор пустым», динамический 
вектор пуст, т. е. не содержит ни одного элемента. Предписания «добавить» и 
«удалить» добавляют или удаляют элемент в конце вектора (т. е. справа, если 
рисовать вектор в порядке возрастания индексов). 
    Структуры как способы конструирования исполнителей. Перечисленные выше 
структуры являются не конкретными исполнителями, а способами их 
конструирования. Пользуясь этими способами, можно сконструировать, например, 
исполнителей «стек символов», «стек целых чисел», «стек элементов типа 
да/нет» и т. п. Такое конструирование записывается в виде 

   исполнитель А : стек элементов типа S 
   исполнитель В : стек элементов типа Z 

    Курсивом показаны части, которые можно опускать. Например, можно написать 
«исполнитель А: стек S». 
    Использование сконструированных таким образом исполнителей ничем не 
отличается от использования любых других исполнителей. Например, мы можем написать 

    А.добавить (вх: "х") в стек 
    А.вершина := " " 
    В.вершина := В.вершина + 1 
    если В.стек пуст то ... 

    Структуры как способы конструирования объектов. Описанные выше структуры 
можно рассматривать и как способы конструирования объектов (множество 
состояний и операции задаются семантикой и системой предписаний 
соответствующей структуры). Например, можно написать 

    объекты: 
     С : стек элементов типа R
     О : очередь элементов типа Z+ 
     R3 : вектор элементов типа R с индексом (1..3) 
     М  : множество элементов типа Z+ 
     MY : множество элементов типа Z+ с нагрузкой типа R 

    Курсивом  показаны  части,  которые  можно  опускать, т.  е.  можно, 
например, писать «R3:вектор R(l .. 3)». 
    Использование сконструированных таким образом объектов практически ничем 
не отличается от использования соответствующих исполнителей. Мы также можем писать 

    С.вершина := С.вершина + 1 
    если С.стек пуст то ... 
    R3(l):= 3.14 и т. п. 

    Разница состоит лишь в том, что исполнители глобальны — они существуют 
все время от начала до конца работы с исполнителем и их можно использовать 
повсюду в программе, а объекты локализованы внутри той программы или 
исполнителя X, где они описаны. Локальность объектов, как мы знаем, надо 
понимать двояко: 
    а) по тексту — их нельзя использовать вне X; 
    б) по времени существования — они не существуют вне периода от начала до 
конца работы X. 
    Именно этим и отличаются объекты от исполнителей. Вместо любого объекта 
А типа Т можно использовать исполнителя А типа Т, и при этом разница будет 
только в вопросах локализации. 
    Замечание. Структуры как способы конструирования объектов и исполнителей 
применимы не только к предопределенным, но 

    106	ГЛ.  I. НАЧАЛА ПРОГРАММИРОВАНИЯ 

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

    Несколько примеров программ. 

    программа инвертирование последовательности (вх/вых: П) 
    . дано	: П : последовательность элементов типа Е 
    . получить : | в П порядок элементов изменен на противоположный 
    . объекты   : 
    .  С : стек элементов типа  Е 
    . -------------
    .  С.начать работу 
    .  П.встать в начало последовательности 
    .  цикл пока П.есть непрочитанные элементы выполнять 
    .  .  П.прочесть очередной элемент в (вых: е) 
    .  .  С.добавить элемент (вх: е) в стек 
    .  конец цикла 
    .  П.сделать последовательность пустой 
    .  цикл пока С.стек не пуст выполнять 
    .  .  С.взять элемент из стека в (вых: е) 
    .  .  П.добавить элемент (вх: е) в конец последовательности
    .  конец цикла
    .  С. кончить работу 
    конец программы 

    программа сжатие пробелов (вх/вых: С) 
    . дано	: С : Л2-список элементов типа символ 
    . получить : | в С каждая   группа подряд идущих пробелов заме
    .            | нена на один пробел 
    . константы: 
    .   пробел = " " 
    . --------------
    .  если С.список пуст то ничего не делать иначе 
    .  .  С.установить указатель в начало списка 
    .  .  С.передвинуть указатель вперед 
    .  .  цикл пока С. указатель не в конце списка выполнять 
    .  .  .  если С.элемент списка до указателя = пробел и 
    .  .  .  .    С. элемент списка за указателем = пробел 
    .  .  .  .  то 
    .  .  .  .   С.удалить элемент списка за указателем 
    .  .  .  . иначе 


    7. СПОСОБЫ КОНСТРУИРОВАНИЯ ТИПОВ 


    .  .  .  .   С.передвинуть указатель вперед 
    .  .  .  конец если 
    .  .  ковец цикла f   
    .  конец если 
    конец программы 

    программа корректировка <вх/вых: П, вх: х : R>
    .  дано : П :    последовательность элементов типа R, 
    . получить : | в последовательности П все элементы, меньшие х, 
    .	           | заменены на х 
    . --------------
    .  П.встать в начало последовательности 
    .  цикл инв: | все меньшие х элементы прочитанной части П 
    .	 .         | заменены на х 
    .  .  пока П. есть непрочитанные элементы 
    .  .  выполнять 
    .  .  если П. очередной элемент < х то 
    .  .  .  П. очередной элемент := х 
    .  .  конец если 
    .  .  П.пропустить очередной элемент 
    .  конец цикла	
    .  конец программы 

    программа в последовательности <вх: П> есть <вх:е0> : да/нет 
    .  дано       : П : последовательность элементов типа Е,     
    .              еО : Е 
    .  получить: | ответ = (е0 е П) 
    . ------------
    .  П. встать в начало последовательности 
    .  ответ := нет 
    .  цикл пока П. есть непрочитанные элементы и ответ = нет 
    .   выполнять 
    .  .  ответ := (П.очередной элемент = е0) 
    .  .  П. пропустить очередной элемент 
    .  конец цикла 
    конец программы 


    Циклы для каждого. При работе со структурами часто возникает необходимость 
перебрать все элементы структуры, или перебрать их до наступления какого-то условия. 
Для организации таких переборов в используемом нами языке программирования 
есть специальные конструкции — циклы для каждого,— о которых мы упоминали 
в разд. 2. Например, приведенную выше программу «инвертирование 
последовательности» с помощью циклов для каждого можно записать так; 

    108	ГЛ. 1. НАЧАЛА ПРОГРАММИРОВАНИЯ 


    программа инвертирование последовательности (вх/вых: П) 
    .  дано	: П: последовательность элементов типа Е 
    .  получить : | в П порядок элементов изменен на противоположный 
    .  объекты   :
    .  С : стек элементов типа Е 
    . ---------------
    .  С.начать работу 
    .  П.встать в начало последовательности 
    .  цикл V е непрочитанной части П выполнять 
    .  .  С. добавить элемент (вх: е) в стек 
    .  конец цикла 
    .  П.сделать последовательность пустой 
    .  цикл Ve е стека С выполнять 
    .  .  П.добавить элемент (вх: е) в конец последовательности 
    .  конец цикла 
    .  С. кончить работу 
    конец программы 

    Общая форма циклов для каждого и эквивалентные им фрагменты программ с 
использованием циклов "пока" приведены в табл. 7.1. 
    Полужирным курсивом выделены части, которые можно опускать. Обратите 
внимание, что: 
    а) перебор элементов происходит в соответствии со структурой, т. е. в 
последовательности перебираются только непрочитанные элементы; из стека, 
очереди и дека элементы при переборе изымаются. при переборе элементов 
множества их порядок неопределен и т. п.; 
    б) для векторов и матриц нет циклов, перебирающих элементы, — при 
необходимости надо перебирать индексы («для каждого И из Имин..Имакс»); 
    в) в теле цикла «для каждого е из X» е является обозначением для 
доступного элемента структуры X (например, для очередного элемента 
последовательности, элемента списка до или за указателем, вершины стека и пр.). 
    Программу «корректировка» можно,например,записать так:

   программа корректировка (вх/вых: П, вх: х: R) 
   .   дано	: П : последовательность элементов типа R 
   .   получить : | в последовательности П все элементы, 
   .              | меньшие х, заменены на х 
   . --------------
   .   П.встать в начало последовательности
   .   цикл Ve е непрочитанной части П выполнять 
   .   .  если е < х то е := х  конец если	'
   .   конец цикла 
   конец программы 


    7. СПОСОБЫ КОНСТРУИРОВАНИЯ ТИПОВ	109 


    Таблица   7.1 

    цикл Vе е стека X выполнять действие <e> конец цикла ==
     цикл пока X.стек не пуст выполнять 
     .  действие <Х.вершина>
     .  X.удалить вершину стека 
     конец цикла 

    цикл Vе e очереди X выполнять действие<e> конец цикла ==
    цикл пока X.очередь не пуста выполнять 
    .  действие <Х.начало>
    .  X.удалить начало очереди 
    конец цикла 

    цикл Vе е начала дека X выполнять действие<e> конец цикла == 
    цикл пока Х.дек не пуст выполнять 
    .  действие (X.начало) 
    .  X.удалить начало дека 
    конец цикла 

    цикл Vе е конца дека X выполнять действие<e> конец цикла ==
    цикл пока Х.дек не пуст выполнять 
    .   действие (X.конец) 
    .   X.удалить конец дека 
    конец цикла 

    цикл Ve e непрочитанной части последовательности X выполнять действие<e>
    конец цикла •= = 
    цикл пока Х.есть непрочитанные элементы выполнять 
    .   действие (X.очередной элемент) 
    .   X.пропустить очередной элемент 
    конец цикла 

    цикл Vе e части списка X за указателем выполнять действие
    конец цикла == 
    цикл пока X.указатель не в конце  списка выполнять 
    .   действие <Х.элемент списка за указателем> 
    .   X.передвинуть указатель списка вперед 
    конец цикла 

    цикл Vе е чаети списка X до указателя выполнять действием 
    конец цикла ==
    цикл пока X.указатель не в начале списка выполнять 
    .  действие <Х.элемент списка до указателя) 
    .  X.передвинуть указатель списка назад 
    конец цикла 

    цикл Vе е множества х выполнять действие<e> конец цикла ==
    У := Х | Y—это еще одно, вспомогательное множество. 
           | которое нужно только для объяснения смысла 
           | цикла Vе е множества. 
    цикл пока У.множество не пусто выполнять 
    .  Y.взять какой нибудь элемент в (вых:е) 
    .  действие <е>	
    конец цикла 

    
    110 ГЛ. I. НАЧАЛА ПРОГРАММИРОВАНИЯ 


    Таблица 7.2 

    цикл Vе е стека X пока условие<e> выполнять действие<e>
    конец цикла == 
    цикл пока Х.стек не пуст и условие<e> <X. вершина> выполнять
    .   действие <X.вершина> 
    .   X.удалить вершину стека 
    конец цикла 

    цикл Vе e очереди X пока условие<e> выполнять действие<e> 
    конец цикла ==
    цикл пока X.очередь не пуста и условие<e> выполнять 
    .  действие <X.начало> 
    .  X.удалить начало очереди 
    конец цикла 

    цикл Vе e начала дека X пока условие<e> 
    выполнять действие<e> конец цикла ==
    цикл пока Х.дек не пуст и условием выполнять 
    .   действие <X.начало> 
    .   X.удалить начало дека 
    конец цикла 

    цикл Vе e конца дека X пока условием выполнять действием конец цикла = = 
    цикл пока Х.дек не пуст и условием выполнять 
    .  действие <X.конец> 
    .  X.удалить конец дека 
    конец цикла 

    цикл Vе е непронатанной части последовательности X пока условием выполнять 
    действие<e> конец цикла ==
    цикл пока Х.есть непрочитанные элементы и 
    .         условие<X.очередной элемент>
    . выполнять 
    .   действие  (X.очередной элемент) 
    .   X. пропустить очередной элемент 
    конец цикла 

    цикл Ve е части списка X за указателем пока условие<e>
      выполнять действие<e> конец цикла ==
    цикл пока X.указатель не в конце списка и 
    .	условие<Х.элемент списка за указателем>
    .  выполнять 
    .    действие <X. элемент списка за указателем>
    .    X.передвинуть указатель списка вперед 
    конец цикла 


    7. СПОСОБЫ  КОНСТРУИРОВАНИЯ ТИПОВ	111


    Таблица  7.2 (продолжение) 

    цикл Vе e часты списка X до указателя пока условие<e>
       выполнять действие<e> 
    конец цикла = = 
    цикл пока X.указатель не в начале списка и 
    .         условие<X.элемент списка до указателя>
    .   выполнять 
    .   действие <Х.элемент списка до указателя) 
    .   X.передвинуть указатель списка назад 
    конец цикла 

    цикл Vе e множества X пока условие<e> 
       выполнять действие<e>
    конец цикла == 
    Y:=X | Y—это еще одно, вспомогательное множество,       
         | которое нужно только для объяснения смысла 
         | цикла  Vе e множества. 
    цикл пока Y.множество не  пусто выполнять 
    .   Y.взять какой нибудь элемент в <вых:е>
    .   если не условие<e> то выход из цикла конец если 
    .   действие<e>
    конец цикла 

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

    программа в последовательности (вх: П) есть (вх: еО) : да/нет 
    .  дано : П : последовательность элементов типа Е, 
    .  е0 : Е 
    .  получить: | ответ = (е0 e П) 
    . ------------
    .	П.встать в начало последовательности 
    .	ответ := нет 
    .	цикл Ve e непрочитанной части П пока ответ = нет 
    .	.   выполнять 
    .	.     ответ := (х = е0)                                                  
    .	конец цикла 
    конец программы 


    ЗАДАЧИ И УПРАЖНЕНИЯ 

    1. Напишите   программу,   которая   определяет   принадлежность 
точки <вх : t: R> отрезку <вх:А>, где А: запись(начало, конец: R). 
    Во всех следующих задачах разрешается использовать только 

    112 ГЛ. 1. НАЧАЛА ПРОГРАММИРОВАНИЯ 

тe объекты-структуры, которые фигурируют в условии задачи. Кроме структур 
разрешается использовать произвольное количество объектов простых типов (не 
структур). Итак, напишите следующие программы; 
    2. программа удалить отрицательные элементы очереди (вх/вых: О>
       .  дано     :    О : очередь элементов типа R 
       .  получить : | из очереди О удалены отрицательные элементы 
       .  объекты :    О1 : очередь элементов типа R 
       .---------------
    3. программа в деке (вх: Д) слово перевертыш : да/нет 
       .   дано      :   Д : дек символов 
       .   получить  : |  ответ = (в деке было слово-перевертыш)
           Д. дек пуст 
       .---------------
    4. программа пересечение множеств (вх: А, В, вых: С) 
       .  дано       : А, В : множество элементов типа Е 
       .  получить: С : множество элементов типа Е | С = А П В 
       .---------------------
    5. программа объединение множеств (вх: А, В, вых: С) 
       .   дано        : А, В : множество элементов типа Е 
       .   получить: С : множество элементов типа Е | C = A V B 
       .----------------
    6. программа разность множеств (вх: А, В, вых: С) 
       .  дано        : А, В : множество элементов типа Е 
       .  получить: С : множество элементов типа Е | С  = А\В 
       .---------------
    7. программа симметрическая разность множеств (вх: А, В, вых:С) 
       .  дано       : А, В : множество элементов типа Е 
       .  получить   : С : множество элементов типа Е | С = А Л В 
                       | А Л В = (А V В)\(А П В) = (А\В)V(В\А) 
       .-----------------
    8. программа увеличить третий элемент (вх/вых: П) на единицу 
       .  дано       : П : последовательность элементов типа R 
       .  получить: | в П третий элемент увеличен на 1 
       .---------------
    9. программа слияние упорядоченных (вх: П1, П2) в (вых: ПЗ) 
       .  дано       : П1, П2 : последовательность элементов типа Е 
                     | последовательности П1 и П2 не убывают 
       .  получить: ПЗ : последовательность элементов типа Е 
       .            | ПЗ состоит из элементов Ш и П2 (с учетом 
                    | кратности) и не убывает 
       .----------------------

    8. ИНДУКТИВНОЕ ВЫЧИСЛЕНИЕ ФУНКЦИЙ 113 

    10. программа сумма элементов последовательности (вх: П) : R 
        .   дано       : П : последовательность элементов типа R 
        .   получить: | ответ = сумма элементов последовательности П 
        .--------------
    11. программа произведение элементов последовательности (вх: П): R 
        .   дано        : П : последовательность элементов типа R 
        .   получить: | ответ = произведение элементов П 
        .--------------
    12. программа удалить отрицательные элементы списка (вх/вых: С) 
        .   дано      : С : Л1-список элементов типа R 
        .   получить: | из списка С удалены все отрицательные элементы 
        .--------------
    13. программа число слов в списке (вх: С) : Z + 
        .   дано    : С : Л2-список элементов типа символ 
        .   получить:  | ответ = число слов  в списке С
        .              | Словом называется максимальная группа подряд 
        .              | идущих символов, не содержащая пробелов 
        .---------------
    14. программа сумма векторов (вх: а,Ь,вых:с) 
        .   дано        : а,Ь: вектор R (1..максинд) 
        .   получить: с : вектор R (1..максинд)  | с — а + Ь 
        . ---------------
    15. программа скалярное произведение векторов (вх: a,b) : R 
        .   дано       : а,Ь : вектор R (1..максинд) 
        .   получить:  | ответ = скалярное произведение (а,Ь) 
        .---------------
    16. программа домножить матрицу (вх/вых: а) на число (вх: х: R } 
        .   дано        : а : матрица R(l..n,l..m) 
        .   получить: | а :   = х * а 
        .---------------
    17. программа произведение матриц (вх: а,Ь,вых: с) 
        .  дано       : а : матрица R(1..n,l..k), 
        .               b : матрица R(l..k,l..m) 
        .   получить:   с : матрица R(l..n,l..m) | с = а * b
        .---------------
