III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C

DATA STRUCTURES USING ‘C’

UNIT-I Basic Concepts: Pointers and dynamic memory allocation, Algorithm-Definition and
characteristics, Algorithm Analysis-Space Complexity, Time Complexity, Asymptotic Notation
Introduction to Data structures: Definition, Types of Data structure, Abstract Data Types (ADT),
Difference between Abstract Data Types, Data Types, and Data Structures. Arrays-Concept of Arrays,
Single dimensional array, Two dimensional array, Operations on arrays with Algorithms (searching,
traversing, inserting, deleting)

UNIT-II Linked List: Concept of Linked Lists, Representation of linked lists in Memory, Comparison
between Linked List and Array, Types of Linked Lists - Singly Linked list, Doubly Linked list, Circularly
Singly Linked list, Circularly Doubly Linked list; Implementation of Linked List ADT: Creating a List,
Traversing a linked list, Searching linked list, Insertion and deletion into linked list (At first Node-
specified Position, Last node), Application of linked lists

UNIT-III Stacks: Introduction to stack ADT, Representation of stacks with array and Linked List,
Implementation of stacks, Application of stacks - Polish Notations - Converting Infix to Post Fix
Notation - Evaluation of Post Fix Notation - Tower of Hanoi, Recursion: Concept and Comparison
between recursion and Iteration Queues: Introduction to Queue ADT, Representation of Queues with
array and Linked List, Implementation of Queues, Application of Queues Types of Queues- Circular
Queues, De-queues, Priority Queue

UNIT-IV Searching: Linear or Sequential Search, Binary Search and Indexed Sequential Search
Sorting: Selection Sort, Bubble Sort, Insertion Sort, Quick Sort and Merge Sort

UNIT-V Binary Trees: Concept of Non- Linear Data Structures, Introduction Binary Trees, Types of
Trees, Basic Definition of Binary Trees, Properties of Binary Trees, Representation of Binary Trees,
Operations on a Binary Search Tree, Binary Tree Traversal, Applications of Binary Tree.

Graphs: Introduction to Graphs, Terms Associated with Graphs, Sequential Representation of Graphs,
Linked Representation of Graphs, Traversal of Graphs (DFS, BFS), Application of Graphs.

1
III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C
UNIT-I

Data Structures
Introduction

Data Structure can be defined as the group of data elements which provides an efficient way of storing and
organizing data in the computer so that it can be used efficiently.
Some examples of Data Structures are arrays, Linked List, Stack, Queue, etc.
Data Structures are widely used in almost every aspect of Computer Science i.e. operating System,
Compiler Design, Artificial intelligence, Graphics and many more.

Basic Terminology:
 Data structures are the building blocks of any program or the software. Choosing the
appropriate data structure for a program is the most difficult task for a programmer.
 Following terminology is used as far as data structures are concerned
Data: Data can be defined as an elementary value or the collection of values, for example,
student's name and its id are the data about the student.
Group Items: Data items which have subordinate data items are called Group item, for example,
name of a student can have first name and the last name.
Record: Record can be defined as the collection of various data items, for example, if we talk
about the student entity, then its name, address, course and marks can be grouped together to form
the record for the student.
File: A File is a collection of various records of one type of entity, for example, if there are 60
employees in the class, then there will be 20 records in the related file where each record contains
the data about each employee.
Attribute and Entity: An entity represents the class of certain objects. it contains various
attributes. Each attribute represents the particular property of that entity.
Field: Field is a single elementary unit of information representing the attribute of an entity.

Need of Data Structures:

As applications are getting complexed and amount of data is increasing day by day, there
may arise the following problems:
Processor speed: To handle very large amount of data, high speed processing is required, but as
the data is growing day by day to the billions of files per entity, processor may fail to deal with
that much amount of data.
Data Search: Consider an inventory size of 106 items in a store; if our application needs to search
for a particular item, it needs to traverse 106 items every time, results in slowing down the search
process.

2
III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C
Data Types
 A data type is a term which refers to the kind of data that may be appear in the calculation.
 The result of the calculation is depends on the type of data used in the calculation.
 Data type specifies set of values and set of operations defined on them.
 For example with numbers we perform addition, subtraction, multiplication, division operations and
with strings we perform concatenation, extraction operations.

Data Data Type

30 Numeric(integer)
45.6 Numeric(Float)
12/12/17 Date
C Program String
Data types are mainly two types. They are
1. Built-in data types
2. User defined data types or Abstract Data Types
1. Built-in data types :
 Data types provided by the language are known as built in data types.
 Most of the languages provide various kinds of built in data types. Some of them are as follows
Language Data types
C Int,float,double,char etc.
Fortran Integer,real,character, logical,complex etc
Pascal Integer,real,character, boolean etc

2. User defined data types or Abstract Data Types(ADT) :

 Programmer defined data types are known as user defined data types or Abstract data types
(ADT).
 When an application requires a special kind of data which is not available in built in data types,
then the programmer has to develop their own data type called Abstract Data type (ADT).
 An ADT is an organized collection of related information (data) and set of operations
(methods) used to manage the information.
 ADT uses data encapsulation to combine both data and operations in a single unit.
 ADT’s are defined using list of abstract fields called data and operations.

3
III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C

Abstract Data Type

User
Abstract Data
(Or)
Programmer
Operations

Examples:

1. Arrays
2. Stacks
3. Queues
4. Trees
5. Lists

Abstract Data Types (ADT)

 Programmer defined data types are known as user defined data types or Abstract data types (ADT).
 When an application requires a special kind of data which is not available in built in data types, then
the programmer has to develop their own data type called Abstract Data type (ADT).
 An ADT is an organized collection of related information (data) and set of operations (methods) used
to manage the information.
 ADT uses data encapsulation to combine both data and operations in a single unit.
 ADT’s are defined using list of abstract fields called data and operations.

Abstract Data
Type
User
Abstract Data
(Or)
Programmer
Operations

Common ADTs:
1. Arrays
2. Stacks
3. Queues
4. Trees
5. Graphs

4
III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C
1. Array:
An array is a collection of similar data items which share common name. The elements of
an array are accessed using a number called “Index”. The index of the first element is 0 and the
index of the last element is [Link] elements are stored in a sequential memory locations.

Memory address 101 105 109 ………………

Values 30 40 50 100
Index 0 1 2 ………………. Size-1
ADT array
{
Data:
Linear list of elements
Operations:
lowerbound(): returns the index of first element
upperbound(): Returns the index of last element
size(): Returns size of the array
index(element): Returns the index of specified element.
}

2. Stack:
Stack is a linear list of elements in which elements are inserted and deleted at the same end
called top of the stack. Stacks are also called LIFO (Last In First Out) lists, since the last inserted
element is removed first.

PUSH POP

TOP

ADT stack
{
Data
Linear list of elements
Operations
Push(): Inserts a new element at the top of the stack
5
III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C

Pop(): Removes an element from top of the stack

Top(): Retutns an element located at top of the stack
}
3. Queue:
Queue is a linear list of elements in which elements are inserted at one end called “Rear”
end and elements are deleted from another end called “Front” end. Queues are also called FIFO
(First In First Out) lists,since the first inserted element is removed first.

10 20 30 40 50 60
Insert
Delete
FRONT REAR
ADT queue
{
Data:
Linear list of elements
Operations:
Insert(): Inserts a new element at rear end of the queue
Delete(): Removes an element from the front end of the queue
Top(): Retutns an element located at top of the stack
}
4. Trees:
Tree is a non-linear list of elements made up of nodes or vertices and edges without having
any cycle.
A Root Node

Parent Node
B C

D E F G Child Node

ADT tree
{
Data:
Non linear list of elements
Operations:
Insert(): Inserts a new node to the tree
Delete(): Removes a node from the tree
Search(): Returns the location of the specified node

6
III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C
}
5. Graph:
Graph is a non-linear list of elements made up of nodes or vertices and edges with having
any cycle.

ADT tree
{
Data:
Non linear list of elements
Operations:
Insert(): Inserts a new vertex to a graph
Delete(): Removes a node from the graph
Search(): Returns the location of the specified node
}

Data Structures
 A data structure is a specialized format for collecting, organizing, storing and retrieving data in an
effective way.
 The logical or mathematical model of a particular organization of data is called a data structure.
 Data structure is a programming construct used to implement an ADT.
 Data structure is a physical implement of ADT.
 A data structure that implements an ADT consists collection of variables to store data and the
collection of algorithms or functions to implement operations.
Types of Data Structures:

1. Primitive Data Structures:

 Primitive data types are considered as primitive data structures.
7
III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C
 Primitive data types are the basic data types that are available in most of the languages such as C,
C++, JAVA etc.
 Primitive data types are used to represent a single value.
 Primitive data structures operate machine level instructions directly without using any code.
Types of primitive data structures:
(a) Integer: This is used to represent a number without decimal point.
Ex: 10,30,70
(b) Float or Double: This is used to represent a number with decimal point.
Ex: 10.89,30.9,70.08
(c) Character: This is used to represent a single character that is either an alphabet, digit or a
special symbol.
Ex: ‘A’, ‘9’ , ‘+’
(d) String: This is used to represent more than one character.
Ex: “KCDC”,”21345”
(e) Boolean: This is used to represent logical values either “True” or “False”.
2. Non-Primitive data structures:
 Derived data types and user defined data types are considered as non-primitive data structures
or derived data structures.
 Non-primitive data structures are used to represent group of primitive type values.
Types of primitive data structures:
(a) Linear Data structures:
 A data structure is said to be linear data structure if its elements are in sequence or
linear.
 A list that shows the relationship between adjacency elements is known as linear data
structure.
 A linear data structure traverses the data elements sequentially, in which only one data
element can directly be reached.
Types of Linear data structures:
i. Array:
An array is a collection of similar data items which share common name. The elements of
an array are accessed using a number called “Index”. The index of the first element is 0 and the
index of the last element is [Link] elements are stored in a sequential memory locations.

Memory address 101 105 109 ………………

Values 30 40 50 100

8
III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C
Index 0 1 2 ………………. Size-1

