Т. Пратт, М. Зелковиц - Языки программирования - разработка и реализация (4-е издание_ 2002) (1160801), страница 85
Текст из файла (страница 85)
Прсдложитс реализацию этих функций с использованием стандартных функций ввода-вывода языка С. 23. Разработайтс в Са-ь класс гаЬ) опа) (класс рацион щьных чисел), обьскты которого представляют собой частное от деления двух целых чисел а и Ь, то есть а! Ь. Перегрузите операции Са-ж таким образом, чтобы операторы типа а=Ь+с лгогли использоваться для а, Ь и с, принадлежащих как к целому типу, так н к классу гаг)ола). + Разработайте класс рациональных чисел для операций +, — и *. Включите функцию ргапЬ(х) для рационального аргумента х, которая печатала бы значение х как у!д Если первый аргумент рациональный, то вычисление функции очевидно.
Что будет, если первый аргумент целочисленный? Как бы вы разрабо~али этп операции, если бы оба аргумента принадлежали к целому типу? (Для решения этой задачи вы должны воспользоваться дружественными функциями (Тга ела),) + Попробуйте распшрить класс, включив в него операцию деления х. Какие при этом возникают проблемы и как можно их решить? Помните, что результат деления а! Ь также должен быть рациональным числом. 24. Предположим, что в языке В). опрсдслсна структура данных стек и три опе- рации: МенТор(5. Е) — добавление элемента Е в вершину стека 5; РорТор( 5) — удаление верхнего элемента стека 5; Беттор(5) — возвращение указателя на текущий верхний элемент стека 5.
6.7. Задачи и упражнения 301 Что неправильно в разработке этих трех операций? Как следует их переопределить, чтобы исправить положение? 25. Список свойств может быть прсдстанлсн как множество (а нс как список), поскольку доступ к его элементам осуществляется произвольным образом при помощи индекса (имсни свойства), а нс последовательно, что более характерно для списков. Разработайте представление в памяти списков свойств, используя прсдложсшсую в разделе 6.1.7 методику. 26. В языке 5В)О ВОБЛ список свойств, илп таблица (в терминологии этого языка), создастся при помощи оператора, подобного следующему: Х = ТАВЕЕ(50.20) Таблицы хранятся в памяти с использованием смешанного последовательного и связаннс>го представлений. В памяти выделяется начальный блок, достато'пп> болыпой для храпе>шя 50 пар «ипдскг — значение», и указатель на этот блок присваивается псрсмсппой Х.
Пары «ппдскс — зпачспис» помещая>тся и таблицу с помощью операций присваивания вида Х(Аде) - 52 который заноси~ пару (Яде, 52) в таблицу, сели в ной индекс Аде сщс нс существует. Если же этот индекс уже присутствует в таблице, то соответствующее ему значение мснястся на 52. Когда в начальный блок будет занесено 50 пар «с>ндекс -значение», то в памяти будет выделен новый блок вместимостью до 20 пар (второй параметр при вызове функции )АВЕЕ), который будет связан с первым блоком при помосци указателя. Новые пары теперь будут заноситься в этот новый блок, пока он пс заполнится, что приведет к выделению еще одного блока снова вместимостью до 20 пар.
Удаление пар из блока нс лонускастся. Разработайте детальную структуру представления таких таблиц в памягсс, включан дескриптор времени выполнения, а затем прсдложитс ал~оритм для реализации приведенной ньнпс операции присваивания в случае произвольной таблипы, 27. В синтаксическом представлении списка с использованием обычной списочной нотации (как последовательности элементов, заключенных в круглыс скобки) завсршакнций сог указатель па и>) ш>дразумсвастся нсянным образом (цапримср, записывают как (А В С), а нодразумсвают (А В С и> ) ) ) И>согда требуется, чтобы последний алсмснт списка имел сйг указатель на атом, отличный от п1Е В этом случае можно использовать альтернативную форму записи — точечную нотацисо.
В точс шой нотации каждый элемент списка записывастс я в виде пары ползлсментов, представляющих собой сег и с()г элемента. Подзлсмспты заключак>тся в круглыс скобки и разделяются точкой. Например, список (А) в списочной нотации преобразуется в (Я, ш) ) в точечной нотации, (А В) запишется как (А. (В.п>) ) ) и ((Я В) С) — как ((А.
(В. и> ) ) ) . (С. пП ) ). Теперь пара из элементов А и В, которая нс может быть записана в списочной нотации, может быть записана в точечной нотации как (А. В). Перепишите в точечной нотации следующие списки: а) (А (В 0); б) (((А)) В (С О)), 302 Глава б. Инкапсуляция 28. Списки свойств атомов, которые содержат свойства, отличные от печатаемого имени атома, никогда не могут быть удалены утилитой сборки мусора, даже если они полностью недоступны из активной списковой структуры во время сборки мусора. Объясните почему. 29, Самовоспроизводящаяся функция. Эквивалентность представления программы и данных в языке Е| ЯР позволяет достаточно легко писать довольно сложные программы, реализация которых на других языках была бы значительно труднее.
Нскоторыс из этих программ имеют статус классических задач Е1ЯР, среди которых типичной является задача самовоспроизводящейся функции, Напишите на языке Е|БР функцию 5кг, значением которой было бы се собственное определенно. Функция 5йр нс получает никаких параметров, Если 5кр опрсдслсна как (Оеуип 5ду ()Ьопу) то результатом вызова 5ЙЕ является списочная структура ~ йегип 5кр ( ) Ьойу). Функция 5кр должна собирать список, являющийся результатом се вычисления, по частям. Она нс можст иметь доступа к списку свойств атома 5РГ для того, чтобы получить список, являющийся сс определением. 30. Рассмотрим следующую программу на языке МЕ: Оагатуре йщг = лего ~ опе ) Шо ) Ьпгее 1 уоиг ~ Гнче ) а1х ! аечеп ) е1дпн ! пъпе: оайагуре пивьег = айд)г ог йд1л ) позе ог пипьег * пипьег; Хип й9нсч(опе) - 1 ) йднмгио) - 2 ) йдцчнпгее) - 3 ) йдпгчыоиг) = 4 ) йднч()1че) = 5 ) й91лч(юх) = б ) Онднн(аенеп) = 7 ~ йдгтч(епдЬГ) = 3 ! йдагч(п1пе) - 9 ) йрйгч(лего)=0; Гип на1ие(позе~к,у)) = 10 * ча1ие(х) н ча)не<у) ~ ча1ие(ай 91 Ы х) ) - й да ли(х) .
+ Постройте трассировку выполнения каждой из приведенных ниже функций. Какое значение будет напечатано в результате выполнения каждой из пих? 1) на)ие ( зй д)И 5ечсп) ); 2) ча1ие(попе(зо19)г1пнпе), зйдль1ЬЬгее))); 3) ча1ие(поде(зо1длг(гпгее), попе(зйд1т(опе) зо)даЬНоиг)))). + Изобразите схематически структуру данных для каждого выражения из предыдущего пункта. Глава 7. Наследование В разделе 6,2 мы обсуждали концепцию инкапсулированных типов данных как средство разработки программ, которос позволяет создавать новые типы данных с операциями, выполняющимися только над объектами этих новых типов.
Напри лавр, для создания списков студентов, посещающих различные курсы лекций в университете, можно создать поные типы данных — аесс1оп (группа) и агнбепг (фамилия студента). Для занесения фамилий студентов в списки групп определенного курса можно разработать операцию АМТо5ест1ап С Ситиатурой эсшбепс х эесТ1сс — У ЗЕС- 11 сп. В программе турееег ( СеГшмшп ) аесьшв туреееу ( Сегшншэ ~ ащаещ, аесг1оп Неэс1аав. 5геееш Неь5ШСеш. Аеато5есю ащ пеэ5тэеепы МечС1ааз Н подробности реализации опьектов тина асцсеп1 н зесшсп скрыты в подпрограмме АсоТо5есю оп. Программист может рассматривать зти два новых типа как обычные элементарные тины данных, а подпрограмму АйбТо5есысп — как элементарную встроен пуку в язык функцию. Знание фактической структуры атих типов данных потребуется только разработчику подпрограммы )ьЗо)о5есь1оп.
Хотя подобная методика может применяться для написания программ на любом языке, хотелось бы максимально упростить ее использование н по возможности избежать связанных с се применением ошибок. Лучше иметь э распоряжении такой язык программирования, который полюгает осуществлять инкапсуляцию данных, а не полагаться на то, что программисты нс будут ошибаться. Сначала мы опишем механизмы автоматической ивкапсу зяции данных, такие, например, как конструкция расее (пакет) в языке Ада. Затем мы расширим эту концепцию таким образом, чтобы операции, применяемые к инкапсулированным объектам данных, можно было выводить автоматически, используя так называемую концепцию нпслегзованил.
Выводимые таким образом операции называются методами. Логическим развитием этой концепции является полный полиморфизм операций, который также обсуждается в атой главе. 304 Глава 7. Наследование 7.1. Повторное рассмотрение абстрактных типов данных Напомним, что в разделе 6.2 мы определили абстраялн<ый тип данных как новый тип данных, определяемый программистом и включаюн<и1и 1) опредсляемый программистом тип данных; 2) наоор абстрактных операций над объектами этоп> типа; 3) инкапсуляцию объектов этого типа таким образом, что пользователь нового тш<а не может манипулировать этими объектами, иначе как только с помощью определенных прп разработке типа абстрактных операций. Абстракция данных, то есть конструирование новых типов данных и операций над обьектамн этих типов, как было сказав> выше, является одной из фундаментальных концепций программирования. В тех языках, которые плохо обеспечивают прямую пою<с ржку абстракции дапцых сверх обычного механизма определения подпрограмл<, иГя>граммисту все жс предоставлена возможность создавать и использовать абстрактные типы данных, несмотря ца то что такое п<вятис в языке пс представлено.
ГГозтому программист должен использовать соглашения по кодировали к>, организуя программу таким образом, чтобы достичь эффекта использования абстракции типов данных. Однако без поддержки определения абстрактных типов данных в язьн<с инкансуляция нового типа данных невозможна. Так, например, если нарушены соглац<спия по кодированию (со<ни<тельно или случайно), то реализация языка пе сможет обнаружить нх нарушения. В таких языках, как С, ГОЕТКАМ и Равса1-подобш <е, определенные программистом абстрактные юшы данных часто появляются в виде спсш<альн ых библиотек подпрограмм.
А<1а, )ага и Сьь относятся к гсм немногим широко распросграпеппым языкам, в которых имеются специальные средства для по>щсржки абстракции данных. Способ определения типов, подобный тому, что используется в языке С, упрощает объявление новых переменных данного типа, так как для:>того треоустся только имя этого типа. Однако внутренняя структура объектов данных этого типа не инкапсулирована. Любая нодпроц>амма, в которой можно объявить переменную как при надлсжащук> к новому типу данных, также позволяет получить доступ к компонентам представления этого типа.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
