-
header nodes
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
Code:
//#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.
Code:
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
-
Re: header nodes
Hello,
Why don’t you use std::map?
-
Re: header nodes
We are not allowed to use std::map
-
Re: header nodes
Are you allowed to write your own map?
-
Re: header nodes
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
-
Re: header nodes
Ok, I guess you must write everything from scratch. Did you learn about templates? Do you understand the code below?
Code:
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;
}
-
Re: header nodes
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
-
Re: header nodes
Ok. Here it is a possible solution to your problem:
Code:
#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.
