II Semester BSC ( MPCS / MSCS / BZCS)

Data Structures Using C

UNIT – I:
Introduction to Data Structures: Introduction to the Theory of Data Structures, Data Representation,
Abstract Data Types, Data Types, Primitive Data Types, Data Structure and Structured Type, Atomic Type,
Difference between Abstract Data Types, Data Types, and Data Structures.
Principles of Programming and Analysis of Algorithms: Algorithms, Complexity, Big ‘O’ Notation,
Algorithm Analysis, Structured Approach to Programming, Recursion.

UNIT – II:
Arrays: Introduction to Linear and Non- Linear Data Structures, One- Dimensional Arrays, Array
Operations, Two- Dimensional arrays, Multidimensional Arrays, Pointers and Arrays, an Overview of
Pointers.

Linked Lists: Introduction to Lists and Linked Lists, Dynamic Memory Allocation, Basic Linked List
Operations, Doubly Linked List, Circular Linked List, Atomic Linked List, Linked List in Arrays, Linked List
versus Arrays
UNIT – III:
Stacks: Introduction to Stacks, Stack as an Abstract Data Type, Representation of Stacks through Arrays,
Representation of Stacks through Linked Lists, Applications of Stacks, Stacks and Recursion .

Queues: Introduction, Queue as an Abstract data Type, Representation of Queues through Arrays,
Representation of Queues through Linked Lists, Circular Queues, Double Ended Queues- Dequeues,
Priority Queues, Application of Queues
UNIT – IV:
Binary Trees: Introduction to Non- Linear Data Structures, Introduction Binary Trees, Types of Trees, Basic
Definition of Binary Trees, Properties of Binary Trees, Representation of Binary Trees, Operations on a
Binary Search Tree, Binary Tree Traversal, Counting Number of Binary Trees, Applications of Binary Tree.
UNIT – V:
Searching and sorting: Sorting – An Introduction, Bubble Sort, Selection Sort, Insertion Sort, Merge Sort,
Quick Sort. Searching – An Introduction, Linear or Sequential Search, Binary Search.
Graphs: Introduction to Graphs, Terms Associated with Graphs, Sequential Representation of Graphs,
Linked Representation of Graphs, Traversal of Graphs, Spanning Trees, Shortest Path, Application of
Graphs.
BOOKS:
1. “Data Structures using C”, ISRD group Second Edition, TMH
2. “Data Structures through C”, Yashavant Kanetkar, BPB Publications
3. “Data Structures Using C” Balagurusamy E. TMH

Page 1
 UNIT – I
Introduction to Data Structures : Data Structure is a way of organizing the data, not only stored items and
also stores its relationship. (or) A data may be organized in many ways such as the Logical (or)
mathematical representation of given data is called as "data structure". (or) The method to store the
information and computes the memory is collectively known as Data structure. Data Structure can be
defined as the group of data elements which provides an efficient way of storing and organising data in the
computer, so that it can be used efficiently. Some examples of Data Structures are arrays, Linked List,
Stack, Queue, etc. Data Structure plays a very important role in various algorithms, it allows the
programmer to handle the data efficiently.
NEED OF THE DATA STRUCTURE :
1. A data structure helps us to understand the relationship of one data element With other.
2. Data structure helps us to analyze the data in a logical or mathematical manner.
3. Data structure helps us to store the data and organize in logical or mathematical manner
4. Modern day computing problems are complex and large. So, there is a need to handle large amount of
data which is overcome using data structure.
5. The collecting of data and link dynamically over time is organized by using various efficient algorithms in
data structure.
OPERATIONS ON DATA STRUCTURES

The operations involve in data structure are as follows.

Traversing: It means to access each data item exactly once so that it can be processed. For example, to
print the names of all the students in a class.

Searching : It is used to find the location of one or more data items that satisfy the given constraint. Such a
data item may or may not be present in the given collection of data items. For example, to find the names
of all the students who secured 100 marks in Computers.

Inserting: It is used to add new data items to the given list of data items. For example, to add the details of
a new student who has recently joined the course.

Deleting:It means to remove (delete) a particular data item from the given collection of data items. For
example, to delete the name of a student who has left the course.

Sorting:Data items can be arranged in some order like ascending order or descending order depending on
the type of application. For example, arranging the names of students in a class in an alphabetical order.

Merging: Lists of two sorted data items can be combined to form a single list of sorted data items.

Page 2
ADVANTAGES OF DATA STRUCTURES: We need data structures because there are several advantages of
using them, few of them are as follows:
1. Data Organization: We need a proper way of organizing the data so that it can accessed efficiently when
we need that particular data. DS provides different ways of data organization so we have options to store
the data in different data structures based on the requirement.
2. Efficiency The main reason we organize the data is to improve the efficiency. We can store the data in
arrays then why do we need linked lists and other data structures? because when we need to perform
several operation such as add, delete update and search on arrays , it takes more time in arrays than some
of the other data structures. So the fact that we are interested in other data structures is because of the
efficiency.
3. Reusability Data structure can be reused. Once we have implemented a data structure, the same data
structure can be used later.
4. Abstraction Data structure hides (abstracts) the implementation details from the user. The user access
the data through an interface and enjoys the benefits of data structures, the important complex
implementation details are hidden from the user.

Data Representation:
Data Representation refers to the form in which data is stored, processed, and transmitted. Devices such
as smart phones, iPods, and computers store data in digital formats. Digitization is the process of
converting information, such as text, numbers, photo, or music, into digital data that can be manipulated
by electronic devices. The 0s and 1s used to represent digital data are referred to as binary digits — from
this term we get the word bit that stands for binary digit. A bit is a 0 or 1 used in the digital representation
of data.
Representing Numbers Numeric data consists of numbers that can be used in arithmetic operations.
Digital devices represent numeric data using the binary number system, also called base 2. The binary
number system only has two digits: 0 and 1. No numeral like 2 exists in the system, so the number “two” is
represented in binary as 10 (pronounced “one zero”).

Page 3
Representing Text Character data is composed of letters, symbols, and numerals that are not used in
calculations. Examples of character data include your name, address, and hair colour. Character data is
commonly referred to as “text.”Digital devices employ several types of codes to represent character data,
including ASCII, Unicode, and their variants. ASCII (American Standard Code for Information Interchange,
pronounced “ASK ee”) requires seven bits for each character. The ASCII code for an uppercase A is
1000001.

: Abstract Datatypes:
The abstract datatype is special kind of datatype, whose behaviour is defined by a set of values and
set of operations. The word ‘abstract’ in the context of data structures means considered apart from the
detailed specifications or implementation. The keyword “Abstract” is used as we can use these datatypes,
we can perform different operations. But how those operations are working that is totally hidden from the
user. The ADT is made of with primitive datatypes, but operation logics are hidden. It does not specify how
data will be organized in memory and what algorithms will be used for implementing the operations.

In C, an abstract data type can be a structure considered without regard to its implementation. The
end-user is not concerned about the details of how the methods carry out their tasks. They are only aware
of the methods that are available to them and are only concerned about calling those methods and getting
the results. They are not concerned about how they work.

For example, when we use a stack or a queue, the user is concerned only with the type of data and
the operations that can be performed on it. Therefore, the fundamentals of how the data is stored should
be invisible to the user.

Advantages of using ADTs

In the real world, programs evolve as a result of new requirements or constraints, so a modification
to a program commonly requires a change in one or more of its data structures.

For example, if you want to add a new field to a student’s record to keep track of more information about
each student, then it will be better to replace an array with a linked structure to improve the program’s
efficiency. In such a scenario, rewriting every procedure that uses the changed structure is not desirable.
Therefore, a better alternative is to separate the use of a data structure from the details of its
implementation. This is the principle underlying the use of abstract data types.

DATA TYPE
A data type is a set of data values having predefined characteristics. You will have encountered data types
during computer programming. In sense, it describes which type of data is stored in the variable. Ex:
integer, float, character and Boolean. Generally in all programming languages we have a limited number of
such data types. The range of values that can be stored in each of these data types is defined by the
languages and the computer hardware that the high level language is used.

Page 4
Data types can be broken up to two types
I. Scalar or primitive data types
II. Structured or non- primitive data types.
I. Scalar or primitive data type A simple (scalar) data type consists of a collection of or ordered values and
set of operations that can be performed on those values. The C,C++, and Java programming languages
refers to scalar types primitive data types. A scalar variable can hold only one piece of data at a time. So in
C, C++ , and java scalar data type include int , char , float, and double , along with others. Scalar variable
of the same type can be arranged into ascending or descending order based on the value.
A. Integer Types Integer types can hold whole numbers as 286,-32…. The size of the values that can be
stored depends on the integer data type. Java supports four types of integer as shown below. These can
be positive or negative.
Integer

Type Size (in bytes) Min. value Max. value

Byte 1 -128 127
Short 2 -32,768 32,767
Int 4 -2,147,483,648 2,147,483,647

-
Long 8 9,223,372,036,854,775,8 9,223,372,036,854,775,80
08 8

B. Floating point types

Floating point types can hold numbers containing fractional parts such as 7.5, 9.04, etc..

Floating point

Type Size (in bytes) Min. value Max. value

Float 4 3.4 e-038 3.4 e+038
long 8 1.7 e -308 1.7 e +308

C. Character type Java provide a character data type called char to store character constants .The char
type assumes a size of 2 bytes but it can hold only a single characters.

Page 5
D. Boolean type Boolean type is used when we want to test a particular condition during the execution of
the program. There are only 2 values that Boolean type can take: true or false. Only one bit is required to
store Boolean values.
II. Structured or non- primitive data types :Non - primitive data types hold a collection of data values. This
collection will generally consists of the primitive data types. Example of this would include ARRAYS,
RECORDS (STRUCTURES), CLASSES AND FILES. These data types, which are created by programmers, are
extremely important and are the building block of data structures. Non-primitive data types in java
languages are arrays, classes, interface etc. These are also examples of reference data types.

Data Structure Classification:

Primitive Data Structures are the basic data structures that directly operate upon the machine
instructions.

Ex: Integer,float,character,double etc.

Non-primitive data structures are more complicated data structures and are derived from primitive data
structures.

Linear Data Structures: A data structure is called linear if all of its elements are arranged in the linear
order. In linear data structures, the elements are stored in non-hierarchical way.

Arrays: An array is a collection of similar type of data items and each data item is called an element of the
array. The data type of the element may be any valid data type like char, int, float or double.

Linked List: Linked list is a linear data structure which is used to maintain a list in the memory.

Page 6
Stack: Stack is a linear list in which insertion and deletions are allowed only at one end, called top.

Queue: Queue is a linear list in which elements can be inserted only at one end called rear and deleted
only at the other end called front.

Non Linear Data Structures: This data structure does not form a sequence i.e. each item or element is
connected with two or more other items in a non-linear arrangement. The data elements are not arranged
in sequential structure.

Trees: Trees are multilevel data structures with a hierarchical relationship among its elements known as
nodes.

Graphs: Graphs can be defined as the pictorial representation of the set of elements (represented by
vertices) connected by the links known as edges.

Atomic Type

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

1.Data storage

2.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 corresponding 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.

Difference between Abstract Data types, 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.

Page 7
  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.

 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, i.e., a data type has its root in the
abstract data type and a data structure comprises a set of computer variables of some 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.

The applications 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 level

 Programming or implementation level

 Application level

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.

Algorithmic or Data Structure Level

At data structure level we decide about the operations on the data as needed by our problem.

Programming or implementation Level

At implementation level, we decide the details of how the data structures will be represented in the
computer memory.

Page 8
Application Level

This level determines all details required for particular application such as names for variables or special
requirements for the operations imposed by applications.

Principles of Programming and Analysis of Algorithms

Software Engineering:

Software Engineering is the theory and practice of methods helpful for the construction and maintenance
of large software systems. Development of a good software is a complicated process which continues for
long time before the software or program takes the final shape and is put into use. There are many stages
in software development cycle. The process is often referred to as Software Development Life Cycle
(SDLC). In SDLC, the output from one stage becomes the input to the next stage.

