Некоторые обобщенные представления о структурах данных

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

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

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

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

Разновидностями последовательностей являются также не рассматриваемые здесь очереди и стеки, которые отличаются тем, что для них устанавливаются особые схемы добавления (размещения в памяти) новых элементов и их выборки. Для очереди порядок размещения/выборки определяется правилом «первым размещен — первым выбран», для стека — «первым размещен — последним выбран». Кроме того, выборка элемента влечет его удаление из последовательности.

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

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