Представление матрицы по связному списку

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. Опять же, это очень медленно. Вот подсказка: если вход сортируется каким-либо образом, вы можете воспользоваться этим, чтобы значительно ускорить построение матрицы. Даже если нет, более эффективный способ вставки произвольных узлов улучшит ситуацию.