DATASTRUCTURE AND APPLICATIONS

Module -1
Introduction
1.1 Data Structures
 “A data structure is a method of storing and organizing the data in a computer so that it
can be used efficiently”.
 Data Structure is a way of collecting and organizing data in such a way that we can perform
operations on these data in an effective way.
 Data Structures is about rendering data elements in terms of some relationship, for better
organization and storage.
 If the data contains a single value, then it can be represented using primitive data types.
 If the data contains set of values, then it can be represented using non-primitive data types.

Need for Data Structures

 The computers are electronics data processing machines.
 In order to solve a particular problem we need to know:
1. How to represent data in a computer.
2. How to access them.
3. What are the steps to be performed in order to get the needed output.
 These tasks can be achieved with the knowledge of Data structures & Algorithms.

The Study of data structure includes

1. Defining operations that can be performed on data.

2. Representing data in the memory.
3. Determining the amount of memory required to store the data.
4. Determining the amount of time needed to process the data.

Dept. of CS&E,JIT-DVG PAGE1

DATASTRUCTURE AND APPLICATIONS

1.2 Classification of Data Structures

The data structures can be classified as shown below:
Integer
Floating point
Primitive Character
Double
Pointers
Data structures
Arrays
Stacks
Linear Queues
Linked lists
Non primitive
Trees
Non linear
Graphs

Figure 1.1 shows the classification of data structures.

Dept. of CS&E,JIT-DVG 1
DATASTRUCTURE AND APPLICATIONS

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

 There are basically four ways of representing such linear structure in memory.
1. Arrays: An array is a collection of similar type of items (elements) stored sequentially
(continuously) one after the other in memory.
2. Stack: A stack is an ordered list in which insertions and deletions are made at one end called
the top.
3. Queue: A queue is an ordered list in which insertions and deletions take place at different
ends.”
4. Linked list: Linked list is a linear data structure that consists of a sequence of elements where
each element comprises of two items - the data and a reference (link) to the next node

 A data structure is said to be non-linear if the data are not arranged in sequence or linear. The
insertion and deletion of data is not possible in linear fashion. i.e.,elements form a hierarchical
classification where, data items appear at various levels.

 Trees: Tree is a non-linear data structure which organizes data in hierarchical fashion and
the tree structure follows a recursive pattern of organizing and storing data.
 Graph: It is basically a collection of vertices (also called nodes) and edges that connect these
vertices.

1.3 Data Structures Operations

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 the location of the data item with a given key value or finding
the locations of all data which satisfy one or more conditions.
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 logical order. e.g., in ascending or
descending order in case of numerical data and in dictionary order in case of alphanumeric
data.
6. Merging: It is used to combine the data items of two sorted files into single file in the sorted
form.

Dept. of CS&E,JIT-DVG 2
DATASTRUCTURE AND APPLICATIONS

1.4 Review of Arrays

1.4.1 Arrays
An Array is a special and powerful data structure and it is used to store, process and print
large amounts of data.
 “An array is a collection of similar type of items (elements) stored sequentially (continuously)
one after the other in memory”.

Ex: 1. int A[5] ; // Array of 5 Integers

A[0] 10
A[1] 20
A[2] 30
A[3] 40
A[4] 50

 The Elements in the Array A can be accessed using the common name A, but with different index.
 The Element „10‟ is called 0th Element and it can be accessed using the Subscript 0 (called Index „0‟)
along with name of the array „A‟.
 An „Index‟ is also called as Subscript ([ ]). It is used to indicate the position of an element in the
Array.

Basic Properties of the Arrays

1. All the elements in an array should be of the same data type.
2. The elements are stored continuously in the memory. (For example, in the array char B[5] , if the first
address is 1000 then the data is stored contiguously in the addresses 1000, 1001, 1002 and so on).

Dept. of CS&E,JIT-DVG 3
 DATASTRUCTURE AND APPLICATIONS

3. The Subscript (index) of first item is always zero.

4. Each element of an array is accessed using the name of the Array, but with different subscript.
5. The Index of the Array is always an Integer number can‟t be float.
Ex: a [1] or a [5].
a [1.5] is an Error.

1.4.2 Classification of Arrays

