Data Structure - Lab
1.a. List Abstract Data
Type (ADT) using an array
To
write a Python program to implement the List
Abstract Data Type (ADT) using an array, and to perform basic operations such as insertion, deletion, searching, and display.
- Start the program.
- Create an empty list L.
- Display the menu with list
operations.
- Read the user’s choice.
- If choice is Insert, read the element and add
it to the list.
- If choice is Delete, read the element and
remove it from the list if it exists.
- If choice is Search, check whether the element
is present in the list.
- If choice is Display, print all the elements
of the list.
- Repeat steps 3–8 until the user
selects Exit.
- Stop the program.
#
List ADT using Array
L =
[] # empty list (array)
while
True:
print("\nLIST ADT MENU")
print("1. Insert")
print("2. Delete")
print("3. Search")
print("4. Display")
print("5. Exit")
choice = int(input("Enter your choice:
"))
# Insert element
if choice == 1:
item = int(input("Enter element to
insert: "))
L.append(item)
print("Element inserted")
# Delete element
elif choice == 2:
item = int(input("Enter element to
delete: "))
if item in L:
L.remove(item)
print("Element deleted")
else:
print("Element not
found")
# Search element
elif choice == 3:
item = int(input("Enter element to
search: "))
if item in L:
print("Element found at
position", L.index(item))
else:
print("Element not
found")
# Display list
elif choice == 4:
if len(L) == 0:
print("List is empty")
else:
print("List elements:",
L)
# Exit
elif choice == 5:
print("Program terminated")
break
else:
print("Invalid choice")
OUTPUT:
LIST ADT MENU
1. Insert
2. Delete
3. Search
4. Display
5. Exit
Enter your choice: 1
Enter element to insert: 10
Element inserted
LIST ADT MENU
1. Insert
2. Delete
3. Search
4. Display
5. Exit
Enter your choice: 1
Enter element to insert: 20
Element inserted
LIST ADT MENU
1. Insert
2. Delete
3. Search
4. Display
5. Exit
Enter your choice: 4
List elements: [10, 20]
LIST ADT MENU
1. Insert
2. Delete
3. Search
4. Display
5. Exit
Enter your choice: 2
Enter element to delete: 20
Element deleted
LIST ADT MENU
1. Insert
2. Delete
3. Search
4. Display
5. Exit
Enter your choice: 3
Enter element to search: 10
Element found at position 0
LIST ADT MENU
1. Insert
2. Delete
3. Search
4. Display
5. Exit
Enter your choice: 4
List elements: [10]
LIST ADT MENU
1. Insert
2. Delete
3. Search
4. Display
5. Exit
Enter your choice: 5
Program terminated
1.b) List Abstract Data
Type (ADT) using Singly Linked List
# Simple List ADT using Singly Linked List
class Node:
def
__init__(self, data):
self.data = data
self.next = None
head = None
while True:
print("\n1.Insert
2.Delete 3.Search 4.Display
5.Exit")
ch
= int(input("Enter choice: "))
#
Insert at end
if
ch == 1:
item = int(input("Enter element: "))
new = Node(item)
if head is None:
head = new
else:
temp = head
while temp.next:
temp = temp.next
temp.next = new
print("Inserted")
#
Delete element
elif ch == 2:
item = int(input("Enter element to delete: "))
temp = head
prev = None
while temp and temp.data != item:
prev = temp
temp = temp.next
if temp is None:
print("Not found")
elif prev is None:
head = temp.next
print("Deleted")
else:
prev.next = temp.next
print("Deleted")
#
Search element
elif ch == 3:
item = int(input("Enter element to search: "))
temp = head
pos = 0
while temp:
if temp.data == item:
print("Found at
position", pos)
break
temp = temp.next
pos += 1
else:
print("Not found")
#
Display list
elif ch == 4:
temp = head
if temp is None:
print("List empty")
else:
while temp:
print(temp.data, end="
")
temp = temp.next
print()
elif ch == 5:
break
else:
print("Invalid choice")
OUTPUT:
1.Insert
2.Delete 3.Search 4.Display
5.Exit
Enter choice: 1
Enter element: 10
Inserted
1.Insert
2.Delete 3.Search 4.Display
5.Exit
Enter choice: 1
Enter element: 20
Inserted
1.Insert
2.Delete 3.Search 4.Display
5.Exit
Enter choice: 1
Enter element: 30
Inserted
1.Insert
2.Delete 3.Search 4.Display
5.Exit
Enter choice: 2
Enter element to delete: 20
Deleted
1.Insert
2.Delete 3.Search 4.Display
5.Exit
Enter choice: 3
Enter element to search: 30
Found at position 1
1.Insert
2.Delete 3.Search 4.Display
5.Exit
Enter choice: 3
Enter element to search: 10
Found at position 0
1.Insert
2.Delete 3.Search 4.Display
5.Exit
Enter choice: 4
10 30
Result:
Thus, the above program has been executed
successfully.
2.a. Stack Abstract Data Type (ADT) using a Singly Linked
List
Aim
To implement the Stack Abstract Data Type (ADT) using
a Singly
Linked List and perform push and pop operations.
Algorithm
1.
Start
the program.
2.
Create
a node structure with data and next pointer.
3.
Initialize
top as NULL.
4.
Push:
Insert a new node at the beginning of the list.
5.
Pop:
Remove the first node from the list.
6.
Peek:
Display the top element.
7.
Display
all stack elements.
8.
Repeat
until exit.
9.
Stop.
class Node:
def
__init__(self, data):
self.data = data
self.next = None
top = None
# top of the stack
while True:
print("\nSTACK MENU")
print("1. Push")
print("2. Pop")
print("3. Peek")
print("4. Display")
print("5. Exit")
choice = int(input("Enter your choice: "))
#
Push operation
if
choice == 1:
item = int(input("Enter element to push: "))
new_node = Node(item)
new_node.next = top
top = new_node
print("Element pushed")
#
Pop operation
elif choice == 2:
if top is None:
print("Stack Underflow")
else:
print("Popped element:", top.data)
top = top.next
#
Peek operation
elif choice == 3:
if top is None:
print("Stack is empty")
else:
print("Top element:", top.data)
#
Display stack
elif choice == 4:
if top is None:
print("Stack is empty")
else:
temp = top
print("Stack elements:")
while temp:
print(temp.data)
temp = temp.next
#
Exit
elif choice == 5:
print("Program terminated")
break
else:
print("Invalid choice")
OUTPUT:
STACK MENU
1. Push
2. Pop
3. Peek
4. Display
5. Exit
Enter your choice: 1
Enter element to push: 10
Element pushed
STACK MENU
1. Push
2. Pop
3. Peek
4. Display
5. Exit
Enter your choice: 1
Enter element to push: 20
Element pushed
STACK MENU
1. Push
2. Pop
3. Peek
4. Display
5. Exit
Enter your choice: 4
Stack elements:
20
10
STACK MENU
1. Push
2. Pop
3. Peek
4. Display
5. Exit
Enter your choice: 3
Top element: 20
STACK MENU
1. Push
2. Pop
3. Peek
4. Display
5. Exit
Enter your choice: 2
Popped element: 20
STACK MENU
1. Push
2. Pop
3. Peek
4. Display
5. Exit
Enter your choice: 4
Stack elements:
10
STACK MENU
1. Push
2. Pop
3. Peek
4. Display
5. Exit
Enter your choice: 5
Program terminated
2.b. Queue Abstract Data Type (ADT) using a Singly Linked List
Aim
To implement the Queue Abstract Data Type (ADT) using
a Singly
Linked List and perform enqueue and dequeue operations.
Algorithm
1.
Start
the program.
2.
Create
a node with data and next pointer.
3.
Initialize
front and rear as NULL.
4.
Enqueue:
Insert a new node at the rear.
5.
Dequeue:
Delete the node from the front.
6.
Display
queue elements.
7.
Repeat
until exit.
8.
Stop.
# Queue ADT using Singly Linked List
class Node:
def
__init__(self, data):
self.data = data
self.next = None
front = None
# front of the queue
rear = None
# rear of the queue
while True:
print("\nQUEUE MENU")
print("1. Enqueue")
print("2. Dequeue")
print("3. Display")
print("4. Exit")
choice = int(input("Enter your choice: "))
#
Enqueue operation
if
choice == 1:
item = int(input("Enter element to insert: "))
new_node = Node(item)
if rear is None:
front = rear = new_node
else:
rear.next = new_node
rear = new_node
print("Element inserted")
#
Dequeue operation
elif choice == 2:
if front is None:
print("Queue Underflow")
else:
print("Deleted element:", front.data)
front = front.next
if front is None:
rear = None
#
Display queue
elif choice == 3:
if front is None:
print("Queue is empty")
else:
temp = front
print("Queue elements:", end=" ")
while temp:
print(temp.data, end="
")
temp = temp.next
print()
#
Exit
elif choice == 4:
print("Program terminated")
break
else:
print("Invalid choice")
OUTPUT:
QUEUE MENU
1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter your choice: 1
Enter element to insert: 100
Element inserted
QUEUE MENU
1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter your choice: 1
Enter element to insert: 200
Element inserted
QUEUE MENU
1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter your choice: 3
Queue elements: 100 200
QUEUE MENU
1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter your choice: 2
Deleted element: 100
QUEUE MENU
1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter your choice: 3
Queue elements: 200
QUEUE MENU
1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter your choice: 4
Program terminated
Result:
Thus, the above program has been executed
successfully.
3. Infix to Postfix Conversion and
Evaluation using Stack ADT
Aim
To read an infix expression, convert it into postfix expression,
and then evaluate
the postfix expression using a stack.
Algorithm
Step 1: Convert Infix to Postfix
1.
Initialize
an empty stack and an empty postfix string.
2.
Scan
the infix expression from left to right.
3.
If operand, append it to the postfix string.
4.
If '(', push it onto the stack.
5.
If ')', pop and append operators from stack
until '(' is encountered; discard '('.
6.
*If operator (+, -, , /), pop operators from stack with higher or equal precedence
and append to postfix, then push current operator.
7.
After
scanning, pop any remaining operators from the stack and append to postfix.
Step 2: Evaluate Postfix Expression
1.
Initialize
an empty stack.
2.
Scan
the postfix expression from left to right.
3.
If operand, push it onto the stack.
4.
If operator, pop two operands from the stack,
perform the operation, and push the result back.
5.
After
scanning, the stack will contain the final result.
# Infix to Postfix Conversion and Evaluation
def precedence(op):
if op in
'+-':
return
1
if op in
'*/':
return
2
return 0
# Convert infix to postfix
def infix_to_postfix(exp):
stack = []
postfix =
""
for ch in
exp:
if
ch.isalnum(): # Operand (digit or
letter)
postfix
+= ch
elif ch
== '(':
stack.append(ch)
elif ch
== ')':
while stack and stack[-1] != '(':
postfix += stack.pop()
stack.pop()
else: # Operator
while
stack and precedence(stack[-1]) >= precedence(ch):
postfix += stack.pop()
stack.append(ch)
while
stack:
postfix
+= stack.pop()
return
postfix
# Evaluate postfix
def eval_postfix(postfix, values):
stack = []
for ch in
postfix:
if
ch.isalpha(): # Operand letter
stack.append(values[ch])
else: # Operator
b =
stack.pop()
a =
stack.pop()
if
ch == '+': stack.append(a+b)
elif ch == '-': stack.append(a-b)
elif ch == '*': stack.append(a*b)
elif ch == '/': stack.append(a//b)
return
stack.pop()
# Main Program
expr = input("Enter infix expression (use
letters or digits): ")
postfix = infix_to_postfix(expr)
print("Postfix Expression:", postfix)
# Collect operand values if letters are used
values = {}
for ch in postfix:
if
ch.isalpha() and ch not in values:
values[ch] = int(input(f"Enter value for {ch}: "))
result = eval_postfix(postfix, values)
print("Evaluated Result:", result)
OUTPUT:
Enter infix expression (use letters or digits):
a+b*c-d
Postfix Expression: abc*+d-
Enter value for a: 3
Enter value for b: 4
Enter value for c: 2
Enter value for d: 3
Evaluated Result: 8
Thus, the above program has been executed
successfully.
4. Priority Queue
Abstract Data Type (ADT)
Aim
To implement the Priority Queue Abstract Data Type (ADT)
and perform insertion, deletion, and display operations.
Algorithm
1.
Start
the program.
2.
Create
an empty list for the priority queue.
3.
Insert
element along with its priority.
4.
Sort
the queue based on priority.
5.
Delete
the element with highest priority.
6.
Display
all elements.
7.
Repeat
until exit.
8.
Stop.
# Priority Queue ADT using list
pq = []
# empty priority queue
while True:
print("\nPRIORITY QUEUE MENU")
print("1. Insert")
print("2. Delete (Highest Priority)")
print("3. Display")
print("4. Exit")
ch
= int(input("Enter your choice: "))
#
Insert element with priority
if
ch == 1:
item = int(input("Enter element: "))
priority = int(input("Enter priority (lower value = higher
priority): "))
pq.append((priority, item))
print("Element inserted")
#
Delete highest priority element
elif ch == 2:
if len(pq) == 0:
print("Priority Queue is empty")
else:
pq.sort() # sort
based on priority
p, item = pq.pop(0) # remove
highest priority element
print("Deleted element:", item)
#
Display queue
elif ch == 3:
if len(pq) == 0:
print("Priority Queue is empty")
else:
print("Priority Queue
elements:")
for p, item in pq:
print("Element:",
item, "Priority:", p)
elif ch == 4:
print("Program terminated")
break
else:
print("Invalid choice")
OUTPUT:
PRIORITY QUEUE MENU
1. Insert
2. Delete (Highest Priority)
3. Display
4. Exit
Enter your choice: 1
Enter element: 300
Enter priority (lower value = higher
priority): 2
Element inserted
PRIORITY QUEUE MENU
1. Insert
2. Delete (Highest Priority)
3. Display
4. Exit
Enter your choice: 1
Enter element: 200
Enter priority (lower value = higher
priority): 3
Element inserted
PRIORITY QUEUE MENU
1. Insert
2. Delete (Highest Priority)
3. Display
4. Exit
Enter your choice: 1
Enter element: 100
Enter priority (lower value = higher
priority): 1
Element inserted
PRIORITY QUEUE MENU
1. Insert
2. Delete (Highest Priority)
3. Display
4. Exit
Enter your choice: 3
Priority Queue elements:
Element: 300 Priority: 2
Element: 200 Priority: 3
Element: 100 Priority: 1
PRIORITY QUEUE MENU
1. Insert
2. Delete (Highest Priority)
3. Display
4. Exit
Enter your choice: 2
Deleted element: 100
PRIORITY QUEUE MENU
1. Insert
2. Delete (Highest Priority)
3. Display
4. Exit
Enter your choice: 2
Deleted element: 300
PRIORITY QUEUE MENU
1. Insert
2. Delete (Highest Priority)
3. Display
4. Exit
Enter your choice: 3
Priority Queue elements:
Element: 200 Priority: 3
PRIORITY QUEUE MENU
1. Insert
2. Delete (Highest Priority)
3. Display
4. Exit
Enter your choice: 4
Program terminated
Result:
Thus, the above program has been executed successfully.
5. Binary Search Tree (BST)
AIM
To write a Python program to implement a Binary Search Tree (BST) and perform the operations
insertion, deletion, and searching of elements.
ALGORITHM
1. Start the program.
2. Create a node with data, left and right pointers.
3. Create a Binary Search Tree with root as NULL.
4. Read the user’s choice (insert / search / delete).
5. If the choice is insert,
o Compare the element with current node.
o If smaller, move to left child.
o If greater, move to right child.
o Insert the element at the correct position.
6. If the choice is search,
o Compare the element with current node.
o If equal, element is found.
o If smaller, go to left child.
o If greater, go to right child.
7. If the choice is delete,
o Find the node to be deleted.
o If it has no child, delete it.
o If it has one child, replace it with its child.
o If it has two children, replace it with the smallest value in the right subtree and delete that node.
8. Repeat the above steps until exit is selected.
9. Stop the program.
# Binary Search Tree implementation in Python
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
class BinarySearchTree:
def __init__(self):
self.root = None
# Insert a node
def insert(self, root, key):
if root is None:
return Node(key)
if key < root.key:
root.left = self.insert(root.left, key)
elif key > root.key:
root.right = self.insert(root.right, key)
return root
# Search a node
def search(self, root, key):
if root is None:
return False
if root.key == key:
return True
elif key < root.key:
return self.search(root.left, key)
else:
return self.search(root.right, key)
# Find minimum value node
def find_min(self, root):
while root.left is not None:
root = root.left
return root
# Delete a node
def delete(self, root, key):
if root is None:
return root
if key < root.key:
root.left = self.delete(root.left, key)
elif key > root.key:
root.right = self.delete(root.right, key)
else:
# Case 1: No child
if root.left is None and root.right is None:
return None
# Case 2: One child
elif root.left is None:
return root.right
elif root.right is None:
return root.left
# Case 3: Two children
temp = self.find_min(root.right)
root.key = temp.key
root.right = self.delete(root.right, temp.key)
return root
# Inorder traversal
def inorder(self, root):
if root:
self.inorder(root.left)
print(root.key, end=" ")
self.inorder(root.right)
# Main Program
bst = BinarySearchTree()
while True:
print("\n1.Insert\n2.Delete\n3.Search\n4.Display (Inorder)\n5.Exit")
choice = int(input("Enter your choice: "))
if choice == 1:
key = int(input("Enter element to insert: "))
bst.root = bst.insert(bst.root, key)
elif choice == 2:
key = int(input("Enter element to delete: "))
bst.root = bst.delete(bst.root, key)
elif choice == 3:
key = int(input("Enter element to search: "))
if bst.search(bst.root, key):
print("Element found in BST")
else:
print("Element not found in BST")
elif choice == 4:
print("Inorder Traversal:")
bst.inorder(bst.root)
print()
elif choice == 5:
print("Exiting...")
break
else:
print("Invalid choice!")
OUTPUT:
1.Insert
2.Delete
3.Search
4.Display (Inorder)
5.Exit
Enter your choice: 1
Enter element to insert: 20
1.Insert
2.Delete
3.Search
4.Display (Inorder)
5.Exit
Enter your choice: 1
Enter element to insert: 10
1.Insert
2.Delete
3.Search
4.Display (Inorder)
5.Exit
Enter your choice: 1
Enter element to insert: 30
1.Insert
2.Delete
3.Search
4.Display (Inorder)
5.Exit
Enter your choice: 4
Inorder Traversal:
10 20 30
1.Insert
2.Delete
3.Search
4.Display (Inorder)
5.Exit
Enter your choice: 3
Enter element to search: 20
Element found in BST
1.Insert
2.Delete
3.Search
4.Display (Inorder)
5.Exit
Enter your choice: 3
Enter element to search: 40
Element not found in BST
1.Insert
2.Delete
3.Search
4.Display (Inorder)
5.Exit
Enter your choice: 2
Enter element to delete: 10
1.Insert
2.Delete
3.Search
4.Display (Inorder)
5.Exit
Enter your choice: 4
Inorder Traversal:
20 30
1.Insert
2.Delete
3.Search
4.Display (Inorder)
5.Exit
Enter your choice: 5
Exiting...
1. AVL Tree
Aim
To implement an AVL Tree and perform insertion and deletion
while maintaining the balanced property of the tree.
Algorithm
Insertion
1. Insert the element like in a Binary
Search Tree.
2. Update the height of each node.
3. Find the balance factor of the node.
4. If unbalanced, perform the required
rotation:
o
Left-Left
→ Right rotate
o
Right-Right
→ Left rotate
o
Left-Right
→ Left rotate then Right rotate
o
Right-Left
→ Right rotate then Left rotate
Deletion
1. Delete the element as in a Binary
Search Tree.
2. Update the height of the node.
3. Find the balance factor.
4. If unbalanced, perform suitable
rotation to balance the tree.
# Short AVL Tree
Program (Insert + Delete)
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
self.height = 1
def height(n):
return n.height if n else 0
def balance(n):
return height(n.left) - height(n.right) if
n else 0
def rightRotate(y):
x = y.left
T2 = x.right
x.right = y
y.left = T2
y.height = 1 + max(height(y.left),
height(y.right))
x.height = 1 + max(height(x.left),
height(x.right))
return x
def leftRotate(x):
y = x.right
T2 = y.left
y.left = x
x.right = T2
x.height = 1 + max(height(x.left),
height(x.right))
y.height = 1 + max(height(y.left),
height(y.right))
return y
def insert(root,
key):
if not root:
return Node(key)
if key < root.key:
root.left = insert(root.left, key)
else:
root.right = insert(root.right, key)
root.height = 1 + max(height(root.left),
height(root.right))
b = balance(root)
if b > 1 and key < root.left.key:
return rightRotate(root)
if b < -1 and key > root.right.key:
return leftRotate(root)
if b > 1 and key > root.left.key:
root.left = leftRotate(root.left)
return rightRotate(root)
if b < -1 and key < root.right.key:
root.right = rightRotate(root.right)
return leftRotate(root)
return root
def
minValueNode(node):
while node.left:
node = node.left
return node
def delete(root,
key):
if not root:
return root
if key < root.key:
root.left = delete(root.left, key)
elif key > root.key:
root.right = delete(root.right, key)
else:
if not root.left:
return root.right
if not root.right:
return root.left
temp = minValueNode(root.right)
root.key = temp.key
root.right = delete(root.right,
temp.key)
root.height = 1 + max(height(root.left),
height(root.right))
b = balance(root)
if b > 1 and balance(root.left) >= 0:
return rightRotate(root)
if b > 1 and balance(root.left) < 0:
root.left = leftRotate(root.left)
return rightRotate(root)
if b < -1 and balance(root.right) <=
0:
return leftRotate(root)
if b < -1 and balance(root.right) >
0:
root.right = rightRotate(root.right)
return leftRotate(root)
return root
def inorder(root):
if root:
inorder(root.left)
print(root.key, end=" ")
inorder(root.right)
# Main
root = None
while True:
print("\n1.Insert 2.Delete
3.Display 4.Exit")
ch = int(input("Enter choice: "))
if ch == 1:
x = int(input("Enter element:
"))
root = insert(root, x)
elif ch == 2:
x = int(input("Enter element to
delete: "))
root = delete(root, x)
elif ch == 3:
inorder(root)
print()
elif ch == 4:
break
else:
print("Invalid choice")
OUTPUT:
1.Insert 2.Delete
3.Display 4.Exit
Enter choice: 1
Enter element: 10
1.Insert 2.Delete
3.Display 4.Exit
Enter choice: 1
Enter element: 20
1.Insert 2.Delete
3.Display 4.Exit
Enter choice: 1
Enter element: 30
1.Insert 2.Delete
3.Display 4.Exit
Enter choice: 3
10 20 30
1.Insert 2.Delete
3.Display 4.Exit
Enter choice: 2
Enter element to
delete: 20
1.Insert 2.Delete
3.Display 4.Exit
Enter choice: 3
10 30
1.Insert 2.Delete
3.Display 4.Exit
Enter choice: 4
=== Code Execution
Successful ===
Result
Thus, the AVL Tree
operations are performed successfully and the tree remains balanced.
2. BFS and DFS for a Graph
Aim
To write a Python program to perform Breadth First Search (BFS) and
Depth First Search (DFS) for a given
graph.
Algorithm
BFS Algorithm
1. Initialize an empty queue and visited
list.
2. Insert the starting node into the
queue and mark it visited.
3. Remove a node from the queue and
display it.
4. Insert all unvisited adjacent nodes
into the queue and mark them visited.
5. Repeat steps 3–4 until the queue is
empty.
6.
DFS Algorithm
1. Initialize an empty visited list.
2. Start from the given node and mark it
visited.
3. Visit each unvisited adjacent node
recursively.
4. Repeat until all nodes are visited.
# BFS and DFS using adjacency list
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': [],
'F': []
}
# BFS Function
def bfs(start):
visited = []
queue = []
queue.append(start)
visited.append(start)
print("BFS Traversal:", end=" ")
while queue:
node = queue.pop(0)
print(node, end=" ")
for i in graph[node]:
if i not in visited:
visited.append(i)
queue.append(i)
print()
# DFS Function
def dfs(start):
visited = []
print("DFS Traversal:", end=" ")
def
dfs_visit(node):
visited.append(node)
print(node, end=" ")
for i in graph[node]:
if i not in visited:
dfs_visit(i)
dfs_visit(start)
print()
# Main
bfs('A')
dfs('A')
OUTPUT:
BFS Traversal: A B C D E F
DFS Traversal: A B D E C F
Result:
Thus, the above program has been executed
successfully.
8.a. Linear Search
Aim
To write a Python program to search
an element in a list using Linear Search technique.
Algorithm
1.
Start
the program.
2. Read the number of elements and store
them in a list.
3. Read the element to be searched.
4. Compare the search element with each
element of the list one by one.
5. If a match is found, display the
position.
6. If no match is found after checking
all elements, display “Element not found”.
7. Stop the program.
# Linear Search Program
L = []
n = int(input("Enter number of elements:
"))
for i in range(n):
L.append(int(input("Enter element: ")))
key = int(input("Enter element to
search: "))
found = False
for i in range(n):
if
L[i] == key:
print("Element found at position", i+1)
found = True
break
if not found:
print("Element not found")
OUTPUT:
Enter number of elements: 5
Enter element: 10
Enter element: 20
Enter element: 30
Enter element: 40
Enter element: 50
Enter element to search: 30
Element found at position 3
8.b. Binary Search
Aim
To write a Python program to search an element in a list
using the Binary Search technique.
Algorithm
1.
Start
the program.
2. Read n elements and store them
in a list.
3. Sort the list.
4. Read the search element (key).
5. Set low = 0 and high = n - 1.
6. Find mid = (low + high) // 2.
7. If list[mid] == key, display
position and stop.
8. If key < list[mid], set high = mid - 1.
9. Else set low = mid + 1.
10. Repeat steps 6–9 until low > high.
11. If not found, display “Element not
found”.
12. Stop.
L = []
n = int(input("Enter number of elements:
"))
for i in range(n):
L.append(int(input("Enter element: ")))
L.sort()
# Binary search works only on sorted list
print("Sorted list:", L)
key = int(input("Enter element to
search: "))
low = 0
high = n - 1
found = False
while low <= high:
mid
= (low + high) // 2
if
L[mid] == key:
print("Element found at position", mid+1)
found = True
break
elif key < L[mid]:
high = mid - 1
else:
low = mid + 1
if not found:
print("Element not found")
OUTPUT:
Enter number of elements: 6
Enter element: 1
Enter element: 2
Enter element: 3
Enter element: 4
Enter element: 5
Enter element: 6
Sorted list: [1, 2, 3, 4, 5, 6]
Enter element to search: 6
Element found at position 6
Result
Thus, the above
program has been executed successfully.
9.a. Bubble Sort
Aim
To write a Python program to sort a list of elements
using the Bubble Sort technique.
Algorithm
1.
Start
the program.
2. Read n elements into a list.
3. Compare adjacent elements.
4. Swap them if they are in the wrong
order.
5. Repeat steps 3 and 4 for all passes.
6. Display the sorted list.
7. Stop.
# Bubble Sort Program
n = int(input("Enter number of elements:
"))
arr = []
for i in range(n):
arr.append(int(input("Enter element: ")))
# Bubble Sort Logic
for i in range(n-1):
for
j in range(n-1-i):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
print("Sorted list:", arr)
OUTPUT:
Enter number of elements: 5
Enter element: 3
Enter element: 6
Enter element: 7
Enter element: 1
Enter element: 4
Sorted list: [1, 3, 4, 6, 7]
9.b. Selection Sort
Aim
To write a Python program to sort a list of elements
using the Selection Sort technique.
Algorithm
1.
Start
the program.
2. Read n elements into a list.
3. Find the smallest element in the list.
4. Swap it with the first element.
5. Repeat for the remaining elements.
6. Display the sorted list.
7. Stop.
# Selection Sort Program
n = int(input("Enter number of elements:
"))
arr = []
for i in range(n):
arr.append(int(input("Enter element: ")))
# Selection Sort Logic
for i in range(n-1):
min_index = i
for
j in range(i+1, n):
if arr[j] < arr[min_index]:
min_index = j
arr[i], arr[min_index] = arr[min_index], arr[i]
print("Sorted list:", arr)
OUTPUT:
Enter number of elements: 5
Enter element: 3
Enter element: 9
Enter element: 6
Enter element: 1
Enter element: 7
Sorted list: [1, 3, 6, 7, 9]
9.c. Insertion Sort
Aim
To write a Python program to sort a list of elements
using the Insertion Sort technique.
Algorithm
1.
Start
the program.
2. Read n elements into a list.
3. Take the second element and compare it
with the first.
4. Insert it in the correct position.
5. Repeat the process for all elements.
6. Display the sorted list.
7. Stop.
# Insertion Sort Program
n = int(input("Enter number of elements:
"))
arr = []
for i in range(n):
arr.append(int(input("Enter element: ")))
# Insertion Sort Logic
for i in range(1, n):
key
= arr[i]
j =
i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
print("Sorted list:", arr)
Enter number of elements: 5
Enter element: 6
Enter element: 8
Enter element: 4
Enter element: 2
Enter element: 10
Sorted list: [2, 4, 6, 8, 10]
9.d. Radix Sort
Aim
To write a Python program to sort a list of elements
using the Radix Sort technique.
Algorithm
1.
Start
the program.
2. Read n elements into a list.
3. Find the largest number to know the
number of digits.
4. Sort the elements digit by digit
starting from the least significant digit (LSD).
5. Use counting sort for each digit
position.
6. Repeat until all digit positions are
processed.
7. Display the sorted list.
8. Stop.
# Radix Sort Program
def counting_sort(arr, exp):
n =
len(arr)
output = [0] * n
count = [0] * 10
for
i in range(n):
index = (arr[i] // exp) % 10
count[index] += 1
for
i in range(1, 10):
count[i] += count[i - 1]
i =
n - 1
while i >= 0:
index = (arr[i] // exp) % 10
output[count[index] - 1] = arr[i]
count[index] -= 1
i -= 1
for
i in range(n):
arr[i] = output[i]
def radix_sort(arr):
max_num = max(arr)
exp
= 1
while max_num // exp > 0:
counting_sort(arr, exp)
exp *= 10
# Main Program
n = int(input("Enter number of elements:
"))
arr = []
for i in range(n):
arr.append(int(input("Enter element: ")))
radix_sort(arr)
print("Sorted list:", arr)
OUTPUT:
Enter number of elements: 5
Enter element: 3
Enter element: 9
Enter element: 6
Enter element: 1
Enter element: 11
Sorted list: [1, 3, 6, 9, 11]
Thus, the given
list is sorted successfully
Comments
Post a Comment