SATISH PRADHAN DNYANASADHNA COLLEGE A.Y.

[2023-2024]
Name: Sahil Ramjan Saiyad
Name: Sahil Ramjan Saiyad
Div.: A Batch: BRollRoll
Div:=A / Batch: B
No.:52
No.:52
Subject:Subject:=
Data Structure Practical
Data Structure Prac cal Std.:
Std.: S.Y.BSc. Computer
S.Y.BSc. Computer Science
Science

INDEX
Sr. Practical Name Date Page Signature
No. No.
1 Write a program to implement
Abstract Data Types (ADT) 14/07/2023 2-9
2 Write a program to implement
Singly Linked list with insertion, 21/07/2023 10-13
deletion, traversal operations
3 Write a program to implement
Doubly Linked list with insertion, 18/08/2023 14-15
deletion, traversal operations
4 Write a program to implement
Stack with insertion, deletion, 28/08/2023 16-17
traversal operations
5 Write a program to implement
Queue with insertion, deletion, 28/08/2023 18-19
traversal operations
6 Write a program to implement
Priority Queue with insertion, 4/08/2023 20-21
deletion, traversal operations
7 Write a program to implement
Binary Tree with insertion, 11/09/2023 22-23
deletion, traversal operations
8 Write a program to implement
Graph with insertion, deletion, 08/09/2023 24-25
traversal operations
9 Write a program to implement
Huffman Coding algorithm 08/09/2023 26-27

10 Write a program to create a simple

Hash table for insertion, deletion 25/09/2023 28-30
and traversal operations

Page 1 of 29
Name: Sahil Ramjan Saiyad Div:=A / Batch: B Roll No.:52
Subject:= Data Structure Prac cal Std.: S.Y.BSc. Computer Science
Practical No.1
Aim := Write a program to implement Abstract Data Types
(ADT)
A. Using Builtin Data Type (List)
Program 1
list1 = [10,20,30,40,50]
print("printing element in python by using different ways")
print("print list by print()method",list1)
print("print list by for loop")
for i in list1:
print(i,end=" ")
print() print("print list by * asterisk")
print(*list1)
print("print list by comma separator")
print(list1,sep=" , ")
Output:
printing element in python by using different ways print list by print()method
[10, 20, 30, 40, 50]
print list by for loop 10 20 30 40 50 print list by * asterisk 10 20 30 40 50 print
list by comma separator
[10, 20, 30, 40, 50]
Program 2
list1 = [10,20,30,40,50]
print(list1[0])
print(list1[1:4])
print(list1[1:3])
print(list1[-1])

Page 2 of 29
Name: Sahil Ramjan Saiyad Div:=A / Batch: B Roll No.:52
Subject:= Data Structure Prac cal Std.: S.Y.BSc. Computer Science
print(list1[3:-1])
print(list1[0:2:2])
print(list1[0:5])
Output:
[20, 30, 40]
[20, 30]
50
[40]
[10]
[10, 20, 30, 40, 50]

