Линейные структуры

К линейным структурам относятся массивы, последователь­ности, таблицы.

Порядок следования (и, соответственно, выборки) элементов таких структур имеет линейный характер и соответствует поряд­ку расположения элементов в памяти: один за другим без ка­ких-либо промежутков. Адрес элемента соответствует его поло­жению и определяется индексом - порядковым номером эле­мента в последовательности размещения. К элементу имеется прямой доступ, если известен его индекс.

Особенностью линейной структуры является то, что при по­следовательной организации (размещении) она допускает воз­можность прямого доступа к произвольному элементу, посколь­ку условие однородности (однотипности) предполагает, что все элементы занимают расположенные строго последовательно об­ласти одинакового размера, что и позволяет достаточно просто вычислять значение физического адреса элемента по значению его индекса.

Массив представляет собой совокупность однотипных элемен­тов, причем число элементов массива известно до его размещения, что позволяет строить гибкие многомерные системы адресации.

Последовательность, так же, как и массив, представляет со­бой совокупность однотипных элементов. Однако число элемен­тов до размещения неизвестно.

И, хотя каждая конкретная последовательность имеет конечную длину, до начала обработки (и, соответственно, размещения) необходимо считать длину после­довательности бесконечной. Принципиальность такого предпо­ложения выражается в том, что необходимо предусматривать специальную процедуру использования памяти (выделения/осво­бождения) и, возможно, алгоритм обработки последовательности по частям.

Важность рассмотрения такого типа данных обуслов­лена тем, что именно он превалирует в операциях ввода/вывода с устройствами внешней памяти. Именно последовательный дос­туп позволяет организовать «потоковые» операции: однородность позволяет рассматривать пересылаемые данные как непрерыв­ный поток. Поток не может быть прерван по контекстно опреде­ляемому условию, например, при пересылке текста - по значе­нию кода «перевод строки», и это не заставляет программу ана­лизировать значение каждого очередного элемента. И, кроме того, последовательный доступ - это простота управления памя­тью и устройством ввода-вывода.

Таблица - это последовательности, обычно представляемые строками - совокупностями разнотипных элементов. Или, ина­че, таблица - это множество записей, каждая из которых пред­ставляет набор поименованных полей.

Однако с точки зрения размещения элементов таблица мо­жет быть представлена как одномерный массив (или, в случае БД — последовательность) с однородными композиционными элементами, каждый из которых представляет собой совокуп­ность разнотипных элементов. Именно это позволяет свести ввод/вывод таких типов структур к последовательным элемен­тарным операциям.

Кроме того, разнотипность элементов позволяет ввести отлич­ную от перечислительной схему идентификации записей, опреде­лив одно из полей как ключ записи. Обычно ключ содержит зна­чение, используемое в процедурах упорядочения и поиска записей.