Scribd
Upload
6 views17 pages

Untitled 5

vfdfdsfs

Uploaded by

johibel889
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
6 views17 pages

Untitled 5

vfdfdsfs

Uploaded by

johibel889
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 17

# SINGLYLINKEDLIST

class node:
def __init__(self,elt):
self.value=elt
self.next=None
def printnode(self):
print(self.value,end=" ")

class sll:
def __init__(self):
self.head=None
self.no_of_nodes=0

def insertatfirst(self,elt):
temp=node(elt)
temp.next=self.head
self.head=temp
self.no_of_nodes=self.no_of_nodes+1

def insertatlast(self,elt):
temp=node(elt)
trv=self.head
if self.head is None:
self.head=temp
else:
while trv.next is not None:
trv=trv.next
trv.next=temp
self.no_of_nodes=self.no_of_nodes+1

def insertatpos(self,elt,pos):
if pos<0 or pos>self.no_of_nodes+1:
print("OUT OF RANGE")
else:
if pos==1:
self.insertatfirst(elt)
elif pos==self.no_of_nodes+1:
self.insertatlast(elt)
else:
temp=node(elt)
cnt=1
trv=self.head
while cnt<pos-1:
trv=trv.next
cnt+=1
temp.next=trv.next
trv.next=temp
self.no_of_nodes=self.no_of_nodes+1
def deletefirst(self):
if self.head is not None:
temp=self.head
self.head=temp.next
print(f"{temp.value} deleted")
temp=None
else:
print("list is empty")

def deletelast(self):
if self.head==None:
print("List is empty")
elif self.head.next is None:
print(f"{self.head.value} is deleted")
self.head=None
else:
trv=self.head
while trv.next.next is not None:
trv=trv.next
print(f"{trv.value} -> ",end='')
temp=trv.next
trv.next=None
print(f"{temp.value} is deleted")
temp=None

def deletepos(self,pos):
if pos<0 or pos>self.no_of_nodes:
print("POSITION NOT VALID")
elif pos==1:
self.deletefirst()
elif pos==self.no_of_nodes:
self.deletelast()
else:
trv=self.head
cnt=1
while cnt<pos-1:
trv=trv.next
cnt+=1
temp=trv.next
print(f"{temp.value} deletedpos")
trv.next=temp.next
temp=None

def printlist(self):
trv=self.head
while trv is not None:
trv.printnode()
trv=trv.next
print("\n node = ",self.no_of_nodes)
s1=sll()
s1.insertatfirst(1)
s1.insertatfirst(2)
s1.insertatfirst(3)
s1.insertatlast(6)
s1.insertatpos(5,3)
s1.insertatpos(4,3)
s1.insertatpos(8,8)

#s1.deletefirst()
s1.deletelast()
#s1.deletepos(5)
s1.printlist()

OUT OF RANGE
2 -> 4 -> 5 -> 1 -> 6 is deleted
3 2 4 5 1
node = 6

# DOUBLYLINKEDLIST

class dnode:
def __init__(self,elt):
self.pre=None
self.value=elt
self.next=None
self.no_of_node=0

class dll:
def __init__(self):
self.head=None
self.no_of_node=0
self.tail=None

def insertfirst(self,elt):
temp=dnode(elt)
if self.head is None:
self.head=temp
self.tail=temp
else:
temp.next=self.head
self.head.pre=temp
self.head=temp
self.no_of_node+=1

def insertlast(self,elt):
temp=dnode(elt)
if self.head is None:
self.head = temp
self.tail=temp
else:
self.tail.next=temp
temp.pre=self.tail
self.tail=temp
self.no_of_node+=1

def insertpos(self,pos,elt):
temp=dnode(elt)
if pos<0 or pos>self.no_of_node+1:
print("out of range")
return
else:
if pos==1:
self.insertfirst(elt)
elif pos==self.no_of_node+1:
self.insertlast(elt)
else:
cnt=1
trv=self.head
while cnt<pos-1:
trv=trv.next
cnt+=1
temp.next=trv.next
temp.pre=trv
trv.next=temp
if temp.next:
temp.next.pre=temp
self.no_of_node+=1

def deletefirst(self):
if self.head is None:
print("List is EMPTY!")
return
elif self.head.next is None:
print(f"{self.head.value} is deleted")
else:
curr=self.head
self.head=curr.next
print(f"{curr.value} is deleted")
curr.next.pre=None
self.no_of_node-=1

def deletelast(self):
if self.head is None:
print("List is EMPTY!")
return
elif self.head.next is None:
print(f"{self.head.value} is deleted")
else:
curr=self.head
while curr.next is not None:
curr=curr.next
print(f"{curr.value} is deleted")
curr.pre.next=None
self.no_of_node-=1

