بسم الله الرحمن الرحيم

المصفوفة المتناثرة أو مصفوفة الأصفار ( Sparse Matrix ) :

لو ألقينا نظرة على المصفوفة التالية التي تحوي 6 صفوف و6 أعمدة وتتكون من : 6x 6 = 36 عنصر  :

سيتضح لنا من الوهلة الأولى أن أكثر عناصر هذه المصفوفة عبارة عن " أصفار " ؛ تسمى المصفوفة  التي أكثر عناصرها أصفار  بـمصفوفة الأصفار أو المصفوفة المتناثرة " Sparse Matrix " .. ومن الصعب علينا تحديد ما إذا كانت المصفوفة عبارة عن Sparse Matrix أو لا .. ولكن يتضح لنا ذلك عن طريق النظر ؛ ففي المصفوفة السابقة يوجد فقط 8 عناصر لا تساوي الصفر من أصل  36 عنصر ؛  بينما البقية كلها أصفار ..
تستخدم الـ Sparse Matrix لتوفير المساحة في الذاكرة حيث نستطيع تخزين العناصر الغير مساوية للصفر فيها ففقط ؛ وذلك من خلال استخدام مصفوفة وحيدة لكل عنصر من عناصرها يوجد 3 صفات هي : الصف والعمود والقيمة الخاصة به  ؛ ويتم ذلك عن طريق استخدامنا لـStructure   يحوي هذه الصفات  ؛ كالتالي :
 

#define MAX_TERMS 10 /* maximum number of terms + 1 */
typedef struct {
  int row ;
  int col ;
  int value ;
  } sparse;
sparse a[MAX_TERMS] ;

ولكن يجب أن نراعي هنا أن ترتيب العناصر في هذه المصفوفة الوحيدة سيكون تابع لأحد هذه الصفات وهو الصف " row  " و لابد من أن يكون  تصاعدياً ..
ملاحظة : لتتعلم أكثر عن الـ Structures راجع هذا الدرس للأخ طلال : السجلات في سي " Structures in C "

إذن .. يتضح لدينا أن تعريف الـ Sparse Matrix كما هو موجود في قاموسنا كالتالي :
مصفوفة ذات بعد واحد تحوي الكثير من العناصر المتشابهة ، والتي غالباً ما تساوي صفر. ، لكل عنصر فيها ثلاث صفات : الصف ، العمود ، والقيمة التي تسند إليه .

* Sparse_Matrix : a set of triples < row , col , value > , where row & column are integers & from a unique combination , & value comes from the set item .
* Sparse_Matrix Create(max_row , max_col) ::= return a Sparse_Matrix that can hold up to max_item = max_row X max_col ,& whose maximum row size is max_row , & whose maximum column size is max_col.

ومن هنا نستطيع إعادة رسم الـ Sparse Matrix كما في الشكل التالي :

حيث أن a[0].row تحتوي عدد الأسطر الكلي للمصفوفة الأصلية ( في هذا المثال = 6 ) , كذلك a[0].col فهي تحوي عدد الأعمدة الكلي للمصفوفة الأصلية ( في هذا المثال = 6 ) , وأيضاً a[0].value عدد العناصر الغير مساوية للصفر فقط ( في هذا المثال = 8 ) .
ولكي نعرف رقم الصف لأي عنصر ننظر لـ Field row , وبالمثل إذا أردنا أن نعرف رقم العمود فننظر لـ Field col وستكون قيمة هذا العنصر مخزنة في Field value . والثلاثي < row , col , value > سيكون مرتب في المصفوفة على حسب الصفوف " تصاعدياً " كما ذكرنا سابقاً ..
ولكن كيف نستطيع كتابة شيفرة لإنشاء هذه المصفوفة بلغة السي ؟ هذا ما سنعرفه ان شاء الله خلال الاسطر التالية : سنقوم بالبداية بإنشاء Structure مشابه للمذكور أعلاه .. وسنفترض في مثالنا الحالي أن المصفوفة مكوّنة من 3 صفوف و3 أعمدة ..
وبعد ذلك نسمح للمستخدم بإدخال العناصر كمصفوفة عادية شريطة أن تكون أكثرها مساوية للصفر ونطبع المصفوفة بالطريقة التقليدية العادية :

 Part1:

//------------------((( Sparse Matrix )))---------------
#include
#define MAX_TERM 10
typedef struct {
   int row ;
   int col ;
   int val ;
   } sparse;

int main()
{
    sparse a[MAX_TERM]; //  تعريف المصفوفة الصفرية 
    int b[3][3] ;  //  تعريف مصفوفة عادية
    int i, j, count ;
    printf("Plz. Enter the element one by one with press Enter :\n");
    for (i=0 ; i <3 ; i++ ) {
       for (j=0 ; j <3 ; j++ ) {
          scanf("%i",&b[i][j]) ;
        } // end j loop
    } // end i loop

//------------>--------------- -
    printf("\n**********************************\n\nNormal_Mat rix is : \n") ;
    for (i=0 ; i <3 ; i++ ) {
        for (j=0 ; j <3 ; j++ ) {
           printf("%i \t",b[i][j]) ;
        } // end j loop
        printf("\n") ;
    } // end i loop

بعد ذلك .. نقوم بإنشاء الـ Sparse Matrix ؛ نخزّن في البداية عدد الصفوف الكلي وعدد الأعمدة الكلي  في كل من  a[0].row  و a[0].col .. ثم نضع عداداً  = 1  كفهرس لكي نبدأ التخزين ..
نقوم بعمل Loop يمّر على كل عناصر المصفوفة العادية ويسأل ما إذا كان هذا العنصر مساوياً للصفر أما لا ؟
إذا اتضح أن العنصر لا يساوي الصفر .. نقوم بتخزين رقم الصف الموجود فيه هذا العنصر وكذلك رقم العمود ثم نخزّن قيمة العنصر باستخدام  العداد الذي جعلنا قيمته =1 كفهرس  لأول عنصر يقابلنا غير مساوي للصفر  .. ثم نزيد قيمة العداد بواحد لكي يفهرس العنصر المخزن الجديد .. وهكذا إلى أن ننتهي من جميع عناصر المصفوفة الأصلية .
الآن قمنا بتخزين جميع القيم الغير مساوية للصفر في الـ Sparse Matrix  ولكن يتبقى Field واحد لم نخزّن به شئ .. أتعلمون ما هو ؟
إنه الـ Field  الخاص بعدد العناصر الغير مساوية للصفر في المصفوفة الأصلية (a[0].val ) .. ونستطيع معرفة عدد العناصر الغير مساوية للصفر من خلال العداد الذي فهرس العناصر ..
 ولكن نلاحظ هنا أن هذا العداد داخل Loop عندما انتهى التخزين قد زادت قيمته بواحد على عدد العناصر الغير مساوية للصفر ؛ فيجب علينا أن نقوم بانقاص قيمته بمقدار واحد ثم نخزنها في a[0].val ...
 إذن ؛ نستطيع طباعة المصفوفة المتناثرة الناتجة لدينا ..  وذلك بإضافة  الكود التالي للكود السابق  :  
 

 Part2:

//------------>----------------
a[0].row=3 ;
a[0].col=3 ;
count=1;
for (i=0 ; i <3 ; i++ ){
 for (j=0 ; j <3 ; j++ ){
  if ( b[i][j]!= 0 ){
   a[count].row=i ;
   a[count].col=j ;
   a[count].val=b[i][j] ;
   count++;
  } // end if
 } // end j loop
} // end i loop
a[0].val=count-1 ;
printf("\n*******************\n\nSparse_Matrix is : \nrow\tcol\tvalue\n---------------------\n") ;
 for ( i=0 ; i
    printf("%i\t",a[i].row) ;
    printf("%i\t",a[i].col) ;
    printf("%i\n",a[i].val) ;

 }

 return 0;

}// end of main

وهكذا .. نكون قد وفرنا الذاكرة لدينا عند استخدام مثل هذه المصفوفات في حل المشكلات الكبيرة ..

أتمنى أن أكون وفقت في الشرح .. وسنتعرض لعملية تدوير المصفوفة المتناثرة أو مصفوفة الأصفار (Sparse Matrix  Transpose ) في الدرس القادم إن شاء الله ..
تحياتي، وأشركونا في صالح الدعاء
 

المصفوفة المتناثرة أو مصفوفة الأصفار [ Sparse Matrix(1