1. Single Dimensional Array
2. Multi-Dimensional Array

1. Single Dimensional Array

Definition:
Single dimensional array (One-dimensional array) is a linear list consisting of related data
items of same data type and in the memory, all the data items are stored contiguously in
memory locations one after the other.
Or
An array with one index is called as Single dimensional array (One-dimensional array)

Declaration of Single dimensional arrays

 As we declare the variables before they are used in a program, an array must also be declared and
defined before it is used using following syntax.
 Syntax
data_type array_name[size];
Where,
data_type: data type can be int, float, char etc.
array_name: name of the array which is a valid C variable.
size: it is the number of elements in the array.
Complete declaration ends with Semicolon.
Ex: int Marks[5];
Declares Marks as an array consisting of 5 elements of integer data type.

Ex: int Marks[5];

1000 35 Marks[0]
data type array_name 1002 45 Marks[1]
1004 65 Marks[2]
1006 55 Marks[3]
75
char name[5]; 1008 Marks[4]

Memory location Array name

 5 memory locations are reserved. sizeof(int) is 2 bytes, 2*5=10 bytes are reserved.
 5 memory locations are reserved. sizeof(char) is 1 bytes 1*5=5 bytes are reserved.

Dept. of CS&E,JIT-DVG 4
 DATASTRUCTURE AND APPLICATIONS

Initialization of Single dimensional arrays

 Once an array is declared it must be initialized with some values using Initialization.
“Process of assigning the values to the individual elements of an array is called as Initialization
of an array”.

Syntax data_type array_name[size]={v1,v2, ----- ,vn};

data_type: it can be int, float, char etc.

array_name: it is the name of the array.
size: it is the number of elements in the array.
v1,v2, ---- ,vn are the values and should be enclosed within „{„ and „}‟ separated by commas.

Ex: 1. int a[5] = {10, 20, 30, 40, 50};

 The compiler allocates 5 memory locations and these locations are initialized with the integer values
in the order specified.

a[0] 10
a[1] 20
a[2] 30
a[3] 40
a[4] 50

 Address Calculation in single (one) Dimension Arrays:

If the memory address of list[i] needs to be computed, then the size of the int would get by
sizeof (int), then memory address of list[i] is as follows:

list[i] = α + i * sizeof(int)

Where, α is base address.

 For example, an array of 10 integer variables, with indices 0 through 9, may be stored as 10 words at
memory addresses 2000, 2004, 2008, ........ 2036, so that the element with index i has the address 2000
+ i× 4.[hereα is base address whose value is 2000 and sizeof (int) is4]
 For i=0,1,2… (size of int is 4 bytes(32bit machine))

1.4.3 Representation of linear arrays in memory

 Let LA be a linear array in the memory of the computer. The memory of the computer is simply a
sequence of address location as shown below:
Dept. of CS&E,JIT-DVG 5
DATASTRUCTURE AND APPLICATIONS

LOC (LA [K]) = address of the element LA [K] of the array LA

 The elements of LA are stored in successive memory cells.
 The computer does not keep track of the address of every element of LA, but needs to keep track only
the address of the first element of LA denoted by,
 Base (LA) and called the base address of LA.
 Using the base address of LA, the computer calculates the address of any element of LAby the
formula
LOC (LA[K]) = Base(LA) + w(K – lower bound)
 Where, w is the number of words per memory cell for the array LA.

1.5 Array Operations

1.5.1 Traversing
 Let array A be a collection of data elements stored in the memory of the computer. Suppose if the
contents of the each elements of array A needs to be printed or to count the numbers of elements of
array A it can be accomplished by Traversing.
 Traversing is a accessing and processing each element in the array exactly once.

 If you want to read n data items from the keyboard, the following statement can be used:
for(i=0;i<5;i++)
{
scanf(“%d”,&a[i]);
}
 If you want to print „n‟ data items from the keyboard, the following statement can be used:
for(i=0;i<5;i++)
{
printf(“%d\n”, a[i]);
}

1.5.2 Inserting
 Let A be a collection of data elements stored in the memory of the computer. Inserting refers to the
operation of adding another element to the array A.
 Inserting an element at the “end” of the linear array can be easily done provided the memory space
