Модели и структуры данных



         

Специальные массивы


На практике встречаются массивы, которые в силу определенных причин могут записываться в память не полностью, а частично. Это особенно актуально для массивов настолько больших размеров, что для их хранения в полном объеме памяти может быть недостаточно. К таким массивам относятся симметричные и разреженные массивы.

Симметричные массивы.

Двумерный массив, в котором количество строк равно количеству столбцов называется квадратной матрицей. Квадратная матрица, у которой элементы, расположенные симметрично относительно главной диагонали, попарно равны друг другу, называется симметричной. Если матрица порядка n симметрична, то в ее физической структуре достаточно отобразить не n^2, а лишь n*(n+1)/2 еЯ элементов. Иными словами, в памяти необходимо представить только верхний (включая и диагональ) треугольник квадратной логической структуры. Доступ к треугольному массиву организуется таким образом, чтобы можно было обращаться к любому элементу исходной логической структуры, в том числе и к элементам, значения которых хотя и не представлены в памяти, но могут быть определены на основе значений симметричных им элементов.

На практике для работы с симметричной матрицей разрабатываются процедуры для:

а) преобразования индексов матрицы в индекс вектора,

б) формирования вектора и записи в него элементов верхнего треугольника элементов исходной матрицы,

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

В приложении приведен пример программы для работы с симметричной матрицей.

Разреженные массивы.

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

Различают два типа разреженных массивов:

  • 1) массивы, в которых местоположения элементов со значениями отличными от фонового, могут быть математически описаны;
  • 2) массивы со случайным расположением элементов.




Содержание  Назад  Вперед