ABHYUDAYA MAHILA DEGREE COLLEGE

WITH C
affiliated to Acharaya Nagarjuna University

BSC- II SEM

P.Y.KUMAR
M.C.A,M.Tech,M.Phil..,
 www.anuupdates.org
2
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

This Book is dedicated to my Daughter and my friend A.kotiah. May God

Bless you and be with you little one!
 www.anuupdates.org
3
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
 www.anuupdates.org
4
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

DATA REPRESENTATION
Various methods are used to represent data in computers. Hierarchical
layers of data structure are used to make the use of data structure easy and
efficient. The basic unit of data representation is a bit. The value of a bit
asserts one of the two mutually exclusive possibilities–0 or 1. Various
combinations of two values of a bit are used to represent data in a different
manner in different systems. Eight bits together form one byte which
represents a character and one or more than one characters are used to
form á string. A string can thus be seen as a data structure that emerges
through several layers of data structures

The representation of a string can be made easier (i.e. working with the
strings without bothering about the NULL (‘\0’) character at the end of the
string) by wrapping it into another data structure which takes care of such
intricacies and supports a set of operations that allows us to perform
various string related operations like storing and fetching a string joining
two strings, finding the length of strings, etc The use of the concrete data
structure during design creates lot of difficulties and requires much. more
efforts, such a problem can be avoided by using abstract data type in the
design process. Bui before moving to the discussion of concepts of Abstract
Data Types (ADTS), let us discuss how the primitive or basic data types of
any language (i.e. integer, character, etc.) are internally represented in the
memory
 www.anuupdates.org
5
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

Integer Representation
An integer is the basic data type which is commonly used for storing
negative as well as non-negative integer numbers. The non-negative data is
represented using binary number system. In this, each bit position
represents the power of 2. The rightmost bit position represents 2" which is
1, the next represents 2 which is 2, then 2' which is 4 and so on. For
example, 00100110 represents the integer as 2' + 2- + 2 = 2 + 4 + 32 = 38.
For negative binary numbers the methods of representation used are one's
complement and two's complement
In one's complement method the number is represented by complementing
each bit, i.e. changing each bit in its value to the opposite bit setting. For
example, 00100 | 10 represents 38, after complementing, it becomes
1101100 1 which is used to represent -38.
In two's complement method, 1 is added to one's complement representation
of the negative number. For example. -38 is represented by 1101100 1
which on adding 1 to it will become

11011001
+1
11011010, which represents –38 in Ino's complement notation

Real Number Representation

The method used to represent real numbers in computers is floating-point
notation. In this notation, the real number is represented by a number called
a mantissa, times a base raised to an integer power, callcd an exponent. For
example, if thc base is fixed as 10, the number 209.52 could be represented as 20952 X
10The mantissa is 20952 and exponent is - 2. Both the mantissa and exponents are
two'scomplement binary integers. For example, 20952 can be
represented as 10100011101 | in binary forin.
Therefore, the 24 bit representation of the number will be
00000000101000111011 and 8 bit two's complement binary representation of -2 is
1111111 0; thus, the number is represented as 0 0000000101000111011111111 10.
Character Representation
The information in computers is not always interpreted numerically. For example, to
store the salary of an employee we use the integer representation of the data but with
salary we also need to store the name of the employee which requires a different
data representation. Such information is usually represented in character
string form. There are different codes available to store data in character
form such as BCD, EBCDIC and ASCII.
For example, if 8 bits are used to represent a character, then up to 28=256
different characters can be represented as bil pallers. I 1000000 is used to
represent the character A* and 1 1000001 is used to represent character 'B'.
 www.anuupdates.org
6
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
Then, finally AB can be représented as 1100000011000001

ATOMIC TYPE
Generally, a data structure is represented by a memory block, which has
two parts:

 Data storage
 Address storage
This facilitates in storing the data and relating it to some other data by
means of storing pointers in the address part.
An atomic type data is a data structure that contains only the data items
and not the pointers. Thus, for a list of data items, several atomic type
nodes may exist each with a single data item coresponding to one of the
legal data types. The list is maintained using a list node which contains
pointers to these atomic nodes and a type indicator indicating the type of
atomic node to which it points. Whenever a test node is inserted in the list,
its address is stored in the next free element of the list of pointers.

a list of atomic nodes maintained using list of nodes. In each node, type represents
the type of data stored in the atomic node to which the list node points. I
stands for integer type, 2 for real number and 3 for character type or any
different assumption can be made at implementation level to indicate different data
types.

DIFFERENCE BETWEEN ABSTRACT DATA YPES, DATA

TYPES AND DATA STRUCTURES
To avoid the confusion between abstract data types, data types, and data
structures, it is relevant to understand the relationship between the three

 An abstract data type is the specification of the data type which

specifies the logical and mathematical model of the data type.
 A data type is the implementation of an abstract data type:
 www.anuupdates.org
7
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

 Data structure refers to the collection of computer variables that are

connected in some specific manner.
Thus, there seems to be an open relationship between the three, that is, a
data type has its root in the abstract data type and a data structure
comprises a set of computer variables of same or different data types.

REFINEMENT STAGES
The best approach to solve a complex problem is to divide it into smaller
parts such that each part becomes an independent module which is easy to
manage. An example of this approach is the System Development Life Cycle
(SDLC) methodology. This helps in understanding the problem, analyzing
solutions, and handling the problems efficiently.
The principle underlying writing large programs is the top-down refinement.
While writing the main program, we decide exactly how the work will be
divided into various functions and then, in the refinement process, it is
further decided what will be the task of each function, and what inputs are
to be given and results to be obtained. The data and actions of the
functions are specified precisely. Similarly, the purpose of studying Abstract
data types is to find out some general principles that will help in designing
efficient programs. There exists a similarity between the process of top down
refinement of algorithms and the top-down specification of the data
structures. In algorithm design, we begin with the problem and slowly
specify more details until we develop a complete program. In data
specification, we begin with the selection of mathematical concepts and
abstract data types required for our problem, and slowly specify more details
until finally we can describe our data structures in terms of programming
language.
The application or the nature of problem determines the number of
refinement stages required in the specification process. Different problems
have different number of refinement stages, but in general, there are four
levels of refinement processes:
 Conceptual or abstract level
 Algorithmic or data structures
 Programming or implementation
 Applications
Conceptual Level
At this level we decide how the data is related to each other, and what
operations are needed. Details about how to store data and how various
operations are performed on that data are not decided at this level
 www.anuupdates.org
8
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

Algorithmic or Data Structure Level

At data structure level we decide about the operations on the data as needed
by our problem. For example, we decide what kind of data structure will be
required to solve the problem-contiguous list will be preferred for finding the
length of a list, or for retrieving any element, whereas for the evaluation of
any expression into prefix or postfix, stacks will be used.
Programming or Implementation Level
At implementation level, we decide the details of how the data structures will
be represented in the computer memory. For example, we decide whether
the linked lists will be implemented with pointers or with the cursors in an
array.
Application Level
This level settles all details required for particular application such as
names for variables or special requirements for the operations imposed by
applications

The first two levels are often called conceptual. The middle two levels can be
called algorithmic as they are concerned with representing data and the
operations performed on the same. Last level is basically concerned with
programming

at the conceptual level, the queue has been selected as an abstract data type
and further at the next level circular queue has been selected, as this could
provide the best solution. Last level shows the operations which can be
performed on the data, for the Airport simulation,
 www.anuupdates.org
9
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

Q) What is Data Structure? What are the different types of

Data Structures?
Data means collection of raw facts like 12, ‘a’, 34.45 etc., any processed
data is referred as information. Any user may require data to be processed.
In order to manage data in a most efficient manner one would require better
approaches and such approaches might be referred as data structures.
A data structure is a mathematical & logical representation of data in order
to organize the data in a most efficient manner.

Data structures are basically of following types:

 Linear Data structures
 Non linear Data structures
(OR)
 Static Data structures
 Dynamic Data structures
(OR)
 Homogeneous Data Structures
 Heterogeneous Data Structures
Linear Data structures: A linear data structure is a means where data may
be organized in sequential manner or in linear order.

Example: “Arrays, Stacks, Queues and linked lists” are the examples
for linear data structures.

Non-linear Data structures: A non-linear data structure is a means where

data may be organized in quite a different manner. It doesn’t follow any
linear form.

Example: “Trees & Graphs” are the examples for the non-linear data
structures.

Static Data structures: A static data structure is fixed in its size as it is

specified during the compile time.
Example: “Arrays, Stacks & Queues” are the examples for static data
structures.

Dynamic Data structures: A dynamic data structure is created during the

runtime. It provides better flexibility to the user as it allows the user to
increase or decrease the size during the execution of the program. Hence we
say that dynamic data structures may vary during the runtime. Moreover,
dynamic data structures allow the user to add, delete and rearrange data
items at runtime.
Example: Linked lists, Trees & Graphs

Homogeneous Data Structures: It is a data structure where items of

similar kind or same type of items are placed/arranged.
 www.anuupdates.org
10
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
Example: Arrays, Stacks, Queues are the examples of this kind.

Heterogeneous Data Structure: It is a data structure where items of

different can be placed and operated. Linked Lists, Trees & Graphs may be
the examples of Heterogeneous data structures

Q) What is primitive and non-primitive data structures?

Primitive Data Structures:

Primitive Data Structures are the basic data structures that directly operate
upon the machine instructions. They have different representations on
different computers. They are:
 Integers,
 Floating point numbers,
 Character constants,
 String constants
 Pointers
Non-primitive Data Structures:
Non-primitive data structures are more complicated data structures and are
derived from primitive data structures.
They emphasize on grouping same or different data items with relationship
between each data item.
These are:
 Arrays
 Lists
 Files
 www.anuupdates.org
11
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

Q) What is Linear and Non-Linear data structures?

Data structure is a way to organize a data in computer so that it can be
used efficiently.
In computer science, Data Structure is classified into two categories :
 Linear Data Structure
 Non Linear Data Structure

Linear Data Structures: The data structure where data items are organized
sequentially or linearly where data elements attached one after another is
called linear data structure. Data elements in a liner data structure are
traversed one after the other and only one element can be directly reached
while traversing. All the data items in linear data structure can be traversed
in single run.
These kind of data structures are very easy to implement because memory
of computer is also organized in linear fashion.
Examples of linear data structures are:
 Arrays,
 Stack,
 Queue
 Linked List.
 An arrays is a collection of data items having the same data types.
 A Stack is a LIFO (Last In First Out) data structure where element
that added last will be deleted first. All operations on stack are
performed from on end called TOP. A Queue is a FIFO (First In First
Out) data structure where element that added first will be deleted
first.
 In queue, insertion is performed from one end called REAR and
deletion is performed from another end called FRONT.
 A Linked list is a collection of nodes, where each node is made up of a
data element and a reference to the next node in the sequence.
 www.anuupdates.org
12
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

Non Linear Data Structures: The data structure where data items are not
organized sequentially is called non linear data structure. In other words, A
data elements of the non linear data structure could be connected to more
than one elements to reflect a special relationship among them. All the data
elements in non linear data structure can not be traversed in single run.
Examples of non linear data structures are:
 Trees
 Graphs
 A tree is collection of nodes where these nodes are arranged
hierarchically and form a parent child relationships.
 A Graph is a collection of a finite number of vertices and an edges that
connect these vertices. Edges represent relationships among vertices
that stores data elements.
Difference Between Linear and Non Linear Data Structure:

Linear Data Structure Non-Linear Data Structure

Every item is related to its previous Every item is attached with many
and next item. other items.

Data is arranged in linear sequence. Data is not arranged in sequence.

Data items can be traversed in a Data can not be traversed in a

single run. single run.

Examples: Array, Stack, Queue,

Examples: Tree, Graph.
Linked List.

Implementation is Easy. Implementation is Difficult.

Q) Explain about Arrays?

Array is a collection of similar kind of items or elements. In other words, an
array is a linear list in which a group of elements are identified by a unique
name. In some other way, a group of elements that have common name is
said to be an array. An array can be called as linear list or simply list.

Types of Arrays: Arrays are of three different types. They are:

 Single Dimensional arrays

 Double Dimensional arrays
 Multi-dimensional arrays.
 www.anuupdates.org
13
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

Single dimensional arrays have only one subscript or index where as multi-
dimensional arrays may have more than one subscript or index.
For Example:
int a[20];
float b[10]; //single dimensional or one dimensional arrays
int a[3][3]; // double dimensional or table or two dimensional
int a[3][3][3]; // multi-dimensional

Note: There may be any number of subscripts for arrays.

Declaration of Arrays:
Syntax:
datatype array_name [no. of items];
OR
datatype array_name [index];
Ex:
int a [10]; // integer array

char str[ 8 ]; // character array

Data type array name index

Note:
 Array name should not contain any spaces.
 Index of the array should not be zero or less than zero.
 Array size is fixed.
 Array index starts from zero always.
 www.anuupdates.org
14
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

Symbolic representation of two dimensional arrays follow:

For example, consider int a [3][4];

11 33 22 55 44 88 66 55 77 99 100 101

0 1 2 3 0 1 2 3 0 1 2 3

Initialization of array:

int a[5]={11,12,13,14,15};
int a[]={11,22,33};
char a[7]={“sairam”};
float b[4]={1.2,3.5,7};

Two Dimensional Array:

These arrays are also called double dimensional array. Another name of two-
dimensional array is Tabular or Rectangular Array. These arrays are in row
and column form, so these are also called Row-Column array or square
Array. These arrays have two subscripts and also called double subscripted
array. We can write the double dimensional array in the matrix form as
below and so these are also known as matrix array. The syntax used for
declaration of two dimensional array is as:

data-type array-name [row size] [column size];

For example, some of the valid double dimensional arrays are written as
below:
int a[10][10];
float b[50][50];
char name[10][20];

Also you can declare two-dimensional array in static form i.e. these type of
array declarations have fixed value or constant value. The syntax used for
static two dimensional array is as follows:

static data-type array-name [row size][column size = {list of value};

For example, suppose you want to assign some fixed value to a variable
array named table by using the static two-dimensional array as.

static int table [2][3] = {15, 7, 12, 2, 20, 8};

 www.anuupdates.org
15
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
Here the values assigned to the tabular array-name is as:
table[0][0] = 15
table[0][1] = 7
table[0][2] = 12
table[l][0] = 2
table[l][1] = 20
table[l][2] = 8
Also we can write the above statement as:
static int table[ ][ ] = {15, 7, 12, 2, 20, 8};
Above statement fails in some cases.
Another way to write the above statement is as follows:
static int table[][]={ {5, 7, 12} , {2, 20, 8} };
char table[2][30]={“kumar”,”dheeraj”};

Multi Dimensional Array:

It is a collection of double dimension arrays. Each double dimension
array is identified by with ‘i’ each array is identified by ‘j’ and each value
is identified by with ‘k’
Syntax:
Datatype variable[no_of_dd_arrays][row_size][col_size];

Eg:
int a[3][2][4];
 www.anuupdates.org
16
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

Operations on Arrays:

1. Creation of array
2. Initialization of array
3. Accepting data into array
4. Displaying contents of array
5. Insertions
6. Deletions
7. Search
8. Sort

Advantages of arrays:
 As arrays store all the elements in continuous locations, it becomes
easy to access all the elements. 
 Arrays allow the user to store elements of same type in sequential
manner.
 Array elements can be accessed randomly (need not to follow any
order).
 Arrays avoid no. of variables & their naming.
Disadvantages of arrays:
 Array size is fixed. The user cannot grew or shrink the size
dynamically. 
 Optimum utilization of memory may not be achieved (i.e., there is a
scope for wasting the memory).
 Arrays allow only similar kind of items as data.
Characteristics of a Data Structure
 Correctness:
Data structure implementation should implement its interface correctly.
 Time Complexity:
Running time or the execution time of operations of data structure must be
as small as possible.
 Space Complexity:
Memory usage of a data structure operation should be as little as possible.
 Operations on Data Structures: The operations involve in data
structure are as follows.
 Create: Used to allocate/reserve memory for the data element(s).
 Destroy: This operation de allocate /destroy the memory space
assigned to the specified data structure.
 Selection: Accessing a particular data within a data structure.
 Update: For updating (insertion or deletion) of data in the data
structure.
 www.anuupdates.org
17
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

 Searching: Used to find out the presence of the specified data item in
the list of data
 Sorting: Process of arranging all data items either in ascending or in
descending order.
 Merging: Process of combining data items of two different sorted lists
of data items into a single list.

Q)Explain about Sparse Matrix Matrix?