ADT array
{
Data:
Linear list of elements
Operations:
lowerbound(): returns the index of first element
upperbound(): Returns the index of last element
size(): Returns size of the array
index(element): Returns the index of specified element.
}
ii. Linked list:
Linked list is a linear list of elements represented as nodes. Each node in a linked
list contains two parts: data part and link part. The data part contains value of the node and the link
part contains address of the next node. Linked lists are called dynamic data structures since the
nodes are created whenever necessary at the time of executing the program.
ADT Linked list
{
Data:
Collection of nodes
Operations:
Insert(): inserts a new node.
Delete():deletes the specified node.
size(): Returns size of the list.
Traverse():visits all the nodes in the list.
}
iii. Stack:
Stack is a linear list of elements in which elements are inserted and deleted at the same end
called top of the stack. Stacks are also called LIFO (Last In First Out) lists, since the last inserted
element is removed first.

PUS POP
H
TOP

9
III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C

ADT stack
{
Data
Linear list of elements
Operations
Push(): Inserts a new element at the top of the stack
Pop(): Removes an element from top of the stack
Top(): Retutns an element located at top of the stack
}

[Link]:
Queue is a linear list of elements in which elements are inserted at one end called “Rear”
end and elements are deleted from another end called “Front” end. Queues are also called FIFO
(First In First Out) lists,since the first inserted element is removed first.

10 20 30 40 50 60
Insert
Delete
FRONT REAR
ADT queue
{
Data:
Linear list of elements
Operations:
Insert(): Inserts a new element at rear end of the queue
Delete(): Removes an element from the front end of the queue
Top(): Retutns an element located at top of the stack
}
(b) Non-linear data structures:
 A data structure is said to be non-linear data structure if its elements are not in a sequence.
 Non-Linear data structure is opposite to linear data structure.
 In non-linear data structure, the data item is connected to several other data items.
 It uses memory efficiently. Free contiguous memory is not required for allocating data
items.

Types of Non-linear data structures:

i. Trees:
Tree is a non-linear list of elements made up of nodes or vertices and edges without having any cycle.

10
III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C

A Root Node

Parent Node
B C

D E F G Child Node

ADT tree
{
Data:
Non linear list of elements
Operations:
Insert(): Inserts a new node to the tree
Delete(): Removes a node from the tree
Search(): Returns the location of the specified node
}
ii. Graphs:
Graph is a non-linear list of elements made up of nodes or vertices and edges with
having any cycle.

ADT tree
{
Data:
Non linear list of elements
Operations:
Insert(): Inserts a new vertex to a graph
Delete(): Removes a node from the graph
Search(): Returns the location of the specified node
}

Algorithms

 An algorithm can be defined as a finite set of steps, which has to be followed while carrying out a
particular problem. It is nothing but a process of executing actions step by step.
 An algorithm is a distinct computational procedure that takes input as a set of values and results in
the output as a set of values by solving the problem. More precisely, an algorithm is correct, if, for
each input instance, it gets the correct output and gets terminated.

11
III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C
 An algorithm unravels the computational problems to output the desired result. An algorithm can
be described by incorporating a natural language such as English, Computer language, or a
hardware language.

Characteristics of Algorithms:
o Input: It should externally supply zero or more quantities.
o Output: It results in at least one quantity.
o Definiteness: Each instruction should be clear and ambiguous.
o Finiteness: An algorithm should terminate after executing a finite number of steps.
o Effectiveness: Every instruction should be fundamental to be carried out, in principle, by a person
using only pen and paper.
o Feasible: It must be feasible enough to produce each instruction.
o Flexibility: It must be flexible enough to carry out desired changes with no efforts.
o Efficient: The term efficiency is measured in terms of time and space required by an algorithm to
implement. Thus, an algorithm must ensure that it takes little time and less memory space meeting
the acceptable limit of development time.
o Independent: An algorithm must be language independent, which means that it should mainly
focus on the input and the procedure required to derive the output instead of depending upon the
language.

Advantages of an Algorithm:
o Effective Communication: Since it is written in a natural language like English, it becomes easy
to understand the step-by-step delineation of a solution to any particular problem.
o Easy Debugging: A well-designed algorithm facilitates easy debugging to detect the logical errors
that occurred inside the program.
o Easy and Efficient Coding: An algorithm is nothing but a blueprint of a program that helps
develop a program.
o Independent of Programming Language: Since it is a language-independent, it can be easily
coded by incorporating any high-level language.

Disadvantages of an Algorithm:
o Developing algorithms for complex problems would be time-consuming and difficult to
understand.
o It is a challenging task to understand complex logic through algorithms.

Algorithm Analysis
 In the analysis of the algorithm, it generally focused on CPU (time) usage, Memory usage, Disk
usage, and Network usage.
 All are important, but the most concern is about the CPU time.
Be careful to differentiate between:

12
III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C
 Performance: How much time/memory/disk/etc. is used when a program is run. This depends on
the machine, compiler, etc. as well as the code we write.
 Complexity: How do the resource requirements of a program or algorithm scale, i.e. what happens
as the size of the problem being solved by the code gets larger.
 Algorithm analysis is an important part of computational complexity theory, which provides
theoretical estimation for the required resources of an algorithm to solve a specific
computational problem.
 Analysis of algorithms is the determination of the amount of time and space resources required
to execute it.

 To predict the behavior of an algorithm without implementing it on a specific computer.

 It is much more convenient to have simple measures for the efficiency of an algorithm than to
implement the algorithm and test the efficiency every time a certain parameter in the underlying
computer system changes.
 It is impossible to predict the exact behavior of an algorithm. There are too many influencing
factors.
 The analysis is thus only an approximation; it is not perfect.
 More importantly, by analyzing different algorithms, we can compare them to determine the best
one for our purpose.
A complete analysis of the running time of an algorithm involves the following steps:
 Implement the algorithm completely.
 Determine the time required for each basic operation.
 Identify unknown quantities that can be used to describe the frequency of execution of the basic
operations.
 Develop a realistic model for the input to the program.
 Analyze the unknown quantities, assuming the modelled input.
 Calculate the total running time by multiplying the time by the frequency for each operation, then
adding all the products.

Complexity
o Time Complexity of an algorithm is the representation of the amount of time required by the
algorithm to execute to completion.
o Time requirements can be denoted or defined as a numerical function t(N), where t(N) can be
measured as the number of steps, provided each step takes constant time.
o For example, in case of addition of two n-bit integers, N steps are taken.
o Consequently, the total computational time is t(N) = c*n, where c is the time consumed for
addition of two bits.
o Here, we observe that t(N) grows linearly as input size increases.
o In other words, the time complexity is how long a program takes to process a given input.
o The efficiency of an algorithm depends on two parameters:
 Time Complexity
 Space Complexity
Time Complexity: It is defined as the number of times a particular instruction set is executed
rather than the total time is taken. It is because the total time took also depends on some external
factors like the compiler used, processor’s speed, etc.
Space Complexity: It is the total memory space required by the program for its execution.

13
III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C
Big oh Notation (O)

Big oh Notation (O):-

 Big O notation is an asymptotic notation that measures the performance of an algorithm by

simply providing the order of growth of the function.
 This notation provides an upper bound on a function which ensures that the function never
grows faster than the upper bound. So, it gives the least upper bound on a function so that the
function never grows faster than this upper bound.
It is the formal way to express the upper boundary of an algorithm running time. It measures the worst
case of time complexity or the algorithm's longest amount of time to complete its operation. It is
represented as shown below:

For example:
If f(n) and g(n) are the two functions defined for positive integers,
then f(n) = O(g(n)) as f(n) is big oh of g(n) or f(n) is on the order of g(n)) if there exists constants c
and no such that:

f(n)≤c.g(n) for all n≥no

This implies that f(n) does not grow faster than g(n), or g(n) is an upper bound on the function f(n). In this
case, we are calculating the growth rate of the function which eventually calculates the worst time
complexity of a function, i.e., how worst an algorithm can perform. Let's understand through examples
Example : f(n)=2n+3 , g(n)=n
Now, we have to find Is f(n)=O(g(n))?

To check f(n)=O(g(n)), it must satisfy the given condition:

f(n)<=c.g(n)
First, we will replace f(n) by 2n+3 and g(n) by n. 2n+3 <= c.n
Let's assume c=5, n=1 then 2*1+3<=5*1
5<=5
For n=1, the above condition is true. If n=2
2*2+3<=5*2
7<=10
For n=2, the above condition is true.

14
III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C
Arrays
Definition:
 An array is a collection of elements of same type that share a common name. (OR) An array is a
collective name given to a group of similar quantities.
 The elements of an array are stored in contiguous memory locations.
 Elements of an array can be accessed through a number called “Index”.
 The index of a first element is ‘0’ and the index of the last element is ‘size-1’.
 The memory is allocated to an array is depend on its type and size.
 Address of the first array element is called “base address”.
Advantages:
1. An array reduces the usage of number of variables in a program.
2. It maintains a list of values with a single name
3. An array is used for searching operations
4. It is used to sort a list of values
5. It is useful for matrix operations
Types of Arrays:
In ‘C language, arrays are classified into two types. They are
1. One Dimensional Arrays
2. Multi Dimensional Arrays
ONE DIMENSIONAL ARRAY:-
When an array is declared with only one dimension (subscript) then it is called “One dimensional
array” or “single dimensional array”.
Declaring One Dimensional Array:
Syntax: datatype arrayname[size];
In the above syntax,
 The datatype is any data type of C language. An array can hold all the values based on the data
type.
 The ‘arrayname’ is an identifier that specifies name of the array variable. All the elements use this
variable name.
 The ‘size’ indicates maximum number of elements of an array. It must be a positive integer
constant.
Example-1: int a[5];
The above declaration reserves 5 contiguous memory locations of integer type for the array
‘num’. The memory representation is as shown below:

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

15
III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C
1001 1003 1005 1007 1009
Base Address
Example-2: float marks[50];
Example-3: char name[10];
Accessing elements of one dimensional array:
 A one dimensional array element is accessed by specifying the array name followed by index. The
array indexes can be from 0 to size-1 of the array.
 The index must be positive integer. The index value must be enclosed within square brackets.
 It can be a constant, variable or an expression.
