Н. Джехани - Язык Ада (1988) (1160771), страница 20
Текст из файла (страница 20)
Конечно, полное описание должно быть задано позднее. Тип ЕМР10УЕЕ не может быть описан как гуре ЕМР1.0УЕЕ Ь гесоп1 ХАМЕ: ЯТК1ХО (1 .. 30); 1рч1ХТЕОЕК; МАХАОЕК:ассекя ЕМР(.ОУЕЕ; -*"неверно епо гесоп1; так как язык Ада не допускает использования определения ссылочного типа прн описании объекта, как показано в приведенном выше описании компоненты МАХАОЕК именуемого типа ЕМР10УЕЕ. 2.8. Примеры Примеры этого раздела акцентируют внимание на дополнительных возможностях именуемых и ссылочных типов.
В первом примере вычисляется площадь геометрической фигуры, представленной записью с вариантами. Этот пример иллюстрирует удобства использования оператора саве для работы с записями с вариантами. Второй и третий примеры касаются печати н поиска в бинарном дереве, каждый узел которого представлен в виде рекурсивного именуемого типа. Рекурсивное программирование очень хорошо сочетается с рекурсивными типами. 93 Е о тинах 2.8.1. Использование записей с вариантами Функция АКЕА вычисляет площадь объекта типа ОЕОМЕТК)С-НО13КЕ (объявленного ранее в разделе, описывающем записи с вариантами): 1ппсйоп АКЕА (НОЕОМЕТК)С НОРКЕ) ге!пгп НОАТ Ь Р1 сопзгапг:= 3.!416; Ьей!п сане ЕБ !з — выбор основан на дискриминанте Е зч)геп КЕСТ = ) ге!пгп НОАТ (Е1.еКВ); — используется явное преобразование — в действительное значение зчйеп С1КС1.Е = > гегпгп Р1еЕКАРПЗБеККАРПЛ; згйеп РО1ХТ = > ге!игл 0.0; епй сане; епз) АКЕА; 2,8.2.
Печать дерева Задача состоит в распечатке значений узлов бинарного дерева с корнем К. Каждый узел представлен в виде ЧА1Л)Е ЬЕГТ и!ОВТ где компонента ЧАШЕ есть значение узла (типа 1ХТЕОЕК), а компоненты ЬЕЕТ и К1ОНТ указывают на левое и правое поддеревья. Наличие значения ппй в компонентах ЬЕЕТ и К1ОНТ означает пустое поддерево. Тип узла задан следующими описаниями, которые являются частью пакета ТКЕЕ: !уре ХОРЕ; — неполное объявление типа гуре ВКАХСН Ь ассека ХОРЕ; гуре ХОРЕ Ь вЂ” объявление типа становится полным гасо уз) ЧАШЕ: 1ХТЕОЕК; ЬЕЕТ, К1ОНТ: ВКАХСН; епе! гесогй; Отметим то, как в языке Ада описываются рекурсивные типы.
Как уже упоминалось ранее, вместо описания прямой рекурсии должен использоваться ссылочный тип. Сначала задается неполное описание типа. Используя неполное описание типа, описывается ссылочный тип. Наконец, неполное описание типа дополняют до полного описания типа. Имя неполного типа можно использовать только в описании ссылочного типа~~. Следовательно, следующее альтернативное задание типа является ошибочным: о В противном случае возникают сложности при компиляции описания, использующих иепонные типы.
Глава 2 1уре ВКАХСН; '- неполное описание типа (уре ХОРЕ Ь гесоп1 ЧАШЕ: 1ХТЕОЕК; ЬЕРТ, К(ОНТ: ВКАХСН; — ошибочное использование неполного — типа ВКАХСН епо гесогг); 1уре ВКАХСН Ь ассеээ ХОРЕ; Процедура РК1ХТ для печати бинарного дерева основана на следующем аб- страктном алгоритме: Ы дерево не пусто (йеп печатать левое поддерево печатать корень печатать правое поддерево епб Ы; Алгоритм обеспечивает печать узлов в обратном порядке. В постановке задачи порядок печати узлов дерева не был определен, поэтому можно использовать любой порядок.
Процедура РК1ХТ имеет вид «з(й ТЕХТ 1О, ТКЕЕ; — эти пакеты подключаются к единице компиляции вяе ТЕХТ 1О, ТКЕЕ„ — их компоненты становятся непосредственно — видимыми ргосеопге РК1ХТ (К: )п ВКАХСН) Ь раскайе 1О 1ХТ Ь пезг 1ХТЕОЕК 10 (1ХТЕОЕК); пяе 10 1ХТ; Ьей)п Ы К/ = пп11 1)геп РК1ХТ (К.ЬЕРТ); Р()Т (К ЧАШЕ); — процедура РОТ из пакета„.10 1ХТ вЂ” имеет аргументы целого — типа ХЕ% Ь)ХЕ; РК1ХТ (К.К1СНТ); епг) Ы; епй РК1ХТ; 2.8.3. Поиск в бинарном дереве Задача состоит в написании двух эквивалентных функций: одна рекурсивная, а другая итеративная, которые осуществляют поиск значения Х в упорядоченном бинарном дереве с корнем К (типа ВКАХСН, который был определен ранее).
Функции возвращают значение ТЛЕ, если Х присутствует в дереве, и значение РАЬВЕ в противном случае. о гвиях Упорядоченные бинарные деревья — это бинарные деревья, упорядоченные в соответствии с некоторым правилом. Одним из определений упорядоченного бинарного дерева является следующее: упорядоченное бинарное дерево есть бинарное дерево, в котором левый сын узла всегда имеет значение меньшее, чем значение у его родительского узла, а правый сын узла всегда имеет значение большее, чем у его родительского узла. — рекурсивная версия функции поиска в — бинарном дереве 1ппс!!оп В1М БКСН КЕС (К: !п ВКА)чСН: Х: !п 1ХТЕОЕК) ге!вгп ВООЬЕАМ В Ьей!п И К = пп11 !!геп ге!пгп РАЬБЕ; е1яЫ Х = КЧАЬ1)Е !)геп ге!пгп ТКОЕ; е!яЫ Х < КУАРЕ гйеп гемгп В1Х БКСН КЕС (К.ЬЕРТ, Х); е!яе ге!пгп В1М БКСН КЕС (К.К1ОНТ, Х); епг! И; епй В1Н БКСН КЕС; — итеративная версия функции поиска в — бинарном дереве 1ппсбоп В1Х БКСН 1ТЕК (К: !пВКАХСН; Х: !и 11ЧТЕОЕК) ге!пгп ВООЬЕА)ч !я Т.
ВКАХСН; — промежуточная переменная для — прохождения по дереву Ьей!п Т:= К; !вор И Т = пп1! !пеп ге!пгп РАЬБЕ; е!яЫ Х = ТУАПСЕ !пеп ге!вгп ТКЫЕ; е!яИ Х < ТУАЬ()Е !)геп Т:= Т,ЬЕРТ; е1яе Т:= Т.К1ОНТ, епй И; епй 1оор; епг! В1Х БКСН 1ТЕК; В этом примере обе версии функции — рекурсивная и итеративная — просты и легки для понимания. Однако некоторые задачи лучше выражаются рекурсивно, например задача о ханойской башне и алгоритм быстрой сортировки, приведенные в гл.
1. Многие программисты избегают рекурсии и трактуют ее как новинку (ОК175). Такие языки, как Фортран и Кобол, не допускают рекурсии, поэтому для многих программистов, знающих эти языки, данное ограничение становится препятствием в понимании рекурсии. Примеры рекурсии, обычно приводимые в учебниках, такие как вычисление факториала и чисел Фибоначчи, часто лучше выражаются итеративно и поэтому являются неубедительными, показывающими неуместность рекурсии. Глава 3 Пакеты [7~ 3.1. Введение Пакеты, подпрограммы, задачи и настраиваемые модули представляют четыре вида программных модулей, из которых состоят программы на языке Ада. Пакеты, подобно подпрограммам, могут быть раздельно компилируемыми, тем самым допуская расчленение больших программ на небольшие и легко управляемые части.
Расчленение программ на маленькие фрагменты помогает в построении, понимании и поддержке больших программных систем [НОК79ь Пакет обычно представлен двумя частями — спецификацией пакета и телом пакета. Спецификация определяет возможности, обеспечиваемые пакетом. Тело пакета реализует эти возможности. Спецификации пакетов и тела пакетов могут быть раздельно компилируемыми. Однако компиляция спецификации пакета должна предшествовать компиляции соответствующего тела пакета.
Пакеты представляют собой механизм скрытия информации и инкапсуляции данных. Они могут быть использованы для групп логически связанных сущностей, таких как константы, переменные, типы и подпрограммы. Пользователь пакета может видеть только спецификацию пакета и не видеть деталей реализации, заданных в теле пакета.
Более того, только сущности, определенные в видимой части спецификации пакета, могут быть использованы пользователем пакета. Детали реализации пакета скрыты от пользователя пакета, поэтому он не может использовать эти знания в программе; таким образом, программа не может быть сделана зависимой от реализации пакета. Следовательно, если спецификация пакета была согласована заранее, то реализатор пакета свободен в выборе той или иной реализации пакета, согласующейся со спецификацией пакета. Реализация пакета может быть как угодно изменена при условии, что она останется согласованной со спецификациями пакета.
3.2. Спецификация пакета [7.21 Спецификация пакета имеет следующую форму: расМайе идентификатор !в основные элементы описания [рнчазе основные элементы описания1 епд идентификатор; Основной элемент описания является либо основным описанием, либо специауикатором использования, либо специЯикатором представления. Основное описание представляет собой любое описание, исключая тело подпрограммы, пакета, задачи, след тела (след тела обсуждается в гл. 7 «Структура программ и раздельная компиляция»). Тело подпрограммы, пакета (если оно существует), задачи или настраиваемого модуля, определенное в спецификации пакета, должно быть задано в теле пакета.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
