c++ - 用链表表示矩阵

Question

问题是:

An alternative linked representation for sparse matrices uses nodes that have the fields down, right, roe, col, and value. Each nonzero entry of the sparse matrix is represented by a node. The zero terms are not explicitly stored. The nodes are linked together to form two circular lists. The first list, the row list, is made up by linking nodes by rows and within rows by columns using the right eld. The second,list, the column list, is made up by linking nodes via the down field. In this list, nodes are linked by columns and within columns by rows. These two lists share a common header node. In addition, a node is added to the dimensions of the matrix.

我希望重载运算符>>，同时添加和转置方法:

 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。不过，这又很慢。这是一个提示:如果输入以任何方式排序，您可以利用它来更快地构建矩阵。即使没有，一种更有效的执行任意节点插入的方法也会使事情变得更好。