C 

In this example we will see how to represent sparse matrix using C programming language. A sparse matrix is one where most of its elements are zero (0). For example, the following image represents a sparse matrix:

Such matrix can be represented more economically in terms of space if two dimensional array is not used to represent the matrix. The idea is to store the data regarding non-zero elements only. In this manner the matrix is thought of as an ordered list of non-zero elements with three parts:

  • An integer represents its row
  • An integer represents its column
  • The data associated with this element or at row & column indices

So we can define structure in C programming language as shown below.

An element can be implemented as shown below:

typedef struct element {
    int row, col, val;
} element;

A sparse matrix can be implemented as shown below:

typedef struct spmat {
    element data[100];
    int noOfRows, noOfCols, noOfElements;
} spmat;

So the above 4×5 matrix as shown in the image, can be described as a one-dimensional array sp, such that sp.noOfElements is 6, sp.noOfRows is 4, sp.noOfCols is 5 and sp.data can be depicted as shown below:

0, 2, 30, 4, 41, 2, 51, 3, 73, 1, 23, 2, 6

So each element in the array is 3-tuples in the above representation.

Now we will see how to find out number of elements in each column. The below function does the job.

void noOfElementsInColoumn(spmat *s) {
    int i,j, count = 0;

    for(i=0; i<s->noOfCols; i++) {
        count = 0;

        for(j=0; j<s->noOfElements; j++) {
            if(s->data[j].col == i) {
                count++;
            }
        }

        printf("\nNumber of elements in column %d is %d", i , count);
    }
}

The next problem is to deal with computing the transpose of the sparse matrix.

The below function does the required job to perform the transpose of the given sparse matrix.

spmat* transposeMatrix(spmat *s) {
    int i, j, k=0;
    spmat *t;

    t = malloc(sizeof(spmat));

    t->noOfRows = s->noOfCols;
    t->noOfCols = s->noOfRows;
    t->noOfElements = s->noOfElements;

    for(i=0; i<s->noOfCols; i++) {
        for(j=0; j<s->noOfElements; j++) {
            if(s->data[j].col == i) {
                t->data[k].row = i;
                t->data[k].col = s->data[j].row;
                t->data[k].val = s->data[j].val;
                k++;
            }
        }
    }

    return t;
}

We will also use the below function to print the matrix:

void printMatrix(spmat *s) {
    int i;

    for(i=0; i<s->noOfElements; i++) {
        printf("[%d, %d, %d] ", s->data[i].row, s->data[i].col, s->data[i].val);
    }

    printf("\n");
}

The main function that will ask for user input for sparse matrix, it will print the given sparse matrix, it will display the number of elements in each column and it will display the transpose of the given sparse matrix.

sparse matrix using c program

That’s all about sparse matrix representation using C program.

Source Code

Download

Thanks for reading.

Tags:

Leave a Reply

Your email address will not be published. Required fields are marked *