Program 3
Le = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 130, 140, 150, 160, 170,
180, 190, 200]
print("Printing the list element using print:\n", le)
print("Printing the list element using for loop:")
for i in le:
print(i, end=" ")
print("\nPrinting the list element * Asterisk:")
print(*le)
print("Printing the list element by comma separator:")
print(le, sep=",")
Output:
Printing the list element using print:
[10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 130, 140, 150, 160, 170,
180, 190, 200]
Printing the list element using for loop:
10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190 200
Printing the list element * Asterisk:
Page 3 of 29
Name: Sahil Ramjan Saiyad Div:=A / Batch: B Roll No.:52
Subject:= Data Structure Prac cal Std.: S.Y.BSc. Computer Science
10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190 200
Printing the list element by comma separator:
[10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 130, 140, 150, 160, 170, 180,
190, 200]
Program 4:
le = [10,20,30,40,50]
print(le)
print(le[1::])
print(le[1:3])
print(le[4:])
print(le[3::])
print(le[::2])
print(le[::4])
print("Printing in reverse")
print((le[::-1]))
print(le[-1:-5:-1])
print(le[-3:-5:-1])
print(le[4:])
print(le[::-1])
print(le[::2])
print(le[::4])
Output:
[10, 20, 30, 40, 50]
[20, 30, 40, 50]
[20, 30] [50]
[40, 50]
[10, 30, 50]
[10, 50]
Printing in reverse
[50, 40, 30, 20, 10]
[50, 40, 30, 20]
Page 4 of 29
Name: Sahil Ramjan Saiyad Div:=A / Batch: B Roll No.:52
Subject:= Data Structure Prac cal Std.: S.Y.BSc. Computer Science
[30, 20]
[50]
[50, 40, 30, 20, 10]
[10, 30, 50]
[10, 50]
B. using modules numpy
Program1:
import numpy as np
from numpy
import * a =
np.array([["Mon",1,2,3,4],["Tue",5,6,7,8],["Wed",9,10,11,12],["Thu",13,14,15,1
6],["F ri",17,18,19,20],["Sat",21,22,23,24]])
m = reshape(a,(6,5))
O/p:
print(m)
[['Mon' '1' '2' '3' '4']
['Tue' '5' '6' '7' '8']
['Wed' '9' '10' '11' '12']
['Thu' '13' '14' '15' '16']
['Fri' '17' '18' '19' '20']
['Sat' '21' '22' '23' '24']]

Program2:
import numpy as np
from numpy
import * a =
np.array([["Mon",1,2,3,4],["Tue",5,6,7,8],["Wed",9,10,11,12],["Thu",13,14,15,1
6],["F ri",17,18,19,20],["Sat",21,22,23,24]])
m = reshape(a,(6,5))
print(m[2])

Page 5 of 29
Name: Sahil Ramjan Saiyad Div:=A / Batch: B Roll No.:52
Subject:= Data Structure Prac cal Std.: S.Y.BSc. Computer Science
#Printing array
O/p:
['Wed' '9' '10' '11' '12']

Program 3:
Code: import numpy as np
from numpy
import * a =
np.array([["Mon",1,2,3,4],["Tue",5,6,7,8],["Wed",9,10,11,12],["Thu",13,14,15,1
6],["F ri",17,18,19,20],["Sat",21,22,23,24]])
m = reshape(a,(6,5))
print(m)
#Printing array
r = append(m,["Sun",25,26,27,28])
print(r)
O/p:
[['Mon' '1' '2' '3' '4']
['Tue' '5' '6' '7' '8']
['Wed' '9' '10' '11' '12']
['Thu' '13' '14' '15' '16']
['Fri' '17' '18' '19' '20']
['Sat' '21' '22' '23' '24']]
['Mon' '1' '2' '3' '4' 'Tue' '5' '6' '7' '8' 'Wed' '9' '10' '11' '12'
'Thu' '13' '14' '15' '16' 'Fri' '17' '18' '19' '20' 'Sat' '21' '22' '23' '24' 'Sun' '25' '26' '27'
'28']
Program 4:
import numpy as np
from numpy

