目录

前置数据结构定义

顺序表

单链表

矩阵元素三元组结构【稀疏矩阵】

矩阵链式元素结构 【十字链表】

稀疏矩阵

十字矩阵

下三角矩阵

三对角矩阵

对角矩阵

---

前置数据结构定义

顺序表

template <class T> class arrayList
	: public linearList< T >

#include <iostream>
#include <sstream>

#include <stdexcept>
#include <exception>

#include <algorithm>
#include <iterator>
#include <type_traits>

#include <cstdint>
#include <cstddef>
#include <assert.h>

template<typename T> class arrayList;
template <typename value_type>
bool operator<( const arrayList<value_type>& lhs,
			     const arrayList<value_type>& rhs){
	register int i;
	for(i = 0; i < std::min( lhs.listSize, rhs.listSize ); ++i)
		if( !( *( lhs.elements + i ) == *(rhs.elements + i) ) )
			return *( lhs.elements + i) < *(rhs.elements + i);
	return lhs.listSize < rhs.listSize;
}

template <typename value_type>
bool operator==( const arrayList<value_type>& lhs,
			     const arrayList<value_type>& rhs){
	if( !( lhs.listSize == rhs.listSize ) ) return false;
	register int i;
	for(i = 0; i < lhs.listSize; ++i)
		if( !( *( lhs.elements + i ) == *(rhs.elements + i) ) )
			return false;
	return true;
}

template <typename value_type>
bool operator!=( const arrayList<value_type>& lhs,
			     const arrayList<value_type>& rhs){
	return !( lhs == rhs );
}

template < typename T >
std::ostream& operator<<( std::ostream& os, const arrayList< T >& x){
	x.output( os );
	return os;
}

template < class T > class linearList{
public:
	virtual ~linearList( void ) {};
	virtual bool empty( void ) const = 0;
	virtual std::size_t size( void ) const = 0;
	virtual T& get( int theIndex ) const = 0;
	virtual int indexOf( const T& theElement ) const = 0;
	virtual void erase( int theIndex ) = 0;
	virtual void insert( int theIndex, const T& theElement ) = 0;
	virtual void output( std::ostream& os ) const = 0;
};

template <class T> class arrayList
	: public linearList< T >{
		friend bool operator==<T>( const arrayList<T>&,
					     const arrayList<T>&);
		friend bool operator< <T>( const arrayList<T>&,
					     const arrayList<T>&);
		friend bool operator!=<T>( const arrayList<T>&,
					     const arrayList<T>&);
		friend std::ostream& operator<< <T>( std::ostream&,
					     const arrayList<T>&);
class iterator{
	public:
		typedef std::bidirectional_iterator_tag iterator_category;
		typedef T value_type;
		typedef std::ptrdiff_t difference_type;
		typedef value_type* pointer;
		typedef value_type& reference;

		iterator(pointer thePosition = nullptr) : position( thePosition ) {}

		reference operator*( void ) const { return *position; }
		pointer operator->( void ) const { return &(*position); }

		iterator& operator++( void ) {
			++position;
			return *this;
		}
		iterator& operator--( void ){
			--position;
			return *this;
		}
		iterator operator++( int dummy ){
			iterator tmp = *this;
			++position;
			return tmp;
		}
		iterator operator--( int dummy ){
					iterator tmp = *this;
					--position;
					return tmp;
		}

		bool operator!=( const iterator rhs ) const{
			return position != rhs.position;
		}
		bool operator==( const iterator rhs ) const{
					return position == rhs.position;
		}
	protected:
		pointer position;
};
public:
	arrayList(int initialCapacity = 10, std::size_t Scaler = 2);
	arrayList( const arrayList< T >&);
	~arrayList( void ){
		if(elements) delete[]elements;
		elements = nullptr;
	}
	virtual bool empty( void ) const { return listSize == 0; }
	virtual std::size_t size( void ) const { return listSize; }
	virtual T& get( int theIndex ) const;
	virtual int indexOf( const T& theElement ) const;
	virtual void erase( int theIndex );
	virtual void insert( int theIndex, const T& theElement );
	virtual void output( std::ostream& os ) const;
	
	T& operator[]( std::size_t position ) const;

	std::size_t capacity( void ) const { return arrayLength; }

	iterator begin( void ){ return iterator( elements ); }
	iterator end( void ){ return iterator( elements + listSize ); }
	
	inline void trimToSize( void );
	void setSize( std::size_t _Size );
	
protected:
	void checkIndex(int theIndex) const;
	T* elements { nullptr };
	std::size_t arrayLength { 10 };
	std::size_t listSize { 0 };
	uint8_t Scaler;
};

