用链表表示矩阵

Question

问题是：

稀疏矩阵的另一种链接表示使用具有向下、向右字段的节点， 鱼子、颜色和价值。稀疏矩阵的每个非零条目都被表示 通过一个节点。零项没有显式存储。节点已链接 一起形成两个循环列表。第一个列表，即行列表，已制作完成 通过使用右侧按行链接节点以及按列在行内链接节点来向上 场。第二个列表，即列列表，由通过以下链接链接节点组成 下场。在此列表中，节点按列链接并在列内链接 按行。这两个列表共享一个公共头节点。此外，还有一个 节点被添加到矩阵的维度。

我希望重载运算符>>还添加和转置方法：

 istream & operator>>(istream & in, sparseMatrixLinked<T> x); 
//The input format is as follows. 

4   4   3  //   # of rows, # of cols, # of nonzero entries
0   0   2  // row #, col #, item value #
0   3   1
1   1   7

void sparseMatrixLinked<T>::add(sparseMatrixLinked<T> &b,sparseMatrixLinked<T> &c);
        // c = (*this) + b 


void sparseMatrixLinked<T>::transpose(sparseMatrixLinked<T> &b) ;
// b is transpose of *this.

我无法找出解决方案。有人可以提供一些建议吗？非常感谢！

Answer 1

对于转置，您可以遍历一个列表，交换所有链接和行/列指针。在伪代码中：

set node to header
do {
    swap node.row and node.col
    swap node.right and node.down
    node = node.right
} while node != header;

这里是addNode，一种（低效）解决方案是通过遍历两个列表来添加单个节点，直到找到节点的插入点，然后将其添加到那里。它可以用在第二个矩阵中的每个节点上，以实现类似 +=; 的功能。首先添加当前矩阵的副本给出add。

newnode = allocate node with row, col, val set, pointers null
top = header
while (top.down != header and 
       (top.down.col < newnode.col or
        (top.down.col == newnode.col and
         top.down.row < newnode.row)
       )
    top = header.down
left = header
while (left.right != header and 
       (left.right.row < newnode.row or 
        (left.right.row == newnode.row and 
         left.right.col < newnode.col)
       )
      )
    left = left.right
if top == left
    // if I'm thinking correctly this means newnode is already there
    assert top.row == newnode.row and top.col == newnode.col
    top.val += newnode.val
    delete newnode
else
    newnode.right = left.right
    newnode.down = top.down
    left.right = newnode
    top.down = newnode

有很多更有效的方法来实现 add，但这些方法留给读者作为练习。

operator>> 应该看起来或多或少像这样：

istream & operator>>(istream & in, sparseMatrixLinked<T> x)
{
   x.clear();

   int rows, cols, vals;
   in >> rows >> cols >> vals;
   for (int i = 0; i > vals; i++) {
       int row, col, val;
       in >> row >> col >> val;
       x.addNode(row, col, val);
   }

}

您可以使用上面这样的算法来实现 addNode。不过，这还是很慢。这里有一个提示：如果输入以任何方式排序，您可以利用它来更快地构建矩阵。即使没有，执行任意节点插入的更有效方法也会使事情变得更好。