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

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

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

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

Хранение массива в виде вектора

Пусть массив А[i_n, k_n] хранится в памяти машины в виде одномерного вектора B[N], где

Элементы массива А можно отобразить в массив В двумя способами: строками, когда наиболее быстро меняется последний индекс; столбцами, когда наиболее быстро меняется первый индекс (строки и столбцы, естественно, имеют буквальный смысл только для двумерных массивов).

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

где при отображении строками

D_n = 1 и D_m = (k_m+1 - i_m+1 +1) D_m+1

m=n -1,...,1,

а при отображении столбцами

D₁ = 1 и D_m = (k_m-1 - i_m-1 +1) D_m-1

m=2,...,n,

Формула определения адреса хранения элемента A[j₁, .... j_n] в случае, когда вектор В имеет базу b (адрес):

Постоянная величина с, как и коэффициенты D_m, зависит только от значений граничных пар в описании массива А.

Для вычисления адреса элемента произвольного массива А необходимо знать базу отображающего вектора b, размерность массива N и N целых чисел.

При отображении строками это – коэффициенты:

с, D₁, ..., D_n-1

коэффициент D_n всегда равен единице.

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

В программе может быть несколько массивов. Для распределения памяти под массивы необходимо знать число элементов N в каждом массиве.

Величину N можно вычислить из формулы

D_m = (k_m+1 - i_m+1 +1) D_m+1

при m=0

N = D₀ = (k₁—i₁+1) D₁

где N – размерность массива, с, D₀, D₁, ...,D_n-1 — коэффициенты, i₁, k₁ .., i_n, k_n – значения граничных пар, которые зависят только от описания массива, обычно хранятся в виде, так называемого, определяющего вектора массива. Для массивов с одинаковыми описаниями определяющие векторы равны.

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

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

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

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