Working with Sparse Matrix

#include<stdio.h>
#include<conio.h>
# define MAX 50

struct triplet
{
int row;
int col;
int element;
}spmatrix[MAX];

void main()
{
clrscr();
int i, j, k=0, n, row, col;
printf("Array representation of Sparse Matrix\n\n");
printf("Enter Matrix Dimension:\n");
scanf("%d%d",&row,&col);
printf("\nEnter number of non-zero elements in sparse matrix: ");
scanf("%d",&n);

for(i=0;i<n;i++)
{
printf("\nEnter element row, element column and its value\n");
scanf("%d%d%d",&spmatrix[i].row,&spmatrix[i].col,&spmatrix[i].element);
}

printf("\nThe Sparse Matrix is:\n");

for(i=0;i<row;i++)
{
printf("\n");

for(j=0;j<col;j++)
{
if((spmatrix[k].row==(i+1))&&(spmatrix[k].col==(j+1)))
{
printf("\t%d",spmatrix[k].element);
k++;
}

else
{
printf("\t0");
}
}
}
getch();
}

Static Implementation of Stack

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define MAX 5

int stack[MAX], top;

void display()
{
int i;

printf("The Elements in Stack are:\n");
for(i=0;i<=top;i++)
{
printf("%d\n",stack[i]);
}
}

void push()
{
char no;

if(top==MAX-1) printf("Stack Overflow");

else
{
top=top+1;

printf("Enter a Number: ");
scanf("%d",&no);

stack[top]=no;
display();
}
}

void pop()
{
if(top==-1) printf("Stack Underflow");

else
{
top--;
display();
}
}

void main()
{
clrscr();
char ch=1;
top=-1;
char choice;
printf("Working with Data Structure\n\n");
printf("Menu\n\n1. Push\n2. Pop\n");
printf("0. Exit");

while(ch)
{
printf("\n\nEnter your choice: \n");
choice=getch();

switch(choice)
{
case '1': push();
break;

case '2': pop();
break;

case '0': return;

default: printf("Wrong choice");
}
}
}

Dynamic Implementation of Stack

#include<stdio.h>
#include<conio.h>
#include<alloc.h>

struct node
{
int info;
struct node *link;
}*top;

void create()
{
struct node *ptr, *cpt;
char ch;

ptr=(struct node*)malloc(sizeof(struct node));    //Allocating memory to ptr

printf("Enter the information of first node: ");
scanf("%d",&ptr->info);

ptr->link=NULL;

do
{
cpt=(struct node*)malloc(sizeof(struct node));    //Allocating memory to cpt

printf("\nEnter the information of next node: ");
scanf("%d",&(cpt->info));

cpt->link=ptr;
ptr=cpt;

printf("\nPress <Y> for more nodes\n");
ch=getch();
}
while(ch=='y'||ch=='Y');
top=ptr;
}

void traverse()
{
struct node *ptr;
ptr=top;

if(ptr==NULL) printf("Stack Underflow");

else
{
printf("\nThe Elements in the list are: ");
while(ptr!=NULL)
{
printf("\n%d",ptr->info);
ptr=ptr->link;
}
}
}

pop()
{
struct node *ptr;

if(top==NULL)
{
printf("Stack Underflow");
}

else
{
ptr=top;
top=ptr->link;
free(ptr);
traverse();
}
}

push()
{
struct node *ptr, *cpt;

ptr=(struct node*)malloc(sizeof(struct node));    //Allocating memory to ptr

printf("Enter the information of node: ");
scanf("%d",&ptr->info);

ptr->link=top;
top=ptr;
traverse();
}

void main()
{
clrscr();
char ch=1;
char choice;
printf("Working with Data Strucrure\n\n");
printf("Menu\n\n1. Create\n2. Push\n3. Pop\n4. Traverse\n");
printf("0. Exit");

while(ch)
{
printf("\n\nEnter your choice: \n");
choice=getch();

switch(choice)
{
case '1': create();
break;

case '2': push();
break;

case '3': pop();
break;

case '4': traverse();
break;

case '0': return;

default: printf("Wrong choice");
}
}
}

Potege Z20t Device

Toshiba has introduced Hybrid Toshiba Potraz Z20t device which runs on Windows 8.1. This Hybrid device has 12.5 inch touch screen. It comes with reversible keyboard power dock. It is powered by Intel Core M Processor. This device has option for RAM up to 8GB. It could be available in market by this month with 128GB, 256GB and 512GB SSD variants. This device owns 9 hours battery life according to company which can be extended to 17 hours with keyboard dock.

Sparse Matrix

These are special type of matrices in which most of the elements are "0s" (zeros). That is, if a lot of elements  from a matrix have a value 0 then the matrix is known as sparse matrix.

There is no precise definition of when a matrix is sparse and when it is not, but it is a concept, which we all recognize intuitively. If the matrix is a sparse, we must consider an alternative way of representing it rather than the normal row-major or column-major arrangement. This is because a sparse matrix is a matrix containing very few non-zero elements. If the user stores the entire matrix including zero elements then there is a wastage of storage space.

There are two ways of representing a sparse matrix:

• Arrays representation
• Linked representation

In array representation of of a sparse matrix, only the non-zero elements are stored so that storage space can be reduced. Each non-zero element in the sparse matrix is represented as (Row, Column, Value).

For this, a two-dimensional array containing 3 columns can be used. The first column is for storing the row number, the second column is for storing the column number and the third column is represents the value of corresponding to non-zero element at (row, column) in the first two columns. For example, consider the following sparse matrix.

Sparse Matrix of 5X6 Order

The above matrix can be represented as

Row	Column	Value
0	3	8
1	2	1
1	5	7
2	1	3
3	2	2
4	5	5

The structure declaration of array is given below:

#define MAX 50

struct triplet

{

int row;

int column;

int element;

}spmatrix[MAX];

The maximum number of non-zero elements in the sparse matrix is defined by constant MAX.

The array representation will use, [2*(n+1)*size of (int) + n*size of (T)] bytes of memory where n is the number of non-zero bytes and T is the data type of elements.

The major limitation of of array representation of a sparse matrix is that we need to know the number of non-zero elements in the matrix.

In the linked list representation, a separate list is maintained for each column as well as each row of the matrix, i.e., if the matrix is of size 4 X 4, then there would be 4 lists for 4 columns and 4 lists for 4 rows.

The head node for the column list stores the column number, a pointer to the node which comes first in the column and a pointer to the next column head node.

The head node for the row list stores, a pointer to the node, which comes first in the row list, and a pointer to the next row head node.

A node on the other hand stores the row number, column number and the value of the non-zero element of the sparse matrix. It also stores a pointer to the node that is immediatly to the right of the node in the row list as well as a pointer to the node that is immediatly below the node in the column list.

For example: A sparse matrix (5 X 6), the figure is given above:

The linked list representation of the above matrix is:

Linked List Representation of Sparse Matrix