2.

Data Structure

Data: Data are simply values or set of values.

Data item : Data items is a single unit of values.

1.Group Item:Data items those can divided into sub items.

Ex:Full Name: First Name,Middle Name,Last Name

2.Elementary item: Data items those can not be divided into sub items.

Ex:Age:17

Entity:An entity is something that has certain attributes or properties which assigned values.

The collection of all entities form an entity set.

Information:The information is also used for data with given attributes ,information means
meaningful data.

Field:Field is single elementary unit of information representing an attributes of entity.

Record:A record is a collection of field values of a given entity.

File:A file is a collection of records of the entities.

Data Structure:The logical or mathematical model of a particular organization is called Data

Data structure Operation

The data in data structure are processed by certain operation like:

1.Traversing:For Processing certain item in record,each record is accessed exactly once.

2.Searching:Finding location of a record with given key value or finding the location of all
records,which satisfy one or more conditions.

3.Inserting:Adding a new record to the structure.

4.Deleting:Removing a record from a structure.

5.Sorting:Arranging the records in some order.

6.Merging;Combining the records in two different sorted files into a single sorted file.

Algorithm Notations

An alogorithm is a finite step-by step list of well-defined instruction for solving a particular
problem.the form for formal representation of an algorithm consists of two part

1) It tells the purpose of algorithm,identification variables,which occur in algorithm and

Generally three types of logic are used in algorithm that are as follow,

1)Sequence Logic

2)Selection Logic

3)Iteration Logic

Arrays

A linear array is a list of finite number n of homogeneous data elements . the elements of array are
referenced by index set consisting of n consecutive numbers.

The number n of elements is called length or size of the array.

Length=UB-LB+1

Where UB=Largest index i.e upper bound

LB=Smallest index i.e lower bound

Representation of linear array in memory

Elements of linear array are stored in successive memory cells/blocks

The number of cells required depends on type of data elements.

Computer keeps track of address of the first elements of array

Here Array is linear array and address of first elements is denoted by base(Array) and called as base
address of Array.

Using base address computer calculates the address of any elements of Array by using formula.

LOC(Array[K])=Base(Array)+W(K-LB)

Traversing Linear Array

Assesing each element of arrat only once so that it can be processed.

Let LA is a linear array with lower bound LB and upper bound UB.

The algorithm will apply process to each element of LA.

LA

12 42 34 25
1 2 3 4

Steps:

1)Start

2)Initialize counter

Set K=LB

3)Repeat steps 4th and 5th while(K<=UB)

4)Visit element

Apply process to LA[K]

5)Increment counter

K=K+1

6)Stop

Inserting a new element into Array

Let LA is a linear array of size N,this algorithm will inset ITEM at the kth position of LA,where K<= N+1

Steps:

1)Start

2)Initialize counter

Set J=N

3)Repeat 4th and 5th while(J>=K)

4)Move Jth element downword

LA[J+1]=LA[J]

5)Decrement counter

J=J-1
6)Insert ITEM

LA[K}=ITEM

7)Reset N=N-1

8)Stop

Deleting elements in array

1)Start

2)Set ITEM=LA[K]

3)Initialize counter

Set J=K

4)Repeat 5th and 6th while J<=N-1

5)Move J +1 th element upword

LA[J]=LA[J+1]

6)Increament counter

J=J+1

7)Reset N=N-1

8)Stop

Bubble Sorting

Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent
elements if they are in the wrong order. This algorithm is not suitable for large data sets as its
average and worst-case time complexity are quite high.

 We sort the array using multiple passes. After the first pass, the maximum element goes to
end (its correct position). Same way, after second pass, the second largest element goes to
second last position and so on.

 In every pass, we process only those elements that have already not moved to correct
position. After k passes, the largest k elements must have been moved to the last k positions.

 In a pass, we consider remaining elements and compare all adjacent and swap if larger
element is before a smaller element. If we keep doing this, we get the largest (among the
remaining elements) at its correct position.

Steps:

1)Start

2)Repeat steps 3rd and 4th for K=1 to N-1 by 1

4)Repeat step 5th and 6th while PTR <=N-K

5)Compare element

If (Data[PTR]>Data[PTR+1] then,

Interchange their values

Set temp=Data[PTR]

Set Data[PTR]=Data[PTR+1]

Set Data[PTR+1]=Temp

6)Increment counter

PTR=PTR+1

7)Display Sorted Data

8)Stop

Record

A record is collection of related data items. Each data item is termed as field. file is collection of
similar records. each data item may be a group item composed of sub item.

Ex

Linked List

It’s a linear collection of data elements called nodes .linear order is given by means of pointer.
Each node is divided into two parts,first part contains the information part of the elements and
second part contains the address of the next node in the list.

The left part represents the information part of node.the right part represents pointer field of
node.the arrow is drawn from this field to next node.pointer field of last node contain null
pointer.the address of first node in list called as start or name.we need only this address to trace the
linked list.

Tree

It is non linear data structure.it used to represents data containing hierarchical relationship between
elements.

Basic Terminologies In Tree Data Structure:

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

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

 Leaf Node or External Node: The nodes which do not have any child nodes are called leaf
nodes. {I, J, K, F, G, H} are the leaf nodes of the tree.

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

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

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

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

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

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

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

Binary Tree

A binary tree T is defined as a finite set of elements,called nodes such that-

1)T is empty(null tree or empty tree) or

2) T contains a distinguished node R,called root of T and the remaining node of T form an ordered
pair of disjoint binary tree T1 and T2
Representation binary tree in memory

1)Linked representation

2)sequential representation

Stack and queue in data structure

A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. This means that
the last element added to the stack is the first one to be removed. It can be visualized as a pile of
plates where you can only add or remove the top plate.

Operations on Stack:

The primary operations associated with a stack are:

 Push: Adds an element to the top of the stack.

 Pop: Removes and returns the top element of the stack.

 Peek (or Top): Returns the top element of the stack without removing it.

 IsEmpty: Checks if the stack is empty.

 Size: Returns the number of elements in the stack.

Queues
Queue

A queue is a linear data structure that follows the First In, First Out (FIFO) principle. This means that
the first element added to the queue is the first one to be removed. It can be visualized as a line of
people waiting for a service, where the first person in line is the first to be served.

Operations on Queue:

The primary operations associated with a queue are:

 Enqueue: Adds an element to the end (rear) of the queue.

 Dequeue: Removes and returns the front element of the queue.

 Front (or Peek): Returns the front element of the queue without removing it.

 IsEmpty: Checks if the queue is empty.

 Size: Returns the number of elements in the queue.