ડેટા સ્ટ્રક્ચર અને એપ્લિકેશન (1333203) - વિન્ટર 2023 સોલ્યુશન

class Student:
    # ક્લાસ એટ્રિબ્યુટ
    school = "GTU"
    
    # કન્સ્ટ્રક્ટર
    def __init__(self, roll_no, name):
        # ઇન્સ્ટન્સ એટ્રિબ્યુટ્સ
        self.roll_no = roll_no
        self.name = name
    
    # ઇન્સ્ટન્સ મેથડ
    def display(self):
        print(f"Roll No: {self.roll_no}, Name: {self.name}")
    
    # ક્લાસ મેથડ
    @classmethod
    def change_school(cls, new_school):
        cls.school = new_school

# ઓબ્જેક્ટ બનાવવું
student1 = Student(101, "રાજ")
student1.display()  # આઉટપુટ: Roll No: 101, Name: રાજ

# પોલીમોર્ફિઝમ ઉદાહરણ
class Animal:
    def speak(self):
        pass

class Dog(Animal):
    def speak(self):
        return "ભૌં ભૌં!"

class Cat(Animal):
    def speak(self):
        return "મ્યાઉં!"

class Duck(Animal):
    def speak(self):
        return "ક્વેક!"

# પોલીમોર્ફિઝમ દર્શાવતું ફંક્શન
def animal_sound(animal):
    return animal.speak()

# ઓબ્જેક્ટ્સ બનાવવા
dog = Dog()
cat = Cat()
duck = Duck()

# એક જ ફંક્શન વિવિધ પ્રાણી ઓબ્જેક્ટ્સ માટે કામ કરે છે
print(animal_sound(dog))   # આઉટપુટ: ભૌં ભૌં!
print(animal_sound(cat))   # આઉટપુટ: મ્યાઉં!
print(animal_sound(duck))  # આઉટપુટ: ક્વેક!

class Stack:
    def __init__(self, size):
        self.stack = []
        self.size = size
        self.top = -1
    
    def push(self, element):
        if self.top >= self.size - 1:
            return "Stack Overflow"
        else:
            self.top += 1
            self.stack.append(element)
            return "Pushed " + str(element)
    
    def pop(self):
        if self.top < 0:
            return "Stack Underflow"
        else:
            element = self.stack.pop()
            self.top -= 1
            return element

def factorial(n):
    # બેઝ કેસ
    if n == 0:
        return 1
    # રિકર્સિવ કેસ
    else:
        return n * factorial(n-1)

# ઉદાહરણ
result = factorial(5)  # 5! = 120

class Queue:
    def __init__(self, size):
        self.queue = []
        self.size = size
        self.front = 0
        self.rear = -1
        self.count = 0
    
    def enqueue(self, item):
        if self.count >= self.size:
            return "ક્યુ ભરેલી છે"
        else:
            self.rear += 1
            self.queue.append(item)
            self.count += 1
            return "Enqueued " + str(item)
    
    def dequeue(self):
        if self.count <= 0:
            return "ક્યુ ખાલી છે"
        else:
            item = self.queue.pop(0)
            self.count -= 1
            return item
    
    def display(self):
        return self.queue

# ટેસ્ટ
q = Queue(5)
q.enqueue(10)
q.enqueue(20)
q.enqueue(30)
print(q.display())  # [10, 20, 30]
print(q.dequeue())  # 10
print(q.display())  # [20, 30]

class Node:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None

def insert_at_beginning(head, data):
    new_node = Node(data)
    new_node.next = head
    return new_node  # નવો head

def insert_at_end(head, data):
    new_node = Node(data)
    new_node.next = None
    
    # જો લિન્ક્ડ લિસ્ટ ખાલી હોય
    if head is None:
        return new_node
    
    # છેલ્લા નોડ સુધી ટ્રાવર્સ કરો
    temp = head
    while temp.next:
        temp = temp.next
    
    # છેલ્લા નોડને નવા નોડ સાથે જોડો
    temp.next = new_node
    return head

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

# 3 નોડવાળી સર્ક્યુલર લિન્ક્ડ લિસ્ટ બનાવવી
head = Node(1)
node2 = Node(2)
node3 = Node(3)

head.next = node2
node2.next = node3
node3.next = head  # તેને સર્ક્યુલર બનાવે છે

def count_nodes(head):
    count = 0
    temp = head
    
    while temp:
        count += 1
        temp = temp.next
    
    return count

# ઉદાહરણ
# ધારી લો કે head લિન્ક્ડ લિસ્ટના પ્રથમ નોડને પોઇન્ટ કરે છે
total_nodes = count_nodes(head)
print(f"કુલ નોડ: {total_nodes}")

def selection_sort(arr):
    n = len(arr)
    
    for i in range(n):
        min_idx = i
        
        # અનસોર્ટેડ એરેમાં લઘુતમ એલિમેન્ટ શોધો
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        
        # શોધેલા લઘુતમ એલિમેન્ટને પ્રથમ એલિમેન્ટ સાથે સ્વેપ કરો
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