Examples Meaning
1. num[0] To access 1st element of array
2. num[4] To access 5th element of array
3. num[i] To access ith element of array. If i=2 then it is num[2]
4. num[i+2] To access i+2 element of array. If i=2 then it is num[2+2] i.e. num[4]

Storing Values In One Dimensional Array:-

Values can be stored in three ways. They are
(i) Initialisation
(ii) Assigning
(iii) Inputting values.
i) Initialisation of One Dimensional Array: Storing values to an array at the time of declaring an array is
called initializing array.
Syntax: datatype arrayname[size] = {V0, V1, ..., Vsize-1};
Here, V0, V1, …, Vsize-1 are the initial values of the specified array. If we omit values then an array
contains garbage values. The number of values must be less than or equal to the size of the array. When
there are few values then the remaining elements are assigned with zeros.
Example: num[0] num[1] num[2] num[3] num[4]
1. int num[5] = {78, 34, 98, 90, 124}; 
78 34 98 90 124
num[0] num[1] num[2] num[3] num[4]
2. int num[5] = {30, 25, 40};  30 25 40 0 0

ii) Assigning Values: Storing values in an arrary after the declaration is called “assigning”
Example: main()
{
int num[10];
num[0]=120;
num[5]=245;
}

16
III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C
In the above example, 120 is assigned to num[0] element, and 245 is assigned to num[5] element.
The remaining elements contain garbage values.
iii) Inputting Values: We can give values to the elements of an array using input statements.
Examples Meaning
1. scanf(“%d”,&num[0]) ; To input value to num[0]
2. scanf(“%d%d”,&num[0],&num[4]) ; To input values to num[0] and num[4]
3. scanf(“%d”,&num[i]); To input value to num[i]. If i=2 then it is num[2]
4. for(i=0;i<=4;i++) To input values from num[0] to num[4] at once i.e. 5 elements.
scanf(“%d”,&num[i]);

Calculating The Length Of The Array

The length of an array is calculated by the number of values stored in it. The general formula to
calculate the length of the array is:
Length = UpperBound – LowerBound + 1
Here, UpperBound is the index of the last element and LowerBound is the index of the first
element in the array.
Example-1:
int num[5];
num[0] = 10;
num[1] = 20; The memory representation is 10 20 30 40 50
num[2] = 30;  num[0] num[1] num[2] num[3] num[4]
num[3] = 40;
num[4] = 50;
In the above example, LowerBound is 0 and UpperBound is 4.
 Length = 4 – 0 + 1 = 5
Example-2: 20 30 40
int num[5];
num[0] num[1] num[2] num[3] num[4]
num[1] = 20;
The memory representation is
num[2] = 30;

num[3] = 40;
In the above example, LowerBound is 1 and UpperBound is 3..
Length = 3 – 1 + 1 = 3

TWO-DIMENSIONAL ARRAYS
 When an array is declared with two dimensions then it is called “two-dimensional array”. A two-
dimensional array is an array of one-dimensional arrays.
 It can be viewed as table of elements which contains rows and columns. A two-dimensional array
is useful for matrix operations.
Declaring Two-Dimensional Array:

17
III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C
Syntax: datatype arrayname[rowsize][columnsize];
In the above syntax,
i. The datatype is any valid data type of C language. An array can hold all the values based on the
data type.
ii. The ‘arrayname’ is an identifier that specifies name of the array variable. All the elements use this
variable name.
iii. The ‘rowsize’ indicates maximum number of rows and ‘columnsize’ indicates number of columns
in a row.
Example:
int num[2][3];
Here, it reserves 6 (2 rows x 3 columns) integer type memory locations for the array ‘num’. The
memory representation is as shown below:
num[2][3]

0 1 2
0
1
Accessing Elements Of Two Dimensional Array
A two dimensional array element is accessed by specifying the array name followed by two
subscripts. The array indexes can be from 0 to size - 1 of the array.
Each subscript must be positive integer. The subscript values must be enclosed within square
brackets. It can be a constant, variable or an expression.
Examples Meaning
num[0] [0] To access 1st element of array
num[1][2] To access 2nd row and 3rd column element of array
num[i][j] To access ith row, jth column of array. If i=1,j=2 then it is num[1][2]
num[i+2][j+1] To access i+2,j+1 element of array. If i=1,j=2 then it is
num[1+2][2+1] i.e. num[3][3]

Storing Values in Two Dimensional Array

When arrays are declared, it just allocates space for the elements and no values are stored in the
array. Values can be stored in three ways. They are
(i) Initialisation,
(ii) Assigning and
(iii) Inputting values.

18
III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C
i) Initialisation of Two Dimensional Array: Storing values to an array at the time of declaring an
array is called initializing array.

Syntax: datatype arrayname[rowsize][columnsize] = {{row1 values}, {row2 values}, …, } ;

Here, if we omit values then an array contains garbage values. The number of values must
be less than or equal to the size of the array. When there are few values then the remaining
elements are assigned with zeros.
Example-1: int num[2][3] = { {4, 6, 8}, {1, 3, 5}}; num 0 1 2
0 4 6 8
1 1 3 5
num 0 1 2
0 4 8 0
1 5 0 0

Example-2:
int num[2][3] = { {4, 8}, {5}};

ii) Assigning Values: Storing values in an arrary after the declaration is called “assigning”
Example: main()
{
int num[10][10];
num[0][0]=120;
num[5][4]=245;
}
In the above example, 120 is assigned to num[0][0] element, and 245 is assigned to num[5][4]
element. The remaining elements contain garbage values.
iii) Inputting Values: We can give values to the elements of an array using input statements.
Examples Meaning
1. scanf(“%d”,&num[0][0]); To input value to num[0][0]
2. scanf(“%d%d”,&num[0][0],&num[1][2]); To input values to num[0][0] and num[1][2]
3. scanf(“%d”,&num[i][j]); To input value to num[i][j]. If i=1,j=2 then it is
num[1][2]
4. for(i=0;i<=1;i++) To input values from num[0][0] to num[1][2] at
for(j=0;j<=2;j++) once i.e. 6 elements.
scanf(“%d”,&num[i][j]);

19
III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C
ARRAY OPERATIONS
An array is a finite collection of similar elements stored in adjacent memory locations. An array is ‘finite’
means it contains specific number of elements and ‘similar’ means that all the elements are of the same data type.
The array operatiosn are:

 Searching
 Traversing
 Inserting
 Deleting

Searching:
Searching means finding the location of any item in the array. Suppose A is a linear array with n elements.
The simplest way to search for a given item is to compare the item with each element in A one by one. That is,
first we test A[0] = item, and then we test A[1] = item and so on. The algorithm is:

1: Set LOC = 0
2: Repeat step 3 while LOC < N3: If A[LOC] = ITEM then

goto step 4
Else
Set LOC = LOC + 1
4: Print LOC, ITEM
5: Exit

Traversing:
Let ‘A’ be a collection of data elements stored in the computer’s memory. To print the contents of each
element of A, we have to be accessed at least once. This is called traversing. Thealgorithm is:

1: Set I = LB
2: Repeat steps 3 and 4 while I <= UB3: Print A[I]

4: Set I = I + 1
5: Exit

Inserting:
Insertion means adding a new element to the array. If an element is inserted at the end of the array, then
the task is easily done. But if we need to insert an element in the middle of an array then half of the elements must
be moved forward to new locations to put up the new element. The algorithm is:

1: Set J = UB
2: Repeat step 3 and 4 while J >= POS3: Set A[J + 1] = A[J]

4: Set J = J - 1
5: Set A[POS] = ITEM
6: Set UB = UB + 1
7: Exit

20
III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C
Deleting:
Deletion means removing an element from the array. Deleting the element from the end of array is not a
problem. But deleteing from the middle of an array requires moved of each element backward to fill up the empty
space in the array. The algorithm is:

1: Set ITEM = A[POS]

2: Repeat for J = POS to N-1
Set A[J] = A[J + 1]3: Set N = N – 1

4: Set UB = UB-1
5: Exit

POINTERS
Definition: A pointer is a variable that holds the memory address of another variable. It is used to
access value of a variable quickly.
Uses or Advantages of Pointers:
1. Execution of program will be faster.
2. Array elements can be easily accessed.
3. It provides call-by-reference mechanism.
4. We can send arrays and strings to functions.
5. Memory can be efficiently used through dynamic memory allocation (DMA).
6. Dynamic data structures like linked list, binary trees and graphs can be created.
Declaring a Pointer Variable:
 A pointer declaration contains a base type(data type) and asterisk (*) followed by a variable.
 A pointer variable is an unsigned integer and hence it occupies 2 bytes of memory.
Syntax: datatype *variable;
Example: Pointer variable P Q Simple Variable
int Q=50; Value of P (or)
1625 50
int *P; Address of Q Value of Q
P = &Q;
Address of P 2956 1625 Address of Q

POINTER OPERATORS:
‘C’ language provides two special operators to manipulate the values directly from memory using pointer
variables.

21
III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C

1. Address Operator (&): The Address of Points Value of address

operator is used to assign the variable to variable
memory address of a variable to a Pointer pointer
variable
variable. variable
Syntax: Pointer variable = &variable;

2. Indirection Operator (*): The asterisk (*) character is a unary operator that returns the value
stored at the memory address.
Syntax: Variable=*pointer variable;
Dynamic Memory Allocation (DMA)
 Dynamic Memory Allocation means allocation of memory at run-time i.e. during the program execution.
 DMA technique is useful when it is not known how much memory space is required before executing the
program.
 ‘C’ language provides various standard functions to manage memory efficiently.
Memory Management Functions:
malloc( ) Function:
 It allocates memory space to a variable. The space must be specified in the form of bytes.
 This function returns NULL if the allocation of memory fails.
 It means, if the memory is not sufficient to allocate then it returns NULL.
 The general format of malloc( ) function is as follows:
Syntax: pv = (type *) malloc(size);
Example-1:
int *p;
p = (int *) malloc(4); Allocates 4 bytes of memory to the variable ‘p’.
Example-2:
int *p, n=5;
p = (int *) malloc(n*2); Allocates memory for 5*2=10 bytes to p.
calloc( ) Function: This function is also used to allocate space to a variable. But it initializes all the elements with
zero.
Syntax: pv = (type *) calloc(n, size);
Example-1: int *p;
p = (int *) calloc(5, 4); 20 bytes allocated to p and 4 bytes for each block

