Sparse Matrix: Fast Transpose

Sparse Matrix: Fast Transpose

#include<stdio.h>

#include<stdlib.h>

#define MAX 100

typedef struct

{

            int row;

            int col;

            int val;

}sparse;

void readsparse(sparse a[], int m, int n)

{

            int i, j, k, item, p;

            a[0].row = m;

            a[0].col = n;

            k = 1;

            printf("\nEnter the elements:\n");

            for(i=0; i<m; i++)

            {

                        for(j=0; j<n; j++)

                        {

                                    scanf("%d",&item);

                                    if(item == 0)

                                                continue;

                                    a[k].row = i;

                                    a[k].col = j;

                                    a[k].val = item;

                                    k++;

                        }

            }

            a[0].val = k-1;

            printf("\nThe entered sparse matrix is:\n");

            printf("\nRow\tColumn\tValue\n");

            for(p=0;  p<=a[0].val;  p++)

            {

                        printf("%d\t", a[p].row);

                        printf("%d\t", a[p].col);

                        printf("%d\n", a[p].val);

            }

}

void fast_transpose(sparse a[],  sparse b[])

{

            int row_terms[100],  start_pos[100];

            int i,  j,  p;       

            int numTerms = a[0].val;

            int numCols = a[0].col;

             

            b[0].row = numCols;

            b[0].col = a[0].row;

            b[0].val = numTerms;

            if(numTerms>0)

            {

                        for(i =0; i<numCols;  i++)

                                                row_terms[i] = 0;

                        for(i=1; i<=numTerms; i++)

                                                row_terms[a[i].col]++;

                        start_pos[0]=1;

                        for(i=1; i<numCols; i++)

                                                start_pos[i] = start_pos[i-1] + row_terms[i-1];

                        for(i=1; i<=numTerms; i++)

                        {

                                                j = start_pos[a[i].col]++;

                                    b[j].row = a[i].col;

                                                b[j].col = a[i].row;

                                                b[j].val = a[i].val;

                        }

             }

            printf("\nThe Fast Transpose sparse matrix is:\n");

            printf("\nRow\tColumn\tValue\n");

            for(p=0; p<=a[0].val; p++)

            {

                        printf("%d\t", b[p].row);

                        printf("%d\t", b[p].col);

                        printf("%d\n", b[p].val);

            }

}

void main()

{

            int m, n, key;

            sparse a[MAX], b[MAX];

            printf("\nEnter  the no of rows and columns:\t");

            scanf("%d%d",&m, &n);

            readsparse(a, m, n);

             fast_transpose(a, b);

}

Output:

Enter  the no of rows and columns:      6 6

Enter the elements:

15   0   0   22   0   -15

0   11   3   0    0   0

0   0   0   -6   0   0

0   0    0    0   0   0

91  0   0   0   0   0

0   0   28  0   0   0

The entered sparse matrix is:

Row     Column  Value

6       6       8

0       0       15

0       3       22

0       5       -15

1       1       11

1       2       3

2       4       -6

4       1       91

5       3       28

The Fast Transpose sparse matrix is:

Row    Column           Value

6          6                      8

0          0                      15

1          1                      11

1          4                      91

2          1                      3

3          0                      22

3          5                      28

4          2                      -6

5          0                      -15