A struktogramok és átírásuk C++ kóddá
A szekvenciális1 programok (vagy legalábbis az a részük, amit struktogrammal megadunk) alapvetően 5 félék lehetnek:
üres utasítás értékadás szekvencia elágazás ciklus
Ezek kombinálásából épül fel még a legbonyolultabb program lényegi algoritmusa is. Ebből az következik, ha ezeket az építőköveket tudjuk értelmezni és ezekből kódolni, akkor közvetetten bármilyen összetett programmal is „el tudunk bánni”, ugyanazzal a megközelítéssel, technikával, a struktúrája mentén. Lássuk az öt féle programot egyesével! Üres utasítás Ez a legegyszerűbb eset, a struktogramban egy kötőjel (esetleg egy SKIP felirat) felel meg neki, kódolása annyi, hogy nem írunk semmit2… Struktogram:
Kód:
Felmerülhet a kérdés, hogy hol használunk ilyet. Ebben a dokumentumban, később, az elágazásról szóló részben van példa arra, hogy a struktogram szintjén üres utasítást kelljen írnunk. A kód szintjén pedig gyakran előfordul az ún. kivételkezelés során a catch blokkban. De ez nem ennek a félévnek a témája. Értékadás Egy olyan egyszerű utasítás, amely egy vagy több változónak értéket ad. Struktogramban a „legyen egyenlő” jel baloldalán felsoroljuk a változókat, a jobb oldalán pedig sorrendhelyesen azokat az értékeket vagy kifejezéseket, amelyeket ezeknek a változóknak értékül adunk. Ezt a struktogramban úgy kell érteni, hogy több változónak egyszerre, egy időben adunk értéket (szimultán értékadás), de a C++ kódban ez a fajta „párhuzamosság” nem megvalósítható. Ha a változóinknak nincs sok köze egymáshoz, akkor felcseréljük a szimultán értékadást egyszerű értékadások szekvenciájára (a sorrend mindegy): Struktogram:
Kód: a=a+1; b=b+1; vagy b=b+1; a=a+1;
1 2
a programsorok, mint utasítások egymás utáni végrehajtásán alapuló modell esetleg, írhatnánk csak úgy magában egy darab pontosvesszőt – mivel minden utasítást pontosvessző zár le, így az üreset is.
Ha viszont egy változót bal és jobb oldalon is felsorolunk, akkor baj van: Struktogram:
Kód: ???
Itt ezt úgy értjük, hogy az értékadás végrehajtása után a növekedjen meg eggyel és b értéke legyen a régi értéke+1, azaz (itt, ebben a példában legalábbis) pontosan az, ami a végrehajtás utáni értéke lesz… Ezt hogy lehet lekódolni? Vagy valami trükközéssel, de van általános szabály is. Nézzük a trükközést: Struktogram:
Kód: a=a+1; b=a;
Nyilván ez nem valami általános megoldás, erre a feladatra speciel használható. Mivel a-nak is és b-nek is a régi értéke +1 kell, hogy legyen az új értéke, ezért előbb a-t megnöveljük, majd ezt b-nek értékül adjuk. Nagyon vigyázni kell ezzel, ismernünk kell a műveleteket, amiket használunk. Most képzeljük el – mert miért ne – hogy a hozzáadás műveletünk úgy működik, hogy minden meghívásakor kiír egy üzentet. Amikor én a stukiba két helyre írok összeadást, akkor számítok erre, hogy ez két üzenetet meg fog jelenni, de a mellékelt kódban csak egy fog megjelenni… Tehát, ez a fajta módszer gondokat okozhat az ún. mellékhatásos függvények hívása esetén. Viszont a szimultán értékadásnál nincs sorrendiség a felsorolt változók között (hisz eredetileg mind egyszerre kap értéket), tehát a fentit így is át lehet írni C++-kódra: Struktogram:
Kód: b=a+1; a=a+1;
… és így máris két összeadás szerepel a kódban, ugyanúgy mint a struktogramban. Az a=a+1; b=a+1; sorrend már nem lenne helyes, hiszen itt b végül a eredeti értékénél kettővel nagyobb lenne. Amúgy két szám, és a rajtuk elvégzett sima mezei összeadás esetében az első megoldás a javasolt átírás, hiszen hatékonyabb (=kevesebb műveletet kell elvégeznie a processzornak gyorsabb a program), mint a második verzió. Általánosabb megoldás, ha kimentünk minden problémás változót egy-egy segédváltozóba, majd ezen segédváltozók értékét használjuk az értékadásokban: Struktogram:
Kód: int c=a; a=c+1; b=c+1;
Ez a logika van a swap-művelet (azaz a két változó megcserélése) átírása mögött is: Struktogram:
Kód: int c=a; a=b; b=c;
Szekvencia Két vagy több (akár bonyolultabb) utasítás egymás utáni végrehajtását jelenti. Ennek megfelelően a kódja is mindössze annyi, hogy egymás után sorban leírjuk a szekvenciában részt vevő programrészekhez tartozó kódokat… Itt persze számít a sorrend, ami a struktogramban felül van, az kerül a kódban is felülre…: Struktogram:
Kód: a=4; b=a+1;
Elágazás Ennek többféle fajtája is van. A struktogram szintjén megkülönböztetjük a két- vagy többágú elágazást, a C++ pedig az egyágú, kétágú, többágú és switch/case eseteket. Nézzük elsőnek a kétágú elágazást: Struktogram:
Kód: if(a>0) { b = a; } else { b = -a; }
A kétágú elágazás struktogramja mindig egy feltétel vizsgálattal indul. A két „átlós pöcök” közé egy logikai kifejezést kell írni, pl, hogy a változó pozitív-e… Ha ez igaz, akkor a bal oldali (igaz-ág) kódja fut le (itt persze egész nagy, összetett program is lehet), ha nem, akkor pedig a jobb (hamis-ág). Kódban az if kulcsszót a feltétel követi kerek zárójelek között, majd kapcsos zárójelek között3 az igaz-ág kódja, majd egy else (különben) kulcsszót követően kapcsos zárójelek között a hamis-ág kódja.
3
Általános C++-os szabály: ha a kapcsos zárójel közti utasításblokk (if, for, while magjában) csak egy utasításból áll, akkor elhagyható a kapcsos zárójel. Illetve a kapcsos zárójelekbe írt programblokkok után (tehát maga a kapcsos zárójel után) nem kell pontosvesszőt írni, annak ellenére sem, hogy amúgy minden utasítást azzal kellene zárni. Ezeket maga a kapcsos zárójel lezárja.
Nézzünk egy ilyen kétágú elágazásos struktogramot: Struktogram:
Kód: if(a>0) { b = a; } else { }
Ez elég gyakran előforduló helyzet, hogy az egyik ág üres. Ekkor (bár a fenti átírás is működik) használjuk az ilyen „csonka” kétágú elágazások átírására a C++ egyágú elágazását, azaz az else ágat egyszerűen hagyjuk el, ugyanis ha egy C++-os if szerkezetben nem fedünk le minden esetet, akkor a C++-fordító automatikusan hozzágondol egy ilyen üres törzsű else ágat. Struktogram:
Kód: if(a>0) { b = a; }
Persze elvileg a baloldali ág is lehet üres: Struktogram:
Kód: if(a>0) { } else { b = a; }
Ez bár helyes és működik is, de azért elég ocsmány. Alakítsuk át… tagadjuk le a feltételt és cseréljük meg az ágakat, és máris szebb alakú elágazást kapunk. Struktogram:
Kód: if(a<=0) { b = a; }
Mi a helyzet akkor, ha nem csak két eset van? Ezeket hívjuk többágú elágazásnak. Struktogram:
Kód:
if(a>0) { b = 1; } else if(a==0) { b = 0; } else if(a<0) { b = -1; } A struktogramot úgy kell érteni, hogy ha a fent felsorolt feltételek valamelyike igazra értékelődik ki, akkor az ő hozzá tartozó ág fut le. Tehát ha a pozitív, akkor b értéke 1 lesz stb. A kétágú elágazás struktogramjánál nem fordulhatott elő, de itt igen, mi van, ha az ágak átfednek, illetve mi van, ha nem fednek le minden esetet? A struktogramban ha az ágak átfednek (pl. van egy és egy feltételű ág is), akkor amikor a változó értéke pozitív, akkor az átfedő ágak valamelyike fog végrehajtódni. Nem tudjuk melyik, de azt tudjuk, hogy csak az egyik. Ha a programot többször is futtatom, nincs rá garancia, hogy mindig ugyanaz az ág fog lefutni. Ezt hívják nemdeterminisztikus működésnek, a C++ viszont ebben a kérdésben determinisztikusan viselkedik. Ha az ágak nem fednek le mindent, tehát pl. a fenti elágazásból kimaradt volna az eset és ha a épp egyenlő 0-val…, akkor a struktogram szerint ilyenkor a program elszáll. C++-ban ez se fordulhat elő, hiszen mint már korábban említettem, a C++ mindig hozzáír az elágazásokhoz egy üres else ágat, tehát ha egyik ág se teljesül, akkor ez az üres blokk fog lefutni, a program továbblép, nem fagy be. A C++ elágazásában tehát nincs nemdeterminisztikusság, ezt fejezik ki a többágú szerkezet során használt kulcsszavak is. A fenti kód így működik: Megvizsgálja, a pozitív-e. Ha igen, lefut az első ág, és vége az elágazásnak. Ha nem, megvizsgálja 0-e. Ha igen, lefut a 2. ág és vége az elágazásnak. Ha nem, megvizsgálja a 3. feltételt, és ha az igaznak bizonyul, lefut a 3. ág, különben az odaképzelt üres törzsű else ág. Tehát a C++-ban leírási sorrendben értékelődnek ki az ágak és kizárják egymást. Tekintsük ezt a példát: if(a>0) b=1; else if(a>=0) b=2; Itt b, ha a pozitív, biztosan 1 lesz. Pedig az ezzel közel ekvivalens struktorgram szerint akár 2 is lehetne. Mindez azért, mert az feltételvizsgálat van előbb. Ha a nulla, akkor b 2 lesz, különben pedig nem történik semmi.
Mi van, ha kihagyjuk az else szócskát? A kód akkor is értelmes, de elképzelhető, hogy nem azt csinálja, amit várunk: if(a==0) a=1; if(a==1) a=2; Azt várjuk, hogy ha a értéke 0, akkor legyen 1, ha 1, akkor meg legyen 2. Ehelyett mit kapunk? Ha a értéke 0, akkor bizony 2 lesz. Miért? Mert ez nem egy többágú elágazás, hanem két szimpla elágazás egymás után írva (azaz szekvencia). Megnézzük a értéke 0-e. Ha igen, akkor 1-re állítjuk, és elágazás vége. Jön a következő elágazás, a értéke vajon 1-e. Persze, hogy az, mert most állítottuk arra. OK, akkor legyen 2. Struktogram:
Kód: if(a==0) a = 1; if(a==1) a = 2;
versus Struktogram:
Kód:
if(a==0) a = 1; else if(a==1) a = 2; (bár ez se teljesen korrekt az automatikusan hozzáíródó üres else ág miatt) Többágú elágazást lehet egymásba ágyazott kétágú elágazásokkal helyettesíteni. if(a==0) { b = 1; } else if(a==1) { b=2; } else if(a==2) { b=3; }
ekvivalens ezzel:
if(a==0) { b = 1; } else { if(a==1) { b=2; } else { if(a==2) { b=3; } } } De azért az első csak szebb. De azt fontos látni, hogy az első se teljesen azt a nemdeterminisztikus algoritmust valósítja meg, amit egy többágú elágazós struktogram sugall, hanem pontosan azt, amit a jobb oldalon álló egymásba ágyazott kétágú elágazásokból felépülő algoritmus struktogramja lenne.
Még egy tipp elágazásokra. Ha adott egy többágú elágazás, ami minden esetet lefed, akkor az utolsó ág feltétele végül is elhagyható: Struktogram:
Kód: if(a>0) { b = 1; } else if(a==0) { b = 0; } else { b = -1; }
Az elágazások utolsó fajtája a switch/case. Ennek nincs struktogrambeli megfelelője, amúgy is ami switch/case-zel megadható, az iffel is, tehát nem túl fontos téma, lehet nélküle is boldog életet élni, de a teljesség igénye miatt megmutatom. A switch/case arra a helyzetre van kitalálva, amikor arra vagyunk kíváncsiak, hogy egy bizonyos változó értéke egy konkrét konstanst vesz-e fel. Ilyen konstrukciót például menük kódolásakor érdemes használni, ahol a felhasználónak például számokat kell beírnia, és attól függően melyik számot írta be történik más és más. Nézzük meg ezt egy iffel: if(menupont == 1) { >>egyes szamu funkcio vegrehajtasa<< } else if(menupont == 2) { >>kettes szamu funkcio vegrehajtasa<< } else { cout<<”HIBA! Nem letezo menupont”<<endl; } Ehelyett alkalmazhatjuk ezt: switch(menupont) { case 1: >>egyes szamu funkcio vegrehajtasa<< break; case 2: >>kettes szamu funkcio vegrehajtasa<< break; default: cout<<”HIBA! Nem letezo menupont”<<endl; break; }
Kinek a pap, kinek a papné, valakinek ez a forma jobban tetszik. Szerintem nem sok értelme van, hiszen az iffel hasonló méretű erőfeszítéssel lehet kifejezni ugyanazt. Szeretném felhívni a figyelmet a break utasításokra. Ez egy régről örökölt, ún. nemstrukturált elem (az ilyenek használata kerülendő és kiveszőfélben is van). Jelentése az, hogy a legbelső blokkból ahol épp a vezérlés van, lépjünk ki és folytassuk a végrehajtást a blokk után. A „blokk” az, ami a kapcsos zárójelek között van, tehát a break utasítás hatására történik (ebben a szerkezetben) az, hogy NEM ugrik tovább a következő ágra a vezérlés és hajtódik végre az is, mert hogy a switch/case alapértelmezett működése ez lenne. Egy példa: switch(menupont) { case 1: >>egyes szamu funkcio vegrehajtasa<< case 2: >>kettes szamu funkcio vegrehajtasa<< break; default: cout<<”HIBA! Nem letezo menupont”<<endl; break; } Itt, ha a felhasználó az egyes menüpontot választja, akkor végrehajtódik a kettes ág is. A default azért nem, mert a kettes végén break van. Amúgy a „default” a hagyományos elágazás else-ének felel meg. A break mellett még két további nemstrukturált elemet ismerünk, a continue-t és a gotot. Használatuk mellőzendő, mert olvashatatlanná és nehezen követhetővé teszik a kódot. A continue ciklusokban használatos és olyasmit jelent mint a break, azaz szakítsuk meg a blokk (ciklusmag) végrehajtását, de ne a ciklus után folytassuk, hanem lépjünk egy iterációt és futtassuk le újra a ciklusmagot. A program soraihoz lehet ún. címkéket rendelni. A goto paranccsal ilyen címkéhez lehet a vezérlést küldeni. De ennek sűrű használata igen átláthatatlanná és követhetetlenné teszi a kódot, ezért ilyet végképp csak nagyon indokolt esetben használhatunk (azaz soha). Ciklusok Ebből meg 4 féle van: elöltesztelős, hátultesztelős, számlálós és foreach. Foreach ciklus a C++-ban nincs4. Amúgy az arra való, hogy ha van egy tömbünk5 és amúgy az indexek nem különösebben érdekelnek, akkor ne az indextartományon menjünk végig, hanem eleve a tömb elemeken. C#, Ada, Java nyelvekben van ilyen szerkezet többek között. Az elöltesztelős (while) ciklus úgy működik, hogy előbb letesztelem az ún. ciklusfeltételt, aztán ha az igaz, végrehajtom a ciklusmagot. Ezután letesztelem a ciklusfeltételt, ha igazat
4
na jó, van, de csak az újabb szabványban… amikor én tanultam, még nem volt :P nem csak tömb van ám a világon… vannak olyan adatszerkezetek is, amik nem indexelhetők, na ahhoz meg főleg kényelmes ezt használni, mert nem is tudnánk olyan ciklust írni, ami az indextartományán megy végig, ha egyszer nincs olyan neki 5
ad akkor lefuttatom a ciklusmagot, stb. Ha egyszer hamis lesz a feltétel, akkor a ciklus utáni részre lép a végrehajtás, ha sose lesz hamis, akkor a program sose áll le (végtelen ciklus). Simán előfordulhat az is, hogy a ciklusmag egyszer se fut le, ha már eleve hamis a feltétel. Ez nem feltétlenül baj, sőt általában összhangban van a programozó szándékával. Struktogram:
Kód:
while(a>0) { --a; } Ez a ciklus voltaképpen 0-ra állítja a-t. Ha a eleve 0, vagy annál kisebb, akkor viszont úgy hagyja ahogy van. A ciklushoz nagyon gyakran tartozik valami inicializáló lépés. Pl. itt van egy tömbbejárás: Struktogram:
Kód:
i=0; while(i
Kód: ( )
do { bekeres(a); } while(a<0); Tehát itt a változóba addig kérek be egy számot, amíg a bekért szám negatív. Így lehet mondjuk azt biztosítani, hogy a egy természetes szám legyen. Számlálós ciklus Ezt a ciklusfajtát akkor használjuk, ha előre tudjuk azt, hogy a ciklusmagot hányszor kell lefuttatni. Az előző két esetben mindig valami feltétel került a ciklus fejébe, most pedig egy számlálóval fogunk végigjárni egy intervallumot, és minden egyes intervallumbeli értékre le fog futni egyszer a ciklusmag. A C++ szintjén a for és a while ciklus ekvivalens, mindkettő helyettesíthető a másikkal a megfelelő paraméterezéssel.
Struktogram:
Kód:
for(int i=1;i<=n;++i) { a+=i; } Tehát itt egy csak a for ciklusban élő segédváltozóval bejárjuk az [1..n] intervallumot, és például megnöveljük a-t a segédváltozó aktuális értékével. A segédváltozó (általában i-vel jelöljük) csak ebben a ciklusban használható, épp ezért ha sok for ciklust írunk egymás után, akkor nyilván az ő „i-jeiknek” semmi közük nem lesz egymáshoz. Viszont ha egymásba ágyazunk ciklusokat, akkor nyilván a belső ciklus változóját illik máshogy hívni, mint a külső ciklusét. Azonban ez a C++-ban nem kötelező! Ez egy érdekes sajátossága a nyelvnek, a jelenséget elfedésnek (shadowing) hívják és nagyon meglepő következményei lehetnek: for(int i=0;i<3;++i) { for(int j=0;j<2;++j) { cout<<j<<" "; } cout<<endl; } Ez a kód 3 sort fog kiírni (mert a külső for ciklus három kört megy), mindannyiszor két számot (mert a belső for ciklus kétszer fut le), 0-t és 1-et, mert ezeket az értékeket veszi fel j minden körben. for(int i=0;i<3;++i) { for(int i=0;i<2;++i) { cout<
Még ennél is sokkal rosszabb ez a megoldás, ami szintén lefordul és lefut: for(int i=0;i<3;++i) { for(i=0;i<2;++i) { cout<
Kód: for(int i=n;i>=1;--i) { a+=i; }
6
Igazából az első és a 3. paraméterhez tetszőleges utasítást, a 2-hoz tetszőleges feltételvizsgálatot írhatunk. Csak így szokás. Írhatunk üres utasításokat is: például a for(;i
Struktogram:
Kód: for(int i=1;i<=10;i+=2) { a+=i; }
Egyéb különbségek Egyenlőségvizsgálat, relációs jelek, értékadás szintaktikája: Struktogramban:
Kódban: a==b //vizsgalat a>b a
=b a<=b a = b //ertekadas
Tömbindexelés: Ha a specifikációban és algoritmusban adott egy [ ] indexelésű tömb, azt a C++-ban [ ] indextartományúként fogjuk kezelni. Ezen kívül az is fontos, hogy általában ez az n egy bemenő adat, tehát a tömb mérete a felhasználó akaratától függ. Egyelőre ezt C++-ban nem engedjük, ezért mindig megadunk egy konstans maximum értéket n-re, a tömb a „valóságban” akkora, mint ez a maximum, de csak az első n darab értékét használjuk. Struktogram:
Kód:
( [ ])
Struktogram: ( [ ])
i=0; while(i
Nyilván az i
Matematikai dolgok: Struktogramban:
Kódban: i=i+1; i+=1; i++ ++i
Igazából bármelyik használható, bár árnyalatnyi különbség van köztük: A + két tetszőleges kifejezést ad össze és ezt egy változónak értékül adhatjuk (a változónak nem kell hogy bármi köze legyen a két kifejezéshez), a += egy változót megnöveli egy kifejezés értékével, a ++ egy változót megnövel eggyel. Ha előre írom a ++-t, akkor megnöveli, és maga a ++i kifejezés felveszi i új értékét, ha hátulra, akkor is megnöveli de a kifejezés értéke még i régi értéke marad. Mivel ez utóbbi megvalósítása eggyel több műveletet tartalmaz, mint a prefixes ++-é (hiszen ki kell mentenie i eredeti értékét egy segédváltozóba), ezért általában illik a ++-t a változó elé írni, mert az a megoldás hatékonyabb. Logikai műveletek: Struktogramban:
Kódban: a&&b a||b !a
Egy feltételvizsgálatban, ha a vizsgálandó feltétel egy logikai változó igazságértéke, akkor fölösleges7 == true-t vagy == false-t írni, még akkor se, ha a struktogram ezt sugallja, hanem ezt sokkal egyszerűbb szintaktikával is meg lehet oldani: Struktogram:
Kód: while(a) { if(!b) c = 1; else c = 2; }
Láthatjuk, ha arra vagyunk kíváncsiak, vajon egy változó igaz-e, akkor csak odaírjuk a nevét, ha a „hamisságot” szeretnénk vizsgálni, akkor pedig egy felkiáltójellel (tagadás jele) lehet jelölni szándékunkat.
7
de szabadni szabad
Egy „komplex” példa: Struktogram:
[] []
Kód:
[]
[] []
[]
[] []
(értelmet ne nagyon keressetek ebben a stukiban :D)
int i = 0; while(ij && t[i]<2*j) t[i] = i+1; else if(t[i]>2*j) t[i] = j; } i += 1; }
i végig a 0..n-1 vonalon mozog, mivel tömbindex, j viszont a kódban is annyi, amennyi a struktogramban, mert őneki tényleg az értékét használjuk, nem pedig indexelésre, mint i-t. t tömbben számértékek vannak, és amikor az alg. szerint i-t kellett beírni, i+1-et írtam be, ugyanis itt i nem egy index, hanem egy szám (de ez már nagyon elfajult dolog, ilyen nem lesz zh-ban). Az elágazás üres programos ágát elhagytam, hiszen így is-úgy is üres programot (=semmit) fog végrehajtani.