allocated for the array is large enough to accommodate the additional element.
 Inserting an element in the middle of the array, then on average, half of the elements must be moved
downwards to new locations to accommodate the new element and keep the order of the other
elements.
Dept. of CS&E,JIT-DVG 6
DATASTRUCTURE AND APPLICATIONS
Algorithm:
1. Start
2. Read pos, elem.
3. Create space for item to insert at position
for(i=n-1;i>=pos;i- -)
{
A[i+1] = A[i];
}
4. Insert item at the specified position
A[pos] = elem;
5. Update number of elements in the array
n=n+1;
6. Stop

Example: Let us consider an array

Int A[5]={10,20,30,40,50};
A [0] A [1] A [2] A [3] A [4]
10 20 30 40 50
Let us consider an example of insertion of element 100 at position 3
i..e ITEM=100 and pos=3 and n=5
Iteration 1: i = 4, a[5] = a[4]

A [0] A [1] A [2] A [3] A [4] A[5]

10 20 30 40 50 50

Iteration 2: i = 3, a[4] = a[3]

A [0] A [1] A [2] A [3] A [4] A[5]

10 20 30 40 40 50

Iteration 3: i = 2, i>=pos –condition failed.

A[3]=100 // insert element to the pos=3
A [0] A [1] A [2] A [3] A [4] A[5]
10 20 30 100 40 50

Iteration 4: Update number of elements in the array n=6

1.5.3 Deletion
Deleting refers to the operation of removing one element from the array A with specified position.

Dept. of CS&E,JIT-DVG 7
DATASTRUCTURE AND APPLICATIONS
Algorithm:
1. Start
2. Read pos.
3. Move the elements towards left
for(i=pos ; i< n-1; i++)
{
A[i] = A[i+1];
}
4. Display deleted element at the specified position
elem = a[pos];
5. Decrement the number of elements in the array
n=n-1;
6. Stop

Example: Let us consider an array, int A[5]={10,20,30,100,40,50};

i.e. A[0] A[1] A[2] A [3] A [4] A[5]
10 20 30 100 40 50

Let us consider an example of deleting an element 100 at position 3

i.e. ITEM=100 and K=3 and N=5
Iteration 1: i = 3, a[3] = a[4]

A [0] A [1] A [2] A [3] A [4] A [5]

10 20 30 40 40 50

Iteration 2: i = 4, a[4] = a[5]

A [0] A [1] A [2] A [3] A [4] A [5]
10 20 30 40 50 50

Dept. of CS&E,JIT-DVG 8
DATASTRUCTURE AND APPLICATIONS

Iteration 3: i = 5, i<4 condition failed

Iteration 4: decrement the number of elements in the array n=5

1.6 Two dimensional arrays (Multi-dimensional arrays)

 Arrays which are specified with 2 subscripts (2 set of square brackets [ ][ ]) are called 2-
dimensional arrays.
 Arrays with two or more dimensions are called Multi-dimensional arrays.
 In 2-Dimensional Array, the first index indicates the „row size‟( the number of rows) and second
index indicates the „column size‟( the number of columns).
Ex: int a[10][10]; //Two-dimensional array
int b[3][4][5]; //Three-dimensional array

Declaration of Two-dimensional arrays

 As we declare the variables before they are used in a program, an array must also be declared before it
is used using the following syntax.
Syntax:
data_type array_name [row_size][col_size];
data_type: It can be int, float, char etc.
array_name: It is the name of the array.
row_size: It is the number of rows in the array.
col_size: It is the number of columns in the array.

 The size used during declaration of the array is useful to reserve the specified memory locations.

Ex: int a [2][4]; a[0][0] a[0][1] a[0][2] a[0][3]

col_size Col.0 Col.1 Col.2 Col.3
Row 0
Data type row_size
Row 1
Array name a[1][0] a[1][1] a[1][2] a[1][3]

 The array „a‟ is a 2-dimensional array with 2 rows and 4 columns. This declaration informs the
compiler to reserve 8 locations (2*4=8 locations, 2*8=16 bytes in total) continuously one after the
other.

