Module 1

BASIC CONCEPTS: Structure & Union, Self-Referential Structures, Pointer to

Structure, Pointer to Function, Introduction to Data Structure and its classification,
the need for Data Structure, Dynamic Memory Allocation, Recursive Algorithms,
Sparse Matrices.

Structure & Union

Structure:

• A structure is a user defined data type contains an ordered group of data

objects.
• Unlike the elements of an array, the data objects within a structure can have
varied data types. Each data object in a structure is a member or field.
• struct is the keyword which is used to declare structure.

The general format of a structure definition is as follows:

struct tag_name
{
data_type member1;
data_type member2;
-------------
-------------
};

In defining a structure we may note the following syntax

[Link] template is terminated with a semicolon

2. While the entire definition is considered as a statement, each member is
declared independently for its name and type in a separate statement inside
the template
3. The tag name such as struct student can be used to declare structure
variables of its type, later in the program.

ISE, DSCE 1
DEFINING A STRUCTURE

• Structures must be defined first for their format that may be used later to
declare structure variables. Let us use an example to illustrate the process
of structure definition and the creation of structure variables.
• Consider a Student database consisting of name, rollno, marks. We can define
a structure to hold this information as follows:

struct student
{
char name[20]:
int rollno;
float percentage;
};
• The keyword struct declares a structure to hold the details of three data fields,
namely
• name, rollno, percentage. These fields are called structure elements or
members.
• Each member may belong to a different type of data. student is the name of
the structure and is called the structure tag.
• The tag name can be used to declare a structure variable.
• The above definition describes a format called template to represent
information as shown below:

DECLARING STRUCTURE VARIABLES

• After defining a structure format we can declare variables of that type.

• A structure variable declaration is similar to the declaration of variables of any
other data types. It includes the following elements:
1. The keyword struct.
2. The structure tag name.
3. List of variable names separated by commas.
4. A terminating semicolon.

ISE, DSCE 2
For example, the statement
struct student sl, s2, s3; declares s1, s2 and s3 as variables of type struct student

The complete declaration might look like this:

1. struct student 2. struct student

{ {
char name[20]: char name[20]:
int rollno; int rollno;
float percentage; float percentage;
} s1,s2; };
int main( )
{
struct student s1,s2;
}
3. struct student • When the compiler comes across a
{ declaration statement, it reserves
char name[20]:
memory space for the structure
int rollno;
float percentage; variables.
}; • It is also allowed to combine both
struct student s1,s2; the structure definition and
variables declaration in one
statement.

ACCESSING STRUCTURE MEMBERS

We can access and assign values to the members of a structure in a number of

ways.
The link between a member and a variable is established using the member
operator ‘.’ which is also known as 'dot operator' or 'period operator'.
For example,
[Link];
is the variable representing the rollno of student and can be treated like any other
ordinary variable. Here is how we would assign values to the members of student.

strcpy ([Link], "Praveen");

strcpy ([Link], "Anil");
[Link]=75.5;

We can also use scanf to give the values through the keyboard.

scanf("%s", [Link]);
scanf("%d", &[Link]); are valid input statements.

ISE, DSCE 3
Note: The definition and the declaration of structures can be placed either in local
or scope when the program has only main() function. But in case the program has
more than one function then it is placed in global scope to be accessed by both
functions. If it is made local to a function then it can be accessed by only that
function.

Initialization of Structure

C language does not permit the initialization of individual structure members within
the template.
The initialization must be done only in the declaration of the actual variables.

Note that the compile-time initialization of a structure variable must have the
following elements:

[Link] keyword struct.

2. The structure tag name
3. The name of the variable to be declared.
4. The assignment operator =.
5. A set of values for the members of the structure variable, separated by
commas and enclosed in braces
6. A terminating semicolon.

1. struct student 2. struct student

{ {
char name[20]; char name[20];
int rollno; int rollno;
float percentage; float percentage;
} s1={“Praveen”,3,75.5}; };
struct student s1={“Praveen”,3,75.5};
struct student s2={“Anil”,6,85.5};
3. Partial initialization Note:
struct student • Uninitialized members will be
{ automatically assigned to Zero for
char name[20]; integer and floating-point numbers.
int rollno;
• ‘\0’ for characters and strings
float percentage;
};
struct student s1={“Praveen”};