22
III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C
UNIT – II

LINKED LISTS

LINKED LIST

Linked list is the most commonly used data structure used to store same data elements inthe memory.
The elements of a linked list are not stored in adjacent memory locations as in arrays.

 A linked list is a linear collection of data elements called nodes. Each node contains two [Link], Data
field and Link field.
Node
Data Link
 Data field contains the element of the list and link field contains the address of the next node.
 In linked lists, each node is connected by using the links.
 Linked lists are dynamic data structure, i.e. we can insert or delete nodes whenever werequired.

Advantages:
 Linked list can be increased or decreased because of dynamic data structure.
 Linked list are dynamic, which allocates the memory when required.
 Insertion and deletion can be easily performed.

Disadvantages:
 It occupies more space because every node contains a link field to store the address of thenext node.
 The elements are accessed sequentially, i.e. from the head node to tail node. No element canbe accessed
randomly.

REPRESENTATION OF LINKED LISTS IN MEMORY

 Instead of storing a collection of data as an array, we can create a linked list.
 Linked lists are used in many cases, like dynamic data storage, stack and queue implementation or graph
representation etc.
 The main advantage using linked lists is that nodes are stored wherever there is free space in memory; the
nodes do not have continuous memory locations like arrays. Another advantage is when inserting or deleting
nodes, the remaining nodes in the list do not have to be shifted.
 The image below shows how a linked list can be stored in memory.
Head Node Tail Node
tr
Headp 10 20 30 40 50 N

100 200 300 400 500

 The first node in a linked list is called the ‘Head’, and the last node is called the ‘Tail’.
 Each node occupies 4 bytes of memory. 2 bytes are used to store integer value, and 2 bytes are used to store
address of the next node.

23
III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C
 By using linked lists we cannot access a node directly like we can with an array (a[5] for example). To get to node
5 in a linked list, we must start with the first node called "head", use that node's pointer to get to the next node,
and do so while keeping track of the number of nodes we have visited until we reach node 5.

COMPARISON BETWEEN LINKED LIST AND ARRAY

We can store same data elements in memory with the use of either an array or a linked list. Arrays are very
simple data structures that are easy to understand but they have the following disadvantages.

 Array is a fixed size, so arrays cannot be increased or decreased during execution. For example, if we have
allocated space for 5 elements and try to add more than 5 elements we are not able to do. Simillarly if we have
allocated space for 5 elements but are not using the whole space, the unused space goes waste.
 The elements in an array are stored in continuous memory locations, but in many cases the continuous memory
space is not available.
 The operations like insertion and deletion after the specified position may be difficult. It requires each element
after the specified position to be moved one position forward (insertion) or one position backward (deletion).

Linked list can be used to overcome all these disadvantages.

 A linked list can be increased or decreased during the execution of the program.
 There is no problem of shortage of memory as the nodes are stored in different memorylocations.
 In various operations like insertion and deletion no moving of nodes is required.

Arrays Linked List

Arrays are stored in continuous memory Linked lists are not stored in continuousmemory
locations. locations.

Size of an array is fixed. Size of a list is not fixed.

Memory is allocated at compile time. Memory is allocated at run time.

Arrays are required less memory space ascompared to Linked lists require more memory space
linked lists. because it stores both data and address ofthe next
node.

Elements are accessed sequentially or randomly. Elements are accessed only sequentially.

Insertion and deletion operation takes time. Insertion and deletion operation is faster

24
III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C
TYPES OF LINKED LISTS
Linked List:

A linked list is a linear collection of data elements called nodes. Each node contains two fields. Namely,
Data field and Link field. Data field contains the element of the list and link field contains the address of the next
node. In linked lists, each node is connected by using the links. Linked lists are dynamic data structure, i.e. we can
insert or delete nodes whenever we required. There are mainly three types of linked lists. They are:

a) Singly Linked List:

 A singly linked list is a collection of nodes. Each node contains two fields. Namely, Data fieldand Link field.
 The Data field contains the element of the list and Link field contains the address of the nextnode.
 In singly linked lists, the nodes are connected with one link.
 We maintain a pointer called Headptr to store the address of first node of the list.
 In singly linked list, we can travel only in direction from Head node to Tail node. Hence it isalso called as
linear linked list or one-way list.
Head Node Tail Node
Headptr 10 20 30 40 50 N

N1 N2 N3 N4 N5

b) Doubly Linked List:

 A doubly linked list is a collection of nodes. Each node contains three fields. Namely, Left Link
field, Data field and Right Link field.

 The Data field contains the element of the list, Left Link field contains the address of theprevious node and
Right Link field contains the address of the next node.
 In doubly linked list, the nodes are connected with two links.
 We maintain a pointer called Headptr to store the address of first node of the lsit.
 In doubly linked list, we can travel both directions either from Head node to Tail node or Tailnode to Head
node. Hence it is also called as two-way list.
Head Node Tail Node
Headp tr N 10 20 30 N

N1 N2 N3

c) Circular Singly Linked List:

 In a linked list the last node link field contains the address of the first node is called Circularsingly linked list.
 Any node in the list can be choose as Head node and before that node is taken as Tail node.

25
III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C

 In a circular singly linked list, the nodes are connected with one link.
 We maintain a pointer called Headptr to store the address of first node of the list.
Head Node Tail Node
Headp
tr 10 20 30

d) Circular Doubly Linked List:

 In a doubly linked list the last node right link field contains the address of the first node and the first node left
link field contains the address of the last node is called circular doubly linked list.
 Any node in the list can be choose as Head node and before that node is taken as Tail node.
 In circular doubly linked list, the nodes are connected with two links.
 We maintain a pointer called Headptr to store the address of the first node.
Head Node Tail Node
Headptr
10 20 30

Difference between Array and Linked List:

Array Linked List

Array is a collection of elements having same Linked list is an ordered collection of elements
data type with common name. which are connected by links.

Elements can be accessed randomly. Elements cannot be accessed randomly. It can be

accessed only sequentially.

Array elements can be stored in consecutive Linked list elements can be stored at any available
manner in memory. place as address of node is stored in previous node.

Insert and delete operation takes more time in Insert and delete operation cannot take more time.
array. It performs operation in fast and in easy way.

Memory is allocated at compile time. Memory is allocated at run time.

It can be single dimensional, two dimensional or It can be singly, doubly or circular linked list.
multidimensional.

Each array element is independent and does not Location or address of element is stored in the link

26
III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C

have a connection with previous element or with part of previous element or node.
its location.

Array elements cannot be added, deleted once it The nodes in the linked list can be added and
is declared. deleted from the list.

In array, elements can be modified easily by In linked list, modifying the node is a complex
identifying the index value. process.

Pointer cannot be used in array. So, it does not Pointers are used in linked list. Elements are
require extra space in memory for pointer. maintained using pointers or links. So, it requires
extra memory space for pointers.

Applications of linked list:

 Linked list can be used to implement stack operations.

 Linked list can be used to represent graph(adjacency list).
 Lined list can be used to implement queue operations.
 Linked lists can be used for dynamic memory allocation.
 Linked lists are used to represent sparce matrix.
 A polynomial can be represented in a linked list by storing co-efficient and exponent.
 Hash tables are represented using linked list.
 Time sharing operating system uses a circular linked list to run multiple applications.
 Radix sort and Bin sort are the applications of linked list.
 Undo and Redo functionalities in various application softwares performed using double linked list.
 Double linked lists are used in music players for next and previous buttons.
 Double linked lists are used in web brousers for back and forward buttons.
 Circular linked lists are used to develop multi-player games.

27
III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C

UNIT- 3

STACKS AND QUEUES

Stack:
 Stack is a linear list of elements in which elements are inserted and deleted at the same end called top
of the stack.
 Stacks are also called LIFO (Last In First Out) lists, since the last inserted element is removed first.
Eg: Stack of books,Stack of coins .
ADT of a Stack:
AbstractDataType Stack
{
Instances
Linear list of elements
Operations
Empty():Returns true if the stack is empty otherwise returns false.
Size():Returns number of elements in the stack.
Top():Returns top element of the stack.
Pop():Removes top element from the stack.
Push(x):Add the element ‘x’at the top of the stack.
}

Representations of Stack:
There are two methods to represent stacks in the memory.
1. Array Representation
2. Linked Representation
1. Array Representation:
 In the aray representation a stack is represented using a one-dimensional array.
 Array representation is used when the stack contains fixed number of elements.
 The right end of an array is considered as top end where we perform both push and pop operations.
 The index of last element in an array is called top.
 Initially top points to one position less than the lower bound to indicate stack is empty.

28
III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C

Algorithm for Push():

Push(element)
Step 1:[check overflow]
If top=max size-1 then
[Link] “stack is overflow”
[Link]
Step 2:[increment top value by 1]
Top=top+1
Step 3:[Storing element at the top of the stack ]
Stack[top]=element
Step 4:Return
Algorithm for pop():
Step 1 :[check underflow]
If top= -1 then
[Link] “Stack is underflow”
[Link]
Step 2:[decrement top value by 1]
Top=top-1
Step 3:Return
2. Linked Representation:
 An array representation of stacks are useful only when we need fixed size of stacks.
 In several applications size of the stack may vary during the execution of the program.
 In this case we represent the stack using a single linked list.
 In the linked representation first node of the list is the top of the stack.
 Initially top points null which indicates stack is empty.
29
III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C

Algorithm for Push():

Push(item)
Data(newnode)=item
Link(newnode)=top
Top=newnode

Algorithm for Pop():

Pop()
If top=NULL
Print “stack is underflow ”
Return
Else
Top=link[top]
Applications of Stacks:
1. Stacks are used in recursive functions.
2. Stacks are used in evaluation of arithmetic expressions.
Eg:a+(b+c)+(x+y)
3. Stacks are used in conversion of arithmetic expressions.
30
III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C

i. Infix=a+b
ii. Prefix=+ab
iii. Post-fix=ab+
4. Stacks are used to traverse a graph with DFS method (Depth First Search).
5. stacks are used in reversing numbers and strings.
6. stacks are used in calling of multiple functions.
7. Stacks are used to evaluate towers of Hanoi problem.
8. stacks are used in back tracking.
9. Operating system internally uses a stack to manage different kinds of processes.
10. Operating system internally uses a stack in memory management.
Stacks in Recursion
Recursion in stack ADT:-