Initialization of 2-dimensional arrays

 As we initialize a variable to the required value, we can initialize the individual elements of the array
during initialization.
Syntax
data_type array_name[row_size][col_size]={
{a1,a2, ---- ,an},
{b1,b2, ----- ,bn},
……………...,
{z1,z2, ---- ,zn}
};

Dept. of CS&E,JIT-DVG 1
DATASTRUCTURE AND APPLICATIONS

data_type: It can be int, float, char etc.

array_name: It is the name of the array.
row_size: It is the number of rows in the array.
col_size: It is the number of columns in the array.
a1 to an are the values assigned to 1st row, b1 to bn are the values assigned to 2nd row and so on.
Ex: 1. int a[4][3]= {{11,22,33}, {44,55,66},{77,88,99},{10,20,30} };
The array has 4 rows and 3 columns.
Columns

0 1 2
0 11 22 33
1 44 55 66
Rows 2 77 88 99
3 10 20 30

1.6.2 Storage representation of 2-dimensional arrays

The elements in a 2-dimensional array can be stored using: 1. Row major order
2. Column major order
1. Row major order: the elements are stored row by row one row at a time.
Ex: int a[4][3] = {{11,22,33},{44,55,66},{77,88,99}};

A[0][0] A[0][1] A[0][2] A[1][0] A[1][1] A[1][2] A[2][0] A[2][1] A[2][2]

11 22 33 44 55 66 77 88 99

2000 2002 2004 2006 2008 2010 2012 2014 2016

| row 0 || row 1 || row 2 |

2. Column major order: the elements are stored column by column one column at a time.
Ex: int a[4][3] = {{11,22,33},{44,55,66},{77,88,99}};

A[0][0] A[0][1] A[0][2] A[1][0] A[1][1] A[1][2] A[2][0] A[2][1] A[2][2]

11 44 77 22 55 88 33 66 99

2000 2002 2004 2006 2008 2010 2012 2014 2016

| col 0 || col 1 || col 2 |

Dept. of CS&E,JIT-DVG 1
 DATASTRUCTURE AND APPLICATIONS

4.1 Structures
Structure is a user defined data type that can hold data items of same/different data
types. All data items grouped are logically related & can be accessed by using variables.

Declaration:
Syntax:
struct tag-name
{
data_type member 1;
data_type member 2;
………………………
………………………
data_type member n;
};

 In this declaration, struct is a required keyword, tag-name is a name of the structure defined.
 The individual members can be ordinary variables, pointers, arrays or other structures. The member
names within a particular structure must be distinct from one another.

Ex: struct person

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

 The above example declares a structure called person that has three fields:
name = a name that is a character array
age = an integer value representing the age of the person
salary = a float value representing the salary of the individual

Ex:
Struct student
{
char name[10]; 10 bytes
int roll_no; 4 bytes
float marks; 8 bytes
}; 22 bytes

 To allocate the memory for the structure, we have to declare the variable as shown below:
Struct student s1,s2; [ size of variables s1,s2 is 22bytes each]
Two ways to declare variables:

Dept. of CS&E,JIT-DVG 11
DATASTRUCTURE AND APPLICATIONS

Initialization or Assigning values to fields

 Initialization is the process of Assigning values to structure variables (structure members).
 To assign values to the fields, use .(dot operator) as the structure member operator. This operator is
used to select a particular member of the structure.
Ex: Method-1
struct person
{
char name[10];
int age;
float salary;
}p;
strcpy(p.name,“james”);
p.age = 10;
p.salary = 35000;
Method-2
struct student Struct student
{ {
char name[10]; char name[10];
introll_no;
int age;
floatmarks;
float marks; };
}s1={“virat”,19,25}; Struct student s1={“virat”,19,25};

Accessing structure members

 To access members of structures, we specify the variables followed by the dot operator then followed
by the name of the member.

printf(“Enter name of the student\n”);

Reading:
scanf(“%s”,s.name);
printf(“Enter marks of the student\n”);
Writing: scanf(“%f”,&s.marks);

printf(“name of the student is %s\n”,s.name);

printf(“marks of the student is %f\n”,s.marks);

Dept. of CS&E,JIT-DVG 12
DATASTRUCTURE AND APPLICATIONS

