Логическая и физическая структуры данных

Структурой данных (data structure) называют совокупность (множество) данных и отношений между ними. Один и тот же набор данных можно представить по-разному. Пусть имеется пять данных типа Char: ¢А¢, ¢B¢, ¢С¢ , ¢D¢ и ¢Е¢. Из этой совокупности значений можно сформировать как линейную последовательность элементов, так и дерево или сеть, как показано на рисунке 1.3.

Как видно из рисунка 1.3, способ построения структур данных определяется характером связей между элементами. Все связи одного элемента данных с другими образуют элемент отношений. Пару, содержащую элемент данных и ассоциированный с ним элемент отношений, называют элементом структуры данных. Заметим, что элементом структуры данных может быть другая структура данных, например, элементом сети может быть запись.

Рисунок 1.3 – Представление множества из пяти элементов разными структурами:

а – линейная последовательность, б – дерево, в - сеть

Графическое представление структур данных, подобное представлению на рисунке 1.3, называется графом. Графовое представление часто используют на практике для показа логической структуры. Вершины графа соответствуют элементам данных, а ребра – отношениям между этими элементами.

Используя термин «структура данных», следует различать понятия логической и физической структур. Логическаяструктура - это абстрактная схема расположения данных, которую представляет себе пользователь или программист.Физическая структура – это способ (или схема) конкретного размещения данных в памяти вычислительной машины. Физическую структуру иногда называют структурой хранения. В общем случае логическая и физическая структуры одних и тех же данных не совпадают. Например, последовательность записей, имеющая логическую структуру, изображенную на рисунке 1.4, представляется программисту как непрерывная последовательность строк одинакового размера.

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

Рисунок 1.4 – Логическая структура таблицы

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

Одна и та же логическая структура может по-разному храниться в памяти разных ЭВМ (различная конфигурация памяти) или для разных компиляторов.

Рисунок 1.5 – Логическая (а) и физическая (б) структуры матрицы типа Word