Data Structures and Applications [21CS32]

MODULE-1
INTRODUCTION
TOPICS:
Introduction: Data Structures, Classifications (Primitive and Non-Primitive), Data Structures
Operations, Review of Arrays, Structures, Self-Referential Structures and Unions. Pointers and
Dynamic Memory Allocation Functions. Representation of Linear Arrays in Memory, Dynamically
Allocated Arrays.
Array Operations: Traversing, Inserting, Deleting, Searching and Sorting. Multidimensional
Arrays, Polynomials and Sparse Matrices.

1. INTRODUCTION

Basic Terminology of Data Organization:

 Data: The term ‘DATA’ simply refers to a value or a set of values. These values may present
anything about something, like it may be roll no of a student, marks, name of an employee,
address of person etc.
 Data item: A data item refers to a single unit of value.
 For Eg. roll no of a student, marks, name of an employee, address of person etc. are
data items.
 Data items that can be divided into sub items are called Group items (Eg. Address,
date, name).
 Data items which cannot be divided in to sub items are called Elementary items (Eg.
Roll no, marks, city, pin code etc.).
 Entity: With similar attributes (Eg. all employees of an organization) form an entity set.
 Information: Data with given attribute or processed data.
 Field: Single elementary unit of information representing an attribute of an entity.
 Record: It is the collection of field values of a given entity.
 File: It is the collection of records of the entities in a given entity set.
 Each record in a file may contain many field items but the value in a certain field may uniquely
determine the record in the file. Such a field K is called a Primary key and the values K1, K2,
K3… in such a field are called keys or key values.

Dr. SL, VGK,SNK Dept of ISE, RNSIT Page 1

 Data Structures and Applications [21CS32]

 Records can be classified as fixed-length records or variable-length records. In fixed length

records, all the records contain the same data items with the same amount of space assigned to
each data item. In variable length records, file records may contain different lengths.
EXAMPLE:
Attributes: Name Age Sex Roll Number Branch
A 17 M 109CS0132 CSE
Values:
B 18 M 109EE1234 EEE

Here, it is an example of student details where STUDENT is the given entity. Then name,
age, sex, roll number, branch are attributes and their values are properties (A, 17, M, 109cs0132,
CSE). Collection of student details is student entity set and Roll number is the primary key which
uniquely indicates each student details.

DATA STRUCTURE
 “Data Structure is a way of collecting and organizing data in such a way that the operations
on these data can be performed in an effective way”.
 “Data structure can be defined as logical or mathematical model of a particular organization
of data.”
 “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.
 Data Structures is about rendering data elements in terms of some relationship, for better
organization and storage in computer.
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
For example, data can be player's name "Virat" and age 26. Here "Virat" is of String data type
and 26 is of integer data type. This data can be recorded as a Player record. Now, it is possible to
collect and store player’s records in a file or database as a data structure. For example: "Dhoni" 30,
"Gambhir" 31, "Sehwag" 33.
In simple language, “Data Structures are structures programmed to store ordered data, so that
various operations can be performed on it easily. It’s an arrangement of data in a computer’s memory.
Algorithms manipulate the data in these structures in order to accomplish some task”.

Dr. SL, VGK,SNK Dept of ISE, RNSIT Page 2

 Data Structures and Applications [21CS32]

CLASSIFICATION OF DATA STRUCTURES

The logical or mathematical model of a particular organization of data is called a Data
Structure.
Data Structures can be classified as
 Primitive data structure
 Non-Primitive data structure
 Linear data structure
 Nonlinear data structure
Anything that can store data can be called as a data structure, hence Integer, Float,
Boolean, Char etc, all are data structures. They are known as Primitive Data Structures and some
complex Data Structures, which are used to store large and connected data. They are called Non-
primitive Data Structures.
Examples:
 Array
 Stack
 Queue
 Linked List
 Tree
 Graph
All these data structures allow us to perform different operations on data. The selection of
these data structures is based on which type of operation is required.

Figure 1: Classification of Data Structures

Figure 1 gives the complete classification of the data structure.

Dr. SL, VGK,SNK Dept of ISE, RNSIT Page 3

 Data Structures and Applications [21CS32]

Definitions:
 Primitive Data Structure: “A primitive data structure used to represent the standard data
types of any one of the computer languages”. Variables, pointers, etc. are examples of primitive
data structures. Simple data structure can be constructed with the help of primitive data structure.
 Non-Primitive Data structure: “Non-Primitive data structure can be constructed with the
help of any one of the primitive data structures and it is having a specific functionality. It can be
designed by user”. Arrays, Structure, Union, linked list, Stacks, Queue, trees, graphs etc are
example for non-primitive data structures.

Non-primitive data structures can be further classified as

1) Linear data structure
2) Non-linear data structure
Linear Data Structures: Linear data structures can be constructed as a continuous
arrangement of data elements in the memory. In linear data structure the elements are stored in
sequential order. In the linear Data Structures the relationship of adjacency is maintained between the
Data elements. It can be represented by using array data type or linked list.”
The linear data structures are:
 Array: Array is a collection of data of same data type stored in consecutive memory location
and is referred by common name
 Stack: A stack is a Last-In-First-Out (LIFO) linear data structure in which insertion and deletion
takes place at only one end called the top of the stack.
 Queue: A Queue is a First in First-Out (FIFO) linear data structure in which insertions takes
place one end called the rear and the deletions takes place at one end called the Front.
 Linked list: Linked list is a collection of data of same data type but the data items need not be
stored in consecutive memory locations.

Non-Linear Data Structures: “Non-linear data structure can be constructed as a collection of

randomly distributed set of data item joined together by using a special pointer (tag). In non-linear
Data structure the relationship of adjacency is not maintained between the Data items. Elements are
stored based on the hierarchical relationship among the data.”

The following are some of the Non-Linear data structure

Dr. SL, VGK,SNK Dept of ISE, RNSIT Page 4

 Data Structures and Applications [21CS32]

 Trees: Trees are used to represent data that has some hierarchical relationship among the data
elements. (as shown in figure 2)

Figure 2: Trees
 Graph: Graph is used to represent data that has relationship between pair of elements not
necessarily hierarchical in nature. For example electrical and communication networks, airline
routes, flow chart, graphs for planning projects.(as shown in figure 3)

Figure 3: Graph

DATA STRUCTURE OPERATIONS

The data in the data structures are processed by certain operations. The particular data structure
chosen largely depends on the frequency of the operation that needs to be performed on the data
structure.
• Traversing
• Searching
• Insertion
• Deletion
• Sorting
• Merging

(1) Traversing: Accessing each record exactly once so that certain items in the record may be
processed.
(2) Searching: Finding the location of a particular record with a given key value, or finding the

Dr. SL, VGK,SNK Dept of ISE, RNSIT Page 5

 Data Structures and Applications [21CS32]

location of all records which satisfy one or more conditions.

(3) Inserting: Adding a new record to the structure.
(4) Deleting: Removing the record from the structure.
(5) Sorting: Managing the data or record in some logical order (Ascending or descending order).
(6) Merging: Combining the record in two different sorted files into a single sorted file.
Operations on linear data structures
1. Add an element
2. Delete an element
3. Traverse all the elements
4. Sort the list of elements
5. Search for a data element
Apply one or more functionality to create different types of data structures.
For ex: Stack, Queue, and Linked Lists.
Operations applied on non-linear data structures
The following list of operations applied on non-linear data structures.
1. Add elements.
2. Delete elements
3. Display the elements
4. Sort the list of elements
5. Search for A data element by applying one or more functionalities and different ways of joining
randomly distributed data items to create different types of data structures.
For ex: Tree, Graphs and Files.

REVIEW OF ARRAYS, STRUCTURES, SELF-REFERENTIAL STRUCTURES AND

UNIONS.
Arrays
Array is a container which can hold fix number of items and these items should be of same
type. Most of the data structures make use of array to implement their algorithms. Following are
important terms to understand the concepts of Array.
An array is a data structure that is a collection of variables of one type that are accessed
through a common name. Each element of an array is given a number by which we can access that
element which is called an index. To refer to a particular location or element in the array we specify
the name to the array and position number of particular element in the array.

Dr. SL, VGK,SNK Dept of ISE, RNSIT Page 6

 Data Structures and Applications [21CS32]

Element − each item stored in an array is called an element.

Index − each location of an element in an array has a numerical index which is used to
identify the element.
Array Representation
Arrays can be declared in various ways in different languages. For illustration, let's take
C array declaration

Figure 4a: Array with 10 elements

Figure 4b: Array index

