*** Algoritmus kezdete *** Foprogram kezdete fileinic; file2lancfa(fbe,lcf); lancfa2statfa(lcf,stf); statfakiir(fki,stf); Foprogram vége. konst nmax=100; {egy tombnek max. ennyi eleme lehet} tipus Tindex=egész; Tertek=karakter; Tstatfa= tömb [1..nmax] of Tertek; Tmutrec=tömb[1..nmax] of TIndex; Trec=rekord(ertek:tertek; m:tmutrec); Ttomb=tömb [1..nmax] of trec; Tvalaki=szöveg[2]; Tlancfa=^tlancfaRec; TlancfaRec=rekord (os:tlancfa; ertek:tertek; balmut:tlancfa; jobbmut:tlancfa); változó fbe,fki:text; stf:Tstatfa; lcf:Tlancfa; hiba:logikai; {tlancfa} Eljárás fileinic; változó bf,kf:logikai; fc:karakter; fn:szöveg; hol:szöveg; i:egész; Sorkihagy(5); Kiir('File-bol olvassak? '); Beolvas(fc); Ha (nagybetu(fc)='N') akkor bf:=hamis különben bf:=igaz; Kiir('File-ba irjak? '); Beolvas(fc); Ha (nagybetu(fc)='N') akkor kf:=hamis különben kf:=igaz; Ha bf=igaz akkor kezdet i:=1; Ciklus... Ciklus... Kiir('Melyik file-bol (letezo, 8 kar. hosszu nevu)? '); Beolvas(fn); növel(i); c. amig nem ((length(fn)<=8) vagy (i=4)); Ha Hossz(fn)<=8 akkor fn:=fn+'.txt'; hol:=FSearch(fn,GetEnv('PATH')); különben hol:=''; c. amig nem ((i=4) vagy (hol<>'')); Ha (hol<>'') akkor Jelöl(fbe,fn); vége {akkor} különben assigncrt(fbe); Ha kf=igaz akkor kezdet Ciklus... Kiir('Melyik file-ba (max. 8 hosszu nev)? '); Beolvas(fn); növel(i); c. amig nem ((i=4) vagy (length(fn) eleme [1..8])); Ha (length(fn) eleme [1..8]) akkor kezdet fn:=fn+'.txt'; assign(fki,fn); vége; vége {akkor} különben assigncrt(fki); Eljárás vége; Eljárás file2lancfa(változó fb:text; változó lf:tlancfa); változó sz:Tvalaki; c:szöveg; {a svagyvegi "szemethez"} kezdet reset(fb); Beolvas(fb,sz); Beolvas(fb,c); lefoglal(lf); Ha lf<>nil akkor kezdet lf^.ertek:=sz[1]; lf^.os:=nil; lfabeszur(sz[2],hamis,lf); {bal} Beolvas(fb,sz); Beolvas(fb,c); lfajobbbeszur(sz[2],igaz,lf); {jobb} Ciklus... Beolvas(fb,sz); Beolvas(fb,c); faelejere(lf,lf,hiba); bkj_keres(lf,sz[1],lf); lfabeszur(sz[2],hamis,lf); {bal} Beolvas(fb,sz); Beolvas(fb,c); lfabeszur(sz[2],igaz,lf^.os); {jobb} c. amig nem (eof(fbe)); hiba:=hamis; vége különben hiba:=igaz; vége AlEljárás LfaBeszur(konstans er:tertek; irany:logikai; változó lf:tlancfa); változó svfa:tlancfa; {uj: ertek, gy1,gy2 os:az eddigi * regi.gyx:=uj * regi:=uj} lefoglal(svfa); Ha lf<>nil akkor kezdet svfa^.ertek:=er; svfa^.balmut:=nil; svfa^.jobbmut:=nil; svfa^.os:=lf; Ha (irany=hamis) akkor lf^.balmut:=svfa; lf:=lf^.balmut; különben lf^.jobbmut:=svfa; lf:=lf^.jobbmut; hiba:=hamis; vége különben hiba:=igaz; {(svfa=nil)} Aleljárás vége; AlElj. lfajobbbeszur(konstans er:tertek; irany:logikai; változó lf:tlancfa); változó svfa:tlancfa; kezdet lefoglal(svfa); Ha svfa<>nil akkor svfa^.ertek:=er; svfa^.os:=lf^.os; svfa^.balmut:=nil; svfa^.jobbmut:=nil; lf^.os^.jobbmut:=svfa; lf:=lf^.os^.jobbmut; hiba:=hamis; különben hiba:=igaz; {(svfa=nil)} Aleljárás vége; Eljárás vége; Eljárás lancfa2statfa(konstans lfa:tlancfa; változó sf:tstatfa); {szelessegi bejarassal} változó i:egész; irany:logikai; {0:bal, 1:jobb} melyseg:egész; {eleg lenne tombmax-ig} svfa:tlancfa; hatvany:egész; j:egész; {cv} tipus tugralt=tömb[1..255] of egész; változó UgralTomb:tugralt; kezdet i:=1; melyseg:=1; lefoglal(svfa); sfanullaz(sf); ugrnullaz(ugraltomb); faelejere(lfa,svfa,hiba); sf[i]:=svfa^.ertek; ugraltfelt(melyseg-2,ugraltomb); gy_ertekad(svfa); svfa:=svfa^.balmut; Ciklus nem(vege(svfa)) do kezdet Ha nem(vege(svfa)) akkor gy_ertekad(svfa); {h,i} ugral(ugraltomb,svfa,melyseg-1); növel(melyseg); ugraltfelt(melyseg-2,ugraltomb); nedikos(svfa,melyseg-1,svfa); {fel} {utolso sf-ertek: (h,i), de lefele nem nvagymalisan jon vissza!} Ciklus j:=1-tol melyseg-ig: svfa:=svfa^.balmut; vége; {Ciklus} vége AlEljárás gy_ertekad(konstans svfa:tlancfa); növel(i); sf[i]:=svfa^.balmut^.ertek; növel(i); sf[i]:=svfa^.jobbmut^.ertek; AlEljárás vége; AlEljárás UgralTFelt(konstans m:egész; változó ugrt:Tugralt); változó sv:szöveg; {sv: akt+valtozas+akt (mindig a megfelelot hozzaadja)} akt:szöveg; {akt: az eddigi, a valtozas nelkul} strsv:szöveg; {az str() parameterezese miatt kell} ok:egész; {a val() parameterezese miatt kell} eddigivalt:egész; i,j:egész; kezdet akt:='1'; val(akt,Ugrt[1],ok); sv:=akt; i:=1; eddigivalt:=1; hatvanyoz(2,m,hatvany); Ciklus ( i<=(hatvany-1) ) kezdet növel(i); növel(eddigivalt); UgrT[i]:=eddigivalt; str(eddigivalt,strsv); sv:=akt+strsv; Ciklus j:=1 to (length(sv)-1) do kezdet val(sv[j],UgrT[i+j],ok) vége; i:=i+j; sv:=sv+akt; akt:=sv; vége; {Ciklus} Aleljárás vége; AlEljárás ugral(konstans UgrT:Tugralt; változó lfa:Tlancfa; k. param:egész); változó mennyitugrik:egész; k:egész; hatv:egész; k:=1; hatvanyoz(2,param,hatv); Ciklus ( k <= (hatv-1) ) do kezdet mennyitugrik:=UgrT[k]; Ha (mennyitugrik=1) akkor lfa:=lfa^.os^.jobbmut; növel(k); Ha nem(vege(lfa)) akkor gy_ertekad(lfa); különben nedikrokon(param,lfa,lfa); növel(k); Ha nem(vege(lfa)) akkor gy_ertekad(lfa); vége; {Ciklus} Aleljárás vége; Eljárás vége; Eljárás StatfaKiir(változó fki:text; konstans sf:tstatfa); Függvény uresegyerek(konstans svsf:tstatfa; sfind:tindex; irany:logikai):logikai; Ha ( (sfind*2)>nmax ) akkor uresegyerek:=igaz különben Ha ( ((sfind*2)+1)>nmax ) akkor uresegyerek:=igaz különben Ha nem( (sorszám(svsf[sfind]) eleme [65..90]) vagy (sorszám(svsf[sfind]) eleme [97..122])) akkor uresegyerek:=igaz {különben Ha... -> tovabbi feltetelek} különben uresegyerek:=hamis; vége; AlEljárás KBJ_kiir(változó fki:text; konstans svsf:tstatfa; akti:tindex); változó bale:logikai; {a bal-gyerekerol van-e szo} kezdet Kiir(fki,svsf[akti]); Kiir(fki,' '); bale:=igaz; {bal} Ha nem(uresegyerek(svsf,akti,bale)) akkor kbj_kiir(fki,svsf,2*akti); bale:=hamis; {jobb} Ha nem(uresegyerek(svsf,akti,bale)) akkor kbj_kiir(fki,svsf,(2*akti)+1); Aleljárás vége; kezdet MegyitIr(fki); Sorkihagy(fki); Kiir(fki,' '); kbj_kiir(fki,sf,1); {a rekurzio miatt van kulon eljarasban} Bezár(fki); Eljárás vége; Eljárás sfanullaz(változó tomb:tstatfa); Ciklus i:=1-tol nmax-ig tomb[i]:='0'; Eljárás ugrnullaz(változó ugrtomb:tömb of egész); Ciklus i:=1 to nmax do ugrtomb[i]:=0; Függvény Vege(konstans lfa:tlancfa):logikai; Ha ((lfa^.balmut=nil) és (lfa^.jobbmut=nil) {es nnövels testvere}) akkor vege:=igaz különben Ha nem( (sorszám(lfa^.ertek) eleme [64..90]) vagy (sorszám(lfa^.ertek) eleme [97..122])) {((ofs(lfa^.balmut)=0) és (ofs(lfa^.jobbmut)=0) )} akkor vege:=igaz különben vege:=hamis; Eljárás vége; Eljárás hatvanyoz(konstans mit,mire:egész; változó hvsv:egész); Ciklus hvi:=1-tol mire-ig hvsv:=hvsv*mit; {--rokonsagi fv-k--} Függvény Szulo(konstans n:Tindex):Tindex; {szulo:=( n-(n mod 2) ) div 2;} Függvény Balgyerek(konstans n:Tindex):Tindex; {Balgyerek:=2*n;} Függvény Jobbgyerek(konstans n:Tindex):Tindex; {Jobbgyerek:=(2*n)+1;} Függvény Gyokere(lf:Tlancfa):logikai; {gyokere:=(lf^.os=nil);} Eljárás NedikOs(k: lfa:tlancfa; n:egész; v: lfn:tlancfa); lfn:=lfa^.os; Ciklus i:=1-tol (n-1)-ig: lfn:=lfn^.os; Eljárás NedikRokon(konstans n:egész; elem:tlancfa; változó rokon:tlancfa); nedikos(elem,n,rokon); rokon:=rokon^.jobbmut; Ciklus i:=1-tol (n-1)-ig rokon:=rokon^.balmut; Eljárás vége; Eljárás FaElejere(k: lfa:tlancfa; v: svfa:tlancfa; hiba:logikai); svfa:=lfa; Ciklus amig nem(svfa^.os=nil): svfa:=svfa^.os; Eljárás BKJ_keres(konstans lfa:tlancfa; er:tertek; változó ezaz:tlancfa); Ha lfa^.ertek=er akkor ezaz:=lfa különben Ha nem(vege(lfa)) akkor Ha (lfa^.ertek<>er) akkor bkj_keres(lfa^.balmut,er,ezaz); bkj_keres(lfa^.jobbmut,er,ezaz); Eljárás vége; *** Algoritmus vége *** A Pm4be2 program dokumentációjának kiegészítése (algoritmus) 2001. április közepe 1 / 4. oldal Szamosközi Péter