Информационный сайт

 

Реклама
bulletinsite.net -> Книги на сайте -> Программисту -> Непейвода Н.Н. -> "Основания программирования " -> 194

Основания программирования - Непейвода Н.Н.

Непейвода Н.Н., Скопин И.Н. Основания программирования — Институт компьютерных исследований , 2002. — 919 c.
Скачать (прямая ссылка): osnovanprogramm2002.pdf
Предыдущая << 1 .. 188 189 190 191 192 193 < 194 > 195 196 197 198 199 200 .. 316 >> Следующая

исключением. Нельзя молиться на то, что сотворено человеком, как на Священное Писание, и воспринимать как ересь любые отступления от частностей даже самых гениальных решений. Точно так же, увидев недостаток или даже прямую ошибку, нельзя сразу же становиться в позу высокомерного пренебрежения и игнорировать имеющиеся в данном решении находки. Тем более это верно потому, что перечисленные недостатки LISP являются скорее мелкими шероховатостями, имеющими полное оправдание для тех условий, в которых создавался язык.
9.4. РЕКУРСИВНЫЕ СТРУКТУРЫ ДАННЫХ
547
Для списков необходимо определить операцию конкатенации (ограничиться присоединением одного элемента в данном случае уже нецелесообразно):
Conc (S1, S2) = (Kf,..., , Kf,..., KS2) ;
В разных языках принята разная нотация для изображения списков. Чаще всего специальным образом помечают рекурсивность и закольцованность списков (по-видимому, метод неподвиной точки рассматривается как сли -ком абстрактный и далекий от реализации, базируейся на понятии адресации памяти).
, наконец, опием оснаеннй ориентированный мультиграф обего вида в качестве рекурсивной структуры данных. Пусть оснащениями вершин служат элементы типа Т1, а оснащениями дуг — элементы типа T2. Тогда мо но задать следуий аблон рекурсивнх определений типа:
Graph(T1, T2) = (T1, *Safearray((*Graph(T1, T2), T2)).
9.4.2. Указательные типы
В современном практическом ООП сложные системы объектов появляются на каждом шагу, в частности, в визуальных средах. Списки и указатели являются стандартным способом взаимосвязи систем объектов. Поэтому рассмотрим организацию систем объектов в более явной взаимосвязи с ны-неней их реализацией и с понятием адреса.
Вначале детализируем вопрос об определении обчного списка (тем более, что взаимосвязи объектов часто идут именно через списки объектов). Пусть имеется специальный примитивный тип pointer, значения которого есть произвольные адреса. Нетипизированный указатель можно рассматривать как типизированный, но с базовым типом, совпадаим с объединением всех возмо нх типов (последнее не является конструкцией языка, поскольку явно определить такое объединение невозмо но). Такие типы предусмотрены, в частности, в C++/C#, Java и Object Pascal.
Имеются некоторые тонкости, ткотрые не очень важны для дальнейшего, но заслуживают упоминания. В C/C++/C# и Java специальной нотации для указателей не требуется, т. к. одновременно с определением типа определяется и указатель для него (спецификатор '*'), а следовательно, в определении структуры, содераей указатель на нее саму, нет ничего нового: эта конструкция попадает под формальное определение рекурсивной структуры
548
9.
даннх. данном языке указатель относится к базовм типам, тогда как в Pascal и в большинстве других языков (во всех языках со строгой статической типизацией) указатель — это конструктор структуры данных (подобнй образовани отрезка из перечисления), имеий единственнй аргумент: имя своего базового типа. Теперь
record Inf: T, Next: pointer; end
описывает структуру, которая может представлять список, т. к. pointer, ука-звая куда угодно, способен на то, чтобы указвать на точно таку е запись, как та, что описывается. Однако фактически он может указывать не только на таку запись, поэтому нельзя утвердать соответствуая память будет иметь описываемую структуру. По существу, приведенная запись не должна рассматриваться в качестве рекурсивной структуры данных, хотя она и может применяться, и применяется для реализации рекурсивных структур. Более того, такая запись с нетипизированным указателем часто реализует в C++/C#, Object Pascal и Java список объектов различных типов, правда, здесь есть одна тонкость: на первом месте стоит так е указатель.
type ListofObjects=record Inf, Next, Prev: pointer; end
онечно е, здесь нет никаких признаков (за искл чением имен) того, что Next и Prev указыва т на такие е структуры. ичем не помогает здесь ограничение мно ества допустимх значений произвольного указателя до множества значений данного типа, ничего нового не обнаруживается. К примеру, описание
type R = record Inf: pointer, Next, Prev : AR; end
можно считать простым сужением предыдущего описания записи с указателем. днако при описании R фактически используется R, а значит, оно попадает под формальное определение рекурсивной структур данных. Тем не менее самая прагматически ваная характеристика структур данных — то, что для кадого ее конкретного экземпляра долно быть выполнено
r. Next. Prev = &r;
(9.8)
r. Prev. Next = &r;
никак не отражено в определении типа.18 Чисто прагматически этот недостаток обходится тем, что определяются три различных конструктора такого ти-
18 Смотрите упражнение 5 в качестве комментария к только что приведенным соотношениям.
9.4.
549
па, соответствуие вставке нового элемента в начало, в конец и в середину списка, и деструктор, который, удаляя объект, одновременно перекоммутирует ссылки.
Рассмотренный пример показывает, почему от тематики Т никуда не деться, поскольку лбе чисто технологические ограничения оста тся на практике благими по еланиями, пока они как следует не поддеран .
Предыдущая << 1 .. 188 189 190 191 192 193 < 194 > 195 196 197 198 199 200 .. 316 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100