In computer programming, a matrix can be defined with a 2-dimensional
array. Any array with 'm' columns and 'n' rows represents a mXn matrix.
There may be a situation in which a matrix contains more number of ZERO
values than NON-ZERO values. Such matrix is known as sparse matrix, i.e
Sparse matrix is a matrix which contains very few non-zero elements. When
a sparse matrix is represented with 2-dimensional array, we waste lot of
space to represent that matrix. For example, consider a matrix of size 100 X
100 containing only 10 non-zero elements. In this matrix, only 10 spaces
are filled with non-zero values and remaining spaces of matrix are filled with
zero. That means, totally we allocate 100 X 4 = 40000 bytes of space to store
this integer matrix. And to access these 10 non-zero elements we have to
make scanning for 10000 times.

Sparse Matrix Representations

A sparse matrix can be represented by using TWO representations, those
are as follows...

1 Triplet Representation
2 Linked Representation

Triplet Representation
In this representation, we consider only non-zero values along with their row
and column index values. In this representation, the 0th row stores total
rows, total columns and total non-zero values in the matrix. For example,
consider a matrix of size 5 X 6 containing 6 number of non- zero values.
This matrix can be represented as shown in the fig:

In above example matrix, there are only 6 non-zero elements ( those are 9, 8,
4, 2, 5 & 2) and matrix size is 5 X 6. We represent this matrix as shown in
the above image. Here the first row in the right side table is filled with values
5, 6 & 6 which indicates that it is a sparse matrix with 5 rows, 6 columns &
6 non-zero values. Second row is filled with 0, 4, & 9 which indicates the
 www.anuupdates.org
18
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
value in the matrix at 0th row, 4th column is 9. In the same way the
remaining non-zero values also follows the similar pattern.
Linked Representation
In linked representation, we use linked list data structure to represent a
sparse matrix. In this linked list, we use two different nodes namely header
node and element node. Header node consists of three fields and element
node consists of five fields as shown in the image...

STACKS
A stack is a linear list in which insertions & deletions are made at one end
called top. Stack follows LIFO manner in order to store data. LIFO means
Last In First Out. As an example to stack, consider a set of plates placed one
over the other or a pile of books.

A stack may be referred as linear data structure or static data structure or

homogeneous data structure.

Stack is used in many computer applications. It is used in system software

like operating systems, compilers. More over a stack may be implemented
either using arrays or using linked list.

Operations on Stack:
 Push
 Pop
 Show
 www.anuupdates.org
19
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

 Is empty
 Is Full

Push() : This allows storing data one after the other.

Pop() : This operation allows deleting data one after the other.
Show() : This operation allows displaying data stored in the stack.
Isempty() : To check whether the stack is empty or not.
Isfull() : To check whether the stack is full or not.
.
Push:
In the push operation, initially top is initialized to –1. From there, items are
stored one after the other by incrementing ‘top’ by 1. As and when ‘top’
reaches the maximum position, the push (or insertion) operation is stopped.

4 4 4 4 4 50 4

3 3 3 3 40 3 40 3

2 2 2 30 2 30 2 30 2

1 1 20 1 20 1 20 1 20 1

0 10 0 10 0 10 0 10 0 10 0

Top = -1 top = 0 top = 1 top = 2 top = 3 top = 4

For each insertion, we check out whether the stack is full or not. If it is
FULL stop the process otherwise continue pushing items.
Procedure to perform push operation:

Procedure: Push ( stk, item)

begin
If (top = MAX-1) then
Display “ Stack is OVERFLOW”
else
begin
1. Increment top by 1.
2. Assign stk [ top ] = item.
End
End.

Note: Here ‘MAX’ is the value of maximum number of items that can be
stored in a stack.
 www.anuupdates.org
20
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
POP:
In pop operation, the elements of stack are removed one after other by
decrementing the value of top. Once after removing the last item from the
stack, pop operation is terminated. For each deletion, we check out whether
the stack is empty or not.

50 4 4 4 4 4 4

40 3 40 3 3 3 3 3

30 2 30 2 30 2 2 2 2

20 1 20 1 20 1 20 1 1 1

10 0 10 0 10 0 10 0 10 0 0

Top = 4 top = 3 top = 2 top = 1 top = 0 top = -1

Procedure: Assume ‘stk’ as a stack.

Procedure: Pop( stk)
Begin
If (top = -1) then
Display “Stack is UNDERFLOW”
Else
Begin
1. Assign item = stk [ top ].
2. Decrement ‘top’ by 1.
3. Print ‘item’
End
End.
Show:
The stack allows display from top to bottom i.e., from top pointer only the
user can list the items.

For the above example, the items are: 50 40 30 20 10 5

Applications of Stack:
 Used in operating systems, compilers other system software
 Processor itself maintains a stack in order to execute applications.
 Used for expression evaluations.
 Used in regular function calls, nested function calls and recursive
function calls.
 www.anuupdates.org
21
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

Q)Write an algorithm for infix to Postfix expression?

Step 1: start
Step 2: Initially push a left parenthesis ‘(‘ into the stack and ‘)’ added to
the given expression.
Step 3: Repeat the following procedure while the stack is not empty.
Step 4: If an operand is encountered added to the postfix expression.
Step 5: If a ‘(‘ is encountered, pushes onto the stack.
Step 6: If an operator is encountered, Repeatedly pop from the stack and
each operator is added to the postfix expression until the same
precedence operator occur on the stack.
(the operator is less than in the stack)
Step 7: If ‘)’ is encountered repeatedly pop from the stack and added to the
postfix expression until ‘(‘ and next remove the ‘(‘.
Step 8: stop.
To convert infix to post fix expression
1) (a+(b*c-(d/e^f)*g)*h)

ans) abc*def^/g*-h*+

2) 5,6,2,+,*,12,4,/,-

ans) 5 5

6 5,6

2 5,6,2

+ 5,8

* 40

12 40,12

4 40,12,4

/ 40,3

- 37
 22
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

To convert Infix to Postfix

((A+B)*(D^(E-F)))

EXPRESSION STACK POST