In the simplified version, the software development life cycle may contain requirement analysis, design,
implementation and maintenance phases which are implemented in sequence over a period of time.

The different steps insoftware development life cycle are as follows:

1. Analyse the problem precisely and completely.

2. Build a prototype and experiment with it until all specifications are finalized.

3. Design the algorithm using the tools of data structures.

4. Verify the algorithm, such that its correctness is self-evident.

5. Analyse the algorithm to determine its requirements.

6. Code the algorithm into an appropriate programming language.

7. Test and evaluate the program with carefully chosen data.

8. Refine and repeat the foregoing steps until the software is complete.

Page 9
 9. Optimize the code to improve performance.

10. Maintain the program so that it meets the changing needs of its users.

Program Design

Program design can be considered as an important phase of the software development life cycle. In this
phase that the algorithms and data structures to solve a problem are proposed. Some of the various points
that can help us to evaluate the proposed program designs are as follows:

 As the design stage involves taking the specification and designing solutions to the problems, the
designer needs to adopt a design strategy. The strategy adopted while designing should be
according to the given specifications.

 Another important point which should be kept in mind while developing a solution strategy is that
it should work correctly in all conditions.

 Generally, the people who use the system are not aware of program design you have adopted.
thus, there is a system manual which is a detailed guide to how the design was achieved. In
addition a user manual serves as a reference for the users who are not familiar with the system or
machines.

 A large program should be divided into small modules and submodules by following one of the two
decomposition approaches-top down approach or bottom-up approach.

 Othe important criteria by which a program can be judged are execution time and storage
requirement.

Algorithms
The term ‘algorithm’ refers to the sequence of instructions that must be followed to solve a problem. In
other words, an algorithm is a logical representation of the instructions which should be executed to
perform a meaningful task.

An algorithm has certain characteristics. They are as follows:

 Each instruction should be unique and concise.

 Each instruction should be relative in nature and should not be repeated infinitely.

 Repetition of same task should be avoided.

 The result should be available to the user after the algorithm terminates.

Thus, an algorithm is any well defined computational procedure, along with a specified set of allowable
inputs, that produce some value or set of values as output.

After an algorithm has been designed, its efficiency must be analyzed. This involves determining whether
the algorithm is economical in the use of computer resources i.e., CPU time and memory.

Page 10
The importance of efficiency of an algorithm is in the correctness- i.e., does it always produce the correct
result.

Different Approaches to Designing an Algorithm

A complex system may be divided into smaller units called modules. Modularity enhances design clarity,
which in turn eases implementation, debugging, testing, documenting, and maintenance of the product. A
system consists of components. Indeed a system is a hierarchy of components. The highest level
component corresponds to the total system. To design such a hierarchy there are two possible
approaches:

1. Top-down approach

2. Bottom-up approach

Top-down Approach

A top-down approach starts by identifying the major components of the system or program, decomposing
them into their lower-level components and iterating until the desired level of module complexity is
achieved.

Top-down design method takes the form of stepwise refinement. Thus, in top-down approach we
start from an abstract design. In each step, design is refined into most concrete level until we reach the
level where no more refinement is needed and the design can be implemented directly. Stepwise
refinement is “top-down” method for decomposing a system from high level specifications into more
elementary levels. The top-down approach, however is often useful way to better document a design.

Bottom-Up Approach

A bottom-up design approach starts with designing the most basic or primitive components and proceeds
to higher-level components. Bottom-up method works with layers of abstraction. Starting from the very
bottom, the operations that provide a layer of abstraction are implemented. Bottom-up approach follows
information hiding.

The design activity should not be constrained to proceed according to a fixed pattern but should be
a blend of top-down and bottom-up approaches.

Complexity
When we talk of complexity in context of computers, we call it as computational complexity.
Computational complexity is a characterization of the time or space requirements for solving a problem by
a particular algorithm. These requirements are expressed in terms of a single parameter that represents
the size of the problem.

The analysis of the program requires two main considerations:

1. Time complexity

Page 11
 2. Space complexity

1. Time Complexity: The time complexity of a program / algorithm is the amount of computer time that it
needs to run to completion. While measuring the time complexity of an algorithm, we concentrate on
developing only the frequency count for all key statements. This is because, it is often difficult to get
reliable timing figure because of clock limitations and the multiprogramming or the sharing environment.

Ex: Consider the algorithm given below:

1. Algorithm A a=a+1
2. Algorithm B for x=1 to n step 1
a=a+1
loop
In the algorithm A we may find that the statement a=a+1 is independent and is not contained within any
loop. Therefore, the number of times this shall be executed is 1. We can say that the frequency count of
algorithm A is 1.

In the second algorithm, i.e., B, the key statement out of three statements is the assignment operation
a=a+1. Because this statement is contained within a loop, the number of times it is executed is n, as the
loop runs for n times. The frequency count for this algorithm is n.

2.Space Complexity: The space complexity of a program / algorithm is the amount of memory that it needs
to run to completion. The space needed by the program is the sum of the following components:

Fixed space requirements: This includes the instructions space, for simple variables, fixed size structured
variables, and constants.

Variable space requirements: This consists of space needed by structured variables whose size depends
on particular instance of variables. It also includes the additional space required when the function uses
recursion.

BIG ‘O’ Notation:

If f(n) represents the computing time of some algorithm and g(n) represents a known standard function
like n,n2, n log n etc. then to write:
f(n) is O g(n).
means that f of n is equal to biggest order of function g(n). From the above statements, we can say that
the computing time of an algorithm is O(g(n)), we mean that its execution takes no more than a constant
time g(n). n is the parameter which characterizes the inputs and/ or outputs. For ex: n might be the
number of inputs or the number of outputs or their sum or the magnitude of one of them.

Need of Big ‘O’ Notation:

 Big O notation helps to determine the time as well as space complexity of the algorithms. Using the
Big O notation, the time taken by the algorithm and the space required to run the algorithm can be
discovered.

 This information is useful to set the prerequisites of algorithms and to develop and design efficient
algorithms in terms of time and space complexity.

Page 12
  The Big ‘O’ Notation has been extremely useful to classify algorithms by their performances.

 Developers use this notation to reach to the best solution for the given problem.
Most Common Computing times of Algorithm:
If the complexity of any algorithm is O(1), it means that the computing time of the algorithm is constant
O(n) and it is called linear time which implies that it is directly proportional to n. O(n 2) is called the
quadratic time, O(n3) is the cubic time, O(2n) is exponential time, O(log n) and O(n log n) are the
logarithmic times.
The common computing times of algorithms in the order of performance are as follows:
 O(1)
 O(log n)
 O(n)
 O(nlog n)
 O(n2)
 O(n3)
 O(2n)

Structured Approach to Programming:

Structured programming is a subset of software engineering. It is a method for designing and coding
programs in a systematic, organized manner. The emphasis of structured programming is mainly on the
technical aspects of programming, whereas software engineering puts equal emphasis on technical,
managerial, psychological and financial aspects of software development.
The term ‘Structured programming’ was coined by “Dijkstra” in the article ‘Structured
Programming’. Wirth has defined program as follows:
Program= algorithm + data structures.

Some of the control structures which can be used for structured programming are as follows:

Page 13
Structured Programming emphasises functional specialization and tries to ensure that only one primary
function is allocated to any module.

Recursion:
A recursive routine is one whose design includes a call to itself. In design phase of software development
we use various problem solving methods in which recursion can be one of the powerful tools.

A common example which can explain the concept of recursion is to find out the factorial of any number.
A ‘C’ function declaration for factorial is:
Factorial(a)
Int a:
{
Int fact=1
If(a>1)
Fact=a*Factorial(a-1); /* recursive function call*/
Return(fact);
}

Tips and Techniques for writing Programs in ‘C’

Page 14
A program in any language is a collection of one or more functions. Every function is a collection of
statements which performs a specific task. For example, a program written in ‘C’ can have the following
format:
Comments
Preprocessor directives
Global_variables
Main()
{
Local variables
Statements
--------------
--------------
Func1()
{
Local variables
Statements
-----------
-----------
}
Func2()
{
Local variables
Statements
-------------
-------------
}
A program starts with comments enclosed between /* and */. Comments can be given anywhere in the
program.
The pre-processor directives are executed before C program code passes through the compiler. These pre-
processor directives make programs more efficient. Most commonly used directives are #include which
includes files, # define which defines the macro name and macro expansion.
Then there are declarations for global variables, which have same data type and same name throughput
the function and are defined outside the main() function. But the declaration of too many global variables
is not advisable. To make the program more efficient constants are used.
‘C’ program contains the main() function but a program should be divided into functions. A function is a
self-contained subprogram which performs some specific, well defined task.

Unit – II
Write about Linear And Non-Linear Data Structures?( Or) Q.What is Data Structure and
Types data Structure?

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:
1. Linear Data Structure
2. Non Linear Data Structure

Page 15
Linear Data Structure:

Data structure where data elements are arranged sequentially or linearly where the elements are
attached to its previous and next adjacent in what is called a linear data structure. In linear data
structure, single level is involved. Therefore, we can traverse all the elements in single run only. Linear
data structures are easy to implement because computer memory is arranged in a linear way. Its
examples are array, stack, queue, linked list.

1. Array
The array is a type of data structure that stores elements of the same type. These are the most basic and
fundamental data structures. Data stored in each position of an array is given a positive value called the
index of the element. The index helps in identifying the location of the elements in an array.
2. Stack
The data structure follows the rule of LIFO (Last In-First Out) where the data last added element is
removed first. Push operation is used for adding an element of data on a stack and the pop operation is
used for deleting the data from the stack. This can be explained by the example of books stacked
together. In order to access the last book, all the books placed on top of the last book have to be safely
removed.
3. Queue
This structure is almost similar to the stack as the data is stored sequentially. The difference is that the
queue data structure follows FIFO which is the rule of First In-First Out where the first added element is
to exit the queue first. Front and rear are the two terms to be used in a queue.

4. Linked List
Linked lists are the types where the data is stored in the form of nodes which consist of an element of
data and a pointer. The use of the pointer is that it points or directs to the node which is next to the
element in the sequence. The data stored in a linked list might be of any form, strings, numbers, or
characters. Both sorted and unsorted data can be stored in a linked list along with unique or duplicate
elements.

Non-linear Data Structure :

Page 16
Data structures where data elements are not arranged sequentially or linearly are called non-linear data
structures. In a non-linear data structure, single level is not involved. Therefore, we can’t traverse all the
elements in single run only. Non-linear data structures are not easy to implement in comparison to
linear data structure. It utilizes computer memory efficiently in comparison to a linear data structure. Its
examples are trees and graphs.

1. Trees
A tree data structure consists of various nodes linked together. The structure of a tree is hierarchical
that forms a relationship like that of the parent and a child. The structure of the tree is formed in a way
that there is one connection for every parent-child node relationship. Only one path should exist
between the root to a node in the tree. Various types of trees are present based on their structures like
AVL tree, binary tree, binary search tree, etc.
2. Graph
Graphs are those types of non-linear data structures which consist of a definite quantity of vertices and
edges. The vertices or the nodes are involved in storing data and the edges show the vertices
relationship. The difference between a graph to a tree is that in a graph there are no specific rules for
the connection of nodes. Real-life problems like social networks, telephone networks, etc. can be
represented through the graphs.

Difference between the Linear and Non Linear Data Structure

S.N
O Linear Data Structure Non-linear Data Structure

In a linear data structure, data elements are arranged in In a non-linear data structure, data
a linear order where each and every elements are elements are attached in hierarchically
1. attached to its previous and next adjacent. manner.

Whereas in non-linear data structure,

2. In linear data structure, single level is involved. multiple levels are involved.

Its implementation is easy in comparison to non-linear While its implementation is complex in

3. data structure. comparison to linear data structure.

While in non-linear data structure, data

In linear data structure, data elements can be traversed elements can’t be traversed in a single
4. in a single run only. run only.

While in a non-linear data structure,

In a linear data structure, memory is not utilized in an memory is utilized in an efficient way.
5. efficient way.

While its examples are: trees and

6. Its examples are: array, stack, queue, linked list, etc. graphs.

Page 17
 S.N
O Linear Data Structure Non-linear Data Structure

Applications of non-linear data

Applications of linear data structures are mainly in structures are in Artificial Intelligence
7. application software development. and image processing.

ARRAYS
we have seen different types of variables which holds only one value. There are many applications which
require to process a group of data item that are of same type such as int, float, char,double.

“An array is a collection of variables of the same type , referred to by a common name ,items stored at
contiguous memory locations .

We can define an array to represent set of 5 elements . A particular value is indicated by writing a number
called index number or subscript in square brockets after an array name. The individual values of an array
referred as elements of array.
Eg: salary [5] => represents 5 employee salary.

Array Operations :
 Traverse − print all the array elements one by one.
 Insertion − Adds an element at the given index.
 Deletion − Deletes an element at the given index.
 Search − Searches an element using the given index or by the value.
 Update − Updates an element at the given index.
Arrays are generally categorized into following types
1. One-dimensional arrays
2. Two-dimensional arrays
3. Multi dimensional arrays
1. One-dimensional arrays:”A list of items can be given one variable name using only one subscript and
such a variable called single-subscripted variable or a one-dimensional array”. It represents only one row
or column of elements.

Page 18
Declaration of One Dimension array:
Like variable, array must be declared and created in the computer memory before they are used. Array
can be declared in two forms:
Syntax: datatype arrayname[size];

Here datatype may be int, float, or char and size indicates the maximum number of elements that can be
stored inside the array.
Eg: int marks[10]
In above example, declares the marks to be an array containing 10 real elements.
Initialization of values into one dimensional array:-
We can assign the values into one dimensional array at the time of
declaration of an array or after the declaration of array.
Example : int a[5];
a[0]=1, a[1]=2 , a[2]=4, a[3]=8, a[4]=16;
OR
int a[5]={ 1,2,4,8,16};
2. Two Dimensional Array :- A list of items can be given to one variable name using two subscripts and
such a variable is called a two subscripted variable or two dimensional array..

Declaration of Two Dimension Array :-

type variable _name[row_size][column_size];

type – data type, variable_name – name of the array, row_size – no of rows, column_size – no of columns
of an array.
Example:-
Int a[3][3];

Initialization of values into two dimensional array:-

We can assign the values into two dimensional array at the time of declaration of an array or after the
declaration of array.
1) int a[ ][ ] = {{1,2,3}, {4,5,6}, {7,8,9}};
Or
2) int a[3][3];
a[0][0]=1, a[0][1]=2, a[0][2]=3, a[1][0]=4, a[1][1]=5

