Podstawowe terminy i definicje

3.1 Operacje na danych: wstawianie, usuwanie, wyszukiwanie

Wstawianie (Insert):

Operacja dodawania nowego elementu do struktury danych. Wstawianie może mieć miejsce na początku, na końcu lub w dowolnej pozycji w strukturze danych.

Usuwanie (Delete):

Operacja usuwania elementu ze struktury danych. Usuwanie może odbywać się poprzez wartość elementu, indeks lub pozycję elementu w strukturze danych.

Wyszukiwanie (Search):

Operacja znajdowania elementu w strukturze danych. Wyszukiwanie może odbywać się poprzez wartość lub inne kryteria.

Przykłady operacji:

• Tablice: Wstawianie i usuwanie wymagają przesunięcia elementów, co może być czasochłonne — O(n).
• Listy połączone: Wstawianie i usuwanie mogą odbywać się za O(1), jeśli znana jest pozycja węzła.
• Tabele haszujące: Wyszukiwanie, wstawianie i usuwanie zwykle wykonuje się za O(1) w średnim przypadku.
• Drzewa: Operacje wyszukiwania, wstawiania i usuwania mogą być wykonywane za O(log n) w zrównoważonych drzewach.

3.2 Podstawowe pojęcia: tablica, lista, stos, kolejka

Tablica

Tablica — to sekwencja elementów jednego typu, do których można uzyskać dostęp przez indeks.

Złożoność operacji: Dostęp przez indeks — O(1), wstawianie i usuwanie — O(n).

Przykład: Tworzenie tablicy, zmiana elementu i wyświetlenie wyniku

# Tworzymy tablicę liczb
arr = [1, 2, 3, 4, 5]

# Zmieniamy element z indeksem 2 (trzeci element, bo indeksowanie zaczyna się od 0)
arr[2] = 10

# Wyświetlamy zmienioną tablicę
print(arr)  # Wyjście: [1, 2, 10, 4, 5]

# Dodajemy nowy element na koniec tablicy
arr.append(6)
print(arr)  # Wyjście: [1, 2, 10, 4, 5, 6]

# Usuwamy element po indeksie
del arr[1]
print(arr)  # Wyjście: [1, 10, 4, 5, 6]

Lista

Lista — to kolekcja elementów, gdzie każdy element zawiera odnośnik do następnego (lista jednokierunkowa) lub do następnego i poprzedniego (lista dwukierunkowa) elementu.

Złożoność operacji: Wstawianie i usuwanie — O(1) przy znanej pozycji, wyszukiwanie — O(n).

Przykład: Tworzenie prostej listy jednokierunkowej i jej przegląd

# Definiujemy strukturę węzła listy
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

# Tworzymy listę jednokierunkową
node1 = Node("101")
node2 = Node("102")
node3 = Node("103")

# Łączymy węzły
node1.next = node2
node2.next = node3

# Ustawiamy początek listy
list_head = node1

# Przechodzimy przez listę i wyświetlamy dane
current = list_head
while current:
    print(current.data)
    current = current.next

# Wyjście:
# 101
# 102
# 103

Stos (Stack)

Stos — to kolekcja elementów z zasadą LIFO (Last In, First Out): ostatni wszedł — pierwszy wyszedł.

Złożoność operacji: Wstawianie (push) i usuwanie (pop) — O(1).

Przykład: Implementacja i użycie stosu do sprawdzania zbalansowania nawiasów

def is_balanced(expression):
    stack = []
    opening = "({["
    closing = ")}]"
    pairs = {")": "(", "}": "{", "]": "["}
    
    for char in expression:
        if char in opening:
            stack.append(char)
        elif char in closing:
            if not stack or stack.pop() != pairs[char]:
                return False
    
    return len(stack) == 0

# Sprawdzamy różne wyrażenia
print(is_balanced("({[]})"))  # Wyjście: True
print(is_balanced("([)]"))    # Wyjście: False
print(is_balanced("(("))      # Wyjście: False

Kolejka (Queue)

Kolejka — to kolekcja elementów z zasadą FIFO (First In, First Out): pierwszy wszedł — pierwszy wyszedł.

Złożoność operacji: Wstawianie (enqueue) i usuwanie (dequeue) — O(1).

Przykład: Implementacja i użycie kolejki do symulacji przetwarzania zadań

from collections import deque

class TaskQueue:
    def __init__(self):
        self.queue = deque()

    def add_task(self, task):
        self.queue.append(task)
        print(f"Zadanie '{task}' dodane do kolejki")

    def process_task(self):
        if self.queue:
            task = self.queue.popleft()
            print(f"Przetwarzanie zadania: '{task}'")
        else:
            print("Kolejka jest pusta")

    def display_queue(self):
        print("Obecna kolejka zadań:", list(self.queue))

# Tworzymy i używamy kolejki zadań
task_queue = TaskQueue()

task_queue.add_task("Wysłać email")
task_queue.add_task("Zaktualizować bazę danych")
task_queue.add_task("Stworzyć raport")

task_queue.display_queue()

task_queue.process_task()
task_queue.process_task()

task_queue.display_queue()

# Wyjście:
# Zadanie 'Wysłać email' dodane do kolejki
# Zadanie 'Zaktualizować bazę danych' dodane do kolejki
# Zadanie 'Stworzyć raport' dodane do kolejki
# Obecna kolejka zadań: ['Wysłać email', 'Zaktualizować bazę danych', 'Stworzyć raport']
# Przetwarzanie zadania: 'Wysłać email'
# Przetwarzanie zadania: 'Zaktualizować bazę danych'
# Obecna kolejka zadań: ['Stworzyć raport']

3.3 Różnice między różnymi typami struktur danych