template < class T >
void arrayList< T >::checkIndex( int theIndex ) const{
	if( theIndex < 0 || theIndex >= listSize ){
		std::ostringstream oss;
		char buf[ 64 ];
		sprintf( buf, "given index = %d; size = %d", theIndex, listSize );
		oss << buf;
		throw std::invalid_argument( oss.str() );
	}
	return;
}

template < class T >
arrayList< T >::arrayList(int initialCapacity, std::size_t Scaler)
:Scaler( Scaler ){
	if( initialCapacity < 1 ){
		std::ostringstream oss;
		char buf[ 64 ];
		sprintf( buf, "initial capacity = %d Must be > 0", initialCapacity);
		oss << buf;
		throw std::invalid_argument( oss.str() );
	}
	arrayLength = initialCapacity;
	elements = new T[ arrayLength ];
}

template < class T >
inline void arrayList< T >::trimToSize( void ){
	changeLength1D( elements, arrayLength, std::max( listSize, 1ULL ) );
	arrayLength = std::max( listSize, 1ULL );
}

template <class T>
void arrayList< T >::setSize( std::size_t _Size ){
	if( listSize > _Size )
		for( std::ptrdiff_t i = _Size; i < listSize; ++i)
			delete (elements + i);
	listSize = _Size;
}

template <class T>
T& arrayList< T >::operator[]( std::size_t position ) const{
	checkIndex( position );
	return *(elements + position);
}

template < class T >
arrayList< T >::arrayList( const arrayList< T >& theList )
	:arrayLength( theList.arrayLength )
	,listSize( theList.listSize )
	,elements( new T[ arrayLength ])
{
	std::copy(theList.elements, theList.element + listSize, elements );
}

template < class T >
int arrayList< T >::indexOf( const T& theElement ) const{
	int ret {};
	return
		( int )( ( ret =
			std::find(elements, elements + listSize, theElement) - elements) )
				== listSize ? -1 : ret;
}

template < typename T >
void arrayList< T >::erase(int theIndex ){
	checkIndex( theIndex );
	std::copy( elements + theIndex + 1, elements + listSize, elements + theIndex );
	elements[ --listSize ].~T();
}

template < typename T >
void arrayList< T >::insert( int theIndex, const T& theElement ){
	checkIndex( theIndex );
	if(listSize == arrayLength ){
		changeLength1D( elements, arrayLength, arrayLength * Scaler );
		arrayLength *= Scaler;
	}
	std::copy_backward( elements + theIndex, elements + listSize, elements + listSize+1 );
	elements[ theIndex ] = theElement;
}

template < typename T >
void arrayList< T >::output( std::ostream& os ) const{
	std::copy( elements, elements + listSize, std::ostream_iterator< T >( os, "	") );
}

template < typename value_type >
void changeLength1D( value_type*& pArray,
					 const signed long& N,
					 const signed long& M )
{
//	static_assert(typename std::is_copy_constructible<value_type>::value, "requires copying");
	if( nullptr == pArray )
		throw std::domain_error( "array is nullptr" );
	if( N < 0 || M < 0)
		throw std::invalid_argument( "illegalParameterValue N|M given" );
	std::size_t checkedN  = static_cast< std::size_t >( N );
	std::size_t checkedM  = static_cast< std::size_t >( M );
	value_type* temp = new value_type[ checkedM ];
	std::copy( pArray, pArray + std::min( checkedN, checkedM ), temp );
	delete [] pArray;
	pArray = temp;
}

template < class T >
T& arrayList< T >::get( int theIndex ) const{
	checkIndex( theIndex );
	return elements[ theIndex ];
}