Two Dimensional array representation:-

Page 19
3. Three Dimensional Array :- A list of items can be given to one variable name using more than two
subscripts and such a variable is called a three dimensional array..
Declaration :-
type variable _name[s1][s2]… [sn];
Example:-
Int a[2][2][2];

Initialization of values Multi dimensional array:-

We can assign the values into three dimensional array at the time of declaration of an array or after the
Declaration of Multi Dimension array .
int a[2][2][2];
a[0][0][0]=1, a[0][0][1]=2, a[0][0][2]=3, a[0][1][0]=4, a[0][1][1]=5

Pointers
Pointer is a variable that can hold the address of another variable. It is a derived data type and the
pointer variables are declared from the built in data type.Therefore a pointer, is a variable that represents
the location of a data item.

Declaring pointer variables:

The declaration of a pointer variable takes the following form:
data_type *pt_name;

This tells to compiler three things about the variable pt_name.

1. The asterisk(*) tells that the variable pt_name is a pointer variable.
2. pt_name points to a variable of type data_type.

E.g: int *p;

declares the variable p as a pointer variable that points to an integer data type.

Accessing the address of a variable:

The actual location of a variable in the memory is system dependent and therefore, the address of a
variable is not known to us immediately. We can access the address of a variable by using address
operator ‘ & ’ . The operator & immediately preceding a variable returns the address of the variable
associated with it.
e.g: x=&p;

Page 20
 The address operator can be used only with a simple variable or array elements.

Initializing of pointer variables:

The process of assigning the address of a variable to a pointer variable is known as initialization of pointer
variable. Once a pointer variable has been declared we can use the assignment operator to initialize the
variable.

int quantity=10;
int *p;
p=&quantity;

Remember that is an initialization of p and not *p.

Accessing a variable through its pointer:

Once a pointer has been assign the address of a variable, then we can access the variable by using asterisk
(*) operator, usually known as the indirection operator. Another name for the indirection operator is the
dereferencing operator. Consider following example
int num,*p,n;
num=179;
p=#
n=*p;
The first line declares num and n as integer variables and p as a pointer variable pointing to an integer. The
second line assigns the values 179 to num and the third line assigns the address of num to the pointer
variable p. The fourth line contains the indirection operator *. When the operator * is placed before a
pointer variable in an expression, the pointer returns the value of the variable of which the pointer value is
the address. In this case, *p returns the value of the variable num, because p is the address of num. the *
can be remembered as ‘value at address’.

Pointer and Arrays

We can access the array elements by using the pointers. This is can be done by assigning the base address
of the array element or directly by storing the entire array into pointer variable.
Ex :- int a[5]={10,20,30,40,50}; int *ptr;

assigning base address to pointer variable:-ptr = &a[0]; or ptr=a;

accessing array elements using pointers :
*(ptr+0) similar to a[0];
-------------
---------------
*(ptr+4) similar to a[4]

Example

#include<stdio.h>

Page 21
void main()
{
int a[3] = {1, 2, 3};
int *p = a;
for (int i = 0; i < 3; i++)
{
printf("%d", *p);
p++;
}
return 0;

LINKED LISTS
LINKED LISTS
A linked list or one way list is a liner collection of data elements, called nodes where the linear order is
given by means of references. That is each node is divided into to parts the first part contains the
information of the element and the second part called the link field or next reference field, contains
the address of the next node in the list.

Node
The reference of the last node contains a special value called “NULL” reference denoted by “
X ” in the diagram signals the end of the list. The linked list also contains a pointer variable called
“START” which refer to the first or head node in the list .
A special case is the list that has no nodes, such list is called the “NULL” list or empty list and is
denoted by null reference in the start variable.

Advantages of linked lists

1) The primary advantage of linked list over arrays is that linked list can increase and decrease in
size. That means their maximum size need not be mentioned inadvance. This is a very good

Page 22
 advantage in practicalapplications.
2) The second advantage of linked list is the flexibility in allowing the items to the rearranged
efficiently. This flexibility is gained at the experience of quick access toany item inthis.
3) The insertion and deletion of an element takes one time. Unlike array implementationin which
they taken-times.

Limitations of linked lists

1) The space needed to store a list usingmore.
2) Another limitation is that it is not possible to travel a list in both directions. This canbe over
come in double linkedlist.

Linked list can be classified as :

1. Singly likedlist
2. Doubly linkedlist
3. Circularly Singly linked list
4. Circularly doubly linkedlist

1.Singly linkedlist
Here in this type of list the node has only one reference variable apart from the information
part which always refers to the next node. In singly linked list we can perform only forward
traversing. This type of lists is also known as one way list.

2. Doubly linkedlist
These types of lists are also known as two way list, which can be traversed in two directions
forward and backward directions. A two list is a collection of data elements called nodes where
each node is divided into three parts
a. An information field INFO which contains thedata
b. A reference field “NEXT” which contains the location of the next node in thelist.
c. A reference field “PREV” which contains the location of the preceding node in the list

3. Circularly Singly linkedList:

In a singly linked list the last node refers to the first node of the same list, then its form a cyclic
or circle, then this type of list called as Circular Single Linked List.

Page 23
 4. Circularly doubly linkedlist:
In a double linked list, the end node refer back to the header node and the header node
refers tothe end node, it forms a circle then it is called as Circular Double linked list.

Linked ListRepresentation:
Linked list can be visualized as a chain of nodes, where every node points to the next node.

As per the above illustration, following are the important points to be considered.
 Linked List contains a link element called first.
 Each link carries a data field(s) and a link field called next.
 Each link is linked with its next link using its next link.
 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 in the list.
 Deletion − Deletes an element in the list.
 Display − Displays the complete list.

Insertion Operation
Adding a new node in linked list is a more than one step activity. We shall learn this with diagrams
here. First, create a node using the same structure and find the location where it has to be inserted.

Imagine that we are inserting a node B (NewNode), between A (LeftNode) and C (RightNode). Then point
B.next to C − NewNode.next −> RightNode; It should look like this −

Page 24
Now, the next node at the left should point to the new node.
LeftNode.next −> NewNode;

This will put the new node in the middle of the two. The new list should look like this −

Similar steps should be taken if the node is being inserted at the beginning of the list. While inserting it at
the end, the second last node of the list should point to the new node and the new node will point to
NULL.

Deletion Operation
Deletion is also a more than one step process. We shall learn with pictorial representation. First, locate the
target node to be removed, by using searching algorithms.

The left (previous) node of the target node now should point to the next node of the target node −
LeftNode.next −> TargetNode.next;

This will remove the link that was pointing to the target node. Now, using the following code, we will
remove what the target node is pointing at.
TargetNode.next −> NULL;

Page 25
We need to use the deleted node. We can keep that in memory otherwise we can simply deallocate
memory and wipe off the target node completely.

Double Linked List

Double 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.
Double 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:
 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.

Insertion Operation
Following code demonstrates the insertion operation at the beginning of a doubly linked list.
Example
//insert link at the first location
void insertFirst(int key,int data){

Page 26
//create a link
struct node *link =(struct node*) malloc(sizeof(struct node));
link->key = key;
link->data = data;

if(isEmpty()){
//make it the last link
last= link;
}else{
//update first prev link
head->prev = link;
}

//point it to old first link

link->next= head;

//point first to new first link

head = link;
}
Deletion Operation
Following code demonstrates the deletion operation at the beginning of a doubly linked list.
Example
//delete first item
struct node* deleteFirst(){

//save reference to first link

struct node *tempLink = head;

//if only one link

if(head->next== NULL){
last= NULL;
}else{
head->next->prev = NULL;
}

head = head->next;

//return the deleted link

return tempLink;
}
Insertion at the End of an Operation
Following code demonstrates the insertion operation at the last position of a doubly linked list.
Example
//insert link at the last location
void insertLast(int key,int data){

//create a link
struct node *link =(struct node*) malloc(sizeof(struct node));

Page 27
 link->key = key;
link->data = data;

if(isEmpty()){
//make it the last link
last= link;
}else{
//make link a new last link
last->next= link;

//mark old last node as prev of new link

link->prev =last;
}

//point last to new last node

last= link;
}
Circular Linked List

Circular Linked List is a variation of Linked list in which the first element points to the last element
and the last element points to the first element. Both Singly Linked List and Doubly Linked List can be
made into a circular linked list.
Singly Linked List as Circular
In singly linked list, the next pointer of the last node points to the first node.

Doubly Linked List as Circular

In doubly linked list, the next pointer of the last node points to the first node and the previous pointer of
the first node points to the last node making the circular in both directions.

As per the above illustration, following are the important points to be considered.
The last link's next points to the first link of the list in both cases of singly as well as doubly linked list.
The first link's previous points to the last of the list in case of doubly linked list.
Basic Operations
Following are the important operations supported by a circular list.
insert − Inserts an element at the start of the list.
delete − Deletes an element from the start of the list.
display − Displays the list.
Insertion Operation
Following code demonstrates the insertion operation in a circular linked list based on single linked list.
Example
//insert link at the first location

