DATA STRUCTURE

UNIT-1
Syllabus:
1. Introduction to data structures: Definition; Types of data structures - Primitive & Non
primitive, Linear and Non-linear ; Operations on data structures.
Dynamic memory allocation: Static & Dynamic memory allocation; Memory
allocation and de-allocation functions - malloc, calloc, realloc and free.
Algorithm Specification, Performance Analysis, Performance Measurement
Recursion: Definition; Types of recursions; Recursion Technique Examples - GCD, Towers of
Hanoi ;Binomial coefficient –Pascal triangle ; Comparison between iterative and
recursive functions.
2. Arrays: Basic Concepts – Definition, Declaration, Initialisation, Operations on
arrays; Types of arrays; Arrays as abstract data types (ADT); Representation of
Linear Arrays in memory.

Chapter-1
Definition of Data structures (DS) :
 A data structure is a storage that is used to store and organize data. It is a way of arranging
data on a computer so that it can be accessed and updated efficiently.
 A data structure is not only used for organizing the data. It is also used for processing,
retrieving, and storing data. There are different basic and advanced types of data structures
that are used in almost every program or software system that has been developed.

Types of Data structures

Chandana S, Asst Prof,GSSS-SSFGC, Mysore

1. Primitive Data Structures
1. Primitive Data Structures are the data structures consisting of the numbers and the
characters that come in-built into programs.
2. These data structures can be manipulated or operated directly by machine-level
instructions.
3. Basic data types like Integer, Float, Character, Boolean and Pointer come under the
Primitive Data Structures.
4. These data types are also called Simple data types, as they contain characters that can't be
divided further

Integer : Used to store whole numbers, such as 1, 2, 3, etc. In most programming

languages, integers have a fixed range of values they can hold, typically between 231 and
231-1 or between 263 and 263-1, depending on the language and system architecture.

Floating-point : a storage unit for decimal numbers like 1.5, 2.3, etc. Mantissa (the
significant digits) and exponent (the power of 10) together make up the representation of
floating-point numbers. Due to limitations in precision, floating-point calculations can
sometimes produce unexpected results.

Character : Used to store a single character, such as 'a', 'b', 'c', etc. Characters are
represented using a specific encoding, such as ASCII or Unicode, which assigns each
character a unique numerical value.

Boolean : Used to store true/false values, such as true or false. Boolean variables are often
used to represent logical conditions in programs, such as whether a statement is true or
false.

Pointer (links): Pointer is a reference to a data structure pointer is a data type which
stores the address of the other data items or the address of the memory location

2.Non-Primitive Data Structures

1. Non-Primitive Data Structures are those data structures derived from Primitive Data
Structures.
2. These data structures can't be manipulated or operated directly by machine-level
instructions.
3. Based on the structure and arrangement of
4. data, we can divide these data structures into two sub-categories -

Chandana S, Asst Prof,GSSS-SSFGC, Mysore

 a. Linear Data Structures
b. Non-Linear Data Structures

Primitive data structure Non-primitive data structure

Primitive data structure is a kind of data Non-primitive data structure is a type of
structure that stores the data of only one data structure that can store the data of more
type. than one type.
Examples of primitive data structure are Examples of non-primitive data structure
integer, character, float. are Array, Linked list, stack,etc
Primitive data structure will contain some Non-primitive data structure can consist of
value, i.e., it cannot be NULL. a NULL value.
The size depends on the type of the data In case of non-primitive data structure, size
structure. is not fixed.
It starts with a lowercase character. It starts with an uppercase character.
Primitive data structure can be used to call Non-primitive data structure cannot be used
the methods. to call the methods.

1. Linear Data Structures are a type of data structure in computer science where data
elements are arranged sequentially or linearly. Each element has a previous and next adjacent,
except for the first and last elements.

There are four types of linear data structures:

1.Array: An array is a collection of the same data types stored at contiguous memory
locations.
2. Linked list: A linked list is a linear data structure in which elements are linked using
pointers. It consists of nodes where each node contains a data field and a
reference(link) to the next node in the list.
3. Stack: A stack is a linear data structure that stores data elements in a Last-In/First
Out (LIFO). Here, a new element is added at one end and an element is
removed from that end only.
4. Queue: A queue is a linear data structure that stores data elements in First-In/First
Out(FIFO) manner, i.e., the element that’s inserted first will be removed first.

2. Non-Linear Data Structures is another important type in which data elements are
not arranged sequentially; mainly, data elements are arranged in random order without
forming a linear structure.
Chandana S, Asst Prof,GSSS-SSFGC, Mysore
Data elements are present at the multilevel, for example, tree.
There are Two types of Non-linear data structures:

1.Tree

o The tree is a non-linear data structure that is comprised of various nodes. The nodes in the
tree data structure are arranged in hierarchical order.
o It consists of a root node corresponding to its various child nodes, present at the next level.
The tree grows on a level basis, and root nodes have limited child nodes depending on the
order of the tree.
o For example, in the binary tree, the order of the root node is 2, which means it can have at
most 2 children per node, not more than it.
o The non-linear data structure cannot be implemented directly, and it is implemented using
the linear data structure like an array and linked list.
o The tree itself is a very broad data structure and is divided into various categories
like Binary tree, Binary search tree, AVL trees, Heap, max Heap, min-heap, etc.
2.Graph
o A graph is a non-linear data structure with a finite number of vertices and edges, and these
edges are used to connect the vertices.
o The graph itself is categorized based on some properties; if we talk about a complete
graph, it consists of the vertex set, and each vertex is connected to the other vertexes
having an edge between them.
o The vertices store the data elements, while the edges represent the relationship between
the vertices.
o Even in Maps, we consider every location a vertex, and the path derived between two
locations is considered edges.
o The graph representation's main motive is to find the minimum distance between two
vertexes via a minimum edge weight.

Linear Data Structure Non-linear Data Structure

data elements are arranged in a linear order data elements are attached in hierarchically
where each and every element is attached to manner.
its previous and next adjacent.
single level is involved. multiple levels are involved.
Its implementation is easy its implementation is complex
data elements can be traversed in a single run data elements can’t be traversed in a single run
only. only.

Chandana S, Asst Prof,GSSS-SSFGC, Mysore

memory is not utilized in an efficient way. memory is utilized in an efficient way.

ex : array, stack, queue, linked list, etc. Ex: trees and graphs.
Applications of linear data structures are Applications of non-linear data structures are in
mainly in application software development. Artificial Intelligence and image processing.

Operations on Data Structures

Design of efficient data structure must take operations to be performed on the data structures
into account. The most commonly used operations on data structure are broadly categorized
into following types.
1. Create: The create operation results in reserving memory for program elements.
This can be done by declaration statement. Creation of data structure may take
place either during compile-time or run-time. Malloc() function of C language is
used for creation.
2. Destroy: Destroy operation destroys memory space allocated for specified data
structure. Free() function of C language is used to destroy data structure.
3. Selection: Selection operation deals with accessing a particular data within a data
structure.
4. Update: It updates or modifies the data in the data structure.
5. Searching: It finds the presence of desired data item in the list of data items, it may
also find the locations of all elements that satisfy certain conditions.
6. Sorting: Sorting is a process of arranging all data items in a data structure in a
particular order, say for example, either in ascending order or in descending order.
7. Merging: Merging is a process of combining the data items of two different sorted
list into a single sorted list.
8. Splitting: Splitting is a process of partitioning single list to multiple list.
9. Traversal: Traversal is a process of visiting each and every node of a list in
systematic manner

Memory Allocations in Data Structures

Memory allocation is the process of setting aside sections of memory in a program to be
used to store variables, and instances of structures and classes. or
Memory allocation in data structures refers to the process of reserving and managing memory
space for storing data elements within the data structure.
There are two types of memory allocations possible in C:
1. Compile-time or Static allocation.
2. Run-time or Dynamic allocation (using pointers)
Chandana S, Asst Prof,GSSS-SSFGC, Mysore
1. Compile-time or Static Memory allocation
o Static memory allocation allocated by the compiler. Exact size and type of memory
must be known at compile time.
o In this approach, memory is allocated at compile time.
o The size of the data structure is fixed and known in advance.
o Arrays are a classic example of statically allocated data structures.
o The main advantage is fast access, but the downside is inflexibility, as the size cannot be
changed at runtime.

Ex: // Static allocation of an array of integers with size 5 //

