Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

--- 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>Binary search tree]]
+<file c c401.c>
+/* ------------------------------ c401.c ------------------------------------ */
+/* Téma: Rekurzivní implementace operací nad BVS (Dynamické pridel.pam.)
+**                           Vytvořil: Petr Přikryl, listopad 1994
+**                           Úpravy:   Andrea Němcová, prosinec 1995
+**                                     Petr Přikryl, duben 1996
+**                                     Petr Přikryl, listopad 1997
+**           Přepracované do jazyku c: Martin Tuček, rijen 2005
+**
+** 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:
+**
+**   BSTInit ...... inicializace vyhledávacího stromu
+**   BSTSearch .... vyhledávání hodnoty uzlu zadaného klíčem
+**   BSTInsert .... vkládání nové hodnoty
+**   BSTDelete .... rušení uzlu se zadaným klíčem
+**   BSTDispose ... rušení celého stromu
+**
+** 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, kdy pouzit dereferencni
+** 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(),...) a operace.
+*/
+#include "c401.h"
+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; //nasel jsem a precetl obsah
+ 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í, protože se při
+** každém rekurzivním zanoření musí kopírovat celý integer "Content" (obecně
+** 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é "Content" odkazem (v tom případě je nutné dosazovat
+**    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(&((*RootPtr)->LPtr), K, Content)
+*/
+ 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(&((*RootPtr) -> LPtr), K, Content); //chci vkladat doleva
+ } else if (K > (*RootPtr) -> Key) { //kdyz vetsi
+ BSTInsert(&((*RootPtr) -> RPtr), K, Content); //vlozit doprava
+ } 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,tBSTNodePtr *RootPtr) {
+/* Pomocná procedura pro vyhledání, přestěhování a uvolnění nejpravějšího
+** 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á, že pomocný ukazatel PtrReplaced
+** 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, &((*RootPtr) -> RPtr)); //bez doprava
+ } else { //no a kdyz tam nic neni
+ PtrReplaced -> BSTNodeCont = (*RootPtr) -> BSTNodeCont; //nahrad obsah
+ PtrReplaced -> Key = (*RootPtr) -> Key; //nahrad klic
+ ptr = *RootPtr; //zalohuj koren
+ *RootPtr = (*RootPtr) -> LPtr; //novy koren
+ free(ptr); //uvolni stary koren
+ }
+}
+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(&((*RootPtr)->LPtr), K).
+** Podobně je tomu tak i u ReplaceByRightMost().
+** Například: ReplaceByRightmost(*RootPtr, (&((*RootPtr)->LPtr)))
+*/
+  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(&((*RootPtr) -> LPtr), K); //bez doleva
+ } else {
+ if (K > (*RootPtr) -> Key) { //kdyz je klic vetsi
+ BSTDelete(&((*RootPtr) -> RPtr), K); //bez doprava
+ } else {
+ ptr = *RootPtr; //zalohuj koren
+ if (ptr -> RPtr == NULL) { //kdyz koren vpravo nic nema
+ (*RootPtr) = ptr -> LPtr; //koren bude levej
+ free(ptr); //uvolni starej koren
+ } else {
+ if (ptr -> LPtr == NULL) { //kdyz koren vlevo nic nema
+ (*RootPtr) = ptr -> RPtr; //koren bude prvej
+ free(ptr); //uvolni starej koren
+ } else {
+ ReplaceByRightmost(*RootPtr, (&((*RootPtr) -> LPtr))); //jinak kouzli
+ }
+ }
+ }
+ }
+ }
+}
+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(&(*RootPtr)->LPtr).
+*/
+ if (*RootPtr != NULL) { //kdyz je co sidposovat
+ BSTDispose(&(*RootPtr) -> RPtr); //disposuj doprava
+ BSTDispose(&(*RootPtr) -> LPtr); //dsposuj doleva
+ free(*RootPtr); //uvolni
+ *RootPtr = NULL; //a oznac za prazdny
+ }
+//solved = FALSE;
+}
+/* --------------------------- konec c401.c -------------------------------- */
+</file>
+<file c c402.c>
+/* --------------------------- c402.c --------------------------------------- */
+/* Téma: Nerekurzivní implementace operací nad BVS
+**                           Implementace: Petr Přikryl, prosinec 1994
+**                                 Úpravy: Petr Přikryl, listopad 1997
+**                                         Petr Přikryl, květen 1998
+**               Přepracované do jazyku c: Martin Tuček, srpen 2005
+**
+** 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):
+**
+**     BTInit .......... inicializace stromu
+**     BTInsert ........ nerekurzivní vložení nového uzlu do stromu
+**     BTPreorder ...... nerekurzivní průchod typu pre-order
+**     BTInorder ....... nerekurzivní průchod typu in-order
+**     BTPostorder ..... nerekurzivní průchod typu post-order
+**     BTDisposeTree ... zruš všechny uzly stromu
+**
+** 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, kde se tato procedura jmenovala Nejlev).
+**
+** 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, kde opětné objevování Ameriky nemá
+** místo. Pokud se vám zdá, že by něco šlo zapsat optimálněji, promyslete
+** 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 '*' použijete
+** 'P' pro zásobník s ukazateli nebo 'B' pro zásobník s boolovskými hodnotami.
+**
+** !Upozornění! Je třeba, abyste spravně rozlišovali, kdy použit dereferenční
+** 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 "c402.h"
+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("NULL\n");
+  else
+    printf("Vypis hodnoty daneho uzlu> %d\n", Ptr->Cont);
+}
+/* -------------------------------------------------------------------------- */
+/* 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->top==MAXSTACK)
+    printf("Přetečení zásobníku s ukazateli!\n");
+  else {
+    S->top++;
+    S->a[S->top] = ptr;
+  }
+}
+tBTNodePtr STopPopP (tStackP *S) {
+/* vrací odstraněnou hodnotu */
+  if (S->top == 0)  {
+    printf("Podtečení zásobníku s ukazateli!\n");
+    return(NULL);
+  }
+  else {
+    return (S->a[S->top--]);
+  }
+}
+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("Přetečení zásobníku pro boolean!\n");
+  else {
+    S->top++;
+    S->a[S->top] = val;
+  }
+}
+bool STopPopB (tStackB *S) {
+/* vrací odstraněnou hodnotu */
+  if (S->top == 0) {
+    printf("Podtečení zásobníku pro boolean!\n");
+    return(NULL);
+  }
+  else {
+    return(S->a[S->top--]);
+  }
+}
+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 'Content'. Z pohledu vkládání
+** 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;       /* příznak ukončení cyklu */
+/* 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; //jednoprvkovy strom nema listy
+ ptr -> RPtr = NULL; //jednprvkovy strom strom nema listy
+ *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, ptr); //pushni uzel na stack
+ BTWorkOut(ptr); //napis uzel
+ 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(&Stack);
+ Leftmost_Preorder(RootPtr, &Stack); //pis levy dokud to jde
+ while (!SEmptyP(&Stack)) { //dokud neprojdes uplne doprava
+ ptr = STopPopP(&Stack); //popni posledni uzel
+ Leftmost_Preorder(ptr -> RPtr, &Stack); //bez od nej doprava
+ }
+}
+/* ------------------------------ 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); //pushni uzel
+ 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;  /* zásobník ukazatelů */
+  tBTNodePtr ptr; /* pomocný ukazatel na uzel */
+ SInitP(&Stack);
+ Leftmost_Inorder(RootPtr, &Stack); //bez doleva co to jde
+ while (!SEmptyP(&Stack)) { //dokud je neco na stacku
+ ptr = STopPopP(&Stack); //vyvolej posledni uzel
+ BTWorkOut(ptr); //vypis uzel
+ Leftmost_Inorder(ptr -> RPtr, &Stack); //bez doprava
+ }
+}
+/* ------------------------------ 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, ptr); //pushni uzel
+ SPushB(StackB, ptr); //uz jsem tam byl
+ ptr = ptr -> LPtr; //bez doleva
+ }
+}
+void BTPostorder (tBTNodePtr RootPtr) {
+/* Nerekurzivní průchod typu post-order. Pro zpracování uzlu volejte
+** proceduru BTWorkOut.
+*/
+  tStackP StackP;  /* zásobník ukazatelů */
+  tBTNodePtr ptr;  /* pomocný ukazatel na uzel */
+  tStackB StackB;  /* zásobník boolovských hodnot */
+ SInitP(&StackP);
+ SInitB(&StackB);
+ Leftmost_Postorder(RootPtr, &StackP, &StackB); //bez doleva co to jde
+ while (!SEmptyP(&StackP)) { //dokud mame uzly k reseni
+ ptr = STopPopP(&StackP); //vyvolej uzel
+ SPushP(&StackP, ptr); //zase ho vrat
+ if (STopPopB(&StackB)) { //kdyz jsem v uzlu jeste nebyl
+ SPushB(&StackB, false); //tak uz jsem tam byl
+ Leftmost_Postorder(ptr -> RPtr, &StackP, &StackB); //a jdi doprava
+ } else { //kdyz uz jsem v uzlu byl
+ STopPopP(&StackP); //vyvolej uzel
+ BTWorkOut(ptr); //vypis
+ }
+ }
+}
+/* ------------------------------ 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é, v jakém pořadí se budou ruš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(&S);
+ do {
+ if (*RootPtr == NULL && !SEmptyP(&S)) { //kdyz uz je strom prazdny ale stack neni prazdny
+ *RootPtr = STopPopP(&S); //precti neco ze stacku
+ } else {
+ if ((*RootPtr) -> RPtr != NULL) { //kdyz vpravo neco je
+ SPushP(&S, (*RootPtr) -> RPtr); //narvi to na stack
+ }
+ ptr = *RootPtr; //zalohuj koren
+ *RootPtr = (*RootPtr) -> LPtr; //novy koren
+ free(ptr); //zrus stary koren
+ }
+ } while (!SEmptyP(&S) || *RootPtr != NULL); //vyse uvedene delj doku je neco na stacku nebo dokud neni prazdny koren
+ }
+}
+/* ----------------------------- konec c402.c ------------------------------- */
+</file>
+<file c c403.c>
+/* ------------------------------- c403.c ----------------------------------- */
+/* Téma: Vyhledávací tabulka v neseřazeném poli se zarážkou (optimalizace)
+**       První implementace: Petr Přikryl, prosinec 1994
+**       Úpravy: Petr Přikryl, listopad 1997, květen 1998
+**       Další úprava: Martin Tuček, srpen 2005 (jazyk C)
+**       Další úprava: Roman Lukáš, říjen 2006
+**
+** 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):
+**
+**   ASInit ..... inicializace tabulky
+**   ASSearch ... vyhledávání se zarážkou v neseřazeném poli
+**   ASInsert ... vkládání do neseřazeného pole s využitím ASSearch
+**
+** 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 'arr' a indexu
+** poslední využité položky pole 'last'. Položky pole jsou tvořeny záznamy
+** 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 "c403.h"
+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("Chyba: Polozka jiz nemuze byt vlozena\n");
+  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é 'ind' vrací první
+** 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 'last' NEMĚNÍ! Zarážka se tedy nachází
+** na pozici 'last' + 1. Zarážka může obsahovat obecně libovolnou hodnotu,
+** 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, Tab -> arr[index].Key) != 0) { // dokud jsme nenasli klic (nebo zarazku)
+ index++; //pousunujeme se v poli
+ }
+ 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]; //zalohujeme nalezeny prvek
+ 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, Key, &index); //zjistime jestli nahodou takovy klic uz neexistuje (a posuneme ho)
+ 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(); //zakric
+ } 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 --------------------------------- */
+</file>

Kalábovi

Uživatelské nástroje

Nástroje pro tento web

Rozdíly

Nástroje pro stránku