template < typename value_type, std::size_t formerN, std::size_t formerM >
value_type** chanegeLeagth2D( value_type (&_Matrix)[ formerN ][ formerM],
					  const signed long& newN,
					  const signed long& newM){
	assert(newN > 0 && newM > 0 || "invalid argument nagetive N | M given");
//	static_assert(typename std::is_copy_constructible<value_type>::value, "requires copying");
	value_type ** _ScaledMatrix = new value_type*[ newN ];
	for( std::ptrdiff_t i = 0; i < newM; ++i) _ScaledMatrix[ i ] = new value_type[ newM ];
	int i,j;
	std::size_t checkedN  = static_cast< std::size_t >( newN );
	std::size_t checkedM  = static_cast< std::size_t >( newM );
	for(i = 0; i < std::min( formerN, checkedN ); ++i)
		for(j = 0; j < std::min( formerM, checkedM ); ++j)
			_ScaledMatrix[i][j] = _Matrix[i][j];
	return _ScaledMatrix;
}

template < typename InputIterator >
void myCopy(InputIterator begIt, InputIterator endIt, InputIterator resIt ){
	while( !( begIt == endIt ) )
		*resIt++ = *begIt++;
}

int main( void ){
	int *pArray = new int[5] { 1, 2, 3, 4, 5 };
	changeLength1D( pArray, 5L, 10L );
	int i;
	for(i = 0;i < 10;++i) std::clog << *( pArray + i ) << '
';
	
	constexpr int N { 5 };
	int *pEnd = pArray + N;
	for( std::ptrdiff_t i { N }; i > 0; --i )
		std::clog << ( *( pEnd - i ) = i ) << '	';
	std::endl( std::cout );
	return 0;
}

单链表

template < class T > class chain :
     public linearList< T >;

#include <iostream>
#include <sstream>
#include <cstdio>
#include <iterator>
#include <type_traits>



template < class T > class linearList{
public:
	virtual ~linearList( void ) {};
	virtual bool empty( void ) const = 0;
	virtual std::size_t size( void ) const = 0;
	virtual T& get( int theIndex ) const = 0;
	virtual int indexOf( const T& theElement ) const = 0;
	virtual void erase( int theIndex ) = 0;
	virtual void insert( int theIndex, const T& theElement ) = 0;
	virtual void output( std::ostream& os ) const = 0;
};

template < class T > class extendedLinearList
: public linearList< T >
{
public:
	virtual ~extendedLinearList( void ){ }
	virtual void clear( void ) = 0;
	virtual void push_back( const T& theElement ) = 0;
};


template < class T> struct chainNode{
	T element;
	chainNode< T > *next { nullptr };
	
	chainNode( void ) {}
	chainNode( const T& element )
		:element( element )
		{}
	chainNode( const T& element, const chainNode< T > *next )
		:chainNode( element )
		{ this->next = next;}
};

template < typename T > class chain;
template < typename T >
std::ostream& operator<<( std::ostream& os, const chain< T >& x){
	x.output( os );
	return os;
}


template < class T > class chain : public linearList< T >{
class iterator{
	public:
		typedef std::forward_iterator_tag iterator_category;
		typedef T value_type;
		typedef chainNode< value_type >* pointer;
		typedef chainNode< value_type >& reference;

		iterator( pointer theNode = nullptr) : node( theNode ) {}

		reference operator*( void ) const { return &node->element; }
		pointer operator->( void ) const { return node->element; }

		iterator& operator++( void ) {
			node = node->next;
			return *this;
		}
		iterator operator++( int dummy ){
			iterator tmp = *this;
			node = node->next;
			return tmp;
		}

		bool operator!=( const iterator rhs ) const{
			return node != rhs.node;
		}
		bool operator==( const iterator rhs ) const{
					return node == rhs.node;
		}
	protected:
		pointer node;
};
public:
	chain( const chain< T >& );
	~chain( void );
	
	virtual bool empty( void ) const { return listSize == 0; }
	virtual std::size_t size( void ) const { return listSize; }
	
	virtual T& get( int theIndex ) const;
	virtual int indexOf( const T& theElement ) const;
	virtual void erase( int theIndex );
	virtual void insert( int theIndex, const T& theElement );
	virtual void output( std::ostream& os ) const;
	
	iterator begin( void ){ return iterator( firstNode ); }
	iterator end( void ){ return iterator(); }
	
protected:
	void checkIndex( int theIndex ) const;
	chainNode< T > *firstNode { nullptr };
	std::size_t listSize { 0 };
};
template < class  T >
chain< T >::chain( const chain< T >& theList)
:listSize( theList.listSize )
{
	if( !listSize ) return;
	chainNode< T > *sourceNode = theList.firstNode;
	firstNode = new chainNode< T >( sourceNode->element );
	chainNode< T > *targetNode = firstNode;
	while( sourceNode ){
		targetNode->next = new chainNode< T >( sourceNode->element );
		targetNode = targetNode->next;
		sourceNode = sourceNode->next;
	}
}

