Cтраница 1
Линейный массив с взаимодействиями между ближайшими соседями впервые описан Лизингом. [1]
Однородный, линейный массив фиксированного размера называется вектором. Логически вектор организован как последовательность элементов данных, к каждому из которых возможен индивидуальный доступ с помощью целого индекса, указывающего позицию элемента в последовательности. Индивидуальные элементы данных, входящие в эту последовательность, могут заменяться новыми с помощью присваивания, но число элементов изменяться не может. Более того, все элементы данных имеют один и тот же дескриптор, задающий тип данных, длину и любые другие атрибуты элемент тов. [2]
На данный линейный массив ( список) может быть только один указатель, хранящийся в другом массиве, и не допускается циклически связанных структур. Таким образом, каждый список может быть подсписком только одного списка. [3]
Расширение понятия линейного массива на более сложные многомерные структуры приводит нас к матрицам и массивам более высокой размерности, деревьям, записям и списковым структурам в зависимости от характера расширения. Однако во всех этих расширениях используется одна основная идея: элемент линейного массива сам может быть линейным массивом. Мы рассмотрим основные свойства линейных массивов и их многомерных расширений в порядке увеличения сложности, начиная с обычных однородных массивов фиксированного размера, существующих в Фортране, Алголе и многих других языках. [4]
Переход от неоднородных линейных массивов к многомерным очевиден. Как обычно, мы просто допускаем, что каждый элемент линейного массива может быть другим неоднородным линейным массивом. Поскольку каждый из этих подмассивов может иметь разные дескрипторы, а значит и разное число элементов разного типа, результирующая структура будет иметь форму дерева. [5]
ТКМ задается линейным массивом, в котором информация о геометрических элементах контура располагается последовательно, в порядке обхода контура. Порядок обхода контура определяется описанием детали и отражает его топологию. Для системы не важен порядок обхода контура ( по или против часовой стрелки), важна упорядоченность элементов контура. [6]
Если А - линейный массив, то доступ к А [2], второму элементу А, может потребоваться для того, чтобы ( 1) получить элемент данных, хранящийся там, или ( 2) найти позицию элемента массива, чтобы можно было записать туда новый элемент данных. Первая операция называется доступом к значению, вторая - доступом к позиции. Доступ к позиции - это более универсальная операция, поскольку зная позицию элемента, обычно не составляет труда извлечь значение, хранящееся в ней. В большинстве языков программирования оба типа операции доступа имеют однаковый синтаксис, например А [2] в инструкции X: А [2] Y представляет операцию доступа к значению, в то время как А [2] в инструкции A [2]: X Y представляет операцию доступа к позиции. При обсуждении методов доступа к структурам данных мы будем в основном рассматривать доступ к позиции, за исключением тех случаев, где явно оговаривается противное. [7]
Для представления в памяти линейных массивов этого типа, как и в случае векторов, используется последовательное представление: битовые цепочки, изображающие индивидуальные элементы, хранятся последовательно в одном блоке памяти. Вследствие вариаций типа элементов, дескриптор для такого массива должен быть более сложным, чем для вектора. Однако присутствие во время трансляции полного описания, а также обсуждаемые ниже ограничения, накладываемые иа доступ, обычно делают ненужным хранение полного дескриптора. [8]
Довольно легко перейти от линейных массивов переменного размера к многомерным структурам, если допустить, что элемент массива может служить указателем на другой массив. А это обычно допускается, когда для линейных массивов используется связанное представление. [9]
Окно W длины w является линейным массивом из w ячеек Jfo, Xw -, каждая из которых может содержать символы из ленточного алфавита М или запрашивающий символ. Каждому окну W ставится в соответствие целое число, называемое позицией W. Передней ячейкой окна W является Xw -, которая представляет ячейку C ( p - - w - 1); задней ячейкой является XQ. [10]
Основная память МП ВМ80 рассматривается как линейный массив, состоящий из 64К байт. Формируемый микропроцессором 16-разрядный адрес дает ему возможность адресовать любой байт памяти. Слова в памяти хранятся в двух соседних байтах. В байте с младшим адресом хранится младшая половина слова, а в байте со следующим адресом - старшая. Адресом слова служит адрес его младшего байта. [11]
Поскольку большинство современных ЭВМ способно распознавать линейные массивы знаков, было разработано несколько методов представления структурных формул в эту удобную для обработки на ЭВМ форму. [12]
ПЛ / 1, которая представляет собой неоднородный линейный массив из двух элементов. [13]
Какое представление в памяти подходит для линейного массива, элементы которого могут динамически менять свою длину во время выполнения программы. Ясно, что простое последовательное представление, применявшееся для линейных массивов до сих пор, не годится, поскольку каждое новое присваивание может потребовать, чтобы более длинная цепочка битов заняла место более короткой, что привело бы к перестановке других элементов массива. Отметим, что число элементов в массиве постоянно в течение всего времени выполнения программы; может изменяться только длина индивидуальных элементов. В этих условиях удобно следующее представление: представим массив вектором указателей на значе ния и будем хранить цепочки битов, представляющие значения, в каком-то другом месте памяти. Вектор указателей может тогда храниться ноеледовательно, поскольку размер каждого указателя является постоянной величиной и не зависит от типа значения, на которое он указывает. [14]
Таблицы в языке Снобол 4 - это неоднородные линейные массивы переменного размера, для доступа к которым в качестве индексов могут использоваться не только целые числа, но и произвольные цепочки. Таким образом, таблицы представляют собой некую разновидность списка свойств. Каждый элемент таблицы состоит из индекса, являющегося указателем на цепочку в центральной таблице цепочек, и значения, которое является числом или указателем на цепочку, массив или иной элемент данных. Для создания таблиц используется примитивная функция TABLE, аргументы которой определяют начальный размер таблицы и величину приращения. [15]