Представление разреженной матрицы в Java с использованием связанных списков - PullRequest
Новая
       18

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

1 голос
/ 25 марта 2011

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

[ Не читайте этот параграф, если вы понимаетеfigure ]
Он должен хранить только элементы, отличные от нуля, сохранять строку и столбец элемента и связывать их следующим образом.Первый элемент матрицы должен иметь его размеры;он связан с узлом, который представляет первую строку с элементом, отличным от нуля, и этот элемент связан с двумя узлами: элементом самой матрицы (ссылки справа) и следующей строкой, которая имеет элемент, отличный от нуля,Таким образом, вся матрица построена.

Хорошо, у меня проблемы с размышлениями о переменных каждого класса.У меня есть два: Node и Matrix. 

public class Node {
    int row;
    int column;
    double value;
    Nodo columnLink;
    Nodo rowLink;
    Nodo nextRowLink;
}

public class Matrix{
    Nodo head;
    Nodo first;
    Nodo last;
}

Это лучший путь?Я имею в виду, что когда это головной узел, он ничего не хранит в value, а когда это ненулевой элемент, он ничего не хранит в nextRowLink.Я спрашиваю об использовании памяти, так как цель разреженной матрицы состоит в том, чтобы не использовать ненужное пространство в памяти.Что означает, что nextRowLink = null; ?, value является нативной переменной, поэтому она занимает 64 бита, даже если она value = 0 or Double.NaN;.

Это лучший способ, чем тот, о котором я думаю?

Ответы [ 2 ]

2 голосов
/ 25 марта 2011

Я бы сделал это так: связанный список связанных списков 

class SparseMatrix {
    ColumnNode head;
    int dimx, dimy;
    // other members
}

class ColumnNode {
    int colNum;
    RowNode head;
    ColumnNode next;
}

class RowNode {
    int rowNum;
    double value;
    RowNode next;
}

, который имеет несколько «более тонкие» узлы, его легче получить с помощью системы типов и позволяет пропустить ненужные «головные» узлы с помощью указателей head.

Если вы знаете, что каждая строка (столбец) содержит хотя бы одно значение, переключитесь на массив списков столбцов (строк).

0 голосов
/ 25 марта 2011

Вы можете определить родительский класс Nodo, который не содержит ни поля value, ни поля nextRowLink. Затем вы можете определить два подкласса: RowHead с nextRowLink и NodoConData с value полем. Используйте первый для заголовка строки, а другой - для остальных узлов в строке.

...