Recursion which is an implicit application of the STACK ADT.

A recursive function is defined as a function that calls itself to solve a smaller version of its task until a
final call is made which does not require a call to itself. Since a recursive function repeatedly calls itself, it
makes use of the system stack to temporarily store the return address and local variables of the calling
function. Every recursive solution has two major cases. They are

 Base case, in which the problem is simple enough to be solved directly without making any
further calls to the same function.
 Recursive case, in which first the problem at hand is divided into simpler sub-parts. Second the
function calls itself but with sub-parts of the problem obtained in the first step. Third, the result is
obtained by combining the solutions of simpler sub-parts.
Therefore, recursion is defining large and complex problems in terms of smaller and more easily solvable
problems. In recursive functions, a complex problem is defined in terms of simpler problems and the simplest
problem is given explicitly.
To understand recursive functions, let us take an example of calculating factorial of a number. To calculate n!
We multiply the number with factorial of the number that is 1 less than that number. In other words, n! = n X
(n–1)!
Let us say we need to find the value of 5! 5! = 5 X 4 X 3 X 2 X 1
= 120
This can be written as
5! = 5 X 4! Where 4! = 4 X 3!
Therefore,
5! = 5 X 4 X 3!
Similarly, we can also write, 5! = 5 X 4 X 3 X 2!
Expanding further
5! = 5 X 4 X 3 X 2 X 1!

31
III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C

We know, 1! = 1
The series of problems and solutions can be given as shown in Fig.

Now if you look at the problem carefully, we can write a recursive function to calculate the factorial of a
number. Every recursive function must have a base case and a recursive case. For the factorial function
Base case is when n = 1, because if n = 1, the result will be 1 as 1! = 1.
Recursive case of the factorial function will call itself but with a smaller value of n, this case can be given as
factorial (n) = n × factorial (n–1).
#include<stdio.h>
long int fact( int n);
main()
{
long int f;
clrscr();
f=fact(6);
printf(“factorial=%l”,f);
}
long int fact( int n)
{
if ( n <= 1 )
return (1) ;
else
return ( n * fact ( n-1) );
Output:
} Factorial=720

32
III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C

Queues
Queue:
Queue is a linear list of elements in which the elements are inserted at one end called REAR end and deleted
at the same end called FRONT end .Queues are also called FIFO(First In First Out) lists since the first
inserted element is removed first.

Insert
Delete 10 20 30 40 50 60

FRONT REAR
ADT of a queue:
AbstractDataType Queue
{
Instances
Ordered list of elements
Operations :
Empty():Returns true if the queue is [Link] it returns false.
Size():Returns number of elements in the queue.
Front():Returns front end of the queue.
Rear():Returns rear element (last) of the queue.
insert(x):adds the element ‘x’ at the rear end of the queue.
delete():Remove an element from the front end of the queue.
}

Representations of queue:
There are two methods of queue representations. They are
1. Array Representation
2. Linked Representation
1. Array Representation:
 A queue is represented using one-dimensional array when a queue contains fixed number of elements.
 The right end of the array is considered as rear end and the left end of an array is considered as front
end.
 While adding items to the queue the rear end of the queue is increased, while deleting items from the
queue the front end of the queue is increased.
 Initially both front and rear points to -1 which indicates queue is empty.
 If we add an element to the queue for the first time, the front and rear points to zero.

33
III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C

 If the values of front and rear are equal than the queue contains only one element.
 Algorithm for queue insert():

Algorithm for queue delete():

Delete()
Step 1:[check underflow]
If (front= -1) then
Print “queue is underflow”
Return
Step 2:[incrementing front value by 1]
If(front==rear) then
Front=rear= -1
Else
Front=front+1
Step 3:Return
[Link] Representation:
 In array representation of queues are useful only when we need fixed size of queues.
 In several applications the size of the queue may vary during the execution of the program.
 In this case we represent a queue using a single linked list.
 In the linked representation the first node of the list is front end and the last node of the list is rear
end.
 Initially front and rear points null which indicates queue is empty.

34
III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C

Algorithm for Queue insert():

