通过链表

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

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

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