4.2 Structure within a structure:

 There is possibility to embed a structure within a structure. There are 2 ways to embed structure.
 1.The structures are defined separately and a variable of structure type is declared inside the definition
of another structure. The accessing of the variable of a structure type that are nested inside another
structure can be done in the same way as accessing other member of that structure.
Example: The following example shows two structures, where both the structure are defined
separately.
struct
struct
{
{ char name[10];
int month; int age;
int day; float salary;
int year; date dob;
}date; } humanBeing;
humanBeing person1;
A person born on February 11, 1944, would have the values for the date struct set as:
person1.dob.month = 2;
person1.dob.day = 11;
person1.dob.year = 1944;

2. The complete definition of a structure is placed inside the definition of another structure.
Example:
typedefstruct
{
char name[10];
int age;
float salary;
struct
{
int month;
int day;
int year;
} date;
} humanBeing;

4.3 Self-Referential Structures

A self-referential structure is the one in which one or more of its components is a
pointer to itself. Self-referential structures usually require dynamic storage management routines
(malloc and free) to explicitly obtain and release memory.
Consider as an example:
struct
{
char data;
Dept. of CS&E,JIT-DVG 13
 DATASTRUCTURE AND APPLICATIONS

struct list *link ;

} list;
 Each instance of the structure list will have two components data and link.
data: is a single character,
link: link is a pointer to a list structure. The value of link is either the address in memory of an
instance of list or the null pointer.

Consider these statements, which create three structures and assign values to their respective fields: list item1, item2, item3;
item1.data = 'a';
item2.data = 'b';
item3.data = 'c';
item1.link = item2.1ink = item3.link = NULL;

Structure variables item1, item2 and item3 each contain the data items a, b, and c respectively, and
the null pointer. These structures can be attached together by replacing the null link field in item 2
with one that points to item 3 and by replacing the null link field in item 1 with one that points to
item 2.
item1.link = &item2;
item2.1ink = &item3;

4.4 Unions
A union is a collection of data of similar data types or dissimilar data types. A union
declaration is similar to a structure, but the fields of a union must share their memory space. This
means that only one field of the union is "active" at any given time.
Syntax:
union tag-name
{
data_type member 1;
data_type member 2;
………………………
………………………
data_type member n;
};
Example:
unionstudent
{
char name[10];
intage;;
float salary;

Dept. of CS&E,JIT-DVG 14
DATASTRUCTURE AND APPLICATIONS
};
 The major difference between a union and a structure is that unlike structure members which are
stored in separate memory locations; all the members of union must share the same memory space.
This means that only one field of the union is "active" at any given time.

Example: C program to show how structure behaves

#include <stdio.h> void main()

struct student {
{ struct student s1;
int marks; s1.marks=29;
s1.grade= „A‟;
char grade; s1.percentage=99.5;
float percentage; printf(" Marks= %d \n", s1.marks);
}; printf(" Grade= %c \n", s1.grade);
OUTPUT: printf("Percentage = %c \n", s1.percentage);
Marks=29 }
Grade= A
Percentage =99.5
Example: C program to show how union behaves
#include <stdio.h>
union student void main()
{ {
union student s1;
int marks;
char grade; s1.marks=29;
float percentage; printf(" Marks= %d \n", s1.marks);
};
s1.grade=‟A‟;
printf(" Grade= %c \n", s1.grade);
OUTPUT:
s1.percentage=99.5;
Marks=29 printf("Percentage = %c \n", s1.percentage);
Grade= A }
Percentage =99.5

Differences between structure and union in C:

C Structure C Union
keyword struct is used to define a structure keyword union is used to define a union
Structure allocates storage space for all its Union allocates one common storage space for
members separately. all its members. Union finds that which of its
member needs high storage space over other
members and allocates that much space.

Dept. of CS&E,JIT-DVG 15
DATASTRUCTURE AND APPLICATIONS
Structure occupies larger memory space. Union occupies lower memory space over
structure.
We can access all members of structure at a time. We can access only one member of union at a
time.
Address of each member will be in ascending Address is same for all union members.
order (different address).

5. Pointers and Dynamic Memory Allocation Functions