def delpos(self,pos):
if pos<0 and pos>=self.no_of_node+1:
print("out of range!")
return
elif self.head is None:
print("Empty list")
return
elif pos==1:
self.deletefirst()
elif pos==self.no_of_node:
self.deletelast()
else:
cnt=1
curr=self.head
while cnt<pos-1:
cnt+=1
curr=curr.next
temp=curr.next
temp.next.pre=temp.pre
temp.pre.next=temp.next
print(f"{temp.value} is deleted at position {pos}")
temp=None
self.no_of_node-=1

def display(self):
trv=self.head
while trv is not None:
print(f"{trv.value}", end=" ")
trv=trv.next
print(f"\n\nnode size = {self.no_of_node}")

d1=dll()
d1.insertfirst(10)
d1.insertfirst(20)
d1.insertfirst(30)
d1.insertlast(33)
d1.insertlast(38)

d1.insertpos(5,99)
d1.insertpos(5,97)

#d1.deletefirst()
#d1.deletefirst()

#d1.deletelast()
#d1.deletelast()
#d1.deletelast()
#d1.deletelast()

d1.delpos(6)

d1.display()

99 is deleted at position 6
30 20 10 33 97 38

node size = 6

# CIRCULAR LINKEDLIST
class node:
def __init__(self,elt):
self.value=elt
self.next=None

class csll:
def __init__(self):
self.head=None
self.non=0
self.tail=None

def insertfirst(self,n):
while n>0:
c=int(input("enter ele = "))
temp=node(c)
if self.head is None:
self.head=temp
temp.next=self.head
self.tail=temp
else:
temp.next=self.head
curr=self.head
while curr.next is not self.head:
curr=curr.next
curr.next=temp
self.head=temp
self.non+=1
n-=1

def insertlast(self,n):
while n>0:
c=int(input("enter ele = "))
temp=node(c)
if self.head is None:
self.head=temp
temp.next=self.head
self.tail=temp
else:
curr=self.head
while curr.next is not self.head:
curr=curr.next
curr.next=temp
temp.next=self.head
self.tail=temp
self.non+=1
n-=1

def insertpos(self,n,pos):
temp=node(n)
if self.head is None:
print("list is empty")
return
elif pos<0 or pos>=self.non+2:
print("OUT OF RANGE!")
return
elif pos==1:
self.insertfirst(n)
elif pos==self.non+1:
self.insertlast(n)
else:
cnt=1
curr=self.head
while cnt<pos-1:
curr=curr.next
cnt+=1
temp.next=curr.next
curr.next=temp
self.non+=1

def delfirst(self):
if self.head is None:
print("CIRCULAR LIST IS EMPTY!")
return
elif self.head.next is None:
print(f"{self.head.value} is deleted")
self.head=None
return
else:
curr=self.head
print(f"{curr.value} is deleted")
self.head=curr.next
self.tail.next=self.head
curr=None
self.non-=1

def dellast(self):
if self.head is None:
print("CIRCULAR LIST IS EMPTY!")
return
elif self.head.next is None:
print(f"{self.head.value} is deleted")
self.head=None
return
else:
curr=self.head
while curr.next is not self.head:
prev=curr
curr=curr.next
prev.next=curr.next
print(f"{curr.value} is deleted")
curr=None
self.non-=1

def delpos(self,pos):
if self.head is None:
print("list is empty")
return
elif pos<0 or pos>=self.non+2:
print("OUT OF RANGE!")
return
elif pos==1:
self.delfirst()
elif pos==self.non:
self.dellast()
else:
cnt=1
curr=self.head
while cnt<pos-1:
curr=curr.next
cnt+=1
temp=curr.next
curr.next=temp.next
print(f"{temp.value} is deleted")
temp=None
self.non+=1

def display(self):
if self.head is None:
print("List is empty")
return
trv=self.head
while True:
print(f"{trv.value}",end=" ")
trv=trv.next
if(trv==self.head):
break
print(f"\nsize of nodes = {self.non}")
print()

c1=csll()

c1.insertfirst(3)

c1.insertlast(3)
#c1.insertpos(98,5)

#c1.dellast()
#c1.dellast()

#c1.delfirst()
#c1.delfirst()

c1.delpos(5)

c1.display()

enter ele = 1
enter ele = 2
enter ele = 3
enter ele = 4
enter ele = 5
enter ele = 6

98 is deleted
3 2 1 4 5 6
size of nodes = 8

# CIRCULAR DOUBLY LINKEDLIST

class node:
def __init__(self,elt):
self.value=elt
self.next=None
self.prev=None