ISE, DSCE 4
Example program :

struct student // structure definition

{
char name[20]; // memebers of structure
int rollno;
float percentage;
} s2={“Praveen”,1,75.5};
int main( )
{
struct student s1={“kumar”,2,80}; // compile time initialization
struct student s3,s4; // variable declaration
strcpy([Link],”suman”);
[Link]=3; // Accessing structure member using dot (.)
[Link]=95.5;
printf(“enter the details of s4 students: name, rollno, percentage”);// runtime
initialization
scanf(“%s %d %f”,[Link],&[Link],&[Link]);
printf(“name =%s rollno=%d percentage=%f”,[Link],[Link],[Link]);
}

USER-DEFINED DATA TYPES (typedef)

• The typedef keyword gives a meaningful name to the existing data type which
helps other users to understand the program more easily.
• It can be used with structures to increase code readability and we don't have
to type struct repeatedly.

typedef in structures

1. typedef struct student // structure definition

{
char name[20]; // memebers of structure
int rollno;
float percentage;
}stu;

2. struct student // structure definition

{
char name[20]; // memebers of structure
int rollno;
float percentage;
};
typedef struct student s;

ISE, DSCE 5
Here s is the type name.

The type_name represents structure definition associated with it and therefore can
be used to declare structure variables as shown below:

type_name variable1, variable2,……;

Example Program: use typedef to input and output one student details consisting name,
rollno, percentage.

typedef struct student

