在Java中使用链表来表示一个稀疏矩阵

我正在做一个小程序来表示稀疏矩阵（一个有很多元素等于零的矩阵）。它代表像this第108页（我认为看这个数字就足以理解它），它使用链表。在Java中使用链表来表示一个稀疏矩阵

[如果你理解了数字不要阅读本段]必须存储的零只不同的元素，保存行和元素的列，如下链接它们。矩阵的第一个元素必须具有它的维度;它链接到一个节点，该节点表示具有不同零元素的第一行，并且该元素链接到两个节点：矩阵本身的元素（链接在右侧）和下一行的元素不为零。这样，整个矩阵就构成了。

好吧我有问题思考每个类的变量。我有两个：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中存储任何内容。由于sparce矩阵的目的不是在记忆中使用非平民空间，我在询问关于记忆的使用。这意味着nextRowLink = null;？，value是一个本地变量，所以它需要64位，即使它是value = 0 or Double.NaN;。

这是比我想的更好的方法吗？

来源

2011-03-24 Roger

我会做这样的：链表的链表

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指针跳过不必要的“头”节点。

如果您知道每一行（列）至少包含一个值，请切换到列（行）列表的数组。

来源

2011-03-24 22:04:48

最后一个RowNode必须链接到ColumnNode，因为它们是不同的类，所以存在问题？看看这个图（http://books.google.com/books?id=gMcmb-qYODUC&lpg=PR3&dq=roberto%20florez%20algoritmos&hl=es&pg=PA108#v=onepage&q&f=false） – Roger 2011-03-24 22:14:52

@Roger：你可以将两种类型列表循环如果你想要的，就像图中一样：将最后一个'RowNode'的'next'指向其列中的第一个'RowNode'。不过，这需要空节点来支持空行/列。（我没有看到什么算法会受益于此设置...） – 2011-03-24 22:20:34

您可以定义父级Nodo，该父级不包含value字段也不包含nextRowLink字段。然后，您可以定义两个子类：RowHead，其中nextRowLink和NodoConData具有value字段。将第一个用于行头，另一个用于该行的其余节点。

来源

2011-03-24 22:05:57

最后的NodoConData必须链接到RowHead，它们具有相同的父类，但是，没有问题吗？后面的问题怎么样？ 'nextRowLink = null;'和双重对象的内存有什么用处。 – Roger 2011-03-24 22:20:29

在Java中使用链表来表示一个稀疏矩阵

回答

相关问题