class cdll:
def __init__(self):
self.head=None
self.non=0
self.tail=None
def insertfirst(self,n):
while n>0:
s=int(input("enter first ele = "))
temp=node(s)
if self.head is None:
self.head=temp
self.tail=temp
self.head.next=self.head
self.head.prev=self.head
else:
temp.next=self.head
temp.prev=self.tail
self.head.prev=temp
self.tail.next=temp
self.head=temp
self.non+=1
n-=1

def insertlast(self,n):
while n>0:
s=int(input("enter last ele = "))
temp=node(s)
if self.head is None:
self.head=temp
self.tail=temp
self.head.next=self.head
self.head.prev=self.head
else:
temp.next=self.head
temp.prev=self.tail
self.tail.next=temp
self.head.prev=temp
self.tail=temp
self.non+=1
n-=1

def insertpos(self,n,pos):
temp=node(n)
if self.head is None:
print("list is empty")
return
elif pos<0 or pos>=self.non+2:
print("OUT OF RANGE!")
return
elif pos==1:
self.insertfirst(n)
elif pos==self.non+1:
self.insertlast(n)
else:
cnt=1
curr=self.head
while cnt<pos-1:
curr=curr.next
cnt+=1
temp.next=curr.next
temp.prev=curr.prev
temp.next.prev=temp
curr.next=temp
print(f"{temp.value} is inserted at pos {pos}")
self.non+=1

def delfirst(self):
if self.head is None:
print("LIST IS EMPTY!")
return
elif self.head.next is None:
print(f"{self.head.value} is deleted")
return
else:
curr=self.head
self.tail.next=curr.next
curr.next.prev=curr.prev
self.head=curr.next
print(f"{curr.value} is DELETED")
curr=None

def dellast(self):
if self.head is None:
print("LIST IS EMPTY!")
return
elif self.head.next is None:
print(f"{self.head.value} is deleted")
return
else:
curr=self.tail
curr.prev.next=curr.next
curr.next.prev=curr.prev
self.tail=curr.prev
print(f"{curr.value} is DELETED")
curr=None

def delpos(self,pos):
if self.head is None:
print("list is empty")
return
elif pos<0 or pos>=self.non+1:
print("OUT OF RANGE!")
return
elif pos==1:
self.delfirst()
elif pos==self.non:
self.dellast()
else:
cnt=1
curr=self.head
while cnt<pos-1:
curr=curr.next
cnt+=1
curr=curr.next
curr.next.prev=curr.prev
curr.prev.next=curr.next
print(f"{curr.value} is deleted at pos {pos}")
curr=None
self.non-=1

def display(self):
if self.head is None:
print("LIST IS EMPTY!")
return
trv=self.head
while True:
print(f"{trv.value} <=>",end=" ")
trv=trv.next
if trv==self.head:
break
print(f"\nno of nodes = {self.non}")

c1=cdll()

c1.insertfirst(3)
c1.insertlast(2)
c1.insertpos(33,5)

#c1.delfirst()
#c1.delfirst()

#c1.dellast()
#c1.dellast()
c1.delpos(5)
c1.display()

enter first ele = 1


enter first ele = 2
enter first ele = 3
enter last ele = 4
enter last ele = 5

33 is inserted at pos 5
33 is deleted at pos 5
3 <=> 2 <=> 1 <=> 5 <=>
no of nodes = 5

# STACK LINKEDLIST
class node:
def __init__(self,elt):
self.data=elt
self.next=0

class stack:
def __init__(self,sz):
self.size=sz
self.top=None
self.non=0
self.cnt=0

def push(self,elt):
if self.non==self.size:
print("stack is full")
return
else:
temp=node(elt)
temp.next=self.top
self.top=temp
self.non+=1
print(f"{elt} is added\n")

def pop(self):
if self.top is None:
print("stack is Empty")
return
else:
temp=self.top
self.top=temp.next
self.non-=1
print(f"{temp.data} is deleted\n")
temp=None
return

def display(self):
t=self.top
while t is not None:
print(f"{t.data}")
t=t.next

s1=stack(5)

s1.push(5)
s1.push(4)
s1.push(3)
s1.push(2)
s1.push(1)
s1.push(0)

s1.pop()
s1.pop()
s1.pop()
s1.pop()
s1.pop()
s1.pop()

s1.display()

5 is added

4 is added

3 is added

2 is added

1 is added

stack is full
1 is deleted

2 is deleted

3 is deleted

4 is deleted

5 is deleted

stack is Empty

# QUEUE LINKEDLIST

class node:
def __init__(self,elt):
self.data=elt
self.next=None

class queue:
def __init__(self,sz):
self.size=sz
self.data=[]
self.front=-1
self.rear=-1

