Linear Search Using Python

Linear Search is the simplest way of searching key element from the list of elements. In linear search the order of elements can be in ascending order or can be in descending order. The elements in the list can be redundant. Time complexity of this search is O(n).

Source Code:

a=[]
count=0
n=int(input("how many elements u want to enter"))
for i in range(n):
    num=int(input("enter number"))
    a.append(num)
print(a)
key=int(input("enter the key to be serched"))
for i in range(n):
    if key==a[i]:
        print("%d found in %d" %(key,i))
        count=count+1
if count==0:
    print("%d not found" %key)
else:
    print("%d found %d time(s)" %(key,count))

Output:

Python 3.4.0 (v3.4.0:04f714765c13, Mar 16 2014, 19:24:06) [MSC v.1600 32 bit (Intel)] on win32

Type "copyright", "credits" or "license()" for more information.

>>> ================================ RESTART ================================

>>> 

how many elements u want to enter6

enter number1

enter number2

enter number3

enter number4

enter number5

enter number6

[1, 2, 3, 4, 5, 6]

enter the key to be serched3

3 found in 2

3 found 1 time(s)

>>> ================================ RESTART ================================

>>> 

how many elements u want to enter6

enter number1

enter number2

enter number3

enter number3

enter number4

enter number5

[1, 2, 3, 3, 4, 5]

enter the key to be serched3

3 found in 2

3 found in 3

3 found 2 time(s)

>>> 

Binary Search Tree

Binary Search Tree 

Binary search tree is a binary tree where node values greater than root node are placed towards right side of root and node values less than or equal to root node are placed towards left side of root.

Source Code:

class Node:
    def __init__(self,data):
        self.data=data
        self.rchild=None
        self.lchild=None
class Bst:
    def __init__(self):
        self.root=None             
 
    def createtree(self,data):
        if self.root==None:
            self.root = Node(data)
        else:
            temp = self.root
            while temp !=None:
                if data < temp.data:
                    if temp.lchild==None:
                        temp.lchild = Node(data)
                        return
                    else:
                        temp = temp.lchild
                else:
                    if temp.rchild==None:
                        temp.rchild = Node(data)
                        return
                    else:
                        temp = temp.rchild
     
    def inorder(self, root):
        if root!=None:
            self.inorder(root.lchild)
            print(root.data)
            self.inorder(root.rchild)
 
    def preorder(self, root):
        if root!=None:
            print(root.data)
            self.preorder(root.lchild)         
            self.preorder(root.rchild)
         
    def postorder(self,root):
        if root!=None:
            self.postorder(root.lchild)         
            self.postorder(root.rchild)
            print(root.data)

    def display(self,root):
        if root!=None:         
            print(root.data)
            self.inorder(root.rchild)
            self.inorder(root.lchild)
         
    def count(self, root):
        if root == None:
            return 0
        else:
            return 1 + self.count(root.lchild) + self.count(root.rchild)

