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

Sparse Matrix: Transpose

Sparse Matrix: 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 transpose(sparse a[], sparse b[])

{

          int i, j, k, n, p;

          n = a[0].val;

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

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

b[0].val  = n;

if( n > 0)

       {

                k = 1;

               for(i =  0; i<a[0].col ; i++)

              {

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

                    {

                           if(a[j].col == i)

                           {

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

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

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

                                     k++;

                            }

                     }

              }

        }

printf("\nThe 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;

sparse a[MAX], b[MAX];

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

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

readsparse(a, m, n);

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 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

Sparse Matrix

Sparse Matrix

#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 main()
{
int m, n;
sparse a[MAX];
printf("\nEnter  the no of rows and columns:\t");
scanf("%d%d",&m, &n);
readsparse(a, m, n);
}

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           3               -6
4           0               91
5           2               28

Arrays Bubble sort

Sorting an Array using Bubble Sort

#include<stdio.h>

void main()

{

         int i, j, n, a[10], temp;

         printf("\nEnter the value of n:");

         scanf("%d", &n);

         printf("\nEnter array elements:");

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

                   scanf("%d", &a[i]);

         for(i=0; i<n-1; i++)

        {

              for(j=0; j<n-1-i; j++)

              {

                    if(a[j+1]<a[j])

                    {

                             temp = a[j+1];

                             a[j+1] = a[j];

                             a[j] = temp;

                     }

                }

         }

          printf("\nBubble sort: array elements:");

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

                   printf("%d ", a[i]);

 }

Output

Enter the value of n: 7

Enter array elements: 3 2 1 5 6 9 1

Bubble sort: array elements: 1 1 2 3 5 6 9

Arrays Selection Sort

Sorting an Array using Selection Sort

#include<stdio.h>

void main()

{

          int i, j, n, a[10], temp;

          printf("\nEnter the value of n:");

          scanf("%d", &n);

          printf("\nEnter array elements:");

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

                  scanf("%d", &a[i]);

          for(i=0; i<n-1; i++)

         {

               for(j=i+1; j<n; j++)

               {

                     if(a[j]<a[i])

                    {

                            temp = a[j];

                            a[j] = a[i];

                            a[i] = temp;

                    }

               }

          }

          printf("\nSelection sort: array elements:");

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

                  printf("%d ", a[i]);

}

Output:

Enter the value of n:7

Enter array elements:3 2 1 5 6 9 1

Selection sort: array elements:1 1 2 3 5 6 9

Arrays Binary Search

Search for key Element in an Array using Binary Search

#include<stdio.h>

void main()

{

        int a[100], i, n, low, high, mid, key;

        printf("\nEnter value of n: ");

        scanf("%d", &n);

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

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

                        scanf("%d", &a[i]);

       printf("\nEnter key: ");

       scanf("%d", &key);

       low = 0;

       high = n-1;

       while(low<=high)

       {

                        mid = (low+high)/2;

                        if(key == a[mid])

                        {

                                        printf("\nKey element is found at position = %d",mid+1);

                                       break;

                        }

                        else  if(key<a[mid])

                                        high=mid-1;

                        else

                                        low=mid+1;

       }

       if(low>high)

                        printf("\nKey is not found");

}

Output:

Case 1:

Enter value of n: 6

Enter the array elements: 11 22 33 44 55 66

Enter key: 55

Key element is found at position = 5

Case 2:

Enter value of n: 6

Enter the array elements: 11 22 33 44 55 66

Enter key: 88

Key is not found

Arrays Linear Search

Search for key Element in an Array using Linear Search

Download the Program

#include<stdio.h>
void main()
{
    int i, j, n, a[100], key;
    printf("\nEnter value of n:");
    scanf("%d", &n);
    printf("\nEnter array elements:");
    for(i=0; i<n; i++)
    {
        scanf("%d", &a[i]);
    }
    printf("\nEnter key:");
    scanf("%d", &key);

    for(i=0; i<n; i++)
    {
            if(a[i] == key)
                break;
    }
    if(i<n)
        printf("\nKey found at position %d", i+1);
    else
        printf("\nNot found");
}

Output:
Enter value of n: 6
Enter array elements: 1  3  2  4  5  1
Enter key: 3
Key found at position 2

Program to Delete an Element from an Array at Valid Position

Write program to Delete an Element from an Array at Valid Position

#include<stdio.h>

#include<stdlib.h>

#define MAX 5

int a[MAX], pos, elem;

int n = 0;

void create();

void display();

void delete();

void main()

{

                int i;

                printf("\nEnter the number of elements: ");

                scanf("%d", &n);

                if(n!=0)

                                printf("\nEnter the elements: ");

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

                                {

                                                scanf("%d", &a[i]);

                                }

                delete();

                display();

}

void display()

{

                int i;

                if(n == 0)

                {

                                printf("\nNo elements to display");

                                return;

                }

                printf("\nArray elements are: ");

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

                                printf("%d\t ", a[i]);

}

void delete()

{

                int i;

                if(n == 0)

                {

                                printf("\nArray is empty and no elements to delete");

                                return;

                }

                do

                {

                                printf("\nEnter a valid position from where element to be deleted:    ");

                                scanf("%d", &pos);

                }while(pos>=n);

               

                elem = a[pos];

                printf("\nDeleted element is : %d \n", elem);

                for( i = pos; i< n-1; i++)

                {

                                a[i] = a[i+1];

                }

                n = n-1;

}

Output:

Case 1:

Enter the number of elements: 0

Array is empty and no elements to delete

No elements to display

Case 2:

Enter the number of elements: 3

Enter the elements: 11             12           13

Enter a valid position from where element to be deleted:    6

Enter a valid position from where element to be deleted:    1

Deleted element is : 12

Array elements are: 11    13

Program to Insert an Element to an Array at Valid Position

Write a program to Insert an Element to an Array at Valid Position

#include<stdio.h>

#include<stdlib.h>

#define MAX 5

int a[MAX], pos, elem;

int n = 0;

void create();

void display();

void insert();

void main()

{

                int i;

                printf("\nEnter the number of elements: ");

                scanf("%d", &n);

                if(n != 0)

                                printf("\nEnter the elements: ");

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

                                {

                                                scanf("%d", &a[i]);

                                }

                insert();

                display();

}

void display()

{

                int i;

                if(n == 0)

                {

                                printf("\nNo elements to display");

                                return;

                }

                printf("\nArray elements are: ");

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

                                printf("%d\t ", a[i]);

}

void insert()

{

                int i;

                if(n == MAX)

                {

                                printf("\nArray is full. Insertion is not possible");

                                return;

                }

                do

                {

                                printf("\nEnter a valid position where element to be inserted:    ");

                                scanf("%d", &pos);

                }while(pos>n);

                printf("\nEnter the value to be inserted:   ");

                scanf("%d", &elem);

                for(i =n-1; i>=pos ; i--)

                {

                                a[i+1] = a[i];

                }

                a[pos] = elem;

                n = n+1;

    }

Output:

Case 1:

Enter the number of elements: 3

Enter the elements: 11                  22           33

Enter a valid position where element to be inserted:    5

Enter a valid position where element to be inserted:    1

Enter the value to be inserted:   44

Array elements are: 11   44      22      33

Case 2:

Enter the number of elements: 5

Enter the elements: 11                  22           33           44           55

Array is full. Insertion is not possible

Array elements are: 11   22      33      44      55

Also Check,

• Program to Delete an Element from an Array at Valid Position

Arrays

Module 1: Arrays

• Read and Display elements of One dimensional Array

• Insert an Element to an Array at Valid Position

• Delete an Element from an Array at Valid Position

• Searching for Key element in an Array using Linear Search

• Searching for Key element in an Array using Binary Search

• Sorting an Array using Selection Sort

• Sorting an Array using Bubble Sort

• Polynomial Addition

• Sparse Matrix

• Sparse Matrix Transpose

• Sparse Matrix Fast Transpose

Program to Read and Display elements of One dimensional array

Write a program to Read and Display elements of One Dimensional Array

#include<stdio.h>

void main()

{

        int n, i, a[100];

        printf("\nEnter the number of elements:");

        scanf("%d", &n);

        printf("\nEnter the elements:");

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

        {

                        scanf("%d", &a[i]);

        }

        printf("\nArray elements are: ");

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

        {

                        printf("%d ", a[i]);

        }

}

Output:

Enter the number of elements:   5

Enter the elements:  1  2 3 4 5

Array elements are:    1 2 3 4 5

Also Check: 

• Program to Insert an Element to an Array at Valid Position
• Program to Delete an Element from an Array at Valid Position