template < class T >
void chain< T >::checkIndex( int theIndex ) const{
	if( theIndex < 0 || theIndex >= listSize ){
		std::ostringstream oss;
		char buf[ 64 ];
		sprintf( buf, "given index = %d; size = %d", theIndex, listSize );
		oss << buf;
		throw std::invalid_argument( oss.str() );
	}
	return;
}

template < class T >
T& chain< T >::get( int theIndex ) const{
	checkIndex( theIndex );
	chainNode< T > *currentNode = firstNode;
	for( register int i { 0 }; i < theIndex; ++i)
		currentNode = currentNode->next;
	return currentNode->element;
}

template < class T >
int chain< T >::indexOf( const T& theElement ) const{
	chainNode< T > *currentNode = firstNode;
	int index = 0;
	while( currentNode && !( currentNode->element == theElement ) ){
		currentNode = currentNode->next;
		++index;
	}
	return currentNode ? index : -1;
}

template < class T >
void chain< T >::erase( int theIndex ){
	checkIndex( theIndex );
	chainNode< T > *deleteNode;
	if( !theIndex ){
		deleteNode = firstNode;
		firstNode = firstNode->next;
	}else{
		chainNode< T > *p =firstNode;
		for( register int i { 0 }; i < theIndex; ++i )
			p = p->next;
		deleteNode = p->next;
		p->next = p->next->next;
	}
	listSize--;
	delete deleteNode;
}

template < class T >
void chain<T>::insert( int theIndex, const T& theElement ){
	checkIndex( theIndex );
	if( !theIndex ) firstNode = new chainNode< T >( theElement, firstNode );
	else{
		chainNode< T > *p = firstNode;
		for( register int i { 0 }; i < theIndex; ++i )
			p = p->next;
		p->next = new chainNode< T >( theElement, p->next );
	}
	listSize++;
}

template < class T >
void chain< T >::output( std::ostream& os ) const{
	for( chainNode< T > *currentNode = firstNode;
		 currentNode;
		 currentNode = currentNode->next)
			os << currentNode->element << '	';
}

int main( void ){

	return 0;
}

矩阵元素三元组结构【稀疏矩阵】

// a term in sparseMatrix

#ifndef matrixTerm_
#define matrixTerm_

using namespace std;

template <class T>
struct matrixTerm 
{
   int row,     
       col;
   T value;

   operator T() const {return value;}
      // type conversion from matrixTerm to T
};

#endif

矩阵链式元素结构 【十字链表】

// element types used by class linkedMatrix

#ifndef matrixElements_
#define matrixElements_

#include "extendedChain.h"

using namespace std;

template<class T>
struct rowElement 
{
   int col;
   T value;

   bool operator !=(const rowElement<T>& y)
      {return (value != y.value);}
   void output(ostream& out) const
      {out << "column " << col 
           << " value " << value << endl;}
};

template<class T>
ostream& operator<<(ostream& out, const rowElement<T>& x)
   {x.output(out); return out;}

template<class T>
struct headerElement
{
      int row;
      extendedChain<rowElement<T> > rowChain;

      bool operator !=(const headerElement<T>& y)
         {return (row != y.row);}
      void output(ostream& out) const
         {out << "row " << row << endl << "  " << rowChain << endl;}
};

template<class T>
ostream& operator<<(ostream& out,
                    const headerElement<T>& x)
   {x.output(out); return out;}

#endif

稀疏矩阵

// sparse matrix using an extended array list

#ifndef sparseMatrix_
#define sparseMatrix_

