#include <iostream.h>                                       
                                                                  
//   ===========================================================  
//   =================   class MatrixSparse   ==================  
//   ===========================================================  
                                                                  
struct Element                                                    
   {                                                              
   int column;                                                    
   float value;                                                   
   Element *next;                                                 
   };                                                             
                                                                  
class MatrixSparse                                                
{                                                                 
private:                                                          
   int numRows,numColumns;                                        
   Element **elementRow;                                          
                                                                  
   float &InsertElement                                           
           (Element *elem,int row,int column,int first);          
   void Initialize(int rows,int columns);                         
                                                                  
public:                                                           
//   ===========================================================  
//   ******************   constructor   ***********************   
//   ===========================================================  
                                                                  
   // sizing constructor                                          
   MatrixSparse(int rows,int columns);                            
                                                                  
//   ===========================================================  
//   ********************   destructor   ***********************  
//   ===========================================================  
   ~MatrixSparse(void);                                           
                                                                  
                                                                  
//   ===========================================================  
//   ******************   Access functions   *******************  
//   ===========================================================  
   // number of rows                                              
   int Rows(void) const                                           
      {                                                           
	return numRows;                                           
      }                                                           
                                                                  
   // number of columns                                           
   int Columns(void) const                                        
      {return numColumns;}                                        
                                                                  
   // assigns and receives vector values with control             
   float &operator ()                                             
      (int row,int column);                                       
                                                                  
//   ===========================================================  
//   =============   Modifying Functions =======================  
//   ===========================================================  
   void DeleteMatrix(void);                                       
   void CleanMatrix(void);// eliminates all elements              
                                                                  
};                                                                
                                                                  
                                                                  
void MatrixSparse::Initialize(int rows,int columns)               
   {                                                              
   numRows = rows;                                                
   numColumns = columns;                                          
   elementRow = new Element *[numRows + 1];                       
                                                                  
   for(int row = 0;row <= numRows;row++)elementRow[row] = 0;      
   return;                                                        
   }                                                              
                                                                  
//   *******************< InsertElement >***********************  
//   * Purpose: Inserting an element                           *  
//   * Description: Used internally                            *  
//   ***********************************************************  
float &MatrixSparse::InsertElement                                
            (Element *elem,int row,int column,int first)          
   {                                                              
   Element *newElement = new Element;                             
   newElement->column = column;                                   
   newElement->value = 0.;                                        
   if(first == 1)                                                 
      {                                                           
      newElement->next = elem;                                    
      elementRow[row] = newElement;                               
      }                                                           
   else                                                           
      {                                                           
      newElement->next = elem->next;  // inserted next            
      elem->next = newElement;                                    
      }                                                           
   return newElement->value;                                      
   }                                                              
                                                                  
//   ===========================================================  
//   ================== Public functions =======================  
//   ===========================================================  
                                                                  
//   ===========================================================  
//   ******************   constructor   ************************  
//   ===========================================================  
                                                                  
                                                                  
//   ********************< dimensions >*************************  
//   * Purpose: Providing the dimensions of a matrix           *  
//   * Examples: MatrixSparse A(120,350);                      *  
//   ***********************************************************  
MatrixSparse::MatrixSparse(int rows,int columns)                  
   {                                                              
   Initialize(rows,columns);                                      
   }                                                              
                                                                  
//   ===========================================================  
//   ********************   destructor   ***********************  
//   ===========================================================  
MatrixSparse::~MatrixSparse(void)                                 
   {                                                              
   DeleteMatrix();                                                
   }                                                              
                                                                  
//   ===========================================================  
//   *****************    Access functions *********************  
//   ===========================================================  
                                                                  
//   ********************< operator () >************************  
//   * Purpose: Receiving and assigning values with control    *  
//   * Example: x = A(1,5); A(3,7) = 5.;                       *  
//   ***********************************************************  
float &MatrixSparse::operator () (int row,int column)             
   {                                                              
   Element *elem = elementRow[row];                               
   if(elem == 0 || column < elem->column)                         
      return InsertElement(elem,row,column,1);                    
   if(column == elem->column)                                     
      return elem->value;                                         
   for(;elem->next != 0;elem = elem->next)                        
      {                                                           
      if(column == elem->next->column)                            
        return elem->next->value;                                 
      else if(column < elem->next->column)break;                  
      }                                                           
   return InsertElement(elem,row,column,0);                       
   }                                                              
                                                                  
                                                                  
//   *******************< DeleteMatrix >************************  
//   * Purpose: Eliminating a matrix of no use                 *  
//   * Example: A.DeleteMatrix();                              *  
//   ***********************************************************  
void MatrixSparse::DeleteMatrix(void)                             
   {                                                              
   if(elementRow == 0)return;                                     
   CleanMatrix();                                                 
   delete elementRow;                                             
   elementRow = 0;                                                
   numRows = numColumns = 0;                                      
   }                                                              
                                                                  
//   *******************< CleanMatrix >*************************  
//   * Purpose: Eliminating all coefficients of a matrix       *  
//   * Example: A.CleanMatrix();                               *  
//   ***********************************************************  
void MatrixSparse::CleanMatrix(void)                              
   {                                                              
   if(elementRow == 0)return;                                     
   Element *elem,*temp;                                           
   for(int row =1; row <= numRows; row++)                         
      {                                                           
      elem = elementRow[row];                                     
      while(elem != 0)                                            
        {                                                         
        temp = elem;                                              
        elem = elem->next;                                        
        delete temp;                                              
        }                                                         
      elementRow[row] = 0;                                        
      }                                                           
   }                                                              
                                                                  
                                                                  
int main()                                                        
{                                                                 
  MatrixSparse A(1000,1000);                                      
                                                                  
  A(1,1) = 15.;                                                   
  cout << A(1,1) <<"\n";                                          
  cout << A.Rows();                                               
                                                                  
                                                                  
}