5.1 Pointers
Pointer is the important feature available in C.
As we store data/information in memory, computer stores data in its memory.
1. Computer memory is divided into number of cells called memory locations.Each
locationholds 1byte of data.
2. Each location is associated with address. Address of memory location ranges from 0 to
65535.
3. We can‟t change these addresses assigned by the system & hence these are constant. But we
can only use them to store the data.
These addresses are called pointer constants.
Data
Address
0 10
1 20
2 30
3 40
4 50 Memory
5 … locations
... …
65534 …
65535 …

Definition
“A pointer is a variable which contains the address of another variable as its value”.

Declaring a Pointer Variable

Syntax
data_type *pointer_variable_name;
where,
data_type: It can be int, float, char etc.
Asterisk (*): It tells the compiler that we are declaring a pointer variable.
pointer_variable_name: It is the name of the pointer variable.

Example:
1. int *ptr; // declares a pointer variable ptr of integer type.
2. float *temp; // declares a pointer variable temp of floating type.

Dept. of CS&E,JIT-DVG 16
DATASTRUCTURE AND APPLICATIONS

Operators used with Pointers:

The two basic operators used with pointers are:
i. The Address of operator (&): By using the address of (&) operator, we can determine the
address of the variable.
ii. The Indirection operator (*): It gives the value stored at a particular address.
Example:

int a=3;
int *ptr;
ptr=&a;
ptr a
Memory layout:
65530 3
Address: 65530
 „ptr = &a‟ copies the address of „a‟ to the pointer variable „ptr‟.

Example Program: Write a C program to print value and address of the variable using
pointers.
#include<stdio.h>
#include<conio.h>
void main () Output:
{ The address of a=65530 and value of a=20
int a=20, *ptr1;
clrscr ();
ptr1 = &a; //ptr1 is a pointer to variable a
printf(“The address of a=%d and value of a=%d\n”,ptr1,*ptr1);
getch();
}
ptr1 a
Memory layout:
65530 20
Address: 65530

Dept. of CS&E,JIT-DVG 17
DATA STRUCTURES AND APPLICATIONS
Initializing a Pointer Variable
 We can initialize the pointer variables by assigning the address of other variable to them.
However these variables must be declared in the program.

Syntax
data_type *pointer_variable_name = address_of_variable;
where,
data_type:. It can be int, float, char etc.
Asterisk (*): It tells the compiler that we are declaring a pointer variable.
pointer_variable_name: It is the name of the pointer variable.
address_of_variable: It is the address of another variable.

Example:
1. int a;
int *ptr;
ptr=&a;
or
int a;
int *ptr=&a;
Both are equivalent.

5.2 Dynamic Memory Allocation Methods

 Memory can be reserved for the variables either during compilation time or during
execution time (run time).
 Based on this memory can be allocated for variables using two different techniques:
1. Static allocation
2. Dynamic allocation

Static Allocation
 If memory space is allocated for variables during compilation time, then it is called „Static
Memory allocation‟.
 Size of memory space is „fixed‟; it can‟t be altered during execution time.
Example: int a [10];
 During compilation, the compiler will allocate 10 memory locations for the array variable „a‟.
Inserting less than 10 elements leads to underutilization of allocated space and more than 10
elements cannot be inserted.

Dynamic Allocation
 “Dynamic memory allocation is the process of allocating memory space during the
execution time (Run time).”
 The various predefined memory management functions that are used to allocate or deallocate
memory are:
1. malloc( )
2. calloc( )
3. realloc( )
4. free( )
JIT, DAVANAGERE 1
DATA STRUCTURES AND APPLICATIONS

5.3 Different Dynamic Memory allocation Functions:

1. malloc( ): Allocating a Block of Memory
 This function reserves a block of memory of specified size and returns a pointer of data type to
that memory block.
 If there is insufficient memory to make the allocation, then it returns a NULL value.

Syntax:
ptr = (data_type *) malloc (size);
where,
ptr: ptr is a pointer variable of type int, float, char, double etc.
data_type: It can be any of the basic data type or user defined data type.
size: size is the number of bytes to be reserved for a block.

