Słowniki (Python) i Mapy (C++) na Maturze z Informatyki
Słownik (w Pythonie `dict`) lub mapa (w C++ `std::map`) to jedna z najważniejszych struktur danych, jakie poznasz. Zapomnij o indeksach 0, 1, 2... Tutaj sam decydujesz, jaki jest 'indeks'. Działa to jak prawdziwy słownik: masz unikalne klucze (np. słowo 'jabłko') i przypisane do nich wartości (np. definicję 'czerwony owoc'). Zamiast pytać 'co jest na pozycji 5?', pytasz 'jaka jest wartość dla klucza 'jabłko'?'. To fundamentalna zmiana: dostęp do danych masz nie przez numeryczną pozycję, ale przez unikalny identyfikator, który sam nadajesz. To, co czyni słowniki tak potężnymi, to ich *szybkość*. Znalezienie wartości dla danego klucza jest niemal natychmiastowe (złożoność O(1) w Pythonie), niezależnie od tego, czy słownik ma 10, czy 10 milionów elementów.
Dlaczego to ważne? Na maturze słowniki to Twoje sekretne narzędzie do *zliczania* i *grupowania*. Ile razy wystąpiła każda liczba w pliku? Słownik. Jaka jest łączna suma punktów dla każdego ucznia? Słownik (klucz: imię ucznia, wartość: suma). Ile razy wystąpiła każda litera? Słownik. Zamiast pisać skomplikowane pętle i sortowania, słownik rozwiązuje te problemy w kilku linijkach.
Teoria
Słownik (mapa) to struktura przechowująca dane w postaci par klucz-wartość. Każdy klucz w słowniku musi być unikalny. Klucze w Pythonie muszą być *niemutowalne* (np. liczby, stringi, krotki), w C++ muszą być porównywalne. Struktura ta pozwala na błyskawiczne dodawanie, usuwanie i wyszukiwanie elementów na podstawie ich klucza.
Jak to działa?
- Tworzenie: W Pythonie `moj_slownik = {}`. W C++ `map<typ_klucza, typ_wartosci> moja_mapa;`.
- Dodawanie / Modyfikacja: `slownik[klucz] = wartosc`. Jeśli `klucz` nie istnieje, nowa para jest tworzona. Jeśli `klucz` już istnieje, jego `wartosc` jest nadpisywana.
- Odczyt Wartości: `wartosc = slownik[klucz]`. W Pythonie, próba odczytu nieistniejącego klucza rzuci błąd `KeyError`.
- Bezpieczny Odczyt (Python): Użyj `slownik.get(klucz, domyslna_wartosc)`. Jeśli klucza nie ma, zwróci `domyslna_wartosc` (np. `0` lub `None`) zamiast błędu.
- Sprawdzanie Klucza (Python): Najlepszy sposób to `if klucz in slownik:`. To sprawdza, czy klucz jest w słowniku.
- Iteracja (Python): Możesz iterować po kluczach (`for klucz in slownik:` lub `slownik.keys()`), po wartościach (`slownik.values()`) lub po obu na raz (`for klucz, wartosc in slownik.items():`).
Złożoność: Złożoność czasowa: Python (`dict`) - bazuje na tablicy haszującej. Średnia złożoność dodawania, usuwania i wyszukiwania to O(1) (czas stały). To jest *niesamowicie* szybkie. C++ (`std::map`) - bazuje na zrównoważonych drzewach (red-black tree). Złożoność dodawania, usuwania i wyszukiwania to O(log n). Wciąż bardzo szybko. (C++ ma też `std::unordered_map`, które działa jak `dict` w Pythonie, ze złożonością O(1)).
Implementacja
Podstawy: Tworzenie, Dostęp, Modyfikacja
Python# 1. Tworzenie i dodawanie
uczniowie = {}
uczniowie["Jan"] = 100
uczniowie["Anna"] = 95
uczniowie["Piotr"] = 80
# {'Jan': 100, 'Anna': 95, 'Piotr': 80}
# 2. Modyfikacja (nadpisanie wartości)
uczniowie["Anna"] = 98
# {'Jan': 100, 'Anna': 98, 'Piotr': 80}
# 3. Odczyt (niebezpieczny)
# print(uczniowie["Kasia"]) # Rzuci błąd KeyError
# 4. Bezpieczne sprawdzanie (NAJWAŻNIEJSZE)
klucz = "Kasia"
if klucz in uczniowie:
print(f"{klucz} ma {uczniowie[klucz]} pkt")
else:
print(f"Nie ma ucznia o imieniu {klucz}")
# 5. Iteracja (klucz + wartość)
for imie, punkty in uczniowie.items():
print(f"{imie} -> {punkty}")To jest esencja słowników. Tworzysz `{}`, dodajesz przez `[klucz] = wartosc`. Najważniejszy wzorzec maturalny to bezpieczne sprawdzanie `if klucz in slownik:`, aby uniknąć błędów.
Zadanie: Zliczanie wystąpień (klasyczny przykład)
Pythonnapis = "ala ma kota, kot ma ale"
zlicz_litery = {}
for litera in napis:
if litera == ' ' or litera == ',':
continue # Pomiń spacje i przecinki
# Wzorzec na zliczanie:
if litera in zlicz_litery:
zlicz_litery[litera] += 1 # Jeśli już jest, zwiększ licznik
else:
zlicz_litery[litera] = 1 # Jeśli nie ma, stwórz klucz z wartością 1
print(zlicz_litery)
# Wynik: {'a': 4, 'l': 2, 'm': 2, 'k': 2, 'o': 2, 't': 2, 'e': 1}To jest *najważniejszy* wzorzec użycia słownika na maturze. Iterujemy po danych. Sprawdzamy, czy klucz (tutaj 'litera') jest już w słowniku. Jeśli tak, zwiększamy jego wartość (licznik). Jeśli nie, tworzymy go z początkową wartością 1.
Mapa w C++ (std::map) - Podstawy i zliczanie
C++#include <iostream>
#include <map>
#include <string>
using namespace std;
int main() {
// 1. Tworzenie mapy (klucz: string, wartość: int)
map<string, int> uczniowie;
// 2. Dodawanie i modyfikacja
uczniowie["Jan"] = 100;
uczniowie["Anna"] = 95;
uczniowie["Piotr"] = 80;
uczniowie["Anna"] = 98; // Nadpisanie
// 3. Odczyt (C++ automatycznie tworzy klucz!)
// cout << uczniowie["Kasia"] << endl; // To jest pułapka! Stworzy "Kasia" z wartością 0.
// 4. Bezpieczne sprawdzanie
if (uczniowie.count("Kasia")) {
cout << "Kasia ma " << uczniowie["Kasia"] << " pkt" << endl;
} else {
cout << "Nie ma ucznia o imieniu Kasia" << endl;
}
// 5. Wzorzec na zliczanie (prostszy niż w Pythonie!)
string napis = "alamakota";
map<char, int> zlicz_litery;
for (char litera : napis) {
zlicz_litery[litera]++; // Jeśli klucz 'litera' nie istnieje, C++ tworzy go z wart. 0 i OD RAZU zwiększa o 1.
}
// 6. Iteracja
for (auto const& [klucz, wartosc] : zlicz_litery) {
cout << klucz << ": " << wartosc << endl;
}
return 0;
}W C++ `std::map` jest z biblioteki `<map>`. Jest jedna duża różnica: `mapa[klucz]++` działa *zawsze*, nawet jeśli klucza nie ma! Dzieje się tak, bo `mapa[klucz]` automatycznie tworzy nowy element z domyślną wartością (0 dla `int`), a dopiero potem `++` zwiększa ją do 1. To bardzo ułatwia zliczanie.
Przykładowe Zadania Maturalne
W pliku 'owoce.txt' znajduje się 1000 wierszy, z których każdy zawiera nazwę owocu (np. 'jablko', 'banan', 'jablko'). Napisz program, który policzy i wypisze, ile razy w pliku pojawiła się każda unikalna nazwa owocu. Posortuj wyniki alfabetycznie według nazw owoców.
Wskazówka: To jest klasyczne zadanie na zliczanie. Użyj słownika, gdzie kluczem będzie nazwa owocu (string), a wartością będzie liczba jego wystąpień (int). Iteruj po pliku i dla każdego owocu implementuj wzorzec 'sprawdź-czy-jest / zwiększ-licznik'.
Pokaż szkic rozwiązania
1. Stwórz pusty słownik: `licznik_owocow = {}`.
2. Otwórz plik 'owoce.txt' do odczytu.
3. Dla każdej linii w pliku:
a. Wczytaj owoc: `owoc = linia.strip()`.
b. Sprawdź, czy owoc jest w słowniku: `if owoc in licznik_owocow:`.
c. Jeśli tak: `licznik_owocow[owoc] += 1`.
d. Jeśli nie: `licznik_owocow[owoc] = 1`.
4. Po pętli, posortuj klucze słownika: `posortowane_owoce = sorted(licznik_owocow.keys())`.
5. W pętli po posortowanych kluczach, wypisz wynik:
a. `for owoc in posortowane_owoce:`
b. ` print(f"{owoc}: {licznik_owocow[owoc]}")`.W bazie danych są tabele 'Laziki' (nr_lazika, nazwa) oraz 'Pomiary' (nr_lazika, data_pomiaru, ...). Podaj nazwę łazika, który wykonywał pomiary w najdłuższym okresie, licząc od pierwszego (najwcześniejszego) do ostatniego (najpóźniejszego) pomiaru. Podaj datę pierwszego i ostatniego pomiaru wykonanego przez ten łazik.
Wskazówka: To jest zadanie na grupowanie. Użyj słownika, aby przechować dane 'per łazik'. Kluczem będzie `nr_lazika`. Wartością może być lista, ale lepiej trzymać `[min_data, max_data]`. Iteruj po wszystkich pomiarach i na bieżąco aktualizuj `min_data` i `max_data` dla każdego łazika w słowniku.
Pokaż szkic rozwiązania
1. Wczytaj dane z 'Pomiary' i 'Laziki' (np. do dwóch list lub słownika nazw łazików).
2. Stwórz słownik do śledzenia dat: `daty_lazikow = {}`.
3. Iteruj po wszystkich pomiarach (każdy to `nr_lazika`, `data_pomiaru`):
a. Sprawdź, czy łazik jest już w słowniku: `if nr_lazika in daty_lazikow:`
b. `stara_min_data = daty_lazikow[nr_lazika][0]`
c. `stara_max_data = daty_lazikow[nr_lazika][1]`
d. `daty_lazikow[nr_lazika][0] = min(stara_min_data, data_pomiaru)`
e. `daty_lazikow[nr_lazika][1] = max(stara_max_data, data_pomiaru)`
f. Jeśli nie: `daty_lazikow[nr_lazika] = [data_pomiaru, data_pomiaru]`.
4. Po pętli, iteruj po słowniku `daty_lazikow`, aby znaleźć łazika z największą różnicą (max_data - min_data).Częste Błędy
❌ Błąd `KeyError` (Python)
Najczęstszy błąd. Próba odczytania klucza, który nie istnieje, np. `print(slownik['klucz_ktorego_nie_ma'])`. Program się zatrzymuje.
Poprawka: Zawsze sprawdzaj, zanim odczytasz: `if klucz in slownik: ...` lub użyj bezpiecznej metody `.get()`: `wartosc = slownik.get(klucz, 0)`.
❌ Błędna logika zliczania
Uczeń od razu próbuje `slownik[klucz] += 1`. To zadziała tylko, jeśli klucz już tam jest. Jeśli nie, dostanie `KeyError`, bo próbuje dodać 1 do czegoś, co nie istnieje.
Poprawka: Użyj pełnego wzorca: `if klucz in slownik: slownik[klucz] += 1 else: slownik[klucz] = 1`. Albo prościej: `slownik[klucz] = slownik.get(klucz, 0) + 1`.
❌ Użycie listy jako klucza (Python)
Klucze w słowniku Pythona muszą być *niemutowalne* (niezmienne). Próba `slownik[[1, 2]] = 'lista'` rzuci błąd `TypeError: unhashable type: 'list'`. Stringi, liczby i krotki (tuple) są OK.
Poprawka: Jeśli musisz użyć 'listy' jako klucza, zamień ją na krotkę (tuple): `slownik[(1, 2)] = 'krotka'`.
❌ Mylenie iteracji po kluczach i wartościach
Piszesz `for element in slownik: print(element)` i oczekujesz wartości. Domyślnie pętla `for` w Pythonie iteruje po *kluczach*.
Poprawka: Jeśli chcesz wartości, pisz: `for wartosc in slownik.values():`. Jeśli chcesz oba, pisz: `for klucz, wartosc in slownik.items():`.
Kluczowe Wnioski
- Słownik (mapa) przechowuje pary klucz-wartość.
- Dostęp do wartości jest przez klucz, nie przez indeks (`slownik['klucz']`).
- Jest to idealna struktura do zliczania wystąpień i grupowania danych.
- W Pythonie (`dict`), odczyt i zapis są (średnio) O(1) - natychmiastowe.
- W C++ (`std::map`), odczyt i zapis są O(log n) - bardzo szybkie.
- W Pythonie, zawsze bezpiecznie sprawdzaj klucz (`if klucz in slownik:`) lub używaj `.get(klucz, 0)`.
- W C++, `mapa[klucz]++` to prosty i bezpieczny sposób na zliczanie (automatycznie tworzy klucz z wartością 0, jeśli nie istnieje).
Najczęściej Zadawane Pytania
❓ Jaka jest główna różnica między listą a słownikiem?
W liście odwołujesz się do elementów przez ich *numeryczną pozycję* (indeks), np. `lista[0]`. W słowniku odwołujesz się do elementów przez ich *unikalny klucz* (nazwę), np. `slownik['Anna']`. Poza tym lista jest uporządkowana, a słownik (przed Pythonem 3.7) nie gwarantował kolejności.
❓ Kiedy używać słownika, a kiedy listy?
Użyj listy, gdy masz zbiór danych i ich kolejność jest ważna (np. wczytane dane z pliku, które chcesz posortować). Użyj słownika, gdy chcesz coś *zliczyć* lub *grupować* dane na podstawie jakiejś etykiety (np. 'ile razy wystąpiło każde słowo' lub 'jaka jest suma punktów dla 'Jana'').
❓ Co się stanie, jak dodam element z kluczem, który już istnieje?
Nie zostanie dodany drugi element. Zamiast tego, *wartość* dla tego klucza zostanie *nadpisana* (zaktualizowana) nową wartością.
❓ Jaka jest różnica między `map` a `unordered_map` w C++?
`map` (oparty na drzewach) gwarantuje złożoność O(log n) i przechowuje klucze *posortowane*. `unordered_map` (oparty na haszowaniu, jak `dict` w Pythonie) ma średnią złożoność O(1), ale nie przechowuje kluczy w żadnym określonym porządku. Na maturę oba są wystarczająco szybkie.
❓ Jak w Pythonie iterować po kluczach i wartościach jednocześnie?
Użyj metody `.items()`. Jest to bardzo czytelne: `for klucz, wartosc in moj_slownik.items(): print(f"Klucz: {klucz}, Wartość: {wartosc}")`.
Chcesz opanować wszystkie tematy maturalne?
Dołącz do kursu i zyskaj dostęp do interaktywnych lekcji, edytora kodu i setek zadań.