Binárny strom - Morseova abeceda (riešené príklady)
Obsah
Zadanie[1]
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.
struct TUzol{
char znak;
TUzol *bodka, *ciarka;
};
Zo súboru čítame postupnosti bodiek a čiarok. Znak bodka znamená presun ukazovateľa na ľavý podstrom, znak čiarka na pravý podstrom.
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:
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
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
1 #include <stdlib.h>
2 #include <iostream.h>
3 #include <fstream.h>
4
5 struct TUzol{
6 char znak;
7 TUzol *bodka, *ciarka;
8 };
9 //------------------------------------------------------------------------------
10 TUzol *vytvor(char z, TUzol *b, TUzol *c)
11 {
12 TUzol *novy = new TUzol;
13
14 novy->znak = z;
15 novy->bodka = b;
16 novy->ciarka = c;
17 return(novy);
18 }
19 //------------------------------------------------------------------------------
20 void dekoduj(TUzol *strom)
21 {
22 ifstream fr;
23 fr.open("sprava.txt");
24
25 TUzol *p;
26 char c;
27 p = strom;
28
29 while (fr>>c )
30 {
31 if (c == '.')
32 p = p->bodka;
33 else
34 if (c == '-')
35 p = p->ciarka;
36 else
37 {
38 cout<<p->znak;
39 p = strom;
40 }
41 }
42 fr.close();
43 }
44 //------------------------------------------------------------------------------
45 void vypis(TUzol *v)
46 {
47 if (v != NULL) {
48 vypis(v->bodka);
49 cout<<v->znak;
50 vypis(v->ciarka);
51 }
52 }
53 //------------------------------------------------------------------------------
54 int main()
55 {
56 TUzol *strom = NULL;
57
58 /* vytvorenie dekódovacieho stromu */
59 strom = vytvor(' ',
60 vytvor('e',
61 vytvor('i',
62 vytvor('s', vytvor('h', NULL, NULL), vytvor('v', NULL, NULL)),
63 vytvor('u', vytvor('f', NULL, NULL), NULL)),
64 vytvor('a',
65 vytvor('r', vytvor('l', NULL, NULL), NULL),
66 vytvor('w', vytvor('p', NULL, NULL), vytvor('j', NULL, NULL)))),
67 vytvor('t',
68 vytvor('n',
69 vytvor('d', vytvor('b', NULL, NULL), vytvor('x', NULL, NULL)),
70 vytvor('k', vytvor('c', NULL, NULL), vytvor('y', NULL, NULL))),
71 vytvor('m',
72 vytvor('g', vytvor('z', NULL, NULL), vytvor('q', NULL, NULL)),
73 vytvor('o', NULL, NULL))));
74
75
76
77 cout<<"Sprava: ";
78 dekoduj(strom);
79 return 0;
80 }
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.
1 TUzol *strom = NULL;
2
3 TUzol *h = vytvor('h',NULL,NULL);
4 TUzol *v = vytvor('v',NULL,NULL);
5 TUzol *f = vytvor('f',NULL,NULL);
6 TUzol *s = s=vytvor('s',h,v);
7 TUzol *u = u=vytvor('u',f,NULL);
8 TUzol *i = vytvor('i',s,u);
9
10 TUzol *l = vytvor('j',NULL,NULL);
11 TUzol *p = vytvor('p',NULL,NULL);
12 TUzol *j = vytvor('j',NULL,NULL);
13 TUzol *r = vytvor('r',l,NULL);
14 TUzol *w = vytvor('w',p,j);
15 TUzol *a = a=vytvor('a',r,w);
16 TUzol *e = a=vytvor('e',i,a);
17
18 TUzol *b = vytvor('b',NULL,NULL);
19 TUzol *x = vytvor('x',NULL,NULL);
20 TUzol *c = vytvor('c',NULL,NULL);
21 TUzol *y = s=vytvor('y',NULL,NULL);
22 TUzol *z = s=vytvor('z',NULL,NULL);
23 TUzol *q = s=vytvor('q',NULL,NULL);
24
25 TUzol *d = u=vytvor('d',b,x);
26 TUzol *k = vytvor('k',c,y);
27 TUzol *g = vytvor('g',z,q);
28 TUzol *o = s=vytvor('o',NULL,NULL);
29
30 TUzol *m = u=vytvor('m',g,o);
31 TUzol *n = vytvor('n',d,k);
32 TUzol *t = vytvor('t',n,m);
33
34 strom= vytvor(' ',e,t);
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
