Cтраница 4
Многомерные неоднородные массивы могут быть получены путем непосредственного применения техники однородных массивов, рассмотренной в разд. В других случаях можно допустить, что элемент линейного массива указателей указывает на другой линейный массив указателей, а не на простой элемент данных. Такое представление применяется широко, но в основном для массивов переменного размера, рассматриваемых в следующем разделе. Там, где длина массива фиксирована, первый метод обеспечивает эффективный доступ к элементам с помощью той же самой формулы доступа, что и для однородных массивов. [46]
Переход от неоднородных линейных массивов к многомерным очевиден. Как обычно, мы просто допускаем, что каждый элемент линейного массива может быть другим неоднородным линейным массивом. Поскольку каждый из этих подмассивов может иметь разные дескрипторы, а значит и разное число элементов разного типа, результирующая структура будет иметь форму дерева. [47]
Расширение понятия линейного массива на более сложные многомерные структуры приводит нас к матрицам и массивам более высокой размерности, деревьям, записям и списковым структурам в зависимости от характера расширения. Однако во всех этих расширениях используется одна основная идея: элемент линейного массива сам может быть линейным массивом. Мы рассмотрим основные свойства линейных массивов и их многомерных расширений в порядке увеличения сложности, начиная с обычных однородных массивов фиксированного размера, существующих в Фортране, Алголе и многих других языках. [48]
В языках программирования существует большое разнообразие форм данных, которые может определить программист. Несмотря на то, что большинство языков обеспечивает представление того или иного вида числовых данных и какую-то форму линейных массивов, особого единообразия в отношении других типов данных незаметно. Такое разнообразие не удивительно, поскольку часто одним из основных мотивов разработки нового языка программирования является потребность в непосредственной работе с каким-либо типом структур данных, непредусмотренным в существующем языке. [49]
Файлы с прямым доступом организованы в виде множества неупорядоченных записей. Доступ осуществляется с помощью адреса, указывающего положение записи во внешней памяти; например, номер дорожки диска. Файл выглядит как линейный массив записей, доступных только по адресу, который понимает аппаратура. Указатель текущей записи излишен, поскольку каждая операция доступа требует указания адреса нужной записи. [50]
Расширение понятия линейного массива на более сложные многомерные структуры приводит нас к матрицам и массивам более высокой размерности, деревьям, записям и списковым структурам в зависимости от характера расширения. Однако во всех этих расширениях используется одна основная идея: элемент линейного массива сам может быть линейным массивом. Мы рассмотрим основные свойства линейных массивов и их многомерных расширений в порядке увеличения сложности, начиная с обычных однородных массивов фиксированного размера, существующих в Фортране, Алголе и многих других языках. [51]
Нередко в задачах предъявляются такие требования к представлению данных, которые исключают использование массивов фиксированного размера. Данные могут поступать с устройства ввода в неизвестном заранее количестве, или они могут генерироваться внутри программы непредсказуемым образом. Для естественного представления таких данных и манипулирования ими во многих языках допускаются линейные массивы, которые могут динамически расти и сокращаться во время выполнения программы. Для таких массивов переменной размерности известно много различных названий, приведем лишь некоторые из них: стеки, очереди, множества, списки, таблицы. Логическая организация таких массивов не слишком отличается от логической организации массивов фиксированного размера; однако их переменный размер приводит к другим представлениям в памяти и другим методам доступа, в частности используется метод связанного представления, который в описанных выше случаях применяется редко. [52]