#include <stdio.h>
int main()
{
int arr[5]; // Initializing the array elements
arr[0] = 10;
arr[1] = 20;
arr[2] = 30;
arr[3] = 40;
arr[4] = 50;
printf("Array elements: "); // Accessing and printing array elements
for (int i = 0; i < 5; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
In this example, an array arr of integers with size 5 is statically allocated. The size of the array is
determined at compile time, and memory is allocated accordingly. Elements of the array are
accessed using index notation (arr[0], arr[1], etc.), and values are assigned to them.

Note:
Static memory allocation is fast and efficient but lacks flexibility since the size of the array
cannot be changed at runtime. Once the array is allocated, its size remains fixed throughout the
program execution

2. Run-Time or Dynamic Memory Allocation

o Memory is allocated at runtime from the heap.

o This allows for flexibility in terms of size, as memory can be allocated and deallocated as
Chandana S, Asst Prof,GSSS-SSFGC, Mysore
 needed during program execution.
o Examples of dynamically allocated data structures include linked lists, trees, and dynamic
arrays.
o managing dynamic memory can lead to issues like memory leaks and fragmentation.

Static Memory Allocation Dynamic Memory Allocation

variables get allocated permanently, till the variables get allocated only if your program
program executes or function call finishes. unit gets active.
Static Memory Allocation is done before Dynamic Memory Allocation is done during
program execution. program execution.
It uses stack for managing the static allocation It uses heap for managing the dynamic
of memory allocation of memory
It is less efficient It is more efficient
there is no memory re-usability there is memory re-usability and memory can
be freed when not required
once the memory is allocated, the memory size when memory is allocated the memory size
can not change. can be changed.
In this memory allocation scheme, we cannot This allows reusing the memory. The user can
reuse the unused memory. allocate more memory when required. Also,
the user can release the memory when the
user needs it.
In this memory allocation scheme, execution is In this memory allocation scheme, execution
faster than dynamic memory allocation. is slower than static memory allocation.
In this memory is allocated at compile time. In this memory is allocated at run time.
In this allocated memory remains from start to In this allocated memory can be released at
end of the program. any time during the program.
Example: This static memory allocation is Example: This dynamic memory allocation is
generally used for array. generally used for linked list.

Memory allocation and de-allocation functions

 Malloc( )
 Calloc( )
 Realloc( )
 Free( )

Chandana S, Asst Prof,GSSS-SSFGC, Mysore

Memory allocation functions
malloc(): Allocates a block of memory of the specified size in bytes. It returns a pointer to the
beginning of the allocated memory block.
calloc(): Allocates a block of memory for an array of elements, each with the specified size in
bytes. It initializes all bytes of the allocated memory to zero. It returns a pointer to the beginning
of the allocated memory block.
realloc(): Changes the size of the previously allocated memory block pointed to by ptr to the
specified size in bytes. It returns a pointer to the beginning of the resized memory block. If ptr is
NULL, realloc() behaves like malloc()
Syntax: #include <stdlib.h>
void *malloc(size_t size);
void *calloc(size_t num, size_t size);
void *realloc(void *ptr, size_t size);

Memory deallocation function

free(): Deallocates the previously allocated memory block pointed to by ptr. It releases the
memory back to the system, making it available for future allocations.
Syntax:
#include <stdlib.h>
void free(void *ptr);

ex:
#include <stdlib.h>
int main()
{
int *ptr;
// Memory allocation
ptr = (int *)malloc(10 * sizeof(int)); // Allocate memory for 10 integers
// Memory deallocation
free(ptr); // Deallocate the allocated memory
return 0;
}

Algorithm Specification:
An algorithm is defined as a finite set of instructions that, if followed, performs a particular
task. All algorithms must satisfy the following criteria.

Chandana S, Asst Prof,GSSS-SSFGC, Mysore

  Input: An algorithm has zero or more inputs, taken or collected from a specified set of
objects.
 Output: An algorithm has one or more outputs having a specific relation to the inputs.
 Definiteness: Each step must be clearly defined; Each instruction must be clear and
unambiguous.
 Finiteness: The algorithm must always finish or terminate after a finite number of
steps.
 Effectiveness: All operations to be accomplished must be sufficiently basic that they
can be done exactly and in finite length
.
We can depict an algorithm in many ways.
 Natural language: Implement a natural language like English
 Flow charts: Graphic representations denoted flowcharts, only if the algorithm is
small and simple.
 Pseudo code: This pseudo code skips most issues of ambiguity; no particularity
regarding syntax programming language.

Performance Analysis and Performance Measurements

A. Performance Analysis (Algorithm Analysis): The algorithm can be analyzed in two

levels, i.e., first is before creating the algorithm, and second is after creating the
algorithm.
The following are the two analysis of an algorithm:
 Priori Analysis: Here, priori analysis is the theoretical analysis of an algorithm
which is done before implementing the algorithm.
Various factors can be considered before implementing the algorithm like processor speed,
which has no effect on the implementation part.
 Posterior Analysis: Here, posterior analysis is a practical analysis of an
algorithm. The practical analysis is achieved by implementing the algorithm using
any programming language. This analysis basically evaluate that how much
running time and space taken by the algorithm.

B. Performance Measurements (Algorithm Complexity): The performance of the

algorithm can be measured in two factors:
 Time complexity: The time complexity of an algorithm is the amount of time
required to complete the execution. The time complexity of an algorithm is
denoted by the big O notation. Here, big O notation is the asymptotic notation to
Chandana S, Asst Prof,GSSS-SSFGC, Mysore
represent the time complexity.
The time complexity is mainly calculated by counting the number of steps to finish the
execution.

Let's understand the time complexity through an example.

sum=0;
for i=1 to n
sum=sum+i;
return sum;

// Suppose we have to calculate the sum of n numbers.

// when the loop ends then sum holds the sum of the n numbers
In the above code, the time complexity of the loop statement will be atleast n, and if the value
of n increases, then the time complexity also increases. While the complexity of the code, i.e.,
return sum will be constant as its value is not dependent on the value of n and will provide
the result in one step only. We generally consider the worst-time complexity as it is the
maximum time taken for any given input size.

 Space complexity: An algorithm's space complexity is the amount of space/memory

required to solve a problem and produce an output. Similar to the time complexity, space
complexity is also expressed in big O notation.
For an algorithm, the space is required for the following purposes:
1. To store program instructions
2. To store constant values
3. To store variable values
4. To track the function calls, jumping statements, etc.

 Auxiliary space: The extra space required by the algorithm, excluding the input size, is
known as an auxiliary space. The space complexity considers both the spaces, i.e.,
auxiliary space, and space used by the input.
So, Space complexity = Auxiliary space + Input size.

Recursion in data structures

 When function is called within the same function, it is known as recursion in C. The
function which calls the same function, is known as recursive function.
 Recursion is defined as defining anything in terms of itself. Recursion is used to solve
problems involving iterations, in reverse order.
Chandana S, Asst Prof,GSSS-SSFGC, Mysore
Types of Recursion
1. Direct Recursion: In the direct recursion, functions call themselves. This kind of
operation consists of a single-stage recursive call by the function from within itself.
In direct recursion, a function calls itself directly.
Direct Recursion can be further divided into 5 types
a. Linear Recursion:
Linear recursion involves a function calling itself only once in each recursion step.
b. Binary Recursion:
Binary recursion involves a function calling itself twice in each recursion step. An example of
binary recursion is the computation of Fibonacci numbers.
void fun(int n) // Recursive function
{
if (n > 0)
{
printf("%d ", n);
fun(n - 1) + fun(n - 2); // function calls twice
}
}
int main()
{
fun(3);
return 0;
}

c. Tail Recursion: A recursive function is referred to as tail-recursive if the recursive call is the
end execution executed by the function.
Ex for tail and linear Recursion
#include <stdio.h>
void fun(int n) // Recursion function
{
if (n > 0)
{
printf("%d ", n);
fun(n - 1); // Last statement in the function and function calls once
}
}
int main() {
int x = 3;
fun(x);
return 0; }
Chandana S, Asst Prof,GSSS-SSFGC, Mysore
d. Tree Recursion
if a recursive function calling itself for more than one time then it’s known as Tree Recursion.
Ex:
void fun(int n) // Recursive function
{
if (n > 0) {
printf("%d ", n);
fun(n - 1); // Calling once
fun(n - 1); } // Calling twice

}
int main()
{
fun(3);
return 0;
}

Output: 3 2 1 1 2 1 1

e.Nested Recursion:
a recursive function will pass the parameter as a recursive call. That means “recursion inside
recursion” is called Nested Recurtion

2. Indirect Recursion: Indirect recursion involves two or more functions calling each other
in a circular manner, either directly or indiretly. Each function calls another function, which in
turn might call the first function or another one in the cycle. This creates a circular chain of
function calls.
Ex:
#include <stdio.h>
void fun1(int n); // Prototype of fun1
void fun2(int n); // Prototype of fun2
void fun1(int n) {
if (n > 0) {
printf("%d ", n);
fun2(n - 1); // Call fun2
}
}
void fun2(int n) {
if (n > 1) {
Chandana S, Asst Prof,GSSS-SSFGC, Mysore
 printf("%d ", n);
fun1(n / 2); // Call fun1
}
}
int main() {
fun1(10);
return 0;
}

Recursion Technique Examples

1. Program to find GCD using recursive function

#include<stdio.h>
#include<conio.h>
int gcd(int i, int j);
void main()
{
int a,b;
printf("Enter two integer numbers\n");
scanf("%d%d",&a,&b);
printf("GCD of %d and %d is %d\n",a,b,gcd(a,b));
getch();
}
int gcd(int i, int j)
{
if(j>i)
return gcd(j,i);
if(j==0)
return i;
else
return gcd(j,i%j); // recursive function
}

2. Program to display Pascal Triangle using binomial function.

Chandana S, Asst Prof,GSSS-SSFGC, Mysore
#include<stdio.h>
int main()
{
int n,row,a,i;
clrscr();
printf("Enter the number of rows: ");
scanf("%d",&n);
for(row=1; row<=n; row++)
{
a=1;
for(i=1; i<=row; i++)
printf("%d ",a);
a = a * (row-i)/i;
}
printf("\n");
}
getch();
return 0;
}

3. Program to generate n Fibonacci numbers using recursive function.

#include <stdio.h>
#include <conio.h>
int fibo(int n)
{
if(n == 0 || n== 1)
return n;
else
return fibo(n-1) + fibo(n-2); // recursive function.
}
int main(void)
{
int m,i;
clrscr();
printf("Enter n value:\n");
scanf("%d",&m);
printf("Fibonacci Sequence is as follows:\n");
Chandana S, Asst Prof,GSSS-SSFGC, Mysore
for(i = 0; i < m; i++)
printf("%d ", fibo(i));
getch();
return 0;
}

4. Write a C Program to implement Towers of Hanoi.

#include <stdio.h>
#include <conio.h>
void TOH (int n ,char A,char B,char C)
{
if(n>0)
{
TOH(n-1, A, C, B);
printf("Move disk %d from %c to %c\n", n, A, B);
TOH(n-1, C, B, A);
}
}
int main()
{
int n;
clrscr();
printf("How many disks?\n");
scanf("%d", &n);
TOH(n,'A','B','C');
getch();
return 0;
}

Iterative Functions
 Iterative functions are a type of function in programming where a set of instructions or
operations is repeated in a loop.
 The process of repeatedly applying the same function is called iteration.
 Iterative functions are functions that use iteration, typically in the form of loops, to repeat
a set of instructions until a specific condition is met. In other words, they involve a
repetitive process where a block of code is executed repeatedly until a certain condition is
satisfied.
Chandana S, Asst Prof,GSSS-SSFGC, Mysore
Comparison between iterative and recursive functions.

Aspect Iterative Functions Recursive Functions

Implementation Implemented using loops (e.g., for, Implemented using function calls
while)
Control Explicit control over iteration and Control relies on function call stack
termination and base cases
Readability Often more verbose and requires Can be more concise and expressive
manual tracking of state
Performance Generally more efficient for large May consume more memory due to
datasets function call overhead
Debugging Easier to debug due to May be trickier to debug due to stack-
straightforward flow of control based execution
Tail Recursion Not applicable Can be optimized with tail recursion
Optimization (if supported)
Stack Overflow Less likely to cause stack overflow More prone to stack overflow if base
for deep recursion cases aren't met
Calculating factorial using a loop Calculating factorial using recursive
calls
Examples Binary search implementation using Binary search implementation using
loops recursion
Finding the sum of elements in an Finding the sum of elements in an
array using a loop array using recursion

Questions
1. What is DS ? Explain Classifications (Types) of DS Briefly.
2. Explain Operations of DS.
3. Explain Memory allocation in DS.
4. Explain Memory allocation and De-allocation Functions.
5. Explain Algorithm Specification in detail.
6. What is Recursion ? Explain its Types.
7. What is Recursion ? Write a program to
i. Find GCD of 2 numbers,
ii. Find Towers of Hanoi,
iii. Draw Pascal triangle using Binomial coefficient,
iv. Generate Fibonacci series
8. Write Comparison between iterative and recursive functions

Chandana S, Asst Prof,GSSS-SSFGC, Mysore

 DATA STRUCTURE
UNIT-1(Chapter-2)

Syllabus:
Arrays: Basic Concepts – Definition, Declaration, Initialization, Operations on arrays;
Types of arrays; Arrays as abstract data types (ADT); Representation of Linear Arrays in
memory.

ARRAYS:
An array is a linear data structure that collects elements of the same data type and
stores them in contiguous and adjacent memory locations (OR)
An array is a type of linear D.S consisting of finite number of similar/homogeneous objects.
Here we can derive linear relationships between the elements because elements are arranged
one
after the other. (OR)
An array is an indexed collection of data elements of the same type.
1. Indexed means that the array elements are numbered (starting at 0).
2. The restriction of the same type is an important one, because arrays are stored in
consecutive memory cells. Every cell must be the same type (and therefore, the same size)

Declaration and Initialization of Array

There are various ways in which an array can be declared and initialized. We can declare
an array of any data type (i.e. int, float, double, char) in C. The following ways can be used
to declare and initialize an array in C.

1. Array Declaration by Specifying the Size

Arrays can be declared by specifying the size or the number of array elements. The size of
the array specifies the maximum number of elements that the array can hold.

Chandana S, Asst Prof,GSSS-SSFGC, Mysore

Datatype arrayname[size] ;
int my_array1[20];
char my_array2[5]; // declare an array by specifying user defined size.
int size = 20;
int my_array3[size];
When an array is declared without allocating any value, then it stores a garbage value. If
you access any uninitialized array value, then just like any uninitialized variable, it will give
you a garbage value.

2. Array Declaration by Initializing Elements

An array can be initialized at the time of its declaration. In this method of array declaration,
the compiler will allocate an array of size equal to the number of the array elements.
The following syntax can be used to declare and initialize an array at the same time.
Datatype array_name [ ] = {v1,v2,v3…..} ;
int my_array[] = {100, 200, 300, 400, 500} // initialize an array at the time of declaration.
In the above syntax, an array of 5 elements is created and even though the array size has not
been specified here, the compiler will allocate a size of 5 integer elements.
3. Array Declaration by Specifying the Size and Initializing Elements
An array can also be created by specifying the size and assigning array elements at the time
of declaration. This method of array creation is different from the previous one. Here, if the
number of initialized elements is less than the size of the array specified, then the rest of the
elements will automatically be initialized to 0 by the compiler.
See the following syntax to understand this.
Datatype array_name [Size] = {v1,v2,v3…..} ;
// declare an array by specifying size and initializing at the time of declaration
int my_array1[5] = {100, 200, 300, 400, 500};
int my_array2[5] = {100, 200, 300}; // my_array2 = {100, 200, 300, 0, 0}
In the above array syntax, my_array1 is an array of size 5 with all five elements initialized.
Whereas, my_array2 is an array of size 5 with only three of its elements initialized. The
remaining two elements of the second array will be initialized to 0 by the compiler.

Chandana S, Asst Prof,GSSS-SSFGC, Mysore

Types of an array

Two Dimensional Three Dimensional

Array Array

1. One / Single Dimensional Arrays(1D)

A one-dimensional array is one in which only one subscript specification is needed to
specify a particular element of the array.
A one-dimensional array is a list of related variables. Such lists are common in
programming.
One-dimensional array can be declared as follows :
Data_type array_name [size];
Ex : int a[10];
int ex[5] = { 10, 5, 15, 20, 25} ;
char word[10] = { 'h', 'e', 'l', 'l', 'o' } ;

2. Multi Dimensional Array

Multi-dimensional Arrays in C are those arrays that have more than one dimension. Some
of the popular multidimensional arrays are 2D arrays and 3D arrays. We can declare
arrays with more dimensions than 3d arrays but they are avoided as they get very complex
and occupy a large amount of space.

a. Two Dimensional Array (2D)

• Two dimensional arrays are also called table or matrix, two dimensional arrays have
two subscripts.
• Two dimensional array in which elements are stored column by column is called as
column major matrix.

Chandana S, Asst Prof,GSSS-SSFGC, Mysore

 • Two dimensional array in which elements are stored row by row is called as row
major matrix.
• First subscript denotes number of rows and second subscript denotes the number of
columns.

two-dimensional array can be declared as follows :

Data_type array_name [size1][size2];
Ex: int array[3][3] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 } ;

