Question

Write a program to convert a sparse matrix from a 2D array into
A. An array representation of nx3 size, where n is the number of non-zero elements in the
sparse matrix and each element is represented by row, column, and data.
B. A chain list (Linked list representation of the sparse matrix where each non-zero element
is represented by a node containing the data, row, column, and a p

Answer 1

#include <stdio.h>
#include <stdlib.h>

int** matrix_to_array(int n, int m, int matrix[][m], int *non_zero) {
    *non_zero = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (matrix[i][j] != 0)
                (*non_zero)++;

    int **array = malloc(*non_zero * sizeof(int*));
    int pos = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (matrix[i][j] != 0) {
                array[pos] = malloc(3 * sizeof(int));
                array[pos][0] = i;
                array[pos][1] = j;
                array[pos][2] = matrix[i][j];
                pos++;
            }
    return array;
}

 struct node {
    int data;
    int row;
    int column;
    struct node* next;
};

struct node *matrix_to_list(int n, int m, int matrix[][m]) {
    struct node *head = NULL;
    struct node *last = NULL;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (matrix[i][j] != 0) {
                struct node *next = malloc(sizeof(struct node));
                next->data = matrix[i][j];
                next->row = i;
                next->column = j;
                next->next = NULL;

                if (head == NULL)
                    head = next;
                if (last != NULL)
                    last->next = next;
                last = next;
            }
    return head;
}

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    int matrix[n][m];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            scanf("%d", &matrix[i][j]);

    int non_zero;
    int** arr = matrix_to_array(n, m, matrix, &non_zero);
    struct node *list = matrix_to_list(n, m, matrix);


    // print data and free all memory in the same time
    printf("Array:\n");
    for (int i = 0; i < non_zero; i++) {
        printf("(%d, %d): %d\n", arr[i][0], arr[i][1], arr[i][2]);
        free(arr[i]);
    }
    free(arr);

    printf("\nList:\n");
    while (list != NULL) {
        printf("(%d, %d): %d\n", list->row, list->column, list->data);
        struct node *tmp = list->next;
        free(list);
        list = tmp;
    }
}