A C program to transpose a sparse matrix using simple transpose method

/*

Simple transpose of Sparse Matrix in C

Simple transpose method is rather simple to learn and understand (as the name suggests).Here Algorithm goes through each row of the sparse matrix by looking through all terms for once in the column. Its Time complexity is O(Number of columns * Number of values).

 Suppose we have a sparse matrix

We require three variables say (I, j, k ), so i takes values from 0-3 here (number of columns ([0][1]) ), j takes values from 1-6 ( max number of elements ([0][2])  & it starts from 1 because we put values in sparse matrix from second row) while k starts from 1.

So what happens is it first go, it will check if 0 is present in the column of sparse matrix. If yes, it will swap values in resultant matrix. So in first go, matrix will be like

 In second go, it will check for I = 1 (column for value 1 in sparse) and after swapping resultant matrix will be like

And after checking for I = 2 (column for value 2 in sparse), the resultant matrix will be

*/

#include<stdio.h>
#include<stdlib.h>
int r,c1;

void accept(int a1[10][10])
{
     int i,j;
     printf("Enter the Rows and Columns of matrix\n");
     scanf("%d%d",&r,&c1);
     printf("Enter the element\n");
     for (i=0;i<r;i++)
     {
for (j=0;j<c1;j++)
{
    scanf("%d",&a1[i][j]);
}
     }
}

void display(int a1[10][10],int r,int c)
{
     int i,j;
     for (i=0;i<r;i++)
     {
for (j=0;j<c;j++)
{
    printf("%d\t",a1[i][j]);
}
printf("\n");
     }
}

void convert (int a[10][10],int b[10][10],int r,int c)
{
     int i,j,k=1;
     for(i=0;i<r;i++)
{
for(j=0;j<c;j++)
{
if(a[i][j]!=0)
{
b[k][0]=i;
b[k][1]=j;
b[k][2]=a[i][j];
k++;
}
}
}
b[0][0]=r;
b[0][1]=c;
b[0][2]=k-1;
}

void simple(int b[10][10],int c1[10][10])
{
     int i,j,k=1;
     c1[0][0] = b[0][1];
c1[0][1] = b[0][0];
c1[0][2] = b[0][2];
if (b[0][2]>0)
{
k=1;
for (i=0;i<b[0][1];i++)
{
for (j=1;j<=b[0][2];j++)
{
if (b[j][1] == i)
{
c1[k][0] = b[j][1];
c1[k][1] = b[j][0];
c1[k][2] = b[j][2];
k++;
}
}
}
}
}

int main()
{
      system("clear");
     int a[10][10], b[10][10], c[10][10], d[10][10], e[10][10];
      accept(a);
      printf("The conventional matrix is \n");
      display(a,r,c1);
      convert(a,b,r,c1);
      printf("The sparse matrix is \n");
      display(b,b[0][2]+1,3);
      simple(b,c);
      printf("The transpose matrix is\n");
      display(c,c[0][2]+1,3);
}

A Simple program to transpose a sparse matrix using fast transpose method

/*

Fast transpose of Sparse Matrix in C

As its name suggests, it is a faster way to transpose a sparse and also a little bit hard to understand. Time complexity is O(Number of columns + Number of terms ). Here, we require 2 arrays, namely, count and position.

Count array mainly stores the values of columns present in sparse matrix.

Eg. If we have conventional matrix of size [3 x 4], then our count array will be {0,1,2,3,4}

Position array stores the position of the first occurrence of the values present in column of sparse. It is later incremented in the program.

*/

#include<stdio.h>
#include<stdlib.h>
int r,c1;

void accept(int a1[10][10])
{
     int i,j;
     printf("Enter the Rows and Columns of matrix\n");
     scanf("%d%d",&r,&c1);
     printf("Enter the element\n");
     for (i=0;i<r;i++)
     {
for (j=0;j<c1;j++)
{
    scanf("%d",&a1[i][j]);
}
     }
}

void display(int a1[10][10],int r,int c)
{
     int i,j;
     for (i=0;i<r;i++)
     {
for (j=0;j<c;j++)
{
    printf("%d\t",a1[i][j]);
}
printf("\n");
     }
}

