Úloha 3 - množina s binárním stromem

Evropský sociální fond

Praha & EU: Investujeme do vaší budoucnosti

Tato úloha vznikla za přispění fondu OPPA.

Vytvořte za pomoci binárního vyhledávacího stromu třídu BSTSET (= Binary Search Tree SET), která bude reprezentovat datový typ množina.

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:

Implementace BTSET obsahuje:

• Přetížený operátor « pro vkládání hodnot.
• Přetížený operátor [] pro získání informace o tom, jak hluboko je v binárním vyhledávacím stromu prvek uložen. Pokud se hodnota ve stromu nenachází, vrací -1.
• Přetížený operátor () pro ziskání informace o tom, kolikrát je hodnota do množiny již vložena. Pokud se hodnota ve stromu nenachází, vrací -1.
• Přetížený operátor « tak, aby šel objekt BSTSET předat objektu cout. Mělo by to vypsat všechny uložené hodnoty od nejmenší k největší.

Více by měl napovědět soubor DU3.cpp.

K dispozici máte již hotový zdrojový kód DU3.cpp, který je součástí testování. DU3.cpp je k nalezení v adresáři testeru a nesmí být editován (protože odevzdáváte pouze soubor BSTSET.h, takže změny by se při ostrém testování neprojevily)! Dále pak vkládá zdrojový kód BSTSET.h, který by měl obsahovat vaši implementaci množiny BSTSET. DU3.cpp použije vaši třídu a naplní ji daty na základě příkazového souboru, který dostává přes argument. Před koncem chodu vytiskne všechny prvky množiny BSTSET (viz řádek 52 v DU3.cpp). Více v sekci testování.

V sekci download jsou k dispozici testovací software (tester) a referenční řešení v binární podobě pro základní platformy. Tester přeloží předložený kód s parametry: -pedantic -pedantic-errors -Wall -Werror. Tyto volby způsobí, že překladač hlídá všechny detaily a pokud se při překladu objeví warning, je automaticky považován za chybu a překlad skončí. Pokud se podaří kód úspěšně přeložit, je pak porovnáván výstup aplikace s výstupem referenčního řešení. Jakákoliv odchylka, třeba i jedna mezera navíc, způsobí neplatnost testu! Během testování máte k dispozici všechny vstupy i informaci, kde došlo k nesrovnalostem. Pro domácí testování je ke stažení k dispozici i sada testovacích vstupů. Zde je třeba upozornit na rozdílnost platforem. V aplikace se používají floating point čísla, takže přesnost se může na různých platformách lišit. Výstupní hodnotu z testované a referenční aplikace se doporučuje porovnávat pouze v rámci jedné platformy!

Tester po skončení běhu napíše procentuální úspěšnost. Doporučuje se testovat na Solarisu, ale stejně tak by měl tester fungovat v jakémkoliv linuxu s nainstalovaným pythonem verze 2.4.6 a vyšším. K úspěšnému chodu je zapotřebí i nainstalovaný překladač g++. Po odevzdání bude váš kód testován stejným testerem, takže každý by měl předem vědět, jaký počet bodů dosáhl.

Pro spuštění testu stačí stáhnout a rozbalit adresář s testerem DU3-tester.tar. Poté v rozbaleném adresáři zavolejte příkaz make (na solarisu gmake) a řiďte se pokyny. V následujícím odstavci je popis testování, kdyby příkaz make (gmake) z nejakého důvodu nefungoval.

Tester vyžaduje dva parametry z příkazové řádky. Prvním je cesta k referenční aplikaci. Druhým parametrem je přímo testovaný zdrojový kód, v tomto případě to bude vždy DU3.cpp. Jako referenční aplikaci použijte tu správnou pro danou platformu. Pro solaris je to například refApp.solaris, pro 32 bitové linuxy refApp.linux_32 atd. Testování lze spustit příkazem:

python DU3-tester.py refApp.XXX DU3.cpp

Místo XXX si samozřejmě doplňte příslušnou platformu.

Pro testování přímo ve Windowsech je nutné nainstalovat 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:

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:

cd DU3-tester

Pak zkopírujte zdrojový kód domácího úkolu do složky testeru (do toho v adresáří home) a pojmenujte jej DU3.cpp. Pak stačí spustit test příkazem

make test_win

Pro záruku, že Váš kód bude při odevzdání přijat, otestujte jej také na solarisu, viz další sekce.

Vzdálené testování na serveru z OS Windows lze pomocí kombinace programů putty a WinSCP. Přes WinSCP lze na Solaris zkopírovat data a přes putty získáte vzdálený terminálový přístup. Jako adresu zadávejte např. sunray1.felk.cvut.cz, nebo sunray3.felk.cvut.cz. Uživatelské jméno a heslo byste měli znát.

Nejsnažší je použít příkazovou řádku a kombinaci příkazů ssh a scp. ssh slouží pro vzdálený přístup a scp pro kopírování. Přesuňte se do adresáře, kde máte uložen adresář DU1-tester. Pak zadejte příkaz

scp -r DU2-tester username@sunray1.felk.cvut.cz:

a po vyzvání buď potvrďte dotaz nebo rovnou zadejte heslo. Tímto byste měli mít celý adresář DU1-tester ve vašem domovském adresáři na Solarisu. Pro vzdálený přístup pak zavolejte příkaz

ssh username@sunray1.felk.cvut.cz

a opět zadejte heslo. Pro ukončení vzdáleného přístupu zadejte příkaz exit.

* Na solarisu používejte primárně příkkaz gmake. Příkaz gmake vypíše instrukce pro testování. Pokud tento postup selže, neprodleně to sdělte na adresu cernyvi@fel.cvut.cz. Můžete testovat i ručně viz předchozí sekce, ale předtím pro jistotu nastavte referenční řešení jako spustitelné (místo XXX si doplňte příslušnou platformu):

chmod +x refApp.XXX

• Vývoj a testování domácího úkolu lze značně zjednodušit. Stačí si vytvořit zástupce nebo symbolický link na zdrojový kód, který může být umístěn například v projektovém adresáři vývojového prostředí. Tohoto zástupce nebo link umístěte do adresáře testeru a přejmenujte jej na DU2.cpp. Poté lze kód vyvíjet a testovat zároveň, aniž byste jej museli po každé změně kopírovat.

• Editován je pouze soubor BSTSET.h, který také potom odevzdáváte!
• Pro tento úkol jsou tři testy:
  • Test 1 - vstupní hodnoty odpovídají ukázkovému vstupu jako na ilustračním obrázku.
  • Test 2 - vstupní hodnoty jsou sadou náhodně generovaných čísel.
  • Test 3 - test je defaultně vypnutý a slouží ke kontrole práce s pamětí. Funguje pouze na linuxu nebo MacOSX s nainstalovaným valgrindem (viz sekce Download) a kontroluje memory leaky. Spouští se příkazem:

python DU3-tester.py refApp.XXX DU3.cpp -valgrind

• Pokud nemáte k dispozici linux můžete zkusit použít na kontrolu Vašeho kódu obdobný nástroj pro systém Windows - Dr. Memory (viz sekce Download), ale je to bez záruky.

Tester: du3-tester.zip

Domovská stránka valgrindu: http://valgrind.org/

Domovská stránka Dr. Memory: http://code.google.com/p/drmemory/

• Pro implementaci stromu je vhodné využít dědičnost.