// header file lsmatrix.h// linked representation of a sparse matrix#ifndef LinkedMatrix_#define LinkedMatrix_#include <stdlib.h>#include <iostream.h>#include "echain.h"#include "citer.h"#include "matnodes.h"#include "xcept.h"template<class T>class LinkedMatrix {   friend ostream& operator<<          (ostream&, const LinkedMatrix<T>&);   friend istream& operator>>          (istream&, LinkedMatrix<T>&);   public:      LinkedMatrix(){}      ~LinkedMatrix(){}      void Transpose(LinkedMatrix<T> &b) const;   private:      int rows, cols;        // matrix dimensions      Chain<HeadNode<T> > a; // head node chain};template<class T>istream& operator>>(istream& in, LinkedMatrix<T>& x){// Input matrix x from the stream in.   x.a.Erase(); // delete all nodes from x   // get matrix characteristics   int terms;   // number of terms to be input   cout << "Enter number of rows, columns, and terms"         << endl;   in >> x.rows >> x.cols >> terms;   // create fictional row zero   HeadNode<T> H;  // head node for current row   H.row = 0;      // current row number   // get terms of matrix x   for (int i = 1; i <= terms; i++) {      // get next term      cout << "Enter row, column, and value of term "            << i << endl;      int row, col;      T value;      in >> row >> col >> value;      // check if new term is part of current row      if (row > H.row) {// start a new row         // append head node H of current row to         // head node chain x.a only if row not zero         if (H.row) x.a.Append(H);         // prepare H for new row         H.row = row;         H.a.Zero();}  // save from chain destructor      // add new term to row chain      CNode<T> *c = new CNode<T>;      c->col = col;      c->value = value;      H.a.Append(*c);      }   // take care of last row of matrix   if (H.row) x.a.Append(H);   H.a.Zero(); // save from chain destructor   return in;}template<class T>ostream& operator<<(ostream& out,                    const LinkedMatrix<T>& x){// Put matrix x into the output stream out.   ChainIterator<HeadNode<T> > p;// head node iterator   // output matrix dimensions   out << "rows = " << x.rows << " columns = "       << x.cols << endl;   // set h to point to first head node   HeadNode<T> *h = p.Initialize(x.a);   if (!h) {out << "No non-zero terms" << endl;   	    return out;}   // output one row at a time   while (h) {      out << "row " << h->row << endl;      out << h->a << endl;  // output row chain      h = p.Next();         // next head node      }   return out;}template<class T>void LinkedMatrix<T>::     Transpose(LinkedMatrix<T> &b) const{// Return transpose of *this as matrix b.   b.a.Erase(); // delete all nodes from b   // create bins to collect rows of b   Chain<CNode<T> > *bin;   bin = new Chain<CNode<T> > [cols + 1];   // head node iterator   ChainIterator<HeadNode<T> > p;   // set h to point to first head node of *this   HeadNode<T> *h = p.Initialize(a);   // copy terms of *this into bins   while (h) { // examine all rows      int r = h->row; // row number for row chain      // row chain iterator      ChainIterator<CNode<T> > q;      // set z to point to first node in row chain      CNode<T> *z = q.Initialize(h->a);      CNode<T> x;  // temporary node      // terms from row r of *this go to column r of b      x.col = r;      // examine all terms in row r of *this      while (z) {// go down row r         x.value = z->value;         // append term to bin for row z->col of b         bin[z->col].Append(x);         z = q.Next();  // next term in row         }      h = p.Next(); // go to next row      }   // set dimensions of b   b.rows = cols;   b.cols = rows;   // assemble head node chain of b   HeadNode<T> H;   // scan bins   for (int i = 1; i <= cols; i++)      if (!bin[i].IsEmpty()) {// row i of transpose         H.row = i;         H.a = bin[i];         b.a.Append(H);         bin[i].Zero();} // save from destructor   H.a.Zero(); // save from destructor   delete [] bin;}#endif