Представление разреженных матриц методом связанных структур

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

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

Рис. 3.4. Формат вершины для представления разреженных матриц

Для представления разреженных матриц требуется базовая структура вершины (рис.3.4), называемая MATRIX_ELEMENT ("элемент матрицы"). Поля V, R и С каждой из этих вершин содержат соответственно значение, индексы строки и столбца элемента матрицы. Поля LEFT и UP являются указателями на следующий элемент для строки и столбца в циклическом списке, содержащем элементы матрицы. Поле LEFT указывает на вершину со следующим наименьшим номером строки.

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

Головная вершина каждого списка строки содержит нуль в поле С; аналогично каждая головная вершина в списке столбца имеет нуль в поле R. Строка или столбец, содержащие только нулевые элементы, представлены головными вершинами, у которых поле LEFT или UP указывает само на себя. Может показаться странным, что указатели в этой многосвязной структуре направлены вверх и влево, вследствие чего при сканировании циклического списка элементы матрицы встречаются в порядке убывания номеров строк и столбцов. Такой метод представления используется для упрощения включения новых вершин в структуру.

Рис. 3.5. Многосвязная структура для представления матрицы А

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

Массивы C#

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

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