توضیح در مورد ضرب ماتریس اسپارس

[shahinshyd]

با سلام
سر کلاس استاد یه سورس ماتریس اسپاریس نوشت که من هیچی نفهمیدم
اگه امکان داره یکم در مورد این سورس توضیح بدید
include<iostream.h>
#include<conio.h>
#include<stdlib.h>
int **arr,**bb,*t,*p;
int main()
{ clrscr();
int i,j,x,y,a=2,b=1,z=0,u=3;
cout<<"enter x:";
cin>>x;
cout<<"enter y:";
cin>>y;
p=(int *)malloc(sizeof(int)* x);
for(i=1;i<=x;i++)
arr[i]=(int *)malloc(y * sizeof(int));
for(i=1;i<=x;i++)
for(j=1;j<=y;j++)
{
cout<<"enter arr["<<i<<"]["<<j<<"]=";
cin>>arr[i][j];
}
for(i=1;i<=x;i++)
for(j=1;j<=y;j++)
if(arr[i][j]!=0 )z++;
t=(int *)malloc(u * sizeof(int));
for(i=1;i<x;i++)
bb[i]=(int *) malloc(z * sizeof(int));

bb[1][1]=x;
bb[1][2]=y;
bb[1][3]=z;
for(i=1;i<=x;i++)
for(j=1;j<=y;j++)
if(arr[i][j]!=0)
{
bb[a][b]=i;
b++;
bb[a][b]=j;
b++;
bb[a][b]=arr[i][j];
b=1;
a++;
}
for(i=1;i<=(z+1);i++)
for(j=1;j<=3;j++)
{
cout<<bb[i][j];
if (j==3)
cout<<endl;
}
getch();
return 0;
}

با تشکر

[shahinshyd]

با سلام از اساتید میخوام اگه مثال ساده تری دارند که به فهم این برنامه کمک میکنه راهنمایی کنند

[quiet_programmer]

با سلام.

اکه روش فشرده سازی ماتریس اسپارس رو بدونی کد بالا خیلی راحت به نظرت میرسه.
فکر نکنم از این ساده تر بشه فقط خوانایی کد پایینه.

حالا من توضیح میدم.
قبل توضیح کد لینک زیر رو نگاه کن که روش فشرده سازی و توضیح داده:
http://barnamenevis.org/showthread.php?281072-%D8%AC%D9%85%D8%B9-%D8%AF%D9%88-%D9%85%D8%A7%D8%AA%D8%B1%DB%8C%D8%B3-%D8%A7%D8%B3%D9%BE%D8%A7%D8%B1%D8%B3-%D8%AF%D8%B1-%D8%AD%D8%A7%D9%84%D8%AA-%D9%81%D8%B4%D8%B1%D8%AF%D9%87

خوب:
cout<<"enter x:"; cin>>x;
cout<<"enter y:";

ابعاد ماتریس رو میگیره: x میشه تعدا سطر y میشه ستون.
p=(int *)malloc(sizeof(int)* x); for(i=1;i<=x;i++)
arr[i]=(int *)malloc(y * sizeof(int));



یه ماتریس دو بعدی رو از حافظه با تعداد سطر x و ستون y میگیره.

for(i=1;i<=x;i++) for(j=1;j<=y;j++)
{
cout<<"enter arr["<<i<<"]["<<j<<"]=";
cin>>arr[i][j];
}

عناصر ماتریس رو میگیره و تو ماتریس ذخیره میکنه.

for(i=1;i<=x;i++) for(j=1;j<=y;j++)
if(arr[i][j]!=0 )z++;

تعداد عناصر غیر صفر ماتریس رو میشماره و داخل متغییر z قرار میده.
t=(int *)malloc(u * sizeof(int)); for(i=1;i<x;i++)
bb[i]=(int *) malloc(z * sizeof(int));


یه ماتریس 3 در z(تعداد عناصر غیر صفر) ایجاد میکنه. ماتریس اسپارس فشرده شده میره داخل این ماتریس

bb[1][1]=x; bb[1][2]=y;
bb[1][3]=z;

سطر اول ستون یک: تعداد سطرهای ماتریس اسپارس
سطر اول ستون دو: تعداد ستونهای ماتریس اسپارس
سطر اول ستون سه: تعداد عناصر غیر صفر در ماتریس اسپارس

