header nodes

[brad sue]

I have a problem implementing sparse matrix.I want to create the header nodes but I just can't find the solution. this is what I have done:

This is the mnode class

//#include"matrix.h"
//#ifndef EXCEPTIONCLASS_H
//#define EXCEPTIONCLASS_H

#include<iostream>
using namespace std;

#include <string>
class mnode
{ public:
        mnode(int i, int j,float item=0,mnode* rightPtr=NULL,mnode* downPtr=NULL);
    /*
       purpose: to create a node to represent the (i,j)th entry of the
         sparse matrix.
      
    */    

        mnode* next(const string& specific) const;
    /* 
       purpose: get the next row or column node.
       
    */

        float& nodeData(); //const;  XXXXXXXXXXXXXXXXXXXXXXXXXXXXX  XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
    /*
       purpose: to get the stored matrix data/entry.
    */  

    int nodeIndex(const string& specific) const;
    /* 
       purpose: to get the row or column index of the node.
    */

    void set(const string& specific, mnode* aNode);
    /* 
       purpose: set the next row or column pointer.
         If specific = "down", set the next row node.
       exceptions: wrongData -- if specific is not "right" or "down".
    */

  private:
    int row;
    int col;
        float  data;
        mnode* right;
        mnode* down;
};

typedef mnode* rMnode;

//#endif
//------IMplementation mnode.h------------------------------
mnode::mnode(int i, int j,float item,mnode* rightPtr,mnode* downPtr)
{
          item=data;
          row=i;
          col=j;
          rightPtr=right;
          downPtr=down;
}

mnode* mnode::next(const string& specific) const
{
        
         if(specific=="right")
            return right;
         if(specific=="down")
            return down;
         //execption
}
          
float& mnode::nodeData() //const
{
         float& temp=data;
         return temp;
}

int mnode::nodeIndex(const string& specific) const
{
       if(specific=="row")
          return row;
       if(specific=="col")
          return col;   
}

void mnode::set(const string& specific, mnode* aNode)
{
     if(specific=="right")
        aNode=aNode->right;
     if(specific=="down")
         aNode=aNode->down;
     // exception
}

Note the pointer float* a is a pointer of a 2-dim full matrix .It is ONLY used to provide information to the constructor to construct the sparse matrix object and must not be used after that in the program.

class matrix
{ public:
    matrix(float* a, int n, int m);
    /*
       purpose: to create a nXm sparse matrix.
       requirement: both n and m are positive integers.
       promise: to create the sparse matrix using the mnode. If a is the     NULL pointer, the nXm zero matrix (all
         matrix entries are zeroes) is created.
       exceptions:
         wrongData -- if either n and/or m is not a positive integer.
    */

    void display() const;
    /*
       purpose: output the full matrix in a nice/formatted manner.  
       
    */

  private:
    int row, col;
    rMnode head;
};

//#endif
//----------Implementation matrix ------------------------------------------------------------------------------------
matrix::matrix(float* a, int n, int m)
{
        head->down=head;
        head->right=head;
        head->row=n;
        head->col=m;
        head->data=0;
        //create column header
        mnode* ptr=head;
        for(int j=1;j<=m;j++)
        {
                mnode* colheader;
                colheader->col=j;
                colheader->row=0;
                colheader->right=colheader;
                colheader->down=head;
                
                ptr->down=colheader;
                ptr=colheader;
        }

        //create row header
        mnode * ptr=head;
        for(int i=1;i<=n;i++)
        {
                mnode* rowheader;
                rowheader->col=0;
                rowheader->row=i;
                rowheader->down=rowheader;
                rowheader->right=head;
                
                ptr->right=rowheader;
                ptr=rowheader;
        }
        
}//end constructor

The implementation for the mnode compile ok(but not sure if right)
The compilation for matrix is not comiling well. Too much errors are in there
.
My second problem is How to use the float * a to store the non-zero element innthe sparse matrix.,how to find the correct header and insert the data at the good place.

Can I have some help for this?
I am struggling on it for several days now.
Thank you.
B

[zdf]

Hello,

Why don’t you use std::map?

[brad sue]

We are not allowed to use std::map

[zdf]

Are you allowed to write your own map?

[brad sue]

I will get back to you with a response , but I dont think so. We only talked about the use of circular linked list to implement the matrix.
B

[zdf]

Ok, I guess you must write everything from scratch. Did you learn about templates? Do you understand the code below?

template < typename A_T > class CNode
{

public:
  CNode() : m_pLeft( 0 ), m_pRight( 0 )
  {
    // nop
  }

  A_T m_Data;
  CNode* m_pLeft;
  CNode* m_pRight;

};

class CMatrixPos
{

public:
  unsigned short m_Col;
  unsigned short m_Row;

};

int main()
{
  CNode< CMatrixPos > Node;
  return 0;
}

[brad sue]

yes I learned about templates.

If I dont mistaken, You have created a class Cnode -construcror initialize to Null pointer for left and right.
Then you used a new class Cmatixpos to be the type of the Cnode class.
B

[zdf]

Ok. Here it is a possible solution to your problem:

#include <iostream>
#include <list>
#include <algorithm>

class CMatrixCell
{

public:
  CMatrixCell( unsigned short a_Col, unsigned short a_Row ) : m_Col( a_Col ), m_Row( a_Row )
  {
    // nop
  }
  CMatrixCell( unsigned short a_Col, unsigned short a_Row, float a_Value ) : m_Col( a_Col ), m_Row( a_Row ), m_Value( a_Value )
  {
    // nop
  }
  unsigned short m_Col;
  unsigned short m_Row;
  float m_Value;

  bool operator==( const CMatrixCell& a_Right ) const
  {
    return m_Col == a_Right.m_Col && m_Row == a_Right.m_Row;
  }

};

class CSparseMatrix
{

public:
  CSparseMatrix( float a_DefaultValue ) : m_DefaultValue( a_DefaultValue )
  {
    // nop
  }

  float Get( WORD a_Col, WORD a_Row ) const
  {
    using namespace std;
    list< CMatrixCell >::const_iterator i = find( m_List.begin(), m_List.end(), CMatrixCell( a_Col, a_Row ) );
    if ( i == m_List.end() )
      return m_DefaultValue;
    else
      return i->m_Value;
  }
  
  void Set( WORD a_Col, WORD a_Row, float a_Value )
  {
    using namespace std;
    list< CMatrixCell >::iterator i = find( m_List.begin(), m_List.end(), CMatrixCell( a_Col, a_Row ) );
    if ( i == m_List.end() )
      m_List.push_back( CMatrixCell( a_Col, a_Row, a_Value ) );
    else
      i->m_Value = a_Value;
  }

protected:
  float m_DefaultValue;
  std::list< CMatrixCell > m_List;

};

int main()
{
  CSparseMatrix m( 3. );
  m.Set( 0, 0, 10 );
  m.Set( 30, 0, 12 );

  std::cout << m.Get( 1, 1 ) << std::endl;
  std::cout << m.Get( 0, 0 ) << std::endl;
  return 0;
}

All you have to do is write your own generic list class and replace the standard list std::list.