:Data-Structures:-
• The logical or mathematical model of a particular organization of data is called data structure. It is a way of storing, accessing, manipulating data.
• Types of data structure:
Data Structures
|
|-Linear
| |-Arrays
| |-Linked List
| |-Stacks
| |-Queues
|
|-Non-Linear
|- Trees
|- Graphs
|- Tables
|- Sets
• Operation on data structure:
Traversing: – Accessing each record exactly once.
Insertion: – Adding a new element to the structure.
Deletion: – Removing element from the structure.
Searching: – Search the element in a structure.
Sorting: – Arrange the elements in ascending and descending order.
Merging: – Joining two data structures of same type.
• List: – An array or list is the collection of elements in ordered way.
• There are two types of arrays:
– One dimensional list (1-D Lists)
– Multi-dimensional list (Nested Lists)
• Traversing 1-D array (List):
L = [10, 20, 30, 40, 50]
for i in L:
print (i)
Output:
10
20
30
40
50
>>>
• Inserting Element in a list: There are two ways to insert an element in a list.
– If the array is not sorted
– If the array is sorted
• If the array is not sorted: In this case, enter the element at any position using insert() function or add the element in the last of the array using append() function.
Example:
L = [15, 8, 25, 45, 13, 19]
L.insert(3,88) # insert element at the index 3
print(L)
Output:
[15, 8, 25, 88, 45, 13, 19]
• If the array is sorted: In this case, import bisect module and use the functions bisect() and insort(). bisect(): identifies the correct index for the element and returns the index. insort(): Inserts the element in the list in its correct order.
• Deletion of an element from a List: To delete an element from a list we can use remove() or pop() method.
Example:
L= [10, 15, 35, 12, 38, 74, 12]
val=int(input("Enter the element that you want to delete: "))
print ("List Before deletion of element: ", L)
L.remove(val)
print("After deletion the element ", val," the list is: ", L)
Output:
Enter the element that you want to delete: 12
List Before deletion of element: [10, 15, 35, 12, 38, 74, 12]
After deletion the element 12 the list is: [10, 15, 35, 38, 74, 12]
>>>
• Searching in a List: There are two types of searching techniques we can use to search an element in a list. These are:
– Linear Search
-Binary Search
(i) Linear Search: It is a simple searching technique.
Program:
L = eval(input("Enter the elements: "))
n = len(L)
item = eval(input("Enter the element that you want to search: "))
count = 0
for i in range(n):
if L[i]==item:
print("Element found at the position :", i+1)
count += 1
break
if count == 0:
print("Element not Found")
Output:
Enter the elements: 5,3,9,6,8,7,1
Enter the element that you want to search: 6
Element found at the position: 4
>>>
(ii) Binary Search:
Binary search can work for only sorted arrays whereas linear search can work for both sorted as well as unsorted arrays.
You can understand binary search method by following program: –
def bisearch (ar, key):
low = 0
high = len(ar)-1
while low <= high :
mid = int ((low+high)/2)
if key == ar[mid]:
return mid
elif key < ar [mid]:
high = mid - 1
else :
low = mid +1
else : # loop else
return -999
ar = [12,16,19,21,26,59,86,92,97]
item = int (input("Enter search item : " ))
res = bisearch(ar , item)
if res >= 0:
print (item , "FOUND at index ", res+1)
else :
print ("Sorry ! ",item ,"Not FOUND in array")
Output:
Enter search item: 19
19 FOUND at index 2
>>>
Linear Search
– Access of elements sequentially.
– Elements may or may not be in sorted order.
– Takes more time to search an element.
– Easy
– Efficient for small array.
Binary Search
– Access of elements randomly.
– Elements must be in sorted order i.e. ascending or descending order
– Takes less time to search an element.
– Tricky
– Efficient for larger array
• Sorting: To arrange the elements in ascending or descending order. There are many sorting techniques.
Program:
L = eval(input("Enter the elements:"))
n=len(L)
for p in range(0, n-1):
for i in range(0, n-1):
if L[i] > L[i+1]:
L[i], L[i+1] = L[i+1], L[i]
print("The sorted list is : ", L)
Output:
Enter the elements:[5,3,26,4,9]
The sorted list is: [3, 4, 5, 9, 26]
>>>
• Stack: It is a linear data structure. Stack is a list of elements in which an element may be inserted or deleted only at one end, called the TOP of the stack. It follows the principle Last in First out (LIFO).
• There are two basic operations associated with stack: –
– Push: Insert the element in stack
– Pop: Delete the element from stack
• Menu based program for stack:
S= []
from os import system
#menu display
def menu():
ch = 0
while(ch<1 or ch>4):
#print("\n" 100)
anyvar = system("cls")
print("\n\n\n\n\n")
print ("\t\t\t1: PUSH")
print ("\t\t\t2: POP")
print ("\t\t\t3: DISPLAY")
print("\t\t\t4: EXIT")
ch = int(input("\n\t\tEnter a choise (1- 4):"))
return ch
def push():
#code to push an item
item = int(input("\t\t\tEnter an item to push: "))
S.append(item)
print("\t\t\t ITEM", item," PUSHESD IN THE STACK")
def pop():
#code to pop from stack
if (S == []):
prínt ("\t\t\t NO ITEM TO POP")
else:
item = S.pop()
print ("\t\t\t ITEM ", item," POPPED FROM THE STACK")
def display():
#code to display stack
if (S== []):
print ("\t\t\tEMPTY STACK")
else:
print ("\t\t\t",)
for i in S:
print( i, '', end="")
#code to call all functions
import sys
ch = 0
while(ch != 4):
ch=menu()
if(ch == 1):
push()
elif(ch == 2):
pop()
elif(ch == 3):
display()
elif(ch == 4):
print ("\t\t\t ABORTING PROGRAM.")
sys.exit()
anyvar = input("\n\t\t\tPress any key to continue... \n")
• QUEUE: Queue is a linear data structure. Queue is a list of elements in which insertion takes place at one end called REAR and deletion takes place only at the other end, called the FRONT. It follows the principle First In First Out (FIFO).
• There are two basic operations associated with stack:
– Enqueue: Insert the element in queue
– Dequeue : Delete the element from queue.
• Menu based program for queue:
Q = []
from os import system
#menu display
def menu():
ch = 0
while(ch<1 or ch>4):
#print ("\n"*100)
anyvar = system("cls")
print ("\n\n\n\n\n")
print ("\t\t\t1: INSERT")
print ("\t\t\t2: DELETE")
print ("\t\t\t3: DISPLAY")
print ("\t\t\t4: EXIT")
ch = int(input("\n\t\t\tEnter a choise (1-4): "))
return ch
def insert():
#code to insert an item
item = int(input("\t\t\tEnter an item to insert: "))
Q.append(item)
print("\t\t\tITEM", item," INSERTED IN THE QUEUE")
def delete():
#code to delete from queue
if (Q == []):
print ("\t\t\tNO ITEM TO DELETE")
else:
item = Q.pop(0)
print ("\t\t\t ITEM", item," DELETED FROM THE QUEUE")
def display():
#code to display stack
if (Q == [] ):
print ("\t\t EMPTY QUEUE")
else:
print ("\t\t\t",)
for i in Q:
print (i, '', end = " ")
#code to call all functions
import sys
ch = 0
while(ch != 4):
ch = menu()
if(ch == 1):
insert()
elif (ch == 2):
delete()
elif(ch == 3):
display()
elif(ch == 4):
print("\t\t\tABORTING PROGRAM.")
sys.exit()
anyvar = input("\n\t\t\tPress any key to continue... \n")
Discover more from EduGrown School
Subscribe to get the latest posts sent to your email.