Page 6 of 29
Name: Sahil Ramjan Saiyad Div:=A / Batch: B Roll No.:52
Subject:= Data Structure Prac cal Std.: S.Y.BSc. Computer Science
import * a =
np.array([["Mon",1,2,3,4],["Tue",5,6,7,8],["Wed",9,10,11,12],["Thu",13,14,15,1
6],["F ri",17,18,19,20],["Sat",21,22,23,24]])
m = reshape(a,(6,5))
d = np.delete(m,[3],0)
print(d)
O/p:
[['Mon' '1' '2' '3' '4']
['Tue' '5' '6' '7' '8']
['Wed' '9' '10' '11' '12']
['Fri' '17' '18' '19' '20']
['Sat' '21' '22' '23' '24']]
Program 5:
import numpy as np
from numpy
import*a=np.array([["Mon",1,2,3,4],["Tue",5,6,7,8],["Wed",9,10,11,12],["Thu",
13,14,15,16],["F ri",17,18,19,20],["Sat",21,22,23,24]])
m = reshape(a,(6,5))
print(m)
#Printing array
r = append(m,["Sun",25,26,27,28])
print(r)
d = np.delete(r,[3],0)
print(d)
print(a[2])
O/p:
[['Mon' '1' '2' '3' '4']
['Tue' '5' '6' '7' '8']
Page 7 of 29
Name: Sahil Ramjan Saiyad Div:=A / Batch: B Roll No.:52
Subject:= Data Structure Prac cal Std.: S.Y.BSc. Computer Science
['Wed' '9' '10' '11' '12']
['Thu' '13' '14' '15' '16']
['Fri' '17' '18' '19' '20']
['Sat' '21' '22' '23' '24']]
['Mon' '1' '2' '3' '4' 'Tue' '5' '6' '7' '8' 'Wed' '9' '10' '11' '12' 'Thu' '13' '14' '15' '16'
'Fri' '17' '18' '19' '20' 'Sat' '21' '22' '23' '24' 'Sun' '25' '26' '27' '28']
['Mon' '1' '2' '4' 'Tue' '5' '6' '7' '8' 'Wed' '9' '10' '11' '12' 'Thu' '13' '14' '15' '16' 'Fri'
'17' '18' '19' '20' 'Sat' '21' '22' '23' '24' 'Sun' '25' '26' '27' '28']
['Wed' '9' '10' '11' '12']

Program 6:
import numpy as np
from numpy
import * a =
array([["Mon",1,2,3,4],["Tue",5,6,7,8],["Wed",9,10,11,12],["Thu",13,14,15,16],
["Fri", 17,18,19,20],["Sat",21,22,23,24]])
print(a)
a[3] = ["N/a",0,0,0,0]
print(a)
Output:
[['Mon' '1' '2' '3' '4']
['Tue' '5' '6' '7' '8']
['Wed' '9' '10' '11' '12']
['Thu' '13' '14' '15' '16']
['Fri' '17' '18' '19' '20']
['Sat' '21' '22' '23' '24']]
[['Mon' '1' '2' '3' '4']
['Tue' '5' '6' '7' '8']
['Wed' '9' '10' '11' '12']
['N/a' '0' '0' '0' '0']
Page 8 of 29
Name: Sahil Ramjan Saiyad Div:=A / Batch: B Roll No.:52
Subject:= Data Structure Prac cal Std.: S.Y.BSc. Computer Science
['Fri' '17' '18' '19' '20']
['Sat' '21' '22' '23' '24']]

Page 9 of 29
Name: Sahil Ramjan Saiyad Div:=A / Batch: B Roll No.:52
Subject:= Data Structure Prac cal Std.: S.Y.BSc. Computer Science

Practical No.2
Write a program to implement Singly Linked list with insertion,
deletion, traversal operations
Program 1
class Node:
def __init__(self, data, next=None):
self.dataVal = data
self.nextVal = next
class SingleLinkList:
def __init__(self, head=None):
self.headVal = head
def listprint(self):
printval = self.headVal
while printval is not None:
print(printval.dataVal, end=", ")
printval = printval.nextVal
def insertAtBeginning(self, newdata):
NewNode = Node(newdata)
NewNode.nextVal = self.headVal
self.headVal = NewNode
def insertAtEnd(self, newdata):
NewNode = Node(newdata)
if self.headVal is None:
self.headVal = NewNode
return
laste = self.headVal
while laste.nextVal:
laste = laste.nextVal
laste.nextVal = NewNode
def insertInBetween(self, middle_node, newdata):
if middle_node is None:
print("The mentioned node is absent")
return
NewNode = Node(newdata)
Page 10 of 29
Name: Sahil Ramjan Saiyad Div:=A / Batch: B Roll No.:52
Subject:= Data Structure Prac cal Std.: S.Y.BSc. Computer Science
NewNode.nextVal = middle_node.nextVal
middle_node.nextVal = NewNode
def removeNode(self, Removekey):
HeadVal = self.headVal
if HeadVal is not None:
if HeadVal.dataVal == Removekey:
self.headVal = HeadVal.nextVal
HeadVal = None
return
while HeadVal is not None:
if HeadVal.dataVal == Removekey:
break
prev = HeadVal
HeadVal = HeadVal.nextVal
if HeadVal is None:
return
prev.nextVal = HeadVal.nextVal
HeadVal = None
def removeStart(self):
if self.headVal is not None:
self.headVal = self.headVal.nextVal
def removeEnd(self):
last = self.headVal
if last is None:
print("List is empty")
return
if last.nextVal is None:
self.headVal = None
return None
while last.nextVal.nextVal:
last = last.nextVal
if last.nextVal.nextVal is None:
last.nextVal = None
# Test the corrected code
sli = SingleLinkList()
e1 = Node("Mon")
e2 = Node("Tue")
Page 11 of 29
Name: Sahil Ramjan Saiyad Div:=A / Batch: B Roll No.:52
Subject:= Data Structure Prac cal Std.: S.Y.BSc. Computer Science
e3 = Node("Wed")
e4 = Node("Thu")
e5 = Node("Fri")
sli.headVal = e1
e1.nextVal = e2
e2.nextVal = e3
e3.nextVal = e4
e4.nextVal = e5
print("*** Printing Link List ***")
sli.listprint()
print("\n*** Printing Link List After Inserting At Beginning ***")
sli.insertAtBeginning("Sun")
sli.listprint()

