Virt N. Algoritmy struktury dannyh = programmy (ru)(T)(410s) (522393), страница 34
Текст из файла (страница 34)
рнс. 4.3). Следует подчеркнуть, что использование ссылок для реализации рекурсивных структур — чисто технический прием. Прогр ммясту необязательно знать об их существовании. Память может выделяться автоматически, как только упоминается новая переменная. Однако если использование ссылок илп указателей сделать явным, то можно строить более разнообразные структуры данных, чем те, которые можно задать 'лишь с помощью рекурсивных определений. В частности, в этом случае можно определять «бесконечныв», или циклические, структуры. Кроме того, на одну и ту же подструктуру можно ссылаться из разных мест, т, е.
относить ее к нескольким разным структурам. Поэтому в современных языках программирования принято обеспечивать явное ма, ннпулнрование не только данными, но и ссылками на них. Это предполагает четкое разграничение в обозначениях данных и ссылок на них. Следовательно, нужно ввести тнйы данныгм значениями которых являются ссылки (указатели) 4. Диииииееекие иицгорлациоииые етруитдрег 194 на другие данные.
Для этого мы используем такие обозначения; (уреТ = '( Т (4.4) В описании типа (4.4) имеется в виду, что значениями типа Т являются ссылки на данные типа Т. Таким образом, стрелка в (4.4) читается как «ссылка па». Существенно, что тип элементов, на которые ссылаются значения типа Тр, задан в его определении. Мы говорим, что Те связан с Т. Эта Рнс. 4.3. Структура, связанная ссылкаин, связь отличает ссылки в языках высокого уровня от адресов в языке ассемблера и является очень важным средством увеличения надежности программ с помощью избыточности обозначений.
Значения ссылочных типов создаготся всякий раз, когда динамически размещается какой-либо элемент данных. Мы будем придерживаться соглашения, чтобы каждый такой случай явно выделялся в программе в отличие от ситуации, когда предполагается, что при первом упомннапин элемента он автоматически размещается в памяти. Для динамического размещения данных мы вводим встроенную процедуру ггею. Если дана ссылочная переменная р типа Т„, то оператор пеги(р) (4.5) выделяет память для переменной типа Т, создает ссылку типа Т„на эту новую переменную и присваивает значение этой ссылки переменной р (см. рис. 4.4). Теперь сама ссылка обозначается как р (т, е, является значением ссылочной переменной р). В отличие от этого через ру обозначается переменная, на которую указывает р (т, е.
динамически размещенная переменная типа Т). 4 2. Ссылки или Икизатели 195 Выше упоминалось, что квжд~ и рекурсивный тип для того, иобы его кардинальное число было конечным, должен содержать некоторый вариант. !1а', более типичный случай показан ца примере генеалопщеско:о дерева; после признака принимает одно вз двух значений (булевскнх); когда оно принимает значение !а!зе, все прочие компоненты отсутствуют. Это изображается такой схемой описаний; !уре Т = гесогс! И р Феп 5 (Т) епс! (4.6) 5(Т) означает последовательность определений полей, содержащую хотя бы одно поле типа Т, что приводит к рекурсии. р:1Т Рнс.
4.4. динамическое размещение переменной р!о Все структуры типов, описанных по образу (4.6), представляют собой древовидную (или сппсковую) структуру, подобную изображенной на рис. 4.3. Недостаток такой структуры — наличие ссылок на элементы, состоящие только из одного поля признака, т. е. не содержащве никакой существенной информации. Применение метода ссылок дает возможность легко экономить память, так как позволяет вклюппть информацию поля признака в значение самой ссылки, Обычно принято расширять область значений типа Т, добавляя и ией значение, ко~орое не ссылается нн на какой элемент. й!ы обозначаем его специальным символом п!! н считаем, что пИ автоматически является элементом всех ссылочных типов, описанных в программе.
Это расширение области ссылочных значений позволяет создавать конечные структуры без явного использования вариантов (условий) в (рекурсивных) описаниях. Новые формулировки описаний типов данных (4.1) и (4.3), основанные на явных ссылках, даны соответственно в (4.7) и (4.8). Заметим, что в случае (4.8) (который соответствует схеме (4.6)) отсутствует вариант, поскольку р!'.йпогип=!а!зе теперь выражается как р = и!1, Изменение названия типа рес( на регзоп («человек») отражает новую точку зрения на структуру, связанную с использованием явных ссылок. Вместо того чтобы рассматривать вначале данную структуру как целостное образование, а затем выделять в ией подструктуры и их компоненты, мы обращаем внимание в первую очередь на компоненты, а их взаимосвязь (основанная на ссылках) 4.
Дпноллические ннфорллоцоонные структуры из любого фиксированного описания не очевидна. Фура ехргегяоп = гесогй ор: орега1ог; орд!, орд2:, гегпг евй; Фуре геггн — — гесогй ФГ Г Фйеп(Иг афа) еЬе (глча: ",ехрчегглоп) (4,7) епй Фуре реагочл = гесоги члаллл«: ада; ,)аГйегл чподлег; 1Реггап (4 й) епй Структура данных, представляющая генеалопчческое дерево, показанная на рис. 4.2 н 4.3, здесь вновь изображается па рис. 4.5, гдс ссылки на неизвестных лпц обозначены через п11. Очевидно, что при этом дотов стигается значительная экономна памяти. Обращаясь шювь к рис.
4.5, предположим, что Фред н МэГгеа пн, мочу он 1ли — брат и сестра, т. е. имеют общих отца и мать. Такой случай легко выразить, заме- Е:Ш нив два значения п)1 в соотяао о ои оп кто ои оп ветствуюших полях двух запи- сей (тоЯег — у Фреда и гаг ° ркс. 4д. Структура с он бег — у Мэри), Реализация, прп которой концепция ссылок скрыта или используются другие приемы управления памятью, вынуждала бы программиста представить записи Лдама и Евы по два раза каждую. Хотя при просмотре даинь1х не имеет значения, представлены эти два идентичных отца (плп две матери) двумя записями плн одной, разница валгна, когда допцскаегвя выборочное изгаенение. Когда ссылки используются как явные элементы данных, а не как скрытые вспомогательные средства реализации, программист может явно указывать случаи «разделения» памяти (в смысле совместного владения какой-либо областью памяти), Другое следствие использования явных ссылок †возможность определять и обрабатывать циклические структуры данных.
Разумеется, эта дополнительная гибкость не только увеличивает возможности, но и требует большей осторожности, так как работа с циклическими структурами легко может привести к бесконечным вычислениям. 4.2. Ссылки илп указатели !йт То, что мощность и гибкость тесно связаны с опасностью ошибочного использования, — явление, шиРоко известное в программировании. Особенно это касается оператора безусловного перехода (яо1о). Возможно, продолжая аналогию между структурами программ и структурами данных, чисто рекурсивные структуры данных можно поместить на уровень, соответствукпций процедуре, тогда как введение ссылок можно сравнить с использованием операторов (ио1о).
Так же как с помощью оператора (но1о), можно строить любые программные схемы (включая циклы), так и с помощью ссылок можно создавать структуры данных любого вида (в том числе циклические). Соответствия между структурами программ и структурамн данных указаны в табл. 4.1. Таблица 4.!. Соответствия между структурами программ и даннык Твп Лаамыа Оператор Схема етроепеа Скалярный ткп Запись <е<ассив Присваиванне 3 остивной оператор ператор пекла с параметром Условный оператор Атомарный элемент Перечисление Извесы<ос число повторений Выбор Запись с вариантами, объединение типов Последователы<ость, илв Файл Оператор никла с предуслонием нлн постусловнем Оператор процедуры Неизвестное число по- вторений Рекурсивный< тнн данных Структура, связанная ссылками Рекурсия Универсальный граф Оператор безусловного перехода ргоседцге Р; Ьеи!и И <а 1Ьеп Ьен!и Р;, Р еп<1 епд (4.9) где Рс — оператор, не содержащий Р, эквивалентен итеративному оператору чуЬ11е В до Ра Аналогии, указанные в табл.
4.1, позволяют обнаружить такую же связь между рекурсивными типами данных и после- В гл. 3 было показано, что итерация есть частный случай рекурсии н что вызов рекурсивной процедуры Р, описанной по схеме 198 4. Динамические информационные структуры (4.10) где То — тип, ие содержащий Т, эквивалентен файловому типу данных Ие отТс и может быть им заменен. Отсюда видно, что рекурсию можно заменять итерацией в программах и описаниях данных в том (и только в том) случае, если имя процедуры или типа появляется только один раз и конце (илн начале) своего описания.
Остальная часть этой главы посвящена созданию и обработке структур данных, компоненты которых связаны явными ссылками. Особое значение придается структурам простой формы; приемы работы с белес сложными структурами можно получить из способов работы с основными видами структур. Эти виды — линейные списки, или цепочки, самый простой случай, а также дсревья. Предпочтение, которое мы оказываем этим «строительпым блокам», не означает, что на практике не встречаются более сложные структуры. В действительности следующая история, напечатанная в цюрихской газете в июле 1922 г., доказывает, что иррегулярность может появляться даже в структурах, которые обычно считаются образцом регулярности, таких, как (семейные) деревья.
В этой истории говорится о человеке, который так описывает несчастье своей жизни: Я женился на алове, т которой была взрослая дочь. Мой отец, который давольно часто иас навешал, влюбилси в мою падчерицу а женился на ней. Следовательно, мой отец стал моим зятем, а моя падче. рпца стала моей матерью. Спусти несколько месяцев, мои 1кена ро. лила сына, который стал шурином моего отца и одновременно моим Лялей У жены моего отца, то есть моей падчерицы, тоске родился сыи. таким образом, у меня появился брат и одновременно внук.
Моя жена является моей бабушкой, так как она мать моей матери. Слсзоввтельпо, я музк моей >иены и одновременно ее внук, другнмв словами, я — свой собственный дедушка, л.з. пмнвпньгв списки 4.3.1. Основные операции Самый простой способ соединить, или связать, множество элементов — это расположить нх линейно в списка, илн в очереди. В этом случае каждый элемент содержит только одну ссылку, связывающую его со следующим элементом списка. довательностыо.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
