ડેટા સ્ટ્રક્ચર વિથ પાયથોન (4331601) - શિયાળા 2023 સોલ્યુશન

# Class definition
class Student:
    def __init__(self, name, age):
        self.name = name
        self.age = age
    
    def display(self):
        print(f"Name: {self.name}, Age: {self.age}")

# Object creation
student1 = Student("John", 20)
student1.display()

# Method 1: Simple Nested Loop નો ઉપયોગ
def matrix_multiply_nested(A, B):
    rows_A, cols_A = len(A), len(A[0])
    rows_B, cols_B = len(B), len(B[0])
    
    # Result matrix initialize કરો
    result = [[0 for _ in range(cols_B)] for _ in range(rows_A)]
    
    # Matrix multiplication
    for i in range(rows_A):
        for j in range(cols_B):
            for k in range(cols_A):
                result[i][j] += A[i][k] * B[k][j]
    
    return result

# Method 2: NumPy નો ઉપયોગ
import numpy as np

def matrix_multiply_numpy(A, B):
    A_np = np.array(A)
    B_np = np.array(B)
    return np.dot(A_np, B_np)

# ઉદાહરણ
A = [[1, 2], [3, 4]]
B = [[5, 6], [7, 8]]

print("Nested Loop Result:", matrix_multiply_nested(A, B))
print("NumPy Result:", matrix_multiply_numpy(A, B))

import array

# Array બનાવો
arr = array.array('i', [1, 2, 3, 4, 5])

def array_operations():
    print("મૂળ array:", arr)
    
    # Element insert કરો
    arr.insert(2, 10)
    print("insert(2, 10) પછી:", arr)
    
    # Element append કરો
    arr.append(6)
    print("append(6) પછી:", arr)
    
    # Element remove કરો
    arr.remove(10)
    print("remove(10) પછી:", arr)
    
    # Element pop કરો
    popped = arr.pop()
    print(f"Pop કરેલું element: {popped}, Array: {arr}")
    
    # Element શોધો
    index = arr.index(3)
    print(f"3 નું index: {index}")
    
    # Occurrences ગણો
    count = arr.count(2)
    print(f"2 નું count: {count}")

array_operations()

class MyClass:
    class_var = "હું class variable છું"
    
    @classmethod
    def class_method(cls):
        return f"Class method accessing: {cls.class_var}"
    
    @staticmethod
    def static_method():
        return "Static method - કોઈ class access નથી"

# ઉપયોગ
print(MyClass.class_method())
print(MyClass.static_method())

# Base class
class Vehicle:
    def __init__(self, brand, model):
        self.brand = brand          # Public attribute
        self._model = model         # Protected attribute
        self.__year = 2023          # Private attribute
    
    def start_engine(self):
        return f"{self.brand} engine શરૂ થયું"
    
    def _display_model(self):       # Protected method
        return f"Model: {self._model}"
    
    def __private_method(self):     # Private method
        return f"Year: {self.__year}"

# Derived class (Single level inheritance)
class Car(Vehicle):
    def __init__(self, brand, model, doors):
        super().__init__(brand, model)
        self.doors = doors
    
    def car_info(self):
        # Public અને protected members ને access કરી શકે
        return f"Car: {self.brand}, {self._display_model()}, Doors: {self.doors}"
    
    def demonstrate_access(self):
        print("Public access:", self.brand)
        print("Protected access:", self._model)
        # print("Private access:", self.__year)  # આ error આપશે

# ઉપયોગ
my_car = Car("Toyota", "Camry", 4)
print(my_car.car_info())
print(my_car.start_engine())
my_car.demonstrate_access()

class Student:
    def __init__(self, name="અજ્ઞાત", age=18):  # Constructor
        self.name = name
        self.age = age
        print(f"Student {name} બનાવ્યો")
    
    def display(self):
        print(f"નામ: {self.name}, ઉંમર: {self.age}")

# Object creation automatically constructor ને call કરે છે
s1 = Student("Alice", 20)
s2 = Student()  # Default values ઉપયોગ કરે

# Base class
class Animal:
    def make_sound(self):
        pass

