8. Datové struktury

Při řešení různorodých problémů se hodí mít možnost uspořádat si data do takového uspořádání (struktury), která nám napomůže ke správnému řešení či zlepší jeho efektivitu, přehlednost atp. Tyto struktury jsou obecně nazývány datovými a informatika jim věnuje nemálo pozornosti.

Datová struktura

Datová struktura je konkrétní způsob uspořádání nějakých dat. Konkrétní datová struktura typicky implementuje nějakou abstraktní datovou strukturu, která popisuje s jakými daty pracujeme a jaké operace s danou strukturou můžeme provádět (e.g. přidání/odebrání prvku atp.)

_images/data_structures.jpg

Pole

Jednou z nejjednodušších struktur, mající fixní počet míst pro data jednoho datového typu, je vestavěna do jazyků jako C, C++, Java apod. V Pythonu se místo této struktury používají seznamy, která mají řadu funkcí navíc, například append, či možnost mít v seznamu libovolně různorodé datové typy.

Seznam

Jednou z nejjednodušších datových struktur v Pythonu je seznam (anglicky/slangově “list”), probíraný v kapitole Řetězce a seznamy. Pro zopakování, nejdůležitější operace:

V této kapitole se budeme zabývat jen zásobníky, frontami, slovníky a množinami, ale datových struktur existuje velká řada a během dalšího studia se s nimi určitě potkáte, například se stromy:

_images/tree.png

(zdroj: XKCD)

8.1. Zásobníky

Zásobník (anglicky “stack”), slangově s je speciální variantou seznamu, umožňující prvky vkládat a odebírat pouze z vrcholu zásobníku, tedy podle principu LIFO: Last In – First Out. Tyto dvě dodatečné operace se nazývají pop a push. V Pythonu pro ně můžeme použít seznamy, které obě operace implementují:

8.1.1. Interpretace výrazu v postfixu

Při běžném počítání s aritmetickými výrazy 6 + 5 používáme takzvanou infixovou notaci s operátorem mezi operandy. V tomto příkladě budeme pracovat s takzvaně reverzní polskou notací, kdy operátor následuje po operandech, například 6 5 *.

Vyzkoušejte si převést 7 * 8 + 2 * 6 + 5 do postfixu a následně si ho zkuste spolu s 5 7 * 3 - 4 + vyhodnotit.

Napište funkci, která obdrží řetězec v postfixové notaci a ta výraz za pomocí zásobníku vyhodnotí. Implementuje operace +, -, / a * v plovoucí čárce.

Tip: může se vám hodit metoda split, která je použitelná na řetězcích: "a b c".split().

def evaluate_postfix(expr: str) -> float:
    pass

def test_evaluate_postfix() -> None:
    assert evaluate_postfix("8 7 * 6 5 + 2 * +")) == 78
    assert evaluate_postfix("6 5 -")) == 1
    assert evaluate_postfix("15 7 1 1 + - / 3 * 2 1 1 + + -")) == 5

8.1.2. Stejná výška

Máte 3 sloupce složené z válců, každý válec má stejný průměr, ale mají různou výšku. Výšku sloupce můžete změnit odebráním válce zvrchu. Válce pouze odebírejte, nepřehazujte je na jiné věže.

Napište funkci equal_height, která vrátí nejvyšší možnou výšku takovou, že všechny sloupce mají stejnou výšku. Funkce zároveň upraví seznamy sloupců (viz asserty níže).

Bonusový úkol: upravte pro jakýkoliv počet sloupců (t1: List[int], t2: List[int], t3: List[int] -> ts: List[List[int]]).

def equal_height(t1: List[int], t2: List[int], t3: List[int]) -> int:
    pass

def test_equal_height() -> None:
    t1 = [1, 1, 1, 2, 3]
    t2 = [2, 3, 4]
    t3 = [1, 4, 1, 1]
    assert equal_height(t1, t2, t3) == 5
    assert t1 == [1, 1, 1, 2]
    assert t2 == [2, 3]
    assert t3 == [1, 4]

8.1.3. Další větší než

Napište funkci next_greater, která pro seznam lst vrátí seznam n-tic (e, ng), kde e je prvek ze seznamu lst a ng je další prvek, který je větší než e. Když se v seznamu nenachází větší prvek, použijte None.

