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

Данные

Введение

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

If a > b[i] Then a:= 0;

описаны действия, в которых «участвуют» переменные a, i, элемент массива b[i] и константа 0. Эти информационные объекты и являются данными.

Данные и команды хранятся в памяти компьютера в двоичном коде. Этот код занимает часть памяти, называемую ячейкой или слотом памяти. Местоположение каждой ячейки определяется ее адресом. В оперативной памяти минимальная двоичная ячейка, имеющая собственный уникальный адрес, – это последовательность восьми битов, т. е. байт. Обычно ячейка, предназначенная для хранения индивидуального данного, состоит из нескольких последовательных байтов, т. е. из нескольких адресуемых ячеек.

При компиляции программы программа-компилятор выполняет, в частности, следующие действия:

1) каждому данному выделяется своя ячейка памяти,

2) каждый оператор, записанный на языке высокого уровня, представляется последовательностью машинных команд (или одной командой), которые содержат адреса тех данных, с которыми эти команды оперируют (именно поэтому данные часто называют операндами).

Каждое данное относится к одному из конечного множества типов, допустимых для конкретной версии языка программирования. Программистам хорошо известны данные таких типов как Byte (байтовый), Integer (целый), Rеаl(вещественный), Boolean (логический), Char (символьный). Значение любого данного этих типов логически неразделимо, поэтому такие данные называются неструктурированными или примитивными данными. Неструктурированные данные служат для построения структур данных: записей, массивов, деревьев, файлов и т. д.

Биты в байте нумеруются от 0 до 7, при этом бит с номером 0 является самым младшим битом. При схематическом изображении ячейки, состоящей из одного или нескольких байтов, самый младший бит принято располагать на правом конце ячейки, и старшинство битов увеличивается при приближении к левому концу. На рисунке 1.1 показано схематичное изображение байта, содержащего значение 5 в прямом двоичном коде.

Рисунок 1.1 – Нумерация битов в байте

Два байта со смежными адресами образуют слово (word) разрядностью 16 бит, два смежных слова образуют двойное слово (double word). У четверенное слово (quad word), образуемое последовательностью из восьми байт, имеет разрядность 64 бита. Биты ячеек, состоящих более чем из одного байта, нумеруются от 0, до общего количества битов минус 1, например, самый старший бит учетверенного слова имеет номер 63

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

Рисунок 1.2 – Пример представления двойного слова

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

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

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

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

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

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

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

Запись 1

Запись 2

...

Запись N

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

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

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

						Ячейка ОЗУ	Адрес (смещение)
	a	x [0, 0]	x [0, 1]		б	x [0, 0]	$0A56
		x [1, 0]	x [1, 1]			x [0, 1]	$0A58
		x [2, 0]	x [2, 1]			x [1, 0]	$0A5А
						x [1, 1]	$0A5С
						x [2, 0]	$0A5Е
						x [2, 1]	$0A60

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

Дата добавления: 2014-01-07