# zap 21.9. <{ForumPost(poster="Andreas", timestamp=2006-09-22 13:02:25)}> 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.abc) [http://peklo.unas.cz/shakespeare_small.out](http://peklo.unas.cz/shakespeare_small.out) [http://peklo.unas.cz/shakespeare_small.tree](http://peklo.unas.cz/shakespeare_small.tree) <{/ForumPost}> <{ForumPost(poster="zehyo", timestamp=2006-09-22 20:22:40)}> 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 #include #include 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;islovo)=(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;ileft=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(" "); } <{/ForumPost}> <{ForumPost(poster="Fairfax", timestamp=2006-09-23 10:20:52)}> 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. <{/ForumPost}> <{ForumPost(poster="lavor", timestamp=2006-09-23 10:44:58)}> :D , tak niekoho to cecko riadne poznacilo, 8 hodin :shock: to by som vzdal asi uz 4 krat <{/ForumPost}> <{ForumPost(poster="Fairfax", timestamp=2006-09-23 12:10:31)}> 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](/Forum%20archiv/Attachments/shakespeare.rar)* <{/ForumPost}>