Tablice

4.1 Definicja tablicy i jej właściwości

Tablica to struktura danych, która jest uporządkowanym zbiorem elementów jednego typu, umieszczonymi w przyległych komórkach pamięci. Każdy element tablicy ma unikalny indeks, używany do uzyskania do niego dostępu.

Oto prosta tablica o rozmiarze 4, zawierająca elementy (1, 2, 3 i 4).

Właściwości tablicy:

• Stały rozmiar: Rozmiar tablicy jest określany podczas jej tworzenia i nie może być zmieniany w trakcie działania programu.
• Jednorodność elementów: Wszystkie elementy tablicy muszą być tego samego typu (np. liczby całkowite, napisy).
• Sekwencyjne rozmieszczenie w pamięci: Elementy tablicy przechowywane są w przyległych komórkach pamięci, co zapewnia szybki dostęp po indeksie.
• Szybki dostęp po indeksie: Dostęp do dowolnego elementu tablicy odbywa się w stałym czasie O(1).

4.2 Przykłady użycia tablic

Zobaczmy przykłady użycia tablic, które być może już znasz:

Przechowywanie danych o stałej długości

Dni tygodnia, miesiące roku:

# Tworzenie tablicy z dniami tygodnia
days_of_week = ["Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday"]
print(days_of_week[2])  # Wyjście: Wednesday

Macierze i tablice wielowymiarowe

Macierz 3x3:

# Tworzenie macierzy 3x3
matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]
print(matrix[1][1])  # Wyjście: 5

Użycie w algorytmach sortowania

Sortowanie tablicy liczb:

# Sortowanie tablicy liczb
numbers = [5, 2, 9, 1, 5, 6]
numbers.sort()  # Sortowanie tablicy
print(numbers)  # Wyjście: [1, 2, 5, 5, 6, 9]

Bufor do przechowywania danych tymczasowych

Bufor do czytania danych z pliku:

# Tworzenie bufora o rozmiarze 1024 bajtów
buffer = [0] * 1024
print(len(buffer))  # Wyjście: 1024

4.3 Podstawowe operacje na tablicach

Ważne! Klasa list w Pythonie jest dynamiczną tablicą, może więc zmieniać swój rozmiar podczas działania programu. Więcej o dynamicznych tablicach dowiecie się w kolejnych wykładach.

Podstawowe operacje: dostęp po indeksie, wstawianie, usuwanie

Dostęp po indeksie

Dostęp do elementu tablicy realizowany jest za pomocą indeksu, który wskazuje na jego pozycję.

# Dostęp do elementów tablicy po indeksie
arr = [10, 20, 30, 40, 50]
print(arr[2])  # Wyjście: 30
print(arr[-1])  # Wyjście: 50 (ostatni element)

Wstawianie

Wstawienie elementu do tablicy może wymagać przesunięcia wszystkich kolejnych elementów, aby zrobić miejsce na nowy element.

Przykład (wstawienie elementu w środek tablicy):

# Wstawienie elementu do tablicy
arr = [10, 20, 30, 40, 50]
arr.insert(2, 25)  # Wstawienie 25 na pozycję 2
print(arr)  # Wyjście: [10, 20, 25, 30, 40, 50]

Usuwanie

Usunięcie elementu z tablicy może wymagać przesunięcia wszystkich kolejnych elementów, aby wypełnić zwolnione miejsce.

Przykład (usunięcie elementu):

# Usunięcie elementu z tablicy
arr = [10, 20, 30, 40, 50]
arr.pop(2)  # Usunięcie elementu na pozycji 2
print(arr)  # Wyjście: [10, 20, 40, 50]

4.4 Zalety i wady użycia tablic

Zobaczmy zalety i wady użycia tablic:

Zalety:

• Szybki dostęp po indeksie: Dostęp do dowolnego elementu tablicy odbywa się w stałym czasie O(1), co czyni tablice bardzo efektywnymi do odczytu danych.
• Prostota implementacji: Tablice są łatwe do zrozumienia i używania, łatwo je zaimplementować i zastosować w różnych zadaniach.
• Niskie koszty dodatkowe: Tablice zajmują mniej pamięci w porównaniu do bardziej złożonych struktur danych, jak listy wiązane.

Wady:

• Stały rozmiar: Rozmiar tablicy jest ustalany podczas jej tworzenia i nie może być zmieniany. To oznacza, że trzeba z góry znać potrzebny rozmiar tablicy lub używać dynamicznych tablic, które mogą się powiększać w miarę potrzeb.
• Koszty wstawiania i usuwania: Wstawienie i usunięcie elementów może być czasochłonne, ponieważ wymaga przesunięcia elementów. W najgorszym przypadku wstawienie lub usunięcie elementu w środku tablicy zajmuje O(n) czasu.
• Nieefektywne użycie pamięci: Jeśli tablica nie jest w pełni wykorzystywana, wtedy pozostałe komórki pamięci pozostają niewypełnione, co może prowadzić do nieefektywnego wykorzystania pamięci.