Java稀疏矩阵创建

Question

我目前正在创建一个使用 SparseMatrixNode 的稀疏矩阵程序:

 public SparseMatrixNode(int row, int col, int value, SparseMatrixNode down, SparseMatrixNode across)
  {
      this.row = row;
      this.col = col;
      this.value = value;
      this.down = down;
      this.across = across;
  }

我的程序创建模板稀疏矩阵，如下所示:

  public SparseMatrix()
  {
    noofrows=noofcols=0;    
    // create the top-left entry point cell
    root=new SparseMatrixNode(0, 0, 0, new SparseMatrixNode(0, 0, 0, null, null), new SparseMatrixNode(0, 0, 0, null, null));
  }     


  public void Create(int noofrows, int noofcols)
  {
      this.noofrows=noofrows;
      this.noofcols=noofcols;
      root=new SparseMatrixNode(0, 0, 0, new SparseMatrixNode(noofrows+1, 0, 0, null, null), new SparseMatrixNode(0, noofcols+1, 0, null, null));
  }

这是我的 SetValue 函数，它采用提供的三个整数值来替换当前值或创建一个新节点并将其插入到稀疏矩阵中。

 public void SetValue(int row, int col, int value)
  {     
      if (value == 0)
      {
          return;
      }
      else
      {
          SparseMatrixNode checkNode = FindNode(row, col);
          if (checkNode.value != 0)
          {
              checkNode.setValue(value);
          }
          //SparseMatrixNode dummyRow = root.FindRow(row);
          if (root.down.row == 5)
          {
              root.down = new SparseMatrixNode(row, 0, 0, null, new SparseMatrixNode(row, col, value, null, null));
              root.across = new SparseMatrixNode(0, col, 0, new SparseMatrixNode(row, col, value, null, null), null);
          }          
      }

但是，当我基于 4x4 网格测试代码并调用 SetValue(1, 2, 5) 时，它只是输出一个由 0 组成的网格。 我一直在尝试单步执行我的代码并找出为什么它不输入新节点，但是我已经被困了几个小时，并且想知道是否有人可以阐明这种情况？

所以我的问题是:为什么我的 SetValue 函数不创建一个新节点并将其链接到跨属性和下属性(第 0 行第 0 列)的“虚拟”节点？

Answer 1

如果不显示Find方法和负责打印的代码，很难说哪里出了问题。

但是，您的方法对我来说似乎有点令人费解。我发现使用位置到值的 Map 更容易(这就是所谓的键表示字典)。值得注意的是，稀疏矩阵可能有更有效的存储格式，具体取决于您要执行什么操作。列出了一些典型的例子here .

下面是键字典方法的一个工作示例。

import java.util.*;

class Position {
    private Integer row, col;

    public Position(int row, int col)
    {
        this.row = row;
        this.col = col;
    }

    @Override
    public boolean equals(Object o) {
        if (!(o instanceof Position))
            return false;
        Position other = (Position)o;
        return row == other.row && col == other.col;
    }

    @Override
    public int hashCode() {
        return 31 * row.hashCode() + col.hashCode();
    }

    @Override
    public String toString() {
        return String.format("(%d, %d)", row, col);
    }

}

public class SparseMatrix {

    private Map<Position, Integer> nnzs = new HashMap<>();
    private int maxRows, maxCols;

    public SparseMatrix(int maxRows, int maxCols) {
        this.maxRows = maxRows;
        this.maxCols = maxCols;
    }

    public void SetValue(int row, int col, int value) {     
        if (row > maxRows || col > maxCols)
            throw new RuntimeException("Position out of bounds");
        nnzs.put(new Position(row, col), value);
    }

    public static void main(String[] args) {
        SparseMatrix sp = new SparseMatrix(10, 10);
        sp.SetValue(1, 2, 5);
        System.out.println(sp.nnzs);
        sp.SetValue(1, 2, 7);
        sp.SetValue(1, 10, 8);
        System.out.println(sp.nnzs);
    }
}

输出:

javac SparseMatrix.java && java SparseMatrix
{(1, 2)=5}
{(1, 2)=7, (1, 10)=8}