#include <iostream>
#include "matrixTerm.h"
#include "extendedArrayList.h"
#include "myExceptions.h"

template<class T>
class sparseMatrix
{
   friend ostream& operator<<
          (ostream&, sparseMatrix<T>&);
   friend istream& operator>>
          (istream&, sparseMatrix<T>&);
   public:
      void transpose(sparseMatrix<T> &b);
      void add(sparseMatrix<T> &b, sparseMatrix<T> &c);
   private:
      int rows,    // number of rows in matrix
          cols;    // number of columns in matrix
      arrayList<matrixTerm<T> > terms;
                   // list of nonzero terms
};

// overload <<
template <class T>
ostream& operator<<(ostream& out, sparseMatrix<T>& x)
{// Put x in output stream.

   // put matrix characteristics
   out << "rows = " << x.rows << " columns = "
       << x.cols  << endl;
   out << "nonzero terms = " << x.terms.size() << endl;

   // put terms, one per line
   for (arrayList<matrixTerm<T> >::iterator i = x.terms.begin();
        i != x.terms.end(); i++)
      out << "a(" << (*i).row << ',' << (*i).col
          << ") = " << (*i).value << endl;

   return out;
}

// overload >>
template<class T>
istream& operator>>(istream& in, sparseMatrix<T>& x)
{// Input a sparse matrix.

   // input matrix characteristics
   int numberOfTerms;
   cout << "Enter number of rows, columns, and #terms"
        << endl;
   in >> x.rows >> x.cols >> numberOfTerms;

   // set size of x.terms and ensure enough capacity
   x.terms.reSet(numberOfTerms);

   // input terms
   matrixTerm<T> mTerm;
   for (int i = 0; i < numberOfTerms; i++)
   {
      cout << "Enter row, column, and value of term " 
           << (i + 1) << endl;
      in >> mTerm.row >> mTerm.col >> mTerm.value;
      x.terms.set(i, mTerm);
   }

   return in;
}


/****************************************************************/
// explict code tooverload with T = int for test as compiler
// unable to generate

// overload <<
ostream& operator<<(ostream& out, sparseMatrix<int>& x)
{// Put x in output stream.

   // put matrix characteristics
   out << "rows = " << x.rows << " columns = "
       << x.cols  << endl;
   out << "nonzero terms = " << x.terms.size() << endl;

   // put terms, one per line
   for (arrayList<matrixTerm<int> >::iterator i = x.terms.begin();
        i != x.terms.end(); i++)
      out << "a(" << (*i).row << ',' << (*i).col
          << ") = " << (*i).value << endl;

   return out;
}

