Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
Obě strany předchozí revizePředchozí verze | |||
pitel:ial:ial_du2 [19. 11. 2013, 13.24:34] – file pitel | pitel:ial:ial_du2 [30. 12. 2022, 13.43:01] (aktuální) – upraveno mimo DokuWiki 127.0.0.1 | ||
---|---|---|---|
Řádek 1: | Řádek 1: | ||
+ | ====== 2. domácí úloha ====== | ||
+ | [[wp> | ||
+ | <file c c401.c> | ||
+ | /* ------------------------------ c401.c ------------------------------------ */ | ||
+ | /* Téma: Rekurzivní implementace operací nad BVS (Dynamické pridel.pam.) | ||
+ | ** | ||
+ | ** | ||
+ | ** Petr Přikryl, duben 1996 | ||
+ | ** Petr Přikryl, listopad 1997 | ||
+ | ** | ||
+ | ** | ||
+ | ** Implementujte rekurzivním způsobem operace nad binárním vyhledávacím | ||
+ | ** stromem (BVS; v angličtině BST -- Binary Search Tree). | ||
+ | ** | ||
+ | ** Klíčem uzlu stromu je jeden znak (obecně jím může být cokoliv, podle | ||
+ | ** čeho se vyhledává). Užitečným (vyhledávaným) obsahem je zde integer. | ||
+ | ** Uzly s menším klíčem leží vlevo, uzly s větším klíčem leží ve stromu | ||
+ | ** vpravo. Využijte dynamického přidělování paměti. | ||
+ | ** Rekurzivním způsobem řešte následující procedury a funkce: | ||
+ | ** | ||
+ | ** | ||
+ | ** | ||
+ | ** | ||
+ | ** | ||
+ | ** | ||
+ | ** | ||
+ | ** Přesnou definici typů naleznete v souboru c401.h; pro přehled -- | ||
+ | ** ADT BVS je reprezentováno kořenovým ukazatelem stromu typu tBSTNodePtr. | ||
+ | ** Uzel stromu (struktura typu tBSTNode) obsahuje ukazatele LPtr a RPtr na levý | ||
+ | ** a pravý podstrom, složku char KEY -- klíč, podle kterého se vyhledává, | ||
+ | ** a int BSTNodeCont -- obsah uzlu (demonstrativne integer). | ||
+ | ** | ||
+ | ** !Upozorneni! Je treba, abyste spravne rozlisovali, | ||
+ | ** operator * na samotny ukazatel (tj. kdyz budeme chtit zapsat urcitou hodnotu | ||
+ | ** do tohoto pointeru, typicky modifikacni operace) a kdy budeme pracovat pouze | ||
+ | ** se samotnym ukazatelem (vyhledavaci fce). V techto ulohach poznate tuto | ||
+ | ** skutecnost predevsim pomoci prototypu techto fci. V situaci, kdy pracujeme | ||
+ | ** s ukazatelem na ukazatel, je treba pouzit dereferenci. | ||
+ | ** | ||
+ | ** Poznámka: nepoužívejte nestandardní příkazy (exit(), | ||
+ | */ | ||
+ | |||
+ | #include " | ||
+ | int solved; | ||
+ | int errflg; | ||
+ | |||
+ | void BSTInit (tBSTNodePtr *RootPtr) { | ||
+ | /* Počáteční inicializace stromu před prvním použitím datové struktury. | ||
+ | ** Počáteční testování ukazatele není možné, protože obsahuje nedefinovanou | ||
+ | ** (tj. libovolnou) hodnotu, která ovšem neodráží reálný stav. | ||
+ | ** | ||
+ | ** Všimněte si, ze zde se poprvé v hlavičce objevuje typ ukazatel na ukazatel, | ||
+ | ** proto je treba pri práci s RootPtr(přiřazení) použít dereferenční operátor. | ||
+ | ** Ten bude ještě třeba použít v procedurách BSTDelete, BSTInsert a BSTDispose. | ||
+ | **/ | ||
+ | |||
+ | *RootPtr = NULL; //prazdny strom | ||
+ | |||
+ | } | ||
+ | |||
+ | |||
+ | int BSTSearch (tBSTNodePtr RootPtr, char K, int *Content) { | ||
+ | /* Vyhledávání uzlu v BVS podle zadaného klíče K. Pokud je nalezen, vrací | ||
+ | ** funkce hodnotu TRUE a v proměnné Content se vrací obsah příslušného uzlu. | ||
+ | ** Pokud příslušný uzel není nalezen, vrací funkce hodnotu FALSE a obsah | ||
+ | ** proměnné Content není definován (to znamená, že do ní nebudete nic | ||
+ | ** přiřazovat). Při vyhledávání v binárním stromu bychom typicky použili | ||
+ | ** cyklus ukončený testem zahrnujícím stav dosažení listu nebo nalezení | ||
+ | ** uzlu s klíčem. V tomto případě ovšem test nepoužijte a problém řešte | ||
+ | ** rekurzivním volání této funkce (nedeklarujte žádnou pomocnou proceduru | ||
+ | ** nebo funkci). | ||
+ | **/ | ||
+ | |||
+ | if (RootPtr == NULL) { //kdy je prazdny strom | ||
+ | return FALSE; //neni co hledat | ||
+ | } else if (RootPtr -> Key != K) { //jinak kdyz klic neni hledanym | ||
+ | if (RootPtr -> Key > K) { //kdyz je aktualni klic vetsi nez hledany | ||
+ | return BSTSearch(RootPtr -> LPtr, K, Content); //zanor se doleva | ||
+ | } else { | ||
+ | return BSTSearch(RootPtr -> RPtr, K, Content); //a kdyz mensi tak doprava | ||
+ | } | ||
+ | } else { | ||
+ | *Content = RootPtr -> BSTNodeCont; | ||
+ | return TRUE; //a nasel jsem | ||
+ | } | ||
+ | |||
+ | } | ||
+ | |||
+ | |||
+ | void BSTInsert (tBSTNodePtr* RootPtr, char K, int Content) { | ||
+ | /* Vloží do stromu hodnotu Content s klíčem K. Pokud již uzel | ||
+ | ** se zadaným klíčem existuje, nahradí se obsah uzlu novou hodnotou. | ||
+ | ** Nově vytvořený uzel nechť je vždy listem stromu. Řešte rekurzivně. | ||
+ | ** | ||
+ | ** Tato rekurzivní implementace je poněkud neefektivní, | ||
+ | ** každém rekurzivním zanoření musí kopírovat celý integer " | ||
+ | ** obsah uzlu). V praxi by se tento problém řešil například jedním | ||
+ | ** z těcho způsobů: | ||
+ | ** - předáváním proměnné " | ||
+ | ** při volání proměnnou a není možné přímo zapsat hodnotu); | ||
+ | ** - deklarací vnitřní procedury, které by se parametr předal odkazem; | ||
+ | ** vnější procedura by sloužila jen jako obal (nevolala by se | ||
+ | ** rekurzivně); | ||
+ | ** - při využití předchozí varianty by se do rekurzivní procedury předával | ||
+ | ** předem naplněný nový uzel, který by se na závěr zrušil v případě, | ||
+ | ** že se uzel nepodařilo zařadit (pokud už uzel s tímto klíčem existoval, | ||
+ | ** přepsal by se jen obsah, případně by se uzly vyměnily a ke zrušení | ||
+ | ** by se předal starý uzel); | ||
+ | ** | ||
+ | ** Nerekurzivní varianta by v tomto případě byla efektivnější jak z hlediska | ||
+ | ** rychlosti, tak z hlediska paměťových nároků. Zde však jde o školní | ||
+ | ** příklad. Nedeklarujte žádnou pomocnou proceduru nebo funkci, problém | ||
+ | ** řešte rekurzivním voláním procedury samé. | ||
+ | ** | ||
+ | ** POZOR: Vzhledem k jisté složitosti rekurzívního volání této fce zde uvádím | ||
+ | ** příklad jak funkci zavolat (když jsme přijali RootPtr jako ukazatel na | ||
+ | ** ukazatel). Správné zavolání např. na levý podstrom: | ||
+ | ** BSTInsert(& | ||
+ | */ | ||
+ | |||
+ | if (*RootPtr == NULL) { //kdyz vkladam do prazdnyho stromu | ||
+ | tBSTNodePtr uzel; //novy uzel | ||
+ | if ((uzel = malloc(sizeof(struct tBSTNode))) == NULL) { //zkusime ho alokovat | ||
+ | return; //nebo umrem | ||
+ | } | ||
+ | uzel -> Key = K; //vloz kliv | ||
+ | uzel -> BSTNodeCont = Content; //vloz obsah | ||
+ | uzel -> LPtr = NULL; //prazdny strom nema listy | ||
+ | uzel -> RPtr = NULL; | ||
+ | *RootPtr = uzel; // a konecne ho vloz | ||
+ | } else if (K < (*RootPtr) -> Key) { //nebo kdyz klic je mensi | ||
+ | BSTInsert(& | ||
+ | } else if (K > (*RootPtr) -> Key) { //kdyz vetsi | ||
+ | BSTInsert(& | ||
+ | } else { | ||
+ | (*RootPtr) -> BSTNodeCont = Content; //kdyz uz se nemam kam norit, nalezl jsem a vloz obsah | ||
+ | } | ||
+ | |||
+ | } | ||
+ | |||
+ | |||
+ | /* POZOR NASLEDUJÍCÍ PROCEDURA BUDE POUŽITA DÁLE, | ||
+ | ** PREČTĚTE SI PROTO PODROBNĚ NEJPRVE KOMENTÁŘ K PROCEDUŘE BSTDELETE(), | ||
+ | ** NEŽ ZAČNETE VYTVÁŘET REPLACEBYRIGHTMOST(). | ||
+ | */ | ||
+ | void ReplaceByRightmost (tBSTNodePtr PtrReplaced, | ||
+ | /* Pomocná procedura pro vyhledání, | ||
+ | ** uzlu v podstromu určeném ukazatelem RootPtr. Na vstupu se předpokládá | ||
+ | ** hodnota ukazatele RootPtr různá od NULL (zajistěte to testováním před | ||
+ | ** volání procedury). Dále se předpokládá, | ||
+ | ** ukazuje na uzel, který se má naplnit hodnotami vyhledaného uzlu. | ||
+ | */ | ||
+ | tBSTNodePtr ptr; /* používejte tento pomocný ukazatel */ | ||
+ | ptr = NULL; | ||
+ | |||
+ | if ((*RootPtr) -> RPtr != NULL) { //kdyz vravo neco je | ||
+ | ReplaceByRightmost(PtrReplaced, | ||
+ | } else { //no a kdyz tam nic neni | ||
+ | PtrReplaced -> BSTNodeCont = (*RootPtr) -> BSTNodeCont; | ||
+ | PtrReplaced -> Key = (*RootPtr) -> Key; //nahrad klic | ||
+ | ptr = *RootPtr; //zalohuj koren | ||
+ | *RootPtr = (*RootPtr) -> LPtr; //novy koren | ||
+ | free(ptr); | ||
+ | } | ||
+ | |||
+ | } | ||
+ | |||
+ | |||
+ | void BSTDelete (tBSTNodePtr *RootPtr, char K) { | ||
+ | /* Zruší uzel stromu, který obsahuje klíč K. Pokud uzel se zadaným klíčem | ||
+ | ** neexistuje, nedělá nic. Veškeré manipulace řešte rekurzivně. | ||
+ | ** | ||
+ | ** Pokud má rušený uzel jen jeden podstrom, pak jej zdědí otec. Pokud má | ||
+ | ** oba podstromy, pak je rušený uzel nahrazen nejpravějším uzlem levého | ||
+ | ** podstromu. Pozor! Nejpravější uzel nemusí být listem. Pro tuto operaci | ||
+ | ** jsme deklarovali proceduru ReplaceByRightmost -- viz. její komentář | ||
+ | ** uveden výše. | ||
+ | ** POZOR: Vzhledem k jisté složitosti rekurzívního volání této fce zde uvádím | ||
+ | ** příklad jak funkci zavolat (když jsme přijali RootPtr jako ukazatel na | ||
+ | ** ukazatel). Správné zavolání např. na levý podstrom: | ||
+ | ** BSTDelete(& | ||
+ | ** Podobně je tomu tak i u ReplaceByRightMost(). | ||
+ | ** Například: | ||
+ | */ | ||
+ | tBSTNodePtr ptr; /* používejte tento pomocný ukazatel */ | ||
+ | ptr=NULL; | ||
+ | |||
+ | if (*RootPtr != NULL) { //kdyz je co mazat | ||
+ | if (K < (*RootPtr) -> Key) { //kdyz je klic mensi | ||
+ | BSTDelete(& | ||
+ | } else { | ||
+ | if (K > (*RootPtr) -> Key) { //kdyz je klic vetsi | ||
+ | BSTDelete(& | ||
+ | } else { | ||
+ | ptr = *RootPtr; //zalohuj koren | ||
+ | if (ptr -> RPtr == NULL) { //kdyz koren vpravo nic nema | ||
+ | (*RootPtr) = ptr -> LPtr; //koren bude levej | ||
+ | free(ptr); | ||
+ | } else { | ||
+ | if (ptr -> LPtr == NULL) { //kdyz koren vlevo nic nema | ||
+ | (*RootPtr) = ptr -> RPtr; //koren bude prvej | ||
+ | free(ptr); | ||
+ | } else { | ||
+ | ReplaceByRightmost(*RootPtr, | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | | ||
+ | } | ||
+ | |||
+ | |||
+ | void BSTDispose (tBSTNodePtr *RootPtr) { | ||
+ | /* Korektně zruší celý binární vyhledávací strom. Zvolte nejvýhodnější | ||
+ | ** druh rekurzívního průchodu stromem. Nedeklarujte žádné pomocné procedury | ||
+ | ** nebo funkce. | ||
+ | ** POZOR: Vzhledem k jisté složitosti rekurzívního volání této fce zde uvádím | ||
+ | ** příklad jak funkci zavolat (když jsme přijali RootPtr jako ukazatel na | ||
+ | ** ukazatel). Správné zavolání např. na levý podstrom: | ||
+ | ** BSTDispose(& | ||
+ | */ | ||
+ | |||
+ | if (*RootPtr != NULL) { //kdyz je co sidposovat | ||
+ | BSTDispose(& | ||
+ | BSTDispose(& | ||
+ | free(*RootPtr); | ||
+ | *RootPtr = NULL; //a oznac za prazdny | ||
+ | } | ||
+ | |||
+ | //solved = FALSE; | ||
+ | } | ||
+ | |||
+ | /* --------------------------- konec c401.c -------------------------------- */ | ||
+ | </ | ||
+ | |||
+ | <file c c402.c> | ||
+ | /* --------------------------- c402.c --------------------------------------- */ | ||
+ | /* Téma: Nerekurzivní implementace operací nad BVS | ||
+ | ** | ||
+ | ** | ||
+ | ** Petr Přikryl, květen 1998 | ||
+ | ** | ||
+ | ** | ||
+ | ** S využitím dynamického přidělování paměti, implementujte | ||
+ | ** následující operace nad binárním vyhledávacím stromem -- vše NEREKURZIVNĚ. | ||
+ | ** (BT znamená Binary Tree; Tato předpona je u procedur uvedena kvůli možné | ||
+ | ** kolizi jmen v ostatních příkladech): | ||
+ | ** | ||
+ | ** | ||
+ | ** | ||
+ | ** | ||
+ | ** | ||
+ | ** | ||
+ | ** | ||
+ | ** | ||
+ | ** U všech procedur, které využívají některý z průchodů stromem, deklarujte | ||
+ | ** lokální proceduru nazvanou Leftmost -- nalezení nejlevějšího uzlu | ||
+ | ** v podstromu (viz přednášky, | ||
+ | ** | ||
+ | ** Definice typů naleznete v souboru c402.h; uzel stromu je typu tBTNode, | ||
+ | ** ukazatel na něj je typu tBTNodePtr, uzel obsahuje položku int Cont | ||
+ | ** (obsah) a ukazatele LPtr a RPtr. | ||
+ | ** | ||
+ | ** Příklad slouží zejména k procvičení nerekurzivních zápisů algoritmů | ||
+ | ** nad stromy. Než začnete tento příklad řešit, prostudujte si důkladně | ||
+ | ** principy převodu rekurzivních algoritmů na nerekurzivní. Programování | ||
+ | ** je především inženýrská disciplína, | ||
+ | ** místo. Pokud se vám zdá, že by něco šlo zapsat optimálněji, | ||
+ | ** si všechny detaily vašeho řešení. Povšimněte si typického umístění akcí | ||
+ | ** pro různé typy průchodů. Zamyslete se nad modifikací řešených algoritmů | ||
+ | ** pro výpočet počtu uzlů stromu, počtu listů stromu, výšky stromu a pro | ||
+ | ** vytvoření zrcadlového obrazu stromu (pouze popřehazování ukazatelů bez | ||
+ | ** vytváření nových uzlů a rušení starých). | ||
+ | ** | ||
+ | ** Při průchodech stromem použijte ke zpracování uzlu proceduru BTWorkOut(). | ||
+ | ** Pro práci se zásobníky použijte rovněž předem připravené procedury | ||
+ | ** a funkce. K dispozici máte zásobníky pro hodnoty typu boolean | ||
+ | ** a tBTNodePtr (SInit*, SPush*, STopPop*, SEmpty*, kde místo ' | ||
+ | ** ' | ||
+ | ** | ||
+ | ** !Upozornění! Je třeba, abyste spravně rozlišovali, | ||
+ | ** operátor * na samotný ukazatel a kdy budeme pracovat pouze se samotným | ||
+ | ** ukazatelem (prohledavaci fce). V techto úlohách poznáte tuto skutečnost | ||
+ | ** predevším pomocí prototypu těchto funkcí. V situaci, kdy pracujeme s | ||
+ | ** ukazatelem na ukazatel, je třeba použít dereferenci. | ||
+ | */ | ||
+ | #include " | ||
+ | int solved; | ||
+ | int errflg; | ||
+ | |||
+ | void BTWorkOut (tBTNodePtr Ptr) { | ||
+ | /* Pomocná procedura používaná při průchodech stromem. | ||
+ | ** Zpracuje uzel, na který ukazuje Ptr. | ||
+ | ** Nemodifikovat! | ||
+ | */ | ||
+ | |||
+ | if (Ptr == NULL) | ||
+ | printf(" | ||
+ | else | ||
+ | printf(" | ||
+ | } | ||
+ | | ||
+ | /* -------------------------------------------------------------------------- */ | ||
+ | /* Implementace zásobníků je velmi zjednodušena. Zdrojový text je formátován | ||
+ | ** s ohledem na úsporu místa a není příliš komentován (neberte si z toho | ||
+ | ** příklad -- když, tak odstrašující). Definice datovych struktur, viz. | ||
+ | ** hlavickovy soubor. | ||
+ | */ | ||
+ | |||
+ | /* *********************** OPERACE SE ZÁSOBNÍKEM **************************** */ | ||
+ | |||
+ | /* ----------------------- Zásobník ukazatelů: ------------------------------ */ | ||
+ | void SInitP (tStackP *S) { | ||
+ | /* inicializace zásobníku ukazatelů */ | ||
+ | S->top = 0; | ||
+ | } | ||
+ | |||
+ | void SPushP (tStackP *S, tBTNodePtr ptr) { | ||
+ | /* vloží hodnotu na vrchol zásobníku */ | ||
+ | if (S-> | ||
+ | printf(" | ||
+ | else { | ||
+ | S-> | ||
+ | S-> | ||
+ | } | ||
+ | } | ||
+ | |||
+ | tBTNodePtr STopPopP (tStackP *S) { | ||
+ | /* vrací odstraněnou hodnotu */ | ||
+ | if (S->top == 0) { | ||
+ | printf(" | ||
+ | return(NULL); | ||
+ | } | ||
+ | else { | ||
+ | return (S-> | ||
+ | } | ||
+ | } | ||
+ | |||
+ | bool SEmptyP (tStackP *S) { | ||
+ | /* test na prázdnost zásobníku */ | ||
+ | if (S->top == 0) | ||
+ | return(true); | ||
+ | else | ||
+ | return(false); | ||
+ | } | ||
+ | |||
+ | |||
+ | /* ----------------------- Zásobník boolovských hodnot: --------------------- */ | ||
+ | void SInitB (tStackB *S) { | ||
+ | /* inicializace zásobníku */ | ||
+ | S->top = 0; | ||
+ | } | ||
+ | |||
+ | void SPushB (tStackB *S,bool val) { | ||
+ | /* vloží hodnotu na vrchol zásobníku */ | ||
+ | if (S->top == MAXSTACK) | ||
+ | printf(" | ||
+ | else { | ||
+ | S-> | ||
+ | S-> | ||
+ | } | ||
+ | } | ||
+ | |||
+ | bool STopPopB (tStackB *S) { | ||
+ | /* vrací odstraněnou hodnotu */ | ||
+ | if (S->top == 0) { | ||
+ | printf(" | ||
+ | return(NULL); | ||
+ | } | ||
+ | else { | ||
+ | return(S-> | ||
+ | } | ||
+ | } | ||
+ | |||
+ | bool SEmptyB (tStackB *S) { | ||
+ | if (S->top == 0) | ||
+ | return(true); | ||
+ | else | ||
+ | return(false); | ||
+ | } | ||
+ | |||
+ | /* ---------------------------------- INIT ---------------------------------- */ | ||
+ | void BTInit (tBTNodePtr *RootPtr) { | ||
+ | /* Inicializace stromu. Smí se volat pouze před prvním použitím | ||
+ | ** konkrétního binárního stromu, protože neuvolňuje uzly neprázdného | ||
+ | ** stromu (ani to dělat nemůže). K rušení neprázdného stromu slouží | ||
+ | ** procedura BTDisposeTree (viz dále). | ||
+ | ** | ||
+ | ** Všimněte si, že zde se poprvé v hlavičce objevuje typ ukazatel na ukazatel, | ||
+ | ** proto je třeba při práci s RootPtr(přiřazení) použít dereferenční operator. | ||
+ | ** Ten bude ještě třeba použít v procedurách BTInsert() a BTDisposeTree(). | ||
+ | */ | ||
+ | |||
+ | *RootPtr = NULL; //prazdny strom | ||
+ | |||
+ | } | ||
+ | |||
+ | |||
+ | void BTInsert (tBTNodePtr *RootPtr, int Content) { | ||
+ | /* Vloží do stromu nový uzel s hodnotou ' | ||
+ | ** chápejte vytvářený strom jako binární vyhledávací strom (BVS = BST), | ||
+ | ** kde uzly s hodnotou menší než má otec leží v levém podstromu, uzly větší | ||
+ | ** leží vpravo. Pokud vkládaný uzel již existuje, neprovádí se nic (hodnota | ||
+ | ** se ve stromu vyskytuje maximálně jedenkrát). Pokud se vytváří nový uzel, | ||
+ | ** vzniká vždy jako list stromu. Řešte nerekurzivně. | ||
+ | */ | ||
+ | tBTNodePtr fptr; /* ukazatel na otcovský uzel F */ | ||
+ | tBTNodePtr ptr; /* pomocný ukazatel */ | ||
+ | bool myend; | ||
+ | |||
+ | /* V případě, kdy strom není prázdný, musíme vyhledat místo, kam by se nová | ||
+ | ** hodnota měla vložit. Pokud uzel se zadanou hodnotou již existuje, neděláme | ||
+ | ** nic. Pokud se bude uzel vytvářet, musíme si pamatovat ukazatel na otce, | ||
+ | ** na kterého bude nový uzel připojen. | ||
+ | */ | ||
+ | |||
+ | if (*RootPtr == NULL) { //kdyz mam prazdnys trom | ||
+ | if ((ptr = malloc(sizeof(struct tBTNode))) == NULL) { //zkusim alokovat pomocny uzel | ||
+ | return; //nebo umru | ||
+ | } | ||
+ | ptr -> Cont = Content; //novy obsah | ||
+ | ptr -> LPtr = NULL; // | ||
+ | ptr -> RPtr = NULL; // | ||
+ | *RootPtr = ptr; | ||
+ | } else { //kdyz uz ve stromu neco je | ||
+ | ptr = *RootPtr; //ulozim koren | ||
+ | while (ptr != NULL) { //dokud je nakej koren | ||
+ | fptr = ptr; //tak ten koren bude otec | ||
+ | if (ptr -> Cont == Content) { //kdyz uz takovy uzel existuje | ||
+ | return; //nedelej nic | ||
+ | } else if (ptr -> Cont > Content) { //kdyz je vkladany mensi nez aktualni | ||
+ | ptr = ptr -> LPtr; //jdi doleva | ||
+ | } else if (ptr -> Cont < Content) { //kdyz je vkladany vetsi nez aktualni | ||
+ | ptr = ptr -> RPtr; //jdi doprava | ||
+ | } | ||
+ | } | ||
+ | myend = true; //aby to nervalo chwarning | ||
+ | if ((ptr = malloc(sizeof(struct tBTNode))) == NULL) { //alokuj novy uzel | ||
+ | return; //nebo umri | ||
+ | } | ||
+ | ptr -> Cont = Content; //obsah | ||
+ | ptr -> LPtr = NULL; //list nema podprvky | ||
+ | ptr -> RPtr = NULL; | ||
+ | if (fptr -> Cont > Content) { //znovu se porovna novy obsah s otcem a zvoli se na kterou stranu se pripoji novy uzel | ||
+ | fptr -> LPtr = ptr; | ||
+ | } else { | ||
+ | fptr -> RPtr = ptr; | ||
+ | } | ||
+ | } | ||
+ | |||
+ | } | ||
+ | |||
+ | /* Nyní následuje sekce jednotlivých průchodů stromem, před tvorbou Leftmost | ||
+ | čtěte vždy i popisek nasledujíci procedury = implikace řešení daného Leftmost */ | ||
+ | |||
+ | /* ------------------------------ PREORDER ---------------------------------- */ | ||
+ | void Leftmost_Preorder (tBTNodePtr ptr, tStackP *Stack) { | ||
+ | /* Lokální procedura BTPreorder -- funkce viz přednášky. | ||
+ | ** Pohybuje se po levé větvi podstromu, až narazí na jeho nejlevější uzel. | ||
+ | ** Ukazatele na všechny navštívené uzly ukládá do zásobníku. Protože jde | ||
+ | ** o průchod typu preorder, je navštívený uzel současně zpracován, použijte | ||
+ | ** BTWorkOut(). | ||
+ | */ | ||
+ | |||
+ | while (ptr != NULL) { //dokud je co resit | ||
+ | SPushP(Stack, | ||
+ | BTWorkOut(ptr); | ||
+ | ptr = ptr -> LPtr; //bez doleva | ||
+ | } | ||
+ | |||
+ | } | ||
+ | |||
+ | void BTPreorder (tBTNodePtr RootPtr) { | ||
+ | /* Samotný nerekurzivní průchod typu pre-order, použijte dané Leftmost_Preorder | ||
+ | ** dle prednášek. | ||
+ | */ | ||
+ | tStackP Stack ; /* zásobník ukazatelů */ | ||
+ | tBTNodePtr ptr; /* pomocný ukazatel na uzel */ | ||
+ | |||
+ | SInitP(& | ||
+ | Leftmost_Preorder(RootPtr, | ||
+ | while (!SEmptyP(& | ||
+ | ptr = STopPopP(& | ||
+ | Leftmost_Preorder(ptr -> RPtr, & | ||
+ | } | ||
+ | |||
+ | } | ||
+ | |||
+ | |||
+ | /* ------------------------------ IN ORDER ---------------------------------- */ | ||
+ | void Leftmost_Inorder(tBTNodePtr ptr, tStackP *Stack) { | ||
+ | /* Lokální procedura BTInorder -- funkce viz přednášky. | ||
+ | ** Pohybuje se po levé větvi podstromu, až narazí na jeho nejlevější uzel. | ||
+ | ** Ukazatele na všechny navštívené uzly ukládá do zásobníku. | ||
+ | */ | ||
+ | |||
+ | while (ptr != NULL) { //dokud je co resit | ||
+ | SPushP(Stack, | ||
+ | ptr = ptr -> LPtr; //bez doleva | ||
+ | } | ||
+ | |||
+ | } | ||
+ | |||
+ | |||
+ | void BTInorder (tBTNodePtr RootPtr) { | ||
+ | /* Nerekurzivní průchod typu in-order. Pro zpracování uzlu volejte | ||
+ | ** proceduru BTWorkOut a pracujte s LeftMost_Inorder. | ||
+ | */ | ||
+ | tStackP Stack; | ||
+ | tBTNodePtr ptr; /* pomocný ukazatel na uzel */ | ||
+ | |||
+ | SInitP(& | ||
+ | Leftmost_Inorder(RootPtr, | ||
+ | while (!SEmptyP(& | ||
+ | ptr = STopPopP(& | ||
+ | BTWorkOut(ptr); | ||
+ | Leftmost_Inorder(ptr -> RPtr, & | ||
+ | } | ||
+ | |||
+ | } | ||
+ | |||
+ | |||
+ | /* ------------------------------ POST ORDER -------------------------------- */ | ||
+ | void Leftmost_Postorder (tBTNodePtr ptr, tStackP *StackP, tStackB *StackB) { | ||
+ | /* Lokální procedura pro Postorder -- funkce viz přednášky. | ||
+ | ** Pohybuje se po levé větvi podstromu, až narazí na jeho nejlevější uzel. | ||
+ | ** Ukazatele na všechny navštívené uzly ukládá do zásobníku. Protože jde | ||
+ | ** o průchod typu postorder, je současně do boolovského zásobníku ukládána | ||
+ | ** hodnota, která říká, že uzel byl navštíven poprvé (při průchodu do | ||
+ | ** levého podstromu) a že se tedy ještě nemá zpracovávat. | ||
+ | */ | ||
+ | |||
+ | while (ptr != NULL) { //dokud je co resit | ||
+ | SPushP(StackP, | ||
+ | SPushB(StackB, | ||
+ | ptr = ptr -> LPtr; //bez doleva | ||
+ | } | ||
+ | |||
+ | } | ||
+ | |||
+ | |||
+ | void BTPostorder (tBTNodePtr RootPtr) { | ||
+ | /* Nerekurzivní průchod typu post-order. Pro zpracování uzlu volejte | ||
+ | ** proceduru BTWorkOut. | ||
+ | */ | ||
+ | tStackP StackP; | ||
+ | tBTNodePtr ptr; /* pomocný ukazatel na uzel */ | ||
+ | tStackB StackB; | ||
+ | |||
+ | SInitP(& | ||
+ | SInitB(& | ||
+ | Leftmost_Postorder(RootPtr, | ||
+ | while (!SEmptyP(& | ||
+ | ptr = STopPopP(& | ||
+ | SPushP(& | ||
+ | if (STopPopB(& | ||
+ | SPushB(& | ||
+ | Leftmost_Postorder(ptr -> RPtr, & | ||
+ | } else { //kdyz uz jsem v uzlu byl | ||
+ | STopPopP(& | ||
+ | BTWorkOut(ptr); | ||
+ | } | ||
+ | } | ||
+ | |||
+ | } | ||
+ | |||
+ | /* ------------------------------ DISPOSE ----------------------------------- */ | ||
+ | void BTDisposeTree (tBTNodePtr *RootPtr) | ||
+ | /* Zruší všechny uzly stromu -- uvolní jimi zabíraný prostor voláním | ||
+ | ** standardní funkce free. | ||
+ | ** | ||
+ | ** Pozn.: při rušení uzlů stromu není důležité, | ||
+ | ** proto můžete uvažovat i jiné varianty, než klasické typy průchodu stromem. | ||
+ | */ | ||
+ | tStackP S; /* zásobník ukazatelů */ | ||
+ | tBTNodePtr ptr; /* pomocný ukazatel na uzel */ | ||
+ | |||
+ | if (*RootPtr != NULL) { //kdyz neni prazdny strom | ||
+ | SInitP(& | ||
+ | do { | ||
+ | if (*RootPtr == NULL && !SEmptyP(& | ||
+ | *RootPtr = STopPopP(& | ||
+ | } else { | ||
+ | if ((*RootPtr) -> RPtr != NULL) { //kdyz vpravo neco je | ||
+ | SPushP(& | ||
+ | } | ||
+ | ptr = *RootPtr; //zalohuj koren | ||
+ | *RootPtr = (*RootPtr) -> LPtr; //novy koren | ||
+ | free(ptr); | ||
+ | } | ||
+ | } while (!SEmptyP(& | ||
+ | } | ||
+ | |||
+ | } | ||
+ | |||
+ | /* ----------------------------- konec c402.c ------------------------------- */ | ||
+ | </ | ||
+ | |||
+ | <file c c403.c> | ||
+ | /* ------------------------------- c403.c ----------------------------------- */ | ||
+ | /* Téma: Vyhledávací tabulka v neseřazeném poli se zarážkou (optimalizace) | ||
+ | ** | ||
+ | ** | ||
+ | ** | ||
+ | ** | ||
+ | ** | ||
+ | ** Implementujte vyhledávací tabulku podle následujících požadavků. | ||
+ | ** Tabulka je implementována v poli, obsah prvků pole není seřazen. | ||
+ | ** Při vyhledávání se sekvenčně prochází celé využité pole s využitím | ||
+ | ** takzvané zarážky. Maximální kapacita tabulky je tedy o jedničku nižší, | ||
+ | ** než maximální využitelná kapacita pole. Implementujte následující procedury | ||
+ | ** a funkce (zkratka AS pochází ze slova Array = pole a Sentinel = zde zarážka): | ||
+ | ** | ||
+ | ** | ||
+ | ** | ||
+ | ** | ||
+ | ** | ||
+ | ** Při každém vyhledání se optimalizuje doba vyhledávání často hledaných | ||
+ | ** položek tím, že se nalezená položka vždy posunuje o jedno místo směrem | ||
+ | ** k začátku pole. | ||
+ | ** | ||
+ | ** Definici typů naleznete v souboru c403.h. Tabulka je reprezentována | ||
+ | ** datovou strukturou typu tASTable, která se skládá z pole ' | ||
+ | ** poslední využité položky pole ' | ||
+ | ** typu tASData, ve kterých se nachází složka Key (klíčem je pro jednoduchost | ||
+ | ** číslo typu integer) a obsah Cont (demonstrativně int). Při implementaci těl | ||
+ | ** řešených procedur uvažujte maximální rozměr pole ASSize (viz poznámka | ||
+ | ** v c403.h). | ||
+ | ** | ||
+ | ** Důležitým rysem vyhledávacích metod je počet porovnávání vyhledávaného | ||
+ | ** klíče s klíči prohledávaných položek pole. K porovnávání využívejte | ||
+ | ** povinně funkce ASCompare (viz dále). Počet porovnávání omezte | ||
+ | ** na minimum. To znamená, že nebudete volat podruhé funkci ASCompare | ||
+ | ** pro stejné klíče tam, kde jste si mohli výsledek porovnání zapamatovat | ||
+ | ** v pomocné proměnné. | ||
+ | */ | ||
+ | |||
+ | #include " | ||
+ | int ASCompNum; | ||
+ | int solved; | ||
+ | int errflg; | ||
+ | |||
+ | int ASCompare (int k1, int k2) { | ||
+ | ASCompNum = ASCompNum + 1; /* počet porovnání */ | ||
+ | if (k1 < k2) /* porovnání dvou klíčů */ | ||
+ | return(-1); | ||
+ | else if (k1 == k2) | ||
+ | return(0); | ||
+ | else /* k1 > k2 */ | ||
+ | return(1); | ||
+ | } | ||
+ | |||
+ | void ASError() { | ||
+ | printf(" | ||
+ | errflg = TRUE; | ||
+ | } | ||
+ | /* ------------------------------------------------------------------------- */ | ||
+ | void ASInit(tASTable *Tab) { | ||
+ | /* Inicializace tabulky (výsledkem je prázdná tabulka). | ||
+ | ** Inicializace tabulky se provede tak, že se index posledního prvku nastaví na | ||
+ | ** hodnotu -1. Hodnoty prvků ani klíčů se v tabulce nemění. | ||
+ | */ | ||
+ | |||
+ | Tab -> last = -1; | ||
+ | |||
+ | } | ||
+ | |||
+ | |||
+ | int ASSearch (tASTable *Tab, int key, int* ind) { | ||
+ | /* Vyhledávání v NESEŘAZENÉM poli se zarážkou a s přesunem nalezené | ||
+ | ** položky o jednu pozici dopředu (výměna s předchozí položkou). | ||
+ | ** | ||
+ | ** Vyhledávacím klíčem je hodnota key. Funkce vrací příznak, zda byl prvek | ||
+ | ** nalezen. Pokud ne (vrací false), pak se v proměnné ' | ||
+ | ** volná pozice, na kterou se může prvek vložit. | ||
+ | ** Pokud byl prvek nalezen (vrací true), došlo k jeho posunutí o jednu | ||
+ | ** pozici dopředu a v proměnné ind se vrací nová pozice nalezeného prvku. | ||
+ | ** | ||
+ | ** Pro porovnání dvou klíčů používejte předdefinovanou funkci ASCompare | ||
+ | ** (viz. výše). Vzhledem k tomu, že se při vyhledávání vždy používá | ||
+ | ** zarážka, bude minimální počet porovnání (při prázdné tabulce) roven 1. | ||
+ | ** | ||
+ | ** POZOR!!! | ||
+ | ** Při vložení zarážky se hodnota ' | ||
+ | ** na pozici ' | ||
+ | ** vy ale hodnotu zarážky nastavte na -1, aby se vám shodovaly výsledky testů! | ||
+ | */ | ||
+ | |||
+ | Tab -> arr[Tab -> last + 1].Key = key; //zarazka klice | ||
+ | Tab -> arr[Tab -> last + 1].Cont = -1; //zarazka obsahu | ||
+ | unsigned int index = 0; //index pole | ||
+ | while (ASCompare(key, | ||
+ | index++; // | ||
+ | } | ||
+ | if (index != Tab -> last + 1) { //kdyz jsme nenasli zarazku, budeme prohazovat prvky | ||
+ | if (index > 0) { //prvek uplne na zacatku uz by nebylo s cim prohodit | ||
+ | tASData swap = Tab -> arr[index]; // | ||
+ | Tab -> arr[index] = Tab -> arr[index - 1]; //prohodime prvky | ||
+ | Tab -> arr[index - 1] = swap; //vlozime nalezeny prvek | ||
+ | index--; //taku by bylo dobry aby index ukazoval spravne ;) | ||
+ | } | ||
+ | *ind = index; //nastavime nalezeny index | ||
+ | return TRUE; //a skoncime | ||
+ | } | ||
+ | *ind = index; //nastavime nalezeny index (na prazdny prvek) | ||
+ | return FALSE; //skoncime | ||
+ | |||
+ | } | ||
+ | |||
+ | |||
+ | void ASInsert (tASTable *Tab, int Key, int Content) { | ||
+ | /* Vloží novou položku s obsahem Content a klíčem Key do tabulky Tab. | ||
+ | ** | ||
+ | ** Pokud by vložením další položky došlo k přeplnění Tab (pokud by nešlo | ||
+ | ** při dalším vyhledávání uložit zarážku), volejte proceduru ASError() | ||
+ | ** a novou položku nevkládejte. | ||
+ | ** | ||
+ | ** Pokud daná položka (udaná klíčem Key) v poli již existuje, přiřadí se do | ||
+ | ** odpovídající složky záznamu nový obsah. Při vyhledávání již existující | ||
+ | ** položky využijte dříve implementovanou funkci ASSearch (to znamená, že se | ||
+ | ** existující a modifikovaná položka automaticky posune dopředu). | ||
+ | */ | ||
+ | |||
+ | int index = 0; //index polozky v poli | ||
+ | short nasli = ASSearch(Tab, | ||
+ | if (nasli) { //kdyz uz klic existuje | ||
+ | Tab -> arr[index].Cont = Content; //zapiseme novou hodnutu | ||
+ | } else { //klic neexistuje, vlozime novy | ||
+ | if (index > ASSize - 2) { //bacha, lezem za roh (-2 kvuli zarazce a indexovani od 0) | ||
+ | ASError(); | ||
+ | } else { //vlezeme se | ||
+ | Tab -> arr[index].Key = Key; //novy klic | ||
+ | Tab -> arr[index].Cont = Content; //novy obsah | ||
+ | Tab -> last = index; //nova posledni prazdna polozka | ||
+ | } | ||
+ | } | ||
+ | |||
+ | } | ||
+ | |||
+ | /* -------------------------- konec c403.c --------------------------------- */ | ||
+ | </ |