Т. Пратт, М. Зелковиц - Языки программирования - разработка и реализация (4-е издание_ 2002) (1160801), страница 75
Текст из файла (страница 75)
Различные виды списков В некоторых языках опрсделсиь< различные вариации обычных списков. Стеки и очереди. Стек — это ~акой список, в котором операции выбора, вставки ц удалепия компонента ограиичсиы только одиим его концом. Очередь — это такой список, в ко~ором выбор и удалеиис компонента осуществляются с одного его конца, а добавление — с другого. Для очередей и стеков используется как последовательное, так и связанное представление.
Деревья. Список, компопеитами которого могут быть как списки, так и элемеитариые объекты данных, иазывастся деревом, при условии, что каждый список является компоиецтом ие более чем одного другого списка. Большая часть примеров, иллюстрирующих 118Р в этой книге 1см. рис. 6 10), в действительности я вляются деревьями. Ориеитироваипые графы. Структура дапиых, в которой компопепты могут быть связаны друг с другом произвольным образом (то есть ие обязательио последовательным способом), пазь<вастся ориеитироваииым графом. Списки свойств. Запись с переменным количеством компоиеитов обычно иазывается списком свойств, если количество компонентов может варьироваться без каких-либо ограничений.
(Структура вариаитиых записей в Разса1 может изменяться только в рамках строго опрсделеииого набора альтернатив.) В списке свойств должны присутствовать и имена компоиеитов (иь<еиа полей), и их зиа- 268 Глава 6. Инкапсуляция чения. Каждое имя называется именем свойства; значение соответствующего поля называется значением свойства. Общим представлением списков свойств являются обычные связанные списки, в которых имена свойств н их значения чередуются. Для того чтобы выбрать конкретное значение свойства (например, значение свойства Аяе (возраст)), осуществляется поиск только по именам свойств в списке, пока не булет найдено нужное имя.
Следующий компонент списка— зто значение этого свойства. Когда в список свойств вставляется новое свойство, фактически добавляются два объекта: имя свойства и его значение. В различных языках программирования списки свойств называются по-разному; в 1.1ВР они называются также таблицами (и для их хранения в памяти иногда используется смешанное последовательно-связанное представление). Также используются термины «список атрибутов-значений» (аггпЬвге-ча!ое !!зг) и «список описаний» (дезснрбоп !!ьц). Объекты данных переменных размероя естественно использовать в тех залачах, в которых количество данных заранее неизвестно.
Структуры данных переменного размера позволяют выделять память по мере необходимости во время выполнения программы. В языках программирования существуют два различных по существу подхода к использованию подобных типов данных. В неко~орых языках, например в М1. и 1!ЯР, такие типы данных, как список, список свойстн, очередь и стек предоставляются непосредственно языком, то есть встроены в него. Реализация языка включает в себя скрытую систему управления памятью, которая автоматически распределяет память для этих структур и восстанавливает ее для последующего использования в случае их уничтожения в программе. В лругих языках, напри»1ер в С, Разса1 н Ас!а, предоставляется тип данных указатель вместе со средством явного динамического выделения памяти программистом, с помощью которых программно~ и строит связанные структуры, как описано в разделе 5,3.2.
Стеки, очереди, деревья и другие типы объектов данных переменного размера очень важны во многих фазах реализации самого языка. Например, стек, создаваемый во время выполнения программы, является одним из центральных объектов данных, определяемых системой, в реализациях большинства языков программирования (см. главу 9), деревья часто используются для представления таблиц симнолов н компиляторе (глана 3), а очереди часто используются лля планирования и синхронизации выполнения параллельных подпрограмм, 6.1.8. Множества Множество — это объект данных, содержащий чеупврядочеяный набор различных значений. В отличие от множесз на список является упорядоченным набором значений, некоторые из них могут повторяться.
Основные операции над множествами таковы. 1. Определение принадлежности к множеству. Эта операция дает ответ на вопрогл является ли объект Х элементом множества 5 (то есть верно ли, что Х и 5)? 2. Вставка и уничтожение отдельных значений. Первая операция нключает Х в множество 5, если там еще нет такого элемента. Вторая операция удаляет Х из 5, если Х является элементом множества, б.1. Структурированные типы данных 269 3.
Объединение, пересечение и разность множетпв. Пусть имеются два множества 5: и 5ъ Каждая из этих операций создает новое множество бъ которое либо содержит элеь<енты обоих множеств 5< и 5< (в случае объединения), либо содержит только те элементы, которые принадлежат и множеству 5<, и множеству 5< (в случае пврвсвчвиил), либо содержит только те элементы 5<, которых нет в 5, (в а<учае разности множеств 5< и 5<). Заметил<, что к компонентам множества невозможна осуществить доступ при помощи индексов илн по их взаимному расположению. Реализация. В языках программирования термин множество иногда применяется к структуре данных, которая представляет собой упорядоченное множвс<ива. Упорядоченное множество фактически является списком, из которого удалень< повторяющиеся элел<енты.
Такое множество не требует дополнительного рассмотрения. Неупорядоченное множество допускает два специальных способа представления, которые заслуживают отдельного обсуждения. 1)редставлеиие множеств битовыми строками. Представление с помощью битовых строк уместно в том случае, если заранее известно, что используемый универсум (универсальное множество, из которого берутся значения, ко<орые могут появиться в объектах данных множества) невелик по размерам. Предположим, что универсум состоит из И элементов. Расположим эти элементы некоторым произвольным образом: е„еъ ..., е,.
Множества элементов, вь<бранпых цз этого универсума, можно представить бинтовой строкой длины <<, в ко~арой бит под номером 1 равен 1, если е, входит в множество, и <) в противном случае. Такая битовая строка представляет харпктвристическу<о функцию множества. В этом представлении операция не~анки элемента в множество сводится к замене соответствующего бита в строке на 1, операция удаления — к замене соответствую<пего бита па О, а определение принадлежности элемента области множеству сводится к проверке значения соответствующего бита.
Операции объединения, пересечения и вычитания над множествами могут быть представлены при помощи поразрядных булевых операций над битовыми строками, которые обычно встроены в аппаратную часть компьютера: поразрядное логическое ИЛИ, примененное к двум б<повым строкам, соответствует объединению, поразрядное логическое И соответствует пересечению, а операци<а вычитания можно представить как поразрядное логическое И, примененное к первой битовой строке и инвертированной второй. Если в компьютере предусмотрена аппаратная поддержка операций над битовыми строками, такой способ представления множеств становится особенно эффективным.
Однако аппаратная поддержка таких операций над битовыми строках<и обычно реализована для битовых строк некоторой определенной длины (например, не более длины слова основной памяти). В случае более длинных строк приходится применять программное моделирование для разбиения длинной строки на несколько коротких, которые уже могут обрабатываться аппаратными командами. Хэш-кодировпние. Распространенной альтернативой представлению с помощью битовых строк служит представление множеств, основанное на технологии хэшкодирования, или фрагментированной памяти (зсаггег э<агапе).
Эгот метод следует использовать в том случае, если используемый универсум достаточно велик (например, если множество содержит числа или строки символов). Он позволяет 270 Глава 6. Инкапсуляция эффективно реализовать операции опрецеления принадлежности к множеству, вставки элементов и (с помощью некоторых методов) удаления элементов множества.
В то же время такие операции, как обьсдиненне, пересечение н вычитание множеств прихолптся реализовывать в виде последовательности операций определения принадлежности элемента множеству, вставки и удаления элементов, поэтому они весьма малоэффективны. Методы хэш-кодирования могут бьп ь эффективными только при условии использования большого объема памяти. Как правило, язык не обеспечивает доступность лля пользователя такого представления типа данных л<но>кество, но в реал из анин языка этот способ используется для представления некоторых данных, определяемых системой и используемых во время трансляции или выполнения программы. Например, большинство реализаций языка Е15Р используют этот способ лля прелставления множества, называемого сиисхо>я объектов, которое сос> опт из имен всех атомов, ис полы>усы ых во время выполнения конкретной программы.
Почти все компиляторы используют хшп-кодирование для поиска имен в таблице символов (см, главу 3). В случае векторов каждый компонент однозначно определяется своим инлексом, и его адрес может быть легко получен с помощью простой формулы доступа. Целью хэш-кодирования является лублированис этой возможности, чтобы организовать эффективный доступ к компонентам множества. Но здесь возникает проблема, связанная с тем, что потенциальное множество допустимых имен огромно по сравнению с доступной памятью. Есл и мы выделим некоторый блок памяп<, называемый хэш-таблицей, по меньшей мере в два раза превышающий тот, который мы предполагаем реально использовать, то хэш-кодирование может быть весьма эффективным (например, сели в множестве будет 1000 элементов, то следует отвести место под 2000 элементов). Вместо того чтобы хранить элементы множества последовательно внутри выделенного блока памяти, они размещаются в нем произвольным образом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