// overload >>
istream& operator>>(istream& in, sparseMatrix<int>& x)
{// Input a sparse matrix.

   // input matrix characteristics
   int numberOfTerms;
   cout << "Enter number of rows, columns, and #terms"
        << endl;
   in >> x.rows >> x.cols >> numberOfTerms;

   // set size of x.terms and ensure enough capacity
   x.terms.reSet(numberOfTerms);

   // input terms
   matrixTerm<int> mTerm;
   for (int i = 0; i < numberOfTerms; i++)
   {
      cout << "Enter row, column, and value of term " 
           << (i + 1) << endl;
      in >> mTerm.row >> mTerm.col >> mTerm.value;
      x.terms.set(i, mTerm);
   }

   return in;
}
/****************************************************************/
template<class T>
void sparseMatrix<T>::transpose(sparseMatrix<T> &b)
{// Return transpose of *this in b.

   // set transpose characteristics
   b.cols = rows;
   b.rows = cols;
   b.terms.reSet(terms.size());

   // initialize to compute transpose
   int* colSize = new int[cols + 1];
   int* rowNext = new int[cols + 1];
   
   // find number of entries in each column of *this
   for (int i = 1; i <= cols; i++) // initialize
      colSize[i] = 0;  
   for (arrayList<matrixTerm<T> >::iterator i = terms.begin();
        i != terms.end(); i++)
      colSize[(*i).col]++;  
   
   // find the starting point of each row of b
   rowNext[1] = 0;
   for (int i = 2; i <= cols; i++)
      rowNext[i] = rowNext[i - 1] + colSize[i - 1];  
   
   // perform the transpose copying from *this to b
   matrixTerm<T> mTerm;
   for (arrayList<matrixTerm<T> >::iterator i = terms.begin();
        i != terms.end(); i++)
   {
      int j = rowNext[(*i).col]++; // position in b
      mTerm.row = (*i).col;
      mTerm.col = (*i).row;
      mTerm.value = (*i).value;
      b.terms.set(j, mTerm);
   }
}

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

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

   // set characteristics of result c
   c.rows = rows;
   c.cols = cols;
   c.terms.clear();
   int cSize = 0;

   // define iterators for *this and b
   arrayList<matrixTerm<T> >::iterator it = terms.begin();
   arrayList<matrixTerm<T> >::iterator ib = b.terms.begin();
   arrayList<matrixTerm<T> >::iterator itEnd = terms.end();
   arrayList<matrixTerm<T> >::iterator ibEnd = b.terms.end();

   // move through *this and b adding like terms
   while (it != itEnd && ib != ibEnd)
   {
     // row-major index plus cols of each term
     int tIndex = (*it).row * cols + (*it).col;
     int bIndex = (*ib).row * cols + (*ib).col;

     if (tIndex < bIndex)
     {// b term comes later
   	 c.terms.insert(cSize++, *it);
         it++;
     }
     else {if (tIndex == bIndex)
           {// both in same position

              // append to c only if sum not zero
              if ((*it).value + (*ib).value != 0)
              {
                 matrixTerm<T> mTerm;
                 mTerm.row = (*it).row;
                 mTerm.col = (*it).col;
                 mTerm.value = (*it).value + (*ib).value;
                 c.terms.insert(cSize++, mTerm);
              }

              it++; 
              ib++;
           }
           else
           {// a term comes later
              c.terms.insert(cSize++, *ib);
              ib++;
           }
          }
     }

   // copy over remaining terms
   for (; it != itEnd; it++)
      c.terms.insert(cSize++, *it);
   for (; ib != ibEnd; ib++)
      c.terms.insert(cSize++, *ib);
}

#endif

十字矩阵

// linked representation of a sparse matrix

#ifndef linkedMatrix_
#define linkedMatrix_

#include <iostream>
#include "extendedChain.h"
#include "matrixElements.h"

using namespace std;

template<class T>
class linkedMatrix 
{
   friend ostream& operator<<
          (ostream&, linkedMatrix<T>&);
   friend istream& operator>>
          (istream&, linkedMatrix<T>&);
   public:
      linkedMatrix(){}
      ~linkedMatrix(){}
      void transpose(linkedMatrix<T> &b);
   private:
      int rows,       // number of rows in matrix
          cols;       // number of columns in matrix
      extendedChain<headerElement<T> > headerChain;
};

template<class T>
istream& operator>>(istream& in, linkedMatrix<T>& x)
{// Input matrix x from the stream in.
   x.headerChain.clear();
       // 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
   headerElement<T> header;  // header for current row
   header.row = 0;           // current row number

   // get terms of matrix x
   for (int i = 1; i <= terms; i++) 
   {
      // input next term
      cout << "Enter row, column, and value of term " 
           << i << endl;
      rowElement<T> *term = new rowElement<T>;
      int row;
      in >> row >> term->col >> term->value;

      // check if new term is part of current row
      if (row > header.row)
      {// start a new row
         // append header of current row to
         // header node chain only if row not zero
         if (header.row != 0)
            x.headerChain.push_back(header);

         // prepare header for new row
         header.row = row;
         header.rowChain.zero();
               // clear without deleting nodes
      }

      // add new term to row chain
      header.rowChain.push_back(*term);
   }

   // take care of last row of matrix
   if (header.row != 0)
      x.headerChain.push_back(header);
   header.rowChain.zero(); // save from chain destructor

   return in;
}

template<class T>
ostream& operator<<(ostream& out, linkedMatrix<T>& x)
{// Put matrix x into the output stream out.
   // output matrix dimensions
   out << "rows = " << x.rows << " columns = "
       << x.cols << endl << "  ";

   if (x.headerChain.empty())
   {
      out << "No non-zero terms" << endl;
      return out;
   }

   out << x.headerChain << endl;
   return out;
}