Ve výsledném seznamu se musí nacházet všechny prvky z předaného seznamu, na pořadí nezáleží.

def next_greater(lst: List[int]) -> List[Tuple[int, Optional[int]]]:
    pass

def test_next_greater() -> None:
    assert set(next_greater([4, 5, 2, 25])) == {(4, 5), (5, 25), (2, 25), (25, None)}
    assert set(next_greater([13, 7, 6, 12])) == {
        (13, None),
        (7, 12),
        (6, 12),
        (12, None),
    }
    assert set(next_greater([11, 13, 21, 3])) == {
        (11, 13),
        (13, 21),
        (21, None),
        (3, None),
    }

8.2. Fronty

Fronta (anglicky/slangově “queue” či “deque”) je struktura, do které lze prvky přidávat (push) a odebírat (pop). Pořadí odebírání se ale děje podle principu FIFO (First In – First Out), tak jako v klasické frontě v obchodě. Jedná se tedy opět jen o speciální variantu seznamu, umožňující vkládat prvky na jeden konec a odebírat z druhého konce. Mohli bychom tedy klidně opět využít seznamy, tento způsob však není moc efektivní (přidávání nebo odebírání prvků ze začátku seznamu způsobí, že všechny prvky dál se musí posunout o 1 pozici). Lepší je tedy použít specializovaný typ deque z knihovny collections.

from collections import deque

queue = deque(["Petr", "Zdenek", "Filip"]) # 3 studenti cekaji ve fronte na obed

queue.append("Kuba") # Kuba prisel na konec fronty
print(queue) # deque(["Petr", "Zdenek", "Filip", "Kuba"])

queue.append("Roman") # Roman prisel na konec fronty
print(queue) # deque(["Petr", "Zdenek", "Filip", "Kuba", "Roman"])

student = queue.popleft() # prvni student ve fronte (Petr) dostal obed
print(queue, student) # deque(["Zdenek", "Filip", "Kuba", "Roman"]), student: "Petr"

student = queue.popleft() # dalsi student ve fronte (Zdenek) dostal obed
print(queue, student) # deque(["Filip", "Kuba", "Roman"]), student: "Zdenek"

8.2.1. Má mě rád, nemá mě rád

Nejprve si vygenerujeme kytici lineárně uspořádaných n květin, každou o 1 až 4 okvětních lístcích. Poté vezmeme první květinu a utrhneme z ní právě jeden lístek a zařadíme ji nakonec. Postup opakujeme dokud nejsou všechny květiny otrhané. Má vás rád?

from random import randint

def game(n: int) -> None:
   pass

print(game(1))
print(game(10))

8.2.2. Horký brambor

Horký brambor je jednoduchá dětská hra, kterou hraje n lidí s jedním horkým bramborem, který si mezi sebou přehazují. Kdo má brambor vyhodnotí jednoduché kritérium (jako každý sedmý) a pokud toto kritérium splňuje, pak vypadává ze hry. Vyhrává poslední hráč.

Naprogramujte tuto hru za použití fronty. Přičemž hraje n lidí, jejichž jména dostane program v seznamu a vypadává každý k-tý hráč. Průběh hry, vítěze a počet kol průběžně vypisujte.

def hot_potato(namelist: List[str], k: int) -> None:
    pass

hot_potato(["Bill","David","Susan","Jane","Kent","Brad","Sam"],7)
# Bill is off!
# Sam is off!
# Kent is off!
# David is off!
# Brad is off!
# Jane is off!
# After 43 rounds Susan is winner!

8.2.3. Fronta v obchodě

V obchodě je fronta u samoobslužných pokladen. Vaším úkolem je napsat funkci queue_time, která vypočítá nejmenší možný celkový čas nutný k vyřízení celé fronty.

Funkce dostává parametry customers a n. customers je seznam kladných čísel, každé číslo reprezentuje zákazníka a jeho hodnota udává čas, který potřebuje k vyřízení nákupu. n je kladné číslo, které reprezentuje počet pokladen.

from collections import deque

def queue_time(customers: Deque[int], n: int) -> int:
    pass