( (

(( ((

A (( A

+ ((+ A

B ((+ AB

) ( AB+

* (* AB+

( (*( AB+

D (*( AB+D

^ (*(^ AB+D

( (*(^( AB+D

E (*(^( AB+DE

- (*(^(- AB+DE

F (*(^(- AB+DEF

) (* AB+DEF-
(^

) AB+DEF-^
(*

) AB+DEF-^*
 23
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

QUEUES
Types of Queues:

There are different types of queues. The list follows:

 Queues
 Circular Queues
 Double Ended Queues (De-Queues)
 Priority Queues
Queues

A queue is a linear list where items may be inserted or deleted in FIFO manner.
FIFO means First In First Out. That is, the item placed in the first, will be
accessed and removed first from the queue. Similarly the item placed last will
be accessed and removed last. A queue uses two pointers called front, rear to
perform storage & retrieval operations.

In other words, queue has two ends: front and rear. All the insertions into
queue are made at ‘rear’ end and all the deletions are done at ‘front’ end.
 24
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
A queue is called as linear data structure or static data structure or
homogeneous data structure. The no. Of items in a queue is fixed. The
operating system itself maintains an instruction queue while executing user
programs.

A queue of people is the regular example for queues.

Operations on Queues:
 Create or Initialize a queue.
 Insert an item into a queue (Insertq () or Enqueue())
 Delete an item from a queue (Deleteq()).
 Display all the items (show ()).
 Check whether Queue is empty or not (isempty())
 Check whether Queue is full or not (isfull())
Initially declaration & initializing the front and rear pointers is to be done.

Enqueue:(Insertq) Storing elements one after the other into the queue is
possible at this level of operation using the rear pointer. Increment each time
an item is placed in the queue.

Dequeue Operation(Deleteq): Removal elements from the queue one by one is

done at this level of operation using the front pointer. Increment front
whenever an item is removed from the queue.

Show: Displaying elements of the queue are performed in this operation

because unless the user doesn’t know what is the content of the queue, he is
unable to process other operations.

The process of adding an element into the queue is known as Enqueue. The
following steps should be taken to enqueue (insert) data into a queue .

Procedure: enqueue (que, item)

Begin
If (rear = MAX-1)
Display “ Queue is OVERFLOW”
Else
Begin
a. Increment rear by 1.
b. Assign q [rear] = item
End
End.
 25
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

Symbolic Representation of Insertions follows:

0 1 2 3 4 0 1 2 3 4

10

r =-1 f = 0 f=r=0

10 20 10 20 30

f r f r

10 20 30 40 10 20 30 40 50

f=0 r=3 f=0 r=4

Dequeue Operation(Deletions):
This operation allows removing of elements from the queue one by one. Here we
use front end (or pointer) to remove each item. For each removal front is
incremented by 1. The process of removing items from the queue is done until
the queue becomes EMPTY. That is, when the queue becomes empty, the
deletion process is terminated.

Symbolic Representation of Deletion operation:

0 1 2 3 4 0 1 2 3 4
10 20 30 40 50 20 30 40 50

f r f r
0 1 2 3 4 0 1 2 3 4
30 40 50 40 50

f r f r
0 1 2 3 4 0 1 2 3 4
50

f, r queue is empty !! f=0 r=-1

 26
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
The following is the procedure to delete an item from the queue:

Assume front = 0, rear = 4.

Procedure: Deleteq ( que)

Begin
if((front==0)&&(rear==-1))

PRINT Queue is underflow

else

if(front==rear)
BEGIN
front=0;rear=-1;
END
else
front=front+1;

End.
Applications of queue
There are various applications of computer science, which are performed using
data structure queue. This data structure is usually used in simulation,
various features of operating system, multiprogramming platform systems and
different type of scheduling algorithm are implemented using queues. Round
robin technique is implemented using queues. Printer server routines, various
applications software are also based on queue data structure.
 The operating system itself uses a queue called an Instruction Queue & a Message
Queue.
 In a network, there will be a print queue that manages the documents to be printed
Circular Queues( It is also called as “Ring buffer”.)
In regular queues, there is a situation where the user cannot insert items
through the positions are free. That is, for example, consider a queue with full
of data.

f r

10 20 30 40 50 60 70

Perform Deletion operation on the above queue for 3 times. The following is the
resultant queue.
 27
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

40 50 60 70
f r
Now there are 3 empty locations, but still the user cannot store any more items
because the rear pointer cannot be incremented further.
In order to overcome the above problem and to reutilize the empty locations,
circular queues have come into picture.
Step1: Empty CQueue

Step2: Inserting ‘10’ element into CQueue

Step3: Inserting the ‘20’ element into CQueue

 28
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
Step4: Inserting the ‘30’ and ‘40’ elements into CQueue

Step5: Inserting the ‘50’ and ‘60’ elements into CQueue

Step6: Inserting the ‘70’ element into

CQueue
If we try to insert ‘70’ element in queue. It displays “queue is full” message.

Removing values from the CIRCULAR QUEUE:

Step1: Removing ‘10’ element from the CQueue
 29
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
Step2: Removing ‘20’ element from the Queue

Step3: Removing ‘30’ and ’40’ element from the Queue

Circular Queue Behavior:

Step4: inserting ‘70’ element into the Queue

So that in CIRCULAR QUEUE we can again insert new values at the deleted
positions
 30
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

Double Ended Queue

A double-ended queue is a queue where items can be inserted & deleted at
either end. That is, we can insert elements from both rear & front ends. Again
there are 2 types of double-ended queues. They are:

 An input-restricted deque is one where deletion can be made from both

ends, but insertion can be made at one end only.

 An output-restricted deque is one where insertion can be made at both

ends, but deletion can be made from one end only.

Initializing a DeQue: Consider the DeQueue with size is 5

Step1: Empty DeQueue

Inserting Using Rear:

Step2: Inserting ‘10’ element into Queue

Step3: Inserting the ‘20’ element into Queue

 31
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
Step4: Inserting the ‘30’ element into Queue

Step5: Inserting the ‘40’ element into Queue

Step6: Inserting the ‘50’ element into Queue

Removing values using Front:

Step1: Removing ‘10’ element from the Queue

Step2: Removing ‘20’ element from the Queue

 32
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

The above insertions and deletions are done as like normal QUEUE. Now we
can see the insertions and deletions are not doing by the normal
QUEUE….they are:

Inserting using Front:

Step1: inserting ‘60’ element using Front

Step2: inserting ‘70’ element using Front

Deletion from Rear:

Step1: Deleting ‘50’ element from Rear

Step2: Deleting ‘40’ and ‘30’ elements from Rear

 33
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

Priority Queue
Often the items added to a queue have a priority associated with them; this
priority determines the order in which they are removed from the queue. Higher
priority items are removed first. Such a queue is said to be priority queue.
Priority queues are used in Process Control Systems.

Applications:
 Band width management : pq can be used to manage the limited
resources such as band width on transmission line from a network
router
 Discrete event simulation: pq is to manage events in a discrete event
simulation . The events are added to the queue with their simulation
time used as priority 
 Relationship to store the algorithms: the semantics of pq naturally
suggested to storing methods (heap sort)

LINKED LIST
A linked list is a sequence of nodes connected by means of pointers. In other
words a linked list is a collections of nodes that are connected using pointers. If
the memory is allocated in the memory before the execution of the program, it
is fixed and cannot be changed. We have to use an alternative strategy to
allocate memory only when it is required. There is a special kind of data
structure called “Linked List “ that provides more flexible storage system.

A linked list is constructed using dynamic memory allocation. Compare to

other data structures like arrays, stacks and queues linked lists support
efficient memory organization.

There are different linked lists:

 Single linked list

 Double linked list
 Circular linked list
In a linked list, a node is a collection of different kinds of data. Particularly, a
node is a collection of data and the address of next node.
 34
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

Node = data + address of next node

i.e., Node = Data field + Link field

As a node is a collection of different data, it can be assumed as a structure. A

node can be defined as follows:

struct node
{
data type data member;
struct node *next node pointer;
};
Ex:
struct node
{
int data;
struct node *next;
};

Single Linked List:

A single linked list is a collection of several nodes that are connected using
pointers in forward direction.
Operations on Linked List:

1) Create
2) Insert
a) Insert at begin
b) Insert at Location
c) Insert at end
3) Delete
a) Delete at begin
b) Delete at Location
c) Delete at End
4) Concat
5) Merge
6) Search
7) Sort
8) Display

The following is the representation of singly Linked List:

head
 35
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
Insert at Begin:

Insert at Middle:

Insert at End:

Delete at Begin:

Delete at Middle:
 36
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
Delete at End:

Syntax: Struct node

{
data type data member;
struct node *next node pointer;
};
Ex:
struct node
{
int data;
struct node *next;
};

Circular Linked List

In a single list, once we traverse from one node to another is becomes difficult
to get back as it links the entire nodes in one direction that is forward
direction. To over come this drawback, we can move on to
circular linked lists where the last node holds the address of the first node. The
operation looks like as follows:

Advantages of Circular Linked Lists:

 Any node can be a starting point. We can traverse the whole list by
starting from any point. We just need to stop when the first visited node
is visited again.
 Useful for implementation of queue. Unlike this implementation, we don’t
need to maintain two pointers for front and rear if we use circular linked
list. We can maintain a pointer to the last inserted node and front can
always be obtained as next of last.
 Circular lists are useful in applications to repeatedly go around the list.
For example, when multiple applications are running on a PC, it is
common for the operating system to put the running applications on a
 37
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
list and then to cycle through them, giving each of them a slice of time to
execute, and then making them wait while the CPU is given to another
application. It is convenient for the operating system to use a circular list
so that when it reaches the end of the list it can cycle around to the front
of the list.)
 Circular Doubly Linked Lists are used for implementation of advanced
data structures like Fibonacci Heap.

Operations of Circular Linked List:

Insert at Begin:

Insert at Middle:

Insert at End:
 38
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
Delete at Begin:

Delete at Middle:

Delete at End:

Doubly Linked List

Doubly Linked List is a variation of Linked list in which navigation is possible
in both ways, either forward and backward easily as compared to Single
Linked List. Following are the important terms to understand the concept of
doubly linked list.
 Link − Each link of a linked list can store a data called an element.
 Next − Each link of a linked list contains a link to the next link called
Next.
 Prev − Each link of a linked list contains a link to the previous link
called Prev.
 LinkedList − A Linked List contains the connection link to the first link
called First and to the last link called Last.
 39
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

Doubly Linked List Representation

As per the above illustration, following are the important points to be

considered.

 Doubly Linked List contains a link element called first and last.
 Each link carries a data field(s) and two link fields called next and
prev.

 Each link is linked with its next link using its next link.
 Each link is linked with its previous link using its previous link.
 The last link carries a link as null to mark the end of the list.
Basic Operations
Following are the basic operations supported by a list.

 Insertion − Adds an element at the beginning of the list.

 Deletion − Deletes an element at the beginning of the list.
 Insert Last − Adds an element at the end of the list.
 Delete Last − Deletes an element from the end of the list.
 Insert After − Adds an element after an item of the list.
 Delete − Deletes an element from the list using the key.
 Display forward − Displays the complete list in a forward manner.
 Display backward − Displays the complete list in a backward manner.
 40
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

1) Add a node at the front:

2) Add a node after a given node.:

3) Add a node at the end:

4) Delete a Node at Begin

 41
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
5) Delete Node at Middle

6) Delete Node at End

Advantages & Disadvantages of Linked Lists:

Advantages:
 Optimum utilization of memory can be achieved.
 Easy to implement insert & delete operations.
 As it is dynamic, any number of data items can be stored.
 It can hold different kinds of data in each node.
 Garbage collection can be achieved.
Disadvantages:
 As the nodes are connected sequentially, it is difficult to
perform random access.
 Memory may be wasted in terms of pointers.
Differences between arrays & linked lists

Arrays Linked List

1. Array is fixed in size. 1. No.of nodes in the list is unlimited.

2. Static allocation of memory is 2. Dynamic Memory allocation is

done. done.
 42
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
3. Use either initialized/un- 3. Uses free store or heap memory
initialized area. area.

4.Only identical items can be placed. 4. Identical or different items may be

placed.
5. Optimum utilization of memory will 5. Optimum utilization of memory is
not be found. done.
6. Do not use pointers concept. 6. Uses pointers only.

7. Continuous blocks of memory is 7. Doesn’t need continuous memory.

required.

TREES
A tree is a nonlinear data structure and is generally defined as a nonempty
finite set of elements, called nodes such that:
 T contains a distinguished node called root of the tree.
 The remaining elements of tree form an ordered collection of zero or
more disjoint subsets called sub tree.
Q) Explain Binary Tree and its properties ?
A binary tree is defined as a finite set of elements, called nodes, such that:
 Tree is empty (called the null tree or empty tree) or
 Tree contains a distinguished node called root node, and the remaining nodes
form an ordered pair of disjoint binary trees.
 43
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

Q) Properties of binary trees

 The depth of a binary tree containing N nodes is at most N-1.

 The depth of a binary tree containing N leaves is at least [log2(N)].
 A binary tree of depth d has at most 2d leaves.
 The number of nodes in a binary tree of depth d is at most 2d-1 - 1.
 The average depth of a binary tree containing N nodes is o√N
 The maximum number of nodes on level i of a binary tree is 2i-1, i >= 1
 The maximum number of nodes in a binary tree of depth k is 2 – 1, k >= 1
k

 If a complete binary tree with n nodes (depth = log2n +1 ) is

represented sequentially,
then for any node with index i, 1 <= i < n, we have:
 parent ( i ) is at L i / 2 if i != 1 if i = 1, i is at the root and has no parent
 left_child( i ) is at 2i if 2i n. If 2i > n, then i has no left child
 rightt_child( i ) is at 2i + 1 if 2i + 1 <= n. If 2i + 1 > n, then i has no right
child
Trees and its related terminology:

Tree Terminologies: In a tree data structure, we use the following

terminology...

1. Root: In a tree data structure, the first node is called as Root Node. Every
tree must have root node. We can say that root node is the origin of tree data
structure. In any tree, there must be only one root node. We never have
multiple root nodes in a tree.
 44
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
2. Edge: In a tree data structure, the connecting link between any two
nodes is called as EDGE. In a tree with 'N' number of nodes there will be
a maximum of 'N-1' number of edges.

3. Parent: In a tree data structure, the node which is predecessor of any node
is called as PARENT NODE. In simple words, the node which has branch from
it to any other node is called as parent node. Parent node can also be defined
as "The node which has child / children".

4. Child: In a tree data structure, the node which is descendant of any node
is called as CHILD Node. In simple words, the node which has a link from its
parent node is called as child node. In a tree, any parent node can have any
number of child nodes. In a tree, all the nodes except root are child nodes.
 45
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

5. Siblings: In a tree data structure, nodes which belong to same Parent are
called as SIBLINGS. In simple words, the nodes with same parent are called as
Sibling nodes.

6. Leaf: In a tree data structure, the node which does not have a child is called
as LEAF Node. In simple words, a leaf is a node with no child.
In a tree data structure, the leaf nodes are also called as External Nodes.
External node is also a node with no child. In a tree, leaf node is also called as
'Terminal' node.
 46
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
7. Internal Nodes: In a tree data structure, the node which has atleast one
child is called as INTERNAL Node. In simple words, an internal node is a node
with atleast one child.
In a tree data structure, nodes other than leaf nodes are called as Internal
Nodes. The root node is also said to be Internal Node, if the tree has more than
one node. Internal nodes are also called as 'Non-Terminal' nodes.

8. Degree: In a tree data structure, the total number of children of a node is

called as DEGREE of that Node. In simple words, the Degree of a node is total
number of children it has. The highest degree of a node among all the nodes in
a tree is called as 'Degree of Tree'

9. Level: In a tree data structure, the root node is said to be at Level 0 and
the children of root node are at Level 1 and the children of the nodes which are
at Level 1 will be at Level 2 and so on... In simple words, in a tree each step
from top to bottom is called as a Level and the Level count starts with '0' and
incremented by one at each level (Step).
 47
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

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

11. Depth: In a tree data structure, the total number of egdes from root node to a
particular node is called as DEPTH of that Node. In a tree, the total number of edges
from root node to a leaf node in the longest path is said to be Depth of the tree. In
simple words, the highest depth of any leaf node in a tree is said to be depth of that
tree. In a tree, depth of the root node is '0'.
 48
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

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

13. Sub Tree: In a tree data structure, each child from a node forms a sub
tree recursively. Every child node will form a sub tree on its parent node.

.
 49
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

Applications of binary trees

 Binary Search Tree
Used in many search applications where data is constantly
entering/leaving, such as the map and set objects in many languages'
libraries.
 Binary Space Partition
Used in almost every 3D video game to determine what objects need to
be rendered.
 Binary Tries
Used in almost every high-bandwidth router for storing router-tables.
 Hash Trees
Used in p2p programs and specialized image-signatures in which a
hash needs to be verified, but the whole file is not available.
 Heaps
Used in implementing efficient priority-queues, which in turn are
used for scheduling processes in many operating systems, also used
in heap-sort.
 Huffman Coding Tree (Chip Uni)
Used in compression algorithms, such as those used by the .jpeg and
.mp3 file-formats.
 GGM Trees
Used in cryptographic applications to generate a tree of pseudo-
random numbers.

Q)Types of Tree data structure

The following are the types of a tree data structure:

General tree: The general tree is one of the types of tree data structure.
In the general tree, a node can have either 0 or maximum n number of
nodes.
 50
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

There is no restriction imposed on the degree of the node (the number of

nodes that a node can contain). The topmost node in a general tree is
known as a root node. The children of the parent node are known
as subtrees.
There can be n number of subtrees in a general tree. In the general tree, the
subtrees are unordered as the nodes in the subtree cannot be ordered.
Every non-empty tree has a downward edge, and these edges are connected
to the nodes known as child nodes. The root node is labeled with level 0.
The nodes that have the same parent are known as siblings.

Binary tree: Here, binary name itself suggests two numbers, i.e., 0 and 1. In a
binary tree, each node in a tree can have utmost two child nodes. Here, utmost
means whether the node has 0 nodes, 1 node or 2 nodes.
 51
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

Binary Search tree: Binary search tree is a non-linear data structure in

which one node is connected to n number of nodes. It is a node-based data
structure. A node can be represented in a binary search tree with three
fields, i.e., data part, left-child, and right-child. A node can be connected to
the at most two child nodes in a binary search tree, so the node contains
two pointers (left child and right child pointer).
Every node in the left sub tree must contain a value less than the value of
the root node, and the value of each node in the right sub tree must be
bigger than the value of the root node.

A node can be created with the help of a user-defined data type known
as struct, as shown below:

struct node
{
int data;
struct node *left;
struct node *right;
}
The above is the node structure with three fields: data field, the second field is
the left pointer of the node type, and the third field is the right pointer of the
node type.

AVL tree
It is one of the types of the binary tree, or we can say that it is a variant of the
binary search tree. AVL tree satisfies the property of the binary tree as well as of
the binary search tree. It is a self-balancing binary search tree that was invented
by Adelson Velsky Lindas. Here, self-balancing means that balancing the heights of
left sub tree and right sub tree. This balancing is measured in terms of
the balancing factor.

We can consider a tree as an AVL tree if the tree obeys the binary search tree
as well as a balancing factor. The balancing factor can be defined as
the difference between the height of the left subtree and the height of the right
subtree. The balancing factor's value must be either 0, -1, or 1; therefore, each
node in the AVL tree should have the value of the balancing factor either as 0, -
1, or 1.
 52
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

Q) Traversing Binary Trees

There are three standard ways of traversing a binary tree T with root R. These
three algorithms, called preorder, inorder and postorder, are as follows.

Preorder:
1) Process the root R.
2) Traverse the left sub tree of R in preorder.
3) Traverse the right sub tree of R in preorder.
Inorder:
1) Traverse the left sub tree of R in inorder.
2) Process the root R.
3) Traverse the right sub tree of R in inorder.
Postorder:
1) Traverse the left sub tree of R in postorder.
2) Traverse the right sub tree of R in postorder.
3) Process the root R.

Operations on a Binary tree

There are several operations on a binary tree. Some of them are:
1. Create
2. Insert a node
3. Delete a node
4. Search
5. Count
6. Leaf Nodes
7. Height
8. Display:
i. Pre-order
ii. In-order
iii. Post-Order
A binary tree can be represented mainly in two ways:?
 Sequential representation
 Linked representation
Sequential (Array) representation:
The simplest way to represent binary trees in memory is the sequential
representation that uses a one-dimensional array.
The following method is used to represent the tree:
 The root of binary tree is stored in the first location of array.
 53
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

 If a node is in Jth location of array, then its left child is stored in the
location (2J) and its right child in the location (2J+1) 
 The maximum size that is required for an array to store a tree is 2 power
(d+1) – 1, where d is the depth of the binary tree.

The above binary tree is represented sequentially as,

A B C D E F G H I J

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Here the node C at location 3 has child F at 6 th (2*3) location and the right
child at 7th (2*3+1) location. Since the depth of the binary tree is 4 the required
array size is 32-1 = 31.

 The main advantage of this method is no complex pointer maintenance and we can
easily identify the locations.

 The basic disadvantage is that growing and shrinking of a tree cannot be made
efficiently.

LINKED (POINTER) REPRESENTATION:

Linked representations of trees in

memory are implemented using pointers.
Since each node in binary tree can have
maximum two children, a node in a
linked representation has two pointer
fields for both left child and right child,
and one information field. If anode does
not have any child the corresponding
pointer field is made NULL pointer.

NULL is represented by (X). A binary tree with N nodes contains N+1 NULL
pointers. In essence all leaf nodes has two NULL pointers. Each node is
associated with one information field and two pointer fields, LeftPtr and
RightPtr, which denote the pointers to the left child and the right child of the
node.
 54
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
The disadvantages are, wasted space due to NULL pointers and finding a
parent of a particular node is difficult.

Write an algorithm for each of the following in recursive methods

i) Inorder (travellsall)
ii) Preorder
iii) Postorder

B C

Inorder traversal: -
Step 1: (check if the tree is empty by verifying root pointer p)
If (p==NULL)
Print tree is empty
Step 2: if=(leftptr (p)! =NULL) then call
Inorder (leftptr (p))
Step 3: print data (p)
Step 4: if (rightptr (p)! =NULL) then call
Inorder (rightptr (p))
Step 5: return

Preorder traversal: -
Step 1: (check if the tree is empty by verifying the root pointer p)
If (p==NULL)
Print tree is empty
Step 2: print data (p)
Step 3: if (leftptr (p)! =NULL) then call
Preorder (leftptr (p))
Step 4: if (rightptr (p)! =NULL) then call
Preorder (rightptr (p))
Step 5: return

Postorder traversal: -
Step 1: (check if the tree is empty by verifying the root pointer p)
If (p==NULL)
 55
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
Print tree is empty
Step 2: if (leftptr (p)! =NULL) then call
Preorder (leftptr (p))
Step 3: if (rightptr (p)! =NULL) then call
Postorder (rightptr (p))
Step 4: print data (p)
Step 5: return

