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ů data next data next data next data prev next data prev next data prev next •Kruhový seznam –Jednosměrný nebo obousměrný Typy (zřetězených) seznamů data next data next data next 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 list.append(x) Přidá prvek x na konec seznamu list.extend(L) Přidá všechny prvky L na konec seznamu list.insert(i, x) Přidá prvek x před prvek na pozici i list.remove(x) Odstraní první prvek s hodnotou x list.pop(i) Odstraní prvek na pozici i list.pop() Odstraní poslední prvek list.index(x) Navrátí index prvního prvku s hodnotou x list.count(x) Navrátí počet výskytů hodnoty x v seznamu list.sort() Setřídí prvky seznamu list.reverse() Přehodí pořadí prvků (od posledního k prvnímu) x in list Test zda seznam obsahuje 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ů 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ů len(s) počet prvků množiny x in s Test zda prvek x se nachází v množině s s1 <= s2 Test zda s1 je podmnožinou s2 union nebo operátor | Sjednocení množin intersection nebo operátor & Průnik množin difference nebo operátor - Rozdíl množin symmetric_difference nebo operátor ^ Položky z jedné z množin nenacházející se v množině druhé 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