Page 28
void insertFirst(int key,int data){
//create a link
struct node *link =(struct node*) malloc(sizeof(struct node));
link->key = key;
link->data= data;

if(isEmpty()){
head = link;
head->next= head;
}else{
//point it to old first node
link->next= head;

//point first to new first node

head = link;
}
}
Deletion Operation
Following code demonstrates the deletion operation in a circular linked list based on single linked list.
//delete first item
struct node * deleteFirst(){
//save reference to first link
struct node *tempLink = head;

if(head->next== head){
head = NULL;
return tempLink;
}

//mark next to first link as first

head = head->next;

//return the deleted link

return tempLink;
}
Display List Operation
Following code demonstrates the display list operation in a circular linked list.
//display the list
void printList(){
struct node *ptr = head;
printf("\n[ ");

//start from the beginning

if(head != NULL){
while(ptr->next!= ptr){
printf("(%d,%d) ",ptr->key,ptr->data);
ptr = ptr->next;
}
}

Page 29
 printf(" ]");
}
Array VS. LinkedList
ARRAY LINKED LIST
1. An array is a collection of elements having 1. Linked List is an ordered collection of
same data type with commonname. elements which are connected by links
orpointers.
2. In Array, elements can be accessed using index 2. In Linked List, elements can be accessed
or subscript value i.e., elements can be accesses sequentially and accessing
accessed randomly. So array provides element takes order of n O(n) times.
fasterrandom access.
3. In Linked List, elements can be stored at
3. In Array, elements are stored in consecutive any available place as address of node is
memorylocations. stored in previous node.
4. Insertion & Deletions are fast and easy
4. Insertion & Deletion takes more time in array as in linked list as only value of pointer is
elements are stored in consecutive needed to change.
memorylocations. 5. In Linked List memory is allocated at
runtime i.e., Dynamic Memory
5. In Array memory is allocated at compile time Allocation.
i.e., static memoryallocation. 6. Linked List can be single, double or
circular linkedlist.
6. Array can be single dimensional, two 7. In Linked List location or address is
dimensional or multidimensional. stored in the link part of previous
7. In Array each element is independent, no element ornode.
connection with previous element or with its 8. In Linked List, adjacency between the
location. elements are maintained using pointers
8. In Array no pointers are used like linked list. So, or links. So pointers are used for that
no need of extra space in memory for pointer. extra memory space is needed.

Page 30
 Unit – III
Stacks
Stack is a linear data structure that follows the LIFO (Last-In-First-Out) principle. Stack has one end,
whereas the Queue has two ends (front and rear). It contains only one pointer top pointer pointing to the
topmost element of the stack. Whenever an element is added in the stack, it is added on the top of the
stack, and the element can be deleted only from the stack.
A stack can be defined as “a container in which insertion and deletion can be done from the one
end known as the top of the stack”.
Somekey points
 It is called as stack because it behaves like a real-world stack, piles of books, etc.
 A Stack is an abstract data type with a pre-defined capacity, which means that it can store the
elements of a limited size.
 It is a data structure that follows some order to insert and delete the elements, and that order can
be LIFO

TheStack Abstract Data Type

The stack abstract data type is defined by the following structure and operations. A stack is
structured, as described above, as an ordered collection of items where items are added to and removed
from the end called the “top.” Stacks are ordered LIFO.

Stack operations

Push : The insertion operation is called as push operation.

Pop : The deletion operation is called as pop operation.
Traverse : visiting each and every data item of a stack is called traverse operation
OVERFLOW: Inserting an element in an already filled stack is called overflow situation. Before inserting an
element into the stack, we need to take care about the overflow situation.
UNDERFLOW: The Pop operation with an empty stack is called as underflow situation. So, before popping
an element from the stack, we need to take care about the underflow situation.

Page 31
 Representation of Stack using Array
A stack is a data structure that can be represented as an array.
An array is used to store an ordered list of elements. Using an array for representation of stack is one of
the easy techniques to manage the data. But there is a major difference between an array and a stack.
Size of an array is fixed. While, in a stack, there is no fixed size since the size of stack changed with the
number of elements inserted or deleted to and from it.
Despite the difference, an array can be used to represent a stack by taking an array of maximum size; big
enough to manage a stack.

Stack Operations using Array

Before implementing actual operations, first follow the below steps to create an empty stack.
Step 1 - Include all the header files which are used in the program and define a constant 'SIZE' with specific
value.
Step 2 - Declare all the functions used in stack implementation.
Step 3 - Create a one dimensional array with fixed size (int stack[SIZE])
Step 4 - Define a integer variable 'top' and initialize with '-1'. (int top = -1)
Step 5 - In main method, display menu with list of operations and make suitable function calls to perform
operation selected by the user on the stack.
push(value) - Inserting value into the stack. push() is a function used to insert an element into the stack. In
a stack, the new element is always inserted at top position. Push function takes one integer value as
parameter and inserts that value into the stack. We can use the following steps to push an element on to
the stack...
Step 1 - Check whether stack is FULL. (top == SIZE-1)
Step 2 - If it is FULL, then display "Stack is FULL!!! Insertion is not possible!!!" and terminate the function.

Page 32
Step 3 - If it is NOT FULL, then increment top value by one (top++) and set stack[top] to value (stack[top] =
value).

pop() - Delete a value from the Stack. In a stack, pop() is a function used to delete an element from the
stack. In a stack, the element is always deleted from top position. Pop function does not take any value as
parameter. We can use the following steps to pop an element from the stack...
Step 1 - Check whether stack is EMPTY. (top == -1)
Step 2 - If it is EMPTY, then display "Stack is EMPTY!!! Deletion is not possible!!!" and terminate the
function.
Step 3 - If it is NOT EMPTY, then delete stack[top] and decrement top value by one (top--).

display() - Displays the elements of a Stack. We can use the following steps to display the elements of a
stack...
Step 1 - Check whether stack is EMPTY. (top == -1)
Step 2 - If it is EMPTY, then display "Stack is EMPTY!!!" and terminate the function.
Step 3 - If it is NOT EMPTY, then define a variable 'i' and initialize with top. Display stack[i] value and
decrement i value by one (i--).
Step 3 - Repeat above step until i value becomes '0'.
Implementation of a stack using an Array
#include <stdio.h>
int stack[20],top;
void main()
{
top=-1;
push(100);
push(500);
push(600);
display();
pop();
display();
}
push(int num)
{

Page 33
 top++;
stack[top]=num;
printf("item pushed =%d\n",num);
}
pop()
{
int d;
d=stack[top];
top--;
printf("Element deleted: %d \n",d);
}
display()
{
int i=0;
for(i = top ; i >=0 ; i--)
{
printf(" %d \n",stack[i]);
}
}

Stack Using Linked List

The major problem with the stack implemented using an array is, it works only for a fixed number
of data values. That means the amount of data must be specified at the beginning of the implementation
itself. Stack implemented using an array is not suitable, when we don't know the size of data which we are
going to use.
A stack data structure can be implemented by using a linked list data structure. The stack
implemented using linked list can work for an unlimited number of values. That means, stack implemented
using linked list works for the variable size of data. So, there is no need to fix the size at the beginning of
the implementation. The Stack implemented using linked list can organize as many data values as we
want.
In linked list implementation of a stack, every new element is inserted as 'top' element. That means
every newly inserted element is pointed by 'top'. Whenever we want to remove an element from the
stack, simply remove the node which is pointed by 'top' by moving 'top' to its previous node in the list. The
next field of the first element must be always NULL.

Page 34
Stack Operations using Linked List
To implement a stack using a linked list, we need to set the following things before implementing
actual operations.
Step 1- Include all the header files which are used in the program. And declare all the user defined
functions.
Step 2 - Define a 'Node' structure with two members data and next.
Step 3 - Define a Node pointer 'top' and set it to NULL.
Step 4 - Implement the main method by displaying Menu with list of operations and make suitable
function calls in the main method.
push(value) - Inserting an element into the Stack. We can use the following steps to insert a new node into
the stack...
Step 1 - Create a newNode with given value.
Step 2 - Check whether stack is Empty (top == NULL)
Step 3 - If it is Empty, then set newNode → next = NULL.
Step 4 - If it is Not Empty, then set newNode → next = top.
Step 5 - Finally, set top = newNode.

pop() - Deleting an Element from a Stack. We can use the following steps to delete a node from the stack...
Step 1 - Check whether stack is Empty (top == NULL).
Step 2 - If it is Empty, then display "Stack is Empty!!! Deletion is not possible!!!" and terminate the
function
Step 3 - If it is Not Empty, then define a Node pointer 'temp' and set it to 'top'.
Step 4 - Then set 'top = top → next'.
Step 5 - Finally, delete 'temp'. (free(temp)).

display() - Displaying stack of elements. We can use the following steps to display the elements (nodes) of
a stack...
Step 1 - Check whether stack is Empty (top == NULL).
Step 2 - If it is Empty, then display 'Stack is Empty!!!' and terminate the function.
Step 3 - If it is Not Empty, then define a Node pointer 'temp' and initialize with top.

Page 35
Step 4 - Display 'temp → data --->' and move it to the next node. Repeat the same until temp reaches to
the first node in the stack. (temp → next != NULL).
Step 5 - Finally! Display 'temp → data ---> NULL'.

Implementation of Stack using Linked List

#include <stdio.h>
struct node
{
int val;
struct node *next;
};
struct node *head;
void main ()
{
clrscr();
printf("\n*********Stack operations using linked list*********\n");
printf("\n----------------------------------------------\n");
push(44);
push(67);
push(81);
display();
pop();
pop();
display();
}
push (int val)
{
struct node *ptr = (struct node*)malloc(sizeof(struct node));
if(head==NULL)
{
ptr->val = val;
ptr -> next = NULL;

Page 36
 head=ptr;
}
else
{
ptr->val = val;
ptr->next = head;
head=ptr;
}
printf("Item pushed : %d\n",val);
}
pop()
{
int item;
struct node *ptr;
item = head->val;
ptr = head;
head = head->next;
free(ptr);
printf("Item popped : %d\n",item);
}
display()
{
int i;
struct node *ptr;
ptr=head;
printf("Printing Stack elements \n");
while(ptr!=NULL)
{
printf("%d\n",ptr->val);
ptr = ptr->next;
}}

Page 37
 QUEUE
A Queue is a linear data structure which follows FIFO mechanism, which means the element which was
inserted first in to the Queue will be the first one to go out. The insertion in Queue will be done at one end
and deletion will be done at another end. The place where insertions are made is called “rear” of the
Queue. The place where deletions are made is called “front” of the Queue. In a Queue, the elements are
inserted from rear end and deleted from front end.

The following are the list of operations that can be performed on Queue.
EnQueue: The insertion operation is called EnQueue(ENQ).
DeQueue: The deletion operation is called DeQueue(DNQ).
Traverse( Display ): Visiting each and every element of a Queue is called “Traversing”.
OVERFLOW: Inserting an extra element in an already filled Queue is called Overflow. Before inserting an
element into a Queue, we need to take care about the overflow.
UNDERFLOW: The deletion operation with an empty Queue is called Underflow. So, before deleting an
element from the Queue, we need to take care about the underflow situation.

Algorithm: InsertionOperation:
Initially front = rear = -1
Step-1: [ check for Overflow ] If( rear + 1 >= maxsize)
Display “Queue Overflow” Else
Read an element into item. if(rear = = -1) then
Rear = front = 0 Else
Rear = rear + 1 a[rear] = item
Step-2: Exit
Algorithm: DeletionOperation:
Step-1: [ check for underflow ]
If( front = -1 or front > rear ) Display “ Queue is underflow”
Else item=Q[front] front=front+1
Display :Deleted item is” + item
Step-2: Exit

Algorithm:Traversing
Step-1: set i = front
Step-2:while(i<=rear)
display Q[ i ] i=i+1
Step-3:Exit

Page 38
Types of Queues:
There are several types of Queues, each one is used in different type of application. The
following are thedifferent types ofQueues.
1. CircularQueues
2. PriorityQueues
3. Double Ended Queues(DEQueues)
1. CIRCULARQUEUES:
Let us consider a situation in ordinary Queue that the max-size of the Queue is 5 and 5
insertions arealready performed and 2 deletions are performed. After performing

deletions the Queue is as follows:

One more insertion operation is not permitted in the above Queue because the
rear reaches the max-size of theQueue even though there is a space left for 2 elements
before front.
In order to overcome such a kind of problem, we implement Queue as a circular one. In
a circular Queuethere is no beginning and there is no ending. If the rear reaches end of Queue,
it move towards front and the space utilized properly.

1. Insertion( ) 2. Insertion( )
Item=10 Item=20

3. Insertion( ) 4. Insertion( )
Item=30 Item=40

Page 39
 5. Insertion( )
Item=50 6. Deletion( )

7. Deletion( ) 8. Deletion( )

9. Insertion( ) 10.Insertion(
Item=60 )Item=70

11. Insertion( ) 12.Insertion( The next iteration of rear is

Item=80 )Item=90 equal to front. So, the Queue
is overflow.

Page 40
 Algorithm: Insertion()
Step-1: [ check for overflow ]
If((rear+1) % max-size = = front) then Display “ Queue is
Overflow”
Else
read a value into item if( rear = = -1) then
rare=front=0
else
rear = ( rear + 1 ) % max-size ;
Q[rear] = item;
Step 2 : Exit
(A) Algorithm: Deletion()

Page 41
 Step-1: [ check for underflow ] If( front = = -1 ) then
Display “Queue is underflow”
Else item=Q[front]
if( front = = rear ) then
Front = rear = -1
Else
Front = (front+1)%max-size display “element deleted”+item
Step-2: Exit
(B) Algorithm: Traversing()

Step-1: set i=front

Step-2: while ( i != (rear + 1)%max-size )
display Q[ i ]
i=(i+1)%max-size
Step-3: Exit

DOUBLE ENDED QUEUES

A Double Ended Queue is an abstract data structure that implements a Queue in which insertions and
deletions will be done either at the front end or at the rear end pf the Queue. The operations that can
be performed on double ended queue are
1. Insert an item from frontend
2. Insert an item from rearend
3. Delete an item from frontend
4. Delete an item from rearend
5. Display the elements ofQueue

A dequeue is a double-ended queue. You can insert items at either end and delete them from
either end. The methods might be called insertLeft() and insertRight(), and removeLeft() and
removeRight(). If you restrict yourself to insertLeft() and removeLeft() (or their equivalents on the right),
then the deque acts like a stack. If you restrict yourself to insertLeft() and removeRight() (or the
opposite pair), then it acts like aqueue.
A dequeue provides a more versatile data structure than either a stack or a queue, and is
sometimes used in container class libraries to serve both purposes. However, it's not used as often as
stacks and queues, so we won't explore it further here.

PRIORITY QUEUES
A priority queue is a more specialized data structure than a stack or a queue. However, it's a useful tool
in a surprising number of situations. Like an ordinary queue, a priority queue has a front and a rear, and
items are removed from the front. However, in a priority queue, items are ordered by key value, so that
the item with the lowest key (or in some implementations the highest key) is always at the front. Items
are inserted in the proper position to maintain theorder.

Page 42
 Here's how the mail sorting analogy applies to a priority queue. Every time the postman hands
you a letter, you insert it into your pile of pending letters according to its priority. If it must be answered
immediately (the phone company is about to disconnect your modem line), it goes on top, while if it can
wait for a leisurely answer (a letter from your Aunt Mabel), it goes on the bottom. When you have time
to answer your mail, you start by taking the letter off the top (the front of the queue), thus ensuring
that the most important letters are answered first.

Page 43
 UNIT – IV
Trees
A tree is a non-linear data structure and is generally defined as a nonempty finite set of elements,
called nodes such that:
1. Itcontainsaspecialnodecalledrootofthetree.
2. Others all nodes are partitioned under root, and should exist one path between any pairs of nodes.
(It doesn’t form anycycle).

Tree Terminologies:

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

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.

Page 44
 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
childnodes.

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

6. Leaf:
In a tree data structure, the node which
does not have a child is called as
LEAFNode. 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.

Page 45
 7. InternalNodes:
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

andsoon...Insimplewords,inatreeeachstepfromtoptobottomiscalledasaLevel and the Level count

starts with '0' and incremented by one at each level (Step).

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

Page 46
 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'.

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. SubTree:
In a tree data structure, each child
from a node forms a subtree
recursively.Every child node will form a
subtree on its parent node.

BINARY TREE

A binary tree is a tree-type non-linear data structure with a maximum of two children for each parent.
Every node in a binary tree has a left and right reference along with the data element. The node at the top
of the hierarchy of a tree is called the root node. The nodes that hold other sub-nodes are the parent
nodes.

Page 47
A parent node has two child
nodes: the left child and right
child. Hashing, routing data for
network traffic, data compression,
preparing binary heaps, and binary
search trees are some of the
applications that use a binary tree.

TYPES OF TREES

1. Complete BinaryTree:
A binary tree is said to be complete if all its level except possibly the last,
have maximum number of possible nodes, and if all the nodes at the last
level appear as far left as possible.

2. Full binarytree:
A Binary Tree is a full binary tree if every node has 0 or 2 children.
The following are the examples of a full binary tree. We can also
say a full binary tree is a binary tree in which all nodes except leaf
nodes have two children.

3. Perfect Binary Tree

A perfect binary tree is a binary tree in which all interior nodes have two
children and all leaves have the same depth or same level

4. SkewedTree:
A tree is called Skew if all the nodes of a tree are attached to one side
only. i.e A left skew will not have any right children in its each node and
right skew will not have any left child in its each node.

BINARY-TREE REPRESENTATION
A binary tree data structure is represented in two ways.
A. Arrayrepresentation
B. Linked listrepresentation

A. ARRAYREPRESENTATION:
In array representation of binary tree, we
use one-dimensional array. Let’s consider
the followingtree.

Page 48
 1. Store the left child at 2*i+1 position, if its parent node is at ithposition.
2. Store the right child at 2*i+2 position, if its parent node is at ithposition.
3. We need one-dimensional array with a maximum size of 2n+1-1, to represent a binary tree of
depth“n”.
4. The above example is represented asfollows.

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
A B C D E F G H I - - - J - - -

Advantages:
• This method benefits from more compact storage and better locality of reference,
particularly during a preordertraversal.
Limitations:
 Wastage of space for some types of binarytree.
 Insertion and deletions require potential changes in thearray.

B. LINKEDREPRESENTATION:
We use double linked list to represent binary tree. In a double linked list, every node consists of
three fields. First field is used to store the left child address, second field is used to store data,
third field is used tostore right child address.

Advantages:
Insertion and deletion involve no data movement and no movement of nodes except the rearrangement
ofpointers.

Limitations:
 Given a node structure, it is difficult to determine its parentnode.
 Memory spaces are wasted for storing NULL pointers for the nodes, which have nosubtrees.
BINARY TREE TRAVERSAL
There are three different types of traversing techniques to traverse a binary tree. Traversing means
visiting each and every node of a tree. The following are the different traversingtechniques.
1. Pre-ordertraversal
2. In-ordertraversal
3. Post-ordertraversal

1. Pre-OrderTraversal:
In this traversing technique, the root of the tree is visited first and followed by left sub- tree and
then right sub-tree is visited. The following is the sequence of visiting order of pre-ordertraversal.

Leftsub- Rightsub
Root
tree -tree
Page 49
Algorithm for Pre-Order Traversal:
Step-1: (check if the tree is empty by
verifying root pointer) If (p==NULL)
Print tree is empty
Step-2: visit root (root.data)
Step-3: visit left sub-tree (root.lchild) Step-4: visit right sub-tree (root.rchild) Step-5: exit.
Implementation:

void preorder(node root)

{ if( root != NULL )
{ print root . data;
preorder (root .lchild);
preorder (root .rchild);
}
}

The pre-order traversal of the above tree is as follows:

ABCHDEFGIJ

2. In-OrderTraversal
In this traversing technique the left sub-tree visited first followed by its root and then the right
sub-tree is visited. The following is the sequence of visiting order for an in-order traversal.

Left Right
sub-tree Root sub-tree

Page 50
 Algorithm for In-Order Traversal:
Step-1: (check if the tree is empty by
verifying root pointer) void inorder(node root)
If (p==NULL) { if(root != NULL)
Print tree is empty
{
Step-2: visit left sub-tree (root.lchild)
Step-3: visit root (root.data) inorder(root . lchild);
Step-4: visit right sub-tree (root.rchild) print root . data;
Step-5: exit
inorder(root . rchild);

Implementation: }
}

The In-Order traversal of the above tree is as follows:

HCBDAFEGIJ

3. Post-OrderTraversal:
In this traversing technique, the left sub-tree is visited first and then right sub-tree is visited and
then root is visited. The following is the sequence of visiting order of post order.

Left Right
sub-tree sub-tree Root

Page 51
 Algorithm for Post-Order Traversal:
Step-1: (check if the tree is empty byverifying
root pointer) If (p==NULL)
Print tree is empty
Step-2: visit left sub-tree (root.lchild) Step-3: visit right sub-tree (root.rchild) Step-4:
visit root (root.data)
Step-5: exit

Implementation:

The post-order traversal of the above tree is as follows:

HCDBFJIGEA
Examples of Tree traversals

BINARY SEARCH TREE (BST)

First of all, binary search tree (BST) is a dynamic data structure, which means, that its size is only
limited by amount of free memory in the operating system and number of elements may vary during
the program run.
A Binary tree is said to be binary search tree if the nodes of the left sub- tree of
Page 52
the root node are less than root node and the nodes of the right sub-tree of the root node are
greater than or equal to the root node.
Binary search tree is a data structure, which meets the following requirements:

• It is a binarytree;
• Each node contains avalue/key;
• Every element has a value and no two elements have the samevalue
• The keys in the left subtree are smaller than the key in theroot.
• The keys in the right subtree are larger than the key in theroot.
• Notice, that definition above doesn't allowduplicates.

Let us consider the following numbers to be stored into a binary search tree.
35, 14, 10, 25, 40, 50, 45, 65
The binary search tree of above data is as follows:

TRAVERSAL OF BINARY SEARCH TREE

The following are the different traversing techniques.
1. Pre-ordertraversal
2. In-ordertraversal
3. Post-ordertraversal

1. Pre ordertraversal
Algorithm for Pre-Order traversal:
Step-1: visit root node (display root.data) Step-2:
visit left sub-tree preorder(root.lchild) Step-3:
visit right sub-tree preorder(root.rchild)
Pre-Order : 3514102540504565

2. In ordertraversal
Algorithm for In-order traversal:
Step-1: visit left sub-tree inorder(root.lchild)
Step-2: visit root node ( display root.data) Step-
3: visit right sub-tree inorder(root.rchild)

In-Order :1014253540455065

Page 53
3. Post order traversal
Algorithm for Post-Order traversal:
Step-1: visit left sub-tree postorder(root.lchild)
Step-2: visit right sub-tree postorder(root.rchild)
Step-3: visit root node (display root.data)

Post-Order :1025144565504035

OPERATIONS ON BST
In order of this binary search tree gives ascending order of the list. Operations that can be
performed on binary search tree are:
1) Searching
2) Inserting anydata
3) Deleting any data fromBST

1. Searching in the binary searchtree:-

