Отображение структур данных в структуры хранения

Сети.

Список.

Вектор.

Структуры хранения данных

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

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

Минимальный элемент хранения данных – бит — является одним двоичным разрядом.

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

Для получения адреса элемента a_i необходимо к базе вектора прибавить величину i - 1.

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

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

Списковые структуры используются:

· когда в памяти компьютера требуется разместить несколько динамически изменяющихся массивов (строк, таблиц) с неизвестным заранее числом элементов, что типично для трансляторов;

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

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

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

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

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

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