print("\n*** Printing Link List After Inserting At End ***")

sli.insertAtEnd("Sat")
sli.listprint()
print("\n*** Printing Link List After Inserting In Between ***")
sli.insertInBetween(e3, "n/a")
sli.listprint()
print("\n*** Printing Link List After Removing Element In Between ***")
sli.removeNode("n/a")
sli.listprint()
print("\n*** Printing Link List After Removing Element At Beginning ***")
sli.removeStart()
sli.listprint()
print("\n*** Printing Link List After Removing Element At End ***")
sli.removeEnd()
sli.listprint()

Output
*** Printing Link List ***
Mon, Tue, Wed, Thu, Fri,
*** Printing Link List After Inserting At Beginning ***
Sun, Mon, Tue, Wed, Thu, Fri,
*** Printing Link List After Inserting At End ***
Sun, Mon, Tue, Wed, Thu, Fri, Sat,
Page 12 of 29
Name: Sahil Ramjan Saiyad Div:=A / Batch: B Roll No.:52
Subject:= Data Structure Prac cal Std.: S.Y.BSc. Computer Science
*** Printing Link List After Inserting In Between ***
Sun, Mon, Tue, Wed, n/a, Thu, Fri, Sat,
*** Printing Link List After Removing Element In Between ***
Sun, Mon, Tue, Wed, Thu, Fri, Sat,
*** Printing Link List After Removing Element At Beginning ***
Mon, Tue, Wed, Thu, Fri, Sat,
*** Printing Link List After Removing Element At End ***
Mon, Tue, Wed, Thu, Fri,

Page 13 of 29
Name: Sahil Ramjan Saiyad Div:=A / Batch: B Roll No.:52
Subject:= Data Structure Prac cal Std.: S.Y.BSc. Computer Science
Practical No.3
Aim: Write a program to implement Doubly Linked list with
insertion, deletion, traversal operations
Program 1
# node structure
class Node:
# constructor to create a new node
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
# class Linked List
class LinkedList:
# constructor to create an empty LinkedList
def __init__(self):
self.head = None
# test the code
# create an empty LinkedList
MyList = LinkedList()
# Add first node.
first = Node(10)
# linking with head node
MyList.head = first
# Add second node.
second = Node(20)
# linking with first node
second.prev = first
first.next = second

Page 14 of 29
Name: Sahil Ramjan Saiyad Div:=A / Batch: B Roll No.:52
Subject:= Data Structure Prac cal Std.: S.Y.BSc. Computer Science
# Add third node.
third = Node(30)
# linking with second node
third.prev = second
second.next = third
# Function to print the linked list
def print_linked_list(linked_list):
current = linked_list.head
while current is not None:
print(current.data, end=" -> ")
current = current.next
print("None")
# Print the linked list
print("Linked List:")
print_linked_list(MyList)
Output:
Linked List:
10 -> 20 -> 30 -> None