Searching in BST is much faster than arrays or linked list. Suppose we have to search for “ITEM”
in a binary search tree “T”. We start from root node “ROOT”. If “ITEM” is less than value in
“ROOT”, we proceed to left child. If ITEM is greater than value in ROOT, we proceed to right
child. We continue searching until we have found the desired value or reach the end of the tree.
Algorithm:
1. Read the search
value ITEM = Get
value ()
2. Initializing the variable “p” to
root. P =ROOT
3. Initialize the flag
variable flag
=false;
4. Start the searchprocess
while (p!=NULL && flag= = FALSE)
5. Check the ITEM and goto the left subtree
if (ITEM<data(p)) then
p=leftchild(p);
6. Check the ITEM and goto right subtree.
if (ITEM>data(p)) then p= right child (p);
7. Check the ITEM, if the ITEM is
found. If (ITEM = = data (p)then
8. Change the flag
status flag
=TRUE;

Page 54
 End if
Endwhil
e
9. Check the flagstatus
if (flag = = TRUE) then
print “Data item found at
“, p else
print “search
unsuccess” end if
10. Finish
STOP
2. Inserting in to binary searchtree:-
This is very simple and is extension of searching in binary search tree. To insert “ITEM” in to
binary search tree “T”. We start searching in “T” for “ITEM” from the root node. If “ITEM” is found
in binary search tree there is no insertion. If “ITEM” is not found then we insert it at the dead-end
where the search stops.

Algorithm:-
1. Access root
node P=ROOT;
2. Read the data ITEM
ITEM=Get value ();
3. Search for correct dead-end
node while (p!=NULL){
4. If the ITEM is less than node data, then move to left
child if (ITEM <Data(p))
p=Left child (p);
5. If the ITEM is greater than node data, then move to right
child else if(ITEM >Data(p))
p=Right child (p);
6. If the data ITEM is available in BST then STOP the process.
else if (ITEM = =Data(p))
{
print “The node already
exist”; EXIT;
}
} // End while
7. Insert new node at END. If ITEM is less than node data then create left
child. if (ITEM <Data(p))
Left child (p) = ITEM;

Page 55
 8. Otherwise the ITEM stores as a right child of the
node. else if (ITEM >Data(p))
Right child (p) = ITEM;
9. Finish
STOP
3. Deleting a node from binary searchtree:-
Another important function for maintaining BST is to delete a specific node form the tree. The
method to delete a node depends on the specific position of the node in the tree.

AVL Trees
A binary search tree can be maintained equal sized left and right sub trees, it is correctly suitable to
efficient searching operation. Such a binary search tree is called as balanced binary tree or AVL tree.
It was developed in the year 1962 by Adelson, Velskii and Landis.

Threaded Binary Tree (TBT):We know that a binary tree is represented either by using arrays or by using
linked list. When a binary tree is represented is by using linked list, if any node is not having a child, we
use null reference in thatposition.In any binary tree there are more number of null references than actual
references, it wastes lot of storagespace.

Heap Tree:
Heap data structure is a specialized binary tree based data structure. Hence it is a binary tree with
specialcharacteristics. In a heap data structure, nodes are arranged based on their values.

Every Heap data structure has the following properties.

ORDERING: Nodes must be arranged in a order according to values based on max heap or min
heap.
STRUCTURAL: All levels in a heap must be full, except last level and nodes must be filled from left to
right strictly.
A binary heap is a complete binary tree which satisfies the heap ordering property. The ordering
can be one of two types:
1.Min-heap
The value of each node is greater than or equal to the value of its parent, with the minimum-value
element at the root.

2. Max-heap
The value of each node is less than or equal to the value of its parent, with the maximum- value
element at the root.

Page 56
 UNIT – V
Searching and sorting:
SORTING
Sorting refers to the technique of arranging and rearranging of data in some specific order. A
collection of recordscalledalistwhereeveryrecordhasoneormorefields.The records are then arranged
inascending or descending order depending on the numerical value of the key.

Sorting is the process of arranging data into meaningful order, so that we can analyze it more
effectively and efficiently. Sorting can be done for text data into alphabetical order, and numeric data
into numerical order both are from ascending or descending.

Sorting refers to arrangement of data items either in ascending order or in descending order.
Sorting is the most primitive operation in data organization.

In general, to perform binary search technique among n elements, then we need to arrange
these elements in one order. There are several kinds of sorting algorithms.
1. Bubble Sort
2. SelectionSort
3. InsertionSort
4. QuickSort
5. MergeSort

1. BUBBLESORT
It is the most easiest sorting algorithms used with small number of elements.
In bubble sort technique, each time the consecutive elements are compared and swapping takes place
if necessary
i.e., a[0] is compared with a[1], a[1] is compared with a[2] and so on.

At the end of pass-1(iteration) the highest element of the list will be in its proper position i.e.,
a[n-1] is filled with highest element, again we have to repeat the same procedure for remaining n-1
elements. At the end of each iteration we found that the consecutive highest element will get their
properplace.
Let us consider the following example to implement bubble sort with an array a of 5 elements.
PASS-1:

In this pass a[0] is compared with a[1], a[1] is compared with a[2], a[2] is compared with a[3], a[3] is
compared with a[4]. Whenever greater than condition is true then swapping of those two elements
willbe performed.

Page 57
 PASS-2:

In this pass a[0] is compared with a[1], a[1] is compared with a[2], a[2] is compared with
a[3].Whenever greater than condition is true then swapping of those two elements will be performed.
PASS-3:

In this pass a[0] is compared with a[1], a[1] is compared with a[2]. Whenever greater than condition
istrue then swapping of those two elements will be performed.
PASS-4:

In this pass a[0] is compared with a[1]. Whenever greater than condition is true then swapping ofthose
two elements will beperformed.

As the end of pass-4 the 4th highest element is in a[1] position. The number of comparisons in
pass-4 is 1. Thetotal number of passes is 4 and total number of comparisons in all the passes is 10.
If there are n elements in the array then the total number of comparisons requiredfor bubble
sort isn(n-1)/2.

ALGORITHM:

Step-1: Read list of elements into an array of size n.

Step-2: loop for i=0 to n-1 each time increase i by 1
Step-3: loop for j=0 to n-i-1 each time increase j by 1
Step-4: if a[j]>a[j+1] then
temp = a[j] a[j] = a[j+1] a[j+1] =temp
Step-5: exit

Program to sort an array using Bubble Sort Algorithm.

#include <stdio.h>

Page 58
 #include <conio.h>
void main()
{
int a[15],i,j,n,temp; clrscr();
printf("\nENTER THE SIZE OF ARRAY:");
scanf("%d",&n);
printf("\nENTER VALUES FOR THE ARRAY:\n");
for(i=0;i<n;i++)
scanf("%d",&a[i]); for(i=0;i<n-1;i++)
{
for(j=i+1;j<n;j++)
{
if(a[i]>a[j])
{
temp=a[i]; a[i]=a[j]; a[j]=temp;
}
}
}
printf("\nTHE SORTED ARRAY IS:\n"); for(i=0;i<n;i++)
printf("%d ",a[i]); getch();
}

2. SELECTIONSORT
It is the most easiest sorting algorithm used with small number of elements. In selection sort
techniques, each time one element is compared with all the remaining elements and swapping takes
place if necessary,
i.e., a[0] iscompared with a[1],a[2],..a[n-1] and
a[1] is compared with a[2],a[3]… and so on…. At the end of pass-1, the lowest element of the list will
be in its proper position i.e., a[0].

Again we have to repeat the same process with a[1] for remaining elements. At the end of
each iteration we findthat the consecutive lowest element will be placed in their proper places.
Let us consider the following example to implement selection sort with an array of 5 elements.

Page 59
 PASS-1:

In this pass a[0] is compared with a[1],a[2],a[3] and a[4]. If a[0] greater than any of the element then
swapping will be takes place.

PASS-2:

In this pass a[1] is compared with a[2],a[3] and a[4]. If a[1] greater than any of the element then
swapping will be takes place.

PASS-3:

In this pass a[2] is compared with a[3] and a[4]. If a[2] is greater than any of the element then
swapping will be takes place.

PASS-4:

In this pass a[3] is compared with a[4]. If a[3] is greater than a[4] then
swapping will be done.

Algorithm:
Step-1: Read a list of elements into an array of size n. Step-2: loop i=0 to n-1 each time increment i by 1
Step-3: loop j=i+1 to n-1 each time increment j by 1
Step-4: if a[i] > a[j] then
temp=a[i] a[i]=a[j] a[j]=temp
Step-5: Exit

Page 60
 Program on Selection Sort
#include <stdio.h> #include <conio.h> void main()
{
int array[10]; int i, j, N,temp;
int findmax(int b[10], int k);
/* function declaration */
void exchang(int b[10], int k); clrscr();
printf("Enter the value of N\n"); scanf("%d",&N);
printf("Enter the elements one by one\n"); for (i=0; i<N ; i++)
{
scanf("%d",&array[i]);
}
printf("Input array elements\n"); for (i=0; i<N ; i++) {
printf("%d\n",array[i]);
}
/* Selection sorting begins */
exchang(array,N);
printf("Sorted array is...\n");
for (i=0; i< N ; i++)
{
printf("%d\n",array[i]);
}
}
/* End of main*/
/* function to find the maximum value */
int findmax(int b[10], int k)
{
int max=0,j;
for (j = 1; j <= k;j++)
{
if ( b[j] >b[max])
Page 61
 {
max = j;
}
}
return(max);
}
void exchang(int b[10],int k)
{
int temp, big, j;
for ( j=k-1; j>=1; j--)
{
big = findmax(b,j); temp = b[big]; b[big] = b[j];
b[j] = temp;
}
return;
}

3. INSERTIONSORT:
It is another kind of most efficient sorting algorithm. This algorithm begins with taking first element of
the listas in its proper place i.e, in sorted list and the remaining all elements will be considered as
unsorted list.
Then first element of the unsorted list will be compared with sorted list and if it is less than the
value in sorted list then swapping will be performed. This process will be continued until unsorted list
will become empty.
Let us consider the following list in to an array of size 5.

First we will split the list into two parts as follows.

First element will be considered as sorted list and all the remaining will be
considered as unsorted list.

PASS-1:

In this pass a[1] will be a[0]. Since a[0] < a[1] then a[1] will be taken into sorted list without swapping.

Page 62
 PASS-2:

In this pass a[2] is compared with a[1]. Since a[1] > a[2] then swapping will be performed.

After swapping a[1] and a[0] are compared. Since a[0] > a[1] then again swapping will be performed.

PASS-3

In this pass a[3] is compared with a[2]. Since a[2] > a[3] then swapping will be performed. After

swapping a[2] is compared with a[1]. Since a[1] < a[2] then this will be completed.
PASS-4

In this pass a[4] is compared with a[3]. Since a[3] > a[4] swapping will be performed.

After swapping a[3] is compared with a[2]. Since a[2] >a[3] again these two elements will be swapped.

After swapping a[2] is compared with a[1]. Since a[1] >a[2] again these two elements will be swapped.

After swapping a[1] is compared with a[0]. Since a[0] >a[1] again these two elements will be swapped.

There are no more elements left to compare. So 7 is placed at a[0].

Algorithm:

Step-1: Read a list values into an array of size n. Step-2: loop for i=1 to n-1 each time increment i by 1.
Step-3: set value=a[i] and place =i
Step-4: Repeat step-5
until place > 0 and a[place-1] > value
Step-5: a[place]=a[place-1]
Place=place-1 Step-6: a[place]=value Step-7: Exit

Program on Insertion sort using functions

#include<stdio.h> #include<conio.h> void inst_sort(int []); void main()
Page 63
 {
int num[5],count; clrscr();
printf("\nEnter the Five Elements to sort:\n"); for (count=0;count<5;count++)
scanf("%d",&num[count]); inst_sort(num);
printf("\n\nElements after sorting: \n"); for (count=0;count<5;count++)
printf("%d\n",num[count]);
getch();
}
// Function for Insertion Sorting
void inst_sort(int num[])
{
int i,j,k;
for (j=1;j<5;j++)
{
k=num[j];
for (i=j-1;i>=0 && k<num[i];i--) num[i+1]=num[i];
num[i+1]=k;
}
}

4. QUICKSORT:
This is the most efficient and fastest sorting procedure when compared to all other sorting algorithms.
This sorting algorithm uses divide and conquer approach of the elements of the array to arrange them
either in ascending order or in descendingorder.
 In this algorithm the array will be portioned into two parts based on pivotelement.
 On each step the pivot element will be placed in correct location and hence the array will be divided into two
parts. Those are before pivot element and after the pivotelement.
 The same process is repeated for both parts and therefore again these two parts will be divided and same
process is repeated for these subparts until the size of the sub part become1.
 It is very clear that the algorithm is completely based on portioning approach for the pivot element.

Algorithm:
Step-1 : Read a list of values into an array of sizen.
Step-2 : set i=low andj=high+1
Step-3 : if low <high
Page 64
 Set pivot=a[low]
Step-3.1: Repeat
while a[i] < pivot and i<hight, i++ Step-3.2 : Repeat while a[j]>pivot and j>=high, j --
Step-3.3 : if(i<j) then
temp=a[i] a[i]=a[j] a[j]=Temp
Repeat until 3.1, 3.2, 3.3 otherwise stop the loop
Step-3.4 : swap pivot and a[j]
Quick(a, low, j-1) Quick(a, j+1, high)
Step-4 : Exit

Program using Quick Sort Algorithm.

#include <stdio.h> #include <conio.h> void qsort();

int n;
void main()
{
int a[100],i,l,r; clrscr();
printf("\nENTER THE SIZE OF THE ARRAY: ");
scanf("%d",&n); for(i=0;i<n;i++)
{
printf("\nENTER NUMBER-%d: ",i+1); scanf("%d",&a[i]);
}
printf("\nTHE ARRAY ELEMENTS BEFORE SORTING: \n");
for(i=0;i<n;i++)
{
printf("%5d",a[i]);
} l=0;
r=n-1;
qsort(a,l,r);
printf("\nTHE ARRAY ELEMENTS AFTER SORTING: \n");
for(i=0;i<n;i++)
printf("%5d",a[i]); getch();
}
Page 65
 void qsort(int b[],int left,int right)
{
int i,j,p,tmp,finished,k; if(right>left)
{
i=left; j=right; p=b[left]; finished=0;
while (!finished)
{
do
{
++i;
}
while ((b[i]<=p) && (i<=right));
while ((b[j]>=p) && (j>left))
{

}
if(j<i)

else
{--j;

finished=1;
tmp=b[i]; b[i]=b[j]

b[j]=tmp;
}
}
tmp=b[left]; b[left]=b[j]; b[j]=tmp; qsort(b,left,j-1); qsort(b,i,right);
}
return;
}

Page 66
 MERGESORT
Merge sort technique can be implemented in two ways.
1. We can take two sorted lists and then form a new sorted list by arranging the two sorted lists intoonelist.
2. We will divide the list into two parts until the sub-list contains single values and then merging them in
a sorted order. While merging place lower values in left hand side and larger values in right handside.

Algorithm:
Step-1: Read a list of elements into an array of size n
Step-2: Divide the unsorted list into two sub-lists of about half the size until the sub-list contains single
element.
Step-3: Sort each sub-list recursively by reapplying merge sort
Step-4: Merge the two lists into one sorted list until the final list contains n elements.
Step-5: Exit

Program on Merge Sort using functions

Page 67
 #include <stdio.h> #include <stdlib.h> #define MAX_ARY 10
void merge_sort(int x[], int end, int start); int main(void){
int ary[MAX_ARY]; int j =0;
printf("\n\nEnter the elements to be sorted: \n"); for (j=0;j<MAX_ARY;j++)
scanf("%d",&ary[j]);
/* array before mergesort */ printf("Before :");
for (j = 0; j < MAX_ARY; j++) printf(" %d", ary[j]);
printf("\n");
merge_sort(ary, 0, MAX_ARY - 1);
/* array after mergesort */ printf("After Merge Sort :"); for (j = 0; j < MAX_ARY; j++)
printf(" %d", ary[j]); printf("\n");
getch();
}
/* Method to implement Merge Sort*/
void merge_sort(int x[], int end, int start) { int j = 0;
const int size = start - end + 1; intmid = 0;
int mrg1 = 0; int mrg2 =0;
int executing[MAX_ARY]; if(end == start)
return;
mid= (end + start) / 2;
merge_sort(x, end, mid);
merge_sort(x, mid + 1, start);
for (j = 0; j < size;j++)
executing[j] = x[end + j]; mrg1 = 0;
mrg2 = mid - end + 1;
for (j = 0; j < size; j++) {
if(mrg2 <= start - end) if(mrg1 <= mid - end)
if(executing[mrg1] > executing[mrg2]) x[j + end] = executing[mrg2++];
else x[j + end] = executing[mrg1++];
else x[j + end] = executing[mrg2++];
else x[j + end] = executing[mrg1++];

Page 68
 }} }

