lsmatrix.h

数据结构c++语言描述 Borland C++实现

   // insert new value for (i,j)
   z.value = x;
   h->a.Insert(rCount, z);
   return *this;
}

template <class T>
HeadNode<T>* LinkedMatrix<T>::Copy(HeadNode<T> *h) const
{// Return a copy of row defined by h.

   // copy the head node
   HeadNode<T> *hCopy = new HeadNode<T>;
   hCopy->row = h->row;

   // use a chain iterator to traverse row nodes
   ChainIterator<CNode<T> > q;
   CNode<T> *r = q.Initialize(h->a);
   while (r) {
      // copy and append the term
      hCopy->a.Append(*r);
      // advance to next term in row
      r = q.Next();
      }
   return hCopy;
}
      

template <class T>
HeadNode<T>* LinkedMatrix<T>::AddRows
    (HeadNode<T> *ah, HeadNode<T>* bh) const
{// Add the matrix rows ah and bh and return
 // a pointer to the result.

   // create head node for result
   HeadNode<T> *sum = new HeadNode<T>;
   sum->row = ah->row;

   // define chain iterators for the two chains
   // and initialize
   ChainIterator<CNode<T> > aIter, bIter;
   CNode<T> *aTerm = aIter.Initialize(ah->a),
            *bTerm = bIter.Initialize(bh->a);
   
   // go down the chains copying terms
   while (aTerm && bTerm)
      if (aTerm->col > bTerm->col) {
         // copy bTerm
         sum->a.Append(*bTerm);
         bTerm = bIter.Next();}
      else if (aTerm->col < bTerm->col) {
              // copy aTerm
              sum->a.Append(*aTerm);
              aTerm = aIter.Next();}
           else {// add values and append
                 T x = aTerm->value + bTerm->value;
                 if (x) {// x != 0
                         CNode<T> p;
                         p.col = aTerm->col;
                         p.value = x;
                         sum->a.Append(p);}
                 aTerm = aIter.Next();
                 bTerm = bIter.Next();}
              
   // copy remaining terms
   while (aTerm) {
      sum->a.Append(*aTerm);
      aTerm = aIter.Next();
      }
   while (bTerm) {
      sum->a.Append(*bTerm);
      bTerm = bIter.Next();
      }

   if (sum->a.IsEmpty()) {delete sum;
                          return 0;}
   else return sum;
}
 

template <class T>
void LinkedMatrix<T>::Add(const LinkedMatrix<T> &b,
              LinkedMatrix<T> &c) const
{// Compute c = (*this) + b.

   // verify compatibility
   if (rows != b.rows || cols != b.cols)
     throw SizeMismatch(); // incompatible matrices

   // set characteristics of result c
   c.rows = rows;
   c.cols = cols;
   c.a.Erase();  // delete nodes in c

   // define iterators for head node chains
   // of *this and b and initialize
   ChainIterator<HeadNode<T> > tHeadIter, bHeadIter;
   HeadNode<T> *th = tHeadIter.Initialize(a);
   HeadNode<T> *bh = bHeadIter.Initialize(b.a);

   // go down the head node chains
   // until we fall off one of them
   while (th && bh)
      // compare row numbers
      if (th->row < bh->row) {
         // copy row of *this and append to c.a
         c.a.Append(*Copy(th));
         // advance to next row of *this
         th = tHeadIter.Next();}
      else if (th->row > bh->row) {
              // copy row of b and append to c.a
              c.a.Append(*Copy(bh));
              // advance to next row of b
              bh = bHeadIter.Next();}
            else {// rows are the same, add and
                  // append to c.a
                  HeadNode<T> *x = AddRows(th, bh);
                  if (x)  {// append to head node chain
                           a.Append(*x);
                           // save row nodes from destructor
                           // and delete head node as it has
                           // been copied by Append
                           x->a.Zero();
                           delete x;
                           }
                  th = tHeadIter.Next();
                  bh = bHeadIter.Next();
                  }

   // take care of remaining rows
   // at most one of *this and b has unprocessed rows
   while (th) {// copy a row of *this
      c.a.Append(*Copy(th));
      // advance to next row of *this
      th = tHeadIter.Next();
      }
         
   while (bh) {// copy a row of b
      c.a.Append(*Copy(bh));
      // advance to next row of *this
      bh = bHeadIter.Next();
      }
}

      
template <class T>
HeadNode<T>* LinkedMatrix<T>::MinusCopy(HeadNode<T> *h) const
{// Return a copy of the negative of row defined by h.

   // copy the head node
   HeadNode<T> *hCopy = new HeadNode<T>;
   hCopy->row = h->row;

   // use a chain iterator to traverse row nodes
   ChainIterator<CNode<T> > q;
   CNode<T> *r = q.Initialize(h->a);
   while (r) {// copy a node and append
      CNode<T> c;
      c.col = r->col;
      c.value = -r->value;
      // append to row chain copy
      hCopy->a.Append(c);
      // advance to next node
      r = q.Next();
      }
   return hCopy;
}
      