/****************************************************************/
// explict code to overload with T = int for test as compiler
// unable to generate

istream& operator>>(istream& in, linkedMatrix<int>& x)
{// Input matrix x from the stream in.
   x.headerChain.clear();
       // 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
   headerElement<int> header;  // header for current row
   header.row = 0;             // current row number

   // get terms of matrix x
   for (int i = 1; i <= terms; i++) 
   {
      // input next term
      cout << "Enter row, column, and value of term " 
           << i << endl;
      rowElement<int> *term = new rowElement<int>;
      int row;
      in >> row >> term->col >> term->value;

      // check if new term is part of current row
      if (row > header.row)
      {// start a new row
         // append header of current row to
         // header node chain only if row not zero
         if (header.row != 0)
            x.headerChain.push_back(header);

         // prepare header for new row
         header.row = row;
         header.rowChain.zero();
               // clear without deleting nodes
      }

      // add new term to row chain
      header.rowChain.push_back(*term);
   }

   // take care of last row of matrix
   if (header.row != 0)
      x.headerChain.push_back(header);
   header.rowChain.zero(); // save from chain destructor

   return in;
}

ostream& operator<<(ostream& out, linkedMatrix<int>& x)
{// Put matrix x into the output stream out.
   // output matrix dimensions
   out << "rows = " << x.rows << " columns = "
       << x.cols << endl << "  ";

   if (x.headerChain.empty())
   {
      out << "No non-zero terms" << endl;
      return out;
   }

   out << x.headerChain << endl;

   return out;
}
/****************************************************************/

template<class T>
void linkedMatrix<T>::transpose(linkedMatrix<T> &b)
{// Return transpose of *this as matrix b.
   b.headerChain.clear(); // delete all nodes from b

   // create bins to collect rows of b
   extendedChain<rowElement<T> > *bin;
   bin = new extendedChain<rowElement<T> > [cols + 1];

   // head node iterator
   extendedChain<headerElement<T> >::iterator
      ih = headerChain.begin(),
      ihEnd = headerChain.end();


   // copy terms of *this into bins
   while (ih != ihEnd)
   {// examine all rows
      int r = ih->row; // row number for row chain

      // row chain iterator
      extendedChain<rowElement<T> >::iterator
         ir = ih->rowChain.begin(),
         irEnd = ih->rowChain.end();


      rowElement<T> x;
      // terms from row r of *this go to column r of b
      x.col = r;

      while (ir != irEnd)
      {// copy a term from the row chain into a bin
         x.value = ir->value;
         // x will eventually be in row ir->col of transpose
         bin[ir->col].push_back(x);
         ir++;  // next term in row
      }

      ih++; // go to next row
   }

   // set dimensions of transpose
   b.rows = cols;
   b.cols = rows;

   // assemble header chain of transpose
   headerElement<T> h;
   // scan bins
   for (int i = 1; i <= cols; i++)
      if (!bin[i].empty())
      {// row i of transpose
         h.row = i;
         h.rowChain = bin[i];
         b.headerChain.push_back(h);
         bin[i].zero(); // save from destructor
      }

   h.rowChain.zero();   // save from destructor

   delete [] bin;
}

#endif

下三角矩阵

// lower triangle matrix
#ifndef lowerTriangularMatrix_
#define lowerTriangularMatrix_


#include "myExceptions.h"

using namespace std;

template<class T>
class lowerTriangularMatrix 
{
   public:
      lowerTriangularMatrix(int theN = 10);
      ~lowerTriangularMatrix() {delete [] element;}
      T get(int, int) const;
      void set(int, int, const T&);
   private:
      int n;       // matrix dimension
      T *element;  // 1D array for lower triangle
};


template<class T>
lowerTriangularMatrix<T>::lowerTriangularMatrix(int theN)
{// Constructor.
   // validate theN
   if (theN < 1)
       throw illegalParameterValue("Matrix size must be > 0");

   n = theN;
   element = new T [n * (n + 1) / 2];
}
   
template <class T>
T lowerTriangularMatrix<T>::get(int i, int j) const
{// Return (i,j)th element of matrix.
   // validate i and j
   if ( i < 1 || j < 1 || i > n || j > n)
       throw matrixIndexOutOfBounds();

   // (i,j) in lower triangle iff i >= j
   if (i >= j)
      return element[i * (i - 1) / 2 + j - 1];
   else
      return 0;
}

