回答

[id:lethevert:20070111:p1]
昔、C++を書いていたこともあったのだけれど、もうすっかり忘れていて、苦労した。なれない言語だと、くだらない間違いでもなかなか見つけられない。
テストコードは、こういう感じで。

Matrix matrix1();
Matrix matrix2();

int main (int argc, char** argv)
 {
   Matrix mat1 = matrix1();
   Matrix mat2 = matrix2();
   cout << endl << "matrix1 =" << endl << mat1;
   cout << endl << "matrix2 =" << endl << mat2;
   cout << endl << "matrix1 + matrix2 =" << endl << (mat1 + mat2);
   cout << endl << "matrix1 * matrix2 =" << endl << (mat1 * mat2);
 }

Matrix matrix1()
 {
   Matrix mat(3);
   return mat.append(2, 1, 1)
             .append(3, 2, 2);
 }

Matrix matrix2()
 {
   Matrix mat(3);
   return mat.append(2, 0, 1)
             .append(1, 1, 0)
             .append(3, 2, 2);
 }

以下、実装。ただ、この実装では、+ と * の計算量には問題があります。存在する要素だけに対して計算するようにすれば、もっと計算量は減る。
ああ、あとメモリリークとかはこの際無視で。（Javaは楽だなぁ。）

typedef int Item;

class Matrix
 {
 private:
   struct Node
    {
      Item data;
      int row;
      int col;
      Node *nextrow;
      Node *nextcol;
      Node(Item i, int r, int c)
       { data = i; row = r; col = c; nextrow = 0; nextcol = 0;}
    };
   int size;
   Node *rows;
   Node *cols;
   bool lt(int a1, int b1, int a2, int b2)
    { return a1 < a2 || (a1 == a2 && b1 < b2);}
 public:
   Matrix(int s)
    { size = s; rows = 0; cols = 0;}
   Matrix &append(Item i, int r, int c)
    {
      Node *n = new Node(i,r,c);
      {
        Node **m = &rows;
        while (*m && lt((*m)->row, (*m)->col, r, c)) m = &((*m)->nextrow);
        n->nextrow = *m;
        *m = n;
      }
      {
        Node **m = &cols;
        while (*m && lt((*m)->col, (*m)->row, c, r)) m = &((*m)->nextcol);
        n->nextcol = *m;
        *m = n;
      }
      return *this;
    }
   friend ostream &operator << (ostream &out, const Matrix &mat)
    {
      Node *n = mat.rows;
      for (int r=0; r<mat.size; ++r)
       {
         for (int c=0; c<mat.size; ++c)
          {
            out.width(5); out.setf(ios::right);
            if (n && n->row == r && n->col == c)
             {
               out << n->data;
               n = n->nextrow;
             }
            else
             { out << 0;}
          }
         out << endl;
       }
      return out;
    }
   friend Matrix operator + (const Matrix &m1, const Matrix &m2)
    {
      Node *n1 = m1.rows;
      Node *n2 = m2.rows;
      Matrix mat(m1.size);
      for (int r=0; r<mat.size; ++r)
       for (int c=0; c<mat.size; ++c)
        {
          Item i = 0;
          if (n1 && n1->row == r && n1->col == c)
           { i += n1->data;
             n1 = n1->nextrow;
           }
          if (n2 && n2->row == r && n2->col == c)
           { i += n2->data;
             n2 = n2->nextrow;
           }
          if (i) mat.append(i, r, c);
        }
      return mat;
    }
   friend Matrix operator * (const Matrix &m1, const Matrix &m2)
    {
      Matrix mat(m1.size);
      Node *n1 = m1.rows;
      for (int r=0; r<mat.size; ++r)
       { Node *_n1 = n1;
         Node *n2 = m2.cols;
         for (int c=0; c<mat.size; ++c)
          { n1 = _n1;
            Item i = 0;
            for (int k=0; k<mat.size; ++k)
             {
               if (n1 && n1->row == r && n1->col == k &&
                   n2 && n2->row == k && n2->col == c)
                { i += n1->data * n2->data;}
               if (n1 && n1->row == r && n1->col == k)
                { n1 = n1->nextrow;}
               if (n2 && n2->row == k && n2->col == c)
                { n2 = n2->nextcol;}
             }
            if (i) mat.append(i, r, c);
          }
       }
      return mat;
    }
 };