Insert(item)
Data(newnode)=item
Link(newnode=NULL
if(front=NULL) then
Front=rear=newnode
Rear
Else
Link(rear)=newnode
Rear=newnode
End if
Algorithm for queue delete():
Delete()
If(front=NULL) then
Print “queue is
underflow”
Return
Else
If(front=rear) then
Front=rear=NULL
Else
Front=link(front)
End if
End if

Applications of Queues:
 Queues are used to represent graphs with BFS method(Breadth First Search).
 Queues are used in process scheduling.
 Queues are used in first come first serve applications.
 Queues are used in network applications.
 Queues are used while uploading images to the server and downloading images from the server.
 Queues are used in call center phone system.
 Queues are used in online reservation system (railway reservation, bus tickets).
 Queues are used in memory buffer management.
 Queues are used in input, output management.
 Queues are used to maintain the inbox and outbox contents of e-mail.

Circular queue

35
III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C

 The limitation of simple queue is insertion will not be allowed even if there are some vacant locations
at front of the queue.
 To overcome the limitation of simple queue we use a circular queue.
 In a circular queue the rear end is connected back to the front end to make a circle.
 The operations are performed in the circular queue based on First In First Out Method(FIFO)
 Like a simple queue elements are interested in the rear end and the elements are deleted from the front
end.

Representing a Circular Queue using an array

 A circular queue can be implemented using one dimensional array by maintaining two end points
called Front and Rear.
 Initially both front and rear points to -1 which indicates queue is empty
 Each addition of the element will increase the value of rear and each deletion of an element will
decrease the value of front.
 If the value of rear is length-1 the rear value repeats from the lower bound of the queue.
 If the value of front is length-1 the front value repeats from the lower bound of the queue.

36
III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C

Algorithm for Circular queue insert():

Insert(item)
step 1:[check overflow]
if (front= (Rear+1) mod maxsize) then
print “queue is overflow”
return
Step 2:[incrementing rear value by 1]
If(front= -1) then
Front=rear=0
Else
If(rear=length-1)
Rear=0
Else
Rear=rear+1
Step 3:[inserting item to the queue]
Queue[rear]=item
Step 4:return

37
III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C

Algorithm for queue delete():

Delete()
Step 1:[check underflow]
If (front= -1) then
Print “queue is underflow”
Return
Step 2:[incrementing front value ]
If(front==rear) then
Front=rear= -1
Else
If(front=length-1)
front=0
Else
front=front+1
Step 3:Return

DE Queue
 DE queue stands for Double Ended Queue
 DE Queue is one kind of queue in which both insertion and deletion operations are performed at both
front end and rear end.
 DE Queue is also called head and tail queue.

Insert Insert

Delete Delete

Front Rear

 DE queue can be represented in two ways. They are

1. Input Restricted DE queue
2. Output Restricted DE queue

1. Input Restricted DE queue:

In the Input restricted DE queue the insertion is performed only at one end called rear end and deletion
is performed at both front end and rear end.

38
III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C

Insert

Delete Delete

Front Rear

2. Output Restricted DE queue:

In the output restricted DE queue the deletion is performed only at one end called front end and
insertion is performed at both front end and rear end.

Insert Insert

Delete

Front Rear

Algorithm to insert an element to the DE Queue:

addAtRear(item) addAtFront(item)
if(rear=length-1) then if(front=0) then
print “DE Queue is overflow” print “DE Queue is overflow”
return return
else else
if front=-1 then if front=-1 then
front=rear=0 front=rear=0
else else
rear=rear+1 front=front-1
Endif Endif
DQ[rear]=item DQ[front]=item
Endif Endif

39
III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C

Algorithm to delete an element from the DE Queue:

DeleteFromFront() DeleteFromRear()

if(front=-1) then if(front=-1) then

print “DE Queue is underflow” print “DE Queue is underflow”

return return

else else

if front=rear then if front=rear then

front=rear=-1 front=rear=-1

else else

front=front+1 rear=rear-1

Endif Endif

Endif Endif

Priority queue
A priority queue is an abstract data type that behaves similarly to the normal queue except that
each element has some priority, i.e., the element with the highest priority would come first in a priority queue.
The priority of the elements in a priority queue will determine the order in which elements are
removed from the priority queue.
The priority queue supports only comparable elements, which means that the elements are either
arranged in an ascending or descending order.
For example, suppose we have some values like 1, 3, 4, 8, 14, 22 inserted in a priority queue with an ordering
imposed on the values is from least to the greatest. Therefore, the 1 number would be having the highest
priority while 22 will be having the lowest priority.
Characteristics of a Priority queue:-

A priority queue is an extension of a queue that contains the following characteristics:

Every element in a priority queue has some priority associated with it.
An element with the higher priority will be deleted before the deletion of the lesser priority.
If two elements in a priority queue have the same priority, they will be arranged using the FIFO
principle.
Example: We have a priority queue that contains the following values:

1, 3, 4, 8, 14, 22
All the values are arranged in ascending order. Now, we will observe how the priority queue will look after
performing the following operations:
poll(): This function will remove the highest priority element from the priority queue. In the
above priority queue, the '1' element has the highest priority, so it will be removed from the
priority queue.
add(2): This function will insert '2' element in a priority queue. As 2 is the smallest element
among all the numbers so it will obtain the highest priority.
poll(): It will remove '2' element from the priority queue as it has the highest priority queue.
add(5): It will insert 5 element after 4 as 5 is larger than 4 and lesser than 8, so it will obtain the
third highest priority in a priority queue.
Types of Priority Queue
40
III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C

[Link] order priority queue: In ascending order priority queue, a lower priority number is given as a
higher priority in a priority. For example, we take the numbers from 1 to 5 arranged in an ascending order like
1, 2, 3, 4, 5; therefore, the smallest number, i.e., 1 is given as the highest priority in a priority queue.

[Link] order priority queue: In descending order priority queue, a higher priority number is given as
a higher priority in a priority. For example, we take the numbers from 1 to 5 arranged in descending order like
5, 4, 3, 2, 1; therefore, the largest number, i.e., 5 is given as the highest priority in a priority queue.

Applications of Queues

 Data getting transferred between the IO Buffers (Input Output Buffers).

 CPU scheduling and Disk scheduling.
 Managing shared resources between various processes.
 Job scheduling algorithms.
 Round robin scheduling.
 Recognizing a palindrome.

Applications of circular queue

Traffic light functioning is the best example for circular queues. The colors in the traffic light
follow a circular pattern.
In page replacement algorithms, a circular list of pages is maintained and when a page needs to
be replaced, the page in the front of the queue will be chosen.
Applications of Deque
Palindrome checker.
A-steal job scheduling algorithm
- The A-steal algorithm implements task scheduling for multiple processors (multiprocessor scheduling).
- The processor gets the first element from the double ended queue.
- When one of the processors completes execution of its own thread, it can steal a thread from other
processors.
- It gets the last element from the deque of another processor and executes it.
41
III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C

Undo-redo operations in software applications.

Applications of Priority Queue

Prim's algorithm implementation can be done using priority queues.

Dijkstra's shortest path algorithm implementation can be done using priority queues.
A Search algorithm implementation can be done using priority queues.
Priority queues are used to sort heaps.
Priority queues are used in operating system for load balancing and interrupt handling.
Priority queues are used in Huffman codes for data compression.
In traffic light, depending upon the traffic, the colours will be given priority.

42
III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C

UNIT-IV
SEARCHING AND SORTING

 Searching is an operation which is designed for looking desired information.

 Searching plays important role in the information retrieval.
 There are several methods available to search desired information. some of them are
1. Sequential search or Linear search
2. Binary search.

Sequential search or linear search

 Sequential search is a simplest searching technique among all searching techniques.
 This searching technique is applicable when data is stored in a linear data structure (arrays, stacks etc).
 Sequential search or linear search is a method for finding a target value within a list.
 It sequentially checks each element until the target value is found.
 The minimum number of comparisons is 1 when the desired element is at first location and the
maximum number of comparisons is N (number of elements in the list) when the desired element is at
last location.
Advantages:
 It is simple and conventional method to search desired data.
 It is applicable on both sorted and unsorted data.
Disadvantages:
 It is inefficient when there is large number of elements in the list.
 It is time consuming searching technique.
Algorithm:
Linear_Search(A:list of elements,k:searching elements)
n=length(A)
found=false
i=1
While(i<=n&&found=false)
If(A[i]=k)
Found=true
Break
End if
I=I+1
End while
If(found=true)
Print “element found at” +i
Else
Print “element not found”
End if

Example:

43
III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C

List: 10 14 19 26 27 31 33 35 42 44
Searching element: 27

Element found at 5th location.

Binary Search
 Binary search is a fast searching method when compared to other searching methods.
 This search method works on the principle of divide and conquers method.
 This searching method works properly on the sorted data.
 Binary search looks a particular element by comparing middle most element in the list.
 If a middle element is a searching element the index of the middle element is returned.
 If the middle element greater than the searching element, then the element is searched in the sub list to
the left of the middle element.
 If the middle element is less than the searching element, then the element is searched in the sub list to
the right of the middle element.
 This process is continued up to the sub list size becomes zero.

Algorithm:
BinarySearch (A:list of sorted elements,K:element to be searched)
n=length(A)
lower bound=1
upper bound=n

while true

44
III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C

if upperbound<lowerbound then
print ”element not found”
return
end if
mid=(lowerbound+upperbound)/2
if A[mid]>k then
lowerbound=mid+1
else
if A[mid]>k then
upperbound=mid-1
else
if A[mid]=k then
print “element found at ”+mid
return
end if
end if
end if
end while
Example:
List 10 14 19 26 27 31 33 35 42 44
Element to be search k=42
1st Pass
1 2 3 4 5 6 7 8 9 10
10 14 19 26 27 31 33 35 42 44

LowerBound Mid upperbound

Mid =(lpwer bound+upper bound)/2
=(1+10)/2
=11/2
=5
27<42 then lowerbound =mid+1
=5+1
=6

2ndpass

1 2 3 4 5 6 7 8 9 10
31 33 35 42 44

lowerbound Mid upperbound

Third pass
1 2 3 4 5 6 7 8 9 10
42 44

45
III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C

Mid
upperbound
lowerbound
Mid =(lpwer bound+upper bound)/2
=(9+10)/2
=19/2
=9
42=42 Element found at mid i.e=8

Sorting
Sorting: Sorting is a mechanism of arranging the data either in ascending or descending order. All the sorting
methods performs the following two steps.
[Link] two values.
[Link] two values.
Sorting techniques:
[Link] sort
[Link] sort
[Link] sort
[Link] sort
[Link] sort
[Link] sort or bucket sort
[Link] sort

Bubble sort
 Bubble Sort is a simple sorting method used to sort a given set of elements.
 Bubble Sort compares all the elements one by one and sort them based on their values.
 Bubble sort will start by comparing the first element with the second element, if the first element is
greater than the second element, it will swap both the elements, and then move on to compare the
second and the third element, and so on.
 If we have total n elements, then we need to repeat this process for n-1 passes.
 In each pass each pair of adjacent elements are compared and swapped if they are not in order.
 In the 1st pass the first maximum fixed at nth position. In the second pass the second maximum fixed at
n-1th position. This process is continued for n-1 passes.
 In each pass bubble sort makes n-i comparisons where n is number of elements and i is the pass
number.
Advantages:
 Easy to understand.
 Easy to implement.
 In-place, no external memory is needed.
 Performs greatly when the elements are almost sorted.
Disadvantages
 It does more element assignments.
46
III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C

 Slow in process
 It does not deal well with a list containing a huge number of items.
 Not suitable for real life applications.
Algorithm:
Bubblesort( A: List of elements)
n=length(A)
for i= 1 to n-1
for j=1 to n-i
if(A[j]>A[j+1]) then
temp=A[j]
A[j]=A[j+1]
A[j+1]=temp
End if
End for
End for
Return A
Elements before Sorting:

54 26 93 17 31 44 55 20

1st Pass

Element
s after
Sorting:

17 20 26 31 44 54 55 20

47
III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C

Selection Sort
 Selection sort improves on bubble sort by reducing number of swapping but number of comparisons
and passes remains same.
 Selection sort makes n-1 passes and make one swap in each pass.
 This sorting is also comparison based sorting technique in which the list is divided into two parts:
sorted part and unsorted part.
 Sorted part is located at left and unsorted part is located at right side.
 Initially sorted part is empty and unsorted part is entire list.
 In the first pass the first minimum is fixed at the first position of the sorted part.
 In the second pass the second minimum is fixed at the second position of the sorted part.
 This process is continued up to unsorted part becomes empty.
Elements before Sorting:

54 26 93 17 31 44 55 20
1st Pass

Ele
me
nts
Aft
er
Sor
ting
:

54 26 93 17 31 44 55 20

48
III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C

Advantages:
 Easy to understand.
 Easy to implement.
 In-place, no external memory is needed.
 Minimum number of swappings.

Disadvantages
 It does more element assignments.
 Slow in process.
 Poor efficiency when dealing with a huge list of items.
 Not suitable for real life applications.
Algorithm:
SelectionSort( A: List of elements)
n=length(A)
for i= 1 to n-1
min=i
for j=i+1 to n-1
if(A[min]>A[j]) then
min=j
End if
End for
If i≠min then
temp=A[i]
A[i]=A[min]
A[min]=temp
End if
End for
Return A

Insertion sort
 Insertion sort is a simple and efficient sorting method than bubble sort and selection sort.
 This sorting method reduces number of comparisons and number of swapping than bubble sort and
selection sort.
 This method is useful and best when the number of elements in the list is small.
 It can also be useful when the list is almost sorted [Link] few elements are misplaced.
 This is an in-place comparison based sorting method in which the list is divided into two parts: sorted
and unsorted part.
 The sorted part is at left side and the unsorted part is at right side.
 Initially the left part contains first element and the right part contains the remaining elements.
 In the first pass the second element is inserted in its appropriate place in the sorted part(left part).In the
second pass the third element is inserted in its appropriate place in the sorted part.

49
III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C

 This process is continued up to the unsorted part becomes empty.

Example:

Advantages:
 It is simple to implement.
 It is efficient on small data values.
 It is efficient on data nearly sorted.
 It is efficient when number of elements is small.
Disadvantages:
 It is less efficient if the list contains more number of elements.
 If the number of elements is increased the program would be slow.

Algorithm:
Insertion(A:list of elements)
n=length(A)
for i=2 to n
temp=A[i]
j=i
while(j>1 && A[j-1] >=temp)
A[j]=A[j-1]
J=j-1
End while
A[j]=temp
End for
Return A

50
III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C

Merge Sort
 Merge sort is a sorting technique based on divide and conquer method.
 Merge sort divides the list into equal parts and then combine them in a sorted manner.
 This sorting method requires additional memory space for storing sub lists before merging.
 However merge sort is effective while sorting huge amount of data.
Advantages:
 Uses fewer comparisons than the quick sort.
 Stable when the list contains similar elements.
 Stable when the list is already sorted.
 Stable when the list contains huge amount of data.
Disadvantages:
 Extra memory space is required.
 Time consuming sorting.
Algorithm:

51
III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C

Quick
sort
 Quick sort is most advanced sorting and complicated sorting than other sorting methods.
 The basic concept in quick sort is to pick one element in the list as a pivot, around which the other
elements are rearranged.
 Everything less than the pivot is moved to the left of the pivot.
 Everything greater than the pivot is moved to the right of the pivot.
 At this point each partition is recursively quick [Link] left and right side partitions are again
partitioned into sub partitions with two pivots.
 This process will be continued upto the elements are arranged in a sorted order.
 Quick sort is the fastest sorting method because it uses divide and conquer method.
Algorithm:
1. Choose a pivot value: Take any value as a pivot in the list.
2. Partition:
 The elements which are less than the pivot place them at left side of the pivot.
 The elements which are greater than the pivot place them at right side of the pivot.
3. Sort both sides: Apply quick sort algorithm for both left and right side partitions.

52
III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C

Advantages:
 Fastest sorting technique.
 In-place, no external memory is needed.
 Performs greatly when list contains huge amount of data.
Disadvantages:
 Difficult to partition.
 Efficiency of sorting is depends on the pivot selection.

Example:

53
 III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C

UNIT-V

TREES AND GRAPHS

TREE DEFINITION:

 Tree is a hierarchical Or Non-linear data structure which stores the information naturally in the form of
hierarchy style.
 Tree is one of the most powerful and advanced data structures.
 It is a non-linear data structure compared to arrays, linked lists, stack and queue.
 It represents the nodes connected by edges.

The above figure represents structure of a tree. Tree has 2 sub trees.
A is a parent of B and C.
B is called a child of A and also parent of D, E, F.
BASIC TREE TERMINOLOGY :

o Root: The root node is the topmost node in the tree hierarchy. In other words, the root node is the one
that doesn't have any parent. In the above structure, node numbered 1 is the root node of the tree. If a
node is directly linked to some other node, it would be called a parent-child relationship.

o Child node: If the node is a descendant of any node, then the node is known as a child node.

o Parent: If the node contains any sub-node, then that node is said to be the parent of that sub-node.

o Sibling: The nodes that have the same parent are known as siblings.

o Leaf Node:- The node of the tree, which doesn't have any child node, is called a leaf node. A leaf
node is the bottom-most node of the tree. There can be any number of leaf nodes present in a general
tree. Leaf nodes can also be called external nodes.

o Internal nodes: A node has atleast one child node known as an internal

54
 III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C

o Ancestor node:- An ancestor of a node is any predecessor node on a path from the root to that node.
The root node doesn't have any ancestors. In the tree shown in the above image, nodes 1, 2, and 5 are
the ancestors of node 10.

o Descendant: The immediate successor of the given node is known as a descendant of a node. In the
above figure, 10 is the descendant of node 5.

Advantages of Tree
 Tree reflects structural relationships in the data.
 It is used to represent hierarchies.
 It provides an efficient insertion and searching operations.
 Trees are flexible. It allows to move subtrees around with minimum effort.

Binary Tree in Data Structure

 Binary tree is a special type of data structure. In binary tree, every node can have a maximum of 2
children, which are known as Left child and Right Child.
 It is a method of placing and locating the records in a database, especially when all the data is known
to be in random access memory (RAM).

 Definition:
"A tree in which every node can have maximum of two children is called as Binary Tree."

The above tree represents binary tree in which node A has two children B and C. Each children have
one child namely D and E respectively.

Representation of Binary Tree using Array

 Binary tree using array represents a node which is numbered sequentially level by level from left to
right. Even empty nodes are numbered.

55
 III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C

Array index is a value in tree nodes and array value gives to the parent node of that particular index or
node.
 Value of the root node index is always -1 as there is no parent for root.
 When the data item of the tree is sorted in an array, the number appearing against the node will work
as indexes of the node in an array.

 Location number of an array is used to store the size of the tree.

 The first index of an array that is '0', stores the total number of nodes.
 All nodes are numbered from left to right level by level from top to bottom.
 In a tree, each node having an index i is put into the array as its i th element.
 The above figure shows how a binary tree is represented as an array.
 Value '7' is the total number of nodes. If any node does not have any of its child, null value is stored at
the corresponding index of the array.

Binary Search Tree (BST)

 Binary search tree is a binary tree which has special property called BST.
 BST property is given as follows:
For all nodes A and B,

I. If B belongs to the left subtree of A, the key at B is less than the key at A.

II. If B belongs to the right subtree of A, the key at B is greater than the key at A.

Each node has following attributes:

I. Parent (P), left, right which are pointers to the parent (P), left child and right child respectively.

II. Key defines a key which is stored at the node.

Definition:

"Binary Search Tree is a binary tree where each node contains only smaller values in its left subtree and only
56
 III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C

larger values in its right subtree."

 The above tree represents binary search tree (BST) where left subtree of every node contains smaller values
and right subtree of every node contains larger value.
 Binary Search Tree (BST) is used to enhance the performance of binary tree.
 It focuses on the search operation in binary tree.
Note: Every binary search tree is a binary tree, but all the binary trees need not to be binary search trees.

Binary Search Tree Operations

Following are the operations performed on binary search tree:

1. Insert Operation:

 Insert operation is performed with O(log n) time complexity in a binary search tree.
 Insert operation starts from the root node. It is used whenever an element is to be inserted.
The following algorithm shows the insert operation in binary search tree:

Step 1: Create a new node with a value and set its left and right to NULL.

Step 2: Check whether the tree is empty or not.

Step 3: If the tree is empty, set the root to a new node.

Step 4: If the tree is not empty, check whether a value of new node is smaller or larger than the
node (here it is a root node).
Step 5: If a new node is smaller than or equal to the node, move to its left child.

Step 6: If a new node is larger than the node, move to its right child.

Step 7: Repeat the process until we reach to a leaf node.

57
 III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C

The above tree is constructed a binary search tree by inserting the above elements {50, 80, 30, 20,
100, 75, 25, 15}. The diagram represents how the sequence of numbers or elements are inserted into
a binary search tree.

2. Search Operation :

 Search operation is performed with O(log n) time complexity in a binary search tree.
 This operation starts from the root node. It is used whenever an element is to be searched.
The following algorithm shows the search operation in binary search tree:

Step1: Read the element from the user .

Step2: Compare this element with the value of root node in a tree.

Step 3: If element and value are matching, display "Node is Found" and terminate the function.
Step 4: If element and value are not matching, check whether an element is smaller or larger than a node
value.

Step 5: If an element is smaller, continue the search operation in left subtree.

Step 6: If an element is larger, continue the search operation in right subtree.

Step 7: Repeat the same process until we found the exact element.

Step 8: If an element with search value is found, display "Element is found" and terminate the function.

Step 9: If we reach to a leaf node and the search value is not match to a leaf node, display "Element is not
found" and terminate the function.

58
III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C

Binary Tree Traversal

Binary tree traversing is a process of accessing every node of the tree and exactly once. A tree is defined in a
recursive manner. Binary tree traversal also defined recursively.
There are three techniques of traversal:
1. Preorder Traversal
2. Postorder Traversal
3. Inorder Traversal

1. Preorder Traversal:

Algorithmforpreordertraversal

Step1: StartfromtheRoot.

Step2: Then,gototheLeftSubtree.

Step3: Then,gototheRightSubtree.

The above figure represents how preorder traversal actually works.

Following steps can be defined the flow of preorder traversal:

Step 1 : A + B (B + Preorder on D (D + Preorder on E and F)) + C (C + Preorder on G and H)

Step 2 : A + B + D (E + F) + C (G + H)

Step 3 : A + B + D + E + F + C + G + H

Preorder Traversal : A B C D E F G H

2. Post order Traversal:

Algorithm for post order traversal:

Step 1 : Start from the Left Subtree (Last Leaf).

59
III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C

Step 2 : Then, go to the Right Subtree.

Step 3 : Then, go to the Root.

The above figure represents how post order traversal actually works.

Following steps can be defined the flow of postorder traversal:

Step 1 : As we know, preorder traversal starts from left subtree (last leaf) ((Postorder on E + Postorder on F)
+ D + B )) + ((Postorder on G + Postorder on H) + C) + (Root A)

