هر الگوریتمی که روی یک ماتریس معمولی جواب بده، روی ماتریس اسپارس هم به درستی جواب میده (از جمله الگوریتم ترانهاده کردن ماتریس).

(۲۷ مهر ۱۳۹۲ ۰۹:۱۵ ب.ظ)nazanin2013 نوشته شده توسط:  سلام همگی
استادم تو درس ساختمان داده یه سوال داده که جواب بدیم.اونم اینه که چرا از الگوریتمی که برای محاسبه ترانهاده ماتریس های معمولی نوشته شده نمیشه واسه ماتریس اسپارس بکار برد؟من هر دو برنامه رو نوشتم هم ترانهاده ماتریس معمولی و هم اسپارس.اما وقتی یه ماتریس اسپارس به برنامه اولی که واسه ماتریس های معمولی نوشتم میدم خروجی درستی میده.میشه رهنمایی کنید؟حرف استاد درسته؟

نکته اینه که وقتی شما میای جای سطر و ستون ها رو عوض میکنی، ارایه شما باید بر اساس سطر مرتب باشه(یا بر اساس ستون ماتریس قبلی) یعنی اینکه ماتریس اسپارس شما هم بایر بر اساس سطر(ستون ماتریس قبلی) مرتب باشه.

سلام
ماتریس اسپارس ماتریسیه که تعداد عناصر غیر مفیدش زیادن و لزومی به نگه داری اونا نداریم برای همین از یه ماتریس سه ستونه استفاده می کنیم که تو سطر اولش اطلاعات ماتریس اسپارسمون میاد به این ترتیب: تعداد سطرها،تعداد ستون ها،تعداد مفید(غیر صفر) ماتریس.
بعد به تعداد عناصر مفید اطلاعات اون عناصر در هر سطر میاد که شامل شماره سطرو ستون و مقدار اون المنت.
برای مٍثال برای ماتریس زیر
[tex]\begin{bmatrix} 0&0 &0 \\ 1&0 &1 \\ 1&0 &0 \end{bmatrix}[/tex]
این نمایش به این صورت هستش
[tex]\begin{bmatrix} 3&3 &3 \\ 2&1 &1 \\ 2&3 &1 \\ 3&1 &1 \end{bmatrix}[/tex]
ترانهاده ماتریس رو میشه با جا به جا کردن سطرو ستونا عوض کرد مثلا برای ماتریس بالا ترانهادش میشه:
[tex]\begin{bmatrix} 0&1 &1 \\ 0&0 &1 \\ 1&0 &0 \end{bmatrix}[/tex]
اما اگه همین روال رو رو ماتریس سه ستون اطلاعاتمون اعمال کنیم جز یه کاربی فایده و کنترل نشده هیچ کار دیگه ای نکردیم/به عبارتی ما فقط اطلاعات ماتریسمونو خراب کردیم/شاید شما از اول خود ماتریس اولیه(که اسپارسه) رو ترانهاده کردید واسه همین جواب درست میشه
به هر شکل برای ترانهاده کردن از روی ماتریس سه ستونه الگوریتم به این شکله که :
(۱) تو سطر اول مقادیر سطرو ستونا رو جابجا می کنیم.
(۲) تو ستون دوم به دنبال کمترین عدد میگردیم(ستون صفر رو می خوایم سطر ماتریس جدید کنیم) وبعد جای سطر و ستونشو عوض میکنیم به سطر دوم منتقلش میکنیم.
و به همین ترتیب عناصر بزرگتر در مرحله دو