Т. Пратт, М. Зелковиц - Языки программирования - разработка и реализация (4-е издание_ 2002) (1160801), страница 72
Текст из файла (страница 72)
Тогда в самом худшем случае лля доступа к компоненту массива придется провести следующее вычисление: 1-значение(А!1.Л1) - ЧО ч ! х 5 + 0 х Е Массивы более высоких размерностей. Обобщение приведенных формул на случай массивов более высоких размерностей достаточно очевидно. Можно использовать слелующий общий алгоритм для размещения дескрипторов при создании массива и Лля доступа к его элементам. Предположим, у нас имеется массив Я(Е,: Оп....Е.: 0.1 размерности о, тле Е, — нижние границы, О, — верхние границы з-го измерения, а е — размер каждого элемента массива, Предположим, что начало массива расположено по алресу а, + Вычисление множителей.
Кажлый множителы, вычисляется следующим образом: зн = е Для каждого ! ото - 1 до 1вычисляема, = (О,, — Е„з+ 1) х а,ч. + Вычисление виртуального начального адреса: ЧО=а-Хч !Цхе) Множители з)., и виртуальный начальный адрес ЧО могут храниться в дескрипторе массива во время выполнения программы. 6. 1. Структурированные типы данных 255 + Адрес элемента массива. Адрес элемента А(зи ....з.1 определяется по следующей формуле: уО ч Х"ги(5 Х П1;). Сечения Спецификация. Сечение — это подструктура массива, которая сама является массивом. На рис.
6.6 приведены некоторые примеры сечении: на рис. 6.6, а представлено сечение в виде второго столбца матрицы, состоящей из трех столбцов; на рис. 6.6, б сечение представлено третьей строкой матрицы, состоящей из четырех строк, а на рис. 6.6, в сечением является третья плоскость трехмерного массива. рис.
6.6. Сечения массивов: а — одномерное сечение (столбец); б — одномерное сечение (строкв); в — многомерное сечение (плоскость) Одним из первых языков, в которых были реализованы сечения, является Р1/1. Если массив объявлен как А(4, 3), то сечение, изображенное на рис. 6.6, а, обозначается через А(*. 2), где символ *означает, что первый индекс (строка) меняется от 1 до 4. Аналогично два других сечения этого рисунка можно задать как В(3.
*) и С(3. *. *). Сечения можно передавать подпрограммам в качестве аргументов. В языке ГОРСТКАХ в подпрограммы разрешается передавать часть массива в качестве параметров, Поскольку в ГОРСТКАХ используется развертывание массивов по столбцам, то при передаче элемента А(1.
3) векторному параметру В уста- навливается соответствие междуА(1, 3) и В(1),Я(2, 3) и В(2),А(3, 3) и В(3) ит.д. Это позволяет программистам разрабатывать эффективные матричные алгоритмы обработки большой матрицы по частям. Однако для того, чтобы воспользоваться этими алгоритмами, требуется знание внутренних механизмов представления матриц в языке ГОКТКАХ. Поскольку этот метод противоречит современной концепции разработки языка, в ГОКТКА(ч) 90 реализовано понятие сечений. Сечения, изображенные на рис. 6.6, вГОВТКАХ90 задаются какА(1: 4 2), В(3 1: 3) и С(З 1: 3.1: 4).
Реализация. Использование дескрипторов позволяет эффективно реализовать сечение. Например, матрица А размером 3 к 4 описывается дескриптором. 256 Глава 6. Инкапсуляция 4-4 УО [8 1 08 1 Множителе 1 !В 2 08 2 Мнехнтелз 2 В этом случае формула вычисления адреса элемента А[1. З), приведенная в конце предыдущего раздела, будет выглядеть следующим образом: 1-значение[А[!. 11) - уО + ! х 3 +,) х 1 Обратите внимание нато, что в атом случае множитель 2, который представляет собой размер объекта данных, также определяет расстояние между последовательными элементами массива. В данном случае элементы массива следуют непрерывно один за другим.
Однако зто не обязательно; сечение обладает таким свойством, что все его элементы расположены на одинаковом расстоянии друг от друга, но при размещении массива в памяти они не следуют непрерывно друг за другом. Следовательно, дескриптор сечения А(*, 2) (см. рис. 6.6), учитывая дескриптор всего массива А, можно записать следующим образом. УО [8 1 ОВ 1 иноки!еле 1 Этот дескриптор описывает вектор, состоящий из четырех элементов, виртуальная ттачальная позиция которого смещена на две позиции памяти (УО + 2 х 1) относительно виртуальной начальной позиции УО массива А и элементы которого разнесены с промежутком, равным трем позициям памяти.
Аналогично мы можем представить дескрипторы для сечений В(З,*) и С(З,*,*) (см. рис. 6,6), причем для второго сечения дескриптор будет двухмерным. Ассоциативные массивы Харакгерной чертой тех массивов, которые мы изучили к настоящему моменту, был метод доступа к отдельным их элементам с помощью перечисляемого типа данных под названием индекс.
Элементы массива были упорядочены в соответствии с этим индексом, и доступ к каждому элементу осуществлялся посредством выбора соответствующего значения индекса. В некоторых приложениях желательно получать доступ к элементам массива по имени без предварительного упорядочения соответствующих индексов.
Например, список оценок учеников некоторого класса можно организовать в виде двух массивов, в одном из которых содержатся имена студентов, яа!ле[т ), а во втором— полученные ими оценки, дгат)е[т'1. В данном случае подразумевается упорядочение по целочисленному индексу т. 6.1, Структурированные типы данных 257 Альтернативный метол заключается в том, чтобы использовать в качестве инлекса имя. Поскольку последовательность имен (то есть строк символов) фактически неограниченна, то пе существует какого-либо реального неявного перечисления.
Вместо этого множество имен используется как множество перечисления. При лобавленин нового имени это перечисление увеличивается. Такой массив называется ассациаьчинным массивом. Ассоциативные массивы в В)ь)ОВО[Л называются таблицами и объявляются с помощью ключевого слова тай)е, они также играют важную роль в таких языках обработки процессов, как Рег1'. В Рег) ассоциативный массив создается при помощи специальной операции, которая обозначается символом я. Так, следующий оператор: $0)аззьззв - !"М!сне))е".
'А'. "вот[5", 'В'. "М!сйае!". '0'). создает ассоциативный массив из трех элементов. Первый член каждой пары является ключом, а второй — значением. Доступ к ассоциативному массиву ВС1 а 55! ! 50 продемонстрирован в следующем примере: К)азз[155( чисйе)1е').
№ значение равно А ру=хб)д55г[5ц № Массив у обьявявется насснвон № скалярав нз б зленентов тог [5[=0, $!<б. 5зьч)(Рг!пв "1-, 51, !У[5[1)о") Печать из цикла [ог будет выглядеть так: 1=. 0. Оог!5 1=, 1, В [-, 2. М!свае) 1=. 3. 0 [=. 4. Мьсйе[)е !-. б. А Этот пример помогает понять реализацию ассоциативных массивов. Хотя исходный порядок ключей элементов массива был (Мзс))011е. 0ог[5, Мзс))ае1), при хранении в памяти массив упорядочивается по алфавиту (точнее, в соответствии с алфавитным порядком ключей массива). Это обеспечивает возможность эффективного поиска ключа нужного элемента массива на основе алгоритма двоичного поиска'. 6.1.6.
Записи Структура данных, состоящая из фиксированного количества компонентов различных типов, обычно называется записью. Спецификация и синтаксис. Записи и векторы являкттся различными формами линейной структуры данных фиксированных размеров, но записи отличаются от векторов в двух отноп)ениях: Лссоциатинныс массивы мохаю также Найти н языке РН!', достаточно Широко нрименяеиом для созЛаиия сераерных сценариев в ьчеь-приложсциях. — примеч. науч. ред. Этот абзац не соответствует дейстеительлости. Ассоциативные массивы [тсг! вообще никак це уцорядочи ваки ся цри хранении, более того, цел ьзн даже предугадать их порндок, так как для вычислениин адреса области памяти злсмснта исоользуегся хзш-фушсция.
Чтобы получить упорядоченный набор ключей, слсдуст исоолвоовать функцию сортировки. Ру загг! вЕУ5 [ХС[а551 я 55) ) .. — Урциеч науч ред 258 Глава б. Инкапсуляция 1) компоненты записей могут быть разнородными, то есть объектами данных разных типов, в отличие от одноролных элементов векторов; 2) компоненты записей обозначаются сииволическичи именами (идеятификаторами) в отличие от индексов, пумерующих элементы векторов.
Достаточно типичным прил!ером синтаксиса, используемого лля объявления записей, является конструкция зСгэсЦ используемая в языке С: ВГГВСГ Еар1ЕУЕЕТгаЕ !ш' !О !лг Аде; Т1оат 5АЕАРУ: сваг оерш ! Еяр1оуее; Это объявление опрелеляет запись типа Еяр1оуееТуре, состоящую из четырех компонентов, два из которых целочисленного типа: один — вещественного и один— символьного с именами !О, Аде, 5ЯЕА!(Ч и Оер( соответственно, Е!Рр!оуее объявлена как переменная типа Е!ьр1оуееТуре (в следу!оших объявлениях переменных этого типа не требуется описывать внутреннюю структуру записи Епр1 оуееТуре). Для того чтобы выбрать компонент записи, в языке С используется следующая синтаксическая конструкция: Евр1оуее,!О Еяр1оуее 5ЯЕА!!Ч Атрибуты записи видны из приведен!гого выше объявления: 1) количество компонентов; 2) тип данных лля каждого компонента; 3) имя для обозначения каждого компонента. Компоненты записи часто называются полями, и соответственно имена компонентов являются именами пгьчей.
Записи иногла называются структурами (как в С). Выбор компонентов является одной из основных операций над записями, например Епр1оуее.5АЕАРЧ. Она соответствует выбору элементов из массива при по- моши инлексов, но с одним су!цественным отличием; инпекс здесь всегда является буквальным именем компонента и никогла не может быль вычисляемым значением. Приведенный пример выбора третьего компонента записи, Еар1оуее. 5АЕАЙЧ, соответствует выбору третьего ком!ювента вектора, ЧЕСТЕ3), но для записей не существует аналогичной векторной операции выбора ЧЕСТЕ!), где ! -- вычисляемое значение. Операции над записью как единым целым обычно немногочисленны.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
