Zobrazenie zdroja stránky Binárny strom - Morseova abeceda (riešené príklady)

{{Draft}}
{{Skripta programovanie (zbierka úloh)}}

==Zadanie<ref>http://cec.truni.sk/stoffov/dynamicke-udajove-struktury/Cast2/</ref>==
Vytvorte program na dekódovanie správy napísanej v Morseovej abecede. Správu prečítajte z textového súboru.
==Analýza úlohy==
Pri dekódovaní využijeme binárny vyhľadávací strom. V jeho vrcholoch budú uložené jednotlivé písmená abecedy, v koreni je ako špeciálny znak medzera. Pre potreby tohto príkladu si upravíme dátovú štruktúru binárny strom nasledovne
*dátová časť bude jeden znak (znak kódovanej abecedy)
*smerníky ''lavy'' a ''pravy'' nahradíme smerníkmi ''bodka'' a ''ciarka''. Smerníky majú i naďalej význam ľavého a pravého potomka, ale pre ľahšiu orientáciu v kódovacom strome si ich premenujeme.

<source lang="c">
struct TUzol{
       char  znak;
       TUzol *bodka, *ciarka;
};
</source>
Zo súboru čítame postupnosti bodiek a čiarok. Znak bodka znamená presun ukazovateľa na ľavý podstrom, znak čiarka na pravý podstrom.
[[Súbor:morse_bin_strom.gif|framed|center|Bnárny strom reprezentujúci kódovanie morseovej abecedy]]
===Dekódovanie Morseovej abecedy===
Ak prečítame zo súboru kód '''--..''' pôjdeme z koreňa vpravo, vpravo, vľavo, vľavo. Skončíme vo vrchole s písmenom '''z'''. Takýmto spôsobom pre každý prečítaný kód nájdeme rýchlo zodpovedajúce písmeno. Princíp dekódovanie je v nasledujúcom pseudokóde:
<source lang="pascal">
procedure dekoduj(TUzol strom)
begin
   p - pomocný prvok TUzol
   c - premenná typu znak
   p = strom // p je pomocná premenná s ktorou prechádzame strom
   pokiaľ sa zo súboru načítal znak (do premennej c)
   begin
      ak je c znak '.'
        tak  p=p->bodka // presunieme sa na ľavý podstrom
      inak
         ak je c znak '-'
           tak  p=p->ciarka // presunieme sa na pravý podstrom
         inak // načátali sme oddeľovací znak
         begin
            vypíš hodnotu uzla p
            p=strom //v ďalšom cykle budeme dekódovať ďalší znaka  musíme začať od koreňa stromu
         end
   end
end
</source>
Pred čítaním kódu ďalšieho písmena nastavíme ukazovateľ opäť na koreň stromu!

Pre jednoduchosť budeme predpokladať, že na vstupe je správa v dohodnutom formáte - za kódom písmena ako oddeľovač nasleduje vždy znak /, za každým slovom aspoň dva znaky //.

Vytvorený program má tri časti - vytvorenie dekódovacieho stromu, otvorenie súboru pre čítanie a postupné dekódovanie správy.
==Vzorový príklad==
===Vzorový vstup===
 -../-.--/-./.-/--/../-.-./-.-/.//.../-/.-./..-/-.-/-/..-/.-./-.--/
===Vzorový výstup===
 dynamicke struktury
==Riešenie v jazyku C==
<source lang="c" line>
#include <stdlib.h>
#include <iostream.h>
#include <fstream.h>

struct TUzol{
       char  znak;
       TUzol *bodka, *ciarka;
};
//------------------------------------------------------------------------------
TUzol *vytvor(char z, TUzol *b, TUzol *c)
{
  TUzol *novy = new TUzol;
  
  novy->znak = z;
  novy->bodka  = b;
  novy->ciarka = c;
  return(novy);
}
//------------------------------------------------------------------------------
void dekoduj(TUzol *strom)
{
   ifstream fr;
   fr.open("sprava.txt");
      
   TUzol *p;
   char c;
   p = strom;

   while (fr>>c ) 
   {
     if (c == '.') 
        p = p->bodka;
     else 
        if (c == '-') 
           p = p->ciarka;
        else 
        {
          cout<<p->znak;
          p = strom;
        }
  }
  fr.close();
}
//------------------------------------------------------------------------------
void vypis(TUzol *v) 
{
   if (v != NULL) {
     vypis(v->bodka);
     cout<<v->znak;
     vypis(v->ciarka);
   }
}
//------------------------------------------------------------------------------
int main()
{
  TUzol *strom = NULL;
  
  /* vytvorenie dekódovacieho stromu */
  strom = vytvor(' ',
           vytvor('e',
             vytvor('i',
               vytvor('s', vytvor('h', NULL, NULL), vytvor('v', NULL, NULL)),
               vytvor('u', vytvor('f', NULL, NULL), NULL)),
             vytvor('a',
               vytvor('r', vytvor('l', NULL, NULL), NULL),
               vytvor('w', vytvor('p', NULL, NULL), vytvor('j', NULL, NULL)))),
           vytvor('t',
             vytvor('n',
               vytvor('d', vytvor('b', NULL, NULL), vytvor('x', NULL, NULL)),
               vytvor('k', vytvor('c', NULL, NULL), vytvor('y', NULL, NULL))),
             vytvor('m',
                vytvor('g', vytvor('z', NULL, NULL), vytvor('q', NULL, NULL)),
                vytvor('o', NULL, NULL))));



 cout<<"Sprava: ";
 dekoduj(strom);
 return 0;
}
</source>
===Vysvetlenie zdrojového kódu===
====Hlavný program main====
Ako prvé je potrebné vytvoriť binárny strom (riadok 56). Ďalší krok je vytvoriť kódovací strom Morseovej abecedy ako je na obrázku. Na to použijeme funkciu vytvor. Zaujímavý je spôsob jej použitia. Funkcia vytvor má 3 parametre: znak, ktorý predstavuje dekódovanú postupnosť bodiek a čiarok. Ďalej sú to dva smerníky na potomkov aktuálneho uzla. Ľavý potomok (bodka) a pravý potomok (ciarka).

