4.1 Визначення масиву і його властивості
Масив — це структура даних, що являє собою упорядкований набір елементів одного типу, розташованих у суміжних комірках пам'яті. Кожен елемент масиву має унікальний індекс, який використовується для доступу до нього.
Тут показаний простий масив розміром 4, що містить елементи (1, 2, 3 і 4).
Властивості масиву:
- Фіксований розмір: Розмір масиву задається при його створенні і не може змінюватися під час виконання програми.
- Однорідність елементів: Всі елементи масиву мають бути одного типу (наприклад, цілі числа, строки).
- Послідовне розташування в пам'яті: Елементи масиву зберігаються у суміжних комірках пам'яті, що забезпечує швидкий доступ по індексу.
- Швидкий доступ по індексу: Доступ до будь-якого елемента масиву здійснюється за сталий час
O(1).
4.2 Приклади використання масивів
Давайте розглянемо приклади використання масивів, які ви вже можете знати:
Зберігання даних фіксованої довжини
Дні тижня, місяці року:
# Створення масиву з днями тижня
days_of_week = ["Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday"]
print(days_of_week[2]) # Вивід: Wednesday
Матриці та багатовимірні масиви
Матриця 3x3:
# Створення матриці 3x3
matrix = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
print(matrix[1][1]) # Вивід: 5
Використання в алгоритмах сортування
Сортування масиву чисел:
# Сортування масиву чисел
numbers = [5, 2, 9, 1, 5, 6]
numbers.sort() # Сортування масиву
print(numbers) # Вивід: [1, 2, 5, 5, 6, 9]
Буфер для зберігання тимчасових даних
Буфер для читання даних з файлу:
# Створення буфера розміром 1024 байти
buffer = [0] * 1024
print(len(buffer)) # Вивід: 1024
4.3 Основні операції з масивами
Важливо! Клас list в Python є динамічним масивом, він може змінювати свій розмір під час роботи. Більш докладно про динамічні масиви ви дізнаєтеся через кілька лекцій.
Основні операції: доступ за індексом, вставка, видалення
Доступ за індексом
Доступ до елемента масиву здійснюється за допомогою індексу, який вказує на його позицію.
# Доступ до елементів масиву за індексом
arr = [10, 20, 30, 40, 50]
print(arr[2]) # Вивід: 30
print(arr[-1]) # Вивід: 50 (останній елемент)
Вставка
Вставка елемента в масив може вимагати зсуву всіх подальших елементів, щоб звільнити місце для нового елемента.
Приклад (вставка елемента в середину масиву):
# Вставка елемента в масив
arr = [10, 20, 30, 40, 50]
arr.insert(2, 25) # Вставка 25 на позицію 2
print(arr) # Вивід: [10, 20, 25, 30, 40, 50]
Видалення
Видалення елемента з масиву може вимагати зсуву всіх подальших елементів, щоб заповнити звільнене місце.
Приклад (видалення елемента):
# Видалення елемента з масиву
arr = [10, 20, 30, 40, 50]
arr.pop(2) # Видалення елемента на позиції 2
print(arr) # Вивід: [10, 20, 40, 50]
4.4 Переваги та недоліки використання масивів
Розглянемо переваги та недоліки використання масивів:
Переваги:
- Швидкий доступ за індексом: Доступ до будь-якого елемента масиву здійснюється за сталий час
O(1), що робить масиви дуже ефективними для читання даних. - Простота реалізації: Масиви прості в розумінні та використанні, їх легко реалізувати та застосовувати в різних задачах.
- Низькі накладні витрати: Масиви займають менше пам'яті порівняно з більш складними структурами даних, такими як зв'язані списки.
Недоліки:
- Фіксований розмір: Розмір масиву задається при його створенні і не може бути змінений. Це означає, що потрібно заздалегідь знати необхідний розмір масиву або використовувати динамічні масиви, які можуть збільшуватися за необхідністю.
- Витрати на вставку та видалення: Вставка та видалення елементів можуть бути затратними по часу, так як вимагають зсуву елементів. В найгіршому випадку вставка або видалення елемента в середині масиву займає
O(n)часу. - Неефективне використання пам'яті: Якщо масив використовується не повністю, то залишені комірки пам'яті залишаються незаповненими, що може призвести до неефективного використання пам'яті.
ПЕРЕЙДІТЬ В ПОВНУ ВЕРСІЮ