# Derived classes
class Dog(Animal):
    def make_sound(self):
        return "ભોંભોં!"

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

class Cow(Animal):
    def make_sound(self):
        return "હંભા!"

# Polymorphism demonstration
def animal_sound(animal):
    return animal.make_sound()

# Objects બનાવવા
animals = [Dog(), Cat(), Cow()]

# સમાન method call, અલગ behavior
for animal in animals:
    print(f"{animal.__class__.__name__}: {animal_sound(animal)}")

# Multiple Inheritance
class Teacher:
    def __init__(self, subject):
        self.subject = subject
    
    def teach(self):
        return f"{self.subject} શીખવાડવું"

class Researcher:
    def __init__(self, field):
        self.field = field
    
    def research(self):
        return f"{self.field} માં સંશોધન કરવું"

# Multiple inheritance
class Professor(Teacher, Researcher):
    def __init__(self, name, subject, field):
        self.name = name
        Teacher.__init__(self, subject)
        Researcher.__init__(self, field)
    
    def profile(self):
        return f"પ્રોફેસર {self.name}: {self.teach()} અને {self.research()}"

# Hierarchical Inheritance
class Vehicle:
    def __init__(self, brand):
        self.brand = brand
    
    def start(self):
        return f"{self.brand} શરૂ થયું"

class Car(Vehicle):
    def drive(self):
        return f"{self.brand} કાર ચાલે છે"

class Bike(Vehicle):
    def ride(self):
        return f"{self.brand} બાઇક ચાલે છે"

# ઉપયોગ
prof = Professor("સ્મિથ", "પાયથોન", "AI")
print(prof.profile())

car = Car("Honda")
bike = Bike("Yamaha")
print(car.drive())
print(bike.ride())

stack = []

# Push operation
stack.append(10)  # 10 Push કરો
stack.append(20)  # 20 Push કરો
print("Push પછી:", stack)  # [10, 20]

# Pop operation
item = stack.pop()  # 20 Pop કરો
print(f"Pop કર્યું: {item}, Stack: {stack}")  # [10]

from collections import deque

queue = deque()

# Enqueue operation
queue.append(10)  # 10 Enqueue કરો
queue.append(20)  # 20 Enqueue કરો
print("Enqueue પછી:", list(queue))  # [10, 20]

# Dequeue operation
item = queue.popleft()  # 10 Dequeue કરો
print(f"Dequeue કર્યું: {item}, Queue: {list(queue)}")  # [20]

# ઉદાહરણ: Parentheses matching
def is_balanced(expression):
    stack = []
    pairs = {'(': ')', '[': ']', '{': '}'}
    
    for char in expression:
        if char in pairs:  # Opening bracket
            stack.append(char)
        elif char in pairs.values():  # Closing bracket
            if not stack:
                return False
            if pairs[stack.pop()] != char:
                return False
    
    return len(stack) == 0

# ટેસ્ટ
print(is_balanced("({[]})"))  # True
print(is_balanced("({[}])"))  # False

# Circular Queue Implementation
class CircularQueue:
    def __init__(self, size):
        self.size = size
        self.queue = [None] * size
        self.front = -1
        self.rear = -1
    
    def enqueue(self, item):
        if (self.rear + 1) % self.size == self.front:
            print("Queue ભરાઈ ગયું")
            return
        if self.front == -1:
            self.front = 0
        self.rear = (self.rear + 1) % self.size
        self.queue[self.rear] = item
    
    def dequeue(self):
        if self.front == -1:
            print("Queue ખાલી છે")
            return None
        item = self.queue[self.front]
        if self.front == self.rear:
            self.front = self.rear = -1
        else:
            self.front = (self.front + 1) % self.size
        return item

def infix_to_postfix(expression):
    precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}
    stack = []
    output = []
    
    for char in expression:
        if char.isalnum():
            output.append(char)
        elif char == '(':
            stack.append(char)
        elif char == ')':
            while stack and stack[-1] != '(':
                output.append(stack.pop())
            stack.pop()  # '(' દૂર કરો
        elif char in precedence:
            while (stack and stack[-1] != '(' and 
                   stack[-1] in precedence and
                   precedence[stack[-1]] >= precedence[char]):
                output.append(stack.pop())
            stack.append(char)
    
    while stack:
        output.append(stack.pop())
    
    return ''.join(output)