Step 2 : (E + F) + D + B + (G + H) + C + A

Step 3 : E + F + D + B + G + H + C + A

Postorder Traversal : E F D B G H C A

3. In order Traversal:

Algorithm for in order traversal :

Step 1 : Start from the Left Subtree.

Step 2 : Then, visit the Root.

Step 3 : Then, go to the Right Subtree.

60
III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C

The above figure represents how inorder traversal actually works.

Following steps can be defined the flow of inorder traversal:

Step 1 : B + (Inorder on E) + D + (Inorder on F) + (Root A ) + (Inorder on G) + C (Inorder on H)

Step 2 : B + (E) + D + (F) + A + G + C + H

Step 3 : B + E + D + F + A + G + C + H

Inorder Traversal : B E D F A G C H

Properties of Binary Tree

o At each level of i, the maximum number of nodes is 2 i.

o The height of the tree is defined as the longest path from the root node to the leaf node. The tree which
is shown above has a height equal to 3. Therefore, the maximum number of nodes at height 3 is equal
to (1+2+4+8) = 15. In general, the maximum number of nodes possible at height h is (2 0 + 21 +
22+….2h) = 2h+1 -1.

o The minimum number of nodes possible at height h is equal to h+1.

o If the number of nodes is minimum, then the height of the tree would be maximum. Conversely, if the
number of nodes is maximum, then the height of the tree would be minimum.

If there are 'n' number of nodes in the binary tree.

The minimum height can be computed as:

As we know that,

n = 2h+1 -1

n+1 = 2h+1

Taking log on both the sides,

log2(n+1) = log2(2h+1)

log2(n+1) = h+1

h = log2(n+1) - 1

The maximum height can be computed as:

61
III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C

As we know that,

n = h+1

h= n-1

Applications of trees

The following are the applications of trees:

o Storing naturally hierarchical data: Trees are used to store the data in the hierarchical structure. For
example, the file system. The file system stored on the disc drive, the file and folder are in the form of
the naturally hierarchical data and stored in the form of trees.

o Organize data: It is used to organize data for efficient insertion, deletion and searching. For example,
a binary tree has a logN time for searching an element.

o Trie: It is a special kind of tree that is used to store the dictionary. It is a fast and efficient way for
dynamic spell checking.

o Heap: It is also a tree data structure implemented using arrays. It is used to implement priority
queues.

o B-Tree and B+Tree: B-Tree and B+Tree are the tree data structures used to implement indexing in
databases.

o Routing table: The tree data structure is also used to store the data in routing tables in the routers.

62
III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C

GRAPHS

Graph Data Structure & Graph Terminology

Graph Data structure:
 A Graph is a non-linear data structure consisting of nodes and edges.
 The nodes are sometimes also referred to as vertices and the edges are lines or arcs that
connect any two nodes in the graph.

More formally a Graph can be defined as,

 A graph is a pictorial representation of a set of objects where some pairs of objects are
connected by links.
 The interconnected objects are represented by points termed as vertices, and the links that