Step 1: - initially push NULL on to stack. Then ser ptr=the of T. Here prt is
pointer variable.
Step 2: - proceed down the left most path rooted at ptr=a, pushing the nodes A,
B, D, G, K onto stack (No other nodes are pushed into the stack since k has no
left child)
Step 3: - Back tracking the nodes K, G and D are poped and processed.
Stack=Ө, a, b, (we stop the processing at D since D has right child) then set
ptr=h.
Step 4: - process down the left most part rooted at ptr =h pushing the nodes H
and L onto the stack. Stack=Ө, a, b, h, l (No other nodes is pushed on the stack
L has no left child)
Step 5: - Back traking the nodes l and H are poped and processed.
Stack =Ө, a, b
(We stop the processing at H. Since H has right child then set ptr=M, the right
child of H)
Step 6: - process down the left most path rooted at ptr=m, pushing a node m
onto the stack.
Stack =o, a, b, m.
(No other nodes is pushed on to stack)
Since m has no left child.
Step 7: - Backtracking the nodes m, b and a are poped and processed. Stack=Ө
(No other elements of stack is poped. A have right child) set ptr=c.
Step 8: - process down the left most path rooted at ptr=c pushing the nodes c
and e onto the stack. Stack=c, e, ө.
Step 9: - Backtracking node e is poped and processed and E has no child and
node c is poped and processed. (Since c has no right child so NULL (ө) is poped
from stack) The result will be k, g, d, l, h, m, b, a, e, c.
 56
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

Algorithm: -
Inorder (info, left, right, root)

An array stack is used to hold temporary addresses of stack.

Step1: - (push null on to stack and initialize ptr).
Set top=1,stack [1]=Null and ptr=root.
Step2: - Repeat while (ptr! =Null) [pushes left most path onto stack]
a) Set top=top+1 and stack [top]=ptr [save mode]
b) Set ptr=left [ptr][updates ptr]
(End of loop)
Step3: - set ptr = stack [top] and top=top-1 [pop’s node from the stack]
Step4: - Repeat step 5to7 while ptr! =NULL [Back tracking ]
Step5: - Apply process to info [ptr]
Step6: - [Right child?]
If right [ptr]! =Null, then
a) Set ptr =right [ptr]
b) go to step2
(End if statement)
Step7: - set ptr = stack [top] and top=toop-1 [pop’s node]
(end of step4 loop)
Step8: - exit

Preorder: -
Preorder (info, left, right, root)

A binary tree T is in memory .The algorithm does a preorder traversal of

T, applying an operation process to each of its nodes. An array stack is
used to temporarily hold the addresses of the nodes.

Step1: -[initially push null on to stack, and initialize ptr]

Set Top=1, stack [1]= Null and ptr=root.

Step2: - Repeat steps 3 to 5 while ptr! = Null

Step3:- Apply process to info[ptr]

Step4:- [right child?]

 57
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
if right [ptr]! =Null, then [push on stack]

set top =top+1, and stack [top]=right[ptr].

(end of if structure)

Step5:- [left child ?]

if left [ptr]! =Null , then

set ptr=left [ptr]

else [pop from stack]

set ptr= stack[top] and top =top-1

(end of if structure)

(end of step2 loop)

Step6:- Exit

Post order:-
Explanation:-
Step1:- initially ,push Null on to stack and set ptr=A, the root of T.
Step2:- proceed down the left most path rooted at ptr=A, pushing the
nodes A,B,D,G and K onto stack . Further more, since A has a right child
c, push -c on to stack after A but before B ,and since D has a right child H,
push -H on to stack after D but before G. this yields:
Stack : θ,A,-C ,B,D,H,-M,L.
Step5:- [Back tracking] pop and process L, but only pop –M this leaves
Stack: θ, A, -C, B, D, H.
Now ptr = -M . Reset ptr=n and return to step (a) .
Step6:- proceed down the left-most path rooted at ptr=M.
Now, only M is pushed on to stack. This yields :
stack: θ,A,-C,B,D,H,M.
Step7:- [Back tracking] pop and process M,H,D and B, but only pop -C.
This leaves:
stack: θ,A
Now ptr= -C. Reset ptr=c and return to step(a)
Step8:-proceed down the left most path rooted at ptr=c first c is pushed
onto stack and then E,
stackθ,A,C,E.
 58
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
step9:- [Back tracing] pop and process E,C and A. When NULL is poped,
stack is empty and the algorithm is completed.

Algorithm for postorder: -

Postorder (info, left, right, root)

A binary tree T is in memory .This algorithm does a post order traversal of

T, applying an operation process to each of its nodes. An array stack is
used to temporarily hold the address of nodes.
Step1:- [Push NULL onto stack and initialize ptr]
Set top=1, stack[1]=NULL and ptr=root.
Step2:-[Push left most path onto stack]
Repeat step 3 to 5 while ptr !=NULL
Step3:-set top=top+1 and stack [top]=ptr
[pushes ptr on stack]
Step4:-If right [ptr]!=NULL then [push on stack]
set top=top+1and stack[top]= -right[ptr] .
(end of if structure (statement))
Step5:-set ptr= left[ptr] [updates pointer ptr]
(end of step 2 loop)
Step6:-set ptr=stack[top]and top =top-1
[pops node from stack]
step7:-repeat while ptr>0 then
a) Apply process to info [ptr]
b) Set ptr=stack [top]and top=top-1
(pops node from stack)
( end of loop )
step8:-if ptr<0,then:
a) set ptr=-ptr
b) go to step2
(end of if structure)
step9:-exit
 59
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

write an algorithm insertion of a mode in binary search tree?

Find(info, left, right, root, item, loc, Par)

a) loc=NULL and par=NULL it will indicates that item the root is empty

b) loc !=NULL and par=NULL it will indicates that item is root of T

c) loc=NULL and par!=NULL it will indicates that item is not in T and can
be added to T as a child of the node n with loc par

step1:- [tree empty ?]

if root=NULL , them set loc = NULL and par =NULL and return.

Step2:- [item at root?]

If item=info [root], then loc =root, par =NULL and return

Step3:- [initialize pointers ptr and save ]

If item <info [root] then

Set ptr=left[root] and save=root.

Else

Set ptr= right [root] and save=root

(end if statement)

step4:- repeat step5 and 6 while ptr!=NULL

step5:- [item found ?]

if item=info[ptr], then

set loc =ptr and par=save and return.

Step6:-if item<info[ptr],then

Set save= ptr and ptr=left[ptr]

Else

Set save=ptr and ptr=right[ptr]

[end of if structure]
 60
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
[end of step 4 loop]

step7:-[search unsuccessful]

set loc=NULL and par=save

step8:-exit

insbst(info, left, right, root, avail, item, loc)

step1:- call find (info, left, right, root, item, loc, par)
step2:- if loc!=NULL, then exit,
step3:- (copy item into new node in avail list )
a) if avail=NULL, them write overflow and exit
b) set new=avail, avail=left[avail]and info [new]=item
c) set loc =new, left[new]=NULL and right [new]=NULL
step4:- (Add item to tree )
if par=NULL ,then
set root=new
else
if item<info[par], then
set left[par]=new
else
set right [par]= new
(end of if statement )
step5:- exit

write an algorithm (procedure)deleting a node in a binary

search tree.

del (info, left, right, root, avail, item)

step1:- (find the locations of item and its parent

call find (info, left, right, root, item, loc, par)
step2:- [item in tree?]
if loc =NULL, then print item not in tree and exit
step3:- [delete node containing item]
if right [loc]!=Null and left[loc]!=NULL, then
call caseb (info, left, right, root, loc, par)
(end if statement )
step4:-[return deleted node to the avail list ]
 61
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
set left [loc]=avail and avail =loc
step5:-exit

caseb(info, left, right, root, loc, par)

(The pointer suc gives the location of the inorder successor of n and
parsuc gives the location of the parent of the inorder successor)
step1:- (find suc and parsuc)
a) set ptr=right(loc)and save=loc
b) Repeat while left[ptr]!=NULL
set save=ptr and ptr=left[ptr]
(end of loop )
c) set suc=ptr and parsuc=save
step2:-(delete inorder successor)
call casea (info, left, right, root, suc, parsuc)
step3:- (replace node n by its inorder successor )
a) if par!=NULL,
if loc=left[par]then
set left[par]=suc
else
set right [par]=suc
(end if statement)
else
set root=suc
(end of if)
b) set left[suc] =left[loc] and right[suc]=right[loc]
step4:-return.

Case a (info, left, right, root, loc, par)

Step1:-(initializes child)
If left[loc]=NULL and right[loc]=NULL, then
Set child=NULL
Else
If left[loc]!=NULL, then
Set child =left[loc]
Else
Set child=right[loc]
(end if)
 62
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
step2:-if par!=NULL, then
if loc=left[par], then
set left [par]= child
else
set right [par]= child
(end if )
else
set root=child
(end if )
step3:- return.

Q) THREADED BINARY TREE

Consider the linked representation of a binary tree T, approximately half of the

entries in left pointer field and right pointer field contains NULL elements. This
space occupied by NULL entries can be efficiently utilized to store some kind of
valuable information. These special pointers are called threads, and the binary
tree having such pointers is called a threaded binary tree.
Threads in a binary tree are represented by a dotted line. There are many ways
to thread a binary tree these are—

1. The right NULL pointer of each leaf node can be replaced by a thread to
the successor of that node under in order traversal called a right thread,
and the tree will called a right threaded tree or right threaded binary
tree.
2. The left NULL pointer of each node can be replaced by a thread to the
predecessor of that node under in order traversal called left thread, and
the tree will called a left threaded tree.
3. Both left and right NULL pointers can be used to point to predecessor
and successor of that node respectively, under in order traversal. Such a
tree is called a fully threaded tree.
A threaded binary tree where only one thread is used is also known as one way
threaded tree and where both threads are used is also known as two way
threaded tree.
 63
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
 64
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

Memory Representatin Of THreaded Binayr Tree

GRAPHS
A graph is a set of vertices & a set of edges. Vertices may be called as nodes. In
some other words, a graph is a collection of set of vertices denoted by V and a
set of edges called E

Where V = {v1, v2,………vi};

E = {e1, e2, e3….ej}

A simple graph may be represented as follows:

B
A

c
D

Directed Graph: A directed graph consists of vertices and edges that have
directions. It is also referred as a digraph. The diagram beside this definition is
an example for digraph.
 65
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

Weighted graph: A graph with a set of vertices & edges that have certain
values as weights is said to be weighted graph. If it posses directions on edges
then it is referred as weighted digraph.

Weighted graph Weighted digraph

3 3
B B
A A

6 7 5

5
7 c
c 4
D
D

4
Connected Graph Non-Connected Graph

A B
A

c c
D

Strongly connected graphs:-

A directed graph ‘G’ is said to be strongly connected graph because the path
between A to B and B to A

Eg:-
a

b d

c
 66
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
Weekly connected graph:-
In a weekly connected graph the direction of a graph is ignored and
connectedness is defined as if the graph is undirected

v1 v2 v4

v3

Tree graph :-
A connected graph tree without cycles called as tree graph

Indegree outdegree:-
1

The no of edges coming from the node is called out degree. Here out degree of 2
is two The no of edges enter to the node is called in degree

The in degree of 2 is one.

Q) Graph Representations:
A graph can be represented either by using arrays or linked list representation.
i.e., Graphs may be represented in two different ways:
 Adjacency Matrix
 Adjacency List
Adjacency Matrix: Array representation of a graph is nothing but adjacency
matrix. In adjacency matrix, if you find an edge between two distinct nodes,
place a ‘1’ otherwise place a ‘0’.
Consider the above-directed graph, and Aij is the adjacency matrix.
 67
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

Aij = 1 if and edge is found.

=0 otherwise
C 0 0 0 1

B C

A B C D

A 0 1 1 1

B 1 0 1 1

C 1 1 0 1

D 1 1 1 1

B C

D
 68
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

A B C D

A 0 1 1 1

B 0 0 0 1

C 0 0 0 1

D 0 0 0 0

Adjacency List: Linked list representation of a graph is nothing but an

adjacency list. The following is an example for the above said directed graph.
 69
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

Path matrix: : let G be simple directed graph with m nodes v1,v2,…,vn the
path matrix is square matrix p=v[I,j] is a defined as follows p[I,j]=1 if there is a
path from v[i]to v[j] otherwise zero

Applications of Graphs
Since they are powerful abstractions, graphs can be very important in modeling
data.
 Social network graphs: Graphs that represent who knows whom, who
communicates with whom or other relationships in social structures
 Transportation networks: Graph networks are used by many map
programs such as Google maps, Bing maps and now Apple IOS 6 maps
to find the best routes between locations.
 Utility graphs. The power grid, the Internet, and the water network are
all examples of graphs where vertices represent connection points, and
edges the wires or pipes between them.
 Document link graphs. The best known example is the link graph of the
web, where each web page is a vertex, and each hyperlink a directed
edge.
 Network packet traffic graphs. Vertices are IP (Internet protocol)
addresses and edges are the packets that flow between them.
 Robot planning. Vertices represent states the robot can be in and the
edges the possible transitions between the states.
 Neural networks. Vertices represent neurons and edges the synapses
between them. Neural networks are used to understand how our brain
works and how connections change when we learn.
 Semantic networks. Vertices represent words or concepts and edges
represent the relationships among the words or concepts.
 Graphs in compilers. Graphs are used extensively in compilers. They
can be used for type inference, for so called data flow analysis, register
allocation and many other purposes.
Q) Graph Traversal Mechanisms
Graph nodes can be traversed in two different ways:

 Depth First Search

 Breadth First Search
 70
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

Q) Depth First Search:

Depth First Search, in brief DFS, uses the data structure called Stack to
perform graph traversal. This algorithm executes a Depth-first search on a
graph G beginning at a starting node A.

v1

v3
v2

v6
v4 v5

v7

v8

Explanation:-
Step1:- Visit v1 node adjacency vertices of v1 is ,v2,v3,v8.Let us pick us v2
adjacency vertices are v1,v4,v5.Here v1 is already visited then we pick up v4 .It
adjacency vertices are v2,v8. v2 is already visited then we pickup v8 . It
adjacency vertices are v4, v5, v1,v6, v7. v4, v1 are already visited let us pick up
v5. It’s adjacency vertices are v2, v8. Both are already visited so backtrack. V6,
v7 are unvisited in the list of v8 .We visit v6 it’s adjacency vertices are v8,v3.
Let us we choose v3 it’s adjacency vertices v1,v6,v7. Now we visit v7 them stack
is empty .The DFS travel is

v1

v3
v2

v6
v4 v5

v7

v8
 71
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

Algorithm:
1. Initialize all nodes to the ready state (STATUS=1).
2. Put the starting node A in STACK and change its status to the Waiting state
(STATUS=2).
3. Repeat steps 4 and 5 until STACK is empty.
4. Remove the TOP node N of STACK. Process N and change the status of N to the
processed state (STATUS=3).
5. Add all the neighbors of N that are in the ready state (STATUS=1) on to the TOP,
and change their status to the waiting state (STATUS=2).
[End of step 3 loop.]
6.Exit.

Example:
 72
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
 73
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
 74
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
 75
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

Q) BFS (breadth first search)

BFS (breadth first search)
Algorithm:
1. Initialize all nodes to the ready state (STATUS=1).
2. Insert the starting node A onto QUEUE and change its status to the waiting
state (STATUS=2).
3. Repeat steps 4 and 5 until QUEUE is empty.
4. Pop a node N of QUEUE. Process N and change the status to the processed
state (STATUS=3).
5. Insert onto QUEUE all the neighbors of N that are still in the ready state
(STATUS=1), and change their status to the waiting state (STATUS=2).
[End of step 3 loop.]
6.Exit.