def menu():
    global ch
    print("\n1.create\n2.preorder\n3.postorder\n4.inorder
                   \n5.display\n6.count\n7.stop")
    ch=int(input("enter u r choice"))

t=Bst()
while True:
    menu()
    if ch==1:
         n=int(input("enter no of node for tree"))
         for i in range(n):
            data=int(input("enter data"))
            t.createtree(data)
    elif ch==2:
       print("preorder")
       t.preorder(t.root)
    elif ch==3:
       print("postorder")
       t.postorder(t.root)
    elif ch==4:
       print("inorder")
       t.inorder(t.root)
    elif ch==5:
       t.display(t.root)
    elif ch==6:
        print("number of nodes in binary search tree")
        print(t.count(t.root))
    else:
        exit(0)
 

 

 


 

Output:

Python 3.4.0 (v3.4.0:04f714765c13, Mar 16 2014, 19:24:06) [MSC v.1600 32 bit (Intel)] on win32
Type "copyright", "credits" or "license()" for more information.
>>> ================================ RESTART ================================
>>>

1.create
2.preorder
3.postorder
4.inorder
5.display
6.count
7.stop
enter u r choice1
enter no of node for tree3
enter data20
enter data10
enter data30

1.create
2.preorder
3.postorder
4.inorder
5.display
6.count
7.stop
enter u r choice2
preorder
20
10
30

1.create
2.preorder
3.postorder
4.inorder
5.display
6.count
7.stop
enter u r choice3
postorder
10
30
20

1.create
2.preorder
3.postorder
4.inorder
5.display
6.count
7.stop
enter u r choice4
inorder
10
20
30

1.create
2.preorder
3.postorder
4.inorder
5.display
6.count
7.stop
enter u r choice5
20
30
10

1.create
2.preorder
3.postorder
4.inorder
5.display
6.count
7.stop
enter u r choice6
number of nodes in binary search tree
3

1.create
2.preorder
3.postorder
4.inorder
5.display
6.count
7.stop
enter u r choice7
>>>

Now my new Blog on Fundamentals of Python can be found at https://fundamentalsofpython.blogspot.com/2020/02/list-manipulations.html

Sparse Matrix Using Linked List

This is sparse matrix program. A matrix in which number of zeros are greater than half the size of matrix is known as sparse matrix.

Source Code:

class Node:
  def __init__(self,r,c,v):
    self.r=r
    self.c=c
    self.v=v
    self.next=None
class Sparse:
  def __init__(self):
    self.start=None
  def createlist(self,newnode):
    temp=self.start
    if self.start==None:
      self.start=newnode
    else:
      while temp.next!=None:
        temp=temp.next
      temp.next=newnode
  def display(self):
    temp=self.start
    print("row\tcol\tval")
    while temp!=None:
      print("%d\t%d\t%d" %(temp.r,temp.c,temp.v))
      temp=temp.next

row=int(input("enter number of rows : "))
col=int(input("enter number of coloumns : "))

X = [[0]*col for j in range(row)]
count=0
sp=Sparse()
print ("entry elements")
for i in range (row):
  for j in range (col): 
    X[i][j] = int(input())

print("matrix is:")
for i in range(row):
    for j in range(col):
        print(X[i][j], end=' ')
    print()

for i in range(row):
    for j in range(col):
        if X[i][j]==0:
            count=count+1

print("number of zeros:",count)

if count>(row*col)//2:
    print("sparse matrix")
    for i in range(row):
      for j in range(col):
        if X[i][j]!=0:
          newnode=Node(i,j,X[i][j])
          sp.createlist(newnode)       
    sp.display()
else:

    print("not sparse matrix")

Output:

Python 3.4.0 (v3.4.0:04f714765c13, Mar 16 2014, 19:24:06) [MSC v.1600 32 bit (Intel)] on win32

Type "copyright", "credits" or "license()" for more information.

>>> ================================ RESTART ================================

>>> 

enter number of rows : 3

enter number of coloumns : 3

entry elements

1

2

3

0

0

0

4

5

6

matrix is:

1 2 3 

0 0 0 

4 5 6 

number of zeros: 3

not sparse matrix

>>> ================================ RESTART ================================

>>> 

enter number of rows : 3

enter number of coloumns : 3

entry elements

1

2

3

0

0

0

0

0

4

matrix is:

1 2 3 

0 0 0 

0 0 4 

number of zeros: 5

sparse matrix

row col val

0 0 1

0 1 2

0 2 3

2 2 4

>>>

Now my new Blog on Fundamentals of Python can be found at https://fundamentalsofpython.blogspot.com/2020/02/list-manipulations.html

Sparse Matrix Using List

This is sparse matrix program. A matrix in which number of zeros are greater than half the size of matrix is known as sparse matrix.

Source Code:

row=int(input("enter number of rows : "))
col=int(input("enter number of coloumns : "))

X = [[0]*col for j in range(row)]
count=0

print ("entry elements")
for i in range (row):
  for j in range (col): 
    X[i][j] = int(input())

print("matrix is:")
for i in range(row):
    for j in range(col):
        print(X[i][j], end=' ')
    print()

for i in range(row):
    for j in range(col):
        if X[i][j]==0:
            count=count+1

print("number of zeros:",count)

if count>(row*col)//2:
    print("sparse matrix")
else:

    print("not sparse matrix")

Output:

Python 3.4.0 (v3.4.0:04f714765c13, Mar 16 2014, 19:24:06) [MSC v.1600 32 bit (Intel)] on win32

Type "copyright", "credits" or "license()" for more information.

>>> ================================ RESTART ================================

>>> 

enter number of rows : 3

enter number of coloumns : 3

entry elements

1

2

3

0

0

0

4

5

6

matrix is:

1 2 3 

0 0 0 

4 5 6 

number of zeros: 3

not sparse matrix

>>> ================================ RESTART ================================

>>> 

enter number of rows : 3

enter number of coloumns : 3

entry elements

1

2

3

0

0

0

0

4

5

matrix is:

1 2 3 

0 0 0 

0 4 5 

number of zeros: 4

not sparse matrix

>>> ================================ RESTART ================================

>>> 

enter number of rows : 3

enter number of coloumns : 3

entry elements

1

2

3

0

0

0

0

0

4

matrix is:

1 2 3 

0 0 0 

0 0 4 

number of zeros: 5

sparse matrix

>>>

Now my new Blog on Fundamentals of Python can be found at https://fundamentalsofpython.blogspot.com/2020/02/list-manipulations.html

Towers of Hanoi using python

This is Towers of Hanoi program. This concept uses three towers namely source, intermediate and destination. The concept is to place the disks from source tower to destination tower. Smaller disk should be always on larger disk vice versa is not possible. The order of disks on source tower and on destination tower should be same. This concept uses recursion.

Source code:

def hanoi(n,s,i,d):
    if n==1:
        print("move 1 disk from",s,"to",d)
        return
    else:
        hanoi(n-1,s,d,i)
        hanoi(1,s,i,d)
        hanoi(n-1,i,s,d)

n=int(input("enter no of disks"))
hanoi(n,"s","i","d")

 

Output:

Python 3.4.0 (v3.4.0:04f714765c13, Mar 16 2014, 19:24:06) [MSC v.1600 32 bit (Intel)] on win32

Type "copyright", "credits" or "license()" for more information.

>>> ================================ RESTART ================================

>>> 

enter no of disks3

move 1 disk from s to d

move 1 disk from s to i

move 1 disk from d to i

move 1 disk from s to d

move 1 disk from i to s

move 1 disk from i to d

move 1 disk from s to d

>>>
Now my new Blog on Fundamentals of Python can be found at https://fundamentalsofpython.blogspot.com/2020/02/list-manipulations.html

Queue using Linked list

This program is about Queue using Linked list. This program contains functions
1.Insert
2.Delete
3.Display

Source code:

class Node:
    def __init__(self,data):
        self.data=data
        self.next=None
class Queuell:
    def __init__(self):
        self.rear=None
        self.front=None
    def insert(self):
        data=int(input("enter data"))
        newnode=Node(data)
        if self.front == None:
            self.front=newnode
            self.rear=newnode
        else:
            self.rear.next=newnode
            self.rear=newnode
        print("element inserted")
    def delete(self):
        if self.front == None:
            print("empty")
        else:
            temp=self.front
            print("element deleted is %d" %(temp.data))
            self.front=self.front.next
            del temp

    def display(self):
        if self.front==None:
            print("empty")
        else:
            temp=self.front
            print("elements in Queue")
            while temp!=None:
                print("%d" %(temp.data))
                temp=temp.next
def menu():
    print("1.insert\n2.delete\n3.display\n4.quit")
def stop():
    print("you are about to terminate the program")
    exit(0)     
s=Queuell()
def default():
    print("check your input")
menu()
while True:
    menu= {
    1: s.insert,
    2: s.delete,
    3: s.display,
    4: stop}
    option = int(input("Please enter your choice"))

    menu.get(option,default)()

Output:

Python 3.4.0 (v3.4.0:04f714765c13, Mar 16 2014, 19:24:06) [MSC v.1600 32 bit (Intel)] on win32

Type "copyright", "credits" or "license()" for more information.

>>> ================================ RESTART ================================

>>> 

1.insert

2.delete

3.display

4.quit

Please enter your choice1

enter data1

element inserted

Please enter your choice1

enter data2

element inserted

Please enter your choice1

enter data3

element inserted

Please enter your choice3

elements in Queue

1

2

3

Please enter your choice2

element deleted is 1

Please enter your choice3

elements in Queue

2

3

Please enter your choice2

element deleted is 2

Please enter your choice3

elements in Queue

3

Please enter your choice2

element deleted is 3

Please enter your choice3

empty

Please enter your choice4
Now my new Blog on Fundamentals of Python can be found at https://fundamentalsofpython.blogspot.com/2020/02/list-manipulations.html

Stacks Using Linked list

This program is stacks using linked list. the program covers the following funtions:
1.Push
2.Pop
3.Display

Source Code:


class Node:
    def __init__(self,data):
        self.data=data
        self.next=None
class Stackll:
    def __init__(self):
        self.start=None
        self.top=None
    def push(self):
        data=int(input("enter data"))
        newnode=Node(data)
        if self.start==None:
           self.start=newnode
           self.top=newnode
        else:
            temp=self.start
            while temp.next!=None:
                temp=temp.next
            temp.next=newnode
            top=newnode
    def pop(self):
        temp=self.start
        if temp.next ==None:
            print ("last element of stack deleted is %d" %(temp.data))
            self.start=None
            del self.top
            self.top=None
        else:
            temp=self.start
            prev=self.start
            while temp.next != None:
                prev=temp
                temp=temp.next
         
            prev.next=None
            del temp
     
 
    def display(self):
        if self.top==None:
            print("stack empty")
        else:
            temp=self.start
            print("elements in stack are")
            while temp!=None:
                print ("%d" %(temp.data))
                temp=temp.next
             
def menu():
    print("1.push\n2.pop\n3.display\n4.quit")
def stop():
    print("you are about to terminate the program")
    exit(0)     
s=Stackll()
def default():
    print("check your input")
menu()
while True:
    menu= {
    1: s.push,
    2: s.pop,
    3: s.display,
    4: stop}
    option = int(input("Please enter your choice"))
    menu.get(option,default)()

Output:

Python 3.4.0 (v3.4.0:04f714765c13, Mar 16 2014, 19:24:06) [MSC v.1600 32 bit (Intel)] on win32
Type "copyright", "credits" or "license()" for more information.
>>> ================================ RESTART ================================
>>>
1.push
2.pop
3.display
4.quit
Please enter your choice1
enter data10
Please enter your choice1
enter data20
Please enter your choice1
enter data30
Please enter your choice3
elements in stack are
10
20
30
Please enter your choice2
Please enter your choice3
elements in stack are
10
20
Please enter your choice2
Please enter your choice3
elements in stack are
10
Please enter your choice2
last element of stack deleted is 10
Please enter your choice3
stack empty

Please enter your choice4

Now my new Blog on Fundamentals of Python can be found at https://fundamentalsofpython.blogspot.com/2020/02/list-manipulations.html