Both sides previous revision Previous revision Next revision | Previous revision |
pjc:03:start [2013/02/23 13:31] – [Download] vikturek | pjc:03:start [2013/02/26 14:55] (current) – [Úloha 3 - množina s binárním stromem] vikturek |
---|
====== Domácí úkol 3 - množina s binárním stromem ====== | ====== Úloha 3 - množina s binárním stromem ====== |
| |
{{:homeworks:2011zs:3_loga_velikost_100.jpg|}} | {{:pjc:3_loga_velikost_100.jpg|}} |
| |
| **Evropský sociální fond** |
| |
| **Praha & EU: Investujeme do vaší budoucnosti** |
| |
Tato úloha vznikla za přispění fondu [[http://www.prahafondy.eu/cz/oppa.html|OPPA]]. | Tato úloha vznikla za přispění fondu [[http://www.prahafondy.eu/cz/oppa.html|OPPA]]. |
Množina je datová struktura, do které lze ukládat datové prvky. Do standardní množiny lze uložit stejný prvek jen jednou. U naší množiny BSTSET to platí také, ale navíc si dokáže u každé vložené hodnoty zapamatovat, kolikrát byla vložena. Každá množina se vnitřně implementuje tak, že jsou prvky seřazeny a tím je usnadněno vyhledávání a tím tedy i rozhodování, zda se v množině hodnota již nachází nebo ne. V naší množině je řazení realizováno pomocí binárního vyhledavácího stromu (BST). BST má dva typy uzlů - vnitřní a okrajové. Okrajové uzly obsahují uloženou hodnotu a počet, kolikrát byla vložena. Vnitřní obsahují odkazy na levý a pravý podstrom, přičemž platí, že všechny hodnoty v levém podstromu jsou menší než všechny hodnoty v pravém podstromu. Primárně se vkládá do levého podstromu. Činnost BST pro vložení prvků 5, 8, 3, 6, 9 naznačuje následující obrázek: | Množina je datová struktura, do které lze ukládat datové prvky. Do standardní množiny lze uložit stejný prvek jen jednou. U naší množiny BSTSET to platí také, ale navíc si dokáže u každé vložené hodnoty zapamatovat, kolikrát byla vložena. Každá množina se vnitřně implementuje tak, že jsou prvky seřazeny a tím je usnadněno vyhledávání a tím tedy i rozhodování, zda se v množině hodnota již nachází nebo ne. V naší množině je řazení realizováno pomocí binárního vyhledavácího stromu (BST). BST má dva typy uzlů - vnitřní a okrajové. Okrajové uzly obsahují uloženou hodnotu a počet, kolikrát byla vložena. Vnitřní obsahují odkazy na levý a pravý podstrom, přičemž platí, že všechny hodnoty v levém podstromu jsou menší než všechny hodnoty v pravém podstromu. Primárně se vkládá do levého podstromu. Činnost BST pro vložení prvků 5, 8, 3, 6, 9 naznačuje následující obrázek: |
| |
| {{:pjc:03:bstset.jpg|}} |
{{:homeworks:2011zs:bstset.jpg|}} | |
| |
Implementace BTSET obsahuje: | Implementace BTSET obsahuje: |
Pro testování přímo ve Windowsech je nutné nainstalovat [[http://cygwin.com/setup.exe|cygwin]] se správnými součástmi. Po spuštění instalátoru vyberte nějaký mirror a nastavte dle instrukcí potřebné adresáře. (Pokud to lze, ponechte defaultní hodnoty.) Postupne byste se měli dostat na okno s výběrem instalačních součástí. Do vyhledávání zadejte postupně hesla g++, make, python. Pro instalaci vyberte balíčky tak, jak to je vídět na následujících obrázcích: | Pro testování přímo ve Windowsech je nutné nainstalovat [[http://cygwin.com/setup.exe|cygwin]] se správnými součástmi. Po spuštění instalátoru vyberte nějaký mirror a nastavte dle instrukcí potřebné adresáře. (Pokud to lze, ponechte defaultní hodnoty.) Postupne byste se měli dostat na okno s výběrem instalačních součástí. Do vyhledávání zadejte postupně hesla g++, make, python. Pro instalaci vyberte balíčky tak, jak to je vídět na následujících obrázcích: |
| |
{{:homeworks:2011zs:g_1.jpg|}} | {{:pjc:g_1.jpg|}} |
| |
{{:homeworks:2011zs:make1.jpg|}} | {{:pjc:make1.jpg|}} |
| |
{{:homeworks:2011zs:python1.jpg|}} | {{:pjc:python1.jpg|}} |
| |
Po instalaci zkopírujte rozbalený //DU2-tester// do složky //home/Vase_systemove_uzivatelske_jmeno//, která se nachází v adresáři s nainstalovaným cygwinem. Poté spusťte cygwin a napište příkaz: | Po instalaci zkopírujte rozbalený //DU2-tester// do složky //home/Vase_systemove_uzivatelske_jmeno//, která se nachází v adresáři s nainstalovaným cygwinem. Poté spusťte cygwin a napište příkaz: |