V1

V2 V3

V4 V5 V6 V7

V8
 76
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

We start with V1. Its adjacent vertices are V2, V8, V3. We visit all one by
one.

We pick on one of these, say V2. The unvisited adjacent vertices to V2

are V4, V5. We visit both. We go back to the remaining visited vertices of
V1 and pick on one of those say V3. The unvisited adjacent vertices are
V6, V7. There are no more unvisited adjacent vertices of V8, V4, V5, V6
and V7. Thus the sequence so generated is
V1 V2 V8 V3 V4 V5 V6 V7

Here we need a queue instead of a stack to implement it. We add

unvisited vertices adjacent to the one just visited at the rear and read
at front to find the next vertex to visit.

V1 V1 V1

V2 V8 V3
V2 V3

V8 V4 V5

V1

V2 V8 V3

V4 V5 V6 V7
 77
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

Queue Visited Nodes

V1
V11

V2 V8 V3
V2 V8 V3

V8 V3 V4 V5 V4 V5

V6 V7
V3 V4 V5 V6 V7

V4 V5 V6 V7

V5 V6 V7

V6 V7

V7

Empty Q

The sequence generated is V1 V2 V8 V3 V4 V5 V6 V7.

The sequence generated is V1 V2 V8 V3 V4 V5 V6 V7.

 78
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

Example:
 79
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

’
 80
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
 81
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

Path: a path sequence of vertices that map a source vertex to the destination
vertex.
Cycle: A cycle is a path in which the source & destination vertices are same.
Adjcent Vertices: A vertex v1 is said be adjacent to vertex v2 if there exists an
edge (v1, v2) or (v2, v1).
Degree: The number of edges incident on a vertex determine its degree.
Indegree & Outdegree: The number of edges that are coming towards a vertex
is said be the “In Degree” & the number of edges that are going away from the
vertex is said be the “Out degree”.
Complete Graph: A graph G is said be complete or fully connected if there is
path from every vertex to every other vertex. A complete graph with n vertices
will have n (n-1)/2 edges.
Connected Graph: A graph is said to be connected if there exists a path from
any vertex to any vertex of the graph other wise such a graph is said to be
unconnected graph.
Explain Spanning Tree ? Find Minimum Spanning Cost
Q)Spanning Tree: A tree T is said be spanning tree of a connected graph G (V,
E) such that,
1. Every vertex of G belongs to an edge T and
2. The edges in T form a tree.
Minimum cost spanning Tree: A connected graph can have more than one
spanning tree; if we select or calculate the spanning that can be constructed
with low cost is said to be minimum cost spanning tree.
 82
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
Tree graph: A graph is said to be a tree graph if it has 2 properties:
1) It is connected, and
2) There are no cycles in the graph.
Path Matrix: A matrix that holds a ‘1’ (one) if there exists a path between any
two nodes of a graph otherwise it holds a ‘0’ (zero). It is also known as
‘reachability matrix’.
Hamitonian Path: A path is said to be Hamiltonian path if that passes
through each of the vertices in a graph exactly once.

Algorithm Purpose
Krushkal’s algorithm To find the min. cost spanning
Tree
Prim’s algorithm To find the min. cost spanning
Tree
Dijkstra’s Algorithm To find single source shortest
paths on a weighted digraph.
Warshall’s algorithm To find the path matrix of a
graph
BFS & DFS algorithms Graph traversal algorithms

Warshall’s algorithm: -
A directed graph G with M nodes is maintained in memory by it adjacency
matrix A. This algorithm finds the path matrix P of the graph G.
Step1: - Repeat for I, j=1,2…m (initialize of P)
If A [I, j]=0 then set p [I, j] =0
Else
Set p [I, j]=1
(end loop)
Step2: - repeat step3&4 for k=1,2,3 …….m (updates p)
Step3: - repeat step 4 for I =1, 2,3…m
Step4: - repeat for j=1,2,3…m
set p [I, j]=p[I, j] v (p[I, k] ^ p[k, j])
(end of loop)
 83
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
(end of step3 loop)
(end of step2 loop)
Step5: - exit.

Time complexity: The amount of time taken by an algorithm to execute itself

is said to be the time complexity. There will be three cases in calculating time
complexity.
They are: worst case, average case and best case.
For ex: bubble sort – O (n2)
Garbage Collection: It is a process of identifying & reclaiming the free nodes.
It has 2 phases: marking phase, collection phase. In marking phase, all the
nodes that are accessible are marked where as in collection phase, all
unmarked nodes are made free so that the memory can be reclaimed.
Recursion Vs Iteration

Recursion Iteration
1.It is a technique of defining 1. It is a process of executing itself
anything in terms of itself. a statement or a set of statements
repeatedly until a given condition
satisfied.
2. There must a terminating 2. Iteration involves 4 clear steps:
condition to stop the process. initialization, condition, execution
and updation.
3. Not all problems have recursive 3. Any recursive problem can be
solution. solved iteratively.
4. Recursion will be a overhead on 4. It is a process that utilizes less
the processor as it consumes much cpu time & space to execute itself.
memory & time.
5. Recursive concepts can be 5. Relatively bigger in code compare
implemented in less code. to Recursion.
 84
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
6. Requires stack to implement 6. Does not use any stack data
itself. structure.

Q) Explain Topological sort

An ordering of the vertices in a directed acyclic graph, such that: If there is a
path from u to v, then v appears after u in the ordering.
Types of graphs:
The graphs should be directed: otherwise for any edge (u,v)
there would be a path from u to v and also from v to u,
and hence they cannot be ordered. The graphs should be acyclic: otherwise for
any two vertices u and v on a cycle
u would precede v and v would precede u. The ordering may not be unique
V1, V2, V3, V4 and V1, V3, V2, V4 are legal orderings

Degree of a vertex U: the number of edges (U,V) - outgoing edges

Indegree of a vertex U: the number of edges (V,U) - incoming edgesThe
algorithm for topological sort uses "indegrees" of vertices.
 85
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
Algorithm
Compute the indegrees of all vertices

Find a vertex U with indegree 0 and print it (store it in the ordering)

If there is no such vertex then there is a cycle

and the vertices cannot be ordered. Stop.

Remove U and all its edges (U,V) from the graph.

Update the indegrees of the remaining vertices.

Repeat steps 2 through 4 while there are vertices to be processed.

Example

Compute the indegrees:

V1: 0
V2: 1
V3: 2
V4: 2
V5: 2

Find a vertex with indegree 0: V1

Output V1 , remove V1 and update the indegrees:

Sorted: V1
Remove edges: (V1,V2) , (V1, V3) and (V1,V4)
Updated indegrees:
 86
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
V2: 0
V3: 1
V4: 1
V5: 2

The process is depicted in the following table:

Indegree

Sorted à V1 V1,V2 V1,V2,V4 V1,V2,V4,V3 V1,V2,V4,V3,V5

V1 0

V2 1 0

V3 2 1 1 0

V4 2 1 0

V5 2 2 1 0 0

One possible sorting: V1, V2, V4, V3, V5

Another sorting: V1, V2, V4, V5, V3

Complexity of this algorithm: O(|V| 2), |V| - the number of vertices.

To find a vertex of indegree 0 we scan all the vertices - |V| operations.

We do this for all vertices: |V|2

Improved algorithm
After the initial scanning to find a vertex of degree 0, we need to scan
only those vertices whose updated indegrees have become equal to zero.

Store all vertices with indegree 0 in a queue

 87
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
get a vertex U and place it in the sorted sequence (array or another
queue).

For all edges (U,V) update the indegree of V, and put V in the queue if the
updated indegree is 0.

Perform steps 2 and 3 while the queue is not empty.

Q) Explain Spanning Tree
A spanning tree is a subset of Graph G, which has all the vertices covered with
minimum possible number of edges. Hence, a spanning tree does not have cycles and
it cannot be disconnected. Every connected and undirected Graph G has at least one
spanning tree. A disconnected graph does not have any spanning tree, as it cannot be
spanned to all its vertices.
We found three spanning trees off one complete graph. A complete undirected graph
can have maximum nn-2
number of spanning trees, where n is the number of nodes. In the above addressed

example, 33−2 = 3 spanning trees are possible.

General Properties of Spanning Tree

 Following are a few properties of the spanning tree connected to graph G −
 A connected graph G can have more than one spanning tree.
 All possible spanning trees of graph G, have the same number of edges and
vertices.
 The spanning tree does not have any cycle (loops).
 Removing one edge from the spanning tree will make the graph disconnected,
i.e. the spanning tree is minimally connected.
 Adding one edge to the spanning tree will create a circuit or loop, i.e. the
spanning tree is maximally acyclic.
 Mathematical Properties of Spanning Tree
 Spanning tree has n-1 edges, where n is the number of nodes (vertices).
 From a complete graph, by removing maximum e - n + 1 edges, we can
construct a spanning tree.
 A complete graph can have maximum n n-2 number of spanning trees.
 88
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
Application of Spanning Tree
Spanning tree is basically used to find a minimum path to connect all nodes in
a graph.
Common applications of spanning trees are −
 Civil Network Planning
 Computer Network Routing Protocol
 Cluster Analysis
Q) Explain Minimum spanning tree
A minimum spanning tree (MST) for a graph G = (V, E) is a sub graph
G1 = (V1, E1) of G contains all the vertices of G.

1. The vertex set V1 is same as that at graph G.

2. The edge set E1 is a subset of G.
3. And there is no cycle.

If a graph G is not a connected graph, then it cannot have any spanning tree.
Suppose a graph G with n vertices then the MST will have (n – 1) edges,
assuming that the graph is connected. A minimum spanning tree (MST) for a
weighted graph is a spanning tree with minimum weight .That is all the
vertices in the weighted graph will be connected with minimum edge with
minimum weights.
Two algorithms can be used to obtain a minimum spanning tree of a connected
weighted and undirected graph.
Q) Kruskal‟s Algorithm
Explain KRUSKAL’S ALGORITHM
1. This is a one of the popular algorithm and was developed by Joseph
Kruskal. To create a minimum cost spanning trees, using Kruskalls, we
begin by choosing the edge with the minimum cost and add it to the
spanning tree. In the next step, select the edge with next
2. lowest cost, and so on, until we have selected (n – 1) edges to form the
complete
3. spanning tee. The only thing of which beware is that we don‟t form any
cycles as we add edges to the spanning tree.
ALGORITHM
Suppose G = (V, E) is a graph, and T is a minimum spanning tree of graph G.

1. Initialize the spanning tree T to contain all the vertices in the graph G but no
edges.
 89
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
2. Choose the edge e with lowest weight from graph G.

3. Check if both vertices from e are within the same set in the tree T, for all
such sets of T.If it is not present, add the edge e to the tree T, and replace the
two sets that this edge connects.

4. Delete the edge e from the graph G and repeat the step 2 and 3 until there is
no more edge to add or until the panning tree T contains (n-1) vertices.

5. Exit

Q) Explain Prim's Algorithm

Prim's algorithm is a greedy algorithm that finds a minimum spanning tree
for a

connected weighted undirected graph.

It finds a subset of the edges that forms a tree that includes every vertex,
where the total weight of all the edges in the tree is minimized.
 90
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
This algorithm is directly based on the MST( minimum spanning tree)
property.

ALGORITHM

Suppose G = (V,E) is a graph and T is a minimum spanning tree of graph G.

1. Initialize the spanning tree T to contain a vertex v1.

2. Choose an edge e = (v1, v2) of G such that v2 not equal to v1 and e has
smallest weight among the edges of G incident with v1.

3. Select an edge e = (v2, v3) of G such that v2 is not equal to v3 and e has
smallest weight among the edge of G incident with v2.

4. Suppose the edge e1, e2, e3, ...... ei Then select an edge ei + 1 = (Vj, Vk) such
that

(a) Vj ∈ {v1, v2, v3, ...........vi, vi + 1} and

(b) Vk ∉ {v1, v2, v3, ...... vi, vi + 1} such that ei+1 has smallest weight among
the edge of G

5. Repeat the step 4 until (n – 1) edges have been chosen

6. Exit
 91
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

Now, Cost of Minimum Spanning Tree

= Sum of all edge weights
= 1 + 4 + 2 + 6 + 3 + 10
= 26 units

UNIT-5 – SORT AND TYPES OF SORT

Q1)Explain about BUBBLE sort?
Bubble sort is a simple sorting algorithm. This sorting algorithm is
comparison-based algorithm in which each pair of adjacent
elements is compared and the elements are swapped if they are not
in order. This algorithm is not suitable for large data sets.
Algorithm:
We assume list is an array of n elements. We further assume
that swapfunction swaps the va

Bubble Sort Procedure:

We take an unsorted array for our example.
 92
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
Iteration-1:
Bubble sort starts with very first two elements, comparing them to check
which one is greater.

In this case, value 33 is greater than 14, so it is already in sorted locations.

Next, we compare 33 with 27.

We find that 27 is smaller than 33 and these two values must be swapped.

The new array should look like this −

Next we compare 33 and 35. We find that both are in already sorted positions.

Then we move to the next two values, 35 and 10.

We know then that 10 is smaller 35. Hence they are not sorted.

We swap these values. We find that we have reached the end of the array. After one
iteration, the array should look like this −
 93
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

Iteration-2:
To be precise, we are now showing how an array should look like after each
iteration. After the second iteration, it should look like this −

Iteration-3:
Notice that after each iteration, at least one value moves at the end.

Iteration-4:
And when there's no swap required, bubble sorts learns that an array is
completely sorted.

Now we should look into some practical aspects of bubble sort.

Q2)Explain about INSERTION sort?

Sorting: Sorting is the process of arranging a list of elements in a particular
order (Ascending or Descending).
Insertion sort:
Insertion sort algorithm arranges a list of elements in a particular order. In
insertion sort algorithm, every iteration moves an element from unsorted
portion to sorted portion until all the elements are sorted in the list.

Step by Step Process: The insertion sort algorithm is performed using

following steps...
 94
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
Step 1: Asume that first element in the list is in sorted portion of the list and
remaining all elements are in unsorted portion.

Step 2: Consider first element from the unsorted list and insert that element
into the sorted list in order specified.

Step 3: Repeat the above process until all the elements from the unsorted list
are moved into the sorted list.

Example:
 95
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
 96
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

Q 3)Explain about SELECTION sort?

Selection Sort:

Selection Sort algorithm is used to arrange a list of elements in a particular

order (Ascending or Descending). In selection sort, the first element in the list
is selected and it is compared repeatedly with remaining all the elements in the
list. If any element is smaller than the selected element (for Ascending order),
then both are swapped. Then we select the element at second position in the
list and it is compared with remaining all elements in the list. If any element is
smaller than the selected element, then both are swapped. This procedure is
repeated till the entire list is sorted.

Step by Step Process: The selection sort algorithm is performed using following
steps...

Step 1: Select the first element of the list (i.e., Element at first position in the list).

Step 2: Compare the selected element with all other elements in the list.

Step 3: For every comparison, if any element is smaller than selected element (for Ascending
order), then these two are swapped.

Step 4: Repeat the same procedure with next position in the list till the entire list is sorted.

Sorting Logic: Following is the sample code for selection sort...

Example:
 97
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
 98
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
 99
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

Q 4)Explain about QUICK sort?

