3.1 Операції над даними: вставка, видалення, пошук
Вставка (Insert):
Операція додавання нового елемента у структуру даних. Вставка може відбуватись на початку, в кінці або у довільній позиції структури даних.
Видалення (Delete):
Операція видалення елемента зі структури даних. Видалення може відбуватись за значенням елемента, за індексом або за позицією елемента у структурі даних.
Пошук (Search):
Операція знаходження елемента у структурі даних. Пошук може відбуватись за значенням або за іншими критеріями.
Приклади операцій:
- Масиви: Вставка і видалення потребують зсуву елементів, що може бути затратним за часом —
O(n). - Зв'язані списки: Вставка і видалення можуть відбуватись за
O(1), якщо відома позиція вузла. - Хеш-таблиці: Пошук, вставка і видалення зазвичай виконуються за
O(1)в середньому випадку. - Дерева: Операції пошуку, вставки і видалення можуть виконуватись за
O(log n)в збалансованих деревах.
3.2 Базові поняття: масив, список, стек, черга
Масив
Масив — це послідовність елементів одного типу, до яких можна отримати доступ за індексом.
Складність операцій: Доступ за індексом — O(1), вставка і видалення — O(n).
Приклад: Створення масиву, зміна елемента і виведення результату
# Створюємо масив чисел
arr = [1, 2, 3, 4, 5]
# Змінюємо елемент з індексом 2 (третій елемент, оскільки індексація починається з 0)
arr[2] = 10
# Виводимо змінений масив
print(arr) # Вивід: [1, 2, 10, 4, 5]
# Додаємо новий елемент в кінець масиву
arr.append(6)
print(arr) # Вивід: [1, 2, 10, 4, 5, 6]
# Видаляємо елемент за індексом
del arr[1]
print(arr) # Вивід: [1, 10, 4, 5, 6]Список
Список — це колекція елементів, де кожен елемент містить посилання на наступний (однозв'язний список) або на наступний і попередній (двозв'язний список) елемент.
Складність операцій: Вставка і видалення — O(1) при відомій позиції, пошук — O(n).
Приклад: Створення простого однозв'язного списку і його обхід
# Визначаємо структуру вузла списку
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Створюємо однозв'язний список
node1 = Node("101")
node2 = Node("102")
node3 = Node("103")
# Зв'язуємо вузли
node1.next = node2
node2.next = node3
# Встановлюємо початок списку
list_head = node1
# Проходимо по списку і виводимо дані
current = list_head
while current:
print(current.data)
current = current.next
# Вивід:
# 101
# 102
# 103Стек (Stack)
Стек — це колекція елементів з принципом LIFO (Last In, First Out): останній додався — перший вийшов.
Складність операцій: Вставка (push) і видалення (pop) — O(1).
Приклад: Реалізація і використання стека для перевірки збалансованості дужок
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
# Перевіряємо різні вирази
print(is_balanced("({[]})")) # Вивід: True
print(is_balanced("([)]")) # Вивід: False
print(is_balanced("((")) # Вивід: FalseЧерга (Queue)
Черга — це колекція елементів з принципом FIFO (First In, First Out): перший додався — перший вийшов.
Складність операцій: Вставка (enqueue) і видалення (dequeue) — O(1).
Приклад: Реалізація і використання черги для симуляції обробки задач
from collections import deque
class TaskQueue:
def __init__(self):
self.queue = deque()
def add_task(self, task):
self.queue.append(task)
print(f"Задача '{task}' додана в чергу")
def process_task(self):
if self.queue:
task = self.queue.popleft()
print(f"Обробка задачі: '{task}'")
else:
print("Черга порожня")
def display_queue(self):
print("Поточна черга задач:", list(self.queue))
# Створюємо і використовуємо чергу задач
task_queue = TaskQueue()
task_queue.add_task("Відправити email")
task_queue.add_task("Оновити базу даних")
task_queue.add_task("Створити звіт")
task_queue.display_queue()
task_queue.process_task()
task_queue.process_task()
task_queue.display_queue()
# Вивід:
# Задача 'Відправити email' додана в чергу
# Задача 'Оновити базу даних' додана в чергу
# Задача 'Створити звіт' додана в чергу
# Поточна черга задач: ['Відправити email', 'Оновити базу даних', 'Створити звіт']
# Обробка задачі: 'Відправити email'
# Обробка задачі: 'Оновити базу даних'
# Поточна черга задач: ['Створити звіт']3.3 Відмінності між різними типами структур даних
Ось ключові відмінності між різними типами структур даних:
Масиви:
- Доступ: Швидкий доступ за індексом —
O(1). - Зміна розміру: Фіксований розмір, збільшення вимагає копіювання всіх елементів —
O(n). - Підходить для: Випадковий доступ до елементів, коли розмір даних відомий заздалегідь.
Зв'язані списки:
- Доступ: Повільний доступ за індексом —
O(n). - Зміна розміру: Легко змінюваний розмір, вставка і видалення займають
O(1). - Підходить для: Частого додавання і видалення елементів.
Стек:
- Принцип роботи:
LIFO. - Операції: Вставка і видалення тільки на одному кінці —
O(1). - Підходить для: Зворотного порядку виконання задач, управління викликами функцій.
Черга:
- Принцип роботи:
FIFO. - Операції: Вставка і видалення на різних кінцях —
O(1). - Підходить для: Управління задачами у порядку їх надходження.
3.4 Застосування різних структур даних
Приклади застосування різних структур даних на практиці:
Масиви
Збереження даних фіксованої довжини, таких як дні тижня або місяці в році.
Приклад: Використання масиву для роботи з днями тижня
# Створюємо масив з днями тижня
days = ["Понеділок", "Вівторок", "Середа", "Четвер", "П'ятниця", "Субота", "Неділя"]
# Отримуємо день тижня за індексом (наприклад, третій день)
print(days[2]) # Вивід: Середа
# Змінюємо назву дня
days[0] = "Понеділок (початок тижня)"
print(days[0]) # Вивід: Понеділок (початок тижня)
# Проходимо по всім дням тижня
for day in days:
print(day)
# Вивід:
# Понеділок (початок тижня)
# Вівторок
# Середа
# Четвер
# П'ятниця
# Субота
# НеділяЗв'язані списки
Реалізація динамічних колекцій, де елементи можуть додаватись і видалятись з середини колекції.
Приклад: Реалізація і використання зв'язаного списку для зберігання списку справ
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("Список справ порожній")
else:
while current:
print(f"- {current.task}")
current = current.next
# Створюємо і використовуємо список справ
todo = TodoList()
todo.add_task("Купити продукти")
todo.add_task("Зателефонувати мамі")
todo.add_task("Підготувати презентацію")
print("Мій список справ:")
todo.display_tasks()
# Вивід:
# Мій список справ:
# - Купити продукти
# - Зателефонувати мамі
# - Підготувати презентаціюСтек
Зворотний порядок виконання задач, наприклад, обробка викликів функцій у рекурсії, відміна операцій (undo).
Приклад: Використання стека для обертання рядка
def reverse_string(s):
stack = []
# Поміщаємо кожен символ рядка в стек
for char in s:
stack.append(char)
reversed_s = ''
# Виймаємо символи зі стека, формуючи зворотній рядок
while stack:
reversed_s += stack.pop()
return reversed_s
# Приклад використання
original = "Hello, World!"
reversed_str = reverse_string(original)
print(f"Оригінальний рядок: {original}")
print(f"Зворотній рядок: {reversed_str}")
# Вивід:
# Оригінальний рядок: Hello, World!
# Зворотній рядок: !dlroW ,olleHЧерга
Управління задачами в порядку їх надходження, наприклад, завдання на принтері, черги в обслуговуванні клієнтів.
Приклад: Симуляція черги друку документів
from collections import deque
class PrinterQueue:
def __init__(self):
self.queue = deque()
def add_document(self, document):
self.queue.append(document)
print(f"Документ '{document}' додано в чергу друку")
def print_document(self):
if self.queue:
document = self.queue.popleft()
print(f"Друк документа: '{document}'")
else:
print("Черга друку порожня")
def display_queue(self):
print("Поточна черга друку:", list(self.queue))
# Створюємо і використовуємо чергу друку
printer = PrinterQueue()
printer.add_document("Звіт")
printer.add_document("Презентація")
printer.add_document("Договір")
printer.display_queue()
printer.print_document()
printer.print_document()
printer.display_queue()
# Вивід:
# Документ 'Звіт' додано в чергу друку
# Документ 'Презентація' додано в чергу друку
# Документ 'Договір' додано в чергу друку
# Поточна черга друку: ['Звіт', 'Презентація', 'Договір']
# Друк документа: 'Звіт'
# Друк документа: 'Презентація'
# Поточна черга друку: ['Договір']
В цьому прикладі ми створили просту симуляцію черги друку. Документи додаються в кінець черги і друкуються в порядку їх надходження, що демонструє принцип FIFO (First In, First Out).