Tak tentokrat(a letos naposled) bylo zadani dost husty...aspon podle statistik, ktery mam od kamose(ja tam nebyl az do konce) z 19 lidi to dali dva(jeden po 3hodinach, ktery na to byly puvodne dany a jeden asi o hodinu dyl) a to i pres to, ze nekteri to zkouseli i cca 10 hodin, ano slovy deset hodin!:evil: No posudte sami, tady je zadani:

• Program pro formatovani binarnich stromu slov

Program se bude spoustet z prikazove radky nasledujicim zpusobem:

tree x.tree

a vypise strom na standardni vystup. Vstupni soubor x.tree ma nasledujici
format:

1. radek obsahuje jmeno souboru se seznamem slov (napr. x.abc), ktery se
   nachazi ve stejnem adresari jako x.tree a pro jednoduchost berte ze je vse v
   current working directory.

2. radek obsahuje pocet slov ve slovniku x.abc (znacim by A), za nimz
   (mezerou oddeleny) nasleduje pocet vnitrnich vrcholu (vcetne korene)
   binarniho stromu. Znacim C.

Vyznam je takovy ze slova ve slovniku se cisluji od 1 do A (vcetne) a za
nimi nasleduji cisla vnitrnich vrcholu stromu (od A+1 do A+C vcetne).

Dale nasleduje presne C radku, na kazdem z nich jsou 2 cisla oddelena
mezerou, prvni je index leveho podstromu, druhy index praveho podstromu.
Takze kdyz tato cisla budou >A tak to znamena ze strom dale pokracuje
vnitrnim uzlem, kdyz budou <=A tak jsme v listu a podle souboru s abecedou
muzeme urcit ktery ASCII retezec reprezentuje danne slovo.

Koren slovu je na poslednim radku souboru *.tree a navic je tento soubor
usporadany v tom smyslu, ze pri pruchodu libovolnou vetvi od korene k listu
postupujeme v souboru vzdy jen nahoru.

Soubor *.abc obsahuje slovnik. Obsahuje A radku a na kazdem z nich je slovo.
Slovo na prvnim radku ma index 1, slovo na poslednim ma index A v cislovani
ve kterem se na slovnik odkazuje soubor *.tree. Pritom ve slove se muzou
vyskytnout libovolne znaky, krome '
'.

Nyni co ten program ma delat:

Precte soubor *.tree a prislusny *.abc (kdyz nenalezne tak nejak
civilizovane zkonci). A potom vytiskne na standardni vystup ASCII-art
reprezentaci toho stromu. Nejprve to ukazu na priklade. Dejme tomu ze x.abc
obsahuje

slovo
veliceprevelicedlouhereklbychazpredlouheslovo
nejakedalsislovo
nepouziteslovo

a x.tree obsahuje

x.abc
4 2
2 1
5 3

Tak vysledek bude:

veliceprevelicedlouhereklbychazpredlouheslovo ++
slovo ----------------------------------------/|
nejakedalsislovo ------------------------------/

Bystrejsi z vas jiz pochytili ze jde o to vypsat leve vrcholy stromu vys a
prave niz a pospojovat je pri tom pomoci znaku - | / +
Pritom vetveni stromu se deje znakem + a objevuje se vzdy na leve (tedy
horni vetvi), takze se pise napr:

c ++ nebo pro jiny strom toto: c -+
a /| (1) a +/ (2)
b -/ b /

Tim padem mame vlastnost ze kdyz vyberu ze stromu nejaky uplny podstrom
ktery zacina na radku x a konci na radku y tak jeho koren bude vzdy na radku
x.

Dalsi vlastnost kterou nakresleni musi mit je, ze neplytva znaky -', coz znamena ze kdyz spojuju 2 jinak siroke podstromy tak doplnim jen nezbytny pocet znaku -' k uzsimu z nich (plati to i pro jednotliva slova). Krom toho
znak '/' se smi pouzivat jen kdyz se vetev zalamuje k nejakemu slovu. Neni
tedy dovoleno delat krive vetve ve stylu:

u -+--+
c ++ |
a /| / (3)
b -/ |
x ---/

Kontrola spravnosti bude probihat binarnim porovnanim souboru se vzorovymi
resenimi. To znamena ze zalezi i na mezerach a newlinech. Proto zduraznuji
ze za slovem nasleduje presne 1 mezera, pak je ten strom, ktery musi byt
zaplnen na celou sirku mezerami (viz priklad (2) kde nejnizsi list musi mit
mezeru na konci posledniho radku aby znaky zabiraly sloupec konstantni
sirky) a pak konci znakem '
' (M$-DOSovy '\r' tam tedy neni).

Napoveda:

Da se to elegantne vyresit rekurzivnim pruchodem toho stromu, jen je potreba
ho delat 2* pri prvnim si spocitam jak budou ty veci velike abych pri druhem
vedel kolik mam kam psat minusu.

a tady sou vzorovy soubory:
http://peklo.unas.cz/shakespeare.abc
http://peklo.unas.cz/shakespeare_small.out
http://peklo.unas.cz/shakespeare_small.tree

Zdar.
Ja byl taky na tom zapoctu...byl jsem ten druhy, ktery to odevzdal, a dostal to. Muzu rict, ze se mi ta uloha nejdrive zdala jednoducha, ale kdyz rekl, ze ten strom jak presne musi byt pospojovany, tak jsem se trochu lekl.

Nicmene se musi rict, ze byl ochotny pomoci kazdemu, komu neco neslo (nevedel jak nato, neco se mu zacyklilo, nejaky pointer se ztratil, atd.)
A jak kolega rikal, o case to nebylo...myslim, ze 10 hodim by mohlo stacit.

Ta uspesnost byla asi proto takova, ze slo o treti kolo, a sli tam ty mene nadany...
Asi po hodine se napriklad zaclo resit, ze nekdko neumel kopirovat string (tj. nepouzil strcpy/strdup, ale hodil string1=string2, a divil se, ze se mu to prepisovalo najednou..)
Taky byly problemy u nekoho s rekurzi, ze jak ji napsat.

Jo, a jinak toto nebyl posledni termin. Bude jeste jeden tusim 26. 09.

Tady je moje reseni...jak jsem upraoval ten vypis, tak se to tak trochu sprasilo....

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

struct uzel
{struct uzel *left;struct uzel *right;char *slovo;
};

char konecek[128];
int delka_konecku = 0;