SEARCHING:
Finding the element whether the given element is present in the list or not is called searching.
It is the most important operation in the field of computer science. Searching means finding the
required element from a group of elements. The searching element is used as a key element.
There are two types of searching mechanisms. They are
1. Linear/ SequentialSearch
2. BinarySearch
1. LINEAR or SEQUENTIALSEARCH
As the name implies, the linear search works in a sequential order from the first element to the
required element found or till to the end of the list. The linear search compares the key element with
the group elements one by one until either a match has been found or the list becomesend.
Let us consider the following example.

Let, Searchkey=29.
1. The search process starts at a[0], which is compared with key. Since a[0]≠ key we move to
thenextelement.
2. Now a[1] is compared with key element. Since a[1] ≠ key we move on to thenext element.
3. Now a[2] is compared with key element. Since a[2] = key we stop thesearch process.

Algorithm:
Step-1: Read list of element into array a with size n.
Step-2: set i = 0 , flag = 0
Step-3: Repeat
while(i<n)
if(a[i] = key) then
set flag=1 and break the loop. set i=i+1
Step-4: if flag= = 1 then
Display “element found” else
Display “element not found”
Step-5: Exit

Program : Linear or Sequential Search

#include <stdio.h> #include <conio.h> main()

{
int arr[]={12,23,78,98,67,56,45,19,65,9},key,i,flag=0;
clrscr();
Page 69
 printf("\nENTER A NUMBER: "); scanf("%d",&key); for(i=0;i<10;i++)
{
if(key==arr[i]) flag=1;
}
if(flag==1)
printf("\nTHE NUMBER %d EXISTS IN THE ARRAY",key);
else
printf("\nTHE NUMBER %d DOES NOT EXIST IN THE ARRAY",key);
getch();
}

Output :

2. BINARYSEARCH
It is a divide and conquer technique. In binary search, the search process always focused on
middleelement of the list. In-order to perform binary search, the elements of the list should be
arranged in a sortedorder.
In binary search, first we calculate the location of the middle element. Then that element is
comparedwith key element. Then any one of the following three cases may occur.
1.If the key element is equal to the middle element, then we conclude that the element was found and
willstop the searchingprocess.
2.If the key element is less than middle element then we divide the array from the first element to
middle element and repeat the same process by calculating middleelement.
3.If the key element is greater than middle element, then we divide the array from middle element to
last element and repeat the same process by calculating middleelement.

Algorithm:
Step-1: Read list of elements into array a with size n in sorted order.
Step-2: set start=0, end=n-1, flag=0
Step-3: Repeat
while (start<=end)
Calculate mid=(start+end)/2 If(a[mid]>key) then end=mid-1 If(a[mid]<key) then start mid+1
If(a[mid])==key then
set flag=1 and break the loop
Step-4: if(flag==1) then
Display” element found” else
Display “element not found”
Step-5 : Exit

Page 70
 Program : Binary Search using functions
#include <stdio.h> #include <conio.h> void sort(int *);
int search(int *,int); void main()
{
int a[10],i,j,temp,key,flag; clrscr();
for(i=0;i<10;i++)
{
printf("\nENTER NUMBER-%d: ",i+1); scanf("%d",&a[i]);
}
sort(a);
printf("\nTHE SORTED ARRAY IS: ");
for(i=0;i<10;i++) printf("%d ",a[i]);
printf("\nENTER A NUMBER TO SEARCH: ");
scanf("%d",&key); flag=search(a,key); if(flag==1)
printf("\nTHE NUMBER %d EXISTS",key); else
printf("\nTHE NUMBER %d DOES NOT EXIST ARRAY",key);
getch();
}

void sort(int *x)

{
int i,j,temp; for(i=0;i<10;i++)
{
for(j=i+1;j<10;j++)
{
if(x[i]>x[j])
{
temp=x[i]; x[i]=x[j]; x[j]=temp;
} } } }
int search(int *x,int k)
{

Page 71
 int low=0,high=10,mid,res=0; while(high>=low)
{
mid=(high+low)/2; if(k==x[mid])
{
res=1; break;
}
else
{
if(k>x[mid]) low=mid+1; else high=mid-1;
}}return res;}

GRAPHS
Graph is a non-linear data structure mainly used in the applications for finding shortest path root. This
data structure consists of number of non-empty set of vertices as well as edges.
(OR)
A graph can be defined as group of vertices and edges that are used to connect these vertices. A graph
can be seen as a cyclic tree, where the vertices (Nodes) maintain any complex relationship among
them instead of having parent child relationship.

Definition
A graph G can be defined as an ordered set G(V, E) where V(G) represents the set of vertices and E(G)
represents the set of edges which are used to connect these vertices.

A graph ‘G’ consists of a set of ‘V’ vertices (nodes) and set of ‘E’ edges (arcs)
To represent a graph G= {V, E}, here V is a non-empty set of vertices, E is a set of pairs of vertices called
edges.
Where V = {v1, v2,………vi};
E = {e1, e2,e3….ej}

Generally, graphs are mainly two types, they are

1. Undirectedgraphs
2. Directed graphs.

Page 72
 Fig.undirectedgraph Fig. directedgraph

TERMINOLOGY:
Let us take a graph

1. Path:
The edges involved in connection between any pair of vertices is called path. In the above
example the edges AB,BD forms a path between the vertices A and D.
start vertex

End vertex
2. IsolatedVertex:
A vertex which does not have any edges connect to it os called isolated vertex. In the below

example D is called isolated vertex.

3. UndirectedGraph:
A graph G(V,E) is called an undirected graph, if there is no specified direction for the edges.
4. Directed graph or Digraph:
A graph G(V,E) is said to be digraph, if the directions are specified for all edges.

5 In-degree of agraph:
For a directed graph, the number of edges incident with vertex is called its in-degree. The in-
degrees of vertices of the above graph is shown below.
In-Degree of

Page 73
 A is 0
B is2
C is 1
D is 2
E is 2

6.Out-degree of agraph:
For a directed graph, the number of edges eliminating from a vertex is called out-degree. The
out-degree of vertices of the above graph is shown below.

Out-Degreeof A is 2

B is2
C is 1
D is 1
E is 1
5. Loop (or)Cycle:
A path which starts from a vertex and ends with the same vertex forms a cycle.

6. Self-Loop:
A vertex which has an edge with itself is called as self loop.
7. WeightedGraph:
A graph G(V,E) is called a weighted graph, if there is a positive
integer assigned to each and every edges of a graph.

APPLICATIONS OF GRAPHS
Since they are powerful abstractions, graphs can be very important in
modelingdata.
 Social network graphs: Graphs that represent who knows whom, who communicates with
whom or other relationships in socialstructures
 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 betweenlocations.
 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 betweenthem.
 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 directededge.

Page 74
  Network packet traffic graphs. Vertices are IP (Internet protocol) addresses and edges are the
packets that flow betweenthem.
 Robot planning. Vertices represent states the robot can be in and the edges the possible
transitions between thestates.
 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
welearn.
 Semantic networks. Vertices represent words or concepts and edges represent the
relationships among the words orconcepts.
 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 otherpurposes.

TRAVERSAL OF A GRAPH
A graph traversal means, visiting all the nodes of the graph. Graph traversal may be needed in many
of application areas and there may be many methods for visiting the vertices of the graph. Many
graph applications required to one to systematically examining the nodes and edges of a graph.
There are two standard ways ie., is done
1) Breadth first search(BFS)
2) Depth first search(DFS)
Here, The breadth – first search will use a queue as an auxiliary structure to hold nodes
forfutureprocessingThe depth – first search will use a stack.

1. BREADTH – FIRST SEARCH(BFS)

Breadth first search can be used to find the shortest distance between starting node and the remaining
nodes of the graph. This shortest distance is the minimum number of edges traversed in order to travel
from the starting node to the specific node being examined.

The general idea behind a breadth – first search beginning at a starting node A is
asfollows.
 First we examine the starting nodeA.
 Then we examine all the neighbors ofA.
 After then we examine all the neighbors of the neighbors ofA.
 And soon.