connect the vertices are called edges.

 Formally, a graph is a pair of sets (V, E), where V is the set of vertices and E is the set of
edges, connecting the pairs of vertices.
 In the above Graph, the set of vertices V = {0,1,2,3,4} and the set of edges E = {01, 12, 23,
34, 04, 14, 13}.
 Take a look at the following graph −

In the above graph,

V = {a, b, c, d, e}
E = {ab, ac, bd, cd, de}

Basic Graph Terminology:-

Mathematical graphs can be represented in data structure. We can represent a graph using an array
of vertices and a two-dimensional array of edges.

63
 III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C

 Nodes: These are the most important components in any graph. Nodes are entities whose
relationships are expressed using edges. If a graph comprises 2 nodes A and B and an
undirected edge between them, then it expresses a bi-directional relationship between the
nodes and edge.
 Vertex − Each node of the graph is represented as a vertex. In the following example, the
labeled circle represents vertices. Thus, A to G are vertices. We can represent them using
an array as shown in the following image. Here A can be identified by index 0. B can be
identified using index 1 and so on.
 Edge − Edge represents a path between two vertices or a line between two vertices. In the
following example, the lines from A to B, B to C, and so on represents edges. We can use
a two-dimensional array to represent an array as shown in the following image. Here AB
can be represented as 1 at row 0, column 1, BC as 1 at row 1, column 2 and so on, keeping
other combinations as 0.
 Adjacency − Two node or vertices are adjacent if they are connected to each other through
an edge. In the following example, B is adjacent to A, C is adjacent to B, and so on.
 Path − Path represents a sequence of edges between the two vertices. In the following
example, ABCD represents a path from A to D.

Basic Operations:

Following are basic primary operations of a Graph −

 Add Vertex − Adds a vertex to the graph.
 Add Edge − Adds an edge between the two vertices of the graph.
 Display Vertex − Displays a vertex of the graph.

Types of Graphs

Directed Graph:

 If a graph contains ordered pair of vertices, is said to be a Directed Graph.

 If an edge is represented using a pair of vertices (V1, V2), the edge is said to be directed from V1 to
V2.

64
 III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C

 The first element of the pair V1 is called the start vertex and the second element of the pair V 2 is
called the end vertex.

Set of Vertices V = {1, 2, 3, 4, 5, 5}

Set of Edges W = {(1, 3), (1, 5), (2, 1), (2, 3), (2, 4), (3, 4), (4, 5)}

Undirected Graph:

 If a graph contains unordered pair of vertices, is said to be an Undirected Graph.

 In this graph, pair of vertices represents the same edge.
Set of verticesV={1,2,3,4,5}

Set of Edges E = {(1, 2), (1, 3), (1, 5), (2, 1), (2, 3), (2, 4), (3, 4), (4, 5)}

 In an undirected graph, the nodes are connected by undirected arcs.

 It is an edge that has no arrow. Both the ends of an undirected arc are equivalent, there is no head
or tail.

Applications of Graphs:

 Graphs are used to represent many real-life applications:

 Graphs are used to represent networks.
 The networks may include paths in a city or telephone network or circuit network.
Graphs are also used in social networks like linkedIn, Facebook.
 For example, in Facebook, each person is represented with a vertex(or node).
 Each node is a structure and contains information like person id, name, gender, and
locale. Following is an example of an undirected graph with 5 vertices.

65
 III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C

Graph and its Representations:

A graph is a data structure that consists of the following two components:
1. A finite set of vertices also called as nodes.
2. A finite set of ordered pair of the form (u, v) called as edge.
 The pair is ordered because (u, v) is not the same as (v, u) in case of a directed graph(di-
graph).
The pair of the form (u, v) indicates that there is an edge from vertex u to vertex v. The edges may
contain weight/value/cost.
The following two are the most commonly used representations of a graph.
1. Adjacency Matrix
2. Adjacency List
There are other representations also like, Incidence Matrix and Incidence List. The choice of graph
representation is situation-specific. It totally depends on the type of operations to be performed and
ease of use.
Adjacency Matrix:
 Adjacency matrix is best for dense graph, but for sparse graph, it is not required.
 Adjacency matrix is good solution for dense graph which implies having constant number
of vertices.
 Adjacency matrix of an undirected graph is always a symmetric matrix which means an
edge (i, j) implies the edge (j, i).

66
III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C

 The above graph represents undirected graph with the adjacency matrix representation. It
shows adjacency matrix of undirected graph is symmetric. If there is an edge (2, 4), there is
also an edge (4, 2).

 Adjacency matrix of a directed graph is never symmetric adj[i][j] = 1, indicated a directed

edge from vertex i to vertex j.

 The above graph represents directed graph with the adjacency matrix representation.
 It shows adjacency matrix of directed graph which is never symmetric.
 If there is an edge (2, 4), there is not an edge (4, 2). It indicates direct edge from vertex i to
vertex j.

Advantages of Adjacency Matrix:

 Adjacency matrix representation of graph is very simple to implement.

 Adding or removing time of an edge can be done in O(1) time.
 Same time is required to check, if there is an edge between two vertices.
 It is very convenient and simple to program.

67
III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C

Disadvantages of Adjacency Matrix:

 It consumes huge amount of memory for storing big graphs.

 It requires huge efforts for adding or removing a vertex.
 If you are constructing a graph in dynamic structure, adjacency matrix is quite slow for big
graphs.
Adjacency List:
 Adjacency list is another representation of graphs.
 It is a collection of unordered list, used to represent a finite graphs.
 Each list describes the set of neighbors of a vertex in the graph.
 Adjacency list requires less amount of memory.
 For every vertex, adjacency list stores a list of vertices, which are adjacent to the current one.
 In adjacency list, an array of linked list is used. Size of the array is equal to the number of
vertices.

 In adjacency list, an entry array[i] represents the linked list of vertices adjacent to the
ith vertex.
 Adjacency list allows to store the graph in more compact form than adjacency matrix.
 It allows to get the list of adjacent vertices in O(1) time.
Disadvantages of Adjacency List:

 It is not easy for adding or removing an edge to/from adjacent list.

 It does not allow to make an efficient implementation, if dynamically change of vertices
number is required.

MINIMUM SPANNING TREE(MST)

 A minimum spanning tree is a special kind of tree that minimizes the lengths (or “weights”)
of the edges of the tree.

68
III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C

 An example is a cable company wanting to lay line to multiple neighborhoods; by

minimizing the amount of cable laid, the cable company will save money.

A tree has one path joins any two vertices. A spanning tree of a graph is a tree that:
 Contains all the original graph’s vertices.
 Reaches out to (spans) all vertices.
 Is acyclic. In other words, the graph doesn’t have any nodes which loop back to itself.
 A Spanning tree can be defined as a subset of a graph, which consists of all the vertices
covering minimum possible edges and does not have a cycle. Spanning tree cannot be
disconnected.

 Every connected and undirected graph has at least one spanning tree.

 A disconnected graph does not have a spanning tree as it is not possible to include all
vertices.

There are two most popular algorithms that are used to find the minimum spanning tree in a
graph.
They include:
 Kruskal’s algorithm
 Prim’s algorithm

Kruskal’s Algorithm
Kruskal’s algorithm is an algorithm to find the MST in a connected graph.

Kruskal’s algorithm finds a subset of a graph G such that:

 It forms a tree with every vertex in it.
 The sum of the weights is the minimum among all the spanning trees that can be formed
from this graph.
The sequence of steps for Kruskal’s algorithm is given as follows:
1. First sort all the edges from the lowest weight to highest.
2. Take edge with the lowest weight and add it to the spanning tree. If the cycle is created,
discard the edge.
3. Keep adding edges like in step 1 until all the vertices are considered.

Prim’s Algorithm
 Prim’s algorithm is yet another algorithm to find the minimum spanning the tree of a graph.

 In contrast to Kruskal’s algorithm that starts with graph edges, Prim’s algorithm starts with
a vertex.

 We start with one vertex and keep on adding edges with the least weight till all the vertices
are covered.

The sequence of steps for Prim’s Algorithm is as follows:

1. Choose a random vertex as starting vertex and initialize a minimum spanning tree.
2. Find the edges that connect to other vertices. Find the edge with minimum weight and add
it to the spanning tree.
3. Repeat step 2 until the spanning tree is obtained.

69
III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C

Traversing and searching a graph

Traversing and searching a graph means that the systematic accessing of all the vertices of a
graph. There are two methods to traverse and search a graph. They are:
- Depth-First search(DFS)
- Breadth-First Search(BFS)
Depth-First Search:- Depth first search involves for choosing a node in which a searching process is
started. Then access the neighbouring nodes of the start. This process continues until we reach the null
node of the graph. It uses the stack operation. The algorithm which is used to implement graph
traversing searching is as follows.
Algorithm : DFSStep 1: Start

Step 2 : Initialize all nodes to ready state.

Step 3 : Push the starting node into the stack

Step 4 : Repeat step 5-6 until the stack is empty.

Step 5 : Pop the top node from stack and change status of the node.

Step 6 : Push all the neighbouring nodes and change their status is weighting.

Step 7 : Stop

A push initial node into the stack

stack :
A
pop and print element A and push neighbouring node
into the
C B stack
Stack : C D B
pop and print element B and push neighbouring nodes
into the
D stack
Stack : C D F
pop and print element F and push neighbouring node
E F into the stack
Stack : C D E
pop and print all elements because stack is full
output
A->B -> F -> E -> D -> C

Breadth First Search(BFS) :- Breadth first search involves for choosing a node from the point. These
process continues until we reach null node. It uses the queue operations. The algorithm whichis used to
implements breadth first search method is as follows.

70
III SEM BSC DR C V RAMAN DEGREE COLLEGE DATA STRUCTURES USING C

Algorithm : BFS

Step 1: Start

Step 2 : Initialize all nodes to ready state.

Step 3 : Insert the starting node into the queue

Step 4 : Repeat step 5-6 until the queue is empty.

Step 5 : Remove the 1st node and print

Step 6 : Add the neighbouring nodes to the queue.

Step 7 : Stop

71
DR. C V RAMAN DEGREE COLLEGE III SEM BSC DATA STRUCTURES USING C

72