Page 15 of 29
Name: Sahil Ramjan Saiyad Div:=A / Batch: B Roll No.:52
Subject:= Data Structure Prac cal Std.: S.Y.BSc. Computer Science
Practical No.4
Aim :Write a program to implement Stack with insertion,
deletion, traversal operations
Program 1.
stack=[]
stack.append(10)
stack.append(20)
stack.append(300)
print(stack)
stack.pop()
print(stack)
print("no. of elements in stack",len(stack))
stack.pop()
stack.pop()

Output:
[10, 20, 300]
[10, 20]
no. of elements in stack 2

Program 2
import collections
stack=collections.deque()
stack.append(10)
stack.append(3.14)
stack.append("value of pi")
stack.append("value of radius")
stack.append(10)
stack.append(10)
print(stack)
print("no. of elements in deque=",len(stack))
print("count 10 in deque:-",stack.count(10))

Output:
deque([10, 3.14, 'value of pi', 'value of radius', 10, 10])
no. of elements in deque= 6
Page 16 of 29
Name: Sahil Ramjan Saiyad Div:=A / Batch: B Roll No.:52
Subject:= Data Structure Prac cal Std.: S.Y.BSc. Computer Science
count 10 in deque:- 3

Program 3
import queue
stack=queue.LifoQueue()
stack.put(10)
stack.put(200)
stack.put("SYBSCCS CLASS")
print("check stack is empty or not:-",stack.empty())
print("check stack is full or not:-",stack.full())
print("no of item in LifoQueue:-",stack.qsize())
print("elements:-",stack.get())
print("elements:-",stack.get())
print("elements:-",stack.get())
print("ckeck stack is empty or not:-",stack.empty())

Output:
check stack is empty or not:- False
check stack is full or not:- False
no of item in LifoQueue:- 3
elements:- SYBSCCS CLASS
elements:- 200
elements:- 10
ckeck stack is empty or not:- True

Page 17 of 29
Name: Sahil Ramjan Saiyad Div:=A / Batch: B Roll No.:52
Subject:= Data Structure Prac cal Std.: S.Y.BSc. Computer Science
Practical No.5
Aim: Write a program to implement Queue with insertion,
deletion, traversal operations
Program 1
q=[]
q.append(10)
q.append(20)
q.append(30)
print(q)
print("length of queue is:-",len(q))
q.pop(0)
q.pop(0)
print(q)

Output:
[10, 20, 30]
length of queue is:- 3
[30]
Program 2
q=[]
q.insert(0,10)
q.insert(0,20)
q.insert(0,30)
print(q)
print("Length of queue is:",len(q))
q.pop()
q.pop()
print(q)

Output:
[30, 20, 10]
Length of queue is: 3[30]

Program 3
import collections
q=collections.deque()
Page 18 of 29
Name: Sahil Ramjan Saiyad Div:=A / Batch: B Roll No.:52
Subject:= Data Structure Prac cal Std.: S.Y.BSc. Computer Science
q.appendleft(10)
q.appendleft(20)
q.appendleft(30)
print(q)
print("NO. of elements in deque is:-",len(q))
print("NO. of elements in deque is:-",q.count(10))
q.pop()
q.pop()
print(q)

Output:
deque([30, 20, 10])
NO. of elements in deque is:- 3
NO. of elements in deque is:- 1
deque([30])