As per above shown illustration, following are the important points to be considered. (As shown in
figure 4a and figure 4b)
 Index starts with 0.

 Array length is 10 which mean it can store 10 elements.

 Each element can be accessed via its index. For example, we can fetch element at index 6 as
27.
ADT ARRAY
Objects: A set of pairs<index, value > where for each of index there is a value from the set item. Index
is a finite ordered set of one or more dimensions, for example {0,…,n-1} for one dimension,{(0,0
),(0,1),(0.2),(1,0),(1,2),(1,1),(2,1),(2,2),(2,0))} for two dimensions etc.
Functions:
For all A ∈ Array, I ∈ index, x ∈ item, j, size ∈ integer

Dr. SL, VGK,SNK Dept of ISE, RNSIT Page 7

 Data Structures and Applications [21CS32]

1. Array create (j, list) = return an array of j dimensions where list is a j-tuple whose ith element is the
size of ith dimension. Items are undefined.
2. Item retrieve (A, i) = if (I ∈ index) return the item associated with index value i in array A else return
error.
3. Array store (A, i, x) = if (i in index) return an array that is identical to array A expect the new pair
<i,x> has been inserted else return error.
end Array

One Dimensional Array

Declaration:
Before using the array in the program, it must be declared
Syntax: data_type array_name[size];
Where,
data_type represents the type of elements present in the array.
array_name represents the name of the array.
Size represents the number of elements that can be stored in the array.
Example: int age[100]; float sal[15]; char grade[[20];
Here age is an integer type array, which can store 100 elements of integer type. The array sal is
floating type array of size 15, can hold float values. Grade is a character type array which holds 20
characters.

Initialization:
Initialize arrays at the time of declaration.
Syntax: data_type array_name[size] = {value1, value2,…..... valueN};
Where, value1, value2, valueN are the constant values known as initializers, which are assigned
to the array elements one after another.
Example: int marks[5]={10,2,0,23,4};
The values of the array elements after this initialization are:
marks[0]=10, marks[1]=2, marks[2]=0, marks[3]=23, marks[4]=4;

NOTE:
1. Address of an data element in the array can be calculated as:
A[K]=BA(A)+W(K-LOWERBOUND);

Dr. SL, VGK,SNK Dept of ISE, RNSIT Page 8

 Data Structures and Applications [21CS32]

Where, A is an array, K is the index of the element for which address has to be calculated , BA is
the base address of the array A and W is the size of one element in memory
2. Calculating the length of an array
Length = Upperbound-Lowerbound+1
Where , upperbound is index of the last element and lowerbound is index of the first element in
the array.
Processing: For processing arrays we mostly use for loop. The total no. of passes is equal to the no. of
elements present in the array and in each pass one element is processed.
Example: This program reads and displays 3 elements of integer type.
#include<stdio.h>
main()
{
int a[3], i;
for(i=0; i<=2; i++) //Reading the array values
{
printf(“enter the elements”);
scanf(“%d”, &a[i]);
}
for(i=0; i<=2; i++) //display the array values
{
printf(“%d”, a[i]);
printf(“\n”);
}
}
Example: C Program to Increment every Element of the Array by one & Print Incremented
Array.
#include <stdio.h>
void main()
{
int i;
int array[4] = {10, 20, 30, 40};
for (i = 0; i < 4; i++)
arr[i]++;

Dr. SL, VGK,SNK Dept of ISE, RNSIT Page 9

 Data Structures and Applications [21CS32]

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

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

OPERATIONS ON ARRAYS

Following are the basic operations supported by an array.

 Traversal – processing each element in the list.
 Insertion − adding a new element at given index to the list.
 Deletion – removing an element at given index from the list.
 Search − finding the location of the element with a given value or the record with a given
key.
 Sorting: arranging the elements in some type of order.
 Merging: Combing two lists into a single list.

Traversing Linear Arrays

Let A be the array in the memory of the computer. If the operation required is to print the
contents of each element of A OR Count the number of elements of A. Then this is accomplished by
traversing A, i.e, by accessing and processing each element of A exactly once.

INSERT(LA, N, K, ITEM)
HERE LA is a linear array with N elements and K is a positive integer such that K<=N. this
algorithm inserts an element ITEM into Kth position in LA.
1. [Initalize the counter]. Set J=N.
2. repeat steps 3 and 4 while J>=K
3. [move jth element downward] set LA[J+1]=LA[J].
4. [Decrease the counter] set J=J-1
[end of step 2 loop]
5. [insert element] set LA[K]A=ITEM
6. [reset N] set N=N+1
7. Exit

DELETE(LA, N, K, ITEM)
HERE LA is a linear array with N elements and K is a positive integer such that K<=N. this
algorithm deletes an element ITEM into Kth position in LA.

Dr. SL, VGK,SNK Dept of ISE, RNSIT Page 10

 Data Structures and Applications [21CS32]

1. Set ITEM=LA[K]
2. repeat for J=K to N-1
3.[move j+1st element upward] set LA[J]=LA[J+1].
4.[end of step 2 loop]
5.[reset N] set N=N-1
6.Exit

BUBBLE SORT(DATA, N)
Here DATA is an array with N elements . THIS Algorithm sorts the elemts in DATA.
1. repeat steps 2 and 3 for k=1 to N-1
2. [Initalize the pass pointer PTR]. Set PTR=1.
3. Repeat while PTR<=N-K : [Executes pass]
(a) if DATA[PTR]>DATA[PTR+1] then
Interchange DATA[PTR] and DATA[PTR+1] [end of IF structure]
(b) set PTR=PTR+1
[End of inner loop]
[end of step1 outer loop]
4. Exit

LINEAR SEARCH (DATA, N, ITEM, LOC)

Here DATA is a linear array with N elements and ITEM is a given element to be searched. In linear
search, DATA array is traversed sequentially to locate ITEM. The given algorithm finds the location
LOC of item in DATA or set LOC=0, if the search is unsuccessful.
1. Initialize set K=0 and LOC=0
2. Repeat steps 3 & 4 while(LOC=0 and K<=N-1)
3. If ITEM == DATA[K], then LOC=K
4. Set K=K+1[Increment Counter]
5. [End of step 2 loop]
6. [Successful?]
If LOC=0, then
write: ITEM is not in the array DATA
else
write: LOC+1 is the position of ITEM
7. Exit

Dr. SL, VGK,SNK Dept of ISE, RNSIT Page 11

 Data Structures and Applications [21CS32]

BINARY SEARCH (DATA, LB, UB, ITEM, LOC)

Here DATA is a sorted array with lower bound LB and upper bound UB and ITEM is a given
item of information. The variables BEG, END and MID denote respectively the beginning, end and
middle locations of a segment of elements of data. This algorithm finds the location LOC of item in
DATA or sets LOC=NULL
1. [Initialize segment variables]
Set BEG=LB, END=UB and MID=INT((BEG+END)/2);
2. repeat steps 3 and 4 while BEG<=END and DATA[MID]!=ITEM
3. if ITEM<DATA[MID] then
Set END=MID-1
ELSE
Set BEG=MID+1
[end of loop]
4. set MID=INT(BEG+END)/2
5. if DATA[MID]=ITEM Then
set LOC=MID
else
set LOC=NULL
1. Exit

TWO DIMENSIONAL ARRAYS

Arrays that we have considered up to now are one dimensional array, a single line of elements.
Often data come naturally in the form of a table, e.g. spreadsheet, which need a two-dimensional array.
Declaration: The syntax is same as for 1-D array but here 2 subscripts are used.
Syntax: data_type array_name[rowsize][columnsize];
Where, Rowsize specifies the no. of rows Columnsize specifies the no. of columns.
Example: int a[4][5]; This is a 2-D array of 4 rows and 5 columns. Here the first element of the array is
a[0][0] and last element of the array is a[3][4] and total no. of elements is 4*5=20.
Col 0 Col 1 Col 2 Col 3 Col 4
Row 0 a[0][0] a[0][1] a[0][2] a[0][3] a[0][4]
Row 1 a[1][0] a[1][1] a[1][2] a[1][3] a[1][4]
Row 2 a[2][1] a[2][2] a[2][2] a[2][3] a[2][4]
Row 3 a[3][0] a[3][1] a[3][2] 3a[3][3] a[3][4]

Dr. SL, VGK,SNK Dept of ISE, RNSIT Page 12

 Data Structures and Applications [21CS32]

Initialization:
2-D arrays can be initialized in a way similar to 1-D arrays.
Example: int m[4][3]={1,2,3,4,5,6,7,8,9,10,11,12};
Example: int m[][3]={ {1,10}, {2,20,200}, {3}, {4,40,400} };

2D ARRAY REPRESENTATION USING COLUMN MAJOR ORDER AND ROW MAJOR

ORDER

1. In case of Column Major Order:

The formula is:

LOC (A [J, K]) = Base (A) + w [M (K-1) + (J-1)]
Here
LOC (A [J, K]) : is the location of the element in the Jth row and Kth column.
Base (A) : is the base address of the array A.
w : is the number of bytes required to store single element of the array A.
M : is the total number of rows in the array.
J : is the row number of the element.
K : is the column number of the element.

E.g. A 3 x 4 integer array A is as below:

Address[int Address[int
Subscript Elements
2 bytes] 4 bytes]
(1,1) 10 1000 1000
(2,1) 20 1002 1004
(3,1) 50 1004 1008
(1,2) 60 1006 1012
(2,2) 90 1008 1018
(3,2) 40 1010 1020
(1,3) 43 1012 1024
(2,3) 80 1014 1028
(3,3) 75 1016 1032
(1,4) 55 1018 1036
(2,4) 65 1020 1040
(3,4) 79 1022 1044

Dr. SL, VGK,SNK Dept of ISE, RNSIT Page 13

 Data Structures and Applications [21CS32]

Suppose we have to find the location of A [3, 2]. The required values are:
Base (A) : 1000
w : 2 (because an integer takes 2 bytes in memory)
M : 3
J : 3
K : 2
Now put these values in the given formula as below:

LOC (A [3, 2]) = 1000 + 2 [3 (2-1) + (3-1)]

= 1000 + 2 [3 (1) + 2]

= 1000 + 2 [3 + 2]

= 1000 + 2 [5]

= 1000 + 10 = 1010

we have to find the location of A [3, 2]. The required values are:
Base (A) : 1000
w : 4 ( integer takes 4 bytes in memory)
M : 3
J : 3
K : 2

LOC (A [3, 2]) = 1000 + 4 [3 (2-1) + (3-1)]

= 1000 + 4 [3 (1) + 2]

= 1000 + 4 [3 + 2]

= 1000 + 4 [5]

= 1000 + 20 = 1020

Dr. SL, VGK,SNK Dept of ISE, RNSIT Page 14

 Data Structures and Applications [21CS32]

2. In case of Row Major Order:

The formula is:
LOC (A [J, K]) = Base (A) + w [N (J-1) + (K-1)]
Here
LOC (A [J, K]) : is the location of the element in the Jth row and Kth column.
Base (A) : is the base address of the array A.
w : is the number of bytes required to store single element of the array A.
N : is the total number of columns in the array.
J : is the row number of the element.
K : is the column number of the element.
E.g.
A 3 x 4 integer array A is as below:
Address[int Address[int
Subscript Elements
2 bytes] 4 bytes]
(1,1) 10 1000 1000
(1,2) 60 1002 1004
(1,3) 30 1004 1008
(1,4) 55 1006 1012
(2,1) 20 1008 1018
(2,2) 90 1010 1020
(2,3) 80 1012 1024
(2,4) 65 1014 1028
(3,1) 50 1016 1032
(3,2) 40 1018 1036
(3,3) 75 1020 1040
(3,4) 79 1022 1044

Suppose we have to find the location of A [3, 2]. The required values are:

Base (A) : 1000

w : 2 (because an integer takes 2 bytes in memory)
N : 4
J : 3

Dr. SL, VGK,SNK Dept of ISE, RNSIT Page 15

 Data Structures and Applications [21CS32]

K : 2
Now put these values in the given formula as below:
LOC (A [3, 2]) = 1000 + 2 [4 (3-1) + (2-1)]
= 1000 + 2 [4 (2) + 1]
= 1000 + 2 [8 + 1]
= 1000 + 2 [9]
= 1000 + 18
= 1018
Example 1:
Write a C program to find sum of two matrices
#include <stdio.h>
#include<conio.h>
void main()
{
float a[2][2], b[2][2], c[2][2];
int i,j;
clrscr();
printf("Enter the elements of 1st matrix\n");
/* Reading two dimensional Array with the help of two for loop. If there is an array of 'n'
dimension, 'n' numbers of loops are needed for inserting data to array.*/
for(i=0;i<2;I++)
for(j=0;j<2;j++)
{
scanf("%f",&a[i][j]);
}
printf("Enter the elements of 2nd matrix\n");
for(i=0;i<2;i++)
for(j=0;j<2;j++)
{
scanf("%f",&b[i][j]);
}
/* accessing corresponding elements of two arrays. */ for(i=0;i<2;i++)
for(j=0;j<2;j++)
{

Dr. SL, VGK,SNK Dept of ISE, RNSIT Page 16

 Data Structures and Applications [21CS32]

c[i][j]=a[i][j]+b[i][j]; /* Sum of corresponding elements of two arrays. */

}
/* To display matrix sum in order. */
printf("\nSum Of Matrix:");
for(i=0;i<2;i++)
{
for(j=0;j<2;j++)
printf("%f\t", c[i][j]);
printf("\n");
}
getch();
}
Example 2: Program for multiplication of two matrices
#include<stdio.h>
#include<conio.h>
int main()
{
int i,j,k;
int row1,col1,row2,col2,row3,col3;
int mat1[5][5], mat2[5][5], mat3[5][5];
clrscr();
printf(“\n enter the number of rows in the first matrix:”);
scanf(“%d”, &row1);
printf(“\n enter the number of columns in the first matrix:”);
scanf(“%d”, &col1);
printf(“\n enter the number of rows in the second matrix:”);
scanf(“%d”, &row2);
printf(“\n enter the number of columns in the second matrix:”);
scanf(“%d”, &col2);
if(col1 != row2)
{
printf(“\n The number of columns in the first matrix must be equal to the number of rows
in the second matrix ”);

Dr. SL, VGK,SNK Dept of ISE, RNSIT Page 17

 Data Structures and Applications [21CS32]

getch(); exit();
}
row3= row1; col3= col2;
printf(“\n Enter the elements of the first matrix”);
for(i=0;i<row1;i++)
{
for(j=0;j<col1;j++)
scanf(“%d”,&mat1[i][j]);
}
printf(“\n Enter the elements of the second matrix”);
for(i=0;i<row2;i++)
{
for(j=0;j<col2;j++)
scanf(“%d”,&mat2[i][j]);
}
for(i=0;i<row3;i++)
{
for(j=0;j<col3;j++)
{
mat3[i][j]=0;
for(k=0;k<col3;k++)
mat3[i][j] +=mat1[i][k]*mat2[k][j];
}
}
printf(“\n The elements of the product matrix are”):
for(i=0;i<row3;i++)
{
printf(“\n”);
for(j=0;j<col3;j++)
printf(“\t %d”, mat3[i][j]);
}
return 0;
}

Dr. SL, VGK,SNK Dept of ISE, RNSIT Page 18

 Data Structures and Applications [21CS32]

Output:
Enter the number of rows in the first matrix: 2
Enter the number of columns in the first matrix: 2
Enter the number of rows in the second matrix: 2
Enter the number of columns in the second matrix: 2
Enter the elements of the first matrix
1234
Enter the elements of the second matrix
5678
The elements of the product matrix are
19 22
43 50

Example 3: Program to find transpose of a matrix.

#include <stdio.h>
int main()
{
int a[10][10], trans[10][10], r, c, i, j;
printf("Enter rows and column of matrix: ");
scanf("%d %d", &r, &c);
printf("\nEnter elements of matrix:\n");
for(i=0; i<r; i++)
for(j=0; j<c; j++)
{
printf("Enter elements a%d%d: ",i+1,j+1);
scanf("%d", &a[i][j]);
}
/* Displaying the matrix a[][] */ printf("\n Entered Matrix: \n");
for(i=0; i<r; i++)
for(j=0; j<c; j++)
{
printf("%d ",a[i][j]);
if(j==c-1)

Dr. SL, VGK,SNK Dept of ISE, RNSIT Page 19

 Data Structures and Applications [21CS32]

printf("\n\n");
}
/* Finding transpose of matrix a[][] and storing it in array trans[][]. */
for(i=0; i<r;i++)
for(j=0; j<c; j++)
{
trans[j][i]=a[i][j];
}
/* Displaying the array trans[][]. */ printf("\nTranspose of Matrix:\n");
for(i=0; i<c;i++)
for(j=0; j<r;j++)
{
printf("%d ",trans[i][j]);
if(j==r-1)
printf("\n\n");
}
return 0;
}

STRUCTURE DEFINITION

“Structure is a collection of data items of same or dissimilar data type. Each data item is
identified by its name and type. (Or) A Structure is a user defined data type that can store related
information together. (Or) A structure is a collection of different data items / heterogeneous data items
under a single name.” The variable within a structure are of different data types and each has a name
that is used to select it from the structure.
C arrays allow you to define type of variables that can hold several data items of the same kind
but structure is another user defined data type available in C programming, which allows you to
combine data items of different kinds.
Structures are used to represent a record, Suppose, track of books are kept in a library are
recorded then it is required to track the following attributes about each book:
• Title

Dr. SL, VGK,SNK Dept of ISE, RNSIT Page 20

 Data Structures and Applications [21CS32]

• Author
• Subject
• Book ID

STRUCTURE DECLARATION
It is declared using a keyword struct followed by the name of the structure. The members of the
structure are declared within the structure.
Example:
struct struct-name
{
data_type1 member_name1;
data_type2 member_name2;
.. ..
data_typen member_namen;
}structurevariablename;

STRUCTURE INITIALIZATION
Assigning values to the data members of the structure is called initializing of structure.
Syntax:
struct struct_name
{
data _type member_name1;
data _type member_name2;
} structure variable={constant1,constant2};

Accessing the Members of a structure :-

A structure member variable is generally accessed using a ‘.’ dot operator.
Syntax: structurevariable.member_name;
The dot operator is used to select a particular member of the structure. To assign value to the individual
Data members of the structure variable stud, it is written as,
stud.roll=01;
stud.name=”Rahul”;
To input values for data members of the structure variable stud, can be written as,
scanf(“%d”,&stud.roll);

Dr. SL, VGK,SNK Dept of ISE, RNSIT Page 21

 Data Structures and Applications [21CS32]

scanf(‘’%s”,stud.name);
To print the values of structure variable stud, can be written as:
printf(“%d”,stud.roll);
printf(“%s”,stud.name);

Example for structure:

struct employee
{
char name[10];
int age;
float salary;
}person;

Here struct is a keyword.

This example creates a variable whose name is person and that has three fields
 A name that is a character array
 An integer value Age
 A float value salary
The . (Dot operator) is used as the structure member operator to select a particular member of the
structure.
Example: strcpy(person.name,”james”);
person.age=20;
person.salary=40000;

Program to create a struct person , initializes its data member and print their values
#include<stdio.h>
#include<conio.h>
void main()
{
struct person
{
char name[10];
int age;
float salary;

Dr. SL, VGK,SNK Dept of ISE, RNSIT Page 22

 Data Structures and Applications [21CS32]

};
struct person p1;
clrscr();
strcpy(p1.name,"james");
p1.age=10;
p1.salary=35000;
printf("\n name=%s age=%d salary=%f",p1.name,p1.age,p1.salary);
getch();
}
Array of Structures
An array of structure can also be declared. Each element of the array representing a structure
variable.
Example : struct employee emp[5];
The above code define an array emp of size 5 elements. Each element of array emp is of type employee
#include<stdio.h>
#include<conio.h>
struct employee
{
char ename[10];
int sal;
};
struct employee emp[5];
int i,j;
void ask()
{
for(i=0;i<3;i++)
{
printf("\nEnter %dst employee record\n",i+1);
printf("\nEmployee name\t");
scanf("%s",emp[i].ename);
printf("\nEnter employee salary\t");
scanf("%d",&emp[i].sal);
}

Dr. SL, VGK,SNK Dept of ISE, RNSIT Page 23

 Data Structures and Applications [21CS32]

printf("\nDisplaying Employee record\n");

for(i=0;i<3;i++)
{
printf("\nEmployee name is %s",emp[i].ename);
printf("\nSlary is %d",emp[i].sal);
}
}
void main()
{
clrscr();
ask();
getch();
}
Type definitions and structures
It is possible to create our own data types (user defined) by using typedef statement as below
typedef struct
{
char name[10];
int age;
} humanbeing;
Here humanbeing is the name of the type defined by structure definition and we may follow this
definition with declarations of variables such as humanbeing person1, person2;
 Structures cannot be directly checked for equality or nor equality. i.e. directly using
person1==person2 is not allowed. If each individual data member is checked for equality then
the entire structure can be checked for equality.

Function to Check equity of two structures

#define FALSE 0
#define TRUE 1
int humansEqual(humanBeing person1, humanBeing person2))
{
if(strcmp(person1.name,person2.name))
return FALSE;

Dr. SL, VGK,SNK Dept of ISE, RNSIT Page 24

 Data Structures and Applications [21CS32]

if((person1.age!=person2.age)
return FALSE;
if((person1.salary!=person2. salary)
return FALSE;
return TRUE;
}
void main()
{
if(humansEqual(person1,person2))
printf(“the two human beings are the same\n”);
else
printf(“the two human beings are not the same”);
}

Program to check equality to structure variables.

#include<stdio.h>
#include<conio.h>
#define FALSE 0
#define TRUE 1
typedef struct
{
char name[10];
int age;
float salary;
}humanbeing;
int humansEqual(humanbeing p1,humanbeing p2)
{
if(strcmp(p1.name,p2.name))
return FALSE;
if(p1.age!=p2.age)
return FALSE;
if(p1.salary!=p2.salary)
return FALSE;

Dr. SL, VGK,SNK Dept of ISE, RNSIT Page 25

 Data Structures and Applications [21CS32]

else
return TRUE;
}
void main()
{
humanbeing p1,p2;
clrscr();
strcpy(p1.name,"hiiiii");p1.age=12;p1.salary=12000;
strcpy(p2.name,"hi");p2.age=12;p2.salary=12000;
if(humansEqual(p1,p2))
printf("\n persons are same ");
else
printf("\n persons are not same");
getch();
}

Pointers to Structures
Pointer to a structure is a variable that holds the address of a structure. The syntax to declare
pointer to a structure can be given as:
strcut struct_name *ptr;
eg: struct stud *ptr_stud;
To assign address of stud to the pointer using address operator(&) we would write ptr_stud=&stud; To
access the members of the structure (->) operator is used.
for example
ptr_stud->name=Raj;

Nested Structures
It is possible to embed a structure within a structure. “The structure that contains another
structure variable as its members is called a nested structure or a structure within a structure is
called nested structure.”
 The structure should be declared separately and then be grouped into high level structure. The data
members of the nested structures can be accessed using (.) Dot operator.
 Syntax to follow while accessing the data members of inner structure in nested structure with dot
operator is outer most structure variable. inner most structure variable. inner data member ;

Dr. SL, VGK,SNK Dept of ISE, RNSIT Page 26

 Data Structures and Applications [21CS32]

 Syntax to followed while accessing the data members of outer structure in nested structure with
dot operator is outer most structure variable .outer data member ;
Type1: declaring structure within a structure
Example :
struct student
{
char name[20];
int marks;
float per;
struct dob
{
int day,month,year;
}date;
}s1;
void main()
{
printf(“\n enter the student details-name marks percentage and date of birth”);
scanf (“%s%d%f%d%d%d”,s1.name,&s1.marks,&s1.per,&s1.date.day,&s1. date.month,
&s1.date.year);
printf(“the given student details is as follows”);
printf(“\n name =%s marks=%d percentage=%d dob=%d/%d/%d”, s1.name, s1.marks,s1.per,
s1.date.day,s1.date.month,s1. date.year);
getch();
}
Type 2: declaring a structure variable of one within another structure
Example :
struct dob
{
int day,month,year;
};
struct student
{
char name[20];

Dr. SL, VGK,SNK Dept of ISE, RNSIT Page 27

 Data Structures and Applications [21CS32]

int marks;
float per;
struct dob date;
}s1;
void main()
{
printf(“\n enter the student details-name marks percentage and date of birth”);
scanf (“%s%d%f%d%d%d”,s1.name,&s1.marks,&s1.per,&s1.date.day,&s1. date.month,
&s1.date.year);
printf(“the given student details is as follows”);
printf(“\n name =%s marks=%d percentage=%d dob=%d/%d/%d”, s1.name, s1.marks,s1.per,
s1.date.day,s1.date.month,s1.date.year);
getch();
}
Nested structures with typedef
Example :
typedef struct
{
int month;
int day;
int year;
}date;
typedef struct
{
char name[10];
int age;
salary;
date dob;
}humanbeing;
humanbeing person1,person2;
If humanbeing person1 and person2 declares person1 and person2 variables of type humanbeing.
Then consider a person born on feb 11, 1944, can have the values for the date struct set as:
person1.dob.month=2;

Dr. SL, VGK,SNK Dept of ISE, RNSIT Page 28

 Data Structures and Applications [21CS32]

person1.dob.day=11;
person1.dob.year=1944;
Similarly for considering person2, his dob is 3rd December 1956 then
person2.dob.month=12;
person2.dob.day=3;
person2.dob.year=1956;

Program for illustration of nested structures with typedef

#include<stdio.h>
#include<conio.h>
void main()
{
typedef struct
{
int month;
int day;
int year;
}date;
typedef struct
{
char name[10];
int age;
salary;
date dob;
}humanbeing;
humanbeing person1;
strcpy(person1.name,"james");
person1.age=10;
person1.salary=35000;
Person1.dob.month=2;
Person1.dob.day=11;
Person1.dob.year=1944;
printf(“\n details of the person”);

Dr. SL, VGK,SNK Dept of ISE, RNSIT Page 29

 Data Structures and Applications [21CS32]

printf("\n name=%s age=%d salary=%f dob=%d-%d-%d",person1.name,

person1.age,person1.salary,Person1.dob.day,Person1.dob.month,Person1.dob.year);
getch();
}

SELF REFERENTIAL STRUCTURES

“Self –referential structures are those structures that contain a reference to data of its same
type as that of structure. i.e one or more of the components of the structure will be a pointer to itself.”
Example 1
struct node
{
int val;
struct node*next;
}list;

Example 2:
typedef struct
{
char data;
struct list * link;
}list;
In this example each instance of the structure list have two components data and link.
Data is a single character, while link is a pointer to a list structure.
The value of link is either the address in memory of an instance of list or NULL pointer.
Program to illustrate self-referential structures
#include <stdio.h>
#include <conio.h>
typedef struct
{
char data;
struct list *link;
}list;
void main()
{
Dr. SL, VGK,SNK Dept of ISE, RNSIT Page 30
 Data Structures and Applications [21CS32]

list l1,l2,l3;
l1.data='a';
l2.data='b';
l3.data='c';
l1.link=&l1;
l2.link=&l2;
l3.link=&l3;
printf("\n data values of l1=%d,l2=%d,l3=%d",l1.data,l2.data,l3.data);
printf("\n link of l1,l2,l3=%d %d %d",l1.link,l2.link,l3.link);
getch();
}

UNIONS
Union is a collection of variables of different data types. Union information can only be stored in
one field at any one time.
Definition: “A union is a special data type available in C that enables you to store different
data types in the same memory location. “
union can define many members, but only one member can contain a value at any given time.
Unions provide an efficient way of using the same memory location for multi-purpose.

Declaring Union:
union union-name
{
data_type1 member_name1;
data_type2 member_name2;
.. ..
data_typen member_namen;
}unionvariablename;

Example:
union data
{
char a;

Dr. SL, VGK,SNK Dept of ISE, RNSIT Page 31

 Data Structures and Applications [21CS32]

int x;
float f;
}mydata;
The union tag is optional and each member definition is a normal variable definition, such as int
i; or float f; or any other valid variable definition.
At the end of the union's definition, before the final semicolon, you can specify one or more
union variables but it is optional. The memory occupied by a union will be large enough to hold the
largest member of the union. For example, in above example Data type will occupy 4 bytes of memory
space because this is the maximum space which can be occupied by float data.

Accessing a Member of a Union

#include <stdio.h>
#include <string.h>
union Data
{
int i;
float f;
char str[20];
};
int main( )
{
union Data data;
data.i = 10;
data.f = 220.5;
strcpy( data.str, "C Programming");
printf( "data.i : %d\n", data.i);
printf( "data.f : %f\n", data.f);
printf( "data.str : %s\n", data.str); return 0;
}
Dot operator can be used to access a member of the union. The member access operator is coded
as a period between the union variable name and the union member that we wish to access.

Dr. SL, VGK,SNK Dept of ISE, RNSIT Page 32

 Data Structures and Applications [21CS32]

Program to illustrate union within a structure.

#include<stdio.h>
#include<conio.h>
typedef struct
{
enum tagfield {female,male} gender;
union
{
int child;
int beard;
}u;
}gendertype;
typedef struct
{
int m,d,y;
}date;
typedef struct
{
char name[10];
int age;
float salary;
date dob;
gendertype genderinfo;
}humanbeing;
void main()
{
humanbeing p1;
p1.dob.m=2;
p1.dob.d=11;
p1.dob.y=1994;
p1. genderinfo.gender=female;
p1. genderinfo.u.child=4;
printf("year=%d/%d/%d",p1.dob.m,p1.dob.d,p1.dob.y);

Dr. SL, VGK,SNK Dept of ISE, RNSIT Page 33

 Data Structures and Applications [21CS32]

printf("\n gender=%d b=%d",p1. genderinfo.gender, p1. genderinfo.u. child);

getch();
}

Difference between structure and union

1.The keyword struct is used to define a 1. The keyword union is used to define a union.
structure
2. When a variable is associated with a 2. When a variable is associated with a union,
structure, the compiler allocates the memory the compiler allocates the memory by
for each member. considering the size of the largest memory.
The size of structure is greater than or equal to So, size of union is equal to the size of largest
the sum of sizes of its members. The smaller member.
members may end with unused slack bytes.
3. Each member within a structure is assigned 3. Memory allocated is shared by individual
unique storage area of location. members of union.
4. The address of each member will be in 4. The address is same for all the members of a
ascending order. This indicates that memory union. This indicates that every member begins
for each member will start at different offset at the same offset value.
values.
5 Altering the value of a member will not 5. Altering the value of any of the member will
affect other members of the structure. alter other member values.
6. Individual member can be accessed at a time 6. Only one member can be accessed at a time.
7. Several members of a structure can initialize 7. Only the first member of a union can be
at once. initialized.
Ex: struct Book Ex: union Book
{ {
int isbn; int isbn;
float price; float price;
char title[20]; char title[20];
}book; }book;
Total memory reserved will be Total memory reserved will be
Sizeof(int)+sizeof(float)+(20*sizeof(char)) Max(Sizeof(int)+sizeof(float)+(20*sizeof(char))

Dr. SL, VGK,SNK Dept of ISE, RNSIT Page 34

 Data Structures and Applications [21CS32]

POINTERS
“Pointers are variables that hold address of another variable of same data type”,
Pointers are one of the most distinct and exciting features of C language. It provides power and
flexibility to the language.
Benefit of using pointers
 Pointers are more efficient in handling Array and Structure.
 Pointer allows references to function and thereby helps in passing of function as arguments to
other function.
 It reduces length and the program execution time.
 It allows C to support dynamic memory management.
Concept of Pointer
Whenever a variable is declared, system will allocate a location to that variable in the memory,
to hold value. This location will have its own address number. Let us assume that system has allocated
memory location 80F for a variable a.
Example : int a = 10 ;

The value 10 can be accessed by either using the variable name a or the address 80F.Since the
memory addresses are simply numbers they can be assigned to some other variable. The variable that
holds memory address are called pointer variables. A pointer variable is therefore nothing but a
variable that contains an address, which is a location of another variable. Value of pointer variable will
be stored in another memory location.

Figure 5: Pointer variable

Declaring a pointer variable
General syntax of pointer declaration is, data-type *pointer_name;
Dr. SL, VGK,SNK Dept of ISE, RNSIT Page 35
 Data Structures and Applications [21CS32]

Data type of pointer must be same as the variable, which the pointer is pointing. void type
pointer works with all data types, but isn't used often.
Initialization of Pointer variable
Pointer Initialization is the process of assigning address of a variable to pointer variable.
Pointer variable contains address of variable of same data type. In C language address operator & is
used to determine the address of a variable. The & (immediately preceding a variable name) returns the
address of the variable associated with it.
int a = 10 ;
int *ptr ; //pointer declaration
ptr = &a ; //pointer initialization
or,
int *ptr = &a ; //initialization and declaration together

Pointer variable always points to same type of data.

float a;
float *ptr;
ptr = &a;

Dereferencing of Pointer
Once a pointer has been assigned the address of a variable. To access the value of variable, pointer is
dereferenced, using the indirection operator *.
void main()
{
int a,*p;
a = 10;
p = &a;
printf("%d",*p); //this will print the value of a.
printf("%d",*&a); //this will also print the value of a.
printf("%u",&a); //this will print the address of a.
printf("%u",p); //this will also print the address of a.
printf("%u",&p); //this will also print the address of p.
}

Pointer and Arrays

Dr. SL, VGK,SNK Dept of ISE, RNSIT Page 36

 Data Structures and Applications [21CS32]

When an array is declared, compiler allocates sufficient amount of memory to

contain all the elements of the array. Base address which gives location of the first element is also
allocated by the compiler.
Suppose we declare an array arr,
int arr[5]={ 1, 2, 3, 4, 5 };
Assuming that the base address of arr is 1000 and each integer requires two byte,
the five element will be stored as follows in figure 6

Figure 6: Array Representation

Here variable arr will give the base address, which is a constant pointer pointing to
the element, arr[0]. Therefore arr is containing the address of arr[0] i.e 1000.
We can declare a pointer of type int to point to the array arr.
int *p;
p = arr;
or p = &arr[0]; //both the statements are equivalent.
Now we can access every element of array arr using p++ to move from one element to another.
NOTE: You cannot decrement a pointer once incremented. p-- won't work.

Pointer to Array
As studied above, we can use a pointer to point to an Array, and then we can use that pointer to access
the array. Let’s have an example,
int i;
int a[5] = {1, 2, 3, 4, 5};
int *p = a; // same as int*p = &a[0]
for (i=0; i<5; i++)
{
printf("%d", *p);
p++;
}

Dr. SL, VGK,SNK Dept of ISE, RNSIT Page 37

 Data Structures and Applications [21CS32]

In the above program, the pointer *p will print all the values stored in the array one by one. We can also
use the Base address (a in above case) to act as pointer and print all the values.
Replacing the printf(“%d”,*p); statement of above example ,with below mentioned statements. Let’s see
what will be the result
 printf(“%d”,a[i]); prints the array, by incrementing index

 printf(“%d”,i[a]); this will also print elements of array

 printf(“%d”,a+i); this will also print address of all elements of array

 printf(“%d”,*(a+i)); this will also print values of all elements of array

 printf(“%d”,*a); this will print value of a[0] only

 a++; compile time error, we cannot change base address of the array.

Pointers to multidimensional array

A multidimensional array is of form, a[i][j] . Lets see how we can make a pointer point to such
an array. As we know now, name of the array gives its base address. In a[i][j] , a will give the base
address of this array, even a+0+0 will also give the base address, that is the address of a[0][0] element.
Here is the generalized form for using pointer with multidimensional arrays.
*(*(ptr + i) + j) is same as a[i][j]

DYNAMIC MEMORY ALLOCATION

The memory allocation which is used till now was static memory allocation. So the memory that
could be used by the program was fixed. So it is not possible to allocate or de allocate memory during
the execution of the program. It is not possible to predict how much memory will be needed by the
program at run time.
For example assume an array with size 20 elements is declared, which is fixed. So if at run time
values to be stored in array are less than 20 then wastage of memory occur or our program may fail if
more than 20 values are to be stored in to that array. To solve the above problems and allocate memory
during runtime dynamic memory allocation is used.
The process of allocating memory during the runtime is called as DMA (dynamic memory
allocation) and memory gets allotted in heap area of program stack.

Dr. SL, VGK,SNK Dept of ISE, RNSIT Page 38

 Data Structures and Applications [21CS32]

Example: a new area of memory is allocated using malloc().On success, malloc() returns a
pointer to the first byte of allocated memory. The returned pointer is of type void, which can be type cast
to appropriate type of pointer. The memory allocated by malloc() contains garbage value . when the
requested memory is not available, the pointer NULL is returned. when allocated memory is no longer
required , it is freed by using another function free().
void main()
{
int i,*pi;
float f,*pf;
pi=(int*)malloc(sizeof(int));
pf=(float*)malloc(sizeof(float));
*pi=1024;
*pf=3.14;
printf(“an interger=%d,an float number=%f”,*pi,*pf);
free(pi);
free(pf);
getch();
}
it shows allocation and deallocation of memory
if((pi=(int *)malloc(sizeof(int))==NULL) || (pf=(float*)malloc(sizeof(float))==NULL))
{
fprintf(stderr,”insufficient memory”);
exit(EXIT_FAILURE);
}
if(!(pi=malloc(sizeof(int))) || !(pf=malloc(sizeof(float)))

#define MALLOC(p,s)
If(!((p))=malloc(n,s))
{
fprintf(stderr,”insufficient memory”);
exit(EXIT_FAILURE);
}
thus ,MALLOC(pi, sizeof(int));

Dr. SL, VGK,SNK Dept of ISE, RNSIT Page 39

 Data Structures and Applications [21CS32]

MALLOC(pf,sizeof(float));

int *x;
x=calloc(n,sizeof(int));
Instead of calloc function a calloc macro can be defined as sown below
#define CALLOC(p,n,s)
if(!((p))=calloc(n,s))
{
fprintf(stderr,”insufficient memory”);
exit(EXIT_FAILURE);
}
The function realloc resizes the memory allocated by either malloc or calloc.
Ex: realloc(p,s)
This realloc(p,s) function changes the size of the memory block pointed at p to s.the contents of
the first allocated s with oldsize bytes of the block are unchanged as a result of this resizing.when
s>oldsize the additional s-oldsize have an unspecified value and s<oldsize the rightmost oldsize-s bytes
of the old block are freed.when realloc is able to do the resizing it returns a pointer to the start of the
new block and when it is unable to do the resizing the old block is unchanged and function returns the
value NULL.

#define REALLOC(p,s)
if(!((p))=realloc(p,s))
{
fprintf(stderr,”insufficient memory”);
exit(EXIT_FAILURE);
}
//Sample program to illustrate macro Definition for malloc()
#include<stdio.h>
#define MALLOC(p,s) \
if(!((p)=malloc(s))) { \
fprintf(stderr, "Insufficient Memory");\
exit(1); \
}

Dr. SL, VGK,SNK Dept of ISE, RNSIT Page 40

 Data Structures and Applications [21CS32]

void main()
{
int *p,i,n;
printf("Enter the no. of values\n");
scanf("%d",&n);
MALLOC(p,n*sizeof(int));
printf("Enter n values\n");
for(i=0;i<n;i++)
scanf("%d",(p+i));
printf("Values are\n");
for(i=0;i<n;i++)
printf("%d\t",*(p+i));
}

//Sample program to illustrate macro Definition for realloc()

#include<stdio.h>
#define REALLOC(p,s) \
if(!((p)=realloc(s))) { \
fprintf(stderr, "Insufficient Memory");\
exit(1); \
}
void main()
{
int *p,i,n;
printf("Enter the no. of values\n");
scanf("%d",&n);
MALLOC(p,n*sizeof(int));
printf("Enter n values\n");
for(i=0;i<n;i++)
scanf("%d",(p+i));
printf("Values are\n");
for(i=0;i<n;i++)
printf("%d\t",*(p+i));

Dr. SL, VGK,SNK Dept of ISE, RNSIT Page 41

 Data Structures and Applications [21CS32]

printf("Enter new value of n");

scanf("%d",&n);
REALLOC(p,n*sizeof(int));
printf("Enter n values\n");
for(i=0;i<n;i++)
scanf("%d",(p+i));
printf("Values are\n");
for(i=0;i<n;i++)
printf("%d\t",*(p+i));

}
//Sample program to illustrate macro Definition for calloc()
#include<stdio.h>
#define CALLOC(p,n.s) \
if(!((p)=calloc(n,s))) { \
fprintf(stderr, "Insufficient Memory");\
exit(1); \
}
void main()
{
int *p,i,n;
printf("Enter the no. of values\n");
scanf("%d",&n);
CALLOC(p,n,sizeof(int));
printf("Enter n values\n");
for(i=0;i<n;i++)
scanf("%d",(p+i));
printf("Values are\n");
for(i=0;i<n;i++)
printf("%d\t",*(p+i));
}

Dr. SL, VGK,SNK Dept of ISE, RNSIT Page 42

 Data Structures and Applications [21CS32]

The following functions are used in dynamic memory allocation and are defined in <stdlib.h>
1. malloc()
Declaration: ptr=(datatpe*) malloc(size)
This function is used to allocate memory dynamically. The argument size specifies the number
of bytes to be allocated. On success, malloc() returns a pointer to the first byte of allocated memory. The
returned pointer is of type void, which can be type cast to appropriate type of pointer. The memory
allocated by malloc() contains garbage value .
2. calloc()
Declaration: ptr=(datatype*)calloc(n,size);
This function is used to allocate multiple blocks of memory. The first argument specifies the
number of blocks and the second one specifies the size of each block. The memory allocated by calloc()
is initialized to zero.
3. realloc()
Declaration: ptr=(datatype*)realloc(ptr,newsize)
The function realloc() is used to change the size of the memory block. It alters the size of the
memory block without losing the old data. This function takes two arguments, first is a pointer to the
block of memory that was previously allocated by malloc() or calloc() and second one is the new size for
that block.
4. free();
Declaration: free(ptr);
This function is used to release the memory space allocated dynamically. The memory released
by free() is made available to the heap again and can be used for some other purpose. We should not try
to free any memory location that was not allocated by malloc(), calloc() or realloc().
C programming allots memory at heap during runtime
C provides two additional Dynamic memory allocation functions calloc and realloc . The calloc function
allocates a user specified amount of memory and initializes the allocated memory to 0 , a pointer to the
start of the allocated memoey is returned. In case ther is insufficient memory to make the allocation , the
returned value is NULL.so, the example statements could be used to define a one dimensional array of
integers with the capacity of this array is n and x ranges from 0 to n-1 with initially 0 value.

Dr. SL, VGK,SNK Dept of ISE, RNSIT Page 43

 Data Structures and Applications [21CS32]

Difference between malloc() and calloc()

malloc() calloc()
The name malloc stands for memory The name calloc stands for contiguous
allocation. allocation.

void *malloc(size_t n) returns a pointer void *calloc(size_t n, size_t size) returns a

to n bytes of uninitialized storage, pointer to enough free space for an array of
or NULL if the request cannot be n objects of the specified size, or NULL if the
satisfied. If the space assigned request cannot be satisfied. The storage is
by malloc() is overrun, the results are initialized to zero.
undefined.

malloc() takes one argument that calloc() take two arguments those are: number
is, number of bytes. of blocks and size of each block.

syntax of malloc(): syntax of calloc():

void *malloc(size_t n); void *calloc(size_t n, size_t size);
Allocates n bytes of memory. If the Allocates a contiguous block of memory large
allocation succeeds, a void pointer to the enough to hold n elements of size bytes each.
allocated memory is returned. The allocated region is initialized to zero.
Otherwise NULL is returned.

malloc is faster than calloc. calloc takes little longer than malloc because
of the extra step of initializing the allocated
memory by zero. However, in practice the
difference in speed is very tiny and not
recognizable.

The following program illustrates Dynamic memory allocation.

void main()
{
int *p,n,i;
printf(“Enter the number of integers to be entered”);
scanf(“%d”,&n);
p=(int *)malloc(n*sizeof(int)); /* This is same as “(int *)calloc(n,sizeof(int))”*/

Dr. SL, VGK,SNK Dept of ISE, RNSIT Page 44

 Data Structures and Applications [21CS32]

/* If we write “(int *)malloc(sizeof(int))” then only 2 byte of memory will be allocated

dynamically*/
if(p==NULL)
{
printf(“Memory is not available”); exit(1);
}
for(i=0;i<n;i++)
{
printf(“Enter an integer”);
scanf(“%d”,p+i);
}
for(i=0;i<n;i++)
printf(”%d\t”,*(p+i));
}

DYNAMICALLY ALLOCATED ARRAYS

Array can be dynamically allotted using malloc(), calloc() or realloc() functions, similarly the
allotted memory can be freed after the use of array using free() function.

One dimensional array

When large programs are written, it is difficult to determine how large array to use. So, solution
to this problem is to defer this decision to runtime and allocate the required array size. The advantage of
dynamic array is that the memory for the array of any desired size can be allotted. There is no need to
declare a fixed size array.
During the use of dynamically allocated arrays the following changes are required in first few
lines of main function of program
int i ,n,*list;
printf(“\n enter the n value to generate”);
scanf(“%d”,&n);
if(n<1)
{
fprintf(stderr,”improper value of \n”);
exit(EXIT_FAILURE);
}

Dr. SL, VGK,SNK Dept of ISE, RNSIT Page 45

 Data Structures and Applications [21CS32]

MALLOC(list,n*sizeof(int));
This above main function fails only when n<1 or when sufficient memory is not allotted.

Example program for illustration of use of dynamic array:-

#include<stdio.h>
#include<stdlib.h>
void main()
{
int i,n;
int *ptr;
printf(“\n enter the number of elements\n”);
scanf(“%d”,&n);
ptr=(int*)malloc(sizeof(int)*n);
if(ptr==NULL)
{
printf(“\n insufficient memory”);
return;
}
printf(“\n enter the n elements”);
for(i=0;<n;i++)
scanf(“%d”,(ptr+i));
printf(“the given array elements are \n”);
for(i=0;i<n;i++)
printf(“%d”,*(ptr+i));
getch();
}

Two dimensional array

A two dimensional array is represented as a one dimensional array in which each element is itself
a one dimensional array.(As shown in figure 9)
int x[3][5];
Here, actually a one dimensional array x is created whose length is 3 and each element of x is a one
dimensional array whose length is 5.

Dr. SL, VGK,SNK Dept of ISE, RNSIT Page 46

 Data Structures and Applications [21CS32]

[0] [1] [2] [3] [4]

x[0]
x[1]
x[2]
Figure 9: Two dimensional array
C finds the element x[i][j] by first accessing the point in x[i].this pointer gives the address in memory of
the zeroth element of row I of the array. Then by adding j*sizeof(int) to this pointer , the address of the
[j]th elemnt of row i is determined.
Example program for allocating memory dynamically for 2D array
#include<stdio.h>
#include<conio.h>
#include<alloc.h>
void main()
{
int **a;
int p,q;
int ** make2darray();
printf(“\n enter the no of rows”);
scanf(“%d”,&p);
printf(“\n enter the no of cols”);
scanf(“%d”,&q);
a=make2darray(p,q);
printf(“successful memory creation address is”,a);
getch();
}
int **make2darray(int rows,int cols)
{
int **x,i;
x=malloc(rows*sizeof(*x));
for(i=0;i<rows;i++)
x[i]=malloc(cols*sizeof(**x));
return x;
}
Dr. SL, VGK,SNK Dept of ISE, RNSIT Page 47
 Data Structures and Applications [21CS32]

APPLICATIONS OF ARRAYS
The two major applications of the arrays are polynomial and sparse matrix

1. POLYNOMIALS
Polynomial is a sum of terms where each term has a form axe, where x is the variable, a is the
coefficient and e is the exponent.

Examples :
A(x) = 3x20+2x5+4
B(x) = x4+10x3+3x2+1
The largest exponent of a polynomial is called its degree.
In the above example, degree of first polynomial is 20 and for the second polynomial it is 4.
Note: Coefficients that are zero are not displayed, the term with exponent zero does not show the
variable i.e. 4x2+5x+1 where 1 is a term having exponent zero so variable is not displayed.
Operations on polynomials
 Addition
 Subtraction
 Multiplication
 But division is not allowed.

Polynomial addition is defined as :

Assume A(x)=∑aixi and B(x)=∑bjxi then A(x)+ B(x)=∑(ai+bj)xi
Polynomial multiplication is defined as:
A(x).B(x)=∑ A(x)=∑aixi.(∑bjxi))
Polynomial representation
In c, typedef is used to create the polynomial as below:-
#define MAX_DEGREE 101
typedef struct
{
int degree;
float coef[MAX_DEGREE];
}polynomial;
polynomial a;

Dr. SL, VGK,SNK Dept of ISE, RNSIT Page 48

 Data Structures and Applications [21CS32]

Conisder a is of type polynomial and n>MAX_DEGREE then polynomial A(x)=∑aixi for i=0 to n
would be represented as
a.degree=n;
a.coef[i]=an-i,0<=i<=n.

Useful polynomial representation

To preserve space, an alternative polynomial representation is given below which uses only one
global array, terms to store all polynomials
#define MAX_TERMS 100
typedef struct
{
float coeff;
int expon;
}polynomial;
polynomial terms[MAX_TERMS];
int avail=0;
ADT polynomial

Polynomial addition

Dr. SL, VGK,SNK Dept of ISE, RNSIT Page 49

 Data Structures and Applications [21CS32]

Function which adds two polynomials A and B giving D, represented as D=A+B. using previous
polynomial representation the following figure 10 shows how two polynomials are represented
Ex: A(x) = 2x1000+1
B(x) = 1x4+10x3+3x2+1

Figure 7: Array representation of polynomial

The index of the first term of A and B is given by startA and startB respectively,while finishA
and finishB give the index of the last term of A and B. the index of the next free location in the array is
given by avail.
Example startA=0,finishA=1,startB=2,finish=5 and avail=6.
This representation ha no limitation on the number of terms in a polynomial but total number of
non-zero terms should not exceed MAX_TERMS.
Poly is used to refer a polynomial and is translated poly into a <start,finish>pair. Any polynomial
A that has n nonzero terms has startA and finishA such that finishA=startA+n-1.
Function To Add Two Polynomials
void polyadd(int startA,int finishA,int startB, int finishB,int *startD,int *finishD)
{
float coefficient;
*startD=avail;
while(startA<=finishA && startB<=finishB)
switch(COMPARE(terms[startA].expon,terms[startB].expon))
{
case -1: /* a.expon<b.expon)*/
attach(terms[startB].coef,terms[startB].expon);
startB++;
break;
case 0:/* equal exponents*/
coefficient=terms[startA].coef+terms[startB].coef;
if(coefficient)
attach(coefficient , terms[startA].expon);

Dr. SL, VGK,SNK Dept of ISE, RNSIT Page 50

 Data Structures and Applications [21CS32]

startA++;
startB++;
break;
case 1: /*a.expon>b.expon*/
attach(terms[startA].coef,terms[startA].expon);
startA++;
}
for(;startA<=finishA;startA++)
attach(terms[startA].coef,terms[startA].expon);
for(;startB<=finishB;startB++)
attach(terms[startB].coef,terms[startB].expon);
*finishD=avail-1;
}
Function to add a new term
void attach(float coefficient ,int exponent)
{
if(avail>=MAX_TERMS)
{
printf(stderr,”too many terms in the polynomial\n”);
exit(0);
}
terms[avail].coef=coefficient;
terms[avail++].expon=exponent;
}

2. SPARSE MATRICES
Matrix contains m rows and n columns of elements. it has m rows and n columns. In general
mxn, is used to designate a matrix with m rows and n columns. The total no of elements in such matrix
is m*n. If m equals n then matrix is square.

“Sparse matrix: A matrix containing more number of zero entries, such matrix is called as
sparse matrix.”

Dr. SL, VGK,SNK Dept of ISE, RNSIT Page 51

 Data Structures and Applications [21CS32]

In figure8, since this matrix contains many zeros it is called as sparse matrix. Here 8 of 36
elements are only having non-zero values so it is called as sparse matrix. When sparse matrix is
represented as two dimensional array hence space is wasted so need another form of representation to
save memory where only non-zero values are stored.

Figure 8: Sparse Matrix

ADT sparse matrix

Dr. SL, VGK,SNK Dept of ISE, RNSIT Page 52

 Data Structures and Applications [21CS32]

Sparse Matrix representation

A array of triples <row,col,value> is used to represent sparse matrix. In triples the row indices
are in ascending order as well as column indices are also in ascending order.(as shown in figure 12).
First row in triplet representation gives the total number of rows, total number of columns and total
number of non-zero values in sparse matrix.
Create operation of sparse matrix is written as
#define MAX_TERMS 101
typdef struct
{
int col;
int rows;
int value;
}term A[MAX_TERMS];
The above Sparse matrix is represented as triples.

Figure 9: Triple Representation

Transposing a Matrix

Transpose of a given matrix is obtained rows and columns. each element a[i][j].In the original
matrix becomes element b[j][i] in the transpose matrix.
The following algorithm is given by

Dr. SL, VGK,SNK Dept of ISE, RNSIT Page 53

 Data Structures and Applications [21CS32]

The algorithm indicates that find all the elements in column 0 and store them in row 0 of the
transpose matrix, find all the elements in column1 and store them in row1 etc. Since the original matrix
ordered the rows, the columns within each row of incorporated in transpose. The first array a is the
original array which the second array b holds the transpose.(As shown in figure13)

Figure 10: Transpose of matrix

Function: Transpose a sparse matrix.
void transpose(term a[],term b[])
{
int n,i,j,currentb;
n=a[0].value;
b[0].row=a[0].col;
b[0].col=a[0].row;

Dr. SL, VGK,SNK Dept of ISE, RNSIT Page 54

 Data Structures and Applications [21CS32]

b[0].value=n;
if(n>0)
{
currentb=1;
for(i=0;i<a[0].col;i++)
for(j=1;j<=n;j++)
if(a[j].col==i)
{
b[currentb].row=a[j].col;
b[currentb].col=a[j].row;
b[currentb].value=a[j].value;
currentb++;
}
}
}

Dr. SL, VGK,SNK Dept of ISE, RNSIT Page 55

 Data Structures and Applications [21CS32]

PROGRAMMING EXAMPLES
1) Write a C program to sort N numbers in ascending order using Bubble sort and print both the
given and the sorted array
#include <stdio.h>
#define MAXSIZE 10
void main()
{
int array[MAXSIZE];
int i, j, num, temp;

printf("Enter the value of num \n");

scanf("%d", &num);
printf("Enter the elements one by one \n");
for (i = 0; i < num; i++)
{
scanf("%d", &array[i]);
}
printf("Input array is \n");
for (i = 0; i < num; i++)
{

Dr. SL, VGK,SNK Dept of ISE, RNSIT Page 56

 Data Structures and Applications [21CS32]

printf("%d\n", array[i]);
}
/* Bubble sorting begins */
for (i = 0; i < num; i++)
{
for (j = 0; j < (num - i - 1); j++)
{
if (array[j] > array[j + 1])
{
temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
printf("Sorted array is...\n");
for (i = 0; i < num; i++)
{
printf("%d\n", array[i]);
}
}

2) Write a C program to input N numbers and store them in an array. Do a linear search for a
given key and report success or failure.
#include <stdio.h>
void main()
{
int array[10];
int i, num, keynum, found = 0;
clrscr();
printf("Enter the value of num \n");
scanf("%d", &num);
printf("Enter the elements one by one \n");

Dr. SL, VGK,SNK Dept of ISE, RNSIT Page 57

 Data Structures and Applications [21CS32]

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

{
scanf("%d", &array[i]);
}
printf("Input array is \n");
for (i = 0; i < num; i++)
{
printf("%d\n", array[i]);
}
printf("Enter the element to be searched \n");
scanf("%d", &keynum);
/* Linear search begins */
for (i = 0; i < num ; i++)
{
if (keynum == array[i] )
{
found = 1;
break;
}
}
if (found == 1)
printf("Element is present in the array\n");
else
printf("Element is not present in the array\n");
}

3) Write a C program to input N numbers and store them in an array. Do a binary search for a
given key and report success or failure.
#include<stdio.h>
main()
{
int a[20],i,j,d,t,x,l=0,low,mid,high;
printf("\nEnter the number of elements\n");
scanf("%d",&d);
Dr. SL, VGK,SNK Dept of ISE, RNSIT Page 58
 Data Structures and Applications [21CS32]

printf("Enter the numbers\n");

for(i=0;i<d;i++)
scanf("%d",&a[i]);
for(i=0;i<d;i++)
{
for(j=i+1;j<d;j++)
{
if(a[i]>a[j])
{
t=a[i];
a[i]=a[j];
a[j]=t;
}
}
}
printf("\nThe sorted list :");
for(i=0;i<d;i++)
printf("%d ",a[i]);
printf("\nEnter the number to be searched\n");
scanf("%d",&x);
low=0;
high=d-1;
while(low<=high)
{
mid=(low+high)/2;
if(x<a[mid])
high=mid-1;
else if(x>a[mid])
low=mid+1;
else
{
if(x==a[mid])
{

Dr. SL, VGK,SNK Dept of ISE, RNSIT Page 59

 Data Structures and Applications [21CS32]

l++;
printf("The item %d is found at location %d\n",x,mid+1);
exit(0);
}
}
}
if(l==0)
printf("Item not found\n");
}

4. Program to illustrate union inside structure

#include <stdio.h>
struct student
{
union
{
char name[20];
int roll_no;
};
int marks;
};
int main()
{
struct student stud;
char choice;
printf(“\n you can enter the name or roll number of the student”);
printf(“\n do you want to enter the name?(Y or N:”);
gets(choice);
if(choice == ‘Y’ || choice == ‘y’)
{
printf(“\n enter the name:”);
gets(stud.name);
}
else
Dr. SL, VGK,SNK Dept of ISE, RNSIT Page 60
 Data Structures and Applications [21CS32]

{
printf(“\n enter the roll number:”);
scanf(“%d”,&stud.roll_no);
}
printf(“\n enter the marks:”);
scanf(“%d”,&stud.marks);
if(choice == ‘Y’ || choice == ‘y’)
printf(“\n Name: %s”,stud.name);
else
printf(“\n Roll number: %d”, stud.roll_no);
printf(“\n Marks: %d”, stud.marks);
return 0;
}

Dr. SL, VGK,SNK Dept of ISE, RNSIT Page 61