def test_queue_time() -> None:
    # they have to wait for each other
    assert queue_time(deque([5,3,4]), 1) == 12
    # because 1st customer spends 10 "times" and others go to second machine
    assert queue_time(deque([10,2,3,3]), 2) == 10
    assert queue_time(deque([2,3,10]), 2) == 12

8.3. Slovníky

Slovník, někdy též asociativní seznam (slangově též “mapa”) mapuje klíče na hodnoty. Je podobný seznamu, ale jeho prvky nejsou indexovány pomocí posloupnosti celých čísel, ale pomocí klíčů. Klíčem může být například číslo, řetězec nebo jiný neměnitelný objekt, tedy seznam klíčem být nemůže. Pod tímto klíčem můžeme přistupovat k uloženým hodnotám, jsou-li takové ve slovníku přítomny, či nové ukládat.

(demo_dictionary)

8.3.1. Morseova abeceda

Napište funkce pro převod řetězce do a z Morseovy abecedy.

MORSE_CODE = {
    "A": ".-",      "B": "-...",    "C": "-.-.",    "D": "-..",
    "E": ".",       "F": "..-.",    "G": "--.",     "H": "....",
    "I": "..",      "J": ".---",    "K": "-.-",     "L": ".-..",
    "M": "--",      "N": "-.",      "O": "---",     "P": ".--.",
    "Q": "--.-",    "R": ".-.",     "S": "...",     "T": "-",
    "U": "..-",     "V": "...-",    "W": ".--",     "X": "-..-",
    "Y": "-.--",    "Z": "--..",    "1": ".----",   "2": "..---",
    "3": "...--",   "4": "....-",   "5": ".....",   "6": "-....",
    "7": "--...",   "8": "---..",   "9": "----.",   "0": "-----",
}

def encode(value: str) -> str:
    pass

def decode(value: str) -> str:
    pass

def test_encode() -> None:
    assert encode('SOS') == "... --- ..."
    assert encode('HELLOWORLD') == ".... . .-.. .-.. --- .-- --- .-. .-.. -.."

def test_decode() -> None:
    assert decode('.... . .-.. .-.. --- .-- --- .-. .-.. -..') == "HELLOWORLD"
    assert decode(encode('IDENTITY')) == "IDENTITY"

  1. zkuste reprezentovat abecedu jinou datovou strukturou; která by byla vhodná?

  2. zkuste implementovat podporu pro mezery ve vstupu a case-insensitive vstup

8.3.2. Frekvenční analýza písmen

Napište funkci freq_analysis(text), která spočítá výskyt jednotlivých písmen (znaků) ve vstupním textu a následně tento seznam vypíše setříděný sestupně podle počtu výskytů.

dummy = """Monty Python and Monty Python all over here."""

def freq_analysis(text: str) -> None:
    pass

freq_analysis(dummy)

8.3.3. Frekvenční analýza slov

Napište funkci freq_analysis(text), která spočítá výskyt jednotlivých slov ve vstupním textu a následně tento seznam vypíše setříděný podle abecedy.

Tip: může se vám hodit metoda split, která je použitelná na řetězcích: "a b c".split().

dummy = """Monty Python and Monty Python all over here."""

def freq_analysis(text: str) -> None:
    pass

freq_analysis(dummy)

8.4. Množiny

V množině nemají jednotlivé prvky své indexy, ale můžeme prvky přidávat i odebírat a testovat, zda je nějaký prvek v množině. Množina neobsahuje duplicity (když do ní třikrát přidáme číslo 4, pořád ho bude obsahovat pouze jedenkrát). Přestože nemůžeme přistupovat k jednotlivým prvkům pomocí indexů, můžeme projít celou množinu (a provést nějakou operaci pro každý prvek množiny).

Množinové operace na množinách

8.4.1. Kontrola unikátnosti seznamu

Napište funkci, která zkontroluje, zda předaný seznam obsahuje jen unikátní položky.

def unique_check(temp: List[int]) -> bool:
    pass

def test_unique_check():
    assert unique_check([1, 5, 6, 5, 4, 9]) == False
    assert unique_check([1, 5, 6, 3, 9]) == True

8.4.2. Kontrola řádku Sudoku

