Т. Пратт, М. Зелковиц - Языки программирования - разработка и реализация (4-е издание_ 2002) (1160801), страница 68
Текст из файла (страница 68)
1. Операции выборки компонента. Обработка структур данных часто требует поочередной выборки компонентов атой структуры. Существует два типа операций выборки, посредством которых осуществляется доступ к компонентам структуры данных для их последующей обработки другими операциями: произвольная выборка, прп которой можно получить доступ к произвольному компоненту структуры, и последовательная выборка, при которой 240 Глава б. Инкапсуляция компоненты перебираются в заранее опрелеленной последовательности. Например, при обработке вектора операция индексации позволяет выбирать произвольный компонент вектора (например, Ч[4)), а ее использование совместно с циклами Ног и н011е реализует последовательный выбор компонентов: Гвг 1 1 Ьо 10 ав ..
Н[11 2. Операции над всей структурой данных. Такие операции в качестве аргументов используют структуру данных целиком, а их результатом также является некоторая структура данных. В большинстве языков предусмотрено некоторое ограниченное количество таких операций (например, сложение двух массивов, операция присваивания одной записи другой, объединение множеств), В таких языках, как АРЕ и ЯХОВО[.4, представлен широкий спектр операций над структурами данных, так что программисту редко приходится выбирать отдельные компоненты этих структур для обработки. 3.
Вставка/удаление компонентов. Операции, которые меняют количество компонентов в структуре данных, оказывают большое влияние на способы представления и управления ресурсами памяти для структур данных. Более подробно об этом мы расскажем в следующем разделе.
4. Создание/упичтолвснив структур данных Операции по созданию и уничтожению структур данных также оказывают большое влияние на способы управления ресурсами памяти для структур данных. Выборку (или доппуп) компонента или значения некоторого объекта данных следует отличать от близкой по смыслу операции ссылки на нее (см. подробное обсужлепие этого вопроса в главе 9). Обычно объект данных имеет некоторое имя (например, вектор с именем Ч).
Когда мы в программе пишем Ч[4), подразумевая, что нам нужен четвертый компонент вектора Ч, на самом деле имеет место следующая двухступенчатая последовательность действий: сначала выполняется операция ссьтки, а затем — операция выборки. Операция ссылки определяет текущее местоположение объекта под именем Ч (то есть Рзначение этого объекта) и в качестве результата возвращает указатель на местоположение объекта (то есть всего вектора, обозначенного этим именем).
Операция выГ>орки по этому указателю и по указанному индексу 4, которым обозначен нужный компонент вектора, находит и возвращает указатель на местоположение в памяти этого конкретного компонента. В этом разделе мы будем заниматься только операцией выборки. Обсуждение операпии ссылки (которая может оказаться гораздо более сложной и дорогостоящей, чем операция выборки) мы отложим до главы 9, где будут подробно рассмотрены проблемы определения имен, правила, определяющие области видимости, и среды ссылок 6.1.3. Реализация типов структур данных Задачи, которые необходимо решить для реализации структурированных типов данных, аналогичны тем, что возникают прн реализапии элементарных типов данных.
Кроме того, здесь имеются два дополнительных момента, которые оказывают влияние на выбор способа представления структур данных в памяти при реализа- 6.1. Структурированные типы данных 241 ции языка программирования: эффективная выборка компонентов структуры данных и эффективное управление структурой как единым целым. Представление структур данных Представление структур данных в памяти включает в себя: 1) хранение отдельных компонентов структуры; 2) хранение необязательного дескриптора, в котором хранятся некоторые или все атрибуты структуры. На рис. 6.1 изображены две основные схемы представления. 1.
Последовательное представление, когда структуры данных хранятся в од- ном непрерывном блоке памяти, содержащем и дескриптор, и компоненты. 2. Связанное представление, когда структуры данных хранятся в нескольких отдельных блоках памяти, связанных между собой при помощи указателей. Указатель, связывающий блок А с блоком В, называется связью. Он представлен адресом первой позиции блока В, который хранится в специально отведенном для него месте в блоке памяти А. Последовательное представление используется для структур фиксированного размера и иногда для однородных структур данных переменного размера, например для символьных строк или стеков.
Связанное представление обычно используется для структур переменного размера, например для списков. В следующих разделах рассматриваются некоторые вариации последовательного и связанного представлений. ПОСЛЕДОВАТЕЛЬНОЕ СВЯЗАННОЕ Рис. 6.1. Способы представления линейных структур данных в памяти 242 Глава б. Инкапсуляции Память компьютера, как правило, структурирована в виде простой последовательности байтов. Аппаратные операции, используемые для обеспечения доступа к компонентам структур данных, обычно ограничиваются операциями индексации с использованием индексных регистров, которые позволяют эффективно реализовать доступ к компонентам векторов, представленных в памяти последовательным способом. В большинстве компьютеров аппаратная часть не поддерживает использование дескрипторов для структур данных, манипуляцию структурами при их связанном представлении, распределение памяти для структур данных и управление внешними файлами.
Таким образом, структуры данных и определенные для них операции обычно реализуются при помощи программного моделирования в реализации виртуального компьютера языка программирования. В этом заключается существенное отличие структур данных от элементарного типа данных, для которых, как правило, возможно аппаратное прелставление объектов и операций над этими объектами. Реализация операций над структурами данных Выборка компонентов — одна из наиболее важных операций при реализации большинства структур данных. Необходимо обеспечить эффективность выполнения этой операции как для произвольного, так и для последовательного способа. Например, выборка компонента Яг1] для произвольного 1-го элемента вектора Я11] должна быть достаточно эффективной.
Также весьма желательно, чтобы последовательная выборка элементов А11], А12],... вектора была более эффективной, чем просто аналогичная последовательность операций произвольного выбора элементов вектора. Эти два основных способа выборки компонентов реализуются по-разному для последовательного и связанного представлений объекта в памяти.
Последовательное представление. Произвольная выборка компонентов часто подразумевает вычисление адреса с использованием формулы доступш бззозвй адрес ь сяеаение. Относительное местоположение выбранного компонента а последовательном блоке называется смеи1ениель а местоположение начала всего этого блока в памяти называется сто базовым адресом. Формула доступа по имени или индексу требуемого компонента (например, по целочисленному индексу компонента массива) определяет, как вычислять смещение для данного компонента.
Затем полученное смещение добавляется к базовому адресу для получения фактического адреса требуемого компонента в памяти компьютера, как показано на рис. 6.2. Например, в языке С массив сПаг АН0] представлен в памяти последовательным способом: А10], А[Ц, ..., А19]. Адрес компонента А11] будет состоять из базового адреса массива А ( в данном случае это Азначение элемента А(0]) со смещением на 1. Вообще говоря, в языке С для массивов типа сйаг адрес элемента А11] массива А будет равен 1-значению (А)+1. Обратите внимание на то, что такой способ вычисления может быть очень эффективным; если в качестве индексов используются константы, то транслятор может вычислить формулу доступа для компонента еще во время компиляции и сгенерировать кол для непосредственного доступа к нему.
Для однородной структуры, например для массива, представленного в памяти последовательным способом, выборка последовательности компонентов может осуществляться следующим образом. Б.1. Структурированные типы данных 243 1. Для выбора первого компонента последовательности используется формула доступа, то есть вычисляется сумма базового адреса и смещения компонента. 2. Для перемещения к следующим компонентам последовательности к местоположению текущего компонента добавляется размер этого компонента.
В случае однородной структуры размеры всех компонентов одинаковы, поэтому адрес каждого компонента последовательности может быть найден путем добавления некоторой постоянной величины к адресу предыдущего компонента, Базовый адрес = = адрес местоположения А(0( Смещение = = Гразмер компонента = =5х1=5 Базовый адрес+ смещение = = )-значение (А(ой + 5 = = )-значение (А(5й Рис. 6.2. Доступ к компонентам массива типа спаг в языке С Связанное представление. Произвольная выборка компонента из связанной структуры подразумевает следование по цепочке указателей от первого блока, представляющего эту структуру в памяти, к искомому компоненту.
Для такого алгоритма выборки местоположение в блоках каждого компонента указателя на следующий блок должно быть известно. Выборка последовательности компонентов происходит путем выбора первого компонента и следования по цепочке указателей к последующим компонентам. Представления структур данных иногда расширяются, чтобы включить в себя определяемые системой структуры, которые позволяют эффективно осуществлять выборку компонентов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
