Space matrix Space_Matrix_in_Data_Structures.pptx

🧮 Space Matrix in Data Structures

A space matrix (or sparse matrix) is a type of matrix that has most of its elements as zero (0) and only a few non-zero elements.
Since storing all zeros wastes memory, special representations are used to save only non-zero elements, making it memory-efficient.


---

🔹 1. What is a Sparse Matrix?

A matrix is called a sparse matrix if the number of zero elements is greater than the number of non-zero elements.

👉 Example:

\begin{bmatrix}
0 & 0 & 3 \\
0 & 4 & 0 \\
5 & 0 & 0
\end{bmatrix}

This is a 3×3 sparse matrix because most elements are zero.


---

🔹 2. Why Use Sparse Matrix Representation?

To save memory space

To reduce computation time

To optimize storage for matrices used in graphics, networks, scientific computations, etc
🧮 Space Matrix in Data Structures

A space matrix (or sparse matrix) is a type of matrix that has most of its elements as zero (0) and only a few non-zero elements.
Since storing all zeros wastes memory, special representations are used to save only non-zero elements, making it memory-efficient.


---

🔹 1. What is a Sparse Matrix?

A matrix is called a sparse matrix if the number of zero elements is greater than the number of non-zero elements.

👉 Example:

\begin{bmatrix}
0 & 0 & 3 \\
0 & 4 & 0 \\
5 & 0 & 0
\end{bmatrix}

This is a 3×3 sparse matrix because most elements are zero.


---

🔹 2. Why Use Sparse Matrix Representation?

To save memory space

To reduce computation time

To optimize storage for matrices used in graphics, networks, scientific computations, etc.



---

🔹 3. Representations of Sparse Matrix

There are several ways to represent a sparse matrix efficiently:


---

🟩 (a) Array Representation (Triplet Form)

We use a 3-column array where each row stores:

1. Row index


2. Column index


3. Non-zero value



👉 Example:

For the above matrix:

Row Column Value

0 2 3
1 1 4
2 0 5


Advantages:

Simple to implement

Saves memory



---

🟨 (b) Linked List Representation

Each non-zero element is represented by a node containing:

Row index

Column index

Value

Pointer to the next node


Structure in C:

struct Node {
int row, col, value;
struct Node *next;
};

Advantages:

Dynamic memory allocation (no need to predefine size)

Efficient for modification and insertion



---

🔹 4. Operations on Sparse Matrix

Operation Description

Transpose Swapping rows and columns efficiently
Addition Add two matrices by matching positions of non-zero elements
Multiplication Multiply matrices using non-zero entries only
Display Print the compact representation



---

🔹 5. Applications

Image processing

Graph representations (Adjacency matrices)

1. Space Matrix in Data Structures A matrix is a two-dimensional array of numbers arranged in rows and columns. When most of the elements are zero, it is called a Sparse Matrix.

2. Types of Matrices 1. Dense Matrix - Most elements are non-zero. 2. Sparse Matrix - Most elements are zero. Example Sparse Matrix: [5 0 0] [0 0 8] [0 0 0]

3. Why Sparse Matrix Representation? Storing all elements (including zeros) wastes memory. We store only non-zero elements along with their row and column positions.

4. Triplet Representation Each non-zero element is represented by: - Row index - Column index - Value Example: Row | Col | Value 0 | 0 | 5 1 | 2 | 8

5. Array of Structures Representation struct Element { int row; int col; int value; }; struct Sparse { int rows; int cols; int num; struct Element *e; };

6. Linked List Representation Each node represents a non-zero element and stores: - Row index - Column index - Value - Pointer to next node struct Node { int row, col, value; struct Node *next; };

7. Example Program in C #include <stdio.h> #include <stdlib.h> struct Element { int row, col, value; }; int main() { struct Element sparse[] = { {0, 0, 5}, {1, 2, 8} }; int size = 2; printf("Row Col Value\n"); for (int i = 0; i < size; i++) { printf("%d %d %d\n", sparse[i].row, sparse[i].col, sparse[i].value); } return 0; }

8. Advantages - Saves memory - Faster operations with non-zero elements - Useful for large, sparse data structures

9. Disadvantages - Complex implementation - Slower access compared to normal 2D arrays

10. Applications - Graph representation (Adjacency matrix) - Image processing - Optimization problems - Machine learning weight matrices

11. Conclusion Sparse Matrix efficiently stores matrices with many zeros. By saving only non-zero elements and their positions, it reduces memory and improves performance.