During the execution of our algorithm each node of a graph will be in one of 3
statuses called “STATUS” of the node.

Page 75
 STATUS 1: (Ready state): - The initialize state of the node.
STATUS 2:(Waitingstate): - The node ‘n’ is on the queue waiting for processing.
STATUS 3: (Processed state):- The node ‘n’ has beenprocessed.

Algorithm:
This algorithm executes a breadth – first search on a graph G beginning at a starting node A.
1. Initialize all nodes to the ready state (STATUS =1)
2. Put the starting node A in QUEUE and change its status to the waiting state(STATUS =2).
3. Repeat the steps 4 & 5until the queue isempty.
4. Remove the front node N of QUEUE. Process N and change the status of N
to the processed state(STATUS =3).
5. Add to the rear of QUEUE all the neighbors of N that are in the steady state
(STATUS = 1), and change their status to the waiting state (STATUS =2).
[End of Step3 loop.]
6. Exit.

The above algorithm will process only those nodes which are reachable from the starting
node A. Suppose one wants to examine all the nodes in the graph G. then the algorithm must be
modified so that it begins again with another node (which we will call B) that is still in the ready
state. This node B can be obtained by traversing the list of nodes.

Example:
Consider the graph G In fig. Suppose G represents the daily flights between cities some airline, and
suppose we want to fly from city A to city J with the minimum number of stops. In other words, we
want the minimum path P from A to J (where each edge has length 1).
The minimum path P can be found by using a breadth – first search beginning at city A and
ending when J is encountered. During the execution of the search, we will also keep track of the
origin of each edge by using an array ORIG together with the array QUEUE.

Adjacency Lists
A: F, C, B
F C B B: G, C
C:F
D:C
E:D,C,J
D G F:D
E
G:C,E
J:D,K
K:E,G
J K
Fig.a. Fig.b

Page 76
 The steps of our search follow.
a. Initially, add A to QUEUE and add NULL to ORIG asfollows:
FRONT = 1 QUEUE: A
REAR=1 ORIG:Ø
b. Remove the front element A from QUEUE by setting FRONT:=FRONT + 1. and add to QUEUE
the neighbors of A asfollows:
FRONT = 2 QUEUE: A, F, C,B
REAR=4 ORIG: Ø, A, A,A
Note that the original A of each of the three edges is added to ORIG.
c. Remove the front element F from QUEUE by setting FRONT := FRONT +1, and add to QUEUE
the neighbors of F asfollows:
FRONT = 3 QUEUE: A, F, C, B,D
REAR=5 ORIG: Ø, A, A, A,F
d. Remove the front element C from QUEUE, and add to QUEUE the neighborsof C(which
are in the ready state) asfollows:
FRONT = 4 QUEUE: A, F, C, B,D
REAR=5 ORIG: Ø, A, A, A,F
Note that the neighbor F of C is not added to QUEUE, since F is not in the ready state
(because F has already been added to QUEUE).
e. Remove the front element B from QUEUE, and add to QUEUE the neighborsof B(the
ones in the ready state) asfollows:
FRONT = 5 QUEUE: A, F, C, B, D,G
REAR=6 ORIG: Ø, A, A, A, F,B
Note that only G is added to QUEUE, since the other neighbor, C is not in the ready state.
f. Remove the front element D from QUEUE, and add to QUEUE the neighborsof
D(the ones in the ready state) as follows:
FRONT =6 QUEUE: A, F, C, B, D,G
REAR=6 ORIG: Ø, A, A, A, F,B
g. Remove the front element G from QUEUE, and add to QUEUE the neighborsof G(the
ones in the ready state) asfollows:
FRONT =7 QUEUE: A, F, C, B, D, G,E
REAR=7 ORIG: Ø, A, A, A, F, B,G

h. Remove the front element E from QUEUE, and add to QUEUE the neighbors of E(the
ones in the ready state) asfollows:
FRONT = 4 QUEUE: A, F, C, B, D, G, E, J

Page 77
 REAR=5 ORIG: Ø, A, A, A, F, B, G,E
We stop as soon as J is added to QUEUE, since J is our final destination. We now backtrack
from J, using the array ORIG to find the path P.Thus
J E G B A

2. DEPTH FIRST SEARCH(DFS):

Depth First Search is an alternative to the breadth first search. The general idea behind a depth
– first search beginning at a starting node A is asfollows.

 First we examine the starting nodeA.

 Then we examine each node N along a path P which begins at A; that is, we process a
neighbor ofA,
 then a neighbor of a neighbor ofA, and soon.
After coming to a “dead end,” that is, to the end of the path P, we backtrack on P until we can
continue along another path p’. And soon.

(This algorithm is similar to the inorder traversal of a binary tree, and the algorithm is also similar
to the way one might travel through a maze.)

The algorithm is very similar to the breadth – first search except now we use a stack instead of
the queue.

During the execution of our algorithm each node of a graph will be in one of three statuses
called “STATUS” of the node.

STATUS 1: (Ready state):- The initialize state of the node.

STATUS 2: (Waiting state):- The node ‘n’ is on the stack waiting for processing.
STATUS 3: (Processed state):- The node ‘n’ has been processed.

Algorithm:
This algorithm executes a Depth – first search on a graph G beginning at a starting node A.
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 & 5 until STACK is empty.
4: Remove the front node ‘A’ of STACK. Process ‘A’ and change the status of ‘A’ to the
processed state (STATUS 3).
5: Add to the STACK of all the neighbors of node ‘A’ that are in the ready state and change
their status to the waiting state (STATUS 2).
6:Exist.

Page 78
 Again, the above algorithm will process only those nodes which are reachable from the starting
node A. Suppose one wants to examine all the nodes in G. Then the algorithm must be modified so
that it begins again with another node which we will call
B – that is still in the ready state. This node B can be obtain by traversing the list of nodes.

Example:
Consider the graph G in Fig. Suppose we want to find and print all the node reachable from the
node J (including J itself). One way to do this is to use a depth – first search of G starting at the
node J. the steps of our searchfollow.

a). Initially, push J onto the stack asflows:

STACK: J
b). Pop and print the top element J, and then push onto the stack all the neighbors ofJ (those
that are in the ready state) asfollows:
Print J STACK: D, K
c). Pop and print the top element K, and then push onto the stack all the neighborsof
K(those that are in the ready state) asfollows:
PrintK STACK: D, E,G
d). Pop and print the top element G, and then push onto the stack all the neighbors
G(those in the ready state) asfollows:
PrintG STACK: D, E,C
Note that only C is pushed onto the stack, since the other neighbors, E, is not in the ready
state(because E has already been pushed onto the stack).
e). Pop and print the top element C, and then push onto the stack all the neighbors ofC (those
in the ready state) asfollows:
PrintC STACK: D, E,F
f). Pop and print the top element F, and then push onto the stack all the neighborsof
F(those in the ready state) asfollows:
Print FSTACK: D, E
Note that the only neighbor D of F is not pushed onto the stack, since D is not in the ready
state( because D has already been pushed onto the stack).
g). Pop and print the top element E, and push onto the stack all the neighbors of E(those in the
ready state) asfollows:
PrintE STACK: D

(Note that none of the three neighbors of E is in the ready state.)

h). Pop and print the top element D, and push onto the stack all the neighbors ofD(those in the
ready state) asfollows:
Page 79
 PrintD STACK:
The stack is now empty, so the depth – first search of G starting at J is now complete.

Accordingly, the nodes whichwereprinted, J, K, G, C, F, E,D

SPANNING TREE
Spanning tree of the graph is an undirected graph consisting of only those edges that are necessary to
connect all the vertices in the original graph.
A spanning tree has a property that any pair of vertices they exists only one path
between them, in spanning tree travers from any edge make a unique cycle.

General Properties of Spanning Tree

Following are a few properties of the spanning tree connected to graph G −
1. A connected graph G can have more than one spanningtree.
2. All possible spanning trees of graph G, have the same number of edges
andvertices.
3. The spanning tree does not have any cycle(loops).
4. Removing one edge from the spanning tree will make the graphdisconnected,
i.e. thespanning tree is minimally connected.
5. Adding one edge to the spanning tree will create a circuit or loop, i.e. the
spanning treeis maximallyacyclic.
Mathematical Properties of Spanning Tree
1. Spanning tree has n-1 edges, where n is the number of nodes(vertices).
2. From a complete graph, by removing maximum e - n + 1 edges, we can
construct aspanningtree.
3. A complete graph can have maximum nn-2 number of spanningtrees.

Applications 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 −

Examples of spanning tree

Page 80
 The spanning trees for the above graph are

Minimum Spanning Trees:

For a weighted graph, the spanning tree which is formed with all the vertices of the graph whose
total cost is minimum among all the other spanning trees is called “minimal spanning tree”.
Obtaining a minimum cost spanning tree involves so much of work. In-order to simplify this
process, two algorithms are introducedthey are
1. Kruskal’salgorithm
2. Prim’salgorithm
The DFS and BFS traversals result in a spanning tree but it is not guaranteed to be a minimum
spanningtree.
1. KRUSKAL’SALGORITHM:
The algorithm was introduced by a mathematician J.B.Kruskal.
Kruskal's algorithm finds a minimum spanning forest of an
undirected edge-weighted graph. ... It is a greedy algorithm in graph
theory as in each step it adds the next lowest-weight edge that will
not form a cycle to the minimum spanning forest.
Algorithm:
Step-1: Initialize all the vertices with no edges.
Step-2: Maintain a list of edges I an increasing order of weights.
Step-3: Choose edges from list one by one and add it to the tree if it doesn’t form a cycle.
Step-4: Repeat step 3 until (n-1) edges are added to the tree.

Prim's Algorithm

Prim's Algorithm is used to find the minimum spanning tree from a graph. Prim's algorithm finds the
subset of edges that includes every vertex of the graph such that the sum of the weights of the edges can
be minimized.

Prim's algorithm starts with the single node and explore all the adjacent nodes with all the connecting
edges at every step. The edges with the minimal weights causing no cycles in the graph got selected.

The algorithm is given as follows.

Page 81
Algorithm
o Step 1: Select a starting vertex
o Step 2: Repeat Steps 3 and 4 until there are fringe vertices
o Step 3: Select an edge e connecting the tree vertex and fringe vertex that has minimum weight
o Step 4: Add the selected edge and the vertex to the minimum spanning tree T
[END OF LOOP]
o Step 5: EXIT

Unit Wise Important Questions

Unit-I :

1. What is a Data Structure ? Explain about Different Types of Data Structure ?

2. Explain about Abstract Data Type ?
3. Difference between data types and data structures?
4. Explain about Algorithm ? Explain about algorithm and algorithm analysis?
5. Explain about Big O notation and recursion?
6. Explain about Structured approach to programming?

Unit-II:

1. Explain about linear and non-linear data structures?

2. Explain about different types of arrays?
3. Explain about Dynamic memory allocation?
4. What is a Linked List ? Explain about Operation of Linked List ?
5. Explain about Single Linked List , Double Linked List , Circular Linked List ?
Page 82
 6. Explain about Difference between Arrays and Linked List ?

Unit - III:

1. What is Stack ?Explain about Operations on Stack ?

2. Explain about Stack Representation Using Arrays ?
3. What is Queue ? Explain about Operations
4. Explain about Types of Queues and Applications of Queues ?
5. Explain about Circular Queues ?
6. Explain about : Double Ended Queue , Priority Queue ?

Unit-IV:

1. What is Binary Tree ?Explain about Types of Tree ?

2. Explain about Representation of Binary Trees?
3. Explain about Tree Traversal Methods ?
4. What is Binary Search Tree ? Explain about BST Operations ?

Unit-V:

1. Explain about Insertion Sort , Merge Sort , Quick Sort ?

2. Explain about Sequential Search ?
3. What is Graph ? Explain about Sequential Representation of Graphs ?
4. Explain about Spanning Trees?
5. Explain about Traversal of Graphs (BFS and DFS )?

Page 83