在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中使用鏈表來表示一個稀疏矩陣

回答

相關問題