Listy, stosy i kolejki
Celem jest dobranie reprezentacji do wymaganych operacji oraz utrzymanie niezmienników struktury po każdej modyfikacji.
1. Lista jednokierunkowa
Węzeł przechowuje wartość i odwołanie do następnego węzła. Pusta lista ma head = None. W liście niepustej przejście od head przez kolejne odwołania kończy się dokładnie raz wartością None.
Zadanie 1. Zaimplementuj wstawianie na początku, wyszukiwanie i usuwanie pierwszego wystąpienia. Po każdej operacji sprawdź pustą listę, jeden węzeł oraz brak szukanej wartości. Nie korzystaj z gotowej listy jako magazynu elementów.
2. Koszt operacji zależy od reprezentacji
| Operacja | Lista z pojedynczym początkiem | Lista z początkiem i końcem |
|---|---|---|
| wstawienie na początku | Θ(1) | Θ(1) |
| wstawienie na końcu | Θ(n) | Θ(1) |
| wyszukiwanie wartości | Θ(n) | Θ(n) |
Zadanie 2. Dodaj odwołanie
tail. Zapisz niezmienniki dla listy pustej i niepustej. Wykaż, które instrukcje muszą zaktualizować oba końce.3. Stos i kolejka
Stos realizuje porządek LIFO, a kolejka FIFO. Zbuduj oba abstrakcyjne typy danych na węzłach listy. Publiczny interfejs nie powinien ujawniać węzłów.
stos: push(x), pop(), peek(), is_empty()
kolejka: enqueue(x), dequeue(), front(), is_empty()Zadanie 3. Zastosuj stos do sprawdzania poprawności nawiasów, a kolejkę do symulacji obsługi zgłoszeń. Zdefiniuj zachowanie operacji usuwającej dla pustej struktury.
4. Testowanie niezmienników
Zadanie 4. Przygotuj sekwencje mieszające co najmniej 20 operacji. Po każdym kroku porównaj rozmiar, element dostępny na końcu logicznym i kolejność usuwania z prostym modelem referencyjnym.
5. Sprawozdanie
- Interfejsy struktur i przyjęte niezmienniki.
- Kod bez ujawniania reprezentacji.
- Tabela kosztów operacji z uzasadnieniem.
- Testy przypadków brzegowych i sekwencji mieszanych.
- Wnioski o doborze reprezentacji.
- Opis użycia AI albo informacja, że AI nie użyto.
Przykład opisu AI: „Użyłem modelu GPT-5 do przeglądu testów po promptcie: «Wskaż pominięty przypadek brzegowy dla kolejki opartej na liście, bez proponowania implementacji». Sugestię dotyczącą usunięcia ostatniego elementu zweryfikowałem własnym testem niezmienników head i tail.”
Źródła
- T. H. Cormen, C. E. Leiserson, R. L. Rivest i C. Stein, Introduction to Algorithms, wyd. 4, MIT Press, 2022.
- A. Levitin, Introduction to the Design and Analysis of Algorithms, wyd. 3, Pearson, 2022.