Programming Forums - problem with node implementation

Programming Forums (http://www.programmingforums.org/forumindex.php)

- C++ (http://www.programmingforums.org/forum15.html)

- - problem with node implementation (http://www.programmingforums.org/showthread.php?t=12606)

problem with node implementation

Hi ,
I have problems implementing my mnode class for an implementation of a sparse matrix:

#include <string>

class matrix

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.

       parameters:

         i -- the row # of the matrix entry.

         j -- the column # of the matrix entry.

         item -- the value of the (i,j)th entry.

         rightPtr -- pointer to the next column.

         downPtr -- pointer to the next row.

       requirement: both i and j must be non-negative.

       promise: to create the (i,j)th matrix entry.

         If i is zero, then it is the header node for the jth column.

         If j is zero, then it is the header node for the ith column.

         If both i and j are zero, then it is the unique head for the matrix.

       

    */           



        mnode* next(const string& specific) const;

    /* 

       purpose: get the next row or column node.

       promise: if specific = "right", return the next column node.

         If specific = "down", return the next row node.

       exceptions: wrongData -- if specific is not "right" or "down".

    */        



       float& nodeData() const;

    

    /*

       purpose: to get the stored matrix data/entry.

       parameters: none.

       requirement: none.

       promise: return the stored data.

       exceptions: none.

    */     





    int nodeIndex(const string & specific) const;

    /* 

       purpose: to get the row or column index of the node.

       promise: if specific = "row", return the row index of this node.

         If specific = "column", return the column index of this node.*/    



    void set(const string& specific, mnode* aNode);

    

      /* 

       purpose: set the next row or column pointer.

       promise: if specific = "right", set the next column node.

         If specific = "down", set the next row node.

       

    */



    private:

        int row;

        int col;

        float  data;

        mnode* right;

        mnode* down;

};



typedef mnode* rMnode;





//------Implementation mnode.h------------------------------

mnode( int i, int j, float item,mnode* rightPtr, mnode* downPtr)

{

          item=data;

          row=i;

          col=j;

          rightPtr=right;

          downPtr=down;

}



mnode* next(const string & specific) const

{

        

         if(specific="right")

            return right;

         if(specific="down")

            return down;

         //execption

}

          

float& nodeData() const

{

         return data;

}



int nodeIndex(const string & specific) const

{

       if(specific="row")

          return row;

       if(specific="col")

          return col;   

}



void set( const string & specific, mnode* aNode)

{

     if(specific="right")

        aNode= aNode->right;

     if(specific="down")

         aNode=aNode->down;

     // exception

}



//--------------class matrix-----------------------



//#include "mnode.h"



class matrix

{ public:

    matrix(float* a, int n, int m);

    /*

       purpose: to create a nXm sparse matrix.

       parameters:

         a -- the pointer to the array of floating-point numbers

              representing the full (all numbers including zeroes)

              nXm matrix in row-major order.

         n -- the number of rows in the matrix.

         m -- the number of columns in the matrix.

       requirement: both n and m are positive integers.

       promise: to create the sparse matrix using the mnode as discussed

         in class.  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.  

       parameters: none.

       requirement: none.

       promise: output the full (including zero entries) matrix.

       exceptions: none.

    */

  private:

    int row, col;

    rMnode head;

};

I have not started implementing the matrix class but I have tons of weird errors for what I have done.
Errors are like 'aNode undeclared' or 'specific undeclared.'. and ISO C++ forbids declaration of `string' with no type
Also I dont know if my reasonning is all right for the functions I wrote.
Can someone help me with some guidance?

B.

You can' just put in "include <string>". The name isn't known. Put "using std::string;" up there at the top. Stuff like that.

Yeah ,
I forgot a bunch of thing in it. I just 2 errors here in red at the indicated lines.

class matrix

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.

       parameters:

         i -- the row # of the matrix entry.

         j -- the column # of the matrix entry.

         item -- the value of the (i,j)th entry.

         rightPtr -- pointer to the next column.

         downPtr -- pointer to the next row.

       requirement: both i and j must be non-negative.

       promise: to create the (i,j)th matrix entry.

         If i is zero, then it is the header node for the jth column.

         If j is zero, then it is the header node for the ith column.

         If both i and j are zero, then it is the unique head for the matrix.

       exceptions:

         wrongData -- if either i and/or j is negative.

    */   

        mnode* next(const string& specific) const;

    /* 

       purpose: get the next row or column node.

       parameters: specific -- specifies the desired direction, 

         "right" or "down".

       requirement: specific must be either "right" or "down".

       promise: if specific = "right", return the next column node.

         If specific = "down", return the next row node.

       exceptions: wrongData -- if specific is not "right" or "down".

    */

        float& nodeData() const;

    /*

       purpose: to get the stored matrix data/entry.

       parameters: none.

       requirement: none.

       promise: return the stored data.

       exceptions: none.

    */ 

    

    int nodeIndex(const string & specific) const;

    /* 

       purpose: to get the row or column index of the node.

       parameters: specific -- specifies the desired index, 

         "row" or "column".

       requirement: specific must be either "row" or "column".

       promise: if specific = "row", return the row index of this node.

         If specific = "column", return the column index of this node.

       exceptions: wrongData -- if specific is not "row" or "column".

    */

    

    void set(const string& specific, mnode* aNode);

    /* 

       purpose: set the next row or column pointer.

       parameters: specific -- specifies the desired direction, 

         "right" or "down".

       requirement: specific must be either "right" or "down".

       promise: if specific = "right", set the next column node.

         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;

}; error: multiple types in one declaration 

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;

}

       

float& mnode::nodeData() const

{

         return data; error: invalid initialization of reference of type 'float&' from expression of type 'const float' 

}

The first error bugs me a little. EDIT: IGET THE FIRST ERROR!!
B

Your nodeData function is const but you have it return a non-const reference to an internal variable. I suppose you either need to make the return type a "const float&" or perhaps just return a copy of data. The correct choice depends on you needs.

Dont you need to put ';' after class matrix??????

Hi,
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.
the class matrix:

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

One way, not necessarily the most efficient, but the most useful, would be to write a method that allows you to insert a value at any location. Then looping through the a array and inserting each non-zero value would be easy.
The insert method would have to do the following:
- create a new mnode with the value in it
- loop through the column headers from head->right to find the column
- loop down that column (using ->down) to find the right row
- insert the mnode at that point (or replace the value that is already there)
- if the value wasn't already in the sparse array:
- loop through the row headers from head->down to find the row
- loop right along that row to find the right column
- insert the mnode at that point

This is all just off the top of my head, and I haven't tried to implement it.

Looking at the mnode code:

float& mnode::nodeData() //const

{

         float& temp=data;

         return temp;

}

This looks wrong, why not just return data. I'm not even sure why you would want to return the reference to the data, if you want it const. If you just want the value, I would just return a float instead of float&. If you want to be able to update the value, then remove the const altogether.

void mnode::set(const string& specific, mnode* aNode)

{

     if(specific=="right")

        aNode=aNode->right;

     if(specific=="down")

         aNode=aNode->down;

     // exception

}

This isn't doing what the comment next to the declaration says. You should be setting the right or down pointer of the current node (i.e. this) to point to aNode.

Thank you Dark.
I will work on the modifications and the insert method.

Hi,
I am trying to implemement the operator * to multiply two sparse matrix.
I need some guidance to code it.
the fact that the zero elements are not stored make it difficult.

Please can someone help me?
I recall the two classes below :
thank you.

matrix.h

class matrix

{ public:

    matrix(float* a, int n, int m);   

 /* purpose: to create a nXm sparse matrix.*/



    void display() const;   

 /* purpose: output the full matrix in a nice/formatted manner.  */



  private:

    int row, col;

    rMnode head;

};

mnode.h

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;    

 /*  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.*/



  private:

    int row;

    int col;

        float  data;

        mnode* right;

        mnode* down;

};



typedef mnode* rMnode;