Quick sort technique is based on the divide and conquer design technique. In
this technique at every step each element is placed in its proper position. It
performs very well on longer lists. It works recursively, by first selecting a
random “pivot value” from the list(Array). Then it partitions the list into
elements that are less than the pivot and greater than the pivot. The problem
of sorting a given list is reduced to the problem of sorting two sublists. And
process continues until the list is sorted.
Example:
Consider the list

We have to sort it using quick sort.

Scanning from right to left, the first number visited that has value less than 50
is 30 thus exchange both of them.

Scanning from left to right, the first number visited that has value greater than
50 is 60, so exchange both of them.
 100
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
Scanning from right to left, the first number visited that has value less than 50
is 45, so exchange both of them.

Scanning from left to right, the first number visited that has value greater than
50 is 80, so exchange both of them.

After Scanning, the number 50 is placed in its proper position and we get
sublists, sublist-1 and sublist-2. Sublist-2 has value greater than 50 while
sublist-1 has value lesser than 50, the whole process is repeated for both the
sublists to obtained,

After applying the same method again and again for new sublist until we get
the elements that cannot be sorted further, the final list that we get is the
sorted list as shown below:

Q) Explain about MERGE sort?

Merge sort is a perfect example of a successful application of the divide-and-
conquer technique. It sorts a given array A[0.…n-1] by dividing it into two
halves A[0….[n/2]-1] and A[[n/2]…n-1], sorting each of them recursively and
then merging the two smaller arrays into single sorted one.
 101
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

Algorithm:
Merge-sort( A[0….n-1])

//Sorts array A[0….n-1] recursively

//Input: An array A[0….n-1] to be sorted

//Output: Array A[0….n-1] sorted in increasing order.

If(n>1)

Copy A[0…[n/2]-1] to B[0…[n/2]-1]

Copy A[[n/2]…n-1] to C[0…[n/2]-1]

Mergesort(B[0…[n/2]-1])

Mergesort(C[0…[n/2]-1])

Merge(B,C,A)

Procedure:

To understand merge sort, we take an unsorted array as the following –

We know that merge sort first divides the whole array iteratively into equal
halves unless the atomic values are achieved. We see here that an array of 8
items is divided into two arrays of size 4.

This does not change the sequence of appearance of items in the original. Now
we divide these two arrays into halves.
 102
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
We further divide these arrays and we achieve atomic value which can no more
be divided.

Now, we combine them in exactly the same manner as they were broken down
with a sorted order.

Compare every 2 elements individually, if they are in sorted order combined

them. Otherwise first swapping them and next combined them.

In the next iteration of the combining phase, we compare lists of two data
values, and merge them into a list of found data values placing all in a sorted
order.

After the final merging, the list should look like this –

Searching
Searching is the process of finding some particular element in the list. If the
element is present in the list, then the process is called successful and the
process returns the location of that element, otherwise the search is called
unsuccessful.

There are two popular search methods that are widely used in order to search
some item into the list. However, choice of the algorithm depends upon the
arrangement of the list.

 Linear Search
 Binary Search
 103
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

Linear Search
Linear search is the simplest search algorithm and often called sequential
search. In this type of searching, we simply traverse the list completely and
match each element of the list with the item whose location is to be found. If
the match found then location of the item is returned otherwise the algorithm
return NULL.

Linear search is mostly used to search an unordered list in which the items are
not sorted. The algorithm of linear search

Algorithm
o LINEAR_SEARCH(A, N, VAL)
o Step 1: [INITIALIZE] SET POS = -1
o Step 2: [INITIALIZE] SET I = 1
o Step 3: Repeat Step 4 while I<=N
o Step 4: IF A[I] = VAL
SET POS = I
PRINT POS
Go to Step 6
[END OF IF]
SET I = I + 1
[END OF LOOP]
o Step 5: IF POS = -1
PRINT " VALUE IS NOT PRESENTIN THE ARRAY "
[END OF IF]
o Step 6: EXIT

Binary Search
Binary search is the search technique which works efficiently on the sorted
lists. Hence, in order to search an element into some list by using binary
search technique, we must ensure that the list is sorted.

Binary search follows divide and conquer approach in which, the list is divided
into two halves and the item is compared with the middle element of the list. If
the match is found then, the location of middle element is returned otherwise,
 104
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
we search into either of the halves depending upon the result produced
through the match.

Binary search algorithm is given below.

BINARY_SEARCH(A, lower_bound, upper_bound, VAL)

o Step 1: [INITIALIZE] SET BEG = lower_bound
END = upper_bound, POS = - 1
o Step 2: Repeat Steps 3 and 4 while BEG <=END
o Step 3: SET MID = (BEG + END)/2
o Step 4: IF A[MID] = VAL
SET POS = MID
PRINT POS
Go to Step 6
ELSE IF A[MID] > VAL
SET END = MID - 1
ELSE
SET BEG = MID + 1
[END OF IF]
[END OF LOOP]
o Step 5: IF POS = -1
PRINT "VALUE IS NOT PRESENT IN THE ARRAY"
[END OF IF]
o Step 6: EXIT

Indexed Sequential Search

Another technique to improve search efficiency for a sorted file is indexed sequential search. But it
involves an increase in the amount of memory space required. An auxiliary table called an index, is set
aside in addition to a sorted file. Each element in the index table consists of a key Kindex and pointer to
the record in the field that corresponds to the kindex. The elements in the index, as well as elements in
the file, must be sorted on the file.
 105
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
The algorithm used for searching an indexed sequential file is simple and straight. Let r, k and key be
defined as before. Let k index be an array of the keys in the index, and let pindex be the array of
pointers within the index to the actual records in the file, and the size of index is also taken in a variable.
The indexed sequential search can be explained as the following example in the figure.

The advantage of the indexed sequential method is that items in the table can be examined sequentially
if all records in the file have to be accessed, yet the search time for particular items is reduced. A
sequential search is performed on the smaller index rather than on the large table. Once the index
position is found, the search is made on the record table itself.

Deletion from an indexed sequential table can be most easily by flagging deleted entries. When
sequential searching is done deleted items are ignored. The item is deleted from the original table.

Insertion into an indexed sequential table may be difficult as there may not be any place between two
table entries which may lead to a shift to a large number of elements.
 106
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

Write c program for stack operations using arrays

#include <stdio.h>
#include <conio.h>
int stack[100],i,j,choice=0,n,top=-1;
void push();
void pop();
void show();
void main ()
{
clrscr();

printf("Enter the number of elements in the stack ");

scanf("%d",&n);
printf("*********Stack operations using array*********");

printf("\n -------------------------------------------------\n");
while(choice != 4)
{
printf("\nChose one from the below options...\n");
printf("\n1.Push\n2.Pop\n3.Show\n4.Exit");
printf("\n Enter your choice \n");
scanf("%d",&choice);
switch(choice)
{
case 1:
{
push();
break;
}
case 2:
{
pop();
break;
}
case 3:
{
show();
break;
}
case 4:
{
printf("Exiting. .... ");
break;
}
default:
 107
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
{
printf("Please Enter valid choice ");
}
};
}
}

void push ()
{
int val;
if (top == n-1 )
printf("\n Overflow");
else
{
printf("Enter the value?");
scanf("%d",&val);
top = top +1;
stack[top] = val;
}
}

void pop ()
{
if(top == -1)
printf("Underflow");
else
{
printf("the delted value =%d\n",stack[top]);
top = top -1;
}
}
void show()
{
for (i=top;i>=0;i--)
{
printf("%d\n",stack[i]);
}
if(top == -1)
{
printf("\nStack is empty\n");
}
}
 108
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

Write c program stack operations using linked list method

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
void push();
void pop();
void display();
struct node
{
int val;
struct node *next;
};
struct node *head;
void main ()
{
int choice=0;
printf("\n*********Stack operations using linked list*********\n");
printf("\n ------------------------------------------- \n");
while(choice!=4)
 109
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
{
printf("\n\nChose one from the below options...\n");
printf("\n1.Push\n2.Pop\n3.Show\n4.Exit");
printf("\n Enter your choice \n");
scanf("%d",&choice);
switch(choice)
{
case 1:
{
push();
break;
}
case 2:
{
pop();
break;
}
case 3:
{
display();
break;
}
case 4:
{
printf("Exiting. ....");
break;
}
default:
{
printf("Please Enter valid choice ");
}
};
}
}
void push ()
{
int val;
struct node *ptr = (struct node*)malloc(sizeof(struct node));
if(ptr == NULL)
{
 110
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
printf("not able to push the element");
}
else
{
printf("Enter the value");
scanf("%d",&val);
if(head==NULL)
{
ptr->val = val;
ptr -> next = NULL;
head=ptr;
}
else
{
ptr->val = val;
ptr->next = head;
head=ptr;

}
printf("Item pushed");
}
}

void pop()
{
int item;
struct node *ptr;
if (head == NULL)
{
printf("Underflow");
}
else
{
item = head->val;
ptr = head;
head = head->next;
free(ptr);
printf("Item popped");

}
 111
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
}
void display()
{
int i;
struct node *ptr;
ptr=head;
if(ptr == NULL)
{
printf("Stack is empty\n");
}
else
{
printf("Printing Stack elements \n");
while(ptr!=NULL)
{
printf("%d\n",ptr->val);
ptr = ptr->next;
}
}
}
 112
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

Write a c program queue operation using arrays

#include <stdio.h>
#include<stdlib.h>
#include <conio.h>
#define MAX 4
void insert();
void delete();
void display();
 113
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
int queue_array[MAX];
int rear = - 1;
int front = - 1;
int main()
{
int choice;
clrscr();
while (1)
{
printf("1.Insert element to queue\n");
printf("2.Delete element from queue \n");
printf("3.Display all elements of queue \n");
printf("4.Quit\n");
printf("Enter your choice :\n ");
scanf("%d", &choice);
switch(choice)
{
case 1:
insert();
break;
case 2:
delete();
break;
case 3:
display();
break;
case 4:
exit(1);
default:
printf("Wrong choice\n");
}
}
}
void insert()
{
int item;
if(rear == MAX - 1)
printf("Queue Overflow\n");
else
{
 114
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
if(front== - 1)
front = 0;
printf("Inset the element in queue :\n ");
scanf("%d", &item);
rear = rear + 1;
queue_array[rear] = item;
}
}
void delete()
{
if(front == - 1 || front > rear)
{
printf("Queue Underflow \n");
return;
}
else
{
printf("Element deleted from queue is : %d\n", queue_array[front]);
front = front + 1;
}
}
void display()
{
int i;
if(front == - 1)
printf("Queue is empty \n");
else
{
printf("Queue is : \n");
for(i = front; i <= rear; i++)
printf("%d ", queue_array[i]);
printf("\n");
}
}
 115
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
 116
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

Write a c program linked list operations create,insert,deletion,searching?

#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
};
struct node *head;

void beginsert ();

void lastinsert ();
void randominsert();
void begin_delete();
void last_delete();
void random_delete();
void display();
void search();
void main ()
{
int choice =0;
while(choice != 9)
{
printf("\n\n*********Main Menu*********\n");
printf("\nChoose one option from the following list ...\n");
printf("\n===============================================\n");
printf("\n1.Insert in begining\n2.Insert at last\n3.Insert at any
random location\n
4. Delete from Beginning\n 5.Delete from last\n6.Delete node after
specified location\n7.Search for an element\n
8.Show\n9.Exit\n");
printf("\nEnter your choice?\n");
scanf("\n%d",&choice);
switch(choice)
{
case 1:
beginsert();
break; case
2:
 117
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
lastinsert();
break;
case 3:
randominsert();
break;
case 4:
begin_delete();
break;
case 5:
last_delete();
break;
case 6:
random_delete();
break;
case 7:
search();
break;
case 8:
display();
break;
case 9:
exit(0);
break;
default:
printf("Please enter valid choice..");
}
}
}
void beginsert()
{
struct node *ptr;
int item;
ptr = (struct node *) malloc(sizeof(struct node *));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter value\n");
 118
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
scanf("%d",&item);
ptr->data = item;
ptr->next = head;
head = ptr;
printf("\nNode inserted");
}

}
void lastinsert()
{
struct node *ptr,*temp;
int item;
ptr = (struct node*)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter value?\n");
scanf("%d",&item);
ptr->data = item;
if(head == NULL)
{
ptr -> next = NULL;
head = ptr;
printf("\nNode inserted");
}
else
{
temp = head;
while (temp -> next != NULL)
{
temp = temp -> next;
}
temp->next = ptr;
ptr->next = NULL;
printf("\nNode inserted");

}
 119
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
}
}
void randominsert()
{
int i,loc,item;
struct node *ptr, *temp;
ptr = (struct node *) malloc (sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter element value");
scanf("%d",&item);
ptr->data = item;
printf("\nEnter the location after which you want to insert ");
scanf("\n%d",&loc);
temp=head;
for(i=0;i<loc;i++)
{
temp = temp->next;
if(temp == NULL)
{
printf("\ncan't insert\n");
return;
}

}
ptr ->next = temp ->next;
temp ->next = ptr;
printf("\nNode inserted");
}
}
void begin_delete()
{
struct node *ptr;
if(head == NULL)
{
printf("\nList is empty\n");
 120
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
}
else
{
ptr = head;
head = ptr->next;
free(ptr);
printf("\nNode deleted from the begining ...\n");
}
}
void last_delete()
{
struct node *ptr,*ptr1;
if(head == NULL)
{
printf("\nlist is empty");
}
else if(head -> next == NULL)
{
head = NULL;
free(head);
printf("\nOnly node of the list deleted ...\n");
}

else
{
ptr = head;
while(ptr->next != NULL)
{
ptr1 = ptr;
ptr = ptr ->next;
}
ptr1->next = NULL;
free(ptr);
printf("\nDeleted Node from the last ...\n");
}
}
void random_delete()
{
struct node *ptr,*ptr1;
int loc,i;
 121
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
printf("\n Enter the location of the node after which you want to
perform deletion \n");
scanf("%d",&loc);
ptr=head;
for(i=0;i<loc;i++)
{
ptr1 = ptr;
ptr = ptr->next;

if(ptr == NULL)
{
printf("\nCan't delete");
return;
}
}
ptr1 ->next = ptr ->next;
free(ptr);
printf("\nDeleted node %d ",loc+1);
}
void search()
{
struct node *ptr;
int item,i=0,flag;
ptr = head;
if(ptr == NULL)
{
printf("\nEmpty List\n");
}
else
{
printf("\nEnter item which you want to search?\n");
scanf("%d",&item);
while (ptr!=NULL)
{
if(ptr->data == item)
{
printf("item found at location %d ",i+1);
flag=0;
}
else
 122
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
{
flag=1;
}
i++;
ptr = ptr -> next;
}
if(flag==1)
{
printf("Item not found\n");
}
}

void display()
{
struct node *ptr;
ptr = head;
if(ptr == NULL)
{
printf("Nothing to print");
}
else
{
printf("\nprinting values .............\n");
while (ptr!=NULL)
{
printf("\n%d",ptr->data);
ptr = ptr -> next;
}
}
}
 123
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

Write a cprogram double linked list operations?

#include<stdio.h>
#include<stdlib.h>
struct node
{
struct node *prev;
struct node *next;
int data;
};
struct node *head;
void insertion_beginning();
void insertion_last();
void insertion_specified();
void deletion_beginning();
 124
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
void deletion_last();
void deletion_specified();
void display();
void search();
void main ()
{
int choice =0;
while(choice != 9)
{
printf("\n*********Main Menu*********\n");
printf("\nChoose one option from the following list ...\n");
printf("\n===============================================\n");
printf("\n1.Insert in begining\n2.Insert at last\n3.Insert at any
random location\n4.Delete from Beginning\n
5. Delete from last\n6.Delete the node after the given
data\n7.Search\n8.Show\n9.Exit\n");
printf("\nEnter your choice?\n");
scanf("\n%d",&choice);
switch(choice)
{
case 1:
insertion_beginning();
break;
case 2:
insertion_last();
break;
case 3:
insertion_specified();
break;
case 4:
deletion_beginning();
break;
case 5:
deletion_last();
break;
case 6:
deletion_specified();
break;
case 7:
search();
 125
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
break;
case 8:
display();
break;
case 9:
exit(0);
break;
default:
printf("Please enter valid choice..");
}
}
}
void insertion_beginning()
{
struct node *ptr;
int item;
ptr = (struct node *)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter Item value");
scanf("%d",&item);

if(head==NULL)
{
ptr->next = NULL;
ptr->prev=NULL;
ptr->data=item;
head=ptr;
}
else
{
ptr->data=item;
ptr->prev=NULL;
ptr->next = head;
head->prev=ptr;
head=ptr;
 126
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
}
printf("\nNode inserted\n");
}

}
void insertion_last()
{
struct node *ptr,*temp;
int item;
ptr = (struct node *) malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter value");
scanf("%d",&item);
ptr->data=item;
if(head == NULL)
{
ptr->next = NULL;
ptr->prev = NULL;
head = ptr;
}
else
{
temp = head;
while(temp->next!=NULL)
{
temp = temp->next;
}
temp->next = ptr;
ptr ->prev=temp;
ptr->next = NULL;
}

}
printf("\nnode inserted\n");
}
 127
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
void insertion_specified()
{
struct node *ptr,*temp;
int item,loc,i;
ptr = (struct node *)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\n OVERFLOW");
}
else
{
temp=head;
printf("Enter the location");
scanf("%d",&loc);
for(i=0;i<loc;i++)
{
temp = temp->next;
if(temp == NULL)
{
printf("\n There are less than %d elements", loc);
return;
}
}
printf("Enter value");
scanf("%d",&item);
ptr->data = item;
ptr->next = temp->next;
ptr -> prev = temp;
temp->next = ptr;
temp->next->prev=ptr;
printf("\nnode inserted\n");
}
}
void deletion_beginning()
{
struct node *ptr;
if(head == NULL)
{
printf("\n UNDERFLOW");
}
 128
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
else if(head->next == NULL)
{
head = NULL;
free(head);
printf("\nnode deleted\n");
}
else
{
ptr = head;
head = head -> next;
head -> prev = NULL;
free(ptr);
printf("\nnode deleted\n");
}

}
void deletion_last()
{
struct node *ptr;
if(head == NULL)
{
printf("\n UNDERFLOW");
}
else if(head->next == NULL)
{
head = NULL;
free(head);
printf("\nnode deleted\n");
}
else
{
ptr = head;
if(ptr->next != NULL)
{
ptr = ptr -> next;
}
ptr -> prev -> next = NULL;
free(ptr);
printf("\nnode deleted\n");
}
 129
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
}
void deletion_specified()
{
struct node *ptr, *temp;
int val;
printf("\n Enter the data after which the node is to be deleted : ");
scanf("%d", &val);
ptr = head;
while(ptr -> data != val)
ptr = ptr -> next;
if(ptr -> next == NULL)
{
printf("\nCan't delete\n");
}
else if(ptr -> next -> next == NULL)
{
ptr ->next = NULL;
}
else
{
temp = ptr -> next;
ptr -> next = temp -> next;
temp -> next -> prev = ptr;
free(temp);
printf("\nnode deleted\n");
}
}
void display()
{
struct node *ptr;
printf("\n printing values...\n");
ptr = head;
while(ptr != NULL)
{
printf("%d\n",ptr->data);
ptr=ptr->next;
}
}
void search()
{
 130
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
struct node *ptr;
int item,i=0,flag;
ptr = head;
if(ptr == NULL)
{
printf("\nEmpty List\n");
}
else
{
printf("\nEnter item which you want to search?\n");
scanf("%d",&item);
while (ptr!=NULL)
{
if(ptr->data == item)
{
printf("\nitem found at location %d ",i+1);
flag=0;
break;
}
else
{
flag=1;
}
i++;
ptr = ptr -> next;
}
if(flag==1)
{
printf("\nItem not found\n");
}
}

}
 131
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

