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

Пусть массив А[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. Деревьяи ориентированные графы удобнее всего отображать сетями (в виде мультисписков), а также, используя специальные формы записи, деревья можно хранить в виде векторов, что широко используется в трансляторах.

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