# ટેસ્ટ
result = infix_to_postfix("(a*b)*(c^(d+e)-f)")
print("Postfix:", result)  # ab*cde+^f-*

# Singly Linked List Node
class SinglyNode:
    def __init__(self, data):
        self.data = data
        self.next = None

# Circular Linked List Node
class CircularNode:
    def __init__(self, data):
        self.data = data
        self.next = None

def traverse_singly(head):
    current = head
    while current:  # NULL પર અટકે
        print(current.data)
        current = current.next

def traverse_circular(head):
    if not head:
        return
    current = head
    while True:
        print(current.data)
        current = current.next
        if current == head:  # શરૂઆતમાં પાછા
            break

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

class SinglyLinkedList:
    def __init__(self):
        self.head = None
    
    def insert_at_beginning(self, data):
        """શરૂઆતમાં node insert કરો"""
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node
        print(f"{data} શરૂઆતમાં insert કર્યું")
    
    def insert_at_end(self, data):
        """અંતે node insert કરો"""
        new_node = Node(data)
        
        if not self.head:  # ખાલી list
            self.head = new_node
            print(f"{data} અંતે insert કર્યું (પહેલો node)")
            return
        
        # છેલ્લા node સુધી traverse કરો
        current = self.head
        while current.next:
            current = current.next
        
        current.next = new_node
        print(f"{data} અંતે insert કર્યું")
    
    def display(self):
        """Linked list દર્શાવો"""
        if not self.head:
            print("List ખાલી છે")
            return
        
        current = self.head
        elements = []
        while current:
            elements.append(str(current.data))
            current = current.next
        
        print(" → ".join(elements) + " → NULL")

# ઉપયોગનું ઉદાહરણ
sll = SinglyLinkedList()

# શરૂઆતમાં insert કરો
sll.insert_at_beginning(10)
sll.insert_at_beginning(20)
sll.display()  # 20 → 10 → NULL

# અંતે insert કરો
sll.insert_at_end(30)
sll.insert_at_end(40)
sll.display()  # 20 → 10 → 30 → 40 → NULL

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

# માળખાનું visualization
# NULL ← [prev|data|next] ⇄ [prev|data|next] → NULL

# ઉદાહરણ: Doubly Linked List વાપરીને Browser History
class Page:
    def __init__(self, url):
        self.url = url
        self.prev = None
        self.next = None

class BrowserHistory:
    def __init__(self):
        self.current = None
    
    def visit(self, url):
        page = Page(url)
        if self.current:
            self.current.next = page
            page.prev = self.current
        self.current = page
    
    def back(self):
        if self.current and self.current.prev:
            self.current = self.current.prev
            return self.current.url
        return "કોઈ પાછલું page નથી"
    
    def forward(self):
        if self.current and self.current.next:
            self.current = self.current.next
            return self.current.url
        return "કોઈ આગલું page નથી"

def merge_sort(arr):
    """Merge Sort implementation"""
    if len(arr) <= 1:
        return arr
    
    # Array ને બે ભાગમાં વહેંચો
    mid = len(arr) // 2
    left_half = arr[:mid]
    right_half = arr[mid:]
    
    # બંને ભાગો recursively sort કરો
    left_sorted = merge_sort(left_half)
    right_sorted = merge_sort(right_half)
    
    # Sorted ભાગોને merge કરો
    return merge(left_sorted, right_sorted)

def merge(left, right):
    """બે sorted arrays ને merge કરો"""
    result = []
    i = j = 0
    
    # Elements compare કરીને merge કરો
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    # બાકીના elements ઉમેરો
    result.extend(left[i:])
    result.extend(right[j:])
    
    return result

# ઉદાહરણ
def demonstrate_merge_sort():
    arr = [64, 34, 25, 12, 22, 11, 90]
    print("મૂળ array:", arr)
    
    sorted_arr = merge_sort(arr)
    print("Sorted array:", sorted_arr)

