稀疏矩阵表示

Question

我有 2 个关于稀疏矩阵表示的问题。

基于我上面提供的矩阵示例，我需要提出一个表示稀疏矩阵的解决方案。

我想用链表表示稀疏矩阵。

你们能为我的两个问题建议一个合适的算法吗？提前致谢

Answer 1

表示稀疏对象的方法有很多，虽然所有方法都可以用任何语言实现，但有些语言比其他语言更擅长实现某种表示。一些表示可以提高存储效率，但在矩阵运算上速度较慢，而另一些则提供更快的矩阵运算，但存储要求更大。

例如：

1. 键为非零元素 row/column 的值的散列，例如 Matrix.hash[(i,j)]、Matrix.hash[(i,j)] = n
2. 非零行链表，每一项都是一个非零列链表。例如 Matrix.rows.get(i).get(j)、Matrix.rows.set(i, (j, n))
3. 压缩行 space 表示，CSR（参见下面的参考资料）

参考文献和示例：

1. Sparse Matrix and its representations | Set 1 (Using Arrays and Linked Lists)
2. Sparse Matrix and its representations | Set 2 (Using List of Lists and Dictionary of keys)
3. Sparse Matrix Representations | Set 3 ( CSR )

要显示稀疏矩阵的内容，只需简单地循环：

for all rows i=1 to n:
    for all columns j=1 to m:
        if Matrix.has(i,j): display Matrix.get(i,j)
        else: display 0
    display newLine

注意，根据选择的表示，打印循环可能会优化一点，当然它必须遍历所有行和列，但是，例如，.has 和 .get 操作可以合并为一个优化的 .get 等等..

更新问题：

对于list of lists表示，伪代码插入一个新的非零值n在行i列j 将类似于以下内容：

function insert(matrix, n/*value*/, i/*row*/, j/*column*/)
{
    row = matrix.rows, prevrow = null;
    while(null!=row && row.index<i) { prevrow=row; row=row.next; }
    if ( !row )
    {
       if ( prevrow )
       {
           // rows with indexes less than i
           prevrow.next = {
               index:i,
               columns:{
                  index:j,
                  value:n,
                  next:null
               }, 
               next:null
            };
       }
       else
       {
           // empty matrix
           matrix.rows = {
               index:i,
               columns: {
                  index:j,
                  value:n,
                  next:null
               }, 
               next:null
            };
       }
    }
    else if ( row.index == i )
    {
        // insert column to existing row i
        col = row.columns; prevcol = null;
        while(null!=col && col.index<j){ prevcol=col; col=col.next; }
        if ( !col )
        {
           if ( prevcol )
           {
               // row with column indexes less than j
               prevcol.next = {
                  index:j,
                  value:n,
                  next:null
              };
           }
           else
           {
            // empty row
               row.columns = {
                  index:j,
                  value:n,
                  next:null
               };
           }
        }
        else if ( col.index == j )
        {
            // change value to existing column j
            col.value = n;
        }
        else
        {
            // insert new column at right place
            if ( prevcol )
            {
               prevcol.next = { 
                  index:j,
                  value:n,
                  next:col
               };
            }
            else
            {
                row.columns = {
                  index:j,
                  value:n,
                  next:col
                };
            }
        }
    }
    else
    {
        // insert new row/column at right place
        if ( prevrow )
        {
            prevrow.next = { 
              index:i,
              columns:{
                 index:j,
                 value:n,
                 next:null
              },
              next: row
           };
        }
        else
        {
            matrix.rows = {
                index:i,
                columns:{
                   index:j,
                   value:n,
                   next:null
                },
                next:row
            };
         }
    }
}

对于list of lists表示，打印循环可能会像下面这样（伪代码）进行优化：

function print(matrix, n/*rows*/, m/*columns*/)
{
    row = matrix.rows;
    for(i=0; i<n; i++)
    {
        if ( !row || (row.index > i) )
        {
            for(j=0; j<m; j++) print('0 ');
        }
        else if ( row.index == i )
        {
            col = row.columns
            for(j=0; j<m; j++)
            {
                if ( !col || (col.index > j) )
                {
                    print('0 ');
                }
                else if ( col.index == j )
                {
                    print(string(col.value)+' ');
                    col = col.next;
                }
            }
            row = row.next;
        }

        print("\n"); // print new line
    }
}