Napište funkci, která zkontroluje, zda předaný seznam reprezentuje správný řádek vyplněného Sudoku, tj. obsahuje pouze čísla 1 až 9 a každé z nich právě jedenkrát.

def sudoku_line_check(line: List[int]) -> bool:
    pass

def test_sudoku_line_check() -> None:
assert sudoku_line_check([1, 2, 8, 9, 3, 5, 6, 7, 4]) == True
assert sudoku_line_check([1, 2, 8, 9, 3, 5, 7, 4]) == False
assert sudoku_line_check([1, 1, 2, 8, 9, 3, 5, 7, 4]) == False
assert sudoku_line_check([0, 1, 2, 3, 4, 5, 6, 7, 8]) == False

8.5. Procvičování

8.5.1. Vyhodnocení logického výrazu v postfixové notaci

Funkce vrátí True, pokud je předaný výrok pravdivý, jinak False. Výraz se skládá z následujících znaků:

  • ‘T’: True

  • ‘F’: False

  • ‘N’: negace

  • ‘K’: konjunkce

  • ‘A’: disjunkce

  • ‘C’: implikace

def evaluate_logic_expression(expr: str) -> bool:
    pass

def test_evaluate_logic_expression() -> None:
    assert evaluate_logic_expression("TFK") == False
    assert evaluate_logic_expression("FNTFCNK") == True

8.5.2. CalcuLoS

Následující úloha byla adaptována z šifrovací hry InterLoS 2015.

Napište program, který vezme za vstup řetězec složený pouze z písmen INTERLOS a transformuje (respektive vyhodnotí) na řetězec složený z písmen LOS podle níže popsaných pravidel.

Vyhodnocování probíhá zleva, narazí-li se na nějaké z písmen LOS (hodnota) pokračuje se směrem vpravo. Je-li nalezen nějaký znak z INTER (operátor) vyhodnotí se za použití argumentů, které ihned následují. Přitom ale může dojít k situaci, že tyto argumenty nejsou hodnotami, ale operátory, pak se musí vyhodnotit nejdříve tyto argumenty.

Ukázkové vyhodnocení:

LINLRETOS   Nejprve musíme vyhodnotit T na O → O
LINLREOS    Pak musíme vyhodnotit E na O a S → SO
LINLRSO     Následně musíme vyhodnotit R na S → S S
LINLSSO     Poté musíme vyhodnotit N na L a S → S
LISSO       A nakonec musíme vyhodnotit I na S a S → O
LOO         Výsledek.

Operátor I bere dva argumenty, vrací jednu hodnotu podle následující tabulky:

L

L

L

L

O

L

O

S

S

L

S

O

Operátor N bere dva argumenty, vrací jednu hodnotu podle následující tabulky:

L

L

O

S

O

O

S

L

S

S

L

O

Operátor T bere jeden argument, vrací jednu hodnotu podle následující tabulky:

L

S

O

O

S

L

Operátor E bere dva argumenty, vrací dvě hodnoty: E x y → y x pro všechny x a y z hodnot.

Operátor R bere jeden argument, vrací dvě hodnoty: R x → x x pro všechny x z hodnot.

8.5.3. Kontrola uzávorkování

Napište funkci, která pro zadaný řetězec složený pouze ze závorek [](){} ověří, že jde o korektní uzávorkování.

def parenthesis_check(value: str) -> bool:
    pass

def test_parenthesis_check() -> None:
    assert parenthesis_check('([]({()}))[]{[()]}') == True
    assert parenthesis_check('([)]') == False

8.5.4. Placení v kině

Před kinem čekají lidi ve frontě na nový film. Každý má jenom jednu 100, 50 nebo 25dolarovou bankovku. Vstupenka stojí 25 dolarů.

Napište funkci can_sell_tickets, která dostane frontu a vrátí True, když je možné prodat všem vstupenky, jinak False.

from collections import deque

def can_sell_tickets(people: Deque[int]) -> bool:
    pass

def test_can_sell_tickets() -> None:
    assert can_sell_tickets(deque([25, 25, 50]))
    # not enough to give change for 100
    assert not can_sell_tickets(deque([25, 100]))
    # can't give back 75 exactly
    assert not can_sell_tickets(deque([25, 25, 50, 50, 100]))
Next Section - 9. Objekty