void vypis(struct uzel *koren, int konec,int dalsi)
{char *konecek2;int a,b,c,d;int nestaci = 1;if (koren->slovo==NULL){a=pocti(koren)-1;konecek[a]='|';vypis(koren->left,2,dalsi);konecek[dalsi]=' ';konecek[a]='/';vypis(koren->right,1,a);konecek[a]=' ';}else{printf("%s ",koren->slovo);konecek2=strdup(konecek);d=0;while (nestaci){nestaci=0;while (konecek2[d]!='/' && konecek2[d]!='|'){if (konecek2[d]==' ')konecek2[d]='-';d++;}if (konecek2[d]=='|'){konecek2[d]='+';nestaci=1;}}konecek2[delka_konecku]='\0';printf("%s
",konecek2+strlen(koren->slovo)+1);free(konecek2);}
};
int pocti(struct uzel *aktuzel)
{int vysledek = 0;int vysledek2 = 0;if (aktuzel->slovo==NULL){vysledek=pocti(aktuzel->left)+1;vysledek2=pocti(aktuzel->right)+1;if (vysledek2>vysledek)vysledek=vysledek2;}elsevysledek=strlen(aktuzel->slovo)+1;return(vysledek);
}

main(int argc, char **argv)
{FILE *strom;FILE *slova;char soubor_slov[128];int pocet_slov = 0;int pocet_uzlu = 0;int i,a,b;struct uzel *koren = NULL;struct uzel *aktual = NULL;struct uzel **uzly = NULL;char buffer[256];

if (argc==1){printf("malo arg.
");return(1);}if (!(strom = fopen (argv[1],"rb"))){printf("<<%s>> Soubor neex.
",argv[1]);return(1);}fscanf(strom,"%s",&soubor_slov);if (!(slova=fopen(soubor_slov,"rb"))){printf("<<%s>> Soubor neex.
",soubor_slov);return(1);}fscanf(strom,"%d %d
",&pocet_slov,&pocet_uzlu);
uzly=(struct uzel **)malloc(sizeof(struct uzel *)*(pocet_slov+pocet_uzlu));for(i=0;i<pocet_slov;i++){aktual=uzly[i];aktual=(struct uzel *)malloc(sizeof(struct uzel));(aktual->slovo)=(char *)malloc(sizeof(char)*256);fscanf(slova,"%s",&buffer[0]);strcpy((aktual->slovo),&buffer[0]);aktual->left=NULL;aktual->right=NULL;uzly[i]=aktual;}fclose(slova);
for(i=0;i<pocet_uzlu;i++){fscanf(strom,"%d %d
",&a,&b);uzly[pocet_slov+i]=(struct uzel *)malloc(sizeof(struct uzel));uzly[pocet_slov+i]->left=uzly[a-1];uzly[pocet_slov+i]->right=uzly[b-1];uzly[pocet_slov+i]->slovo=NULL;}koren=uzly[pocet_slov+i-1];
//-----vypis-----//for (i=0;i<127;i++)konecek[i]=' ';konecek[127]='\0';delka_konecku=pocti(koren);konecek[delka_konecku]='/';konecek[delka_konecku+1]='\0';vypis(koren,2,pocti(koren));printf("
");
}

Když jsem psal zápočet z Céčka,
bylo mi úplně jasné,
že moje šance uspět,
s každou hodinou hasne.

Vstup se načíst dal,
nebyla to věda.
Co však dělat dál?
běda ! Běda !! BĚDA !!!
Nechtěl jsem to vzdát,
tak jsem začal psát.

Přestával jsem tápat,
začínal jsem chápat.
Už vím, oč tu kráčí !
Teď to napsat stačí.
Přidám jednu funkci,
rekurze to jistí,
že se tisknout bude,
to stromové listí.

Teď už jenom hlavní věc:
Co tam tisknout nakonec?
plus, mínus a lomítko,
mezera a svislítko.

Není to tak snadné,
jak jsem myslel zprva.
Tenhleten můj kód,
pěkná chlévská mrva.

Když to odladím,
bude hotovo.
Snad si poradím ...
S chutí do toho !
Nechtěl jsem čas ztratit
rychle začal ladit.

Ten, kdo ztratil naději,
dávno vzdal to raději.
Cvičící to nevzdával,
další čas nám nechával.
Nechtěl jsem to vzdát,
tak jsem musel psát.

Po osmi hodinách psaní,
končí programování.
Mozek už nic nestvoří,
Fakta takto hovoří.

Tak jsem to vzdal,
nechal to být.
Aby měl cvičící
konečně klid.
Času nám poskytl
víc než měl v úmyslu
abychom stvořili
hromadu nesmyslů.

Odcházím poučen
ze svého nezdaru:
Snažší než program
je naladit kytaru.

:D , tak niekoho to cecko riadne poznacilo, 8 hodin :shock: to by som vzdal asi uz 4 krat

Moje reseni neni zdaleka tak elegantni, jako uvadi kolega vyse, ale
kdyz uz se mi to konecne povedlo napsat proc ho sem nedat?
Tiskne to vsechno na jeden pruchod.(v jednom miste by se dalo optimalizovat... no posudte sami)

Attachments:

• Shakespeare.rar