Example:
1. ptr = (int *) malloc(10);
 Allocates a block of Memory of 10 bytes.

2. ptr = (int *) malloc(20);

 Allocates a block of Memory of 20 bytes.

2. calloc( ): Allocating multiple Blocks of Memory

 This function allocates space for multiple Blocks, each of the same size and initializes all of its
bytes to zero (0).
 If there is insufficient memory to make the allocation, then it returns a NULL value.

Syntax:
ptr = (data_type *) calloc (n,size);
where,
ptr: ptr is a pointer variable of type int, float, char, double etc.
data_type: It can be any of the basic data type or user defined data type.
n: n is the number of blocks to be allocated.
size: size is the number of bytes in each block.

Example:
1. ptr = (int *) calloc(10, 2);
 Allocates 10 blocks of Memory each of 2 bytes.

2. ptr = (int *) calloc(5, 4);

 Allocates 5 blocks of Memory each of 4 bytes.

3. realloc( ): Reallocating already allocated block of Memory by malloc( ) or calloc( )

 This function reallocates memory space by modifying already allocated memory.
 The function relloc() resizes memory previously allocated by either malloc() or calloc(), which

JIT, DAVANAGERE 2
DATA STRUCTURES AND APPLICATIONS
means, the size of the memory changes by extending or deleting the allocated memory.
 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 the function returns the value
NULL.

Syntax
ptr = (data_type *)realloc (ptr, new_size);

where,
ptr: it is a pointer to a block of previously allocated memory either using malloc( ) or calloc( ).
data_type: It can be any of the basic data type or user defined data type.
new_size: it is the new size of the block.

Example:
char *str;
str = (char *) malloc(10); // malloc function allocates 10 memory blocks
strcpy(str, “Computer”);
str = (char *) realloc (str, 40); //realloc function allocates new memory blocks from 10 to 40
strcpy(str, “Computer Science and Engineering”);

4. free( ): Freeing the memory allocated using malloc( ), calloc( ) or realloc( )

 This function is used to free the previously allocated memory using malloc( ), calloc( ) or
realloc( ).
Syntax
free(ptr);

Ex:int *ptr;
ptr = (int *) malloc(100*sizeof(int));
free(ptr);

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, memory is
allocated while writing the C program. allocated while executing the program.
Compile time allocation. Run time allocation.
Memory size can‟t be modified while Memory size can be modified while
execution. execution.
Example: Array Example: Linked list

JIT, DAVANAGERE 3
 DATA STRUCTURES AND APPLICATIONS
Difference between malloc() and calloc() Functions in C:
malloc() calloc()
It allocates only single block of memory. It allocates multiple blocks of memory.
int *ptr; int *ptr;
ptr = malloc( 20 * sizeof(int)); ptr = calloc( 20, 20 *sizeof(int) );
For the above, 20*4 bytes of memory are For the above, 20blocks of memory will be
allocated in one block.Total = 80 bytes allocated and each contains20*4 bytes of
memory.Total = 1600 bytes.
malloc() doesn‟t initializes the allocated calloc() initializes the allocated memory to
memory. It contains garbage values zero.

*REFER CLASS NOTES FOR PROGRAMS AND EXAMPLES

ASSIGNMENT QUESTIONS

1 Define Data structures. Classify the data structures.

2 List & explain the operations of data structures.
3 What is array? How arrays are declared and initialized in C.
4 Define structure? Explain how structures are declared and initialized.
5 Write a note on structure with in structures with an example.
6 What are self-referential structures? Explain with example.
7 Write a C program with an appropriate structure definition & variable declaration to read & display
information about 5 employees using nested structures. Consider the following fields like
Ename,Empid,DOJ(Date,Month,Year) & Salary(Basic,DA,HRA).

8 Define union. Explain how unions are declared and initialized.

9 Differentiate between unions & structures.
10 Define pointer. What are the advantages & Disadvantages of using pointers?
11 Define dynamic memory allocation. List and explain the functions supported in C for dynamic memory
allocation with examples.
12 Explain the representation of multidimensional arrays.
13 Explain the operations of array with example.

JIT, DAVANAGERE 4
DATA STRUCTURES AND APPLICATIONS

JIT, DAVANAGERE