Úlohy na procvičení

Cílem všech úkolů je procvičit si práci se spojovými seznamy. Pro jejich vyřešení tedy nepoužívejte jiné datové struktury (seznamy, apod.). Můžete úpravy provádět destruktivně, tedy přímo měnit prvky původního seznamu.

Pokud není uvedeno jinak, jako jeden ze vstupních parametrů dostanete první prvek seznamu a máte vrátit první prvek upraveného seznamu.

Operace se spojovým seznamem

Řešení úloh pište jako funkce, které dostanou jako parametr první prvek seznamu (first_node), a pokud mají vrátit seznam, tak vrátí první prvek upraveného seznamu (jako jsme to dělali u úloh, které jsme řešili společně).

  1. Napište funkci add_to_end(first_node: Node, x: int) -> Node, která přidá hodnotu \(x\) na konec spojového seznamu.

  2. Napište funkci delete_last(first_node: Node) -> Node, která vymaže poslední prvek spojového seznamu.

  3. Napište funkci length(first_node: Node) -> int, která spočítá délku spojového seznamu (počet prvků).

  4. Napište funkci get(first_node: Node, index: int) -> int, která vrátí hodnotu v seznamu na pozici index (vraťte rovnou číslo uložené v .item, ne objekt Node). Pokud je index mimo rozsah seznamu, vyhoďte výjimku: raise IndexError().

  5. Napište funkci contains(first_node: Node, x: int) -> bool, která zjistí, zda hodnota \(x\) v seznamu je nebo není.

  6. Napište funkci swap_two(first_node: Node) -> Node, která prohodí pořadí prvního a druhého prvku.

  7. Napište funkci to_list(first_node: Node) -> list[int], která převede spojový seznam na list.

Vkládání do setřízeného seznamu

Do setřízeného seznamu vložte prvek s hodnotou \(x\).

Otočení seznamu

Otočte spojový seznam.

Mazání prvního výskytu

Ze seznamu vymaže prvek s hodnotou \(x\) (první výskyt), pokud tam je.

Mazání všech výskytů

Ze seznamu vymaže všechny prvky s hodnotou \(x\).

Slévání (merge)

Dostanete dva setřízené spojové seznamy. Vraťte seznam, kde jsou všechny prvky obou seznamů a jsou setřízené. (Jako operace merge v merge sortu.)

Sudé a liché

Rozdělte seznam na dva seznamy. V prvním budou pouze sudé prvky, v druhém pouze liché. Například seznam 5, 6, 10, 12, 15, 16, 25 rozdělte na 6, 10, 12, 16 a 5, 15, 25.

Deque

Implementujte oboustrannou frontu (deque) pomocí obousměrného spojového seznamu. Operace na oboustranné frontě jsou

  • push_back - přidání prvku na konec,
  • push_front - přidání prvku na začátek,
  • pop_back - odebrání prvku z konce,
  • pop_front - odebrání prvku ze začátku,

a všechny chceme provádět s konstantní časovou složitostí.

K zamyšlení: Proč nám nestačí jednosměrný seznam?

Linting

Linting je automatická analýza kódu, která se snaží najít možné chyby. Taky může upozorňovat na nedodržování běžného formátování kódu.

Umí to některé chytřejší editory (např. PyCharm). Do VS Code se dají nainstalovat rozšíření (pylint, příp. flake8).

Ruční instalace (použití z příkazové řádky): python -m pip install pylint (pokud vám to píše, že nemáte dostatečná práva, přidejte ještě --user), spuštění: python -m pylint jmeno_souboru.py.

Pokud nechcete dostávat všechna varování, jde některá vypnout. Třeba takhle se vypnou varování ohledně chybějících docstringů: python -m pylint --disable=C0114 --disable=C0115 --disable=C0116 jmeno_souboru.py. Argumenty jdou nastavit i pro rozšíření ve VS Code (vyhledávejte “pylint” v nastavení).

Učební výstupy

Učební výstupy podávají zhuštěný souhrn základních konceptů a dovedností, které byste měli umět vysvětlit a/nebo použít po každém cvičení. Hvězdičkou (⭐) je označena látka nad rámec předmětu Programování 1, kterou tedy teď nemusíte umět, ale někdy v budoucnu se vám může hodit.

  • umět definovat třídu s datovými položkami a metodami
  • chápat význam metody __init__
  • umět vytvořit novou instanci třídy (objekt)
  • vědět, že proměnné jsou ukazatele do paměti a že více proměnných může ukazovat na ten samý objekt v paměti
  • používat třídy a objekty pro seskupení souvisejících dat (a operací s nimi)
  • vytvořit projekt na MFF GitLab, procházet soubory v projektu, zobrazit historii verzí (commitů)
  • ⭐ vědět o existenci nástrojů pro automatické hledání chyb v kódu (např. pylint, inspekce v IDE PyCharm, …) a umět je spustit na svůj kód