Write a c program circular queue program using arrays

#include <stdio.h>
#include <conio.h>
# define max 6
int queue[max]; // array declaration
int front=-1;
int rear=-1;
// function to insert an element in a circular queue
void enqueue(int element)
{
if(front==-1 && rear==-1) // condition to check queue is empty
{
front=0;
rear=0;
queue[rear]=element;
}
else if((rear+1)%max==front) // condition to check queue is full
 132
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

{
printf("Queue is overflow..");
}
else
{
rear=(rear+1)%max; // rear is incremented
queue[rear]=element; // assigning a value to the queue at the r
ear position.
}
}

// function to delete the element from the queue

int dequeue()
{
if((front==-1) && (rear==-1)) // condition to check queue is empty
{
printf("\nQueue is underflow..");
}
else if(front==rear)
{
printf("\nThe dequeued element is %d", queue[front]);
front=-1;
rear=-1;
}
else
{
printf("\nThe dequeued element is %d", queue[front]);
front=(front+1)%max;
}
}
// function to display the elements of a queue
void display()
{
int i=front;
if(front==-1 && rear==-1)
{
 133
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

printf("\n Queue is empty..");

}
else
{
printf("\nElements in a Queue are :");
while(i<=rear)
{
printf("%d,", queue[i]);
i=(i+1)%max;
}
}
}
int main()
{
int choice=1,x; // variables declaration

while(choice<4 && choice!=0) // while loop

{
printf("\n Press 1: Insert an element");
printf("\nPress 2: Delete an element");
printf("\nPress 3: Display the element");
printf("\nEnter your choice");
scanf("%d", &choice);

switch(choice)
{

case 1:

printf("Enter the element which is to be inserted");

scanf("%d", &x);
enqueue(x);
break;
case 2:
dequeue();
break;
 134
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

case 3:
display();

}}
return 0;
}
 135
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

Write a c program priority queue

# include<stdio.h>
# include<malloc.h>
typedef struct node
{
int priority;
int info;
struct node *link;
}NODE;
NODE *front = NULL;

// insert method
void insert(int data,int priority)
{
NODE *temp,*q;

temp = (NODE *)malloc(sizeof(NODE));

temp->info = data;
temp->priority = priority;
// condition to check whether the first element is empty or the ele
ment to be inserted has more priority than the first element
if( front == NULL || priority < front->priority )
{
temp->link = front;
front = temp;
}
else
{
q = front;
while( q->link != NULL && q->link->priority <= priority )
q=q->link;
temp->link = q->link;
q->link = temp;
}
}
 136
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

// delete method

void del()
{
NODE *temp;
// condition to check whether the Queue is empty or not
if(front == NULL)
printf("Queue Underflow\n");
else
{
temp = front;
printf("Deleted item is %d\n", temp->info);
front = front->link;
free(temp);
}

// display method
void display()
{
NODE *ptr;
ptr = front;
if(front == NULL)
printf("Queue is empty\n");
else
{
printf("Queue is :\n");
printf("Priority Item\n");
while(ptr != NULL)
{
printf("%5d %5d\n",ptr->priority,ptr->info);
ptr = ptr->link;
}
}
}
/*End of display*/
 137
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

// main method
int main()
{
int choice, data, priority;
do
{
printf("1.Insert\n");
printf("2.Delete\n");
printf("3.Display\n");
printf("4.Quit\n");
printf("Enter your choice : ");
scanf("%d", &choice);
switch(choice)
{
case 1:
printf("Enter the data which is to be added in the queue : ");
scanf("%d",&data);
printf("Enter its priority : ");
scanf("%d",&priority);
insert(data,priority);
break;
case 2:
del();
break;
case 3:
display();
break;
case 4:
break;
default :
printf("Wrong choice\n");
}
}
while(choice!=4);
return 0;
}
 138
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

Output

Write a c program using double linked list operations?

#include<stdio.h>
#include<stdlib.h>
struct node
{
struct node *prev;
struct node *next;
int data;
};
struct node *head;
void insertion_beginning();
void insertion_last();
void insertion_specified();
void deletion_beginning();
void deletion_last();
void deletion_specified();
 139
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
void display();
void search();
void main ()
{
int choice =0;
while(choice != 9)
{
printf("\n*********Main Menu*********\n");
printf("\nChoose one option from the following list ...\n");
printf("\n===============================================\n");
printf("\n1.Insert in begining\n2.Insert at last\n3.Insert at any
random location\n4.Delete from Beginning\n
5.Delete from last\n6.Delete the node after the given
data\n7.Search\n8.Show\n9.Exit\n");
printf("\nEnter your choice?\n");
scanf("\n%d",&choice);
switch(choice)
{
case 1:
insertion_beginning();
break;
case 2:
insertion_last();
break;
case 3:
insertion_specified();
break;
case 4:
deletion_beginning();
break;
case 5:
deletion_last();
break;
case 6:
deletion_specified();
break;
case 7:
search();
break;
case 8:
 140
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
display();
break;
case 9:
exit(0);
break;
default:
printf("Please enter valid choice..");
}
}
}
void insertion_beginning()
{
struct node *ptr;
int item;
ptr = (struct node *)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter Item value");
scanf("%d",&item);

if(head==NULL)
{
ptr->next = NULL;
ptr->prev=NULL;
ptr->data=item;
head=ptr;
}
else
{
ptr->data=item;
ptr->prev=NULL;
ptr->next = head;
head->prev=ptr;
head=ptr;
}
printf("\nNode inserted\n");
 141
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
}

}
void insertion_last()
{
struct node *ptr,*temp;
int item;
ptr = (struct node *) malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter value");
scanf("%d",&item);
ptr->data=item;
if(head == NULL)
{
ptr->next = NULL;
ptr->prev = NULL;
head = ptr;
}
else
{
temp = head;
while(temp->next!=NULL)
{
temp = temp->next;
}
temp->next = ptr;
ptr ->prev=temp;
ptr->next = NULL;
}

}
printf("\nnode inserted\n");
}
void insertion_specified()
{
 142
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
struct node *ptr,*temp;
int item,loc,i;
ptr = (struct node *)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\n OVERFLOW");
}
else
{
temp=head;
printf("Enter the location");
scanf("%d",&loc);
for(i=0;i<loc;i++)
{
temp = temp->next;
if(temp == NULL)
{
printf("\n There are less than %d elements", loc);
return;
}
}
printf("Enter value");
scanf("%d",&item);
ptr->data = item;
ptr->next = temp->next;
ptr -> prev = temp;
temp->next = ptr;
temp->next->prev=ptr;
printf("\nnode inserted\n");
}
}
void deletion_beginning()
{
struct node *ptr;
if(head == NULL)
{
printf("\n UNDERFLOW");
}
else if(head->next == NULL)
{
 143
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
head = NULL;
free(head);
printf("\nnode deleted\n");
}
else
{
ptr = head;
head = head -> next;
head -> prev = NULL;
free(ptr);
printf("\nnode deleted\n");
}

}
void deletion_last()
{
struct node *ptr;
if(head == NULL)
{
printf("\n UNDERFLOW");
}
else if(head->next == NULL)
{
head = NULL;
free(head);
printf("\nnode deleted\n");
}
else
{
ptr = head;
if(ptr->next != NULL)
{
ptr = ptr -> next;
}
ptr -> prev -> next = NULL;
free(ptr);
printf("\nnode deleted\n");
}
}
void deletion_specified()
 144
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
{
struct node *ptr, *temp;
int val;
printf("\n Enter the data after which the node is to be deleted : ");
scanf("%d", &val);
ptr = head;
while(ptr -> data != val)
ptr = ptr -> next;
if(ptr -> next == NULL)
{
printf("\nCan't delete\n");
}
else if(ptr -> next -> next == NULL)
{
ptr ->next = NULL;
}
else
{
temp = ptr -> next;
ptr -> next = temp -> next;
temp -> next -> prev = ptr;
free(temp);
printf("\nnode deleted\n");
}
}
void display()
{
struct node *ptr;
printf("\n printing values...\n");
ptr = head;
while(ptr != NULL)
{
printf("%d\n",ptr->data);
ptr=ptr->next;
}
}
void search()
{
struct node *ptr;
int item,i=0,flag;
 145
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
ptr = head;
if(ptr == NULL)
{
printf("\nEmpty List\n");
}
else
{
printf("\nEnter item which you want to search?\n");
scanf("%d",&item);
while (ptr!=NULL)
{
if(ptr->data == item)
{
printf("\nitem found at location %d ",i+1);
flag=0;
break;
}
else
{
flag=1;
}
i++;
ptr = ptr -> next;
}
if(flag==1)
{
printf("\nItem not found\n");
}
}

}
 146
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

Write a c program for binary search tree and travels orders?