Here, size1: Size of the first dimension.

size2: Size of the second dimension.

b. Three Dimensional Array (3D)

A 3D array has exactly three dimensions. It can be visualized as a collection of 2D arrays
stacked on top of each other to create the third dimension.

three-dimensional array can be declared as follows :

Data_type array_name [size1] [size2] [size3] ;

Here, size1: Size of the first dimension.

size2: Size of the second dimension.
size3: Size of the third dimension.

OPERATION ON ARRAYS
There are a number of operations that can be performed on an array which are:
1. Traversal
2. Sorting
3. Insertion
4. Deletion
5. Searching
6. Merging
Traversal: Traversal means accessing each array element for a specific purpose, either
to perform an operation on them.
Sorting: It is a process of arranging the elements in the array.
Insertion: it is a process of adding a new element to the array in the specified location.
Deletion: it is a process of removing an element from the array from the specified
location.
Searching: it is a process of finding an element in an array
Merging: it is a process of combining the elements of two array

Chandana S, Asst Prof,GSSS-SSFGC, Mysore

Arrays as Abstract Data Types (ADT)
Abstract Data Type(ADT) is a data type, where only behavior is defined but not
implementation. Examples: Array, List, Queue, Stack, Tree are ADTs.
Array ADT means Representation of Data Using set of operations or functions of
array.
Representation of Data: C provides Array as a basic data structure. Representation of
data is defined by the language compiler itself.
But the operations on the data are not defined by the compiler. We have to implement or
provide the operations on Array data structure. So, data structure array and the set of
operations together we can call it as Abstract Data Type (ADT).
Operations / Functions on Array Data Structure:
We can perform more operations on the array data structure but the above are some basic
operations. Let we know some information about the functions
1. Display () – To Display the entire array on the screen.
2. Add(n) / Append(n) – To add a particular element on the end of the array.
3. Insert (index, n) – To add an element to a particular index.
4. Delete (index) – To delete an element with the help of an index in the given array.
5. Search (n) – To check whether the given element is present or not in an array.
6. Get (index) – It will return the element which presents on the given index.
7. Set (index, x) – It will change the element with the new element at a particular index.
8. Max () / Min () – These will return the max and min element in the given array.
9. Reverse () – It will reverse the order of elements in the given array.
10. Shift () / rotate() – It will shift the whole elements either on the left or right side by
the given Number.

Representation of Linear Arrays in memory.

What is Indexing
• Indexing is a process to get the location of an element in the array. So, when we
write num[0], it informs the compiler about the location of the first element.
• In C, array indexing is started from 0 for the first element. So, 0 will be passed with
subscripting operator [ ], to access the first element of the array.

Ex num[0] = 9; //it updates the value of first element

How to calculate the address of the 1D array

Address of A[i] = Base_Address + W(i – Lower_Bound)

Where Base Address is the address of the first element in an array.

W= is the weight (size) of a data type.
i = is the index of array element to be calculated.
Chandana S, Asst Prof,GSSS-SSFGC, Mysore
Lower-bound= is the index of the first element.

Ex: Given an array int marks[ ] = {99,67,78,56,88,90,34,85}, calculate the address of

marks[4]. if the base address is 1000 and word count is 2.
Solution :

Address of A[i] = Base Address + W(i - Lower_Bound)

Marks[4]=1000+2(4-0)
=1000+ 2(4)
= 1008
Memory representation for above problem

99 1000 A[0]
67 1002 A[1]
78 1004 A[2]
56 1006 A[3]
88 1008 A[4]
90 1010 A[5]
34 1012 A[6]
85 1014 A[7]

Chandana S, Asst Prof,GSSS-SSFGC, Mysore

 1

Unit2
Chapter1-ARRAYS
Traversing the elements in the array
Variables used:
1. i: Loop counter or counter variable for the for loop.
2. arr: Array name.
3. LB: Lower bound.[The index value or simply index of the first element of an array is called its
lower bound]
4. UB:Upper bound.[The index of the last element is called its upper bound ]

Algorithm for Traversing an Array:

Step 01: Start
Step 02: [Initialize counter variable. ] Set i=LB.
Step 03: Repeat for i= LB to UB.
Step 04: visit arr[i].
Step 05: increment i
Step 05: [End of loop.]
Step 06: Stop

Program

void main()
{
int i, n;
int arr[];
printf("Enter number of elements\n");
scanf("%d", &n);
printf("Enter the Numbers\n");
for (i = 0; i < n; i++)
scanf("%d", &arr[i]);
printf("Display the elements in the array\n”);
for (i = 0; i < n; i++)
printf("%d", arr[i]);

Chandana S, Asst Prof, GSSS-SSFGC Mysore

 2

Inserting the element into the array

Insert operation in Array or inserting elements in an Array simply means, Adding one or more
elements at specified index/indices to the existing elements of an array.

Variables used:
1. arr: Name of the array.
2. n: Size of the array(i.e.,total number of elements in the array)
3. i: Loop counter or counter variable for the for loop.
4. x:The data element to be inserted.
5. pos: The position where we wish to insert the element.

Algorithm to Insert an element in an Array:

Insert(a,n,pos)
Step 01:input pos,x.
Step02:[Initialize variables] Set n=n+1,i=n– 1,
Step03: Repeat Step 04 and 05 for i= n-1 to i>= pos
Step04:[Move ith element forward.]
Set arr[i+1]=arr[i]
Step 05:[Decrease counter.] Set i=i-1
Step 06:[End of loop.]
Step07:[Insert element.]
Set arr[pos-1]=x
Step08:Stop

Program

Void main()
{
int i,n,x,pos;
int arr[];
printf("Enter number of elements\n");
scanf("%d",&n);
printf("Enter the Numbers \n");
for(i= 0;i< n;i++)
scanf("%d",&arr[i]);
printf("The array elements before insertion operation:\n");
for(i=0;i<n;i++)
printf(“ %d\n", arr[i]);
printf("Enter the element to be inserted:");
scanf("%d",&x);
printf("Enter the position where you want to insert the element:");
Chandana S, Asst Prof, GSSS-SSFGC Mysore
 3

scanf("%d",&pos);
for(i=n-1;i>=pos;i--) // Starts with end
arr[i+1]=arr[i];
arr[pos-1]=x; // index value
printf("The array elements after insertion operation:\n");
for(i=0;i<n;i++)
printf("arr[%d]=%d\n",i,arr[i]);
}

Deleting the element from the array

Deletion operation in Array or deleting elements in an Array simply means, removing one or more
elements at specified index/indices from array.

Variables used:

1.arr: Name of the array.

2.N: Size of the array(i.e. total number of elements in the array)
3.i: Loop counter or counter variable for the for loop.
4.pos: The position where we wish to delete the element.

Algorithm to delete an element in an Array:

Delete(a,n,pos)
Step 01:input pos.
Step02:[Initialize variables]
Set n=ub, i=pos+1,
Step03:Repeat Step 04 and 05 for i=pos+1 to i<=n
Step04:[Move ith element backward.]
Set arr[i-1]=arr[i]
Step 05:[increase the counter.]Set i=i+1
Step 06:[End of loop.]
Step07: Set n=n-1;
Step08:Stop

Program

Void main()
{
int i,n,pos;
int arr[];
printf("Enter number of elements\n");
scanf("%d",&n);
printf("Enter the Numbers\n");
for(i= 0;i< n;i++)
Chandana S, Asst Prof, GSSS-SSFGC Mysore
 4

scanf("%d",&arr[i]);
printf("The array elements before deletion operation:\n");
for(i=0;i<n;i++)
printf(“ %d\n", arr[i]);
printf("Enter the position where you want to delete the element:");
scanf("%d",&pos);
for(i=pos+1;i<=n;i++)
arr[i-1]=arr[i];
n=n-1; printf("The array elements after deletion operation:\n");
for(i=0;i<n;i++)
printf("arr[%d]=%d\n",i,arr[i]);
}

Sorting
sorting refers to the process of arranging items in a specific order, typically ascending or
descending, according to a predefined criterion or key. Sorting is a fundamental operation in
various applications and algorithms because it facilitates efficient searching, retrieval, and analysis
of data.

Types of Sorting
1. Selection Sort
2. Bubble Sort
3. Insertion Sort
4. Quick Sort
5. Merge Sort

1. Selection Sort
The selection sort algorithm sorts an array by repeatedly finding the minimum element
(considering
ascending order) from unsorted part and putting it at the beginning. The algorithm maintains two
sub-arrays in a given array.
In every iteration of selection sort, the minimum element (considering ascending order) from the
unsorted subarray is picked and moved to the sorted subarray.

How selection sort works?

Lets consider the following array as an example: arr[] = {64, 25, 12, 22, 11}

First pass: For the first position in the sorted array, the whole array is traversed from index 0 to 4
sequentially. The first position where 64 is stored presently, after traversing whole array it is clear
that 11 is the lowest value.
64 25 12 22 11

Chandana S, Asst Prof, GSSS-SSFGC Mysore

 5

Thus, replace 64 with 11. After one iteration 11, which happens to be the least value in the array,
tends to appear in the first position of the sorted list.
11 25 12 22 64

Second Pass: For the second position, where 25 is present, again traverse the rest of the array in a
sequential manner.
11 25 12 22 64
After traversing, we found that 12 is the second lowest value in the array and it should appear at
the second place in the array, thus swap these values.
11 12 25 22 64

Third Pass: Now, for third place, where 25 is present again traverse the rest of the array and find
the third least value present in the array.
11 12 25 22 64
While traversing, 22 came out to be the third least value and it should appear at the third place in
the array, thus swap 22 with element present at third position.
11 12 22 25 64

Fourth pass: Similarly, for fourth position traverse the rest of the array and find the fourth least
element in the array
As 25 is the 4th lowest value hence, it will place at the fourth position.
11 12 22 25 64

Fifth Pass: At last the largest value present in the array automatically get placed at the last
position in the array
The resulted array is the sorted array.
11 12 22 25 64

Algorithm for Selection Sort:

Step1-start
Step 2-initialize counter variable i=0; j=i+1
Step 3 − Set min to the first location
Set min=0;
Step 4 − Search the minimum element in the array
a[i]>a[j]
Step 5 – swap the first location with the minimum value in the array
Swap a[i] with a[min]
Step 6 – assign the second element as min.
Set min=i+1
Step 7 − Repeat the steps 4 5 and 6 until we get a sorted array.
Step 8-stop

Program
Chandana S, Asst Prof, GSSS-SSFGC Mysore
 6

#include<stdio.h>
#include<conio.h>
void selection(int a[],int n)
{
int i,j,min,temp;
for(i=0;i<n-1;i++)
{
min=i; //assign min to point to 1st element in unsorted list
for(j=i+1;j<n;j++)
if(a[min]>a[j]) // if minimum element > nth element
min=j; // then re-assign min to point to nth element
temp=a[i]; // swap minimum element with 1st element in unsorted list
a[i]=a[min];
a[min]=temp;
}
}
int main()
{
int i,n,a[20];
clrscr();
printf("Enter the number of elements: \n");
scanf("%d",&n);
printf("Enter the elements: \n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
selection(a,n);
printf("Sorted list is as follows: \n");
for(i=0;i<n;i++)
printf("%d\n",a[i]);
getch();
return 0;
}

Time complexity of selection sort

• Best Time Complexity: O(n^2)
• Average Time Complexity: O(n^2)
• Worst Time Complexity: O(n^2)
• Best Space Complexity: O(1)

2. Bubble Sort
Bubble sort is one of the easiest sorting techniques in programming and it is very simple to

Chandana S, Asst Prof, GSSS-SSFGC Mysore

 7

implement. It just simply compares the current element with the next element and swaps it, if it
is greater or less, depending on the condition. It gives quite accurate results. Each time an
element is compared with all other elements till it’s final place is found is called a pass.

Bubble sort gets its name because it filters out the elements at the top of the array like bubbles
on water.

How Bubble Sort Works?

We take an unsorted array for our example. Bubble sort takes Ο(n2) time so we're keeping it
short and precise.

First Pass:
Bubble sort starts with very first two elements, comparing them to check which one is greater.
( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps 5>1
( 1 5 4 2 8 ) –> ( 1 4 5 2 8 ), Swap since 5 > 4
( 1 4 5 2 8 ) –> ( 1 4 2 5 8 ), Swap since 5 > 2
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm
does not swap them.

Second Pass:
Now, during second iteration it should look like this:
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ) No change.
( 1 4 2 5 8 ) –> ( 1 2 4 5 8 ), Swap since 4 > 2
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) No change.
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) No change.

Third Pass:
Now, the array is already sorted, but our algorithm does not know if it is completed.
The algorithm needs one whole pass without any swap to know it is sorted.
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) No change
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) No change
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) No change
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) No change

