Ex1.
1:program to implement the List ADT using arrays
global a
a=[]
def Refresh_len():
global l
l=len(a)
def Create():
Refresh_len()
n=int(input("Give the number of elements"))
for i in range(0,n):
d=int(input("Give the next element"))
a.append(d)
print(l)
print(a)
def Insert():
p=int(input("Give the position of the element to be inserted"))
d=int(input("Give the element to be inserted"))
a.append('\0')
Refresh_len()
for i in range(l-1,p-1,-1):
a[i]=a[i-1]
a[p]=d
print(a)
def Delet():
p=int(input("Give the position of the element to be deleted"))
for i in range(p+1,l):
a[i-1]=a[i]
a.pop()
Refresh_len()
print(a)
def Traverse():
for i in range(0,l):
print(a[i])
Create()
Insert()
Delet()
Traverse()
Output:
Give the number of elements4
Give the next element5
Give the next element6
Give the next element7
Give the next element8
[5, 6, 7, 8]
Give the position of the element to be inserted2
Give the element to be inserted3
[5, 6, 3, 7, 8]
Give the position of the element to be deleted2
[5, 6, 7, 8]
8
Ex1.2:Write a program to implement the List ADT using linked lists.
# Create a Node class to create a node
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def insertAtBegin(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
return
else:
new_node.next = self.head
self.head = new_node
def insertAtIndex(self, data, index):
new_node = Node(data)
current_node = self.head
position = 0
if position == index:
self.insertAtBegin(data)
else:
while(current_node != None and position+1 != index):
position = position+1
current_node = current_node.next
if current_node != None:
new_node.next = current_node.next
current_node.next = new_node
else:
print("Index not present")
def insertAtEnd(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
return
current_node = self.head
while(current_node.next):
current_node = current_node.next
current_node.next = new_node
def updateNode(self, val, index):
current_node = self.head
position = 0
if position == index:
current_node.data = val
else:
while(current_node != None and position != index):
position = position+1
current_node = current_node.next
if current_node != None:
current_node.data = val
else:
print("Index not present")
def remove_first_node(self):
if(self.head == None):
return
self.head = self.head.next
def remove_last_node(self):
if self.head is None:
return
current_node = self.head
while(current_node.next.next):
current_node = current_node.next
current_node.next = None
def remove_at_index(self, index):
if self.head == None:
return
current_node = self.head
position = 0
if position == index:
self.remove_first_node()
else:
while(current_node != None and position+1 != index):
position = position+1
current_node = current_node.next
if current_node != None:
current_node.next = current_node.next.next
else:
print("Index not present")
def remove_node(self, data):
current_node = self.head
if current_node.data == data:
self.remove_first_node()
return
while(current_node != None and current_node.next.data != data):
current_node = current_node.next
if current_node == None:
return
else:
current_node.next = current_node.next.next
def sizeOfLL(self):
size = 0
if(self.head):
current_node = self.head
while(current_node):
size = size+1
current_node = current_node.next
return size
else:
return 0
def printLL(self):
current_node = self.head
while(current_node):
print(current_node.data)
current_node = current_node.next
llist = LinkedList()
llist.insertAtEnd('a')
llist.insertAtEnd('b')
llist.insertAtBegin('c')
llist.insertAtEnd('d')
llist.insertAtIndex('g', 2)
print("Node Data")
llist.printLL()
print("\nRemove First Node")
llist.remove_first_node()
print("Remove Last Node")
llist.remove_last_node()
print("Remove Node at Index 1")
llist.remove_at_index(1)
print("\nLinked list after removing a node:")
llist.printLL()
print("\nUpdate node Value")
llist.updateNode('z', 0)
llist.printLL()
print("\nSize of linked list :", end=" ")
print(llist.sizeOfLL())
Output:
Node Data
Remove First Node
Remove Last Node
Remove Node at Index 1
Linked list after removing a node:
Update node Value
Size of linked list : 2
Ex2.1 program to implement the Stack ADT using a singly linked list.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class Stack:
def __init__(self):
self.head = None
def push(self, data):
if self.head is None:
self.head = Node(data)
else:
new_node = Node(data)
new_node.next = self.head
self.head = new_node
def pop(self):
if self.head is None:
return None
else:
popped = self.head.data
self.head = self.head.next
return popped
def display(self):
iternode = self.head
while(iternode != None):
print(iternode.data, end = "")
iternode = iternode.next
if(iternode != None):
print(" -> ", end = "")
print()
return
a_stack = Stack()
while True:
print()
print('1.push <value>')
print('2.pop')
print('3.Display')
print('4.quit')
do = int(input('What would you like to do? '))
if do == 1:
e=int(input("Get the value to be pushed"))
a_stack.push(int(e))
elif do == 2:
popped = a_stack.pop()
if popped is None:
print('Stack is empty.')
else:
print('Popped value: ', int(popped))
elif do==3:
a_stack.display()
elif do == 4:
break
Output:
1.push <value>
2.pop
3.Display
4.quit
What would you like to do? 1
Get the value to be pushed23
1.push <value>
2.pop
3.Display
4.quit
What would you like to do? 1
Get the value to be pushed45
1.push <value>
2.pop
3.Display
4.quit
What would you like to do? 1
Get the value to be pushed56
1.push <value>
2.pop
3.Display
4.quit
What would you like to do? 1
Get the value to be pushed78
1.push <value>
2.pop
3.Display
4.quit
What would you like to do? 2
Popped value: 78
1.push <value>
2.pop
3.Display
4.quit
What would you like to do? 3
56 ->
45 ->
23
1.push <value>
2.pop
3.Display
4.quit
What would you like to do?
Ex2.2 program to implement the Queue ADT using a singly linked list.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class Queue:
def __init__(self):
self.front = self.rear = None
def isEmpty(self):
return self.front == None
def EnQueue(self, item):
temp = Node(item)
if self.rear == None:
self.front = self.rear = temp
return
self.rear.next = temp
self.rear = temp
def DeQueue(self):
if self.isEmpty():
return
temp = self.front
self.front = temp.next
if(self.front == None):
self.rear = None
if __name__ == '__main__':
print()
q = Queue()
c='e'
while (c=='e' or c=='d' or c=='s'):
if c=='e':
d=int(input('Give data to enqueue'))
q.EnQueue(d)
elif c=='d':
q.DeQueue()
elif c=='s':
print("Queue Front : " + str(q.front.data if q.front != None else -1))
print("Queue Rear : " + str(q.rear.data if q.rear != None else -1))
c=input('Type "e" to enqueue or "d" for dequeue or "s" to show')
Output:
Give data to enqueue34
Type "e" to enqueue or "d" for dequeue or "s" to showe
Give data to enqueue45
Type "e" to enqueue or "d" for dequeue or "s" to showe
Give data to enqueue67
Type "e" to enqueue or "d" for dequeue or "s" to shows
Queue Front : 34
Queue Rear : 67
Type "e" to enqueue or "d" for dequeue or "s" to showd
Type "e" to enqueue or "d" for dequeue or "s" to shows
Queue Front : 45
Queue Rear : 67
Type "e" to enqueue or "d" for dequeue or "s" to show
Ex3: program that reads an infix expression, converts the expression to postfix form
and then evaluates the postfix expression using stack ADT.
def prec(c):
if c == '^':
return 3
elif c == '/' or c == '*':
return 2
elif c == '+' or c == '-':
return 1
else:
return -1
def associativity(c):
if c == '^':
return 'R'
return 'L' # Default to left-associative
def infix_to_postfix(s):
result = []
stack = []
for i in range(len(s)):
c = s[i]
# If the scanned character is an operand, add it to the output string.
if ('a' <= c <= 'z') or ('A' <= c <= 'Z') or ('0' <= c <= '9'):
result.append(c)
# If the scanned character is an ‘(‘, push it to the stack.
elif c == '(':
stack.append(c)
elif c == ')':
while stack and stack[-1] != '(':
result.append(stack.pop())
stack.pop() # Pop '('
# If an operator is scanned
else:
while stack and (prec(s[i]) < prec(stack[-1]) or
(prec(s[i]) == prec(stack[-1]) and associativity(s[i]) == 'L')):
result.append(stack.pop())
stack.append(c)
# Pop all the remaining elements from the stack
while stack:
result.append(stack.pop())
print(''.join(result))
exp=input('Give your expression')
# Function call
infix_to_postfix(exp)
Output:
Give your expressiona+3-d*(9-b)
a3+d9b-*-
Ex4: program to implement priority queue ADT.
class PriorityQueue(object):
def __init__(self):
self.queue = []
def __str__(self):
return ' '.join([str(i) for i in self.queue])
# for checking if the queue is empty
def isEmpty(self):
return len(self.queue) == 0
# for inserting an element in the queue
def insert(self, data):
self.queue.append(data)
# for popping an element based on Priority
def delete(self):
try:
max_val = 0
for i in range(len(self.queue)):
if self.queue[i] > self.queue[max_val]:
max_val = i
item = self.queue[max_val]
del self.queue[max_val]
return item
except IndexError:
print()
exit()
if __name__ == '__main__':
myQueue = PriorityQueue()
for i in range(0,5):
p=int(input('Get the priority'))
myQueue.insert(p)
print(myQueue)
while not myQueue.isEmpty():
print(myQueue.delete())
Output:
Get the priority4
Get the priority5
Get the priority2
Get the priority3
Get the priority1
45231
5
4
3
2
1
Ex5.1: Program to Insert an element into a binary search tree and Delete an element
from the binary search tree.
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
def inorder(root):
if root is not None:
inorder(root.left)
print(root.key, end=' ')
inorder(root.right)
def insert(node, key):
# If the tree is empty, return a new node
if node is None:
return Node(key)
# Otherwise, recur down the tree
if key < node.key:
node.left = insert(node.left, key)
else:
node.right = insert(node.right, key)
# return the (unchanged) node pointer
return node
def deleteNode(root, k):
# Base case
if root is None:
return root
if root.key > k:
root.left = deleteNode(root.left, k)
return root
elif root.key < k:
root.right = deleteNode(root.right, k)
return root
# If one of the children is empty
if root.left is None:
temp = root.right
del root
return temp
elif root.right is None:
temp = root.left
del root
return temp
# If both children exist
else:
succParent = root
# Find successor
succ = root.right
while succ.left is not None:
succParent = succ
succ = succ.left
if succParent != root:
succParent.left = succ.right
else:
succParent.right = succ.right
# Copy Successor Data to root
root.key = succ.key
# Delete Successor and return root
del succ
return root
# Driver Code
if __name__ == '__main__':
root = None
root = insert(root, 50)
root = insert(root, 30)
root = insert(root, 20)
root = insert(root, 40)
root = insert(root, 70)
root = insert(root, 60)
print("Original BST: ", end='')
inorder(root)
print("\n\nDelete a Leaf Node: 20")
root = deleteNode(root, 20)
print("Modified BST tree after deleting Leaf Node:")
inorder(root)
print("\n\nDelete Node with single child: 70")
root = deleteNode(root, 70)
print("Modified BST tree after deleting single child Node:")
inorder(root)
print("\n\nDelete Node with both child: 50")
root = deleteNode(root, 50)
print("Modified BST tree after deleting both child Node:")
inorder(root)
Output:
Original BST: 20 30 40 50 60 70
Delete a Leaf Node: 20
Modified BST tree after deleting Leaf Node:
30 40 50 60 70
Delete Node with single child: 70
Modified BST tree after deleting single child Node:
30 40 50 60
Delete Node with both child: 50
Modified BST tree after deleting both child Node:
30 40 60
Ex5.2 Program to Search for a key element in a binary search tree.
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
def insert(node, key):
if node is None:
return Node(key)
if key < node.key:
node.left = insert(node.left, key)
elif key > node.key:
node.right = insert(node.right, key)
return node
def search(root, key):
if root is None or root.key == key:
return root
if root.key < key:
return search(root.right, key)
return search(root.left, key)
# Driver Code
if __name__ == '__main__':
root = None
r=int(input('Get Root value'))
root = insert(root, r)
for i in range(0,6):
d=int(input('Get data'))
insert(root, d)
key = int(input('Get value to be searched'))
if search(root, key) is None:
print(key, "not found")
else:
print(key, "found")
Output 1:
Get Root value56
Get data23
Get data45
Get data78
Get data67
Get data45
Get data23
Get value to be searched11
11 not found
Output 2:
Get Root value34
Get data56
Get data23
Get data78
Get data90
Get data12
Get data34
Get value to be searched78
78 found
Ex6.1 program to perform the Insertion and Deletion from an AVL-tree
class TreeNode(object):
def __init__(self, val):
self.val = val
self.left = None
self.right = None
self.height = 1
class AVL_Tree(object):
def insert(self, root, key):
if not root:
return TreeNode(key)
elif key < root.val:
root.left = self.insert(root.left, key)
else:
root.right = self.insert(root.right, key)
root.height = 1 + max(self.getHeight(root.left),
self.getHeight(root.right))
balance = self.getBalance(root)
if balance > 1 and key < root.left.val:
return self.rightRotate(root)
if balance < -1 and key > root.right.val:
return self.leftRotate(root)
if balance > 1 and key > root.left.val:
root.left = self.leftRotate(root.left)
return self.rightRotate(root)
if balance < -1 and key < root.right.val:
root.right = self.rightRotate(root.right)
return self.leftRotate(root)
return root
def delete(self, root, key):
if not root:
return root
elif key < root.val:
root.left = self.delete(root.left, key)
elif key > root.val:
root.right = self.delete(root.right, key)
else:
if root.left is None:
temp = root.right
root = None
return temp
elif root.right is None:
temp = root.left
root = None
return temp
temp = self.getMinValueNode(root.right)
root.val = temp.val
root.right = self.delete(root.right, temp.val)
if root is None:
return root
root.height = 1 + max(self.getHeight(root.left),self.getHeight(root.right))
balance = self.getBalance(root)
if balance > 1 and self.getBalance(root.left) >= 0:
return self.rightRotate(root)
if balance < -1 and self.getBalance(root.right) <= 0:
return self.leftRotate(root)
if balance > 1 and self.getBalance(root.left) < 0:
root.left = self.leftRotate(root.left)
return self.rightRotate(root)
if balance < -1 and self.getBalance(root.right) > 0:
root.right = self.rightRotate(root.right)
return self.leftRotate(root)
return root
def leftRotate(self, z):
y = z.right
T2 = y.left
y.left = z
z.right = T2
z.height = 1 + max(self.getHeight(z.left), self.getHeight(z.right))
y.height = 1 + max(self.getHeight(y.left), self.getHeight(y.right))
return y
def rightRotate(self, z):
y = z.left
T3 = y.right
y.right = z
z.left = T3
z.height = 1 + max(self.getHeight(z.left), self.getHeight(z.right))
y.height = 1 + max(self.getHeight(y.left), self.getHeight(y.right))
return y
def getHeight(self, root):
if not root:
return 0
return root.height
def getBalance(self, root):
if not root:
return 0
return self.getHeight(root.left) - self.getHeight(root.right)
def getMinValueNode(self, root):
if root is None or root.left is None:
return root
return self.getMinValueNode(root.left)
def preOrder(self, root):
if not root:
return
print("{0} ".format(root.val), end="")
self.preOrder(root.left)
self.preOrder(root.right)
myTree = AVL_Tree()
root = None
nums = [9, 5, 10, 0, 6, 11, -1, 1, 2]
for num in nums:
root = myTree.insert(root, num)
print("Preorder Traversal after insertion -")
myTree.preOrder(root)
print()
key = 10
root = myTree.delete(root, key)
print("Preorder Traversal after deletion -")
myTree.preOrder(root)
print()
Output:
Preorder Traversal after insertion -
9 1 0 -1 5 2 6 10 11
Preorder Traversal after deletion -
1 0 -1 9 5 2 6 11
Ex7.1: Write a programs for the implementation DFS for a given graph.
from collections import defaultdict
class Graph:
def __init__(self):
self.graph = defaultdict(list)
def addEdge(self, u, v):
self.graph[u].append(v)
def DFSUtil(self, v, visited):
visited.add(v)
print(v, end=' ')
for neighbour in self.graph[v]:
if neighbour not in visited:
self.DFSUtil(neighbour, visited)
def DFS(self, v):
visited = set()
self.DFSUtil(v, visited)
# Driver's code
if __name__ == "__main__":
g = Graph()
g.addEdge(0, 1)
g.addEdge(0, 2)
g.addEdge(1, 2)
g.addEdge(2, 0)
g.addEdge(2, 3)
g.addEdge(3, 3)
print("Following is Depth First Traversal (starting from vertex 2)")
g.DFS(2)
Output:
Following is Depth First Traversal (starting from vertex 2)
2013
Ex7.2: Write a programs for the implementation BFS for a given graph.
from collections import defaultdict
class Graph:
def __init__(self):
self.graph = defaultdict(list)
def addEdge(self,u,v):
self.graph[u].append(v)
self.visited=[]
def BFS(self, s):
queue = []
queue.append(s)
self.visited.append(s)
while queue:
s = queue.pop(0)
print (s, end = " ")
for i in self.graph[s]:
if i not in self.visited:
queue.append(i)
self.visited.append(s)
g = Graph()
g.addEdge(0, 1)
g.addEdge(0, 2)
g.addEdge(1, 2)
g.addEdge(2, 0)
g.addEdge(2, 3)
g.addEdge(3, 3)
print ("Following is Breadth First Traversal"
" (starting from vertex 2)")
g.BFS(2)
Output:
Following is Breadth First Traversal (starting from vertex 2)
20313
Ex8.1: Write a programs for implementing the Linear search.
arr = [10, 20, 80, 30, 60, 50, 110, 100, 130, 170]
x = 110
def search(arr, x):
for i in range(len(arr)):
if arr[i] == x:
print('Element exists in ',i,'th index')
return
print('Element does not exist')
return
d= int(input('Give element to be searched'))
search(arr,d)
Output 1:
Give element to be searched 30
Element exists in 3 th index
Output 2:
Give element to be searched 22
Element does not exist
Ex8.2: Write a programs for implementing the Binary search.
def binary_search(arr, low, high, x):
# Check base case
if high >= low:
mid = (high + low) // 2
# If element is present at the middle itself
if arr[mid] == x:
return mid
elif arr[mid] > x:
return binary_search(arr, low, mid - 1, x)
# Else the element can only be present in right subarray
else:
return binary_search(arr, mid + 1, high, x)
else:
# Element is not present in the array
return -1
# Test array
arr = [ 2, 3, 4, 10, 40 ]
x = int(input('Get element to be searched'))
# Function call
result = binary_search(arr, 0, len(arr)-1, x)
if result != -1:
print("Element is present at index", str(result))
else:
print("Element is not present in array")
Output 1:
Get element to be searched 4
Element is present at index 2
Output 2:
Get element to be searched5
Element is not present in array
Ex9.1 : Write a programs for implementing the Insertion sort method
def insertionSort(arr):
n = len(arr)
if n <= 1:
return
for i in range(1, n):
key = arr[i]
j = i-1
while j >= 0 and key < arr[j]:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key
arr = [12, 11, 13, 5, 6]
print('Given array')
print(arr)
insertionSort(arr)
print('Sorted array')
print(arr)
Output:
Given array
[12, 11, 13, 5, 6]
Sorted array
[5, 6, 11, 12, 13]
Ex9.2 : Write a programs for implementing the Selection sort method
def selectionSort(array, size):
for ind in range(size):
min_index = ind
for j in range(ind + 1, size):
# select the minimum element in every iteration
if array[j] < array[min_index]:
min_index = j
# swapping the elements to sort the array
(array[ind], array[min_index]) = (array[min_index], array[ind])
arr = [-2, 45, 0, 11, -9,88,-97,-202,747]
print('The given array ')
print(arr)
size = len(arr)
selectionSort(arr, size)
print('The array after selection sort is:')
print(arr)
Output:
The given array
[-2, 45, 0, 11, -9, 88, -97, -202, 747]
The array after selection sort is:
[-202, -97, -9, -2, 0, 11, 45, 88, 747]
Ex9.3 : Write a programs for implementing the Bubble sort method
def bubbleSort(arr):
n = len(arr)
swapped = False
for i in range(n-1):
for j in range(0, n-i-1):
if arr[j] > arr[j + 1]:
swapped = True
arr[j], arr[j + 1] = arr[j + 1], arr[j]
if not swapped:
return
arr = [64, 34, 25, 12, 22, 11, 90]
print('Given Array is:')
print(arr)
bubbleSort(arr)
print("Sorted array is:")
for i in range(len(arr)):
print("% d" % arr[i], end=" ")
Output
Given Array is:
[64, 34, 25, 12, 22, 11, 90]
Sorted array is:
11 12 22 25 34 64 90
Ex9.4 : Write a programs for implementing the Radix sort method
def countingSort(arr, exp1):
n = len(arr)
output = [0] * (n)
count = [0] * (10)
for i in range(0, n):
index = (arr[i]/exp1)
count[int((index)%10)] += 1
for i in range(1,10):
count[i] += count[i-1]
i = n-1
while i>=0:
index = (arr[i]/exp1)
output[ count[ int((index)%10) ] - 1] = arr[i]
count[int((index)%10)] -= 1
i -= 1
i=0
for i in range(0,len(arr)):
arr[i] = output[i]
def radixSort(arr):
max1 = max(arr)
exp = 1
while max1 // exp > 0:
countingSort(arr,exp)
exp *= 10
arr = [ 170, 45, 75, 90, 802, 24, 2, 66]
print('The given Array')
print(arr)
radixSort(arr)
print('The sorted Array')
for i in range(len(arr)):
print(arr[i],end=" ")
Output:
The given Array
[170, 45, 75, 90, 802, 24, 2, 66]
The sorted Array
2 24 45 66 75 90 170 802
