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