template <class T>
HeadNode<T>* LinkedMatrix<T>::SubRows
    (HeadNode<T> *ah, HeadNode<T>* bh) const
{// Subtract the matrix rows ah and bh and return
 // a pointer to the result.

   // create head node for result
   HeadNode<T> *sum = new HeadNode<T>;
   sum->row = ah->row;

   // define chain iterators for the two chains
   // and initialize
   ChainIterator<CNode<T> > aIter, bIter;
   CNode<T> *aTerm = aIter.Initialize(ah->a),
            *bTerm = bIter.Initialize(bh->a);
   
   // go down the chains copying terms
   while (aTerm && bTerm)
      if (aTerm->col > bTerm->col) {
         // copy negative of bTerm
         CNode<T> y;
         y.col = bTerm->col;
         y.value = -bTerm->value;
         sum->a.Append(y);
         bTerm = bIter.Next();}
      else if (aTerm->col < bTerm->col) {
              // copy aTerm
              sum->a.Append(*aTerm);
              aTerm = aIter.Next();}
           else {// subtract values and append
                 T x = aTerm->value - bTerm->value;
                 if (x) {// x != 0
                         CNode<T> p;
                         p.col = aTerm->col;
                         p.value = x;
                         sum->a.Append(p);}
                 aTerm = aIter.Next();
                 bTerm = bIter.Next();}
              
   // copy remaining terms
   while (aTerm) {
      sum->a.Append(*aTerm);
      aTerm = aIter.Next();
      }
   while (bTerm) {
      CNode<T> y;
      y.col = bTerm->col;
      y.value = -bTerm->value;
      sum->a.Append(y);
      bTerm = bIter.Next();
      }

   if (sum->a.IsEmpty()) {delete sum;
                          return 0;}
   else return sum;
}
 

template <class T>
void LinkedMatrix<T>::Subtract(const LinkedMatrix<T> &b,
              LinkedMatrix<T> &c) const
{// Compute c = (*this) - b.

   // verify compatibility
   if (rows != b.rows || cols != b.cols)
     throw SizeMismatch(); // incompatible matrices

   // set characteristics of result c
   c.rows = rows;
   c.cols = cols;
   c.a.Erase();  // delete nodes in c

   // define iterators for head node chains
   // of *this and b and initialize
   ChainIterator<HeadNode<T> > tHeadIter, bHeadIter;
   HeadNode<T> *th = tHeadIter.Initialize(a);
   HeadNode<T> *bh = bHeadIter.Initialize(b.a);

   // go down the head node chains
   // until we fall off one of them
   while (th && bh)
      // compare row numbers
      if (th->row < bh->row) {
         // copy row of *this and append to c.a
         c.a.Append(*Copy(th));
         // advance to next row of *this
         th = tHeadIter.Next();}
      else if (th->row > bh->row) {
              // copy negative of row of b
              // and append to c.a
              c.a.Append(*MinusCopy(bh));
              // advance to next row of b
              bh = bHeadIter.Next();}
            else {// rows are the same, subtract and
                  // append to c.a
                  HeadNode<T> *x = SubRows(th, bh);
                  if (x)  {// append to head node chain
                           a.Append(*x);
                           // save row nodes from destructor
                           // and delete head node as it has
                           // been copied by Append
                           x->a.Zero();
                           delete x;
                           }
                  th = tHeadIter.Next();
                  bh = bHeadIter.Next();
                  }

   // take care of remaining rows
   // at most one of *this and b has unprocessed rows
   while (th) {// copy a row of *this
      c.a.Append(*Copy(th));
      // advance to next row of *this
      th = tHeadIter.Next();
      }
         
   while (bh) {// copy minus of a row of b
      c.a.Append(*MinusCopy(bh));
      // advance to next row of *this
      bh = bHeadIter.Next();
      }
}

#endif