representing matrix by linkedlist

The problem is:

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. Th开发者_如何学JAVAe 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.

I hope to overload operator >> and also add and transpose methods:

 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.

I cannot figure out a solution. Could anyone provide some advice? Thank you very much!

For transpose, you could traverse one list, swapping all the links and row/col pointers. In pseudocode:

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

Here's addNode, one (inefficient) solution is to add individual nodes by traversing both lists until you find the insertion point for your node, and then add it there. It can be used on every node in a second matrix to implement something like +=; adding a copy of the current matrix first gives 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

There are much more efficient ways to implement add but those are left as an exercise to the reader.

operator>> should look more or less like this:

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);
   }

}

You could use an algorithm like the above to implement addNode. Again, that's very slow, though. Here's a hint: if the input is sorted in any way, you can take advantage of that to make building the matrix much faster. Even if not, a more efficient way of doing arbitrary node inserts will make things better.