Program 4
import collections
q=collections.deque()
q.append(10)
q.append(20)
q.append(30)
print(q)
print("NO. of elements in deque is:-",len(q))
print("NO. of elements in deque is:-",q.count(10))
q.popleft()
q.popleft()
print(q)
Output:
deque([10, 20, 30])
NO. of elements in deque is:- 3
NO. of elements in deque is:- 1
deque([30]

Page 19 of 29
Name: Sahil Ramjan Saiyad Div:=A / Batch: B Roll No.:52
Subject:= Data Structure Prac cal Std.: S.Y.BSc. Computer Science
Practical No.6
Aim: Write a program to implement Priority Queue with
insertion, deletion, traversal operations
Program 1:
q=[]
q.append(150)
q.append(300)
q.append(500)
q.append(130)
print("original queue:",q)
q.sort()
print("After sorting:",q)
#removing the highest priority element.
print("removed element:",q.pop())
print("queue after pop:",q)

Output:
original queue: [150, 300, 500, 130]
After sorting: [130, 150, 300, 500]
removed element: 500
queue after pop: [130, 150, 300]

Program 2:
q=[]
q.append(150)
q.append(300)
q.append(500)
q.append(130)
print("original queue:",q)
q.sort(reverse=True)
print("After sorting:",q)
#removing the highest priority element.
print("removed element:",q.pop(0))
print("queue after pop:",q)
q.append(350)
q.append(380)
q.append(800)
q.append(750)
Page 20 of 29
Name: Sahil Ramjan Saiyad Div:=A / Batch: B Roll No.:52
Subject:= Data Structure Prac cal Std.: S.Y.BSc. Computer Science
#removing the highest priority element.
print("removed element:",q.pop(0))
Output:
original queue: [150, 300, 500, 130]
After sorting: [500, 300, 150, 130]
removed element: 500
queue after pop: [300, 150, 130]
removed element: 300

Program 3:
#Decreasing order
q=[]
q.append(150)
q.append(300)
q.append(500)
q.append(130)
print("original queue:",q)
q.sort(reverse=True)
print("After sorting:",q)
#removing the highest priority element.
print("removed element:",q.pop(0))
print("queue after pop:",q)
Output:
original queue: [150, 300, 500, 130]
After sorting: [500, 300, 150, 130]
removed element: 500
queue after pop: [300, 150, 130]

Page 21 of 29
Name: Sahil Ramjan Saiyad Div:=A / Batch: B Roll No.:52
Subject:= Data Structure Prac cal Std.: S.Y.BSc. Computer Science
Practical No.7
Aim: Write a program to implement Binary Tree with insertion,
deletion, traversal operations
Program1
class Node:
def __init__(self,key):
self.left=None
self.right=None
self.val=key
#traverse preorder
def traversePreOrder(self):
print(self.val,end=' ')
if self.left:
self.left.traversePreOrder()
if self.right:
self.right.traversePreOrder()
#traverse inorder
def traverseInOrder(self):
if self.left:
self.left.traverseInOrder()
print(self.val,end=' ')
if self.right:
self.right.traverseInOrder()
#Traverse PostOrder
def traversePostOrder(self):
if self.left:
self.left.traversePostOrder()
if self.right:
self.right.traversePostOrder()
print(self.val,end=' ')
root=Node(1)
root.left=Node(2)
root.right=Node(3)
root.left.left=Node(4)
root.left.right=Node(5)
Page 22 of 29
Name: Sahil Ramjan Saiyad Div:=A / Batch: B Roll No.:52
Subject:= Data Structure Prac cal Std.: S.Y.BSc. Computer Science
print("pre order Traversal:",end="")
root.traversePreOrder()
print("\nIn order Traversal:",end="")
root.traverseInOrder()
print("\nPost order Traversal:",end="")
root.traversePostOrder()

Output:
pre order Traversal:1 2 4 5 3
In order Traversal:4 2 5 1 3
Post order Traversal:4 5 2 3 1

Page 23 of 29
Name: Sahil Ramjan Saiyad Div:=A / Batch: B Roll No.:52
Subject:= Data Structure Prac cal Std.: S.Y.BSc. Computer Science
Practical No.8
Aim: Write a program to implement Graph with insertion,
deletion, traversal operations
Program :
# Graph implementation using dictionary
class Graph:
def __init__(self, gdict=None):
if gdict is None:
gdict = {}
self.gdict = gdict
def getVertices(self):
return list(self.gdict.keys())
def getEdges(self):
return list(self.gdict.values())
graph_element = {
"a": ["b", "c"],
"b": ["a", "d"],
"c": ["a", "d"],
"d": ["b", "c", "e"],
"e": ["d"]
}
g = Graph(graph_element)
print("Representation of graph using dictionary")
print(graph_element)
print("\nKeys:")
print(g.getVertices())
print("\nEdges:")
print(g.getEdges())

Output:
Representation of graph using dictionary
{'a': ['b', 'c'], 'b': ['a', 'd'], 'c': ['a', 'd'], 'd': ['b', 'c', 'e'], 'e': ['d']}

Keys:
Page 24 of 29
Name: Sahil Ramjan Saiyad Div:=A / Batch: B Roll No.:52
Subject:= Data Structure Prac cal Std.: S.Y.BSc. Computer Science
['a', 'b', 'c', 'd', 'e']

Edges:
[['b', 'c'], ['a', 'd'], ['a', 'd'], ['b', 'c', 'e'], ['d']]

Page 25 of 29
Name: Sahil Ramjan Saiyad Div:=A / Batch: B Roll No.:52
Subject:= Data Structure Prac cal Std.: S.Y.BSc. Computer Science
Practical No. 9
Aim: Write a program to implement Huffman Coding algorithm
Program
string = "BCAADDDCCACACAC" # Replace with your input string
class NodeTree(object):
def __init__(self, left=None, right=None):
self.left = left
self.right = right
def children(self):
return (self.left, self.right)
def nodes(self):
return (self.left, self.right)
def __str__(self):
return '%s_%s' % (self.left, self.right)
def huffman_code_tree(node, left=True, binString=''):
if isinstance(node, str):
return {node: binString}
(l, r) = node.children()
d = {}
d.update(huffman_code_tree(l, True, binString + '0'))
d.update(huffman_code_tree(r, False, binString + '1'))
return d
freq = {}
for e in string:
if e in freq:
freq[e] += 1
else:
freq[e] = 1
freq = sorted(freq.items(), key=lambda x: x[1], reverse=True)
nodes = freq
while len(nodes) > 1:
(key1, c1) = nodes[-1]
(key2, c2) = nodes[-2]
nodes = nodes[:-2]
node = NodeTree(key1, key2)
nodes.append((node, c1 + c2))
nodes = sorted(nodes, key=lambda x: x[1], reverse=True)

huffmanCode = huffman_code_tree(nodes[0][0])
Page 26 of 29
Name: Sahil Ramjan Saiyad Div:=A / Batch: B Roll No.:52
Subject:= Data Structure Prac cal Std.: S.Y.BSc. Computer Science
print('char | huffman code')
print('--------------------')
for (char, frequency) in freq:
print('%-4r | %s' % (char, huffmanCode[char]))

Output:
char | huffman code
--------------------
'C' | 0
'A' | 11
'D' | 101
'B' | 100

Page 27 of 29
Name: Sahil Ramjan Saiyad Div:=A / Batch: B Roll No.:52
Subject:= Data Structure Prac cal Std.: S.Y.BSc. Computer Science
Practical No. 10
Aim: Write a program to create a simple Hash table for insertion,
deletion and traversal operations
Program:
class HashTable1:
def __init__(self, size):
self.size = size
self.table = [None] * size

def _hash_function(self, key):

return hash(key) % self.size

def insert(self, key, value):

index = self._hash_function(key)
self.table[index] = (key, value)

def delete(self, key):

index = self._hash_function(key)
if self.table[index] and self.table[index][0] == key:
self.table[index] = None

def get(self, key):

index = self._hash_function(key)
if self.table[index] and self.table[index][0] == key:
return self.table[index][1]
else:
return None

def traverse(self):
for item in self.table:
if item:
print(f"Key: {item[0]}, Value: {item[1]}")

# Example usage:
ht = HashTable1(10)
Page 28 of 29
Name: Sahil Ramjan Saiyad Div:=A / Batch: B Roll No.:52
Subject:= Data Structure Prac cal Std.: S.Y.BSc. Computer Science

ht.insert("apple", 5)
ht.insert("banana", 10)
ht.insert("cherry", 15)

print("HashTable:")
ht.traverse()

ht.delete("banana")
print("\nAfter deleting 'banana':")
ht.traverse()

search_result = ht.get("cherry")
if search_result is not None:
print("\nSearch result for 'cherry':", search_result)
else:
print("\n'cherry' not found in the HashTable.")

Output:
HashTable:
Key: cherry, Value: 15
Key: banana, Value: 10

After deleting 'banana':

Key: cherry, Value: 15

Search result for 'cherry': 15ss

Page 29 of 29