{
char name[20];
int rollno;
float percentage;
}stu;
void main()
{
stu s1;
printf("\n Enter name , rollno and percentage”);
scanf("%s %d %f”,[Link],&[Link],&[Link]);
printf("\n Entered name , rollno and percentage”);
printf("%s %d %f”,[Link],[Link],[Link]);
}
Output
Entered name, rollno and percentage
Praveen 1 75.5

UNIONS

Union is a derived datatype , like structure, i.e. collection of elements of different

data types which are grouped together. Each element in a union is called member.

• Union and structure in C are same in concepts, except allocating memory

for their members.
• Structure allocates storage space for all its members separately.
• Whereas, Union allocates one common storage space for all its members, or
memory space is shared between its members.
• Only one member of union can be accessed at a time. All member values
cannot be accessed at the same time in union. But, structure can access all
member values at the same time. This is because, Union allocates one
common storage space for all its members, where as Structure allocates
storage space for all its members separately.

ISE, DSCE 6
 • Many union variables can be created in a program and memory will be
allocated for each union variable separately.
• The table below will help you how to form a C union, declare a union,
initializing and accessing the members of the union.

Type Using Normal variable Using pointer variable

union tag_name union tag_name
{ {
data type var_name1; data type var_name1;
Syntax
data type var_name2; data type var_name2;
data type var_name3; data type var_name3;
}; };
union student union student
{ {
int mark; int mark;
Example
char name[10]; char name[10]; float average;
float average; };
};
Declaring union
union student report; union student *report, rep;
variable
Initializing union union student report = {100, union student rep = {100,
variable “Mani”, 99.5}; “Mani”, 99.5};report = &rep;
[Link] report -> mark
Accessing union
[Link] report -> name
members
[Link] report -> average

Example program for C union:

#include <stdio.h>
#include <string.h>
Union student
{
char name[20];
char subject[20];
float percentage;
};
int main()
{
union student record1;
union student record2;

// assigning values to record1 union variable

strcpy([Link], "Raju");
strcpy([Link], "Maths");
[Link] = 86.50;

printf(“Union record1 values example\n”);

printf(" Name : %s \n", [Link]);

ISE, DSCE 7
 printf(" Subject : %s \n", [Link]);
printf(" Percentage : %f \n\n", [Link]);

// assigning values to record2 union variable

printf("Union record2 values example\n");
strcpy([Link], "Mani");
printf(" Name : %s \n", [Link]);

strcpy([Link], "Physics");
printf(" Subject : %s \n", [Link]);

[Link] = 99.50;
printf(" Percentage : %f \n", [Link]);
return 0;
}
Output:
Union record1 values example
Name :
Subject :
Percentage : 86.500000;
Union record2 values example
Name : Mani
Subject : Physics
Percentage : 99.500000

Explanation for above C union program:

There are 2 union variables declared in this program to understand the difference
in accessing values of union members.

Record1 union variable:

• “Raju” is assigned to union member “[Link]” . The memory location

name is “[Link]” and the value stored in this location is “Raju”.
• Then, “Maths” is assigned to union member “[Link]”. Now, memory
location name is changed to “[Link]” with the value “Maths” (Union
can hold only one member at a time).
• Then, “86.50” is assigned to union member “[Link]”. Now,
memory location name is changed to “[Link]” with value
“86.50”.
• Like this, name and value of union member is replaced every time on the
common storage space.
• So, we can always access only one union member for which value is
assigned at last. We can‟t access other member values.
• So, only “[Link]” value is displayed in output. “[Link]”
and “[Link]” are empty.

ISE, DSCE 8
Record2 union variable:

• If we want to access all member values using union, we have to access the
member before assigning values to other members as shown in record2
union variable in this program.
• Each union members are accessed in record2 example immediately after
assigning values to them.
• If we don‟t access them before assigning values to other member, member
name and value will be over written by other member as all members are
using same memory.
• We can‟t access all members in union at same time but structure can do
that.

Example program – Another way of declaring C union:

In this program, union variable “record” is declared while declaring union itself as shown in
the below program.

#include <stdio.h>
#include <string.h>
union student
{
char name[20]; char subject[20]; float percentage;
}record;
int main()
{
strcpy([Link], "Raju");
strcpy([Link], "Maths");
[Link] = 86.50;
printf(" Name : %s \n", [Link]);
printf(" Subject : %s \n", [Link]);
printf(" Percentage : %f \n", [Link]);
return 0;
}

Output:

Name :
Subject :
Percentage : 86.500000

We can access only one member of union at a time. We can‟t access all member
values at the same time in union. But, structure can access all member values at
the same time. This is because, Union allocates one common storage space for all

ISE, DSCE 9
its members. Where as Structure allocates storage space for all its members
separately.

Difference between structure and union in C:

[Link] C Structure C Union

1 Structure allocates storage space for Union allocates one common
all its members separately. storage space for all its
members. Union finds that which
of its member needs high
storage space over other
members and allocates that
much space
2 Structure occupies larger memory Union occupies lower memory
space. space over structure.
3 We can access all members of We can access only one
structure at a time. member of union at a time.
4 Structure example: Union example:
struct student union student
{ {
int mark; int mark;
double average; double average;
}; };
5 For above structure, memory allocation For above union, only 8 bytes of
will be like below. memory will be allocated since
int mark – 2B double data type will occupy
double average – 8B maximum space of memory over
Total memory allocation = 2+8 = 10 Bytes other data types.
Total memory allocation = 8 Bytes

Self-Referential Structures

• A structure can have members which point to a structure variable of the same
type.
• These types of structures are called self-referential structures and are widely
used in dynamic data structures like trees, linked list, etc.
• The following is a definition of a self-referential structure.

struct node
{
int data;
struct node *next;
};

ISE, DSCE 10
 Here, next is a pointer to a struct node variable.

• It should be remembered that a pointer to a structure is similar to a pointer to

any other variable.
• A self-referential data structure is essentially a structure definition which
includes at least one member that is a pointer to the structure of its own kind.
• Such self-referential structures are very useful in applications that involve linked
data structures, such as lists and trees.
• Unlike a static data structure such as array where the number of elements that
can be inserted in the array is limited by the size of the array, a self-referential
structure can dynamically be expanded or contracted.
• Operations like insertion or deletion of nodes in a self-referential structure
involve simple and straight forward alteration of pointers.

Pointer to Structure

• The beginning address of a structure can be accessed in the same manner as

any other address, through the use of the address (&) operator.
• Thus, if variable represents a structure type variable, then & variable represents
the starting address of that variable. A pointer to a structure can be defined as
follows:
struct student *ptr;
• ptr represents the name of the pointer variable of type student. We can then
assign the beginning address of a structure variable to this pointer by writing
ptr= &variable; //pointer initialisation Let us take the following example:
typedef struct
{
char name [ 40];
int roll_no;
float marks;
}student; student s1,*ps;
• In this example, s1 is a structure variable of type student, and ps is a pointer
variable whose object is a structure variable of type student. Thus, the beginning
address of s1 can be assigned to ps by writing.
ps = &s1;
• An individual structure member can be accessed in terms of its corresponding
pointer variable by using the -> operator (arrow operator)
ptr →member

ISE, DSCE 11
• Where ptr refers to a structure- type pointer variable and the operator → is
comparable to the period (.) operator. The associativity of this operator is also
left-to-right.
• The operator → can be combined with the period operator (.) to access a
submember within a structure. Hence, a submember can be accessed by writing
ptr → [Link]

// C Program to demonstrate Structure pointer

#include <stdio.h>
#include <string.h>

struct Student
{
int roll_no;
char name[30];
char branch[40];
int batch;
};

int main()
{

struct Student s1;

struct Student* ptr = &s1;

s1.roll_no = 27;
strcpy([Link], "Kamlesh Joshi");
strcpy([Link], "Computer Science And Engineering");
[Link] = 2019;

printf("Roll Number: %d\n", (*ptr).roll_no);

printf("Name: %s\n", (*ptr).name);
printf("Branch: %s\n", (*ptr).branch);
printf("Batch: %d", (*ptr).batch);

return 0;
}
Out Put
Roll Number: 27
Name: Kamlesh Joshi
Branch: Computer Science And Engineering
Batch: 2019

ISE, DSCE 12
// C Program to demonstrate Structure pointer
#include <stdio.h>
#include <string.h>

// Creating Structure Student

struct Student
{
int roll_no;
char name[30];
char branch[40];
int batch;
};

// variable of structure with pointer defined

struct Student s, *ptr;

int main()
{

ptr = &s;
// Taking inputs
printf("Enter the Roll Number of Student\n");
scanf("%d", &ptr->roll_no);
printf("Enter Name of Student\n");
scanf("%s", &ptr->name);
printf("Enter Branch of Student\n");
scanf("%s", &ptr->branch);
printf("Enter batch of Student\n");
scanf("%d", &ptr->batch);

// Displaying details of the student

printf("\nStudent details are: \n");

printf("Roll No: %d\n", ptr->roll_no);

printf("Name: %s\n", ptr->name);
printf("Branch: %s\n", ptr->branch);
printf("Batch: %d\n", ptr->batch);

return 0;
}

ISE, DSCE 13
Pointer to Function

There are three methods in which we pass a structure to a function as an argument.

1. We can pass each member of a structure. It is not efficient, so we do not use it.
2. We can pass a copy of entire structure to a called function (Call by value)
3. We can pass the entire structure by passing its address (call by reference)

Call by value:

#include<stdio.h>
struct employee
{
char name[20];
char city[20];
int pin;
};
void display(struct employee e);
void main ( )
{
struct employee e;
printf("Enter employee information name,city,pin\n");
scanf("%s %s %d ",[Link],[Link],&[Link]);
display(e);
}
void display(struct employee e)
{
printf("Printing the details....\n");
printf("%s %s %d",[Link],[Link],[Link]);
}
OUT PUT
Enter employee information name,city,pin
Praveen bangalore 560016
Printing the details….
Praveen bangalore 560016

Call by Reference

In the function call, the address of the structure variable is used. The argument in
the function header and declaration is to be declared as a pointer to a structure
variable.

Note :

-> is the member selection operator. (minus sign followed by greater than symbol)

ISE, DSCE 14
Call by reference :

#include<stdio.h>
struct employee
{
char name[20];
char city[20];
int pin;
};
void display(struct employee *e);
void main ( )
{
struct employee e;
printf("Enter employee information name,city,pinn");
scanf("%s %s %d ",[Link],[Link],&[Link]);
display(&e);
}
void display(struct employee *e)
{
printf("Printing the details....\n");
printf("%s %s %d",e->name,e->city,e->pin);
}

Introduction to Data Structure and its classification

Data structure is a representation of logical relationship existing between individual

elements of data. In other words, a data structure defines a way of organizing all
data items that considers not only the elements stored but also their relationship
to each other. The term data structure is used to describe the way data is stored.

To develop a program of an algorithm we should select an appropriate data

structure for that algorithm. Therefore, data structure is represented as: Algorithm
+ Data structure = Program

A data structure is said to be linear if its elements form a sequence or a linear list.
The linear data structures like an array, stacks, queues and linked lists organize
data in linear order. A data structure is said to be non linear if its elements form a
hierarchical classification where, data items appear at various levels.

Trees and Graphs are widely used non-linear data structures. Tree and graph
structures represent hierarchical relationship between individual data elements.
Graphs are nothing but trees with certain restrictions removed.

ISE, DSCE 15
Data structures are divided into two types:
1. Primitive data structures.
2. Non-primitive data structures.

Primitive Data Structures are the basic data structures that directly operate upon
the machine instructions. They have different representations on different
computers. Integers, floating point numbers, character constants, string constants
and pointers come under this category.

Non-primitive data structures are more complicated data structures and are
derived from primitive data structures. They emphasize on grouping same or
different data items with relationship between each data item. Arrays, lists and files
come under this category. Figure shows the classification of data structures.

Data Structures Operations:

1. Traversing
2. Searching
3. Inserting
4. Deleting
5. Sorting
6. Merging

1. Traversing- It is used to access each data item exactly once so that it can be
processed.
2. Searching- It is used to find out the location of the data item if it exists in the
given collection of data items.
3. Inserting- It is used to add a new data item in the given collection of data items.
4. Deleting- It is used to delete an existing data item from the given collection of
data items.
5. Sorting- It is used to arrange the data items in some order i.e. in ascending or
descending order in case of numerical data and in dictionary order in case of
alphanumeric data.

ISE, DSCE 16
6. Merging- It is used to combine the data items of two sorted files into single file
in the sorted form.

the need for Data Structure

• As applications are becoming more complex and the amount of data is

increasing day by day, which may cause problems with processing speed,
searching data, handling multiple requests etc.
• Data structure provides a way of organizing, managing, and storing data
efficiently. With the help of data structure, the data items can be traversed
easily.
• Data structure provides efficiency, reusability and abstraction. It plays an
important role in enhancing the performance of a program because the main
function of the program is to store and retrieve the user’s data as fast as
possible.

Dynamic Memory Allocation

When a variable is defined the compiler (linker/loader actually) allocates a real

memory address for the variable.
– int x; will allocate 4 bytes in the main memory, which will be used to
store an integer value.
When a value is assigned to a variable, the value is actually placed to the memory
that was allocated.
– x=3; will store integer 3 in the 4 bytes of memory.
The process of allocating memory during program execution is called dynamic
memory allocation.
C language offers 4 dynamic memory allocation functions. They are,
1. malloc() : malloc (number * sizeof(int));
2. calloc() : calloc (number, sizeof(int));
3. realloc() : realloc (pointer_name, number * sizeof(int));
4. free() : free (pointer_name);
1. MALLOC():
• is used to allocate space in memory during the execution of the program.
• Does not initialize the memory allocated during execution. It carries
garbage value.

ISE, DSCE 17
 • returns null pointer if it couldn‟t able to allocate requested amount of
memory.
• The expression results in a NULL pointer if the memory cannot be allocated.

Example
ptr = (float*) malloc(100 * sizeof(float));

The above statement allocates 400 bytes of memory. It's because the size of float
is 4 bytes. And, the pointer ptr holds the address of the first byte in the allocated
memory.

2. CALLOC():
• calloc () function is also like malloc () function. But calloc () initializes the
allocated memory to zero. But, malloc() doesn‟t.
• The name "calloc" stands for contiguous allocation.

Example:
ptr = (float*) calloc(25, sizeof(float));

The above statement allocates contiguous space in memory for 25 elements of

type float.

3. REALLOC():
• Realloc () function modifies the allocated memory size by malloc () and
calloc () functions to new size.
• If enough space doesn‟t exist in memory of current block to extend, new
block is allocated for the full size of reallocation, then copies the existing
data to new block and then frees the old block.

Example:
ptr = realloc(ptr, x);
Here, ptr is reallocated with a new size x.

4. FREE():
• free () function frees the allocated memory by malloc (), calloc (), realloc
() functions and returns the memory to the system.
• You must explicitly use free() to release the space.

ISE, DSCE 18
Example:
free(ptr);

Example 1: malloc() and free()

// Program to calculate the sum of n numbers entered by the user

#include <stdio.h>
#include <stdlib.h>
int main()
{
int n, i, *ptr, sum = 0;
printf("Enter number of elements: ");
scanf("%d", &n);
ptr = (int*) malloc(n * sizeof(int));
// if memory cannot be allocated
if(ptr == NULL)
{
printf(“Error! Memory not allocated.”);
exit(0);
}
printf(“Enter elements: “);
for(I = 0; I < n; ++i)
{
scanf("%d", ptr + i);
sum += *(ptr + i);
}
printf("Sum = %d", sum);
// deallocating the memory
free(ptr);
return 0;
}

Output
Enter number of elements: 3
Enter elements: 100
20
36
Sum = 156

Example 2: calloc() and free()

// Program to calculate the sum of n numbers entered by the user

ISE, DSCE 19
#include <stdio.h>
#include <stdlib.h>
int main()
{
int n, i, *ptr, sum = 0;
printf("Enter number of elements: ");
scanf("%d", &n);
ptr = (int*) calloc(n, sizeof(int));
if(ptr == NULL)
{
printf("Error! memory not allocated.");
exit(0);
}
printf("Enter elements: ");
for(i = 0; i < n; ++i)
{
scanf("%d", ptr + i);
sum += *(ptr + i);
}
printf("Sum = %d", sum);
free(ptr);
return 0;
}

Output

Enter number of elements: 3

Enter elements: 100
20
36
Sum = 156

Example 3: realloc()
#include <stdio.h>
#include <stdlib.h>

int main()

ISE, DSCE 20
{
int *ptr, i , n1, n2;
printf("Enter size: ");
scanf("%d", &n1);
ptr = (int*) malloc(n1 * sizeof(int));
printf("Addresses of previously allocated memory:\n");
for(i = 0; i < n1; ++i)
printf("%pc\n",ptr + i);
printf("\nEnter the new size: ");
scanf("%d", &n2);
// rellocating the memory
ptr = realloc(ptr, n2 * sizeof(int));
printf("Addresses of newly allocated memory:\n");
for(i = 0; i < n2; ++i)
printf("%pc\n", ptr + i);
free(ptr);
return 0;
}
Output
Enter size: 2
Addresses of previously allocated memory:
26855472
26855476

Enter the new size: 4

Addresses of newly allocated memory:
26855472
26855476
26855480
26855484

DIFFERENCE BETWEEN STATIC MEMORY ALLOCATION AND DYNAMIC MEMORY

ALLOCATION IN C:

Static memory allocation Dynamic memory allocation

In static memory allocation, memory is In dynamic memory allocation,
allocated while writing the C program. memory is allocated while
Actually, user requested memory will be executing the program. That
allocated at compile time. means at run time.

ISE, DSCE 21
 Memory size can‟t be modified while Memory size can be modified while
execution. execution.
Example: array Example: Linked list

DIFFERENCE BETWEEN MALLOC() AND CALLOC() FUNCTIONS IN C:

malloc() calloc()
It allocates only single block of requested It allocates multiple blocks of requested
memory memory
int *ptr; int *ptr;
ptr = malloc( 20 * sizeof(int) ); Ptr = calloc( 20, 20 * sizeof(int) );
For the above, 20*4 bytes of memory For the above, 20 blocks of memory will
only allocated in one block. Total = 80 be created and each contains 20*4
bytes bytes of memory. Total = 1600 bytes
malloc () doesn‟t initializes the allocated calloc () initializes the allocated memory
memory. It contains garbage values to zero
type cast must be done since this Same as malloc () function int *ptr;
function returns void pointer int *ptr; ptr = (int*)calloc( 20, 20 * sizeof(int) );
ptr = (int*)malloc(sizeof(int)*20 );

Recursive Algorithms

The process in which a function calls itself directly or indirectly is called recursion
and the corresponding function is called a recursive function. Using a recursive
algorithm, certain problems can be solved quite easily.

Need of Recursion

Recursion is an amazing technique with the help of which we can reduce the length
of our code and make it easier to read and write. It has certain advantages over
the iteration technique which will be discussed later. A task that can be defined with
its similar subtask, recursion is one of the best solutions for it. For example; The
Factorial of a number.

Properties of Recursion:

• Performing the same operations multiple times with different inputs.

• In every step, we try smaller inputs to make the problem smaller.
• Base condition is needed to stop the recursion otherwise infinite loop will
occur.

ISE, DSCE 22
Example:

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

void main( )
{
clrscr( )
int factorial(int);
int n,f;
printf("Enter the number: ");
scanf("%d",&n);
f=factorial(n);
printf("Factorial of the number is %d",f);
getch();
}
int factorial(int n)
{
int f;
if(n==1)
return 1;
else
f=n*factorial(n-1);
return f;
}

Sparse Matrices.

A sparse matrix is a matrix in which most of the elements are zero. By contrast, if
most of the elements are nonzero, then the matrix is considered dense. When
storing and manipulating sparse matrices on a computer, it is beneficial and often
necessary to use specialized algorithms and data structures that take advantage
of the sparse structure of the matrix. Operations using standard dense- matrix
structures and algorithms are slow and inefficient when applied to large sparse
matrices as processing and memory are wasted on the zeroes. Sparse data is by
nature more easily compressed and thus require significantly less storage. Some
very large sparse matrices are infeasible to manipulate using standard dense-
matrix algorithms.

ISE, DSCE 23
Storing a sparse matrix

A matrix is typically stored as a two-dimensional array. Each entry in the array

represents an element ai,j of the matrix and is accessed by the two indices i and j.
Conventionally, i is the row index, numbered from top to bottom, and j is the column
index, numbered from left to right. For an m × n matrix, the amount of memory
required to store the matrix in this format is proportional to m × n

In the case of a sparse Sparse Matrix Representations

A sparse matrix can be represented by using TWO representations...

1. Triplet Representation
2. Linked Representation

matrix, substantial memory requirement reductions can be realized by storing

only the non-zero entries.

1. Triplet Representation

In this representation, we consider only non-zero values along with their row and
column index values. Each non zero value is a triplet of the form (R,C,Value) where
R represents the row in which the value appears, C represents the column in which
the value appears and Value represents the non- zero value itself. In this
representation, the 0th row stores total rows, total columns and total non-zero
values in the matrix.
For example, consider a matrix of size 5 X 6 containing 6 number of non-zero values.
This matrix can be represented as shown in the image...

In above example matrix, there are only 6 non-zero elements ( those are 9, 8, 4, 2, 5
& 2) and matrix size is 5 X 6. We represent this matrix as shown in the above image.
Here the first row in the right side table is filled with values 5, 6 & 6 which indicates
that it is a sparse matrix with 5 rows, 6 columns & 6 non-zero values. The second
row is filled with 0, 4, & 9 which indicates the non-zero value 9 is at the 0th-row 4th
column in the Sparse matrix. In the same way, the remaining non-zero values also

ISE, DSCE 24
follow a similar pattern.

Example Program

#include<stdio.h>
int main()
{
int S[10][10],m,n,i,k=0,size=0;
printf("Enter number of rows in the matrix : ");
scanf("%d",&m);
printf("Enter number of columns in the matrix : ");
scanf("%d",&n);
printf("Enter elements in the matrix : ");
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
scanf("%d",&S[i][j]);
printf("The matrix is \n");
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
printf(" %d ",S[i][j]);
if (S[i][j] != 0)
size++;
}
printf("\n");
}
int M[3][size];

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

for (int j = 0; j < n; j++)
if (S[i][j] != 0)
{
M[0][k] = i;
M[1][k] = j;
M[2][k] = S[i][j];
k++;
}

printf("Triplet representation of the matrix is \n");

for (int i=0; i<3; i++)
{

ISE, DSCE 25
 for (int j=0; j<size; j++)
printf(" %d ", M[i][j]);
printf("\n");
}
return 0;
}

ISE, DSCE 26