demonstrate_merge_sort()

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

class BinarySearchTree:
    def __init__(self):
        self.root = None
    
    def insert(self, data):
        """BST માં node insert કરો"""
        if self.root is None:
            self.root = TreeNode(data)
        else:
            self._insert_recursive(self.root, data)
    
    def _insert_recursive(self, node, data):
        if data < node.data:
            if node.left is None:
                node.left = TreeNode(data)
            else:
                self._insert_recursive(node.left, data)
        elif data > node.data:
            if node.right is None:
                node.right = TreeNode(data)
            else:
                self._insert_recursive(node.right, data)
    
    def search(self, data):
        """BST માં node શોધો"""
        return self._search_recursive(self.root, data)
    
    def _search_recursive(self, node, data):
        if node is None or node.data == data:
            return node
        
        if data < node.data:
            return self._search_recursive(node.left, data)
        else:
            return self._search_recursive(node.right, data)
    
    def inorder_traversal(self):
        """Inorder traversal (ડાબે, રૂટ, જમણે)"""
        result = []
        self._inorder_recursive(self.root, result)
        return result
    
    def _inorder_recursive(self, node, result):
        if node:
            self._inorder_recursive(node.left, result)
            result.append(node.data)
            self._inorder_recursive(node.right, result)
    
    def display_tree(self):
        """સાદું tree display"""
        if self.root:
            self._display_recursive(self.root, 0)
    
    def _display_recursive(self, node, level):
        if node:
            self._display_recursive(node.right, level + 1)
            print("  " * level + str(node.data))
            self._display_recursive(node.left, level + 1)

# ઉદાહરણ
bst = BinarySearchTree()
values = [50, 30, 70, 20, 40, 60, 80]

print("મૂલ્યો insert કરી રહ્યા છીએ:", values)
for value in values:
    bst.insert(value)

print("\nTree structure:")
bst.display_tree()

print("\nInorder traversal:", bst.inorder_traversal())

# Search ઉદાહરણો
print(f"\n40 શોધો: {'મળ્યું' if bst.search(40) else 'મળ્યું નહીં'}")
print(f"90 શોધો: {'મળ્યું' if bst.search(90) else 'મળ્યું નહીં'}")

class CompleteBinaryTree:
    def __init__(self):
        self.tree = []
    
    def insert(self, data):
        """Complete binary tree રીતે insert કરો"""
        self.tree.append(data)
    
    def get_parent_index(self, i):
        return (i - 1) // 2
    
    def get_left_child_index(self, i):
        return 2 * i + 1
    
    def get_right_child_index(self, i):
        return 2 * i + 2
    
    def display_level_order(self):
        """Tree ને level દ્વારા દર્શાવો"""
        if not self.tree:
            return
        
        level = 0
        while (2 ** level) <= len(self.tree):
            start = 2 ** level - 1
            end = min(2 ** (level + 1) - 1, len(self.tree))
            print(f"Level {level}: {self.tree[start:end]}")
            level += 1

# ઉદાહરણ
cbt = CompleteBinaryTree()
for i in [1, 2, 3, 4, 5, 6]:
    cbt.insert(i)

cbt.display_level_order()

# Construction માટે implementation code
class BST:
    def __init__(self):
        self.root = None
    
    def insert(self, data):
        if self.root is None:
            self.root = TreeNode(data)
            print(f"{data} ને root તરીકે insert કર્યું")
        else:
            self._insert(self.root, data)
    
    def _insert(self, node, data):
        if data < node.data:
            if node.left is None:
                node.left = TreeNode(data)
                print(f"{data} ને {node.data} ના ડાબે insert કર્યું")
            else:
                self._insert(node.left, data)
        else:
            if node.right is None:
                node.right = TreeNode(data)
                print(f"{data} ને {node.data} ના જમણે insert કર્યું")
            else:
                self._insert(node.right, data)

# BST બનાવો
bst = BST()
sequence = [50, 70, 60, 20, 90, 10, 40, 100]

for num in sequence:
    bst.insert(num)