#include<conio.h>
#include<iostream.h>
#define Max 30
/*********************************************************/
class string;
class Sparse;
/*********************************************************/
class SparseNode
{
 int row, col;
 float value;
 friend class Sparse;
};
/*********************************************************/
class Sparse
{
  int Row, Col, Terms;
  SparseNode Data[Max];
 public:
  void ReadSparse( void );
  void WriteSparse( void );
  void WriteMatrix( void );
  void AddSparse( Sparse a, Sparse b );
  void ManfiSparse();
  void FastTranspose( Sparse b );
  int StoreSum( int sum, int&LastInResult, int r, int c );
  void Sparse :: MulSparse( Sparse a, Sparse b );
};
/*********************************************************/
void Sparse :: ReadSparse( void )
{
 clrscr();
 int i = 0;
 cout << "\n\n@ Lotfan Ettelaat Zir Ra Dar Mored Matrise Sparse Vared Konid : \n\n"
    << "$ Tadade Satrha              : ";
 cin >> Row;
 cout << "$ Tedade Sotoonha            : ";
 cin >> Col;
 do
 {
  cout << "$ Tedade Anasore Gheyre Sefr : ";
  cin >> Terms;
  if( Terms > ( Row * Col ) || Terms < 0 )
   cerr << "\nERROR ! ( In Tedad Ghabele Ghabool Nemibashad )\n\n";
 }
 while( Terms > ( Row * Col ) || Terms < 0 );
 while( i < Terms )
 {
  cout << "\n# Lotfan Shomarehye Satr Va Sotoone Onsore "
     << ( i + 1 )
     << " -om Ra Vared Konid : ";
  cin >> Data[i].row
    >> Data[i].col;
  if( Data[i].row > Row || Data[i].col > Col || Data[i].row < 1 || Data[i].col < 1 )
   cerr << "\nERROR ! ( In Jayegah Dar Moshakhkhasat Matris Nemigonjad )\n";
  else
  {
   cout << "* Lotfan Meghdar Onsor Ra Vared Konid : ";
   cin >> Data[i].value;
   i++;
  }
 }
 clrscr();
}
/*********************************************************/
void Sparse :: WriteSparse( void )
{
 int i;
 cout << "\n\n# Moshakhkhasat Matris Be Soorate Zir Ast :"
    << "\n\n~ Tedade Satrha = "
    << Row
    << "\n~ Tedade Sotoonha = "
    << Col
    << "\n~ Tedade Anasore Gheyre Sefr = "
    << Terms
    << "\n\n~ Liste Anasor Gheyre Sefre Matris Be Sharhe Zir Ast :\n\n"
    << "Satr\tSotoon\tMeghdar\n";
 for( i = 0; i < Terms; i++ )
  cout << Data[i].row
     << "\t"
     << Data[i].col
     << "\t"
     << Data[i].value
     << endl;
 getch();
}
/*********************************************************/
void Sparse :: WriteMatrix( void )
{
 clrscr();
 int i, j;
 float Matrix[Max][Max] = {0};
 cout << "\n\nMatrix Vaghei :\n\n";
 for( i = 0; i < Terms; i++ )
  Matrix[Data[i].row-1][Data[i].col-1] = Data[i].value;
   for( i = 0; i <= Col; i++ )
  cout << "[" << ( i ) << "]\t";
 for( i = 0; i < Row; i++ )
 {
  cout << "\n\n"
     << "[" << ( i+1 ) << "]";
  for( j = 0; j < Col; j++ )
  {
   cout << "\t"
      << Matrix[i][j];
  }
 }
 getch();
   clrscr();
}
/*********************************************************/
void Sparse :: AddSparse( Sparse a, Sparse b )
{
 int i, j, k;
 i = j = k = 0;
 if( a.Row != b.Row || a.Col != b.Col )
 {
  cout << "\n*** ERROR !!! Nemitavan In 2 Matris Ra Ba Ham Jame Kard ***";
  return;
 }
 Row = a.Row;
 Col = a.Col;
 while( i < a.Terms && j < b.Terms )
 {
  if( a.Data[i].row < b.Data[j].row || ( a.Data[i].row == b.Data[j].row && a.Data[i].col < b.Data[j].col ) )
  {
   Data[k].row = a.Data[i].row;
   Data[k].col = a.Data[i].col;
   Data[k++].value = a.Data[i++].value;
  }
  else if( a.Data[i].row > b.Data[j].row || ( a.Data[i].row == b.Data[j].row && a.Data[i].col > b.Data[j].col ) )
  {
   Data[k].row = b.Data[j].row;
   Data[k].col = b.Data[j].col;
   Data[k++].value = b.Data[j++].value;
  }
  else if( a.Data[i].value + b.Data[j].value )
  {
   Data[k].row = a.Data[i].row;
   Data[k].col = a.Data[i].col;
   Data[k++].value = a.Data[i++].value + b.Data[j++].value;
  }
  else
  {
   i++;
   j++;
  }
 }
 while( i < a.Terms )
 {
  Data[k].row = a.Data[i].row;
  Data[k].col = a.Data[i].col;
  Data[k++].value = a.Data[i++].value;
 }
 while( j < b.Terms )
 {
  Data[k].row = b.Data[j].row;
  Data[k].col = b.Data[j].col;
  Data[k++].value = b.Data[j++].value;
 }
 Terms = k;
}
/*********************************************************/
void Sparse :: ManfiSparse()
{
 for( int i = 0; i < Terms; i++ )
  Data[i].value *= -1;
}
/*********************************************************/
void Sparse :: FastTranspose( Sparse a )
{
 int i, k;
 int RowSize[Max], RowStart[Max];
 Row = a.Col;
 Col = a.Row;
 Terms = a.Terms;
 for( i = 0; i < a.Col; i++ )
    RowSize[i] = 0;
 for( i = 0; i < a.Terms; i++ )
  RowSize[a.Data[i].col-1]++;
 RowStart[0] = 0;
 for( i = 1; i < a.Col; i++ )
  RowStart[i] = RowStart[i-1] + RowSize[i-1];
 for( i = 0; i < a.Terms; i++ )
 {
  k = RowStart[a.Data[i].col-1]++;
  Data[k].row = a.Data[i].col;            
  Data[k].col = a.Data[i].row;
  Data[k].value = a.Data[i].value;
 }
}
/*********************************************************/
int Sparse :: StoreSum( int sum, int&LastInResult, int r, int c )
{
 if( sum != 0 )
  if( LastInResult < Max-1 )
  {
   LastInResult++;
   Data[LastInResult].row = r;
   Data[LastInResult].col = c;
   Data[LastInResult].value = sum;
   return 0;
  }
  else
  {
   cerr << "\n*** ERROR !!! Tedade Anasore Gheyre Sefr Az Fazaye Arayeh Biroon Mizanad ***\n";
   return 1;
  }
 else
  return 0;
}
/*********************************************************/
char compare( int x, int y )
{
 if( x < y )
  return '<';
 else if( x == y )
  return '=';
 return '>';
}
/*********************************************************/
void Sparse :: MulSparse( Sparse a, Sparse b )
{
 if( a.Col != b.Row )
 {
  cout << "\n*** ERROR !!! Zarbe 2 Matris Emkan Pazir Nist ***";
  Row = 0;
  Col = 0;
  Terms = 0;
  return;
 }
 if( ( a.Terms == Max ) || ( b.Terms == Max ) )
 {
  cout << "*** ERROR !!! Yek Fazaye Khali Dar Matris 'A' Ya 'B' Lazem Ast ***";
  Row = 0;
  Col = 0;
  Terms = 0;
  return;
 }
 Sparse d;
 d.FastTranspose( b );
 int currRowIndex = 0, LastInResult = -1, currRowBegin = 0, currRowA = a.Data[0].row;
 a.Data[a.Terms].row = a.Row;
 d.Data[b.Terms].row = b.Col;
 d.Data[b.Terms].col = -1;
 int sum = 0;
 while( currRowIndex < a.Terms )
 {
  int currColB = d.Data[0].row;
  int currColIndex = 0;
  while( currColIndex <= b.Terms )
  {
   if( a.Data[currRowIndex].row != currRowA )
   {
    if( StoreSum( sum, LastInResult, currRowA, currColB ) )
    {
     Row = 0;
     Col = 0;
     Terms = 0;
     cout << "\n *** ERROR !!! ***";
     return;
    }
    else
     sum = 0;
    currRowIndex = currRowBegin;
    while ( d.Data[currColIndex].row == currColB )
     currColIndex++;
    currColB = d.Data[currColIndex].row;
   }
   else if( d.Data[currColIndex].row != currColB)
   {
    if( StoreSum( sum, LastInResult, currRowA, currColB ) )
    {
     Row = 0;
     Col = 0;
     Terms = 0;
     cout << "\n *** ERROR !!! ***";
     return;
    }
    else
     sum = 0;
    currRowIndex = currRowBegin;
    currColB = d.Data[currColIndex].row;
   }
   else switch( compare( a.Data[currRowIndex].col, d.Data[currColIndex].col ) )
   {
    case '<' :
     currRowIndex++;
     break;
    case '=' :
     sum += a.Data[currRowIndex].value * d.Data[currColIndex].value;
     currRowIndex++;
     currColIndex++;
     break;
    case '>' :
     currColIndex++;
   }
  }
  while( a.Data[currRowIndex].row == currRowA )
   currRowIndex++;
  currRowBegin = currRowIndex;
  currRowA = a.Data[currRowIndex].row;
 }
 Row = a.Row;
 Col = b.Col;
 Terms = LastInResult + 1;
}
/*********************************************************/
void Moarrefi( void )
{
 clrscr();
 cout << "\t\t\t\tBe Name Khoda"
    << "\n\n\nBarname Nevis       : Mohammad Hasani Eghtedar"
    << "\n\nShomare Daneshjooti : 83525013"
    << "\n\nReshteye Tahsili    : Olume Computer"
    << "\n\nMaghtae Tahsili     : Karshenasi"
    << "\n\nSale Tahsili        : 1384 - 1385 Nimehye Avval"
    << "\n\nMahale Tahsil       : Daneshgahe Dolatiye Qom"
    << "\n\nOstad               : Aghaye Sayyed Esmaeili"
    << "\n\n\n\n\t\t\t\tKelidi Ra Befesharid";
 getch();
}
/*********************************************************/
void Meno( void )
{
 clrscr();
 cout << "\n# Lotfan Alamat Morede Nazar Ra Vared Konid :\n"
    << "\n+ : Jam Ba Matrisi Digar"
    << "\n- : Tafrigh Az Matrisi Digar"
    << "\n* : Zarb Dar Matrisi Digar"
    << "\nP : Chape Matrise Vagheyi"
    << "\nT : Tarane Hadeye Matris";
}
/*********************************************************/
void main( void )
{
 Moarrefi();
 Sparse a, b, c;
 a.ReadSparse();
 a.WriteSparse();
 Meno();
 switch( getch() )
 {
  case '+' :
   b.ReadSparse();
   b.WriteSparse();
   c.AddSparse(a,b);
         cout << "\n\nAnswer Is : ";
   c.WriteSparse();
   break;
  case '-' :
       b.ReadSparse();
   b.WriteSparse();
   b.ManfiSparse();
   c.AddSparse(a,b);
         cout << "\n\nAnswer Is : ";
   c.WriteSparse();
   break;
  case '*' :
       b.ReadSparse();
   b.WriteSparse();
   c.MulSparse(a,b);
         clrscr();
   cout << "\n\nAnswer Is : ";
   c.WriteSparse();
   break;
  case 'p' :
   a.WriteMatrix();
   break;
  case 't' :
   c.FastTranspose( a );
         clrscr();
         cout << "\n\nAnswer Is : ";
   c.WriteSparse();
       break;
 }
}

