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