Bubble sort algorithm

Step 1- Start
Step 2- start with the first element
Set i=0
Step3- Compare the current element with the next element.
a[i]>a[i+1]
Step 4- If current element is greater than the next element swap both elements.
Swap a[i] and a[i+1]
Step 5- Repeat the steps 2-4 until we get sorted array
Step 6- Stop
Chandana S, Asst Prof, GSSS-SSFGC Mysore
 8

Program

#include<stdio.h>
#include<conio.h>
void bubblesort(int a[],int n)
{
int i,j,temp;
for(i=0;i<n;i++)
{
for(j=0;j<n-i-1;j++)
{
if(a[j]>a[j+1]) // if nth element > (n+1)th element then swap them
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
}
int main()
{
int i,n,a[20];
clrscr();
printf("Enter the number of elements: \n");
scanf("%d",&n);
printf("Enter the elements: \n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
bubblesort(a,n);
printf("Sorted list is as follows: \n");
for(i=0;i<n;i++)
printf("%d\n",a[i]);
getch();
return 0;
}

• Best Time Complexity: O(n)

• Average Time Complexity: O(n^2)
Chandana S, Asst Prof, GSSS-SSFGC Mysore
 9

• Worst Time Complexity: O(n^2)

• Best Space Complexity: O(1)

3. Insertion Sort
Insertion sorts works by taking elements from the list one by one and inserting them in their
correct position into a new sorted list. The simple steps of achieving the insertion sort are
listed as follows - If the element is the first element, assume that it is already sorted. Return
1. Pick the next element, and store it separately in a key. Now, compare the key with all
elements in the sorted array
If the element in the sorted array is smaller than the current element, then move to the next
element. Else, shift greater elements in the array towards the right. Insert the value. Repeat
until the array is sorted. Insertion sort consists of N - 1 passes, where N is the number of
elements to be sorted.
Working of insertion sort
Consider an example: arr[]: {12, 11, 13, 5, 6}
12 11 13 5 6

First Pass:
Initially, the first two elements of the array are compared in insertion sort.
12 11 13 5 6
Here, 12 is greater than 11 hence they are not in the ascending order and 12 is not at its
correct position. Thus, swap 11 and 12.
So, for now 11 is stored in a sorted sub-array.
11 12 13 5 6

Second Pass:
Now, move to the next two elements and compare them
11 12 13 5 6
Here, 13 is greater than 12, thus both elements seems to be in ascending order, hence, no
swapping will occur. 12 also stored in a sorted sub-array along with 11

Third Pass:
Now, two elements are present in the sorted sub-array which are 11 and 12
Moving forward to the next two elements which are 13 and 5
11 12 13 5 6
Both 5 and 13 are not present at their correct place so swap them
11 12 5 13 6
After swapping, elements 12 and 5 are not sorted, thus swap again
11 5 12 13 6
Here, again 11 and 5 are not sorted, hence swap again
5 11 12 13 6
Here, 5 is at its correct position

Fourth Pass:
Chandana S, Asst Prof, GSSS-SSFGC Mysore
 10

Now, the elements which are present in the sorted sub-array are 5, 11 and 12
Moving to the next two elements 13 and 6
5 11 12 13 6
Clearly, they are not sorted, thus perform swap between both
5 11 12 6 13
Now, 6 is smaller than 12, hence, swap again
5 11 6 12 13
Here, also swapping makes 11 and 6 unsorted hence, swap again
5 6 11 12 13
Finally, the array is completely sorted.

Algorithm
Step 1- initialize the variable
Set i =1
Step 2- repeat step 3,4,7 till i<n
Step 3- set temp=a[i] and j=i-1
Step 4- repeat steps 5 and 6 till
Temp<a[j] && j>=0
Step 5-set a[j+1]=a[j]
Step 6- decrement j
Set j=j-1
Step 7- a[j+1]=temp
Step 8- increment i
Step 9- end

Program
#include <stdio.h>
#include <conio.h>
void insertion(int a[],int n)
{
int i,j,temp;
for(i=1;i<n;i++)
{
temp=a[i]; //temp is index to nth element
j=i-1; //j is index to (n-1)th element
while((temp<a[j])&&(j>=0)) //check if nth element < (n-1)th element
{
a[j+1]=a[j]; //if yes, insert (n-1)th element into nth position
j=j-1;
}
a[j+1]=temp; // insert nth element into vacant position
Chandana S, Asst Prof, GSSS-SSFGC Mysore
 11

}
}
int main()
{
int i,j,n,temp,a[10];
clrscr();
printf("Enter the number of elements: \n");
scanf("%d",&n);
printf("Enter the elements: \n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
insertion(a,n);
printf("Sorted list is as follows:");
for(i=0;i<n;i++)
printf("\n%d",a[i]);
getch();
return 0;
}

• worst case analysis-o(n2)

• best case analysis-o(n)
• average case analysis-o(n2)

Limitations Of Insertion Sort:

* It is relatively efficient for small lists and mostly-sorted lists.
* It is expensive because of shifting all following elements one by one.

4. Quick Sort
Quick sort is a highly efficient sorting algorithm and is based on partitioning of array of
data into smaller arrays.
A large array is partitioned into two arrays one of which holds values smaller than the
specified value, say pivot, based on which the partition is made and another array holds
values greater than the pivot value.
Quicksort partitions an array and then calls itself recursively twice to sort the two resulting
subarrays.
This algorithm is quite efficient for large-sized data sets as its average and worst-case
complexity are O(n2 ), respectively. Partition in Quick Sort The pivot value divides the list
into two parts. And recursively, we find the pivot for each sub-lists until all lists contains
only one element.

Chandana S, Asst Prof, GSSS-SSFGC Mysore

 12

working

Chandana S, Asst Prof, GSSS-SSFGC Mysore

 13

Algorithm

If low<high
{
Mid=partition (a,low,high)
Quicksort (a,low,mid-1)
Quicksort (a,mid+1,high)
}
Partition (a.low,high)
Step1-initialize the variable
Set i =low-1, pivot=a[high]
Step2-repeat step 3,4,7 till j<high
Step3-if a[i]<=pivot do step 5,6
Step4-increment i
Step 5-Swap(a[i],a[j])
Step 6-increment j
Set j=j+1
Step 7-swap a[i+1],a[j]
Step 8–return i+1
Step 9-end

Program

#include <stdio.h>
#include <conio.h>
int partition(int a[],int low,int high)
{
int pivot,i,j,temp;
pivot=a[high];
i=low-1;
for(j=low;j<high;j++) //j is index to nth element
{
if(a[j]<=pivot) //if nth element < pivot
{
i++; // then place nth element on leftside of pivot
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
temp=a[i+1];
Chandana S, Asst Prof, GSSS-SSFGC Mysore
 14

a[i+1]=a[j];
a[j]=temp;
return(i+1);
}
void quicksort(int a[],int low,int high)
{
int mid;
if(low<high)
{
mid=partition(a,low,high);
quicksort(a,low, mid-1);
quicksort(a, mid+1,high);
}
}
int main()
{
int i,n,a[20];
clrscr();
printf("Enter the number of elements: \n");
scanf("%d",&n);
printf("Enter the elements: \n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
quicksort(a,0,n-1);
printf("Sorted list is as follows: \n");
for(i=0;i<n;i++)
printf("%d\n",a[i]);
getch();
return 0;
}

Quick Sort is useful for sorting arrays.

• In efficient implementations Quick Sort is not a stable sort, meaning that the relative order
of equal sort items is not preserved.
• Overall time complexity of Quick Sort is O(nLogn). In the worst case, it makes O(n2)
comparisons, though this behavior is rare.
• The space complexity of Quick Sort is O(nLogn). It is an in-place sort (i.e. it doesn’t
require any extra storage)
Chandana S, Asst Prof, GSSS-SSFGC Mysore
 15

5. Merge Sort
Merge sort is a comparison based sorting algorithm. It is based on divide and conquer rule. In
this algorithm we divide the array into equal halves first and then combines them in a sorted
manner. This sorting algorithm suffers from space complexity but is it a stable algorithm
because it preserves the input order of equal elements in the sorted output.

It is most respected and trusted sorting algorithm because of its time complexity in worst-case
being Ο(nlogn).

Working

Algorithm

MERGE_SORT(arr, beg, end)

if low < high

set mid = (low + high)/2
MERGE_SORT(arr, low, high)
MERGE_SORT(arr, mid + 1, high)
MERGE (arr, low, mid, high)
end of if
END MERGE_SORT

Chandana S, Asst Prof, GSSS-SSFGC Mysore

 16

Program

#include<stdio.h>
#include<conio.h>
void merge(int a[],int low1,int high1,int low2,int high2)
{ int temp[20];
int i,j,k;
i=low1; //i points to first element in first list
j=low2; //j points to first element in second list
k=0; //k points to first element in new list ie temp[20]
while(i<=high1 && j<=high2)
{
if(a[i]<a[j])
temp[k++]=a[i++];
else
temp[k++]=a[j++];
}
while(i<=high1)
{
temp[k++]=a[i++];
}
while(j<=high2)
{
temp[k++]=a[j++];
}
for(i=low1,j=0;i<=high2;i++,j++)
a[i]=temp[j];
}
void mergesort(int a[],int low,int high)
{ int mid;
if(low<high)
{
mid=(low+high)/2;
mergesort(a,low,mid);
mergesort(a,mid+1,high);
merge(a,low,mid,mid+1,high);
}
}
int main()
Chandana S, Asst Prof, GSSS-SSFGC Mysore
 17

{
int i,n,a[20];
clrscr();
printf("Enter the number of elements: \n");
scanf("%d",&n);
printf("Enter the elements: \n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
mergesort(a,0,n-1);
printf("Sorted list is as follows: \n");
for(i=0;i<n;i++)
printf("%d\n",a[i]);
getch();
return 0;
}

Searching
Searching is the process of fetching a specific element in a collection of elements. The
collection can be an array or a linked list. If you find the element in the list ,the process is
considered successful ,and it returns the location of that element. And in contrast, if you do not
find the element, it says the search unsuccessful.

Two prominent search strategies are extensively used to find a specific item on a list.
a) Linear Search
b) Binary Search

1. Linear Search Algorithm

Linear search, often known as sequential search, is the most basic search technique.
In this type of search, you go through the entire list and try to fetch a match for a single element. If
you find a match, then the address of the matching target element is returned.
On the other hand , if the element is not found ,then it returns a NULL value.

Working

Chandana S, Asst Prof, GSSS-SSFGC Mysore

 18

Algorithm
Step1: set i=0
Step2: if i >=n go to step 7
Step3: If a[i]==key go to step 7
Step4: increment i ( i=i+1)
Step5: go to step 2
Step6: print element x found at position i+1;
Step7: print element not found.
Step8: Stop

Program

#include <stdio.h>
#include<conio.h>
int linear(int a[], int key, int n)
{
int i;
for (i = 0; i < n ; i++)
{
if (key == a[i] )
return 1;
}
return -1;
}
int main()
{
int a[10];
int i, n, key, found = -1;
clrscr();
printf("Enter number of elements: \n");
scanf("%d", &n);
printf("Enter the elements: \n");
for (i = 0; i < n; i++)
scanf("%d", &a[i]);
printf("Enter the element to be searched \n");
scanf("%d", &key);
found=linear(a,key,n);
if (found == -1)
printf("Element is not present in the array\n");
else
printf("Element is present in the array);
getch();
return 0;
}
Chandana S, Asst Prof, GSSS-SSFGC Mysore
 19

2. Binary Search Algorithm

Binary search is the search technique that works efficiently on sorted lists. Hence, to search
an element into some list using the binary search technique, we must ensure that the list is
sorted. or
Binary Search is a searching algorithm used in a sorted array by repeatedly dividing the
search interval in half and the correct interval to find is decided based on the searched value
and the mid value of the interval.

Algorithm
Step1: if high>=low
low=lower bound and high=upper bound
Step2: find the middle element
mid=(low+high)/2
Step3: compare the element to be searched with the element in the middle[mid] of the array.
If a[mid]==key
return the index of the middle element.
return mid Print element found at position mid+1
Step4 : If we do not get a match, we check whether the element to be searched is greater
than middle element.
Step 5: If a[mid]>key
Call binary_search(a,key,low,mid-1)
Else
Chandana S, Asst Prof, GSSS-SSFGC Mysore
 20

Call binary_search(a,key,mid+1,high)
Step 6-Print element not found
Step 7- End

Program

#include <stdio.h>
#include<conio.h>
int binarySearch(int a[], int key, int low, int high)
{
if (high >= low)
{
int mid = low + (high - low) / 2;
if (a[mid] == key) // If found at mid, then return it
return mid;
if (a[mid] > key) // Search the left half
return binarySearch(a, key, low, mid - 1);
return binarySearch(a, key, mid + 1, high); // Search the right half
}
return -1;
}
int main()
{
int a[10];
int i, n, key, found=-1;
clrscr();
printf("Enter number of elements: \n");
scanf("%d", &n);
printf("Enter the elements: \n");
for (i = 0; i < n; i++)
scanf("%d", &a[i]);
printf("Enter the element to be searched \n");
scanf("%d", &key);
found = binarySearch(a, key, 0, n - 1);
if (found == -1)
printf("Element is not present in the array\n");
Chandana S ,Asst prof, GSSS-SSFGC Mysore
else
printf("Element is present in the array\n");
getch();
return 0;
}

Chandana S, Asst Prof, GSSS-SSFGC Mysore

 21

Iterative and Recursive searching-

The major difference between the iterative and recursive version of Binary Search is that
the recursive version has a space complexity of O(log N) while the iterative version has a
space complexity of O(1). Hence, even though recursive version may be easy to
implement, the iterative version is efficient.
What is Iteration Algorithm?
In the case of Iterative algorithms, a certain set of statements are repeated a certain
number of time.An Iterative algorithm will use looping statements such as for loop, while
loop or do-while loop to repeat the same steps number of time.

What is Recursive Algorithm?

Recursive algorithm, a function calls itself again and again till the base
condition(stopping condition) is satisfied.
Let us track the search space by using two index start and end.Initialy low=0 and high=n-
1(as initialy whole array is search space).At each step,we find mid value in the search
space and compare it with target value.There are three cases possible:

CASE1: If target is equal to middle,then return mid.

CASE2:If target is less than middle i.e target<A[mid],we discard all the elements in the
right search space including mid element.Now our new high would be mid-1 while 'low'
remains as it is.
CASE3:If the target element is greater than middle i.e target>A[mid],we discard all the
elements in the left search space including mid element.Now our new low would be
mid+1 while 'high' remains as it is.

Recursive binary searching

Step 1 –Start
Step 2- Binary search(num,key);
Step 3- If num does not match with key
Print “element not found
Step 4- if the middle element is greater than the search element
Call binary search for left half of array.
Step 5- if the middle element is smaller than the search element
Call binary search for right half of array.
Step 6-stop

#include<stdio.h> #include<stdlib.h>
Chandana S, Asst Prof, GSSS-SSFGC Mysore
 22

int binsearch(int[], int, int, int);

int main() { int n, i, key,
position; int low, high,
a[10];
printf("\nEnter the total number of elements");
scanf("%d", &num);
printf("\nEnter the elements of array :");
for (i = 0; i < num; i++) { scanf("%d",
&list[i]);
}

low = 0; high =
num - 1;
printf("\nEnter
element to be
searched : ");
scanf("%d", &key);
position = binsearch(list, key, low, high);
if (position != -1) {

printf("\nNumber present at %d", (position + 1));

exit(0)
} else
printf("\n The number is not present in the list");
return (0);
}

// Binary search function for binary search

int binsearch(int a[], int x, int low, int high) {

int mid; if (low > high)

return -1; mid = (low + high) /
2; if (x == a[mid]) { return
(mid); else if (x < a[mid]) {
binsearch(a, x, low, mid - 1); else
{
binsearch(a, x, mid + 1, high);
}
}

Chandana S, Asst Prof, GSSS-SSFGC Mysore

 23

Features of Binary Search

1. It is great to search through large sorted arrays.

2. It has a time complexity of O(log n) which is a very good time complexity. It has a
simple implementation.

Binary search is a fast search algorithm with run-time complexity of (log n). This search
algorithm works on the principle of divide and conquers. For this algorithm to work
properly, the data collection should be in the sorted form.
Binary search looks for a particular item by comparing the middle most item of the
collection. If a match occurs, then the index of item is returned. If the middle item is
greater than the item, then the item is searched in the sub-array to the left of the middle
item. Otherwise, the item is searched for in the sub-array to the right of the middle item.
This process continues on the sub- array as well until the size of the sub array reduces to
zero.

MULTI-DIMENSIONAL ARRAY- REPRESENTATION OF MULTI

DIMENTIONAL ARRAY

Row Major Ordering(RMO) in an array:-

Row major ordering assigns successive elements, moving across the rows and then
down the columns, to successive memory locations. In simple language, if the
elements of an array are being stored in Row-Wise fashion. This mapping is
demonstrated in the below figure: The formula to compute the Address (offset) for a
two-dimension row-major ordered array as:

Address of A[I][J] = Base Address + W * ( C * I + J)

Where Base Address is the address of the first element in an array.

W= is the weight (size) of a data type.
C= is Total No of Columns.
I= is the Row Number
J= is Column Number of an element whose address is to find out.

Chandana S, Asst Prof, GSSS-SSFGC Mysore

 24

Chandana S, Asst Prof, GSSS-SSFGC Mysore

 25

Column Major Ordering(CMO) in an array:

If the element of an array is being stored in Column Wise fashion then it is called
column-major ordering in an array. In row-major ordering, the rightmost index increased
the fastest as you moved through consecutive memory locations. In column-major
ordering, the leftmost index increases the fastest.
Pictorially, a column-major ordered array is organized as shown below

The formulae for computing the address of an array element when using column-major
ordering is very similar to that for row-major ordering. You simply reverse the indexes
and sizes in the computation:
For a two-dimensional column-major array:

Address of A[I][J] = Base Address + W * ( R * J + I)

Base Address is the address of the first element in an array

W= is the weight (size) of a data type.
R= is Total No of Rows.
I= is the Row Number
J= is Column Number of an element whose address is to find out.

Chandana S, Asst Prof, GSSS-SSFGC Mysore

 26

What is Sparse Matrix?

In computer programming, a matrix can be defined with a 2-dimensional array. Any
array with 'm' columns and 'n' rows represent a m X n matrix. There may be a situation in
which a matrix contains more number of ZERO values than NON-ZERO values. Such
matrix is known as sparse matrix.

Sparse matrix is a matrix which contains very few non-zero elements.

When a sparse matrix is represented with a 2-dimensional array, we waste a lot of space
to represent that matrix. For example, consider a matrix of size 100 X 100 containing
only 10 non-zero elements. In this matrix, only 10 spaces are filled with non-zero values
and remaining spaces of the matrix are filled with zero. That means, totally we allocate
100 X 100 X 2 = 20000 bytes of space to store this integer matrix. And to access these 10
non-zero elements we have to make scanning for 10000 times. To make it simple we use
the following sparse matrix representation.
Sparse Matrix Representations
A sparse matrix can be represented by using TWO representations, those are as follows...
• Triplet Representation (Array Representation)
• Linked Representation
Triplet Representation (Array Representation)
In this representation, we consider only non-zero values along with their row and column
index values. In this representation, the 0th row stores the total number of rows, total
number of columns and the total number of non-zero values in the sparse matrix.

Chandana S, Asst Prof, GSSS-SSFGC Mysore

 27

For example, consider a matrix of size 5 X 6 containing 6 number of non-zero values.

This matrix can be represented as shown in the image...

Sparse Matrix Triplet Representation

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

Linked Representation
In linked representation, we use a linked list data structure to represent a sparse matrix. In
this linked list, we use two different nodes namely header node and element node. Header
node consists of three fields and element node consists of five fields as shown in the
image...

Chandana S, Asst Prof, GSSS-SSFGC Mysore

 28

Questions
1. Explain Insertion, Deletion and Traversal of an array with algorithm and Example.
2. Explain sorting and its Types in Detail.
3. Explain Selection sorting with Algorithm and example (Program).
4. Explain Insertion sorting with Algorithm and example.
5. Explain Bubble sorting with Algorithm and example.
6. Explain Merge sorting with Algorithm and example.
7. Explain Quick sorting with Algorithm and example.
8. Explain Searching with Algorithm and example.
9. Explain Linear Searching with Algorithm and example.
10.Explain Binary Searching with Algorithm and example.
11.Explain Row and Column Major Ordering.
12.Explain Sparse Matrix.

Unit2
Chapter2 – STACKS
DEFINITION :
A stack is an ordered list in which insertions (pushes) and deletions (pops) are made at
one end called the top. or
A Stack is an ordered collection of data elements in which insertion of elements are
called Push and Deletion of element is called Pop

As shown in above figure, the elements are added in the stack in the order A, B, C, D, E,
then E is the first element that is deleted from the stack and the last element is deleted from stack
is A. Figure illustrates this sequence of operations.

Since the last element inserted into a stack is the first element removed, a stack is also known as a
Last-In-First-Out (LIFO) list. Or First-In-Last-Out (FILO)list

Chandana S, Asst Prof, GSSS-SSFGC Mysore

 29

A real-world stack allows operations at one end only. For example, we can place or
remove a card or plate from the top of the stack only. Likewise, Stack ADT allows all
data operations at one end only. At any given time, we can only access the top element of
a stack.
This feature makes it LIFO data structure. LIFO stands for Last-in-first-out. Here, the
element which is placed (inserted or added) last, is accessed first. In stack terminology,
insertion operation is called PUSH operation and removal operation is called POP
operation.

Stack Representation
The following diagram depicts a stack and its operations –

A stack can be implemented by means of Array, Structure, Pointer, and Linked List.
Stack can either be a fixed size one or it may have a sense of dynamic resizing. Here, we
are going to implement stack using arrays, which makes it a fixed size stack
implementation.

Chandana S, Asst Prof, GSSS-SSFGC Mysore

 30

Operations of stack
1. Creation : used to implement stack
Create stack( );
Declare array s(n)
Declare int Top=0

2. IsEmpty( ) : − check if stack is empty.

{
If top== -1 or 0 then
Say stack is empty
}

3. IsFull( ) : check if stack is full

{
If top== n-1 r n then
Say stack is full
}

4. Top( ) : get the top data element of the stack, without removing it.
{
Display s[top]
}

5. Push( ) : Pushing (storing/ Inserting) an element on the stack.

6. Pop( ) : Removing (deleting) an element from the stack.

Implementation of STACK
Stack can be implemented as
• Array
• Dynamic Array

1. Array implementation:
Declaration of stack:

struct Stack
{ int top;
unsigned capacity;

}typedef S

Chandana S, Asst Prof, GSSS-SSFGC Mysore

 31

Here the figure shows how the stack is allocated , the structure Stack is created which holds
3 data first is the top which is integer type and we may store -1 saying that stack is empty.
Second we have capacity of type unsigned integer and we assign capacity or size of array as
5, then we have pointer to the array which stores starting address or the base address of the
array.
2. Stack using Dynamic Array:
struct Stack *createStack(int cap)
{
struct Stack *stack; stack-
>capacity=cap; stack->top=-1;
malloc(sizeof(int)*capacity);
}

Algorithm
Push operation is used to insert an element into stack.
PUSH (STACK, TOP, ITEM) –Here STACK is an array name, TOP is the top most
element in the stack and ITEM is the data to be entered into the stack

Algorithm for PUSH( )

Input : S - Stack
E - Element
Output: S -Updated
Method : if (isfull(S)) then
Say overflow
Else
Top= Top+1
S[Top]= E
If ends
Algorithm ends
Chandana S, Asst Prof, GSSS-SSFGC Mysore
 32

Pop operation is used to remove an item from stack, first get the element and then
decrease TOP pointer. POP_STACK(STACK,TOP,ITEM)

Algorithm for POP( )

Input : S - Stack
Output: E - Element
Method : if (isempty(S)) then
Say underflow or stack is empty
Else
E =S[Top]
Top= Top-1
If ends
Algorithm ends

Implementation of Stack

#include<stdio.h>
#define SIZE 5
int s[SIZE],ch,n,top=-1,item,i;
void push()
{
if(top==SIZE-1)
printf("Stack Overflow \n");
else
{
printf("Enter a value to be pushed:");
scanf("%d",&item);
top=top+1;
s[top]=item;
}
}
void pop()
{
if(top==-1)
printf("Stack Empty\n");
else
{
printf("The popped element is %d \n",s[top]);
Chandana S, Asst Prof, GSSS-SSFGC Mysore
 33

top=top-1;
}
}
void display()
{
if(top==-1)
printf("Stack Empty\n");
else
{
printf("The elements in stack are as follows");
for(i=top; i>=0; i--)
printf("\n%d",s[i]);
}
}
int main()
{
clrscr();
while(1)
{
printf("\nSTACK MENU");
printf("\n 1.PUSH \n 2.POP \n 3.DISPLAY \n 4.EXIT");
printf("\nEnter the Choice:");
scanf("%d",&ch);
switch(ch)
{
case 1:push();
break;
case 2:pop();
break;
case 3:display();
break;
case 4:exit(0);
default: printf ("Invalid Choice\n");
}
}
}

Chandana S, Asst Prof, GSSS-SSFGC Mysore

 34

Applications of Stack
Recursion
Keeping track of function calls
Evaluation of expressions
Reversing characters
Servicing hardware interrupts
Solving combinatorial problems using backtracking

STACK APPLICATIONS
POLISH NOTATION
Expressions: It is sequence of operators and operands that reduces to a single value after
evaluation is called an expression.
X=a/b–c+d*e–a*c
In above expression contains operators (+, –, /, *) operands (a, b, c, d, e).
Expression can be represented in in different format such as

• Prefix Expression or Polish notation

• Infix Expression
• Postfix Expression or Reverse Polish notation
Infix Expression: In this expression, the binary operator is placed in-between the
operand. The expression can be parenthesized or un- parenthesized.
Example: A + B
Here, A & B are operands and + is operand

Prefix or Polish Expression: In this expression, the operator appears before its operand.
Example: + A B
Here, A & B are operands and + is operand

Postfix or Reverse Polish Expression: In this expression, the operator appears after its
operand.
Example: A B +
Here, A & B are operands and + is operand

Chandana S, Asst Prof, GSSS-SSFGC Mysore

 35

Precedence of the operators

The first problem with understanding the meaning of expressions and statements is
finding out the order in which the operations are performed.
Example: assume that a =4, b =c =2, d =e =3 in below

expression X = a / b – c + d * e – a * c

The first answer is picked most because division is carried out before subtraction, and
multiplication before addition. If we wanted the second answer, write expression differently using
parentheses to change the order of evaluation
X= ((a / ( b – c + d ) ) * ( e – a ) * c
In C, there is a precedence hierarchy that determines the order in which operators are
evaluated. Below figure contains the precedence hierarchy for C.

Chandana S, Asst Prof, GSSS-SSFGC Mysore

 36

• The operators are arranged from highest precedence to lowest. Operators with
highest precedence are evaluated first.
• The associativity column indicates how to evaluate operators with the same
precedence. For example, the multiplicative operators have left-to-right
associativity. This means that the expression a * b / c % d / e is equivalent to
((((a*b)/c)%d)/e)
• Parentheses are used to override precedence, and expressions are always
evaluated from the innermost parenthesized expression first .

INFIX TO POSTFIX CONVERSION

Infix to Postfix conversion Algorithm

1.Scan the infix expression from left to right.

2.If the scanned character is an operand, output it.
3.Else,
1.If the precedence of the scanned operator is greater than the precedence of the
operator
in the stack(or the stack is empty or the stack contains a ‘(‘ ), push it.
2. Else, Pop all the operators from the stack which are greater than or equal to in
precedence than that of the scanned operator. After doing that Push the scanned
operator to the stack. (If you encounter parenthesis while popping then stop there and
push the scanned operator in the stack.)
4. If the scanned character is an ‘(‘, push it to the stack.
5. If the scanned character is an ‘)’, pop the stack and output it until a ‘(‘ is
encountered, and discard both the parenthesis.
6. Repeat steps 2-6 until infix expression is scanned.
7. Print the output
8. Pop and output from the stack until it is not empty.

Example: Infix expression: a/b -c +d*e -a*c

Fully parenthesized : ((((a/b)-c) + (d*e))-a*c))
:ab/e–de*+ac*
Example [Parenthesized expression]: Parentheses make the translation process more
difficult because the equivalent postfix expression will be parenthesis-free.
The expression a*(b +c)*d which results abc +*d* in postfix. Figure shows the
translation process. The analysis of the examples suggests a precedence-based scheme
for stacking and unstacking operators.

Chandana S, Asst Prof, GSSS-SSFGC Mysore

 37

The left parenthesis complicates matters because it behaves like a low-precedence

operator when it is on the stack and a high-precedence one when it is not. It is placed in the
stack whenever it is found in the expression, but it is un-stacked only when its matching
right parenthesis is found.

Chandana S, Asst Prof, GSSS-SSFGC Mysore

 38

Chandana S, Asst Prof, GSSS-SSFGC Mysore

 39

Chandana S, Asst Prof, GSSS-SSFGC Mysore

 40

Analysis of postfix: Let n be the number of tokens in the expression. Ө (n) time is spent
extracting tokens and outputting them. Time is spent in the two while loops, is Ө (n) as
the number of tokens that get stacked and unstacked is linear in n. So, the complexity of
function postfix is Ө (n).

EVALUATION OF POSTFIX EXPRESSION

• The evaluation process of postfix expression is simpler than the evaluation of
infix expressions because there are no parentheses to consider.
• To evaluate an expression, make a single left-to-right scan of it. Place the
operands on a stack until an operator is found. Then remove from the stack, the
correct number of operands for the operator, perform the operation, and place the
result back on the stack and continue this fashion until the end of the expression.
We then remove the answer from the top of the stack.
Chandana S, Asst Prof, GSSS-SSFGC Mysore
 41

Consider the following arithmetic expression P, written in postfix notation. Translate

it in infix notation and evaluate. P: 12, 7, 3, -, /, 2, 1, 5, +, *, +
Same Expression in infix notation is : ( 12 / ( 7 – 3 ) ) + ( ( 5 + 1 ) * 2 )
Chandana S, Asst Prof, GSSS-SSFGC Mysore
 42

Program to convert an infix expression to postfix.

#include<stdio.h>
#include<string.h>
#include<conio.h>
int F(char symbol)
{
switch(symbol)
{
case '+':
case '-': return 2;
case '*':
case '/': return 4;
case '^':
case '$': return 5;
case '(': return 0;
case '#': return -1;
default : return 8;
}
}
int G(char symbol)
{
switch(symbol)
{
case '+':
Chandana S, Asst Prof, GSSS-SSFGC Mysore
 43

case '-': return 1;

case '*':
case '/': return 3;
case '^':
case '$': return 6;
case '(': return 9;
case ')': return 0;
default : return 7;
}
}
void infix_postfix(char infix[],char postfix[])
{
int top,i,j;
char s[30],symbol;
top=-1;
s[++top]='#';
j=0;
for(i=0;i<strlen(infix);i++)
{
symbol=infix[i];
while(F(s[top])>G(symbol))
{
postfix[j]=s[top--];
j++;
}
if(F(s[top])!=G(symbol))
s[++top]=symbol;
else
top--;
}
while(s[top]!='#')
{
postfix[j++]=s[top--];
}
postfix[j]='\0';
}
int main()
{
char infix[20];
char postfix[20];
clrscr();
Chandana S, Asst Prof, GSSS-SSFGC Mysore
 44

printf("enter a valid infix expression:\n");

scanf("%s",infix);
infix_postfix(infix,postfix);
printf("the postfix expression is:\n");
printf("%s\n",postfix);
getch();
return 0;
}

Function Call Stack

What are Stacks in C?

In C, stack is a Linear Data Structure where elements are stored at contiguous memory
locations.
Stack follows LIFO mechanism i.e. Last in First Out. Let’s understand LIFO mechanism
more clearly by an example.
tower of Hanoi, all the disks are placed on a peg, To insert a new disk, it must be placed
on the top of peg.
The top disk must be removed from the peg before removing any other disk, this is LIFO
mechanism.
What are stacks

Stack follows a standard terminology for every operation.

Push: Inserting an element at the top of stack.
Pop: Removing an element from the top of stack.
Peek: Returns top element of the stack without deleting.
What is Call Stack in C?
Call stack is a dynamic data structure maintained inside the RAM memory by the
Operating System.

Chandana S, Asst Prof, GSSS-SSFGC Mysore

 45

Primary task of Function Call Stack in C is to manage the function calls and how they
pass parameters to each other.
A call stack is maintained for each task and for each thread. It is also called an execution
stack or machine stack. More often it is simply known as a stack.
Now let’s look at how function calls are actually organized in a stack: Let’s assume we
have two functions f1() and f2() along with main().

#include<stdio.h>
void f2()
{
return;
}
void f1()
{
f2(); //calling f2()
return;
}

//This is main function

int main()
{
f1(); // calling f1()
}

Activation record: When a function calls another function, an entry is pushed to stack.
This entry is called as Activation Record.
Activation record contains parameters, local variables, and return address that the called
function needs to return to the calling function.
On running the program, the main() is called, so an activation record for main() is created
and added to the stack.
Now, main() calls f1(), which creates an activation record for f1() on top of stack and f1()
calls f2() by adding activation record for f2() on top of stack.
When f2() terminates, its activation record is removed from the stack.
After completing the execution of f1(), it returns by removing the activation record from
the stack.
At this stage, we are back to our main() which removes its activation record leading to
the termination of the program.

Chandana S, Asst Prof, GSSS-SSFGC Mysore

 46

Chapter 3-QUEUE

Queue is an abstract data structure, somewhat similar to Stacks. Unlike stacks, a queue is
open at both its ends. One end is always used to insert data (enqueue) and the other is used
to remove data (dequeue). Queue follows First-In-First-Out methodology, i.e., the data
item stored first will be accessed first.
A real-world example of queue can be a single-lane one-way road, where the vehicle
enters first, exits first. More real-world examples can be seen as queues at the ticket
windows and bus-stops.

Chandana S, Asst Prof, GSSS-SSFGC Mysore

 47

Queue Representation

As we now understand that in queue, we access both ends for different reasons. The
following diagram given below tries to explain queue representation as data structure –

As in stacks, a queue can also be implemented using Arrays, Linked-lists, Pointers and
Structures. For the sake of simplicity, we shall implement queues using one-dimensional
array.

Representation of queue using array:

We can easily represent queue by using linear arrays. There are two variables i.e. front and rear,
that are implemented in the case of every queue. Front and rear variables point to the position
from where insertions and deletions are performed in a queue. Initially, the value of front = NULL
indicates that queue is empty and rear = N -1 indicates that queue is full.
Example: Array representation of a queue containing 5 elements along with the respective values
of front and rear, is shown in the following figure.

The above figure shows the queue of characters forming the English word "HELLO". Since, No
deletion is performed in the queue till now, therefore the value of front remains -1 . However, the
value of rear increases by one every time an insertion is performed in the queue. After inserting an
element into the queue shown in the above figure, the queue will look something like following.
The value of rear will become 5 while the value of front remains same.

Chandana S, Asst Prof, GSSS-SSFGC Mysore

 48

After deleting an element, the value of front will increase from -1 to 0. Whoever queue will look
something like following

Representation of queue using linked list:

One of the alternative of array implementation is linked list implementation of queue.

The storage requirement of linked representation of a queue with n elements is o(n) while the time
requirement for operations is o(1).

In a linked queue, each node of the queue consists of two parts i.e. data part and the link part.
Each element of the queue points to its immediate next element in the memory.

In the linked queue, there are two pointers maintained in the memory i.e. front pointer and rear
pointer. The front pointer contains the address of the starting element of the queue while the rear
pointer contains the address of the last element of the queue.

Insertion and deletions are performed at rear and front end respectively. If front and rear both are
NULL, it indicates that the queue is empty.

The linked representation of queue is shown in the following figure.

Chandana S, Asst Prof, GSSS-SSFGC Mysore

 49

Types of queues:
Queue can be of four types:

1. Simple Queue
2. Circular Queue
3. Priority Queue
4. Dequeue (Double Ended queue)

1. Simple Queue:

In Linear Queue, an insertion takes place from one end while the deletion occurs from another
end. The end at which the insertion takes place is known as the rear end, and the end at which the
deletion takes place is known as front end. It strictly follows the FIFO rule.

The major drawback of using a linear Queue is that insertion is done only from the rear end. If the
first three elements are deleted from the Queue, we cannot insert more elements even though the
space is available in a Linear Queue. In this case, the linear Queue shows the overflow condition
as the rear is pointing to the last element of the Queue.

2.Circular Queue

In Circular Queue, all the nodes are represented as circular. It is similar to the linear Queue except
that the last element of the queue is connected to the first element. It is also known as Ring Buffer,
as all the ends are connected to another end.

Chandana S, Asst Prof, GSSS-SSFGC Mysore

 50

The drawback that occurs in a linear queue is overcome by using the circular queue. If the empty
space is available in a circular queue, the new element can be added in an empty space by simply
incrementing the value of rear. The main advantage of using the circular queue is better memory
utilization.

3.Priority Queue

It is a special type of queue in which the elements are arranged based on the priority. It is a special
type of queue data structure in which every element has a priority associated with it. Suppose
some elements occur with the same priority, they will be arranged according to the FIFO
principle.

Insertion in priority queue takes place based on the arrival, while deletion in the priority queue
occurs based on the priority. Priority queue is mainly used to implement the CPU scheduling
algorithms.

There are two types of priority queue that are discussed as follows -

o Ascending priority queue - In ascending priority queue, elements can be inserted in arbitrary
order, but only smallest can be deleted first. Suppose an array with elements 7, 5, and 3 in
the same order, so, insertion can be done with the same sequence, but the order of deleting
the elements is 3, 5, 7.
o Descending priority queue - In descending priority queue, elements can be inserted in
arbitrary order, but only the largest element can be deleted first. Suppose an array with
Chandana S, Asst Prof, GSSS-SSFGC Mysore
 51

elements 7, 3, and 5 in the same order, so, insertion can be done with the same sequence, but
the order of deleting the elements is 7, 5, 3.

4.Dequeue (or, Double Ended Queue)

In Dequeue or Double Ended Queue, insertion and deletion can be done from both ends of the
queue either from the front or rear. It means that we can insert and delete elements from both front
and rear ends of the queue. Dequeue can be used as a palindrome checker means that if we read
the string from both ends, then the string would be the same.
Dequeue can be used both as stack and queue as it allows the insertion and deletion operations on
both ends. Dequeue can be considered as stack because stack follows the LIFO (Last In First Out)
principle in which insertion and deletion both can be performed only from one end. And in
dequeue, it is possible to perform both insertion and deletion from one end, and Dequeue does not
follow the FIFO principle.

There are two types of dequeue that are discussed as follows -

o Input(Insertion) restricted dequeue - As the name implies, in input restricted queue,

insertion operation can be performed at only one end, while deletion can be performed from
both ends.

Output (Deletion) restricted dequeue - As the name implies, in output restricted queue, deletion
operation can be performed at only one end, while insertion can be performed from both ends.

Chandana S, Asst Prof, GSSS-SSFGC Mysore

 52

Basic Operations
Queue operations may involve initializing or defining the queue, utilizing it, and then
completely erasing it from the memory. Here we shall try to understand the basic
operations associated with queues −

• Create() – Used to create queue.

Declare array Q[n]
• enqueue() − add (store/Insert) an item to the queue.
• dequeue() − remove (access/Delete) an item from the queue.
• peek() − Gets the element at the front of the queue without removing it.
• isfull() − Checks if the queue is full.
If(Rear==n) then
Say queue is full

• isempty() − Checks if the queue is empty.

If(Front==0) then
Say queue is full

Algorithm
Enqueue Operation (Insertion)
Input : Q- Queue
E- element
output: Q- Updated
Method: if(isfull(Q)), then
say Overflow
else
if(isempty(Q)), then
front=Rear=0
Q(Rear)=E
Else
Rear=Rear+1
Q(Rear)=E
If ends
If ends
Algorithm ends

Chandana S, Asst Prof, GSSS-SSFGC Mysore

 53

Dequeue Operation (Deletion)

Input : Q- Queue
Output: E- element
Method: if(isempty(Q)), then
Say Queue is empty
Else
E= Q(Front)
If(Front==Rear)
Front=0
Rear=0
Else
Front= Front+1
If ends
If ends
Algorithm ends

Application of Queue:
1. Simulation
2. Various features of Operating system 3. Multi-programming
platform systems.
4. Different types of scheduling algorithms
5. Round robin technique algorithms
6. Printer server routines
7. Various application software’s is also based on queue data structure.

Implementation of Simple Queue

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define SIZE 4
int r=-1,f=-1;
int q[20];
void insert()
{
if(r==SIZE-1)
printf("queue overflow\n");
else
{
Chandana S, Asst Prof, GSSS-SSFGC Mysore
 54

r=r+1;
printf("enter the element to be inserted:");
scanf("%d",&q[r]);
}
if(f==-1)
f=f+1;
}
void delte()
{
if(f==-1)
printf("queue is empty\n");
else
{
printf("the element deleted is %d",q[f]);
if(f==r)
f=r=-1;
else
f=f+1;
}
return;
}
void display()
{
int i;
if(f==-1)
printf("queue is empty\n");
else
{
printf("the elements are as follows .. . .\n");
for(i=f;i<=r;i++)
printf("%d\t",q[i]);
}
return;
}
int main()
{
int ch;
Chandana S, Asst Prof, GSSS-SSFGC Mysore
 55

clrscr();
while(1)
{
printf("\n\nQUEUE MENU");
printf("\n 1.insert");
printf("\n 2.delete");
printf("\n 3.display");
printf("\n 4.exit");
printf("\nenter your choice:");
scanf("%d",&ch);
switch(ch)
{
case 1: insert();
break;
case 2: delte();
break;
case 3: display();
break;
case 4: exit(1);
default: printf("\n invalid choice");
}
}
}

Chandana S, Asst Prof, GSSS-SSFGC Mysore

 UNIT – 03
Chapter 2 – TREE
Tree is a non-linear data structure which organizes data in hierarchical structure with collection of nodes and
connected by edges.

A tree is a set of finite set of one or more nodes that show parent-child relation. This data structure is a
specialized method to organize and store data in the computer to be used more effectively. It consists of a
central node, structural nodes, and sub-nodes, which are connected via edges. We can also say that tree data
structure has roots, branches, and leaves connected.

Basic Terminologies In Tree Data Structure:

Parent Node: The node which is a predecessor of a node is called the parent node of that node. {B} is the
parent node of {D, E}.

Chandana S, Asst Prof, GSSS-SSFGC, Mysore 1

Child Node: The node which is the immediate successor of a node is called the child node of that node.
Examples: {D, E} are the child nodes of {B}.

Root Node: The topmost node of a tree or the node which does not have any parent node is called the root
node. {A} is the root node of the tree. A non-empty tree must contain exactly one root node and exactly one
path from the root to all other nodes of the tree.

Leaf Node or External Node: The nodes which do not have any child nodes are called leaf nodes. {K, L, M,
N, O, P, G} are the leaf nodes of the tree.

Ancestor of a Node: Any predecessor nodes on the path of the root to that node are called Ancestors of that
node. {A,B} are the ancestor nodes of the node {E}

Descendant: A node x is a descendant of another node y if and only if y is an ancestor of y.

Sibling: Children of the same parent node are called siblings. {D,E} are called siblings.

Level of a node: The count of edges on the path from the root node to that node. The root node has level 0.

Internal node: A node with at least one child is called Internal Node.

Neighbours of a Node: Parent or child nodes of that node are called neighbors of that node.

Subtree: Any node of the tree along with its descendant.

Degree: The number of subtrees or child’s of a node is called its degree.

Chandana S, Asst Prof, GSSS-SSFGC, Mysore 2

Height of a Tree: Height-In a tree data structure, the total number of edges from leaf node to a particular node
in the longest path is called as HEIGHT of that Node. In a tree, height of the root node is said to be height of
the tree. In a tree, height of all leaf nodes is '0'.

Depth-In a tree data structure, the total number of edges from root node to a particular node is called as
DEPTH of that Node. In a tree, the total number of edges from root node to a leaf node in the
longest path is said to be Depth of the tree. In simple words, the highest depth of any leaf node in a
tree is said to be depth of that tree. In a tree, depth of the root node is '0'.

Path-In a tree data structure, the sequence of Nodes and Edges from one node to another node is called as
PATH between that two Nodes. Length of a Path is total number of nodes in that path. In belowexample the
path A - B - E - J has length 4.

Chandana S, Asst Prof, GSSS-SSFGC, Mysore 3

Advantages of trees
Trees are so useful and frequently used, because they have some very serious advantages:
o Trees reflect structural relationships in the data
o Trees are used to represent hierarchies
o Trees provide an efficient insertion and searching
o Trees are very flexible data, allowing to move sub trees around with minimum effort

Chapter 3: Binary Tree

In a normal tree, every node can have any number of children. Binary tree is a special type of tree data
structure in which every node can have a maximum of 2 children. One is known as left child and the other is
known as right child.
Definition:
A tree in which every node can have a maximum of two children is called as Binary Tree.
In a binary tree, every node can have either 0 children or 1 child or 2 children but not more than 2 children
or
A binary tree is a tree which has finite set of nodes that is either empty or consist of a root and two subtrees
called left subtree and right subtree. A binary tree can be partitioned into three subgroups namely root. Left
subtree and right subtree.

Root – If tree is not empty, the first node is called root node.
Left subtree – It is a tree which is connected to the left of node. Since this tree comes towards left of root. It is
called left subtree.
Right subtree – It is a tree which is connected to the right of root. Since this tree comes towards right of root,
it is called right subtree.

Chandana S, Asst Prof, GSSS-SSFGC, Mysore 4

Types of Binary Tree:
The binary trees are classified as
1. Strictly Binary Tree(Full Binary Tree/ 2 Tree/ Proper Binary Tree)
2. Complete Binary Tree
3. Binary Search Tree
4. Heap Tree

1. Strictly Binary Tree

Binary Tree in which every node has either two or zero number of children is called Strictly Binary Tree.
Strictly binary tree is also called as Full Binary Tree or Proper Binary Tree or 2-Tree
A binary tree having 2 nodes in any given level i is called strictly binary tree. Here, every node other than the
leaf node has two children.

Chandana S, Asst Prof, GSSS-SSFGC, Mysore 5

For example, in full binary tree shown.
• The number of nodes at level 0 = 20 = 1
• The number of nodes at level 1 = 21 = 2
• The number of nodes at level 2 = 22 = 4

2. Complete Binary Tree:

A complete binary tree is a binary tree in which every level, except possibly the last level is completely
filled. If the nodes in the last level are not completely filled, then all the nodes in that level should be filled
only from left to right.
Or
It is a Binary tree in this the last node is occupied in an systematic way.
Or
It is a Binary tree in this the last but one node is completely occupied and the last level is occupied in an
systematic way.

For example, all the trees shown below are complete binary trees.

The tree shown below is not complete binary tree since the nodes in the last level are not filled from left to
right. There is an empty left child for node 5 in figure(d) and there is an empty right child for node 5 in
figure(e). all the nodes should be as left as

3. Binary Search Tree:

It is a Binary tree in which the values of the left subtree is less than the root and the values of the right subtree
is greater than the root
Chandana S, Asst Prof, GSSS-SSFGC, Mysore 6
 4. Heap Tree
A heap is a complete binary such that the key at each node is greater than or equal to the keys of its children
or vice verse .
Or
It is a Binary tree in which the values at each parent node is greater than , lesser than or equal to the values of
their children.

A heap can be classified as

1. Ascending heap(min heap)
2. Descending heap(max heap)

1. Ascending heap(min heap):

It is a binary tree in which the value of parent node is smaller than the value of the left and right child node.
or
An ascending heap often called min-heap is a complete binary tree such that an item at any given node is
less than or equal to the left child and right child. So, in an ascending heap, the root node contains the least
element and the elements in any path from root to a leaf will be in ascending order.
For example, the tree shown in figure represent an ascending heap.

2. Descending heap(max heap):

Chandana S, Asst Prof, GSSS-SSFGC, Mysore 7
A descending heap often called max-heap is a complete binary tree such that an item at any given node is
greater than or equal to the left child and right child. So, in a descending heap, the root node contains the
highest element and the elements in any path from root to a leaf will be in descending order.
For example, the trees shown below represent descending heaps.

Array Representation of Binary Tree:

A tree can also be represented using an array, which is called sequential representation. Consider the trees
shown in fig. below with array representation.

Binary Tree Traversal:

Definition: traversing is a method of visiting each node of a tree exactly once in a systematic order. During
traversal, we may print the info field of each node visited.

The various traversal techniques of a binary tree are

1. Preorder traversal
2. Postorder traversal
3. Inorder traversal

1. Preorder Traversal (Root - Leftchild - Rightchild )

Chandana S, Asst Prof, GSSS-SSFGC, Mysore 8

 In Pre-Order traversal, the root node is visited before left child and right child nodes. In this
traversal, the root node is visited first, then its left child and later its right child. This pre-order
traversal is applicable for every root node of all subtrees in the tree.

Root

Left 2 3 Right

Ex:

Algorithm
Step 1 − Visit root node.
Step 2 − Recursively traverse left subtree.
Step 3 − Recursively traverse right subtree..

Implementation
void preorder(NODE *root)
{
if(root!=NULL)
{
printf("%d ",root->info);
Chandana S, Asst Prof, GSSS-SSFGC, Mysore 9
preorder(root->left);
preorder(root->right);
}
}

2. Postorder Traversal (Leftchild - Rightchild – Root)

In Post-Order traversal, the root node is visited after left child and right child. In this traversal, left
child node is visited first, then its right child and then its root node. This is recursively performed until
the right most node is visited.

Root

Left 1 2 Right

Ex:

Algorithm
Step 1 − Recursively traverse left subtree.
Step 2 − Recursively traverse right subtree.
Step 3 − Visit root node.

Implementation

void postorder(NODE *root)

{
if(root!=NULL)
{
Chandana S, Asst Prof, GSSS-SSFGC, Mysore 10
postorder(root->left);
postorder(root->right);
printf("%d ",root->info);
}
}

3. Inrder Traversal (Leftchild - Root - Rightchild )

Root

Left 1 3 Right

In In-Order traversal, the root node is visited between left child and right child. In this traversal, the left child
node is visited first, then the root node is visited and later we go for visiting right child node. This in-order
traversal is applicable for every root node of all subtrees in the tree. This is performed recursively for all
nodes in the tree.

Ex:

Algorithm
Step 1 − Recursively traverse left subtree.
Step 2 − Visit root node.
Step 3 − Recursively traverse right subtree

Chandana S, Asst Prof, GSSS-SSFGC, Mysore 11

Implementation
void inorder(NODE *root)
{
if(root!=NULL)
{
inorder(root->left);
printf("%d ",root->info);
inorder(root->right);
}
}

Problem for Practice

1.

2.

3.

Chandana S, Asst Prof, GSSS-SSFGC, Mysore 12

4.

5.

Program to display traversal of a tree.

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct node
{
int info;
Chandana S, Asst Prof, GSSS-SSFGC, Mysore 13
struct node *left,*right;
};
typedef struct node NODE;
NODE *root= NULL;
void insert()
{
int item;
NODE *temp,*p,*q;
printf("enter the element to be inserted:");
scanf("%d",&item);
q=(NODE*)malloc(sizeof(NODE));
q->info=item;
q->left=q->right=NULL;
temp=root;
if(temp==NULL)
{
root=q;
return;
}
while(temp!=NULL)
{
p=temp;
if(temp->info>item)
temp=temp->left;
else
temp=temp->right;
}
if(p->info>item)
p->left=q;
else
p->right=q;
return;
}

void preorder(NODE *root)

{
if(root!=NULL)
{
printf("%d ",root->info);
preorder(root->left);
preorder(root->right);
}
}

void postorder(NODE *root)

{
if(root!=NULL)
{
postorder(root->left);
postorder(root->right);

Chandana S, Asst Prof, GSSS-SSFGC, Mysore 14

printf("%d ",root->info);
}
}

void inorder(NODE *root)

{
if(root!=NULL)
{
inorder(root->left);
printf("%d ",root->info);
inorder(root->right);
}
}

int main()
{
int ch;
clrscr();
while(1)
{ printf("\n\nBINARY TREE MENU");
printf("\n 1.insert \n 2.preorder \n 3.inorder \n 4.postorder \n 5.exit\n");
printf("enter your choice:");
scanf("%d",&ch);
switch(ch)
{
case 1: insert();
break;
case 2: printf("preorder traversal\n");
preorder(root);
break;
case 3: printf("inorder traversal\n");
inorder(root);
break;
case 4: printf("postorder traversal\n");
postorder(root);
break;
case 5: exit(0);
default: printf("invalid choice\n");
}
}
}

Chandana S, Asst Prof, GSSS-SSFGC, Mysore 15