# Struktury, zřetězený seznam Tato kapitola zejména uvede implementaci «zřetězeného seznamu» – datové struktury složené z buněk (uzlů) provázaných odkazy. K tomu budeme potřebovat «složené hodnoty» – uzel musí obsahovat jak hodnotu tak odkaz na další prvek a musí být tedy «složeného typu». Složené typy v jazyce C zavádíme pomocí tzv. «struktur». Konečně jednotlivé buňky budou uložené v poli a odkazy mezi nimi tak můžeme realizovat dvěma způsoby – indexy nebo ukazateli. ## Struktury Struktura je jazyková konstrukce, jenž nám umožní zavést do programu nový «složený typ». Protože typ zavádíme – není součástí jazyka – říká se mu někdy i «uživatelský typ». ### Složená hodnota │ • hodnota složená z jiných hodnot │ • podhodnoty = složky │ • příklad: uspořádaná dvojice │ • příklad: seznam (v Pythonu) Než budeme diskutovat složené typy, připomeneme si pojem «složené hodnoty». Jedná se o hodnotu, kterou lze chápat jako kombinaci několika jednodušších hodnot, a kterou můžeme smysluplně z takových jednodušších hodnot složit a opět je na ně rozložit. Typickým příkladem složené hodnoty je uspořádaná dvojice (nebo obecněji ⟦n⟧-tice), která vzniká kartézským součinem. Dvojici můžeme přímočaře vytvořit (konstruovat) ze dvou jednodušších hodnot a díky projekcím ji můžeme také jednoduše rozložit na dvě jednodušší hodnoty. Typům, které zastřešují hodnoty tohoto charakteru, proto říkáme «součinové typy». Součinové typy mají charakteristické operace: podobně, jako hodnoty aritmetických typů můžeme sčítat nebo násobit, hodnoty součinových typů můžeme: • skládat (konstruovat) z jejich jednotlivých složek, • vytvářet nové hodnoty nahrazením některé složky za novou, • zjistit hodnotu některé složky (projekce). ### Složený typ │ • typ složené hodnoty │ • určuje typy složek │ • vztahuje se i na objekty ### Složené hodnoty vs objekty │ • složený objekt → má podobjekty │ • složená hodnota → má složky │ • podobjekt obsahuje hodnotu │ • složky musí „pasovat“ na podobjekty Abychom mohli s hodnotami v programech pracovat, musíme být schopni nějak si je pamatovat – a u složených hodnot tomu není jinak. Pro uložení «složené hodnoty» se v jazyce C použije «složený objekt», a to takový, že každé «složce» hodnoty odpovídá «podobjekt» příslušného typu (vzpomeňte si, že typ objektu a typ v něm uložené hodnoty se musí shodovat, a že podobjekt je také sám o sobě plnohodnotným objektem). Díky tomuto uspořádání můžeme složené hodnoty přímo «upravovat po složkách», pomocí přiřazení do podobjektu (to, co budeme v jazyce C zapisovat přibližně jako ‹X.i = N›). Protože podhodnoty a podobjekty se na sebe mapují 1:1, je zaručeno, že výsledek přiřazení do podobjektu je tentýž, jako „kanonická“ posloupnost operací: 1. načti složenou hodnotu ⟦V⟧ z objektu ⟦X⟧, 2. vytvoř novou složenou hodnotu ⟦W⟧ výměnou ⟦i⟧-té složky ve ⟦V⟧, tzn. ⟦W = (V₁, …, Vᵢ₋₁, N, Vᵢ₊₁, …, Vₙ)⟧, 3. takto vzniklou hodnotu ⟦W⟧ ulož zpátky do objektu ⟦X⟧. ### Záznamový typ │ • anglicky «record type» │ • obecná, běžná konstrukce │ • pevné typy a pořadí složek │ • «pojmenované» složky Záznamový typ – struktura – je zřejmě nejběžnějším prostředkem k zavedení součinových typů do programovacího jazyka. Vytvoříme-li příslušnými jazykovými prostředky nový součinový typ, automaticky tím získáme: 1. možnost konstruovat hodnoty tohoto typu tak, že dodáme hodnotu pro každou složku, 2. možnost vytvářet nové hodnoty z již existujících tak, že změníme hodnotu některé složky, 3. možnost získat hodnotu libovolné složky. Je zároveň relativně běžné (i mimo jazyk C), že bod 2 je realizován skrze přiřazení do podobjektu, jak bylo diskutováno výše. Z hlediska výrazových možností jazyka jsou obě možnosti ekvivalentní. ### Struktura │ • záznamový typ v C │ • zavedení klíčovým slovem ‹struct› │ • tělo: typy a jména složek │ • jméno typu: ‹struct jméno› │ • literál neexistuje Nyní si stručně popíšeme syntaxi záznamových typů v jazyce C. Nový záznamový typ zavedeme klíčovým slovem ‹struct› například takto: struct pair /* C */ { int a; int b; }; Hodnoty uvedeného typu budou mít dvě složky, obě typu ‹int›, tzn. budou to celá čísla se znaménkem. Identifikátor ‹pair› není sám o sobě názvem typu, musíme ho nadále uvádět uvozený klíčovým slovem ‹struct›. Deklarace proměnné typu ‹struct pair› tedy vypadá například takto: int main() { struct pair var; } ### Inicializace │ • proměnné lze inicializovat │ • proběhne po složkách │ • ‹struct pair x = { 1, 2 };› │ • ‹… x = { .a = 1, .b = 2 };› │ • inicializace ≠ přiřazení Podobně jako u jednoduchých objektů, není-li hodnota objektu inicializovaná, není dovoleno z objektu číst.¹ Inicializaci záznamové proměnné zapisujeme složenými závorkami. Jména složek jsou při inicializaci nepovinná: int main() { struct pair foo = { .a = 1, .b = 2 }, bar = { -1, 3 }; } ¹ Opět zde ale platí, že inicializovaný «podobjekt» je možné používat bez ohledu na to, je-li inicializovaný objekt jako celek. ### Přístup ke složce │ • výraz tvaru ‹e₁.jméno› │ • může se vyhodnotit na objekt │ ◦ když je ‹e₁› objekt │ ◦ při dočasném zhmotnění […] │ • adresy musí být „pohromadě“ ### Nepřímý přístup │ • výraz tvaru ‹e₁->jméno› │ • je vždy objektem (l-hodnotou) │ • ‹e₁› musí být typu ukazatel │ • vstupní podmínka: platnost ‹e₁› ### Přiřazení │ • uložení hodnoty to objektu │ • u struktur proběhne po složkách │ • rekurzivně do podstruktur, atp. ### Pole ve struktuře │ • jméno může označovat i pole │ • každému prvku odpovídá složka │ • struktura je stále hodnota │ • pole stále není hodnota > struct array { int data[ 3 ]; } > > int f( struct array a ) > { > assert( a.data[ 0 ] == 1 ); > } > > int main() > { > struct array arr = { { 1, 2, 3 } }; > f( arr ); > } ### Dočasné zhmotnění │ • co znamená přístup do pole │ ◦ ‹e₁[e₂]› ~ ‹*(e₁ + e₂)› │ ◦ co je ‹f().foo[1]›? │ • při přístupu vytvoříme objekt │ • zanikne s koncem příkazu ## Zřetězený seznam Nejjednodušší dynamická datová struktura – taková, která umožňuje uložit a později zpracovávat předem neznámý počtem prvků – je zřetězený seznam. Klíčovou vlastností datových struktur obecně je, že existují na úrovni «objektů» (nikoliv hodnot). Zřetězený seznam (a později i další datové struktury) tedy budeme zejména chápat jako vzájemně provázaný «soubor objektů». ### Princip │ • složený ze samostatných uzlů │ • uložených na nezávislých adresách │ • každý reprezentuje jeden prvek │ • ukazatel na další uzel ### Výhody │ • jednoduchá implementace │ • velmi flexibilní │ ◦ fronta │ ◦ zásobník │ ◦ seznam (iterace) ### Nevýhody │ • nahodilý přístup do paměti │ • větší paměťová režie │ • nelze indexovat │ • nešikovná abstrakce ### Reprezentace │ • struktura pro uzel │ • lze mít samostatnou hlavu │ • ‹struct node *next› │ • pevný typ uložené hodnoty ### Dvojité řetězení │ • jednodušší odstranění uzlu │ • složitější přidání uzlu │ • výrazně větší režie │ • obvykle se nepoužívá ### Základní operace │ • vložení │ • iterace │ • odstranění ### Iterace │ • při práci s celým seznamem │ • typické využití cyklu ‹for›: │ ◦ ‹struct node *n = head› │ ◦ podmínka ‹n› │ ◦ posun ‹n = n->next› ### Vložení uzlu │ • potřebujeme znát pozici │ • ukazatel na předchozí uzel │ • na začátek → triviální │ • na konec → ukazatel navíc ### Odstranění │ • opět potřebujeme znát pozici │ • ukazatel na «předchozí» uzel │ • ze začátku → triviální │ • z konce → dvojité řetězení