Oto kluczowe różnice między różnymi typami struktur danych:

Tablice:

• Dostęp: Szybki dostęp przez indeks — O(1).
• Zmiana rozmiaru: Stały rozmiar, zwiększenie wymaga kopiowania wszystkich elementów — O(n).
• Odpowiedni dla: Losowego dostępu do elementów, gdy rozmiar danych jest znany z góry.

Listy połączone:

• Dostęp: Wolny dostęp przez indeks — O(n).
• Zmiana rozmiaru: Łatwo zmieniany rozmiar, wstawianie i usuwanie zajmują O(1).
• Odpowiedni dla: Częstego dodawania i usuwania elementów.

Stos:

• Zasada działania: LIFO.
• Operacje: Wstawianie i usuwanie tylko na jednym końcu — O(1).
• Odpowiedni dla: Odwrotnego porządku wykonywania zadań, zarządzania wywołaniami funkcji.

Kolejka:

• Zasada działania: FIFO.
• Operacje: Wstawianie i usuwanie na różnych końcach — O(1).
• Odpowiedni dla: Zarządzania zadaniami w kolejności ich przyjścia.

3.4 Zastosowanie różnych struktur danych

Przykłady zastosowania różnych struktur danych w praktyce:

Tablice

Przechowywanie danych o ustalonej długości, takich jak dni tygodnia czy miesiące w roku.

Przykład: Użycie tablicy do pracy z dniami tygodnia

# Tworzymy tablicę z dniami tygodnia
days = ["Poniedziałek", "Wtorek", "Środa", "Czwartek", "Piątek", "Sobota", "Niedziela"]

# Uzyskujemy dzień tygodnia po indeksie (np. trzeci dzień)
print(days[2])  # Wyjście: Środa

# Zmieniamy nazwę dnia
days[0] = "Poniedziałek (początek tygodnia)"
print(days[0])  # Wyjście: Poniedziałek (początek tygodnia)

# Przechodzimy przez wszystkie dni tygodnia
for day in days:
    print(day)

# Wyjście:
# Poniedziałek (początek tygodnia)
# Wtorek
# Środa
# Czwartek
# Piątek
# Sobota
# Niedziela

Listy połączone

Implementacja dynamicznych kolekcji, gdzie elementy mogą być dodawane i usuwane z środka kolekcji.

Przykład: Implementacja i użycie listy połączonej do przechowywania listy zadań

class TodoItem:
    def __init__(self, task):
        self.task = task
        self.next = None

class TodoList:
    def __init__(self):
        self.head = None

    def add_task(self, task):
        new_item = TodoItem(task)
        if not self.head:
            self.head = new_item
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_item

    def display_tasks(self):
        current = self.head
        if not current:
            print("Lista zadań jest pusta")
        else:
            while current:
                print(f"- {current.task}")
                current = current.next

# Tworzymy i używamy listy zadań
todo = TodoList()
todo.add_task("Kupić produkty")
todo.add_task("Zadzwonić do mamy")
todo.add_task("Przygotować prezentację")

print("Moja lista zadań:")
todo.display_tasks()

# Wyjście:
# Moja lista zadań:
# - Kupić produkty
# - Zadzwonić do mamy
# - Przygotować prezentację

Stos

Odwrotny porządek wykonywania zadań, na przykład przetwarzanie wywołań funkcji w rekurencji, cofanie operacji (undo).

Przykład: Użycie stosu do odwracania łańcucha znaków

def reverse_string(s):
    stack = []
    # Umieszczamy każdy znak łańcucha na stosie
    for char in s:
        stack.append(char)
    
    reversed_s = ''
    # Wyciągamy znaki ze stosu, tworząc odwrotny łańcuch
    while stack:
        reversed_s += stack.pop()
    
    return reversed_s

# Przykład użycia
original = "Hello, World!"
reversed_str = reverse_string(original)
print(f"Łańcuch oryginalny: {original}")
print(f"Łańcuch odwrotny: {reversed_str}")

# Wyjście:
# Łańcuch oryginalny: Hello, World!
# Łańcuch odwrotny: !dlroW ,olleH

Kolejka

Zarządzanie zadaniami w kolejności ich przyjścia, na przykład zadania na drukarce, kolejki w obsłudze klienta.

Przykład: Symulacja kolejki drukowania dokumentów

from collections import deque

class PrinterQueue:
    def __init__(self):
        self.queue = deque()

    def add_document(self, document):
        self.queue.append(document)
        print(f"Dokument '{document}' dodany do kolejki drukowania")

    def print_document(self):
        if self.queue:
            document = self.queue.popleft()
            print(f"Drukowanie dokumentu: '{document}'")
        else:
            print("Kolejka drukowania jest pusta")

    def display_queue(self):
        print("Obecna kolejka drukowania:", list(self.queue))

# Tworzymy i używamy kolejki drukowania
printer = PrinterQueue()
printer.add_document("Raport")
printer.add_document("Prezentacja")
printer.add_document("Umowa")
printer.display_queue()
printer.print_document()
printer.print_document()
printer.display_queue()

# Wyjście:
# Dokument 'Raport' dodany do kolejki drukowania
# Dokument 'Prezentacja' dodany do kolejki drukowania
# Dokument 'Umowa' dodany do kolejki drukowania
# Obecna kolejka drukowania: ['Raport', 'Prezentacja', 'Umowa']
# Drukowanie dokumentu: 'Raport'
# Drukowanie dokumentu: 'Prezentacja'
# Obecna kolejka drukowania: ['Umowa']

W tym przykładzie stworzyliśmy prostą symulację kolejki drukowania. Dokumenty są dodawane na koniec kolejki i drukowane w kolejności ich przyjścia, co demonstruje zasadę FIFO (First In, First Out).