В Камаев - Технологии программирования

По признаку физического размещения структуры данных различают оперативные и файловые структуры. Структуры данных, размещаемые в оперативной памяти, называют оперативными структурами. Файловые структуры соответствуют структурам данных внешней памяти. Оперативная память является быстрой, а внешняя — медленной.

Часто, говоря о той или иной структуре данных, имеют в виду ее логическое представление. Физическое представление может не соответствовать логическому и, кроме того, может существенно различаться в разных программных системах. Нередко физическая структура помимо данных содержит скрытый от программиста дескриптор или заголовок, содержащий общие сведения о физической структуре. Наличие особых данных дескриптора позволяет осуществлять контролируемый на предмет ошибок доступ к необходимым порциям данных.

Статический массив — такая структура данных, которая характеризуется:

1) фиксированным набором элементов одного и того же типа;

2) каждый элемент имеет уникальный набор значений индексов;

3) количество индексов определяет мерность массива, например, два индекса — двухмерный массив, или матрица, три индекса — трехмерный массив, один индекс — одномерный массив, или вектор;

4) обращение к элементу массива выполняется по имени массива и значениям индексов для данного элемента.

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

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

Статическая запись — конечное упорядоченное множество полей, характеризующихся различным типом данных. Записи являются чрезвычайно удобным средством для представления программных моделей реальных объектов предметной области, ибо, как правило, каждый такой объект обладает набором свойств, характеризуемых данными различных типов.

Полем записи может быть, в свою очередь, интегрированная структура данных — вектор, массив или другая запись.

Важнейшей операцией для записи является операция доступа к выбранному полю записи — операция квалификации. Практически во всех языках программирования обозначение этой операции имеет вид

<���имя переменной — записи>.<���имя поля>

В ряде прикладных задач программист может столкнуться с группами объектов, чьи наборы свойств перекрываются лишь частично. Для задач подобного рода развитые языки программирования предоставляют в распоряжение программиста записи с вариантами (union в С, case в Turbo Pascal).

Строка — это линейно упорядоченная последовательность символов, принадлежащих конечному множеству символов, называемому алфавитом. Говоря о строках, обычно имеют в виду текстовые строки — строки, состоящие из символов, входящих в алфавит

какого-либо выбранного языка, цифр, знаков препинания и других служебных символов.

Базовыми операциями над строками являются:

• определение длины строки;

• присваивание строк;

• конкатенация (сцепление) строк;

• выделение подстроки;

• поиск вхождения.

Операция определения длины строки имеет вид функции, возвращаемое значение которой является целым числом, равным текущему числу символов в строке.

Операция присваивания имеет тот же смысл, что и для других типов данных.

Сравнение строк производится по следующим правилам: сравниваются первые символы двух строк. Если символы не равны, то строка, содержащая символ, место которого в алфавите ближе к началу, считается меньшей. Если символы равны, сравниваются вторые, третьи символы и т. д. При достижении конца одной из строк строка меньшей длины считается меньшей. При равенстве длин строк, а главное при одновременном равенстве всех символов в строках, строки считаются равными.

Результатом операции сцепления двух строк является строка, длина которой равна суммарной длине строк-операндов, а значение соответствует значению первого операнда, за которым непосредственно следует значение второго. Операция сцепления дает результат, длина которого в общем случае больше длин операндов. Как и во всех операциях над строками, которые могут увеличивать длину строки (присваивание, сцепление, сложные операции), возможен случай, когда длина результата окажется большей, чем отведенный для него объем памяти. Эта проблема возникает только в тех языках, где длина строки ограничивается.

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

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

Статическая строка (тип String) в языке Pascal представляет собой одномерный массив, в нулевом элементе которого находится дескриптор с количеством символов в строке, а в последующих элементах — коды символов строки.

Главный недостаток статической строки — неизменность физической длины, что приводит к неэффективному расходу памяти.

Статическая таблица с физической точки зрения представляет собой вектор, элементами которого являются записи. Ранее было отмечено, что полями записи могут быть интегрированные структуры данных — векторы, массивы, другие записи. Аналогично и элементами векторов и массивов могут быть также интегрированные структуры. Одна из таких сложных структур — таблица. Частой, характерной логической особенностью таблиц является то, что доступ к элементам таблицы производится не по номеру (индексу), а по ключу — по значению одного из свойств объекта, описываемого записью-элементом таблицы. Ключ — это свойство, идентифицирующее данную запись во множестве однотипных записей. Как правило, к ключу предъявляется требование уникальности в данной таблице. Ключ может включаться в состав записи и быть одним из ее полей, но может и не включаться в запись, а вычисляться по положению записи. Таблица может иметь один или несколько ключей. Например, при интеграции в таблицу записей о студентах выборка может производиться как по личному номеру студента, так и по фамилии.