Datové typy
IB111: Datové typy
Data a algoritmizace
• jaká data potřebuji pro vyřešení problému?
• jak budu data reprezentovat?
• jaké operaci s nimi potřebuji provádět?
• Navržení práce s daty je velice důležité
Datový typ 
• Datový typ 
– rozsah hodnot, které může proměnná daného typu 
přijmout
– a množina operací, které jsou pro tento datový typ 
dovoleny/definovány.
Abstraktní datový typ (ADT)
• specifikuje strukturu a operace nad ní na základě
dokumentované funkcionality 
(případně i složitost)
• nezávisí na konkrétní implementaci
• Důležité principy: 
– Abstrakce
– Oddělení specifikace
– Implementace
Základní ADT
• Mezi základní ADT patří:
– (lineární) seznam
– zásobník
– fronta
– množina
– slovník ‐ asociativní pole
– zobrazení
– textový řetězec
(Zřetězený) seznam
• Obsahuje posloupnost prvků
• Operace:
– Přidání prvku
• Na začátek
• Na konec
• Na určité místo (např. za/před určitý prvek)
– Odebrání prvku
• Ze začátku
• Od konce
• Konkrétní prvek (daný pozicí, hodnotou apod.)
– Test prázdnosti seznamu
• Jednosměrně zřetězený seznam
• Obousměrně zřetězený seznam
Typy (zřetězených) seznamů
nextdata nextdata nextdata
nextprevdata nextprevdata nextprevdata
• Kruhový seznam
– Jednosměrný nebo obousměrný
Typy (zřetězených) seznamů
nextdata nextdata nextdata
Seznamy v Pythonu (opak.)
• Seznam prvků oddělený čárkami a uzavřený do 
hranatých závorek
• K prvkům můžeme 
přistupovat např. 
přes indexy
• Seznamy lze
modifikovat
Seznamy v Pythonu (opak.)
• Na rozdíl od řetězců lze seznamy modifikovat
• Počet prvků – funkce len()
Seznamy: Užitečné funkce
Přehodí pořadí prvků (od posledního k prvnímu)list.reverse()
Test zda seznam obsahuje xx in list
Setřídí prvky seznamulist.sort() 
Navrátí počet výskytů hodnoty x v seznamulist.count(x) 
Navrátí index prvního prvku s hodnotou xlist.index(x) 
Odstraní poslední prveklist.pop()
Odstraní prvek na pozici ilist.pop(i) 
Odstraní první prvek s hodnotou xlist.remove(x) 
Přidá prvek x před prvek na pozici ilist.insert(i, x) 
Přidá všechny prvky L na konec seznamulist.extend(L) 
Přidá prvek x na konec seznamulist.append(x) 
Seznamy: příklady
Seznamy: příkaz del
• Příkaz del smaže prvek nebo jinou část seznamu
• Lze smazat i celou proměnnou
Vnořené seznamy
• Lze použít pro vícerozměrná data
Vnořené seznamy ‐ matice
• Vnořené seznamy
– Vícerozměrná pole
– Vhodné pro například pro matice
• Příklad: vytvoření nulové matice zadaných rozměrů
Příklad: Matice
• Násobení matic
Příklad: (aritmetický) průměr
• Statistická veličina
– Snaha zjistit „typickou hodnotu“
– Nevýhoda: extrémní hodnoty ovlivňují průměr
• Výpočet:
– součet všech hodnot dělený počtem prvků


n
i
iX
n
x
1
1
Příklad: medián
• Medián je číslo, které rozdělí řadu podle velikosti 
seřazených čísel na dvě stejně početné poloviny. 
• Nalezení mediánu:
1. Seřadím čísla podle velikosti
2. Vezmu  číslo, která se nalézá uprostřed seznamu. 
– Pokud není nějaké číslo přesně uprostřed, tj. počet 
prvků je sudý, pak se obvykle za medián považuje 
aritmetický průměr hodnot na dvou místech u 
středu.
Příklad: medián
Zásobník (stack)
• Operace:
– push (vložení)
– pop (odstranění)
– top (horní prvek)
– empty (test prázdnosti)
• LIFO = Last In First Out
• Intuitivní příklad: sloupec knih
• Běžné použití: 
– procházení grafů
– vyhodnocování výrazů
– rekurze
Python: zásobník pomocí seznamu
Příklad: postfixová notace
• Zápis matematických výrazů
– Infixová notace
• Zápis operátorů mezi operandy
• Např. 1 + 2
– Prefixová notace
• Zápis operátorů před operandy
• Např. + 1 2
– Postfixová notace (reverzní polská notace)
• Operátor následuje operandy
• Není třeba používat závorky
• Např. 1 2 +
Příklad: postfixová notace
Příklad: postfixová notace
Fronta (queue)
• operace:
– push (vložení)
– pop (odstranění)
– top (první prvek)
– empty (test prázdnosti)
• FIFO = First In First Out
• příklad: 
– zpracování příchozích požadavků serverem
Python a fronta
• lze pomocí seznamu, ale pomalé
– Protože přidávání a odebírání ze začátku seznamu 
vyžaduje posun všech prvků…
• použití knihovny collections:
Seznam x zásobník  x fronta
• Zásobník a fronta jsou podobné seznamu
– Ale poskytují méně možných operací
• Např. přidání jen na začátek/konec
• Proč používáme struktury, které nám nabízejí méně
funkcí?
• Pokud se omezíme na více specifický datový typ 
mohou být:
– operace rychlejší a/nebo
– paměťové nároky menší
• Při návrhu nám pomáhá uvědomit si, že 
potřebujeme např. zásobník a ne obecně seznam…
Množina (set)
• operace:
– insert (vložení)
– find (test na přítomnost)
– delete (odstranění)
• příklady:
– evidování navštívených vrcholů při prohledávání
– počítání „průniku“ informací ze dvou souborů
Množiny v Pythonu
• Množina
– Neuspořádaná kolekce dat bez duplicitních prvků
Rozdíl množindifference nebo operátor ‐
Položky z jedné z množin nenacházející se v 
množině druhé
symmetric_difference nebo operátor ^
Průnik množinintersection nebo operátor &
Sjednocení množinunion nebo operátor |
Test zda s1 je podmnožinou s2s1 <= s2 
Test zda prvek x se nachází v množině sx in s
počet prvků množinylen(s)
Množiny v Pythonu: příklad
N‐tice (tuples) v Pythonu
• N‐tice podobné seznamům
• Nejsou měnitelné (stejně jako řetězce)
Slovník (dictionary, map)
• Slovník, dictionary, map, asociativní pole
– zobecnění množiny, pole
• dvojice klíč, hodnota
– klíče jsou unikátní
– neuspořádané
• příklady:
– počet výskytů jednotlivých slov v textu
– „kešování“ výsledků časově náročných výpočtů
Slovník v Pythonu
• {}
• Klíč a hodnotu oddělujeme dvojtečkou
– U jednoduchých klíčů lze použít i =
• Slovník lze vyrobit i n‐tic (tuples) 
• Slovník je modifikovatelný
Slovník v Pythonu: příklad
Výpis slovníku
• Jednotlivé položky slovníku můžeme iterovat 
pomocí „.iteritems()“
Příklad: frekvence slov
• Analyzujeme předložený text
• Pro každé slovo vypíšeme kolikrát se v textu 
vyskytuje
• Výsledek lze využít jako 
metriku podobnosti 
dokumentů apod.
Příklad: frekvence slov ‐ výpočet
Příklad: frekvence slov ‐ výpis
Příklad: morseovka
Příklad: převodník