Na riadku 59 je prvý krát použitá funkcia ''vytvor''. Pri tomto volaní vytvárame koreň stromu. Znak obsiahnutý v koreni je medzera. (' '). Druhým parametrom funkcie má byť uzol ktorý je ľavý potomok. Namiesto vytvorenia nového uzla a jeho následného vloženia do stromu ''strom'', opäť použijeme funkciu vytvor, pomocou ktorej vytvárame znak 'e'. Druhý parameter funkcie (pravý potomok uzla - ciarka) je znak 't' - riadok 67.
V nasledujúcom kóde je uvedený ekvivalentný zápis pri vytváraní stromu. V tomto príklade nebude použité vnáranie funkcie ''vytvor''.
<source lang="c" line>
 TUzol *strom = NULL;

 TUzol *h = vytvor('h',NULL,NULL);
 TUzol *v = vytvor('v',NULL,NULL);
 TUzol *f = vytvor('f',NULL,NULL);
 TUzol *s = s=vytvor('s',h,v);
 TUzol *u = u=vytvor('u',f,NULL);
 TUzol *i = vytvor('i',s,u); 
 
 TUzol *l = vytvor('j',NULL,NULL);
 TUzol *p = vytvor('p',NULL,NULL);
 TUzol *j = vytvor('j',NULL,NULL); 
 TUzol *r = vytvor('r',l,NULL);
 TUzol *w = vytvor('w',p,j);
 TUzol *a = a=vytvor('a',r,w);
 TUzol *e = a=vytvor('e',i,a);
 
 TUzol *b = vytvor('b',NULL,NULL);
 TUzol *x = vytvor('x',NULL,NULL);
 TUzol *c = vytvor('c',NULL,NULL);
 TUzol *y = s=vytvor('y',NULL,NULL);
 TUzol *z = s=vytvor('z',NULL,NULL);
 TUzol *q = s=vytvor('q',NULL,NULL);
 
 TUzol *d = u=vytvor('d',b,x);
 TUzol *k = vytvor('k',c,y);   
 TUzol *g = vytvor('g',z,q);   
 TUzol *o = s=vytvor('o',NULL,NULL);

 TUzol *m = u=vytvor('m',g,o);
 TUzol *n = vytvor('n',d,k);   
 TUzol *t = vytvor('t',n,m); 
 
 strom=  vytvor(' ',e,t);
</source>
====Funkcia vytvor====
'''Opis funkcie'''
Funkcia vytvorí a vráti nový uzol binárneho stromu. Hodnota časti ''znak'' nového uzla bude použitá z 1. parametra funkcie. 

'''Parametre funkcie'''
*z - znak, ktorý bude obsahovať nový uzol. Tento znak je zakódované písmeno v kódovacom strome Morseovej abecedy.
*b - smerník na ľavého potomka nového uzla. Určuje ďalší kódový znak v kódovacom strome. Ďalší znak pokračuje kódom '.' (bodka)
*c - smerník na pravého potomka nového uzla. Určuje ďalší kódový znak v kódovacom strome. Ďalší znak pokračuje kódom '-' (čiarka)

Poznámka: ak má nový uzol potomkov (podľa kódovacieho stromu napríklad znak 'e' má potomkov 'i' a 'a'). Tieto uzly už musia byť vytvorené. Smerníky na tieto existujúce uzly sú v parametroch funkcie ''vytvor''.

'''Návratová hodnota'''

Funkcia vráti smerník na novo vytvorený uzol kódovacieho stromu Morseovej abecedy.
====Funkcia dekoduj====
Na začiatku funkcie je otvorený súbor so vstupnými údajmi. Potom nasleduje samotné dekódovanie. Princíp dekódovania bol vysvetlený v časti [[#Dekódovanie Morseovej abecedy|Dekódovanie Morseovej abecedy]]
==Odkazy==
<references/>
* http://en.wikipedia.org/wiki/Morse_code