Sparse Matrix

Sparse Matrix

Numerical analysis in which  a matrix most elements are zeros

 Introduction
 in some situation we face with matrix that they have a lot of zeros element and as you know it is not necessary to multiple,add,... all of them.if there exists a way to ignore them then the matrix algorithms go better and more efficient.
so we can store matrix as list and everywhere that the element is zero we dont store it but in referencing to it we return zero.
if you do a quick look at  it you can see the algorithm,and if you run it you will enjoy



//in the name of allah
#include
using namespace std;
class sparseElem{
  public:
    int row,col;
    double value;
    sparseElem *nextRow;
    sparseElem *nextCol;
    sparseElem(){
    }
   
};


class sparseMatrix{
  public:
    int n,m;
    sparseElem *head_col;
    sparseElem *head_row;
    sparseElem*c;
    sparseElem *r;
    sparseMatrix(){
       m=3;n=3;
      head_col=head_row=NULL;
      c=new sparseElem[n];
      r=new sparseElem[m];
      for(int i=0;i
        r[i].row=i;
      for(int i=0;i
        c[i].col=i;
     }
    sparseMatrix(int m1,int n1){
      m=m1;n=n1;
      head_col=head_row=NULL;
      c=new sparseElem[n];
      r=new sparseElem[m];
      for(int i=0;i
        r[i].row=i;
      for(int i=0;i
        c[i].col=i;
    }
    void setElem(int i,int j,double x){
      sparseElem *tmp=new sparseElem;
        tmp->row=i;
        tmp->col=j;
        tmp->value=x;
        //important
        tmp->nextRow=NULL;                                        //point
        tmp->nextCol=NULL;
      if(!head_row){//head_row=head_col=NULL
        head_row=r+i;
        head_col=c+j;
        r[i].nextRow=tmp;
        r[i].nextCol=NULL;
        c[j].nextCol=tmp;
        c[j].nextRow=NULL;
        tmp->nextRow=NULL;
        tmp->nextCol=NULL;
      }
      else{
        sparseElem *pc=head_col;
        sparseElem *lpc=NULL;
        while(pc->nextRow!=NULL && tmp->col>pc->col){
        //cout<<"while 1"<
          lpc=pc;
          pc=pc->nextRow;
        }
        if(tmp->col < pc->col){
          if(lpc)
            lpc->nextRow=c+j;
          else
            head_col=c+j;
          (c+j)->nextRow=pc;
          c[j].nextCol=NULL;                                                                    //new
        }
      
        else if(tmp->col > pc->col){
          pc->nextRow=c+j;
          c[j].nextRow=NULL;                                      //new added                                                         maybe error
          c[j].nextCol=NULL;                                            //new added maybe optional
        }
        else//both are equal
          pc=c+j;
        //fixing r[i] ha
        sparseElem *pr=head_row;
        sparseElem *lpr=NULL;
        while(pr->nextCol!=NULL && tmp->row > pr->row){
        //cout<<"while 2"<
          lpr=pr;
          pr=pr->nextCol;
        }
        if(tmp->row < pr->row){
          if(lpr)
            lpr->nextCol=r+i;
          else
            head_row=r+i;//the first element is inserting;
          (r+i)->nextCol=pr;
          r[i].nextRow=NULL;                                                                //new
        }
        else if(tmp->row>pr->row){
          pr->nextCol=r+i;
          r[i].nextCol=NULL;                                      //new added
          r[i].nextRow=NULL;//r[i].nextCol=NULL;
        }
        else//both are equal
          pr=r+i;
        //fixing adding element to a others in sparseMatrix
       
        sparseElem *pc2=c+j;
        sparseElem *lpc2=NULL;
        while(pc2->nextCol!=NULL &&pc2->nextCol->rowrow){ 
           lpc2=pc2;
           pc2=pc2->nextCol;//chon dar haman sotun search mikonim
        }
        //agar az ghabk vojud dash faghat value ra be an midahim vagarne hame chiz be ham mirizad va hafeze ezafe mibarad
        if(pc2->nextCol && pc2->nextCol->row ==tmp->row)//      ! if(pc2->nextCol && pc2->nextCol->row>tmp->row)//                   new   error if(pc2->nextCol )
          pc2->nextCol->value=tmp->value;
          //tmp=NULL;//delete tmp; next is  deleting it in below
        else {//if(pc2->nextCol && pc2->nextCol->row > tmp->row){//``````````````````completely new
          lpc2=pc2;
          tmp->nextCol=lpc2->nextCol;
          pc2->nextCol=tmp;
          }
        sparseElem *pr2=r+i;
        sparseElem *lpr2=NULL;
        while(pr2->nextRow!=NULL &&pr2->nextRow->colcol){
           lpr2=pr2;
           pr2=pr2->nextRow;//chon dar haman sotun search mikonim
        }
        if(pr2->nextCol && pr2->nextRow->col ==tmp->col){
          delete tmp;
          }
        else{// if(pc2->nextCol && pc2->nextCol->col > tmp->col){
          lpr2=pr2;                        //       new error //lpr2=lpr;
          tmp->nextRow=lpr2->nextRow;
          pr2->nextRow=tmp;
        } 
      }
    }
    double getElem(int i,int j){
      sparseElem *pc=c+j;
      if(pc==NULL)//if there is no element in matrix returns 0
        return 0;
      while(pc->nextCol!=NULL){
        pc=pc->nextCol;
        if(pc->row==i)
          return pc->value;
        else if(pc->row>i)
          return 0;//if the row has been passed
      }
      return 0;
    }
   
    sparseMatrix *sparseAdd(sparseMatrix &A,sparseMatrix &B){
      sparseMatrix* C=new sparseMatrix(m,n);
      sparseElem *apr=A.head_row;
      while(apr!=NULL){
          sparseElem* ap=apr->nextRow;           
          while(ap){//p!=null
            C->setElem(ap->row,ap->col,A.getElem(ap->row,ap->col));
            ap=ap->nextRow;
          }
          apr=apr->nextCol;
      }
      double value;
      sparseElem *bpr=B.head_row;
      while(bpr!=NULL){
          sparseElem* bp=bpr->nextRow;
          while(bp){//p!=null
            value=C->getElem(bp->row,bp->col)+B.getElem(bp->row,bp->col);
            C->setElem(bp->row,bp->col,value);
            bp=bp->nextRow;
          }
          bpr=bpr->nextCol;
      }
     return C;
    }
    sparseMatrix *sparseMult(sparseMatrix &A,sparseMatrix &B){
      sparseMatrix *C=new  sparseMatrix(A.m,A.n);
      sparseElem *ar=A.head_row;
     
      while(ar){
        sparseElem *r=ar->nextRow;
        sparseElem *bc=B.head_col;
        while(bc){
            //bc=bc->nextRow;
            sparseElem *c=bc->nextCol;
            double value=0;
            while(c && r && c->rowcol)
                c=c->nextCol;
            while(r && c &&  r->colrow)
                r=r->nextRow;
            while(r && c){
              value+=r->value*c->value;
              r=r->nextRow;
              c=c->nextCol;
            }
            if(value)
              C->setElem(ar->row,bc->col,value);
            bc=bc->nextRow;//indexing
            r=ar->nextRow;
        }
        ar=ar->nextCol;
      }
      return C;
    }
};
int main(){
  int m,n;
  cout<<"please enter m,n:"<
  cin>>m>>n;
  sparseMatrix M(m,n);
  sparseMatrix N(m,n);
  double a;
 
  cout<<"please enter two matrix:"<
  for(int i=0;i
    for(int j=0;j
      cin>>a;
      if(a){
        M.setElem(i,j,a);
      }
    }
  cout<
  for(int i=0;i
    for(int j=0;j
      cin>>a;
      if(a){
        N.setElem(i,j,a);
      }
    }
  sparseMatrix *C=M.sparseMult(M,N);
  cout<<"this is multiplaying two matrices:"<
  for(int i=0;i
    for(int j=0;j
      a=C->getElem(i,j);
      cout<<<" ";
    }
  cout<
  }
 
}