void convert (int a[10][10],int b[10][10],int r,int c)
{
     int i,j,k=1;
     for(i=0;i<r;i++)
{
for(j=0;j<c;j++)
{
if(a[i][j]!=0)
{
b[k][0]=i;
b[k][1]=j;
b[k][2]=a[i][j];
k++;
}
}
}
b[0][0]=r;
b[0][1]=c;
b[0][2]=k-1;
}

void fast(int B[10][10],int C[10][10])
{
     int i,j,m,n,pos[3]={0,0,0},count[3]={0,0,0};
     for (i=1;i<=B[0][2];i++)
    {
m = B[i][1];
count[m]++;
    }
    pos[0] = 1;
    for (i=1;i<B[0][1];i++)
    {
pos[i] = pos [i-1] + count[i-1];
    }
    for (i=1;i<=B[0][2];i++)
    {
m = B[i][1];
n= pos[m];
pos[m]++;
C[n][0] = B[i][1];
C[n][1] = B[i][0];
C[n][2] = B[i][2];
    }
    C[0][0] = B[0][0];
    C[0][1] = B[0][1];
    C[0][2] = B[0][2];
}

int main()
{
     system("clear");
     int a[10][10], b[10][10], c[10][10], d[10][10], e[10][10];
      accept(a);
      printf("The conventional matrix is \n");
      display(a,r,c1);
      convert(a,b,r,c1);
      printf("The sparse matrix is \n");
      display(b,b[0][2]+1,3);
      fast(b,c);
      printf("The transpose of sparse matrix is\n");
      display(c,c[0][2]+1,3);
}

A Simple code to accept and display Sparse Matrix

/*
Accept and display Sparse Matrix
Sparse Matrix is the one which is created in place of conventional matrix so the space or memory consumption reduces. It actually neglects or removes the larger number of data present in a simple matrix which is repeated (In case of the below program, I considered this element as '0').

IF U GOT ANY PROBLEM WITH CODING OR THEORY, PUT IT IN COMMENTS
*/

// This code will work on Linux OS (say Ubuntu) only
// Here I took 0 as a maximum repeated value
#include<stdio.h> // preprocessor
#include<stdlib.h> // preprocessor
int r,c1; // took them as global so that it doesn't crate any problem

void accept(int a1[10][10]) // accept function
{
     int i,j;
     printf("Enter the Rows and Columns of matrix\n");
     scanf("%d%d",&r,&c1); // size of rows and columns accepted
     printf("Enter the element\n");
     for (i=0;i<r;i++)
     {
for (j=0;j<c1;j++)
{
    scanf("%d",&a1[i][j]);
}
     }
}

void display(int a1[10][10],int r,int c) // function to display both sparse and conventional matrix
{
     int i,j;
     printf("The matrix is\n");
     for (i=0;i<r;i++)
     {
for (j=0;j<c;j++)
{
    printf("%d\t",a1[i][j]);
}
printf("\n");
     }
}

void convert (int a[10][10],int b[10][10],int r,int c) // to convert conventional to sparse
{
     int i,j,k=1;
     for(i=0;i<r;i++) // goes through rows
{
for(j=0;j<c;j++) // goes through columns
{
if(a[i][j]!=0) // checks whether non zero elements are present
{
b[k][0]=i;
b[k][1]=j;
b[k][2]=a[i][j];
k++;
}
}
}
b[0][0]=r;
b[0][1]=c;
b[0][2]=k-1;
}

int main()
{
system("clear");
     int a[10][10], b[10][10], ch;
     while(1) // I wrote this program so that it runs continuously
     {
    printf("\n\tEnter the choice\n");
    printf("1. accept conventional matrix\n");
    printf("2. convert to sparse matrix\n");
      printf("3. Exit\n");
    scanf("%d",&ch);
    switch(ch)
    {
      case 1:
           accept(a);
           display(a,r,c1);
           break;
      case 2:
           convert (a,b,r,c1);
           display(b,b[0][2]+1,3);
           break;
      default:
           exit(0);
    }
     }
}