Представление данных в памяти ЭВМ

Данные хранятся в памяти компьютера. При этом различают логическую (в программе) и физическую (в памяти) структуры данных. Эффективность алгоритмов зависит от того, насколько согласованы обе эти структуры.

Память современных ЭВМ имеет линейную организацию. Она представляет собой последовательность ячеек (строк). Наименьшей адресуемой единицей является байт. Данные имеют размер, равный 1 или нескольким байтам. Память для них выделяется компилятором.

Так для простых (скалярных) типов данных в разных компьютерах и языках программирования используются следующие объемы памяти.

a) Булевский тип – 1 байт (причем для задания значений «истина» или «ложь» достаточно 1 бита, оно берется из младшего разряда байта);

b) Символьный – 1 байт (в java – 2 байта);

c) Целочисленный – 2 или 4 байта;

d) Вещественный – 4 или 8 байт;

e) Строковый – до 256 байт.

Сложные типы могут размещаться в смежных ячейках памяти или произвольно.

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

Имя

Адрес (элемент(index)) = Начало + размер_ячейки * index.

Такой подход облегчает работу с массивом. Его элементы могут обрабатываться последовательно или в любом порядке.

Линейные списки обычно располагаются в памяти последовательно (как массивы). Этот порядок часто нарушается при выполнении операций вставок и удалений.

Связные списки требуют дополнительного объема памяти для размещения таблицы связей. В них более просто реализуются операции вставки и удаления элементов.

Деревья представляют собой связные списки соответствующей структуры. Они хранятся аналогично.

Графы и таблицы принято представлять таблицами связности, смежности и др., т.е. двумерными массивами.

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

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

Наиболее простой и естественный способ обработки данных всех типов – последовательный. Массивы, таблицы и файлы могут также обрабатываться в любом (произвольном) порядке. Для списков используется только последовательный доступ. При этом добавление и удаление элементов возможно в любом месте списка.

Дата добавления: 2015-07-11