Juraj na 20:30, 16. august 2010

2010-08-16T20:30:22Z

Juraj: Vytvorená stránka „Kategória:Študijné materiály Kategória:Programovanie Kategória:jazyk C {{Draft}} {{Skripta programovanie (zbierka úloh)}} ==Zadaniehttp://cec.truni…“

2010-03-28T18:27:06Z

Vytvorená stránka „Kategória:Študijné materiály Kategória:Programovanie Kategória:jazyk C {{Draft}} {{Skripta programovanie (zbierka úloh)}} ==Zadanie<ref>http://cec.truni…“

Nová stránka

[[Kategória:Študijné materiály]]
[[Kategória:Programovanie]]
[[Kategória:jazyk C]]
{{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

← Staršia verzia		Verzia zo dňa a času 20:30, 16. august 2010
Riadok 1:		Riadok 1:
−	~~[[Kategória:Študijné materiály]]~~
−	~~[[Kategória:Programovanie]]~~
−	~~[[Kategória:jazyk C]]~~
	{{Draft}}		{{Draft}}
	{{Skripta programovanie (zbierka úloh)}}		{{Skripta programovanie (zbierka úloh)}}

Binárny strom - Morseova abeceda (riešené príklady) - História úprav

Juraj na 20:30, 16. august 2010

Juraj: Vytvorená stránka „Kategória:Študijné materiály Kategória:Programovanie Kategória:jazyk C {{Draft}} {{Skripta programovanie (zbierka úloh)}} ==Zadaniehttp://cec.truni…“