for(i=1;i<=x;i++) for(j=1;j<=y;j++)
if(arr[i][j]!=0)
{
bb[a][b]=i;
b++;
bb[a][b]=j;
b++;
bb[a][b]=arr[i][j];
b=1;
a++;
}

عناصر غیر صفر از ماتریس اسپارس رو دونه دونه بر میداره و تو ماتریس bb به شکل زیر ذخیره میکنه.
تو سطر خالی از ماتریس bb:
ستون 1: سطر عنصر غیر صفر جاری
ستون 2: ستون عنصر غیر صفر جاری
ستون 3: مقدار عنصر غیر صفر جاری
بعد به ایندکس سطری که به سطر ماتریس bb اشاره میکنه یکی اضافه میکنه.
for(i=1;i<=(z+1);i++) for(j=1;j<=3;j++)
{
cout<<bb[i][j];
if (j==3)
cout<<endl;
}

در نهایت هم چاپ میکنه.
به این صورت که تو هر سطر سه تا ستون ماتریس نتیجه رو چاپ میکنه میره خط بعد.

[shahinshyd]

دوست من حالا این سورس عمل ضرب را انجام میده ؟اصلا ضرب ماتریس اسپارس یا همون ماتریس خلوت همانند ضرب دوماتریس مثلا2و3 در 2و4 هست؟
من نتها توضیحی که دربارش خوندم اینه که :
هنگامی که ماتریس خلوتی به صورت جدول ایندکس3*(N+1) ذخیره میشود که N تعداد عناصر غیر صفر ان است جهت ترانهاده کردن ان از روش زیر استفاده میکنیم.
ابتدا سطر اول (هدر) که بیانگر ابعاد و عناصر غیر صفر است را باجابه جا کردن سطر وستون ها در ترانهاد مینویسیم.
سپس در ستون وسطی به دنبال اعداد غیر صفر گشته و انها را درستون اول ترانهاد مینویسیم وستون اول متناظر درنمایش اولیه را در ستون وسط ترانهاد منویسیم .بعد از ان در ستون وسطی به دنبال اعداد 1 میگردیم و الی اخر.(فرض شماره سطر وستون ها از 0 شروع میشود)
اگه امکان داره به بیان ساده با مثال توضیح بدید.
با تشکر

[shahinshyd]

باسلام
دوست من مثل اینکه من سوال خودمو درست نگفتم من میخواستم که این برنامه دوتا ماتریس اپارس گرفته و در هم ضرب کنه لطفا راهنمایی کنید

[quiet_programmer]

با سلام.

برای دریافت سورس به لینک زیر مراجعه کن:

http://www.planet-source-code.com/vb/scripts/BrowseCategoryOrSearchResults.asp?optSort=Alphabet ical&txtCriteria=sparse+&blnWorldDropDownUsed=TRUE&txtMaxNumberOfEntriesPerPage=10&blnResetAllVariables=TRUE&lngWId=3&B1=Quick+Search

[quiet_programmer]

باسلام.

ببین این کد چهار عمل اصلی رو بر روی ماتریس اسپارس انجام میده. کد ترو تمیزیه به صورت کلاس در آوره به راحتی میتونی ازش استفاده کنی. (دانلود شده از لینک بالا)


69212

موفق باشی.

[ـraha_mt_]

باسلام.

ببین این کد چهار عمل اصلی رو بر روی ماتریس اسپارس انجام میده. کد ترو تمیزیه به صورت کلاس در آوره به راحتی میتونی ازش استفاده کنی. (دانلود شده از لینک بالا)


69212

موفق باشی.

سلام, میشه کسی قبل از ارایه برنامه توضیحی راجع به ضرب دو ماتریس اسپارس بدهد.
ضربی ک قراره روش انجام بدیم توسط اون ماتریس فشرده هایشان است؟؟
در آخر جواب ب چه صورتی نمایش داده میشود؟ فشرده یا معمولی؟؟

[marzi1055]

سلام میشه درباره الگوریتم ضرب دوماتری اسپارس باآرایه تک بعدی روآموزش بدین:گریه:توروخداعجله دارم ممنون