6. praktikum Kahendpuu Ülesanne 1 Morse - kasutades dünaamilist kahendpuud --------------------------------------------------- Programm loeb sisse morsekoodis teksti, teisendab ta tavaliseks tekstis ja trükib ekraanile. Teisendamiseks TULEB kasutada kahendpuud, kuhu on paigutatud kõik tähed vastavalt nende morsekoodile. Sisend võib olla selline, nagu failides morse1.txt ja morse2.txt näha on. Failid lingi alt "C näited". Näidete all programm morse_algus.c. Sellest tuleb alustada ülesande lahendamist. Puu ehitamise rekursiivset funktsiooni BuildTree() uurisime harjutustunnis. Näites olev funktsioon BuildTree() moodustab täieliku puu, arvutades selleks välja puu kõrguse. Massiivis LETTERS on tähed sellises järjekorras, et tulemuseks tuleb nö õige puu. Puu ehitamise funktsiooni loogikast ei ole hädasti vaja aru saada. Aga võiks :) Näites on ka üks puu kõigi tippude läbimise funktsioon Postorder(), mis tegelikult siia konteksti üldse ei kuulu. Küll aga võib tema käivitamine aimu anda, et tähed on kõik kenasti puusse saanud. Tehnilises plaanis oleks hea morsekood failist välja lugeda. Vaata tekstifaili lugemist: faili_lugemine.c Seal on näha käsud failiga suhtlemiseks ja samuti stringi töötlemiseks. Ülesanne 2 Morse uuesti - kasutades staatilist kahendpuud (massiivi) -------------------------------------------------------------------- Tee sama morsepuu ülesanne ringi (st tee ikka uus fail) nii, et kasutatakse massiivi. 1. Millises järjekorras tähed nüüd massiivi panna tuleb? (Massiivi kirjeldamise näide on morsepuu programmis olemas, kuid seal on tähtede paigutusel teine loogika). 2. Kuida liikuda puus ühest tipust teise? Abi leiad loengumaterjalist, kus on kirjeldatud kahendpuu esitamist massiivina. Rääkisime sellest ka loengus. Ülesanne 3 Loomade arvamine --------------------------- Ülesannet ja lahenduse aluseks olevat andmestikku (kahendpuud) uurisime viimases harjutustunnis. Puu ehitamine ei ole üldse oluliselt raskem ahela ehitamisest. Ära kasuta morse-ülesande BuidTree()-funktsiooni. See oleks varlase tulistamine kahurist. Vaata parem kirvemeetodil ahela ehitamise näidet. Selle alusel tee valmis kolm sõlme ja ühenda need puukujuliselt. 1. Alusta sellist, et teed valmis väikese nö lähtepuu, kus on üks küsimus ja kaks võimalikku vastust (NB! Sa ei ole seotud loomateemaga!!). 2. Tee tsükkel, mille ülesandeks on puu juurelemendist alustades läbida tee (tipud kuni leheni) ja esitada tippudes olevad tekstid kui küsimused. Tee läbimine puus on sarnane morse ülesandega. Mille alusel nüüd otsustatakse liikumine vasakusse või paremasse alampuusse? Mille järgi saad loomapuus aru, et küsimuste esitamine läbi sai ning aeg on looma pakkuda? 3. Peale tsükli lõppu esita lehes olev tekst loomana. Kui kasutaja vastab 'j' (loom on õige), siis rõõmusta. Vastasel juhul lase uus info sisestada, lisa kaks sõlme ning paiguta uued ja vanad tekstid õigetesse sõlmedesse. Joonista paberile ja mõtle järgi, mis kuhu satub. NB! Meenuta!! Stringe ei saa niisama võrrelda ja omistada - funktsioonid! Kasuta vastuse j/e jaoks char-tüüpi muutujat. Sisselugemiseks scanf() või getchar() Stringide sisselugemiseks (loom, loomaküsimus) ei sobi scanf(), sest ta lõpetab lugemise esimese tühemikuga (ingl whitespace). Sobib fgets(). Vaata näidet "stringide ja märkide lugemine".