template<class T>
void lowerTriangularMatrix<T>::set(int i, int j, const T& newValue)
{// Store newValue as (i,j)th element.
   // validate i and j
   if ( i < 1 || j < 1 || i > n || j > n)
       throw matrixIndexOutOfBounds();


   // (i,j) in lower triangle iff i >= j
   if (i >= j)
      element[i * (i - 1) / 2 + j - 1] = newValue;
   else
      if (newValue != 0)
         throw illegalParameterValue
               ("elements not in lower triangle must be zero");
}

#endif

三对角矩阵

// tridiagonal matrix

#ifndef tridiagonal_
#define tridiagonal_


#include "myExceptions.h"

using namespace std;

template<class T>
class tridiagonalMatrix 
{
   public:
      tridiagonalMatrix(int theN = 10);
      ~tridiagonalMatrix() {delete [] element;}
      T get(int, int) const;
      void set(int, int, const T&);
   private:
      int n;       // matrix dimension
      T *element;  // 1D array for tridiagonal
};

template<class T>
tridiagonalMatrix<T>::tridiagonalMatrix(int theN)
{// Constructor.
   // validate theN
   if (theN < 1)
       throw illegalParameterValue("Matrix size must be > 0");

   n = theN;
   element = new T [3 * n - 2];
}

template <class T>
T tridiagonalMatrix<T>::get(int i, int j) const
{// Return (i,j)th element of matrix.

   // validate i and j
   if ( i < 1 || j < 1 || i > n || j > n)
       throw matrixIndexOutOfBounds();
 
   // determine lement to return
   switch (i - j) 
   {
      case 1: // lower diagonal
              return element[i - 2];
      case 0: // main diagonal
              return element[n + i - 2];
      case -1: // upper diagonal
              return element[2 * n + i - 2];
      default: return 0;
   }
}

template<class T>
void tridiagonalMatrix<T>::set(int i, int j, const T& newValue)
{// Store newValue as (i,j)th element

   // validate i and j
   if ( i < 1 || j < 1 || i > n || j > n)
      throw matrixIndexOutOfBounds();

   switch (i - j) 
   {
      case 1: // lower diagonal
         element[i - 2] = newValue; break;
      case 0: // main diagonal
         element[n + i - 2] = newValue; break;
      case -1: // upper diagonal
         element[2 * n + i - 2] = newValue; break;
      default: if (newValue != 0)
                  throw illegalParameterValue
                        ("non-tridiagonal elements must be zero");
   }
}

#endif

对角矩阵

// diagonal matrix
#ifndef diagonalMatrix_
#define diagonalMatrix_


#include "myExceptions.h"

using namespace std;

template<class T>
class diagonalMatrix 
{
   public:
      diagonalMatrix(int theN = 10);
      ~diagonalMatrix() {delete [] element;}
      T get(int, int) const;
      void set(int, int, const T&);
   private:
      int n;       // matrix dimension
      T *element;  // 1D array for diagonal elements
};

template<class T>
diagonalMatrix<T>::diagonalMatrix(int theN)
{// Constructor.
   // validate theN
   if (theN < 1)
       throw illegalParameterValue("Matrix size must be > 0");

   n = theN;
   element = new T [n];
}
  
template <class T>
T diagonalMatrix<T>::get(int i, int j) const
{// Return (i,j)th element of matrix.
   // validate i and j
   if (i < 1 || j < 1 || i > n || j > n)
       throw matrixIndexOutOfBounds();

   if (i == j)
      return element[i-1];   // diagonal element
   else
      return 0;              // nondiagonal element
}

template<class T>
void diagonalMatrix<T>::set(int i, int j, const T& newValue)
{// Store newValue as (i,j)th element.
   // validate i and j
   if (i < 1 || j < 1 || i > n || j > n)
       throw matrixIndexOutOfBounds();

   if (i == j)
     // save the diagonal value
      element[i-1] = newValue;
   else
      // nondiagonal value, newValue must be zero
      if (newValue != 0)
         throw illegalParameterValue
               ("nondiagonal elements must be zero");
}

#endif