def bubble_sort(arr):
    n = len(arr)
    
    # બધા એરે એલિમેન્ટ્સ પર ટ્રાવર્સ કરો
    for i in range(n):
        # છેલ્લા i એલિમેન્ટ્સ પહેલેથી જ યોગ્ય જગ્યા પર છે
        for j in range(0, n-i-1):
            # જો વર્તમાન એલિમેન્ટ આગળના એલિમેન્ટ કરતાં મોટો હોય, તો સ્વેપ કરો
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    
    return arr

# ઇનપુટ લિસ્ટ
list1 = [5, 4, 3, 2, 1, 0]

# લિસ્ટ સોર્ટ કરવી
sorted_list = bubble_sort(list1)

# રિઝલ્ટ ડિસ્પ્લે કરવું
print("સોર્ટેડ લિસ્ટ:", sorted_list)
# આઉટપુટ: સોર્ટેડ લિસ્ટ: [0, 1, 2, 3, 4, 5]

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        
        # key કરતાં મોટા એલિમેન્ટ્સને એક પોઝિશન આગળ ખસેડો
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        
        arr[j + 1] = key

def selection_sort(arr):
    n = len(arr)
    
    for i in range(n):
        # બાકીના અનસોર્ટેડ એરેમાં લઘુતમ એલિમેન્ટ શોધો
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
                
        # શોધેલા લઘુતમ એલિમેન્ટને પ્રથમ એલિમેન્ટ સાથે સ્વેપ કરો
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    
    return arr

# ઇનપુટ લિસ્ટ
list1 = [6, 3, 25, 8, -1, 55, 0]

# લિસ્ટ સોર્ટ કરવી
sorted_list = selection_sort(list1)

# રિઝલ્ટ ડિસ્પ્લે કરવું
print("સોર્ટેડ લિસ્ટ:", sorted_list)
# આઉટપુટ: સોર્ટેડ લિસ્ટ: [-1, 0, 3, 6, 8, 25, 55]

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

# Binary Tree માં ઇન્સર્શન
def insert(root, data):
    if root is None:
        return Node(data)
    
    # લેવલ ઓર્ડર ટ્રાવર્સલથી ખાલી પોઝિશન શોધવી
    queue = []
    queue.append(root)
    
    while queue:
        temp = queue.pop(0)
        
        if temp.left is None:
            temp.left = Node(data)
            break
        else:
            queue.append(temp.left)
            
        if temp.right is None:
            temp.right = Node(data)
            break
        else:
            queue.append(temp.right)
    
    return root

# Binary Tree માંથી ડિલીશન
def delete_node(root, key):
    if root is None:
        return None
    
    if root.left is None and root.right is None:
        if root.data == key:
            return None
        else:
            return root
    
    # ડિલીટ કરવાના નોડને શોધો
    key_node = None
    # છેવટના નોડને શોધો
    last = None
    parent = None
    
    # લેવલ ઓર્ડર ટ્રાવર્સલ
    queue = []
    queue.append(root)
    
    while queue:
        temp = queue.pop(0)
        
        if temp.data == key:
            key_node = temp
            
        if temp.left:
            parent = temp
            queue.append(temp.left)
            last = temp.left
            
        if temp.right:
            parent = temp
            queue.append(temp.right)
            last = temp.right
    
    if key_node:
        # છેવટના નોડના ડેટા સાથે બદલો
        key_node.data = last.data
        
        # છેવટના નોડને ડિલીટ કરો
        if parent.right == last:
            parent.right = None
        else:
            parent.left = None
    
    return root

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

def insert(root, key):
    # જો ટ્રી ખાલી હોય, તો નવો નોડ પાછો આપો
    if root is None:
        return Node(key)
    
    # અન્યથા, ટ્રીમાં નીચે જાઓ
    if key < root.key:
        root.left = insert(root.left, key)
    else:
        root.right = insert(root.right, key)
    
    # અબદાયેલ નોડ પોઈન્ટર પાછો આપો
    return root

def inorder(root):
    if root:
        inorder(root.left)
        print(root.key, end=" ")
        inorder(root.right)

def preorder(root):
    if root:
        print(root.key, end=" ")
        preorder(root.left)
        preorder(root.right)

def postorder(root):
    if root:
        postorder(root.left)
        postorder(root.right)
        print(root.key, end=" ")

# ટેસ્ટ માટેનો પ્રોગ્રામ
def main():
    # આ એલિમેન્ટ્સ સાથે BST બનાવો: 50, 30, 20, 40, 70, 60, 80
    root = None
    elements = [50, 30, 20, 40, 70, 60, 80]
    
    for element in elements:
        root = insert(root, element)
    
    # ટ્રાવર્સલ્સ પ્રિન્ટ કરો
    print("ઇનઓર્ડર ટ્રાવર્સલ: ", end="")
    inorder(root)
    print("\nપ્રીઓર્ડર ટ્રાવર્સલ: ", end="")
    preorder(root)
    print("\nપોસ્ટઓર્ડર ટ્રાવર્સલ: ", end="")
    postorder(root)

# પ્રોગ્રામ ચલાવો
main()