#include<stdio.h>
#include<stdlib.h>
struct node
{
struct node *prev;
struct node *next;
int data;
};
struct node *head;
void insertion_beginning();
void insertion_last();
void insertion_specified();
void deletion_beginning();
void deletion_last();
void deletion_specified();
void display();
void search();
 147
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
void main ()
{
int choice =0;
while(choice != 9)
{
printf("\n*********Main Menu*********\n");
printf("\nChoose one option from the following list ...\n");
printf("\n===============================================\n");
printf("\n1.Insert in begining\n2.Insert at last\n3.Insert at any
random location\n4.Delete from Beginning\n
5.Delete from last\n6.Delete the node after the given
data\n7.Search\n8.Show\n9.Exit\n");
printf("\nEnter your choice?\n");
scanf("\n%d",&choice);
switch(choice)
{
case 1:
insertion_beginning();
break;
case 2:
insertion_last();
break;
case 3:
insertion_specified();
break;
case 4:
deletion_beginning();
break;
case 5:
deletion_last();
break;
case 6:
deletion_specified();
break;
case 7:
search();
break;
case 8:
display();
break;
 148
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
case 9:
exit(0);
break;
default:
printf("Please enter valid choice..");
}
}
}
void insertion_beginning()
{
struct node *ptr;
int item;
ptr = (struct node *)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter Item value");
scanf("%d",&item);

if(head==NULL)
{
ptr->next = NULL;
ptr->prev=NULL;
ptr->data=item;
head=ptr;
}
else
{
ptr->data=item;
ptr->prev=NULL;
ptr->next = head;
head->prev=ptr;
head=ptr;
}
printf("\nNode inserted\n");
}
 149
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
}
void insertion_last()
{
struct node *ptr,*temp;
int item;
ptr = (struct node *) malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter value");
scanf("%d",&item);
ptr->data=item;
if(head == NULL)
{
ptr->next = NULL;
ptr->prev = NULL;
head = ptr;
}
else
{
temp = head;
while(temp->next!=NULL)
{
temp = temp->next;
}
temp->next = ptr;
ptr ->prev=temp;
ptr->next = NULL;
}

}
printf("\nnode inserted\n");
}
void insertion_specified()
{
struct node *ptr,*temp;
int item,loc,i;
 150
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
ptr = (struct node *)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\n OVERFLOW");
}
else
{
temp=head;
printf("Enter the location");
scanf("%d",&loc);
for(i=0;i<loc;i++)
{
temp = temp->next;
if(temp == NULL)
{
printf("\n There are less than %d elements", loc);
return;
}
}
printf("Enter value");
scanf("%d",&item);
ptr->data = item;
ptr->next = temp->next;
ptr -> prev = temp;
temp->next = ptr;
temp->next->prev=ptr;
printf("\nnode inserted\n");
}
}
void deletion_beginning()
{
struct node *ptr;
if(head == NULL)
{
printf("\n UNDERFLOW");
}
else if(head->next == NULL)
{
head = NULL;
free(head);
 151
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
printf("\nnode deleted\n");
}
else
{
ptr = head;
head = head -> next;
head -> prev = NULL;
free(ptr);
printf("\nnode deleted\n");
}

}
void deletion_last()
{
struct node *ptr;
if(head == NULL)
{
printf("\n UNDERFLOW");
}
else if(head->next == NULL)
{
head = NULL;
free(head);
printf("\nnode deleted\n");
}
else
{
ptr = head;
if(ptr->next != NULL)
{
ptr = ptr -> next;
}
ptr -> prev -> next = NULL;
free(ptr);
printf("\nnode deleted\n");
}
}
void deletion_specified()
{
struct node *ptr, *temp;
 152
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
int val;
printf("\n Enter the data after which the node is to be deleted : ");
scanf("%d", &val);
ptr = head;
while(ptr -> data != val)
ptr = ptr -> next;
if(ptr -> next == NULL)
{
printf("\nCan't delete\n");
}
else if(ptr -> next -> next == NULL)
{
ptr ->next = NULL;
}
else
{
temp = ptr -> next;
ptr -> next = temp -> next;
temp -> next -> prev = ptr;
free(temp);
printf("\nnode deleted\n");
}
}
void display()
{
struct node *ptr;
printf("\n printing values...\n");
ptr = head;
while(ptr != NULL)
{
printf("%d\n",ptr->data);
ptr=ptr->next;
}
}
void search()
{
struct node *ptr;
int item,i=0,flag;
ptr = head;
if(ptr == NULL)
 153
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
{
printf("\nEmpty List\n");
}
else
{
printf("\nEnter item which you want to search?\n");
scanf("%d",&item);
while (ptr!=NULL)
{
if(ptr->data == item)
{
printf("\nitem found at location %d ",i+1);
flag=0;
break;
}
else
{
flag=1;
}
i++;
ptr = ptr -> next;
}
if(flag==1)
{
printf("\nItem not found\n");
}
}

}
 154
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

/* LINEAR SEARCH */
#include<stdio.h>
#include<conio.h>
void main()
{
int a[100],i,n,e,f=0;
clrscr();
printf("enter n value\n");
scanf("%d",&n);
printf("enter in array\n");
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
printf("enter element\n");
scanf("%d",&e);
i=1;
 155
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
while((i<=n)&&(f==0))
{
if(a[i]==e)
{
f=1;
break;
}
i++;
}
if(f)
printf("FOUND");
else
printf("NOT FOUND");
getch();
}
/* input
enter n value
5
enter in array
9 6 7 2 10
enter element
10

FOUND */

/* BINARY SEARCH METHOD */

#include<stdio.h>
#include<conio.h>
void main()
{
int i,h,low=1,n,a[100],mid,e;
clrscr();
printf("enter n \n");
scanf("%d",&n);
printf("enter into array in ascending\n");
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
printf("enter element\n");
scanf("%d",&e);
h=n;
mid=(low+h)/2;
while((low<h)&&(a[mid]!=e))
{
 156
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
if(a[mid]>e)
h=mid-1;
else
if(a[mid]<e)
low=mid+1;
mid=(low+h)/2;
}
if(a[mid]==e)
printf("FOUND AT %d",mid);
else
printf("NOT FOUND");
getch();
}
/* input
enter n
5
enter in array in ascending
11 12 13 14 15
enter element
13
FOUND AT 3 */

/*BUBBLE SORTING */

#include<stdio.h>
#include<conio.h>
void main()
{
int a[100],i,j,t,n;
clrscr();
printf("enter n value\n");
scanf("%d",&n);
printf("enter in array\n");
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
for(i=1;i<n;i++)
{
for(j=i+1;j<=n;j++)
if(a[i]>a[j])
{
t=a[i];
a[i]=a[j];
a[j]=t;
 157
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
}
}
printf("after sorting\n");
for(i=1;i<=n;i++)
printf("%4d",a[i]);
getch();
}
/* input
enter n value
6
enter in array
9 45 8 2 5 6
after sorting
2 5 6 8 9 45 */

/* SELECTION SORT */
#include<stdio.h>
#include<conio.h>
void main()
{
int j,n,k,min,i,p,a[100];
clrscr();
printf("enter n value\n");
scanf("%d",&n);
printf("enter in array\n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
p=0;
while(p<n-1)
{
min=p;
for(j=p+1;j<n;j++)
{
if(a[min]>a[j])
min=j;
}
if(min!=p)
{
k=a[p];
a[p]=a[min];
a[min]=k;
}
p++;
}
 158
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
printf(" AFTER SORTING\n");
for(i=0;i<n;i++)
printf("%4d",a[i]);
getch();
}
/* input
enter n value 4
enter in array
6839
AFTER SORTING 3689 */

/*INSERT AN ELEMENT IN ARRAY*/

#include<stdio.h>
#include<conio.h>
void main()
{
int a[100],i,n,e,p;
clrscr();
printf("enter n value\n");
scanf("%d",&n);
printf("enter in array\n");
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
printf("enter e and p\n");
scanf("%d%d",&e,&p);
n++;
for(i=n;i>p;i--)
a[i]=a[i-1];
a[p]=e;
printf("after inserting\n");
for(i=1;i<=n;i++)
printf("%4d",a[i]);
getch();
}

/* input
enter n value
4
enter in array
1345
enter e and p
22
after inserting
1 2 3 4 5 */
 159
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

Insertion sort program

/* INSERTION SORT */

#include<stdio.h>
#include<conio.h>
void main()
{
int i,j,a[100],n,t;
clrscr();
printf("enter n value\n");
scanf("%d",&n);
printf("enter in array\n");
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
for(i=2;i<=n;i++)
{
for(j=i-1;j>=1;j--)
{
if(a[j]>a[j+1])
{
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}
}
printf("AFTER SORTING\n");
for(i=1;i<=n;i++)
printf("%4d",a[i]);
getch();
}
/* input
enter n value
4
enter in array
7 4 2 6
AFTER SORTING
2 4 6 7 */
 160
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

Quick sort
#include <stdio.h>
#include <stdbool.h>
#define MAX 7

int intArray[MAX] = {4,6,3,2,1,9,7};

void printline(int count) {

int i;

for(i = 0;i < count-1;i++) {

printf("=");
}

printf("=\n");
}

void display() {
int i;
printf("[");

// navigate through all items

for(i = 0;i < MAX;i++) {
printf("%d ",intArray[i]);
}

printf("]\n");
}

void swap(int num1, int num2) {

int temp = intArray[num1];
intArray[num1] = intArray[num2];
intArray[num2] = temp;
}

int partition(int left, int right, int pivot) {

int leftPointer = left -1;
int rightPointer = right;

while(true) {
while(intArray[++leftPointer] < pivot) {
//do nothing
 161
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

while(rightPointer > 0 && intArray[--rightPointer] > pivot) {

//do nothing
}

if(leftPointer >= rightPointer) {

break;
} else {
printf(" item swapped :%d,%d\n",
intArray[leftPointer],intArray[rightPointer]);
swap(leftPointer,rightPointer);
}
}

printf(" pivot swapped :%d,%d\n", intArray[leftPointer],intArray[right]);

swap(leftPointer,right);
printf("Updated Array: ");
display();
return leftPointer;
}

void quickSort(int left, int right) {

if(right-left <= 0) {
return;
} else {
int pivot = intArray[right];
int partitionPoint = partition(left, right, pivot);
quickSort(left,partitionPoint-1);
quickSort(partitionPoint+1,right);
}
}

int main()
{
printf("Input Array: ");
display();
printline(50);
quickSort(0,MAX-1);
printf("Output Array: ");
display();
printline(50);
}
 162
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

Output
Input Array: [4 6 3 2 1 9 7 ]
==================================================
pivot swapped :9,7
Updated Array: [4 6 3 2 1 7 9 ]
pivot swapped :4,1
Updated Array: [1 6 3 2 4 7 9 ]
item swapped :6,2
pivot swapped :6,4
Updated Array: [1 2 3 4 6 7 9 ]
pivot swapped :3,3
Updated Array: [1 2 3 4 6 7 9 ]
Output Array: [1 2 3 4 6 7 9 ]
==================================================

polynomial addition in c program

#include<stdio.h>
#include<stdlib.h>

struct Node
{
int coeff;
int pow;
struct Node* next;
};

void readPolynomial(struct Node** poly)

{
int coeff, exp, cont;
struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
*poly = temp;
do{
printf("\n Coeffecient: ");
scanf("%d", &coeff);
printf("\n Exponent: ");
scanf("%d", &exp);
temp->coeff = coeff;
temp->pow = exp;
temp-> next = NULL;
printf("\nHave more terms? 1 for y and 0 for no: ");
scanf("%d", &cont);
if(cont)
{
 163
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
temp->next = (struct Node*)malloc(sizeof(struct
Node));
temp = temp->next;
temp->next = NULL;
}
}while(cont);
}

void displayPolynomial(struct Node* poly)

{
printf("\nPolynomial expression is: ");
while(poly != NULL)
{
printf("%dX^%d", poly->coeff, poly->pow);
poly = poly->next;
if(poly != NULL)
printf("+");
}
}

void addPolynomials(struct Node** result, struct Node* first, struct

Node* second)
{
struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
temp->next = NULL;
*result = temp;
while(first && second)
{
if(first->pow > second->pow)
{
temp->coeff = first->coeff;
temp->pow = first->pow;
first = first->next;
}
else if(first->pow < second->pow)
{
temp->coeff = second->coeff;
temp->pow = second->pow;
second = second->next;
}
else
{
temp->coeff = first->coeff + second->coeff;
temp->pow = first->pow;
first = first->next;
second = second->next;
}

if(first && second)

{
temp->next = (struct Node*)malloc(sizeof(struct
Node));
 164
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
temp = temp->next;
temp->next = NULL;
}
}
while(first || second)
{
temp->next = (struct Node*)malloc(sizeof(struct Node));
temp = temp->next;
temp->next = NULL;

if(first)
{
temp->coeff = first->coeff;
temp->pow = first->pow;
first = first->next;
}

else if(second)
{
temp->coeff = second->coeff;
temp->pow = second->pow;
second = second->next;
}
}
}

int main()
{

struct Node* first = NULL;

struct Node* second = NULL;
struct Node* result = NULL;

printf("\nEnter the corresponding data:-\n");

printf("\nFirst polynomial:\n");
readPolynomial(&first);
displayPolynomial(first);
printf("\nSecond polynomial:\n");
readPolynomial(&second);
displayPolynomial(second);
addPolynomials(&result, first, second);
displayPolynomial(result);
return 0;
}
 165
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

DFS AND BFS PROGRAM USING ADJECENT MATRIX IN C PROGRAM

#include<stdio.h>

#include<stdlib.h>

int a[50][50], n, visited[50];

int q[20], front = -1,rear = -1;

int s[20], top = -1, count=0;

void bfs(int v)

int i, cur;

visited[v] = 1;

q[++rear] = v;

while(front!=rear)

{
 166
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
cur = q[++front];

for(i=1;i<=n;i++)

if((a[cur][i]==1)&&(visited[i]==0))

{ q[++rear] = i;

visited[i] = 1;

printf("%d ", i);

void dfs(int v)

int i;

visited[v]=1;

s[++top] = v;

for(i=1;i<=n;i++)

if(a[v][i] == 1&& visited[i] == 0 )

printf("%d ", i);

dfs(i);

}
 167
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
int main()

int ch, start, i,j;

printf("\nEnter the number of vertices in graph: ");

scanf("%d",&n);

printf("\nEnter the adjacency matrix:\n");

for(i=1; i<=n; i++)

for(j=1;j<=n;j++)

scanf("%d",&a[i][j]);

for(i=1;i<=n;i++)

visited[i]=0;

printf("\nEnter the starting vertex: ");

scanf("%d",&start);

printf("\n==>1. BFS: Print all nodes reachable from a given starting

node");

printf("\n==>2. DFS: Print all nodes reachable from a given starting

node");

printf("\n==>3:Exit");

printf("\nEnter your choice: ");

scanf("%d", &ch);

switch(ch)

case 1: printf("\nNodes reachable from starting vertex %d are: ",

start);
 168
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,
bfs(start);

for(i=1;i<=n;i++)

if(visited[i]==0)

printf("\nThe vertex that is not reachable is %d" ,i);

break;

case 2: printf("\nNodes reachable from starting vertex %d

are:\n",start);

dfs(start);

break;

case 3: exit(0);

default: printf("\nPlease enter valid choice:");

}}

To convert infix to postfix expression

#include<stdio.h>
 169
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

#include<conio.h>
#include<ctype.h>
#define MAX 50
typedef struct stack
{
int data[MAX];
int top;
}stack;
int precedence(char);
void init(stack *);
int empty(stack *);
int full(stack *);
int pop(stack *);
void push(stack *,int);
int top(stack *); //value of the top element
void infix_to_postfix(char infix[],char postfix[]);
void main()
{
char infix[30],postfix[30];
printf("Enter an infix expression(eg: 5+2*4): ");
gets(infix);
infix_to_postfix(infix,postfix);
 170
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

printf("\nPostfix expression: %s",postfix);

}
void infix_to_postfix(char infix[],char postfix[])
{
stack s;
char x,token;
int i,j; //i-index of infix,j-index of postfix
init(&s);
j=0;
for(i=0;infix[i]!='\0';i++)
{
token=infix[i];
if(isalnum(token))
postfix[j++]=token;
else
if(token=='(')
push(&s,'(');
else
if(token==')')
while((x=pop(&s))!='(')
postfix[j++]=x;
else
 171
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

while(precedence(token)<=precedence(top(&s))&&!empt
y(&s))
{
x=pop(&s);
postfix[j++]=x;
}
push(&s,token);
}
}
while(!empty(&s))
{
x=pop(&s);
postfix[j++]=x;
}
postfix[j]='\0';
}
int precedence(char x)
{
if(x=='(')
return(0);
if(x=='+'||x=='-')
 172
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

return(1);
if(x=='*'||x=='/'||x=='%')
return(2);
return(3);
}
void init(stack *s)
{
s->top=-1;
}
int empty(stack *s)
{
if(s->top==-1)
return(1);
return(0);
}
int full(stack *s)
{
if(s->top==MAX-1)
return(1);
return(0);
}
 173
P.Y.KUMAR. M.C.A,M.Tech,M.Phil..,

void push(stack *s,int x)

{
s->top=s->top+1;
s->data[s->top]=x;
}
int pop(stack *s)
{
int x;
x=s->data[s->top];
s->top=s->top-1;
return(x);
}
int top(stack *p)
{
return (p->data[p->top]);
}
Output:
Enter an infix expression(eg: 5+2*4): a+b*c
Postfix expression:abc+*