Data Structures and Algorithms (DSA) using C/C++: Sparse Matrix

Sparse matrix is a special type of matrix in which maximum elements [m×n/2 or 50% and more] are zero and some elements are non zero.

स्पार्स मैट्रिक्स एक विशेष प्रकार का आव्यूह होता है जिसमे आधे या उससे अधिक अवयव शून्य होते है एवं कुछ अवयव अशून्य होते है।

following two representations are used to store sparse matrix in a computer -

स्पार्स मैट्रिक्स को कंप्यूटर में निम्न दो प्रकार से संग्रहित किया जा सकता है -

1. Static /Array/Triplet representation of sparse matrix:- Array representation of sparse matrix uses a 2D array of 3 columns and non zero values+1 rows. Here first row of 2D array shows total number of rows, total number of columns and total number of non zero values exists in sparse matrix and other rows represents row index , column index and non zero value.

अरे रिप्रजेंटेशन में स्पार्स मैट्रिक्स के लिए एक 2D अरे का प्रयोग किया जाता है जिसमे 3 स्तम्भ एवं अशून्य संख्या +1 पंक्तियां होती है। प्रथम पंक्ति द्वारा कुल पंक्तियों की संख्या, कुल स्तंभों की संख्या एवं कुल अशून्य संख्या को प्रदर्शित किया जाता है एवं अन्य पंक्तियों द्वारा रो-इंडेक्स , कॉलम-इंडेक्स एवं अशून्य संख्या को प्रदर्शित किया जाता है।

Example (उदाहरण)-

Static /Array/Triplet representation of sparse matrix

2. Dynamic/Linked list representation of sparse matrix:- Linked list representation of sparse matrix uses Linked list data structure in which following 3 types of nodes are used to store sparse matrix :-

लिंक्डलिस्ट रिप्रजेंटेशन में स्पार्स मैट्रिक्स के लिए लिंक्ड लिस्ट डाटा स्ट्रक्चर का प्रयोग किया जाता है यहाँ निम्न तीन प्रकार के नोडस द्वारा स्पार्स मैट्रिक्स को संग्रहित किया जाता है-

Type A node:- type A node is also called header node. this node has three parts to store total number of rows and total number of columns and address of first type B node of sparse matrix. The address of type A node is stored in a pointer variable sparse.

टाइप A नोड को हैडर नोड भी कहा जाता है इस नोड में तीन भाग होते है जो क्रमशः कुल पंक्तियों की संख्या, कुल स्तंभों की संख्या एवं टाइप B नोड का एड्रेस रखते है। टाइप A नोड का एड्रेस स्पार्स पॉइंटर वेरिएबल में रखा जाता है।

Type B node:- In type B node Row number , address of next type B node/NULL and address of type C node are stored . It is also known as row node. Address of first type B node is stored in type A node.

टाइप B नोड पंक्तियों की संख्या, अगले टाइप B नोड का एड्रेस एवं टाइप C नोड का एड्रेस रखता है। इसे रो-नोड भी कहा जाता है। प्रथम टाइप B नोड का एड्रेस, टाइप A नोड में रखा जाता है।

Type C node:- In type C node column number , non zero value and address of next type C node/ NULL are stored. It is also known as column node. Type C node is prepared for each non zero value of type B node.

टाइप C नोड स्तंभ की संख्या, अशून्य संख्या एवं अगले टाइप C नोड का एड्रेस रखता है। इसे कॉलम-नोड भी कहा जाता है। टाइप C नोड का प्रयोग, टाइप B नोड की प्रत्येक अशून्य संख्या के लिए किया जाता है।