#include<conio.h>
#include<iostream.h>
/***************************************************/
enum Boolean{FALSE,TRUE};
/***************************************************/
struct Triple
{
 int value,row,col;
};
/***************************************************/
class Matrix;
/***************************************************/
class MatrixNode
{
  friend istream& operator>>(istream& is,Matrix& matrix);
  friend ostream& operator<<(ostream& output,Matrix& matrix);
  friend class Matrix;
  MatrixNode *down,*right;
  Boolean head;
  union
  {
   MatrixNode *next;
   Triple triple;
  };
 public:
  MatrixNode(Boolean b,Triple *t);
};
/***************************************************/
MatrixNode::MatrixNode(Boolean b,Triple *t)
{
 head=b;
 if(b)right=next=this;
  else triple=*t;
}
/***************************************************/
typedef MatrixNode *MatrixNodePtr;
/***************************************************/
class Matrix
{
  friend istream& operator>>(istream& is,Matrix& matrix);
  friend ostream& operator<<(ostream& output,Matrix& matrix);
  MatrixNode *headnode;
 public:
  ~Matrix();
};
/***************************************************/
MatrixNode *av;
/***************************************************/
Matrix::~Matrix(void)
{
 if(!headnode)return;
 MatrixNode *y,*x=headnode->right;
 headnode->right=av;
 av=headnode;
 while(x!=headnode)
 {
  y=x->right;
  x->right=av;
  av=y;
  x=x->next;
 }
 headnode=0;
}
/***************************************************/
istream& operator>>(istream& is,Matrix& matrix)
{
 Triple s;
 int p;
   cout<<"Moshakhkhasat Matrise Esparse Ra Vared Konid :"<<endl;
 cout<<" Tedade Satrha = ";
 is>>s.row;
 cout<<" Tedade Sotoonha = ";
 is>>s.col;
 cout<<" Tedade Anasore Gheyre Sefr = ";
 is>>s.value;
 if(s.row>s.col)p=s.row;
  else p=s.col;
 matrix.headnode=new MatrixNode(FALSE,&s);
 if(p==0)
 {
  matrix.headnode->right=matrix.headnode;
  return is;
 }
 MatrixNodePtr *head=new MatrixNodePtr[p];
 for(int i=0;i<p;i++)head[i]=new MatrixNode(TRUE,0);
 int CurrentRow=0;
 MatrixNode *last=head[0];
 for(i=0;i<s.value;i++)
 {
  Triple t;
  cout<<endl<<"Onsore Geyre Sefre Shomarehye "<<i+1<<" : "<<endl;
  cout<<" i = ";
  is>>t.row;
  cout<<" j = ";
  is>>t.col;
  cout<<" a["<<t.row<<"]["<<t.col<<"] = ";
  is>>t.value;
  if(t.row>CurrentRow)
  {
   last->right=head[CurrentRow];
   CurrentRow=t.row;
   last=head[CurrentRow];
  }
  last=last->right=new MatrixNode(FALSE,&t);
  head[t.col]->next=head[t.col]->next->down=last;
 }
 last->right=head[CurrentRow];
 for(i=0;i<s.col;i++)head[i]->next->down=head[i];
 for(i=0;i<p-1;i++)head[i]->next=head[i+1];
 head[p-1]->next=matrix.headnode;
 matrix.headnode->right=head[0];
 delete[]head;
 return is;
}
/***************************************************/
ostream& operator<<(ostream& output,Matrix& matrix)
{
 cout<<endl<<"Moshakhkhasat Matris Be Soorate Zir Ast :";
 cout<<endl<<"Tedade Satrha = "<<matrix.headnode->triple.row<<" ; Tedade Sotoonha = "<<matrix.headnode->triple.col<<" ; Tedade Anasore Gheyre Sefr = "<<matrix.headnode->triple.value;
 cout<<endl<<"Liste Anasor Gheyre Sefre Matris Be Sharhe Zir Ast :"<<endl;
 cout<<endl<<"i\tj\ta[i][j]"<<endl<<endl;
 MatrixNode *HeadR,*HeadD;
 for(HeadD=matrix.headnode->right;HeadD!=matrix.headnode;HeadD=HeadD->next)
  for(HeadR=HeadD->right;HeadR!=HeadR->right&&HeadR->right->triple.value!=0;HeadR=HeadR->right)
  {
   output<<HeadR->triple.row<<"\t"<<HeadR->triple.col<<"\t"<<HeadR->triple.value;
   HeadR->triple.value=0;
   cout<<endl;
  }
 return output;
}
/***************************************************/
void main(void)
{
 Matrix matrix;
 cin>>matrix;
 cout<<matrix;
}

برنامه نویس : محمد حسنی اقتدار

نوشته شده توسط مدیریت در شنبه 1384/09/05 |