def insert(self,elt):
if self.rear==self.size-1:
print("QUEUE is FULL")
return
elif self.front==-1:
self.front+=1
self.data.append(elt)
print(f"{self.data} is inserted")
self.rear+=1
return
else:
self.data.append(elt)
print(f"{self.data} is inserted")
self.rear+=1
return

def delete(self):
if self.front==-1:
print("QUEUE is Empty")
return
elif self.front==self.rear:
print(f"{self.data[self.front]} is deleted")
self.front=-1
self.rear=-1
return
else:
print(f"{self.data[self.front]} is deleted")
self.front+=1
return

def display(self):
if self.front==-1:
print("QUEUE IS EMPTY")
return
v=self.front
while v<=self.rear:
print(f"{self.data[v]}",end=" -> ")
v=v+1
print()

q1=queue(3)
q1.insert(4)
q1.insert(5)
q1.insert(6)
#q1.insert(5) #full queue

q1.delete()
q1.display()

[4] is inserted
[4, 5] is inserted
[4, 5, 6] is inserted
4 is deleted
5 -> 6 ->

# SPARSE MATRIX
mat1 = [[0, 0, 0, 1], [0, 1, 0, 2], [0, 0, 0, 5], [7, 0, 0, 0]]
mat2 = [[0, 0, 0, 1], [1, 1, 0, 0], [1, 0, 0, 5], [0, 0, 2, 0]]
sp1 = []
sp2 = []
sz = 0

# Convert mat1 to sparse format


for row in range(4):
for col in range(4):
if mat1[row][col] != 0:
sz += 1
sp1 = [[4, 4, sz]] # Initialize sparse matrix header for mat1

for row in range(4):


for col in range(4):
if mat1[row][col] != 0:
sp1.append([row, col, mat1[row][col]])

# Convert mat2 to sparse format


sz = 0
for row in range(4):
for col in range(4):
if mat2[row][col] != 0:
sz += 1
sp2 = [[4, 4, sz]] # Initialize sparse matrix header for mat2

for row in range(4):


for col in range(4):
if mat2[row][col] != 0:
sp2.append([row, col, mat2[row][col]])

print("Sparse Matrix 1:", sp1)


print("Sparse Matrix 2:", sp2)

# Check dimensions and add matrices if they match


if sp1[0][0] == sp2[0][0] and sp1[0][1] == sp2[0][1]: # Check for
matching dimensions
sp3 = [[sp1[0][0], sp1[0][1], 0]] # Initialize result sparse
matrix header
m1 = m2 = 1 # Start from the first non-header element in sp1 and
sp2
m3 = 1 # Track the position in sp3

# Process all non-zero elements in sp1 and sp2


while m1 <= sp1[0][2] and m2 <= sp2[0][2]:
if sp1[m1][0] == sp2[m2][0] and sp1[m1][1] == sp2[m2][1]:
# Elements are at the same position, so add their values
sp3.append([sp1[m1][0], sp1[m1][1], sp1[m1][2] + sp2[m2]
[2]])
m1 += 1
m2 += 1
m3 += 1
elif sp1[m1][0] < sp2[m2][0] or (sp1[m1][0] == sp2[m2][0] and
sp1[m1][1] < sp2[m2][1]):
# Add element from sp1 if it comes first
sp3.append([sp1[m1][0], sp1[m1][1], sp1[m1][2]])
m1 += 1
m3 += 1
else:
# Add element from sp2 if it comes first
sp3.append([sp2[m2][0], sp2[m2][1], sp2[m2][2]])
m2 += 1
m3 += 1

# Append remaining elements from sp1 if any


while m1 <= sp1[0][2]:
sp3.append([sp1[m1][0], sp1[m1][1], sp1[m1][2]])
m1 += 1
m3 += 1

# Append remaining elements from sp2 if any


while m2 <= sp2[0][2]:
sp3.append([sp2[m2][0], sp2[m2][1], sp2[m2][2]])
m2 += 1
m3 += 1

# Update the number of non-zero entries in sp3 header


sp3[0][2] = m3 - 1

print("Resultant Sparse Matrix after Addition:", sp3)


else:
print("Matrices dimensions do not match; cannot add.")

Sparse Matrix 1: [[4, 4, 5], [0, 3, 1], [1, 1, 1], [1, 3, 2], [2, 3,
5], [3, 0, 7]]
Sparse Matrix 2: [[4, 4, 6], [0, 3, 1], [1, 0, 1], [1, 1, 1], [2, 0,
1], [2, 3, 5], [3, 2, 2]]
Resultant Sparse Matrix after Addition: [[4, 4, 8], [0, 3, 2], [1, 0,
1], [1, 1, 2], [1, 3, 2], [2, 0, 1], [2, 3, 10], [3, 0, 7], [3, 2, 2]]

You might also like