سوال درس ساختمان داده2

[engeneer_19]

سلام خسته نباشيد.اگه ممكنه جواب اين سوال رو ميخواستم: زودتر بهتر;)@};-


1-برنامه اي بنويسيد كه دو ماتريس اسپارس حداكثر ده عضوي غير صفر را دريافت و ذخيره و سپس حاصل جمع آنها را نشان دهد؟

[آبجی]

اون جوری که برای من توضیح دادی فکر کنم اینا رو میخوای حانیه جان :


خواندن ماتریس اسپارس و چاپ آن
چاپ ماتریس واقعی
جمع و تفریق و ضرب با ماتریسی دیگر



#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;
}
}


پایین هم یه توضیح کلی برات از ماتریس اسپارس میزارم

موفق باشی

[آبجی]

ماتریسی را که درصد کوچکی از عناصرش مخالف صفرند ، اسپارس گویند .

ماتریس های اسپارس بر حسب قرار گرفتن عناصر مخالف صفرش در ماتریس به دو گونه تقسیم می شوند :

1-ماتریس های اسپارس منظم (structured ) : که در این نوع ماتریس ، عناصر غیر صفر از لحاظ مکانی از نظم خاصی پیروی می کنند مثل اسپارس های چند قطری یا بلوکی .

2-ماتریس های اسپارس نا منظم (un structured ) : که عناصر غیر صفرش از لحاظ مکانی ، نظم ندارند.

برای حل دستگاه هایی که شامل ماتریس های اسپارس با n بسیار بزرگند ، می توان روش هایی را ارائه داد که سرعت محاسبه افزایش و مکان های اشغال شده حافظه کاهش یابد . یعنی می توان بجای ذخیره کل ماتریس ، فقط عناصر مخالف صفر و مکان آنها را ذخیره کرد . به این روش کمپرس کردن ماتریس گویند .

روش هایی برای کمپرس کردن ماتریس ها در زیر آمده است :

روش های کمپرس کردن ماتریس های اسپارس نا منظم :

coordinate format (coo)-1
در این روش ، کمپرس کردن در سه سطر صورت می گیرد :
AA= مقادیر عناصر مخالف صفر ماتریس
AR= شماره سطر عناصر مخالف صفر
AC= شماره ستون عناصر مخالف صفر

http://www.anzalimathhouse.com/images/Matrix2.bmp

AA = [ 1 , 3 , 4 , 1 , 6 , 2 , 3 , 2 ]
AR = [ 1 , 1 , 2 , 2 , 3 , 4 , 5 , 5 ]
AC = [ 2 , 5 , 3 , 4 , 5 , 1 , 2 , 5 ]
اگر تعداد عناصر مخالف صفر ماتریس را NZ فرض کنیم آنگاه این روش برای ماتریسی سودمند است که 3NZ<n که n مرتبه ماتریس است .


2 – Compressed Sparse row (CSR)


در این روش ، از سه سطر کمک می گیریم :
AA= مقادیر عناصر مخالف صفر ماتربیس
AC= شماره ستون عناصر مخالف صفر
IR= شماره عناصری از AA که شروع کننده هر سطرند .
مثال

http://www.anzalimathhouse.com/images/mat2.bmp


AA= [ 1 , 3 , 4 , 1 , 6 , 2 , 3 , 2]



AC= [ 2 , 5 , 3 , 4 , 5 , 1 , 2 , 5]



IR = [ 1 , 3 , 5 , 6 , 7 ]

در این روش 2NZ + t ( که تعداد سطرهای مخالف ماتریس اند ) مکانی از حافظه اشغال می شود پس این روش وقتی سودمند است که داشته باشیم :


2nz + t < n^2

در اين روش ماتريس را در دو سطر اول شامل عناصر مخالف صفر و سطر دوم شامل (I , j)|/ هایی است که برای هر I , j منحصر بفردند

http://www.anzalimathhouse.com/images/formul1.bmp
مثال : برای ماتریس A معرفی شده در بالا داریم :


AA= [ 1 , 3 , 4 , 1 , 6 , 2 , 3 , 2 ]



LD = [ 6 , 21 , 12 , 17 , 23 , 4 , 10 , 25 ]



http://www.anzalimathhouse.com/images/formul2.bmp

روشی برای ذخیره ماتریس های اسپارس چند قطری :
در این روش ، ماتریس را در دو نمونه ماتریسی به صورت زیر ذخیره می کنیم :
DIAG : در این ماتریس ، قطرها به صورت ستونی ذخیره می شوند .
IOFF : در این ماتریس سطری ، موقعیت قطرها نسبت به قطر اصلی جای می گیرند .


DIAG ( 1 : n , 1 : d )



IOFF ( 1 : d)

مثال :

http://www.anzalimathhouse.com/images/mat3.bmp


این هم یه توضیح جامع و کامل راجب ماتریس اسپارس ;)

[آبجی]

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

مثلاً اگر از یه آرایه n*n استفاده می کنید می توان از همان الگوریتم معمولی ضرب استفاده کرد:



1 void mm_mul_sa (sa_t *A, sa_t *B, sa_t *C)
2 {
3 int i, j, k;
4 int sum;
5
6 for (i = 0; i < A->num_rows; i++) {
7 for (j = 0; j < B->num_cols; j++) {
8 sum = 0;
9 for (k = 0; k < A->num_cols; k++) {
10 sum += saGet (A,i,k) * saGet (B,k,j);
11 }
12 saSet (C,i,j,sum);
13 }
14 }
15 }