1 Eljárások (alprogramok), függvények • eljárások (procedure) • változók hatásköre • függvények (function)
Mielőtt nekiállna a tanfolyamnak, töltse le és telepítse be a számítógépébe a FreePascal Win32 alatt futó verzióját. Ez a következő weboldalról tölthető le: www.freepascal.org. 1.1 Eljárások (procedure) A programozás során gyakran előfordulhat, hogy valamilyen programrészt a programunkban többször végrehajtunk. Például a tömböknél kiírattuk a tömböt, változtattunk rajta valamit majd ismét kiírattuk a képernyőre. Ilyenkor egyszerűbb a tömb kiírására egy eljárást (alprogramot) írni és kiírásnál csak ezt az eljárást meghívni. A programunk ebben az esetben így nézhet ki: program Pelda01; const n=10; var i:integer; a:array[1..n] of integer; procedure kiir; begin write('A tomb elemei: '); for i:=1 to n do write(a[i],' '); writeln; end; begin { tomb kigeneralasa: } for i:=1 to n do a[i]:=random(99)+1; { tomb kiirasa alprogrammal: } kiir; { tomb megvaltoztatasa, pl. mindegyik elemet megszorozzuk 2-vel: } for i:=1 to n do a[i]:=2*a[i]; { tomb kiirasa ismet alprogrammal: } kiir; end.
Az eljárást (alprogramot) mindig a procedure szóval kezdjük írni még a főprogram kezdete előtt, a változók deklarálása után. A procedure szó után megadjuk az eljárás nevét, majd a következő sortól írhatjuk az eljárást begin és end; közé. Az eljárást a főprogramból egyszerűen az eljárás nevével hívhatjuk meg. Egy programba írhatunk több eljárást is, pl. egyet a tömb generalására, egyet a kiírására, stb. Az eljárásunknak átadhatunk a főprogramból valamilyen értékeket is paraméterek segítségével. Például, ha szeretnénk készíteni egy olyan eljárást, amely kiír valamilyen szöveget úgy, hogy minden betűjét a szövegnek megváltoztatja nagy betűre, akkor a kiírandó szöveget átadhatjuk az eljárás paraméterében. Ekkor a programunk így nézhet ki: program Pelda02a; var s:string; procedure nagybetukkel(m:string); var i:integer; begin for i:=1 to length(m) do m[i]:=upcase(m[i]); writeln(m); end; begin nagybetukkel('Kerek egy szoveget: '); readln(s); nagybetukkel(s); writeln('S erteke a program vegen: ',s); end. Ez program kiírja nagy betűkkel, hogy "KEREK EGY SZOVEGET: ", majd bekér egy mondatot és ezt kiírja nagy betűkkel. Végül még kiírja az s értékét (eredeti szöveget). Az eljárásban paraméterként szereplő m változót csak az eljáráson belül használhatjuk, máshol nem érhető el. Hasonlóan az eljárásban deklarált i változót is csak az eljáráson belül használhatjuk - ezek úgynevezett lokális (helyi) változók. Az eljárás az s változó értékét nem változtatja meg, csak a helyi m változóét. Tehát az eljárás lefutása után az s változóban marad az eredeti, kisbetűs szöveg (ez kiíródik a főprogram végén). Az ilyen m változót nevezzük formális paraméternek. Ha valami végett mégis olyan eljárást szeretnénk írni, amely az s változó értékét is megváltoztatja (tehát azt szeretnénk, hogy az eljárás lefutása után az s változóban is a nagybetűs szöveg legyen - ugyanaz mint az eljáráson belül az m változóban), akkor az eljárásunk paraméterének megadásánál az m változó előtt
használhatjuk a var utasítást. Az ilyen paramétert nevezzük valódi paraméternek. program Pelda02b; var s:string; procedure nagybetukkel(var m:string); var i:integer; begin for i:=1 to length(m) do m[i]:=upcase(m[i]); writeln(m); end; begin s:='Kerek egy szoveget: '; nagybetukkel(s); readln(s); nagybetukkel(s); writeln('S erteke a program vegen: ',s); end. Eljárásunkban használhatunk több változót is, melyek közül lehet némelyik formális paraméter, némelyik valódi paraméter. Például egy eljárást megadhatunk ilyen paraméterezéssel is: procedure szamol(s:string; a,b:integer; var c:integer); Ebben az esetben csak a c valódi paraméter, tehát a főprogramban az eljárás lefutása után csak a c helyén megadott változó értéke változik meg. 1.2 Változók hatásköre A programozás során használhatunk globális változókat és lokális (helyi) változókat. A globális változók azok a változók, melyet a programunkban bárhol elérhetünk, bárhol használhatjuk - a főprogramba is és az eljárásban is. A globális változókat a programunk elején a var szó után soroljuk fel, ahogy eddig is tettük. A lokális (helyi) változók azok a változók, melyek a főprogramban nem érhetők el, csak az eljárásban. Tehát ezeket a változókat csak az adott eljárásban használhatjuk, a főprogramban nem. Ezeket szintén a var utasítás segítségével adjuk meg, de nem a programunk elején, hanem abban az eljárásban, melyben ezeket használni szeretnénk. Ha ugyanolyan nevű változót deklarálunk globális és lokális változóként is, akkor az eljárásban csak a lokális (helyi) változóval tudunk dolgozni, az eljáráson
kívül pedig a globális változóval. Az eljárás nem fogja megváltoztatni a globális változó értékét. Példaként vizsgáljuk meg és próbáljuk ki ezt a programot: program Pelda03; var v:integer; procedure alprg; var v:integer; begin v:=888; writeln('Lokalis V nevu valtozo erteke: ',v); end; begin v:=555; writeln('Globalis V nevu valtozo erteke: ',v); alprg; writeln('Globalis V nevu valtozo erteke: ',v); end. A program kiírja először az 555-t, majd a 888-at végül ismét az 555-t. 1.3 Függvények (function) A Pascalban vannak előre definiált függvények, ilyen például az abs(), sin(), cos( ), upper( ), length(), stb. Készíthetünk mi is saját függvényt. Ezt hasonlóan kell megírnunk mint a saját eljárásunkat, a különbség csak abban van, hogy a procedure szó helyett a function-t használjuk, és meg kell adnunk hogy milyen típust adjon vissza az általunk készített függvény. Továbbá a függvényünkön belül (általában a végén) egy ilyen típusú értéket kell adunk a függvénynek (függvény nevének). Példaként készítsünk egy függvényt, amely megszámolja, hogy egy megadott szövegben mennyi szóköz van és ezt a számot adja vissza függvényértékként: program Pelda04; var s:string; function helyekszama(x:string):integer; var i,h:integer; begin h:=0; for i:=1 to length(x) do if x[i]=' ' then h:=h+1; helyekszama:=h; end;
begin write('Irj be egy modnatot: '); readln(s); writeln('A mondatban ',helyekszama(s),' szokoz van.'); end. 2 Felsorolt típus, record, set típusok • felsorolt típus • record típus • set (halmaz) típus
2.1 Felsorolt típus A programozásban az eddig felsorolt típusokon kívül (integer, string, byte, boolean, char, array...) használhatunk saját adattípusokat is. Ezeket először a type utasítással meg kell adnunk. Az egyik ilyen típus a felsorolt típus, amely csak a felsorolt értékek valamelyikét veheti fel. Pl. program Pelda05; type nagybetu = 'A'..'Z'; szamjegy = 0..9; nap = (hetfo, kedd, szerda, csutortok, pentek, szombat, vasarnap); var a:nagybetu; b:szamjegy; n:nap; begin { program } end. Ezeket a típusokat nem olvashatjuk be közvetlenül a readln paranccsal billentyűzetről és nem is írhatjuk ki az értéküket a write paranccsal a képernyőre. Beolvasásuk és kiírásuk a következőképpen történhet: program Pelda06; type nap = (hetfo, kedd, szerda, csutortok, pentek, szombat, vasarnap); var n:nap;
i:integer; begin {beolvasas} writeln('1 - hetfo'); writeln('2 - kedd'); writeln('3 - szerda'); writeln('4 - csutortok'); writeln('5 - pentek'); writeln('6 - szombat'); writeln('7 - vasarnap'); write('Addj meg egy szamot (1-7): '); readln(i); case i of 1: n:=hetfo; 2: n:=kedd; 3: n:=szerda; 4: n:=csutortok; 5: n:=pentek; 6: n:=szombat; 7: n:=vasarnap; end; {kiiras} write('Az altalad megadott nap a '); case n of hetfo: writeln('hetfo.'); kedd: writeln('kedd.'); szerda: writeln('szerda.'); csutortok: writeln('csutortok.'); pentek: writeln('pentek.'); szombat: writeln('szombat.'); vasarnap: writeln('vasarnap.'); end; end. 2.2 Record típus A record típus mezõkbõl áll, melyek egyedi változóként kezelhetõk. Használatát példán szemléltetjük: program Pelda07; type szemely = record nev: string; szul_ev:integer; end;
var a:array [1..5] of szemely; i,jelen:integer; function beolvas:szemely; var x:szemely; begin write('Nev: '); readln(x.nev); write('Szuletesi ev: '); readln(x.szul_ev); beolvas:=x; end; begin for i:=1 to 5 do begin writeln('Kerem az ',i,'. szemely adatait...'); a[i]:=beolvas; end; write('Milyen evet irunk most? (pl.2004) :'); readln(jelen); for i:=1 to 5 do writeln(a[i].nev,' ',jelen-a[i].szul_ev,' eves.'); end. 2.3 Set (halmaz) típus A halmaz típus (set of ...) használatát is egy példa segítségével mutatjuk be. A feladatunk az volt, hogy egy beolvasott szövegben felasznált betűket írjuk ki ABC sorrendben, minden betűt csak egyszer és minden betűnek a nagybetűs formája legyen kiírva. A feladathoz definiáltunk egy halmazt, amelyet először beállítottunk üresre, majd a betűket sorban beleraktuk ebbe a halmazba. Végül egy for ciklus segítségével végignéztük, hogy az ABC melyik betűje van ebben a halmazban (in). Ha az adott betű benne volt a halmazban, kiírtuk a képernyőre. program Pelda08; const betu = ['A'..'Z','a'..'z']; type nagybetu = 'A'..'Z'; var h:set of nagybetu; s:string;
i:integer; ch:char; begin write('Irj be egy modnatot: '); readln(s); h:=[]; for i:=1 to length(s) do if s[i] in betu then h:=h+[upcase(s[i])]; write('Felhasznalt betuk:'); for ch:='A' to 'Z' do if ch in h then write(ch:2); writeln; end. 3 Állományok kezelése • szöveges állomány • típusos állomány • típus nélküli állomány
3.1 Szöveges állomány A programból elmenthetünk ill. beolvashatunk adatokat állományokból. A Pascal-ban három fajta állománytípust különböztethetünk meg: szöveges állomány, típusos állomány és típus nélküli állomány. Az első programunkban egy szöveges állományt fogunk kiíratni a képernyőre. Ehhez előbb hozzunk létre egy ilyen állományt. Szöveges állományt megírhatjuk pl. a windows jegyzettömbjében. Írjunk tehát a jegyzettömbben pár sort, majd mentsük el a szöveget abba a könyvtárba, ahova a Pascal programjainkat is szoktuk menteni. A szöveget "szoveg.txt" néven mentsük el. Ezen előkészületek után indítsuk el a FreePascal-t. Az alábbi program segítségével kiírathatjuk az elmentett állományt a képernyőre: program Pelda09; var f:text; s:string; begin assign(f,'szoveg.txt'); {$I-}
reset(f); {$I+} if IOResult<>0 then begin writeln('Hiba: nincs meg a file.'); halt; end; while not eof(f) do begin readln(f,s); writeln(s); end; close(f); end. Ha szöveges állományt használunk, azt a változók deklarálásánál text típusként kell deklarálnunk. Az assign(f,'szoveg.txt'); parancs hozzárendeli az f állományhoz a merevlemezen található szoveg.txt állományt. Ezek után a reset(f); parancs megnyitja az állományt olvasásra. A {$I-} és {$I+} utasítások kikapcsolják/bekapcsolják a pascal hibaellenőrzését, tehát azt, hogy ha a file megnyitásánál hiba keletkezik, akkor azt ne a pascal értékelje ki, hanem mi. A megnyitás után az IOResult változó értéke 0, ha sikerült megnyitni az állományt, különben a hiba kódját tartalmazza. Hiba esetén a halt; parancsnál befejeződik a programunk futása. Ha sikerült megnyitni az állományt, akkor egy ciklus segítségével kiolvasunk belőle egy sort a readln(f,s); paranccsal, majd ezt kiírjuk a képernyőre. A ciklus ezt a két utasítást addig ismétli, amíg nem értünk az állomány végére - not eof(f). (eof = end of file). Végül a close(f) paranccsal bezárjuk az állományt. Mindig, amikor a programunkban állományt használunk előbb az assign paranccsal hozzárendeljük a változót a merevlemezen található állományhoz. Utána a reset paranccsal megnyithatjuk az állományt olvasásra vagy a rewrite paranccsal felülírásra. Szöveges állományból olvashatunk a read, readln parancsokkal, írhatunk bele a write, writeln parancsokkal. Típusos állományoknál a readln és writeln parancsokat nem használhatjuk. Miután befejeztük a munkánkat az állománnyal, ne felejtsük el bezárni a fájlt a close paranccsal. A következő program azt mutatja be, hogyan írhatunk szöveges állományba. Miután ezzel a programmal beírtunk valamit az állományba, megnyithatjuk azt olvasásra az előző programmal vagy akár bármilyen szövegszerkesztővel (pl. windows jegyzettömb).
program Pelda10; var f:text; s:string; begin assign(f,'szoveg.txt'); rewrite(f); s:='elso sor'; writeln(f,s); writeln(f,'masodik sor'); write(f,'harmadik '); writeln(f,'sor'); close(f); end. A rewrite parancs törli az állomány tartalmát ha már létezik, majd megnyitja írásra. Ha még nem létezik ez az állomány a merevlemezen, akkor létrehozza azt. 3.2 Típusos állomány A típusos állományba bármilyen típusú változókat (akár általunk létrehozott rekordokat) menthetünk el. Ezt a fajta állományt ha megnyitnánk szövegszerkesztővel, nem egy egyszerű szöveget látnánk, hanem mindenféle jeleket is (akárcsak pl. egy futtatható állomány vagy kép megnyitásakor). A következő program megnyit egy állományt (ha létezik), beolvassa belőle az adatokat egy tömbbe majd a program végén elmenti a tömbből az adatokat az állományba. program Pelda11; var f:file of string; a:array [1..1000] of string; i,n:integer; { n - a tombben levo elemek szamat jeloli } begin n:=0; {beolvasas allomanybol} assign(f,'nevsor.dat'); {$I-} reset(f); {$I+} if ioresult=0 then begin while not eof(f) do begin n:=n+1; read(f,a[n]); end; close(f); end;
{ ... itt dolgozunk a tömbbel, megvaltoztatjuk, stb ... } {kiiras allomanyba} rewrite(f); for i:=1 to n do write(f,a[i]); close(f); end. 3.3 Típus nélküli állomány Míg egy típusos állományba csak ugyanolyan típusú változókat írhattunk, addig a típus nélküli állományba tetszés szerint egymás után beírhatunk bármilyen típusú változókat, vagy akár a memória egy tetszőleges részét. Amire azonban ügyelnünk kell, hogy az adatokat ugyanolyan sorrendben olvassuk ki, ahogy beírtuk azokat. A következő program létrehoz egy ilyen típus nélküli állományt, majd beleír egy string típust, ezután három integer típust, végül még egy real típust is. A program második része megnyitja az elmentett állományt olvasásra, kiolvassa az adatokat és kiírja a képernyőre. program Pelda12; var f:file; nev:string; ev,honap,nap:integer; r:real; begin write('Kerlek add meg a neved: '); readln(nev); write('Szuletesi datumod - ev (pl. 1985): '); readln(ev); write('Szutetesi datumod - honap (1..12): '); readln(honap); write('Szuletesi datumod - nap (1..31): '); readln(nap); write('Kerlek adj meg egy tetszoleges tizedes szamot: '); readln(r); {mentes tipus nelkuli fajlba} assign(f,'adatok.dat'); {$I-} rewrite(f,1); {$I+} if ioresult<>0 then begin writeln('Hiba a fajl megnyitasanal!');
halt; end; blockwrite(f,nev,sizeof(nev)); blockwrite(f,ev,sizeof(ev)); blockwrite(f,honap,sizeof(honap)); blockwrite(f,nap,sizeof(nap)); blockwrite(f,r,sizeof(r)); close(f); {beolvasas a fajlbol} {$I-} reset(f,1); {$I+} if ioresult<>0 then begin writeln('Hiba a fajl megnyitasanal!'); halt; end; blockread(f,nev,sizeof(nev)); blockread(f,ev,sizeof(ev)); blockread(f,honap,sizeof(honap)); blockread(f,nap,sizeof(nap)); blockread(f,r,sizeof(r)); close(f); {adatok kiirasa a kepernyore} writeln('Fajlbol visszaolvasott adatok:'); writeln('Nev: ',nev); writeln('Szul.dat.: ',ev,'.',honap,'.',nap,'.'); writeln('Tizedes szam: ',r); end. A típus nélküli állomány deklarálásánál a file kulcsszót kell használnunk. Az állományt a reset ill. rewrite paranccsal nyithatjuk meg olvasásra ill. írásra. Itt a reset ill. rewrite parancsok második paramétereként (ezt az előző fájltípusoknál nem adtuk meg) meg kell adnunk egy blokk méretét. Ezt célszerű 1 bájtra adni, ahogy a mintapéldánkban is tettük. Ezek után a típus nélküli állományból a blockread paranccsal olvashatunk, írni pedig a blockwrite paranccsal írhatunk. Ezeknek a parancsoknak az első paramétere maga a fájl, a második paraméter a fájlba beírandó vagy kiolvasandó változó neve (ill. mutató egy memóriacímre), a harmadik paraméter pedig egy szám, amely megadja, hogy mennyi blokkot akarunk olvasni ill. írni a fájlba (a második paraméterben megadott memóriacímtől kezdődően). Mi a példaprogramban a harmadik paraméter megadásánál a sizeof függvény segítségével megállapítottuk, hogy mennyi bájton van tárolva az adott változó a memóriában és ennyi blokkot olvastunk ill. írtunk a fájlba (mivel a mi esetünkben 1
block = 1 bájt). Végül a fájlt a close paranccsal be kell zárnunk, hasonlóan mint a többi fájltípusnál. 4 Unitok, crt unit • unitok • crt unit 4.1 Unitok Mik azok a unitok? A unit önállóan lefordítható programegység, amely jól definiált kapcsolódási felületen (interface) keresztül kapcsolódik a program más részeihez. Alapvetõ elv a moduláris programozás során, hogy a modulok belsõ része (implementation) rejtett marad a külvilág számára. Valójában az egyes unitok újabb eljárásokat, függvényeket, konstansokat és típusokat tartalmaznak, így ezeket a unitokat használva további eljárásokat, függvényeket ill. típusokat használhatunk a programjainkban. A pascal rendszer sok szabványos modullal rendelkezik, amelyek hasznos típust, konstanst, eljárást és függvényt tartalmaznak. Ezek közül a leggyakrabban használtak: • system unit - ez a unit automatikosan hozzákapcsolódik minden pascal programhoz, ez tartalmazza tartalmazza a szabványos pascal nyelv eljárásait és függvényeit, melyek közül már néhányat megismerkedtünk (pl. write, writeln, read, readln, inc, dec, abs, ...), • crt unit - elsõsorban a képernyõ szöveges üzemmódját támogató eljárásokat és függvényeket tartalmaz. Ezek segítségével lehetõség van a kurzor pozícionálására, a használt színek beállítására. Ezen kívül a modul tartalmaz néhány eljárást, amelyek segítségével a billentyűzet speciális módon érhetõ el, továbbá a unit segítségével lehetõség adódik hanggenerálásra is. • dos unit - azok az eljárásokat és függvényeket tartalmazza, melyek segítségével hatékonyabban kihasználhatjuk az DOS operációs rendszer lehetõségeit - pl. idő. dátum lekérdezése, mappákkal, állományokkal való munka, • graph unit - a képernyõ grafikus üzemmódját támogató típusok, konstansok,
eljárások és függvények gazdag készletét tartalmazza, • wincrt unit - window operációs rendszer alatt futó program grafikus ablakában használható crt unit, • winmouse unit - windows operációs rendszer alatt futó program grafikus ablakában használható unit, amely az egér kezelésére szolgál, • string unit - #0 karakterrel végzõdõ dinamikus stringek tamogatása. Ahhoz hogy valemelyik unitot (unitokat) használhassunk a programunkban, meg kell adnunk a uses hivatkozás után a unit nevét. Ez alól egyedüli kivétel a system unit, mivel ez automatikusan hozzákapcsolódik minden pascal programhoz. program unitok; uses crt; var .... ; begin .... end. Használhatunk egyszerre több unitot is, ekkor vesszõvel választjuk el õket: program unitok; uses crt, dos, graph; var .... ; begin .... end. 4.2 Crt unit A crt unit segítségével lehetõségünk van színek használatára szöveges módban. Összesen 16 színt használhatunk, ezek mindegyikére van a crt unitban definiálva egy konstans is: Black = 0; Blue = 1; Green = 2; Cyan = 3; Red = 4; Magenta = 5; Brown = 6; LightGray = 7; DarkGray = 8; LightBlue = 9; LightGreen = 10; LightCyan = 11;
LightRed = 12; LightMagenta = 13; Yellow = 14; White = 15; Így ha valamilyen színt szeretnénk használni, megadhatjuk a szín számát (pl. 4) vagy helyette a hozzá tartozó konstant, ami nem más mint a szín angol neve (pl. red). A szöveg színét a textcolor paranccsal állíthatjuk be. A textcolor parancs után addig lesz érvényes a megadott szín, amíg azt nem állítjuk át egy másik színre a textcolor paranccsal. Pl.: program Pelda13; uses crt; begin clrscr; textcolor(red); writeln('Ez a ket sor'); writeln('pirossal van irva.'); textcolor(10); writeln('Ez pedig vilagoszolddel.'); textcolor(7); writeln('Ez mar az eddig megszokott szurkevel.'); end. A clrscr parancs a képernyõ letörlésére szolgál. A képernyõtörlés után a kurzor átáll az elsõ sor elsõ oszlopába. A szöveg (betűk) színéhez hasonló módon megadhatjuk a szöveg háttérszínét is. Ezt a textbackground paranccsal tehetjük meg. program Pelda14; uses crt; begin clrscr; textbackground(blue); textcolor(yellow); writeln('Sarga betu kek haterrel.'); textbackground(0); textcolor(7); writeln('Eredeti - szurke betu feketen.'); end. A gotoxy( oszlop , sor ) parancs segítségével beállíthatjuk a kurzor pozícióját a képernyõn, így segítségével bárhová ki tudunk írni szöveget a képernyõre. Ehhez tudnunk kell, hogy a képernyõ felbontása szöveges módban 80x25, tehát 1-tõl 80ig állíthatjuk be az oszlopot és 1-tõl 25-ig a sort. A következõ példa letörli a
képernyõt, majd kiírja a képernyõ közepére a "Hello" szót. program Pelda15; uses crt; begin clrscr; gotoxy(39,13); write('Hello'); end. A crt unit tartalmaz a bilentyűzetrõl való beolvasáshoz is egy függvényt, ez a readkey. Ez a parancs vár egy billentyű megnyomására. A lenyomott billentyűt a readkey függvény visszadja, így azt megjegyezhetjük (egy char típusú változóban). program Pelda16; uses crt; var c:char; begin clrscr; writeln('Nyomj meg egy betut!'); c:=readkey; writeln('Az ',c,' billentyut nyomtad meg!'); writeln('Nyomj meg egy tetszoleges billentyut.'); readkey; end. Másik hasznos billentyűzettel kapcsolatos függvény a keypressed. Ennek értéke igaz/hamis lehet. Értéke akkor igaz, ha a felhasználó lenyomott valamilyen billentyűt. Ilyenkor a lenyomott billentyűt a readkey segítségével olvashatjuk ki. A következő program addig fogja a "Hello!" szót kiírni a képernyőre véletlenszám generátorral kigenerált helyre véletlen színnel, amíg nem nyomunk meg egy billentyűt. program Pelda17; uses crt; var c:char; begin clrscr; repeat gotoxy(random(75)+1,random(24)+1); textcolor(random(15)+1); write('Hello!'); delay(100); until keypressed; c:=readkey; end.
A delay(100) parancs leállítja 100 millisekundumra a program futását, tehát minden kiírás után vár 100 msec-ot. Ennek a parancsnak a segítségével tudjuk a fenti programunkban megadni, hogy milyen gyorsan írja ki a program a képernyõre az üzeneteket. A következõ program kiírja egy lenyomott billentyű ASCII kódját. Ez a program hasznos segédprogram lehet a későbbiekben, ha meg szeretnénk határozni melyik billentyűhöz milyen ASCII kód tartozik. Az ESC kódja a 27, ezért van a ciklus feltételénél a c=#27 kifejezés. A ciklus tehát akkor fejezõdik be, ha a c-ben levõ karakter ASCII kódja egyenlõ 27-tel, vagyis ha az ESC billentyűt nyomtuk meg. program Pelda18; uses crt; var c:char; begin clrscr; repeat c:=readkey; writeln(c,' kodja: ',ord(c)); until c=#27; end. Ennek a programnak a segítségével figyeljük meg az egyes billentyűk ASCII kódjait. Észrevehetjük, hogy némelyik billentyűnél - pl. F1, F2, ... és a nyilak lenyomásánál két kód jelenik meg. Ez azért van, mivel ezeknél a gomboknál a billentyűzet két kódot küld a számítógépnek, előszőr a 0-t, majd egy másik kódot. Az alábbi program bemutatja hogyan készíthetünk egy egyszerű menüt az eddig tanultak alapján, melyben a felfelé ill. lefelé nyilak segítségével mozoghatunk, Enter-rel aktiválhatjuk a kiválasztott menüpontot és Esc-el léphetünk ki a programból: program Pelda19; uses crt; var k:integer; { ebben fogjuk tarolni, hogy eppen melyik menuponton vagyunk } c:char; begin clrscr; k:=1; { kiirja a menut } textbackground(red); textcolor(white); gotoxy(10,10); write(' Elso '); textbackground(blue);
textcolor(yellow); gotoxy(10,11); write(' Masodik '); gotoxy(10,12); write(' Harmadik '); { a kurzort beallitjuk a jobb also sarokba } gotoxy(80,25); { beolvas egy billentyut es a menut ettol fuggoen atrajzolja } repeat c:=readkey; { ha valamelyik nyil lett megnyomva } if c=#0 then begin { atfestjuk a kivalasztottat kekre } textbackground(blue); textcolor(yellow); gotoxy(10,9+k); case k of 1: write(' Elso '); 2: write(' Masodik '); 3: write(' Harmadik '); end; { megnezzuk melyik billentyut nyomta meg a felhasznalo es ettol fuggoen megvaltoztatjuk a k erteket } c:=readkey; case c of #72: if k>1 then dec(k); { #72 = felfele nyil } #80: if k<3 then inc(k); { #80 = lefele nyil } end; { atfestjuk az uj kivalasztottat pirosra } textbackground(red); textcolor(white); gotoxy(10,9+k); case k of 1: write(' Elso '); 2: write(' Masodik '); 3: write(' Harmadik '); end; { a kurzort beallitjuk a jobb also sarokba } gotoxy(80,25); end; { ha #13 = Enter lett megnyomva } if c=#13 then begin gotoxy(10,15); textbackground(0); textcolor(7); writeln('Kivalaszottad a(z) ',k,'. menupontot!'); gotoxy(80,25);
end; until c=#27; end. A crt unit segítségével hangokat is adhatunk ki. Erre a sound( frekvencia ) ill. a nosound parancsok szolgálnak. Pl. program Pelda20; uses crt; begin sound(800); delay(1000); sound(1200); delay(500); sound(1000); delay(500); nosound; end. A crt unit összes eljárásának, függvényének és konstansának részletes leírása mintapéldákkal megtalálható a FreePascal súgójában (dokumentációjában). 5 Dos unit, rendezési algoritmusok • dos unit • rendezési algoritmusok 5.1 Dos unit A dos unit segítségével többek között lekérhetjük az aktuális dátumot és idõt. A dátumot a getdate eljárás segítségével kérhetjük le. A parancsnak négy paramétere van. Ebbe a négy paraméterként megadott változóba adja vissza az eljárás az aktuális évet, hónapot, napot és azt, hogy a hét melyik napja van éppen (0-vasárnap, 1-hétfõ, ...). Hasonlóan működik az idõ lekérésére is a gettime eljárás. Paraméterként itt is négy változót kell megadnunk, melyekben visszakapjuk az aktuális órát, percet, másodpercet és századmásodpercet. Ennek az eljárásnak a segítségével fogjuk késõbb lemérni az egyes rendezési algoritmusok futásának idõtartamát. program Pelda21; uses dos; var d1,d2,d3,d4,t1,t2,t3,t4:word; begin
getdate(d1,d2,d3,d4); gettime(t1,t2,t3,t4); write('Mai datum: ',d1,'. ',d2,'. ',d3,'. '); case d4 of 0: writeln('vasarnap'); 1: writeln('hetfo'); 2: writeln('kedd'); 3: writeln('szerda'); 4: writeln('csutortok'); 5: writeln('pentek'); 6: writeln('szombat') end; writeln('Ido: ',t1,':',t2,':',t3,'.',t4); end. A dos unit összes eljárásának, függvényének és konstansának részletes leírása mintapéldákkal megtalálható a FreePascal súgójában (dokumentációjában). 5.2 Rendezési algoritmusok Adott egy tömb, melyben véletlenszerű számok vannak. Feladatunk, hogy rendezzük ezeket a számokat növekvõ sorrendbe különbözõ algoritmusok segítségével. A rendezés idejét minden esetben mérjük le századmásodpercekben. Egyszerű rendezés (SimpleSort) Ez a programilag legegyszerűbb rendezési algoritmus. Mindegyik elemet összehasonlítjuk az összes utána következő elemmel két egymásba ágyazott ciklus segítségével. Ha az éppen összehasonlított két elem nem jó sorrendben van, akkor azokat rögtön ki is cseréljük. Rendezés a legkisebb elem kiválasztásával (MinSort, SelectSort) A módszer lényege, hogy az i. helyre ( i = 1,2,3,... ) sorban kiválasztjuk az i...elemekszama helyen levõk közül a legkisebbet. Rendezés a szomszédos elemek cseréjével (BubbleSort) A módszer lényege, hogy egyesével végignézzük a szomszédos elemeket, és ha elõbb van a nagyobb, megcseréljük azokat. Így biztosan a legnagyobb helyre kerül a legnagyobb elem ("a buborék felszáll"). Ugyanezt sorban végrehajtjuk az utolsó elõtti elemig stb., egészen az elsõig. Ha közben kiderül, hogy a tömb rendezett, az eljárást befejezzük. Rendezés beszúrásos módszerrel (InsertSort) A módszer hasonlít a kártyák kézben való rendezéséhez. Mindig vesszük a
következõ elemet, s azt a megfelelõ helyre beszúrjuk úgy, hogy a többi, már rendezett elemet eggyel feljebb toljuk. Mindhárom rendezés pontos algoritmusa megtalálható az alábbi programban: program Pelda22; uses crt, dos; const elemekszama = 30000; var a,b:array [1..elemekszama] of integer; ido:longint; i:integer; procedure kiiras; var i:integer; begin for i:=1 to elemekszama do write(a[i],' '); writeln; writeln; end; procedure stopperbe; var t1,t2,t3,t4:word; begin gettime(t1,t2,t3,t4); ido:=t4+100*(t3+60*(t2+60*t1)); end; procedure stopperki; var t1,t2,t3,t4:word; begin gettime(t1,t2,t3,t4); ido:=t4+100*(t3+60*(t2+60*t1))-ido; end; { egyszeru rendezes } procedure simplesort; var i,j,x:integer; begin for i:=1 to elemekszama-1 do for j:=i+1 to elemekszama do if a[i]>a[j] then begin x:=a[i]; a[i]:=a[j]; a[j]:=x; end; end;
{ rendezes a legkisebb elem kivalasztasaval } procedure minsort; var i,j,min,x:integer; begin for i:=1 to elemekszama-1 do begin min:=i; for j:=i+1 to elemekszama do if a[j]
=1) and (not ok) do begin ok:=true; for j:=1 to i do if a[j]>a[j+1] then begin x:=a[j]; a[j]:=a[j+1]; a[j+1]:=x; ok:=false; end; dec(i); end; end; { rendezes beszurasos modszerrel } procedure insertsort; var i,j,x,ment:integer; begin for i:=2 to elemekszama do begin if a[i]
a[j+1]:=a[j]; until (j=1) or (a[j-1]<=ment); a[j]:=ment; end; end; end; { foprogram } begin clrscr; writeln(elemekszama,' drb. elem rendezese:'); writeln; randomize; for i:=1 to elemekszama do b[i]:=random(64000)-32000; { mindig a-t fogjuk rendezni, b-ben meghagyjuk a kigeneralt szamokat} a:=b; { rendezes } stopperbe; simplesort; stopperki; { kiiras } writeln('SimpleSort: ',ido,' szazadmasodperc'); a:=b; { rendezes } stopperbe; minsort; stopperki; { kiiras } writeln('MinSort: ',ido,' szazadmasodperc'); a:=b; { rendezes } stopperbe; bubblesort; stopperki; { kiiras } writeln('BubbleSort: ',ido,' szazadmasodperc'); a:=b; { rendezes } stopperbe; insertsort; stopperki; { kiiras } writeln('InsertSort: ',ido,' szazadmasodperc'); end. A rendezési algoritmusokat animációk segítségével bemutató program
letölthető itt:
rendalgo.exe 6 Rekurzió, quicksort • rekurzió • quicksort 6.1 Rekurzió Rekurzió az, amikor egy eljárás vagy függvény - közvetve vagy közvetlenül önmagát hívja. A végtelen rekurzió elkerülésére mindig szükségünk van egy feltételre, amely valamilyen lépésszám után leállítja a rekurziót. A következõ program eljárása ciklus helyett rekurziót alkalmaz adott számú csillag kirajzolására: program Pelda23; uses crt;
procedure csillagok(mennyi:integer); begin if mennyi>0 then begin write('*'); csillagok(mennyi-1); end; end; begin clrscr; csillagok(10); end. Az elv: adott számú csillagot úgy rajzolunk ki, hogy kirajzolunk egy csillagot, majd kirajzoljuk a maradékot. A mennyi paraméter azt jelzi, hogy mennyi csillagot kell még kirajzolni. A matematikában találkozhatunk rekurzív definíciókkal, pl. 0! (nulla faktoriális) értéke 1, n! pedig n*(n-1)!. Tehát egy szám faktoriálisát úgy számíthatjuk ki, hogy kiszámítjuk a nála eggyel kisebb szám faktoriálisát és megszorozzuk a számmal. A rekurzió véget ér, ha eljutunk a 0-hoz. Ez pascal programban így néz ki: program Pelda24; uses crt; var k:integer; function fakt(n:integer):longint; begin if n>0 then fakt:=n*fakt(n-1) else fakt:=1; end; begin clrscr; write('Kerek egy egesz szamot (0..12): '); readln(k); writeln(k,'! = ',fakt(k)); end. 6.2 Gyorsrendezés (QuickSort) A módszer lényege: Tekintsük a tömb középsõ elemét (felezzük a tömböt). Ez az elem az ú.n. pivot (vezérelem). Balról keressük meg azt az elsõ elemet, mely ennél nem kisebb, jobbról azt az elsõ elemet, amely ennél nem nagyobb. Cseréljük ki a két elemet, s folytassuk a cserélgetést egészen addig, amíg a bal oldalon a középsõ
elemnél (mely természetesen cserélõdhet menet közben) csupa nem nagyobb, jobb oldalon pedig csupa nem kisebb elem áll. Rekurzív hívással most rendezzük a tömb alsó és felsõ felét, majd ezeknek alsó és felsõ felét, és így tovább. A QuickSort-tal kiegészített rendezést bemutató program: program Pelda25; uses crt, dos; const elemekszama = 30000; var a,b:array [1..elemekszama] of integer; ido:longint; i:integer; procedure kiiras; var i:integer; begin for i:=1 to elemekszama do write(a[i],' '); writeln; writeln; end; procedure stopperbe; var t1,t2,t3,t4:word; begin gettime(t1,t2,t3,t4); ido:=t4+100*(t3+60*(t2+60*t1)); end; procedure stopperki; var t1,t2,t3,t4:word; begin gettime(t1,t2,t3,t4); ido:=t4+100*(t3+60*(t2+60*t1))-ido; end; { egyszeru rendezes } procedure simplesort; var i,j,x:integer; begin for i:=1 to elemekszama-1 do for j:=i+1 to elemekszama do if a[i]>a[j] then begin x:=a[i]; a[i]:=a[j]; a[j]:=x; end; end;
{ rendezes a legkisebb elem kivalasztasaval } procedure minsort; var i,j,min,x:integer; begin for i:=1 to elemekszama-1 do begin min:=i; for j:=i+1 to elemekszama do if a[j]=1) and (not ok) do begin ok:=true; for j:=1 to i do if a[j]>a[j+1] then begin x:=a[j]; a[j]:=a[j+1]; a[j+1]:=x; ok:=false; end; dec(i); end; end; { rendezes beszurasos modszerrel } procedure insertsort; var i,j,x,ment:integer; begin for i:=2 to elemekszama do begin if a[i]
dec(j); a[j+1]:=a[j]; until (j=1) or (a[j-1]<=ment); a[j]:=ment; end; end; end; { gyorsrendezes } procedure quicksort(bal,jobb:integer); var i,j,pivot,x:integer; begin i:=bal; j:=jobb; pivot:=a[(i+j) div 2]; while i<=j do begin while a[i]pivot do dec(j); if i<=j then begin x:=a[i]; a[i]:=a[j]; a[j]:=x; inc(i); dec(j); end; end; if bal<j then quicksort(bal,j); if i<jobb then quicksort(i,jobb); end; { foprogram } begin clrscr; writeln(elemekszama,' drb. elem rendezese:'); writeln; randomize; for i:=1 to elemekszama do b[i]:=random(64000)-32000; { mindig a-t fogjuk rendezni, b-ben meghagyjuk a kigeneralt szamokat} a:=b; { rendezes } stopperbe; simplesort; stopperki; { kiiras } writeln('SimpleSort: ',ido,' szazadmasodperc'); a:=b;
{ rendezes } stopperbe; minsort; stopperki; { kiiras } writeln('MinSort: ',ido,' szazadmasodperc'); a:=b; { rendezes } stopperbe; bubblesort; stopperki; { kiiras } writeln('BubbleSort: ',ido,' szazadmasodperc'); a:=b; { rendezes } stopperbe; insertsort; stopperki; { kiiras } writeln('InsertSort: ',ido,' szazadmasodperc'); a:=b; { rendezes } stopperbe; quicksort(1,elemekszama); stopperki; { kiiras } writeln('QuickSort: ',ido,' szazadmasodperc'); end. Rendezési algoritmusokat animációk segítségével bemutató program letölthető itt:
rendalgo.exe 7 Backtracking • • • •
a bactracking lényege néhány backtrackinggel megoldható feladat nyolc vezér probléma útvonal megkeresése a labirintusban
7.1 A backtracking technika lényege A programozásban a backtracking technika alatt a megoldástér szisztematikus bejárását értjük. A megoldás keresésekor elindulunk egy irányba, feltételezve, hogy az a jó irány. Ha valahol "zsákutcába" jutottunk, akkor visszalépegetünk addig a legközelebbi pontig, ahol tudunk más utat is választani és itt a rákövetkező (másik) úton megyünk tovább. A megvalósítás technikája általában rekurzió.
7.2 Néhány backtrackinggel megoldható feladat Nyolc vezér probléma: Helyezzünk el egy 8x8-as sakktáblán 8 vezért úgy, hogy azok ne üssék egymást! (Tehát helyezzük el a vezéreket úgy, hogy se egy sorban, se egy oszlopban, se átlósan ne legyen egy vonalban kettő.) Hányféleképpen lehetséges így elhelyezni a vezéreket? Labirintus: Adva van egy M*N-es labirintus, (1,1) a bejárat, (M,N) a kijárat. Keressünk egy utat a bejárattól a kijáratig. Sakk-huszár: Keressünk egy olyan huszárugrás-sorozatot, amely minden egyes pontot érint a sakktáblán pontosan egyszer, és ugyan oda tér vissza, ahonnan indult. 7.3 Nyolc vezér probléma A feladatunk tehát a következő: helyezzünk el egy 8x8-as sakktáblán 8 vezért úgy, hogy azok ne üssék egymást (tehát helyezzük el a vezéreket úgy, hogy se egy sorban, se egy oszlopban, se átlósan ne legyen egy vonalban kettő)! Általánosítva a feladatot: helyezzünk el egy NxN-es sakktáblán N vezért úgy, hogy azok ne üssék egymást! Az egyszerűség kedvéért mi most a 4x4-es sakktáblán fogjuk szemlélteni a megoldás megtalálásának a menetét. Az biztos, hogy minden oszlopban csak egy vezért helyezhetünk el, mivel egyébként a két vezér ütné egymást. Ezért megpróbáljuk mindegyik oszlopoban egymás után elhelyezni a vezéreket: • Az első vezért letesszük az első oszlop első sorába. • Majd a második oszlopba megpróbáljuk elhelyezni a vezért az első sortól haladva a negyedik sorig úgy, hogy az ne üsse az első oszlopban levő vezért. Ha sikerült, megyünk tovább a harmadik oszlopba; ha nem sikerült, akkor visszamegyünk az első oszlophoz és ott a vezért eggyel lejjebb tesszük. • Így haladunk tovább, amíg nem sikerül a negyedik oszlopba is lerakni a vezért. A feladat megoldása 4x4-es sakktáblán szemléltetve tehát lépésenként a következő:
1. Az első oszlopban letesszük az első helyre (1. sorba) a vezért, feltételezve, hogy ez a jó hely:
Majd megpróbáljuk a következő vezért lerakni a második oszlopba... 2. A második oszlop 1. és 2. sorába nem tehetünk vezért, mivel akkor ütné a már fent levőt (ábrán pirossal jelölve). A 3. sorba le lehet rakni a vezért, ezért letesszük oda, feltételezve hogy ez is a jó helyre került:
Majd megpróbáljuk a következő vezért lerakni a harmadik oszlopba... 3. A harmadik oszlopban sem az 1., 2., 3., sem a 4. helyre nem tehetünk vezért, mivel mindegyik helyen ütné valamelyik már eddig fent levő vezért:
Mivel így a harmadik oszlopba nem tudunk vezért tenni, ezért visszalépünk a második oszlopba és ott a vezért eggyel lejjebb tesszük (tehát a következő még nem kipróbált helyre):
Ezek után ismét megpróbáljuk lerani a vezért a harmadik oszlopba... 4. Most a harmadik oszlopban az 1. sorba nem tehetünk vezért (mivel ütné az első oszlopban levőt), de a 2. sorba már tehetünk, ezért kitesszük oda:
Majd megpróbáljuk a következő vezért lerakni a negyedik oszlopba... 5. A negyedik oszlopban nem tudunk az 1., 2., 3., de a 4. helyre sem tenni vezért, mivel ütné valamelyik már fent levőt:
Ezért visszalépünk a harmadik oszlopba és megpróbáljuk ott máshová (a sorra következő helyekre, tehát a 3., 4. sorba) tenni a vezért. Azonban itt sem tehetjük a vezért sem a 3., sem a 4. sorba, mivel akkor ütné az első két oszlopban levőket:
Ezért visszamegyünk a második oszlopba. Mivel itt már kipróbáltuk mind a négy helyet, ezért semmi mást nem tehetünk, mint hogy visszamegyünk
egészen az első oszlopba és ott tesszük a vezért eggyel lejjebb:
Majd megpróbáljuk a következő vezért ismét lerakni a második oszlopba... 6. Most a második oszlop 1., 2., 3. sorába nem rakhatjuk le a vezért, mivel akkor ütné az első oszlopban levőt. A 4. sorba azonban lerakhatjuk:
Majd megpróbáljuk a harmadik vezért lerakni a harmadik oszlopba... 7. A harmadik oszlop 1. sorába letehetünk vezért, ezért lerakjuk oda:
Majd megpróbáljuk a következő vezért lerakni a negyedik oszlopba... 8. A negyedik oszlop 1., 2. sorába nem tehetünk vezért, de a 3. sorba lerakhatjuk:
Mivel sikerült a negyedik oszlopban is leraknunk a vezért, ezért megtaláltuk a feladat egyik megoldását, így befejeződhet az algoritmus. :-) Ha az összes megoldást meg szeretnénk találni, akkor a megtalált megoldás után csak megjegyeznénk (esetleg kiírnánk) azt és mennénk tovább a keresésben. Tehát a fenti példában a negyedik oszlop 4. sorával folytatnánk a keresést, majd ismét visszalépnénk a harmadik oszlopoz. Hasonlóan folytatnánk mindaddig, amíg ki nem próbáltuk az összes lehetőséget. A backtracking technika előnye az, hogy ha például már a harmadik vagy a negyedik oszlopban nem tudunk továbblépni, akkor az utánnuk következő oszlopokban nem is próbáljuk lerakni a vezéreket. Így a programnak sokkal kisebb az időigénye, sokkal hamarabb lefut, tehát sokkal hamarabb eljutunk a megoldáshoz, mint ha kipróbáltuk volna négy egymásba ágyazott ciklus segítségével az összes lehetséges kombinációt (tehát ebben a példában a 4*4*4*4 kombinációt). NxN-es sakktáblán egy megoldás megkeresésének menetét backtracking technikával az alábbi program szemlélteti: vezer.pas Az összes megoldás megkeresésére szolgáló program szintén a backtracking technikát felhasználva: vezer2.pas 7.4 Útvonal megkeresése a labirintusban Írjunk egy programot, amely backtracking segítségével megkeresi az útvonalat a bejárattól a kijáratig az alábbi labirintusban:
Mielőtt nekiállnánk, gondoljuk át, hogy milyen adatszerkezet segítségével tudnánk ezt a labirintust ábrázolni a számítógépben. Jó megoldás lehet egy kétdimenziós tömb használata, mely a következő képpen nézne ki:
A mi esetünkben egy 10x10-es tömböt használnánk, melyben az egyes elemek értéke: • 0 jelöli a még nem bejárt útvonalakat (tehát ahová léphetünk), • 9 jelöli a falat (tehát ahová nem léphetünk), • 5 jelöli a célt (ha ide értünk, akkor megvan a megoldás).
Ezeken kívül a feladat megoldása közben még két értéket vehetnek fel a tömb elemei: • 1, amely az adott pontig bejárt, helyesnek tűnő útvonalat fogja jelölni, • 2, amely a mát bejárt, de zsákutcát (tehát nem a kijárathoz vezető) útvonalat fogja jelölni. A megoldás keresése a következő lesz: • Elindulunk a bejáratnál (10.sor, 2. mező) és ezt megjelöljük 1-essel. • Megnézzük, hogy mehetünk-e felfele (az adott hely feletti mező értéke 0 vagy 5). Ha mehetünk, akkor oda lépünk (tehát azt is bejelöljük 1-essel), majd innen próbálunk tovább lépni. Ha nem mehetünk, akkor hasonlóan megnézzük a jobbra, majd a balra, majd a lefele irányt és abba az irányba megyünk, ahol szabad az útvonal (tehát ahol a tömbben 0 vagy 5 van). • Ha valamelyik ponttól egyik irányban sem tudunk tovább lépni, akkor ezt a pontot bejelöljük 2-essel (zsákutca), majd visszalépünk az előző pontra, ahonnan próbálunk más irányba továbbmenni (vagy innen is visszalépni, ha nem vezet sehova). A megoldás menetének keresését az alábbi animáció szemlélteti:
Object 1
Az animációban az 1-es (zöld) jelöli a bejárt és helyes útvonalat, a 2-es (piros) pedig azokat a mezőket, amelyeken keresztül próbáltuk megkeresni a helyes útvonalat, de zsákutcába jutottunk (tehát ezekről vissza kellett lépnünk).
Végül nézzük meg a pascalban megírt programot, mely megkeresi a fenti labirintusban a helyes útvonalat az említett algoritmus szerint: program Pelda26; uses crt; var lab:array [1..10,1..10] of byte = ((9,9,9,9,9,9,9,9,9,9), (9,0,0,9,0,9,0,9,0,5), (9,0,9,9,0,9,0,9,0,9), (9,0,0,0,0,9,0,0,0,9), (9,9,0,9,9,9,9,9,0,9), (9,0,0,0,0,0,0,9,0,9), (9,0,9,9,9,0,9,0,0,9), (9,0,0,0,9,0,0,0,9,9), (9,0,9,0,9,0,9,0,0,9), (9,0,9,9,9,9,9,9,9,9)); procedure kiiras; var i,j:integer; begin for i:=1 to 10 do begin for j:=1 to 10 do case lab[i,j] of 9: begin {fal} textcolor(lightgray); write(#219); { #219 = befestett negyzet karakter } end; 0,5: write(' '); { ures vagy celpont } 1: begin { helyes utvonal } textcolor(lightgreen); write('X'); end; 2: begin { bejart, de rossz utvonal } textcolor(red); write('O'); end; end; writeln; end; writeln; end;
procedure lepes(x,y:integer); begin { nem ertunk be a celba? } if lab[x,y]<>5 then begin { lepes elore... } lab[x,y]:=1; { van felfele bejaratlan utvonal (ures vagy celpont)? } if (x>1) and (lab[x-1,y] in [0,5]) then lepes(x-1,y); { van jobbra bejaratlan utvonal (ures vagy celpont)? } if (y<10) and (lab[x,y+1] in [0,5]) then lepes(x,y+1); { van balra bejaratlan utvonal (ures vagy celpont)? } if (y>1) and (lab[x,y-1] in [0,5]) then lepes(x,y-1); { van lefele bejaratlan utvonal (ures vagy celpont)? } if (x<10) and (lab[x+1,y] in [0,5]) then lepes(x+1,y); { lepes vissza... megjeloles bejart, de rossz utvonalnak } lab[x,y]:=2; end else begin { celba ertunk, utolso lepes elore... } lab[x,y]:=1; { megtalalt utvonal kirajzolasa } kiiras; { utolso lepes vissza } lab[x,y]:=2; end; end; begin clrscr; { ures labirintus kirajzolasa } kiiras; { megoldas keresese, elso lepes: [10,2] } lepes(10,2); { magyarazat kiirasa } textcolor(lightgray); writeln(#219,' ... fal'); textcolor(red); write('O'); textcolor(lightgray); writeln(' ... bejart, de rossz utvonal'); textcolor(lightgreen); write('X'); textcolor(lightgray);
write(' ... helyes utvonal'); { varakozas egy billentyu megnyomasara } readkey; end. Az programban megfigyelhettük, hogy miután megtaláltuk a labirintusból kivezető útvonalat, kiírtuk azt a képernyőre, majd tovább folytatódott a keresés. Így tehát, amennyiben a labirintusnak több kijárata is lenne (a tömbben 5-ös számmal jelölve), megtalálnánk mindegyik kijárathoz a kivezető útvonalat. 8 Graph unit • grafikus ablak, wincrt unit • a graph unit eljárásai és függvényei • sin(x) függvény kirajzolása 8.1 Grafikus ablak, wincrt unit Eddig mindig csak szöveges módban dolgoztunk, melynek felbontása 80x25 karakter. Ahhoz, hogy tudjunk rajzolni is, mindenekelőtt inicializálnunk kell a grafikus képernyőt (módot). Windows alatt futó FreePascal-ban a grafika inicializálása után megjelnik egy új ablak, melybe rajzolhatunk. A grafika inicializálására szolgáló programunk a következőképpen néz ki: program Pelda27; uses graph, wincrt; var gd,gm: integer; begin {grafika inicializalasa} gd := d4bit; gm := m640x480; initgraph(gd,gm,''); {ha hiba tortent, akkor a program leallitasa} if graphresult<>grok then begin writeln('Hiba a grafika inicializalasanal.'); halt; end; {rajzolas} { ... } {grafikus mod bezarasa} readkey; closegraph;
end. Használnunk kell tehát a graph unitot (uses graph), melyben az összes grafikával kapcsolatos parancs megtalálható. A grafika inicializálásához szükségünk lesz két egész szám típusú változóra: gd és gm. Az egyikkel színmélységet (d4bit) a másikkal a grafikus felbontást (m640x480) adjuk meg. A grafikát az initgraph(gd,gm,''); paranccsal inicializáljuk. Ez után a parancs után, ha sikerült, megjelenik egy grafikus ablak. Az initgraph harmadik paramétereként megadhatjuk, hol található a grafikus driver (kiretjesztése bgi), ezt azonban csak akkor szükséges megadnunk ha a Borland Pascal-ét vagy egy sajátot használunk. Azt, hogy sikerült-e inicializálni a grafikát, a graphresult változó segítségével tudjuk leellenőrizni. A rajzolás után ne feledkezzünk meg a grafikus mód bezárásával (grafikus ablak bezárásával) visszatérni a szöveges módba. Erre szolgál a closegraph parancs. A programban használtuk még a wincrt unitot is. Ez a unit ugyanolyan nevű parancsokat tartalmaz, mint a crt unit parancsai, a különbség az, hogy a wincrt unitban található parancsok a grafikus ablakra vonatkoznak. A fenti példában a readkey utasítás végett volt rá szükségünk. Ez a parancs vár egy billentyű megnyomására a grafikus ablakban (ha a crt unitot használtuk volna, akkor a grafikus ablak mögött levő szöveges ablakban várna a billentyű megnyomására). A wincrt és a crt unitokat használhatjuk egy programon belül is. Ekkor ha pl. azt szeretnénk, hogy a programunk a szöveges módban levő ablakban várjon a billentyű megnyomására, akkor crt.readkey formában, ha a grafikus ablakban várja a billentyűleütést, akkor pedig wincrt.readkey forbában kellene használnunk. 8.2 A graph unit eljárásai és függvényei A graph unitban található néhány fontosabb parancs: initgraph(gd,gm,path) - grafika inicializálására szolgál closegraph - grafikus mód bezárása setcolor(szin) - segítségével beállíthatju a toll (vonal) színét. Színként megadhatunk 0 és 15 közötti számot vagy a szín angol nevét (pl. red, blue, green, yellow, white, black).
setbkcolor(szin) - a háttérszín beállítására szolgál értékei hasonlóak lehetnek, mint a setcolor parancsnál. setfillstyle(stilus,szin) - segítségével a kitöltés színét és stílusát adhatjuk meg. A színt hasonlóan adhatjuk meg, mint a setcolor parancsnál, stílusként pedig megadhatjuk a következő konstansok egyikét: EmptyFill SolidFill LineFill ltSlashFill SlashFill BkSlashFill LtBkSlashFill HatchFill Fills XHatchFill Fills InterLeaveFill WideDotFill CloseDotFill SetLineStyle (VonalStilus,Minta,Vastagsag) - ezzel a paranccsal beállíthatjuk, hogy milyen vonaltípussal szeretnénk rajzolni. A vonalstilus lehetséges értékei: Solidln = 0 Dottedln = 1 Centerln = 2 Dashedln = 3 UserBitln = 4 A mintának csak a UserBitln esetében van értelme, ekkor megadhatjuk a vonal mintáját bitek segítségével. A többi esetben ez a paraméter nincs figyelembe véve. A vonalvastagság az alábbi értékek egyike lehet: NormWidth = 1 ThickWidth = 3 settextjustify(horizontalis,vertikalis) - segítségével megadhatjuk, hogy a szöveg kiírásánál a koordináták a szöveg melyik részére vonatkozzanak. Alapbeállításként ez a szöveg bal felső sarka. Az első paraméter lehetséges értékei: LeftText = 0 CenterText = 1 RightText = 2
a második paraméter értékei lehetnek: BottomText = 0 CenterText = 1 TopText = 2 getcolor - segítségével megállapíthatjuk, milyen az éppen beállított szín. getbkcolor - megadja, milyen az éppen beállított háttérszín. getpixel(x,y) - megadja, milyen az X, Y koordinátájú pont színe. A grafikus módban alakzatok rajzolására szolgáló parancsok: line(x1,y1,x2,y2) - vonal [x1,y1] ponttól [x2,y2] pontig. lineto(x,y) - vonalat húz az előző ponttól (a toll helyétől) az [x,y] koordinátájú pontig. linerel(x,y) - vonalat húz az előző ponttól (a toll helyétől) egy olyan pontig, amely x-el jobbra és y-nal lejjebb van. moveto(x,y) - a tollat átteszi (vonal húzása nélkül) az [x,y] koordinátájú pontra. moverel(x,y) - a tollat átteszi (vonal húzása nélkül) egy olyan pontra, amely az előzőtől x-el jobbra és y-nal lejjebb van. circle(x,y,r) - [x,y] középpontú r sugarú kör rajzolása. rectangle(x1,y1,x2,y2) - téglalap rajzolása [x1,y1] ponttól [x2,y2] pontig. arc(x,y,szogkezd,szogvege,sugar) - körív rajzolására szolgáló parancs. ellipse(x,y,szogkezd,szogvege,xfeltengely,yfeltengely) - ellipszis vagy ellipszis ívének rajzolására szolgáló parancs. outtext(szoveg) - szöveg kiírása a toll koordinátáira. outtextxy(x,y,szoveg) - szöveg kiírása a megadott koordinátákra. putpixel(x,y,szin) - az [x,y] koordinátákra egy pont kirajzolása a megadott színnel. Kitöltött alakzatok rajzolására szolgáló parancsok: bar(x1,y1,x2,y2) - kitöltött téglalap.
fillellipse(x,y,xfeltengely,yfeltengely) - kitöltött ellipszis. floodfill(x,y,keretszin) - festték öntése az [x,y] koordinátájú pontra. A festék addig fog folyni minden irányba ettől a ponttól, amíg nem ér el keretszín színű pontig. cleardevice - grafikus képernyő letörlése. imagesize(x1,y1,x2,y2) - segítségével megállapíthatjuk a megadott koordinátájú kép méretét. Erre például akkor lehet szükségünk, ha a memóriában le szeretnénk foglalni egy ekkora területet és oda kimásolni a képet. getimage(x1,y1,x2,y2,bitmap) - kép másolása a grafikus képernyőről a memóriába. putimage(x1,y1,bitmap,hogyan) - kép kirajzolása az X, Y koordinátákra a memóriából. A hogyan paraméter megadja, miként szeretnénk a képet kirajzolni. Ennek lehetséges értékei: CopyPut XORPut ORPut AndPut NotPut 8.3 Sin(x) függvény kirajzolása Az alábbi példa szemlélteti, hogyan rajzolhatjunk ki a képernyőre a sin függvény grafikonját: program Pelda28; uses graph, wincrt; var gd,gm: integer; i:integer; function IntToStr(szam:integer):string; var szoveg:string; begin str(szam,szoveg); IntToStr:=szoveg; end; begin
{grafika inicializalasa} gd := d4bit; gm := m640x480; initgraph(gd,gm,''); {ha hiba tortent, akkor a program leallitasa} if graphresult<>grok then begin writeln('Hiba a grafika inicializalasanal.'); halt; end; {tengelyek kirajzolasa} setcolor(blue); line(100,50,100,350); line(100,200,500,200); settextjustify(centertext,toptext); for i:=1 to 4 do begin line(90*i+100,198,90*i+100,202); outtextxy(90*i+100,205,IntToStr(i*90)); end; settextjustify(righttext,centertext); for i:=-1 to 1 do begin line(98,90*i+200,102,90*i+200); outtextxy(95,90*i+200,IntToStr(-i)) end; {sin(x) kirajzolasa} setcolor(yellow); moveto(100,200); for i:=0 to 360 do lineto(i+100,trunc(sin(i*PI/180)*90+200)); {grafikus mod bezarasa} readkey; closegraph; end. Végezetül gyakorlásképpen érdemes még letöltenünk és átnéznünk egy analóg óra kirajzolását és animálását megvalósító programot. Az óra mutatóit úgy mozgatjuk a programban, hogy azt mindig fekete színnel átrajzoljuk, majd kirajzoljuk az új helyre:
ora.pas 9 Kép mozgatása • • • • •
pointer típus getmem, freemem eljárások getimage, putimage eljárások kép másolása kép mozgatása a kurzorbillentyűk segítségével
9.1 Pointer típus A pointer (mutató) típusú változó egy olyan változó, amely egy memóriacímre mutat. A pointer típusnak lefoglalt memória mérete mindössze 4 byte, ez a 4 byte tartalmazza azt a memóriacímet, ahová a pointer mutat. 9.2 Getmem, freemem eljárások A programunkban lefoglalhatunk a memóriából egy tetszőleges méretű szabad területet, használhatjuk azt, majd később felszabadíthatjuk. A memória lefoglalását a getmem parancs segítségével végezhetjük el. Például: getmem(p,1024); A fenti példa segítségével lefoglahatunk a memóriából 1024 bájtot (tehát 1 kBot). Ezt a méretet adjuk meg a getmem második paraméterében. Az első paraméter egy pointer típusú változó - a getmem ebbe a pointerbe állítja be a lefoglalt terület elejének a memóriacímét (tehát a példánkban az 1024 bájtnyi terület elejét). Így ennek a pointernek a segítségével tudunk majd a lefoglalt területre hivatkozni és dolgozni vele. Amikor már nincs szükségünk a lefoglalt területre, illik azt felszabadítani, hogy ne maradjon lefoglalva a programunk futása után is. A memória felszabadítását a freemem paracs segítségével végezhetjük el. Pédául: freemem(p,1024); A freemem parancs első paramétereként meg kell adnunk egy pointer típusú változót, amely a lefoglalt terület elejére mutat. Második paraméterként megadjuk, hogy attól a memóriacímtől kezdődően, ahová a pointer mutat, mennyi bájtnyi területet szeretnénk felszabadítani. Ügyeljünk arra, hogy ez ugyanannyi legyen, mint amennyit lefoglaltunk!
9.3 Getimage, putimage eljárások A getimage és putimage parancsok segítségével a grafikus képernyőn levő ábra egy részét (vagy akár az egészet) átmásolhatjuk a memóriába, majd visszahelyezhetjük a grafikus képernyőre. Ahhoz, hogy ezt megtehessük először le kell foglalnuk számára a szükséges memóriát a getmem parancs segítségével. Egy kép másolása tehát a következő fő lépésekből fog állni: 1. Memória lefoglalása a kép mentéséhez. Ehhez szükséges egy pointer (p) ami a lefoglalt terület elejére mutat. Azt, hogy mennyi memóriaterületre van szükségünk, attól függ, mekkora képet szeretnénk a memóriában tárolni. Szerencsére a kép méretéből a szükséges memóriaterület kiszámítására létezik a pascalban egy függvény: imagesize. Ennek a függvénynek négy paramétere van, az első kettő az elmentendő kép (téglalap) bal felső sarkának a koordinátái, a második kettő pedig a jobb alsó sarkának koordinátái. Ha tehát el szeretnénk menteni a memóriába a grafikus képernyő 10,10,160,160 részét (tehát egy 150x150-es négyzetnyi területet), akkor a memóriát a következő paranccsal foglalhatjuk le neki: getmem(p,imagesize(10,10,160,160)); 2. Ezek után a képet elmenthetjük a memóriába a p pointertől kezdődően az alábbi parancs segítségével: getimage(10,10,160,160,p^); Itt az első négy paraméter a kép koordinátáit adja meg (bal felső, jobb alsó sarok). Az ötödik paraméter az a terület a memóriában, ahová a képet szeretnénk menteni. Itt megfigyelhetjük, hogy nem p-t, hanem p^-t adtunk meg. Ez azért van, mert a p az maga a pointer, a p^ viszont már az a memóriaterület, ahová a pointer mutat. Mi most a képet arra a területre akarjuk menteni, ahová a pointer mutat (ennek mérete pontosan akkora mint a kép mérete - imagesize(10,10,160,160)), nem arra a memóriaterületre, ahol a pointer van a memóriában (ennek ugyanis a területe csupán 4 bájt - a lefoglalt terület memóriacímét tartalmazza - ide a 4 bájtnyi helyre nem is férne be). 3. A memóriából a képet a grafikus képernyőre visszarakhatjuk bármennyiszer a következő parancs segítségével:
putimage(200,10,p^,copyput); Az első két paraméter adja meg a kép bal felső koordinátáját. Ebben az esetben tehát a kép a 200,10 koordinátától kezdődően lesz kirakva a képernyőre. A harmadik paraméter a memória azon területét jelöli, ahol a képünk van (hasonlóan a getimage-hoz). A negyedik paraméter pedig a kirajzolás módját jelöli. Ez utóbbinak főleg akkor van látszatja a képernyőn, ha a kirakandó kép alatt már van valamilyen rajz. A mi esetünkben a copyput egyszerűen a már képernyőn levő rajz fölé teszi a mi rajzunkat úgy, hogy az alatta levő rajz eltűnik. A copyput helyett kipróbálhatjuk még az orput, andput, xorput, notput konstansokat is. 4. Miután már nincs szükségünk a lefoglalt memóriára, a program végén illik azt felszabadítani: freemem(p,imagesize(10,10,160,160)); 9.4 Kép másolása Az alábbi példa kirajzol egy mosolygós fejet a képernyőre, majd azt az előbb említett parancsok segítségével lemásolja 12-szer a képernyőre. program Pelda29; uses graph, wincrt; var gd,gm,i,j: integer; p:pointer; begin { grafika inicializalasa } gd := d4bit; gm := m640x480; initgraph(gd,gm,''); { rajzolas } setcolor(brown); circle(50,50,40); setfillstyle(SolidFill,yellow); floodfill(50,20,brown); circle(40,50,10); circle(60,50,10); setfillstyle(SolidFill,white); floodfill(40,45,brown); floodfill(60,45,brown); setcolor(black);
circle(40,53,5); circle(60,53,5); setfillstyle(SolidFill,black); floodfill(40,53,black); floodfill(60,53,black); setcolor(red); arc(50,50,210,330,30); { memoria lefoglalasa } getmem(p,imagesize(0,0,100,100)); { kep megjegyzese } getimage(0,0,100,100,p^); { kep kirajzolasa 12-szer } for i:=1 to 4 do for j:=1 to 3 do putimage(i*100,j*100,p^,copyput); { memoria felszabaditasa } freemem(p,imagesize(0,0,100,100)); { varakozas gombnyomasra } readkey; { grafikus mod bezarasa } closegraph; end. 9.5 Kép mozgatása a kurzorbillentyűk segítségével A következő példa szintén kirajzolja a mosolygós fejet, de azt most mindig csak a megadott X,Y koordinátákra rajzolja ki, ami attól függően fog változni, hogy melyik kurzorbillentyűt (nyilat) nyomtuk meg. Így tehát úgy fog tűnni, mintha a fejet a kurzorbillentyűk segítségével mozgatnánk a képernyőn. program Pelda30; uses graph, wincrt; var gd,gm,i,j: integer; p:pointer; x,y:integer; ch:char; begin x := 0; y := 0; { grafika inicializalasa } gd := d4bit; gm := m640x480; initgraph(gd,gm,'');
{ rajzolas } setcolor(brown); circle(50,50,40); setfillstyle(SolidFill,yellow); floodfill(50,20,brown); circle(40,50,10); circle(60,50,10); setfillstyle(SolidFill,white); floodfill(40,45,brown); floodfill(60,45,brown); setcolor(black); circle(40,53,5); circle(60,53,5); setfillstyle(SolidFill,black); floodfill(40,53,black); floodfill(60,53,black); setcolor(red); arc(50,50,210,330,30); { memoria lefoglalasa } getmem(p,imagesize(0,0,100,100)); { kep megjegyzese } getimage(0,0,100,100,p^); { kep mozgatasa a kurzorbillentyuk segitsegevel } repeat ch := readkey; if ch=#0 then begin ch := readkey; case ch of #72: if y-5>=0 then y:=y-5; {fel} #80: if y+5<=379 then y:=y+5; {le} #75: if x-5>=0 then x:=x-5; {balra} #77: if x+5<=539 then x:=x+5; {jobbra} end; putimage(x,y,p^,copyput); end; until ch=#27; { memoria felszabaditasa } freemem(p,imagesize(0,0,100,100)); { grafikus mod bezarasa }
closegraph; end. A kurzorbillentyűk megnyomásakor mindig két kódot kapunk. Először a #0-t, majd a #72, #80, #75, ill. #77-et attól függően melyik billentyűt nyomtuk meg (fel, le, balra, jobbra). Ezeket használjuk fel az új koordináták kiszámításához. A fejet mindig 5 pixellel rakjuk arrébb. Az eredeti képet nem kell letörölnünk, mivel az új kép felülrajzolja azt. Az eredeti kép szélein (5 képpontnyi sáv, amit nem rajzol felül) csak fekete rész van, így nem fog az új kép alól kilógni az előtte kirajzolt kép. 10 WinMouse unit • a winmouse modul használata • kitöltés egérkattintásra véletlenszerű színnel 10.1 A winmouse modul használata A FreePascal windows alatt futó verziójában létezik egy standard modul - a winmouse unit - egérkezelésre. Ha használni szeretnénk a programunkban, mindenekelőtt ki kell egészítenünk programunk uses részét ezzel a winmouse modullal. Ezek után a program elején az egeret inicializálnunk kell az initmouse paranccsal. Ha ezt megtettük, használhatjuk a következő függvényeket és eljárásokat: • lpressed - akkor ad vissza igaz (true) értéket, ha a felhasználó lenyomta a bal (left) egérgombot, • mpressed - akkor ad vissza igaz (true) értéket, ha a felhasználó lenyomta a középső (middle) egérgombot, • rpressed - akkor ad vissza igaz (true) értéket, ha a felhasználó lenyomta a jobb (right) egérgombot, • getmousestate(mposx,mposy,state) - az egér állapotát (kurzor pozícióját és az egérgombok helyzetét) kérhetjük le a segítségével. A parancs kiadásának pillanatában az egérkurzor koordinátái bekerülnek az mposx, mposy változókba. A state változóba az egérengombok helyzete kerül be. Mindhárom változót longint típusúnak kell deklarálnunk. A harmadik, state paraméter első bitje adja meg a bal egérgomb helyzetét (0 - felengedve, 1 - lenyomva), a második bitje a jobb egérgomb helyzetét (0 felengedve, 1 - lenyomva) és a harmadik bitje a középső egérgomb helyzetét
(0 - felengedve, 1 - lenyomva). A programunkban az alábbi feltételek segítségével tudjuk őket ellenőrni: If (State and LButton) = LButton Then ... { ha a bal egergomb le van nyomva } If (State and RButton) = RButton Then ... { ha a jobb egergomb le van nyomva } If (State and MButton) = MButton Then ... { ha a középső egergomb le van nyomva } Az LButton, RButton és MButton a wincrt unitban definiált konstansok, ezért ezeket nem kell a programunkban külön deklarálnunk. Értékeik a következő képpen vannak definiálva: LButton = 1 RButton = 2 MButton = 4 10.2 Kitöltés egérkattintásra véletlenszerű színnel Az alábbi példa szemlélteti az egér használatát a grafikus ablakban. A példában kirajzolunk fehér színnel 10 körvonalat véletlenszerű sugárral és hellyel. Ha az egérrel valamelyik rész belsejébe kattintunk (tehát az egér alatti szín nem fehér, vagyis kisebb mint 15), akkor az egér koordinátáira kiöntünk egy véletlenszerűen kiválasztott színt 1-től 14-ig. Ezzel valójában befestjük azt a részt, ahová az egérrel kattintottunk. program Pelda31; uses graph, wincrt, winmouse; var gd,gm: integer; ch:char; i:integer; mposx, mposy, state: longint; begin gd := d4bit; gm := m640x480; initgraph(gd,gm,''); initmouse;
randomize; for i:=1 to 10 do circle(random(640),random(480),150); repeat if keypressed then ch:= readkey; if lpressed then begin repeat until not lpressed; getmousestate(mposx,mposy,state); if getpixel(mposx,mposy)<15 then begin setfillstyle(solidfill,random(14)+1); floodfill(mposx,mposy,15); end; end; until ch = #27; closegraph; end. Figyelhetjük meg a forráskódban a bal egérgomb lenyomását tesztelő feltételt: ha megnyomtuk az egér bal gombját (if lpressed then), akkor egy ciklus segítségével teszteljük az egeret mindaddig, amíg nem engedjük fel (repeat until not lpressed). Ezzel valójában várunk az egérgomb felengedésére és csak utána festjük ki a kiválasztott részt véletlenszerű színre. 11 Dinamikus adatszerkezetek - egyirányú láncolt lista • egy elem létrehozása, használata és felszabadítása • egyirányú láncolt lista
11.1 Egy elem létrehozása, használata és felszabadítása Dinamikus adatszerkezeteket főleg akkor érdemes használnunk (például tömb helyett), ha nem tudjuk előre meghatározni mennyi elemünk lesz. Másik nagy előnye, hogy mindig csak annyi memória van lefoglalva, amennyire szükségünk van. A memóriát a program futása alatt foglaljuk le és szabadítjuk fel, amikor új elemet hozunk létre vagy elemet törlünk ki. A dinamikus adatszerkezeteket nagyon jól használhatók bináris fák, gráfok tárolására, ábrázolására is a számítógépben.
A dinamikus adatszerkezeteknél mindenekelőtt definiálnunk kell egy elemtípust a type kulcsszó segítségével. Itt mindjárt definiálhatunk egy pointer (mutató) típust is, amely egy ilyen elemre fog mutatni. Pl.: type PElem = ^Elem; { a PTElem egy mutato, ami Elem tipusra mutat } Elem = record { Elem tipus definialasa } szam: integer; kov: PElem; end; Ezek után már csak deklarálnunk kell néhány ilyen pointert, pl.: var p: PElem; Majd kezdődhet a program fő része. Alapértelmezett értékben, amíg a p pointer nem mutat semmilyen memóriaterületre sem, az értéke nil. Később ezt az értéket fogjuk hozzárendelni akkor is, ha például törölünk egy elemet és azt szeretnénk, hogy valamilyen mutató már ne mutasson sehová sem a memóriában. Új elemnek a new parancs segítségével foglalhatunk le szabad memóriarészt: new(p); A new parancs lefoglalja a szükséges memóriaterületet, majd a p pointerbe berakja ennek a memóriaterületnek a címét. A memória lefoglalása után a lefoglalt elem egyes részeit (pl. szam) a következő képpen olvashatjuk be vagy írhatjuk ki: readln(p^.szam); writeln(p^.szam); Megfigyelhetjük, hogy itt már nem p-t, hanem p^-t használunk. Ennek oka, hogy nem a p pointert akarjuk beolvasni vagy kiírni, hanem a p pointer által mutatott memóriaterületnek (p^) a "szam" részét (a p pointernek nincs szám része, az csak egy 4 bájtnyi memóriaterület, amely egy memóriacímet tartalmaz). Ha már nincs szükségünk a lefoglalt memóriaterületre, akkor a program végén illik azt felszabadítani. Ezt a dispose parancs segítségével tehetjük meg, amely ellentettje a new parancsnak: dispose(p); 11.2 Egyirányú láncolt lista A következő interaktív animáció bemutatja az egyirányú láncolt listát:
Object 2
Az alábbi példaprogram egy egyirányú láncolt lista kialakítását szemlélteti. A láncolt listában egész számokat tárolunk. A program addig olvas be egész számok, amíg nem adunk meg számként 0-t. Ha nem 0-t adtunk meg, lefoglaljuk az új elemnek a memóriát, majd beírjuk a "szam" részébe a beolvasott egész számot (uj^.szam:=a), beállítjuk, hogy ez után az elem után még nincs következő elem (uj^.kov:=nil), majd beállítjuk az első mutatót (elso:=uj) erre az elemre (ha ez az első elemünk), vagy az utolsó elem következőjét (utolso^.kov:=uj) erre az elemre (ha már van elemünk a listában). Végül beállítjuk, hogy a lista utolsó eleme a most létrehozott új elem (utolso:=uj). program Pelda32; uses crt; type PElem = ^Elem; { a PTElem egy mutato, ami Elem tipusra mutat } Elem = record { Elem tipus definialasa } szam: integer; kov: PElem; end; var a: integer; uj,akt,elso,utolso: PElem; begin clrscr; {beolvasas} repeat writeln('Kerek egy szamot (0-bevitel vege):'); readln(a); if a>0 then begin new(uj); uj^.szam:=a; uj^.kov:=nil; if elso=nil then elso:=uj else utolso^.kov:=uj;
utolso:=uj; end; until a=0; writeln; {kiiras} akt:=elso; while akt<>nil do begin write(akt^.szam,','); akt:=akt^.kov; end; writeln; {memoria felszabaditasa} akt:=elso; while akt<>nil do begin elso:=akt^.kov; dispose(akt); akt:=elso; end; end. A beolvasás után beállítottuk az akt mutató értékét az első elemre, majd egy ciklus segítségével kiírtuk az aktuális elemet és az akt mutatót beállítottuk a következő elemre. Ezt mindaddig elvégeztük, amíg az akt értéke nem nil, vagyis amíg nem írtuk ki az összes elemet. A memória felszabadítása a program végén szintén egy ciklus segítségével történik. Az egyirányú láncolt lista segítségével ki tudunk alakítani sort vagy vermet. A sor kialakítása során a memóriában létrejövő dinamikus adatszerkezetet (mely valójában egyirányú láncolt lista) szemlélteti az alábbi interaktív animáció:
Object 3
A verem kialakítását mutatja be a következő interaktív animáció:
Object 4
Az alábbi alkalmazás segítségével kipróbálhatjuk a dinamikus adatszerkezeteknél használt parancsokat, miközben megfigyelhetjük milyen folyamat megy végbe a memóriában:
Object 5
A fenti alkalmazás segítségével próbáljunk meg kialakítani pl. egy egyirányú láncolt listát.
12 Dinamikus adatszerkezetek - egyirányú rendezett lista • egyirányú rendezett láncolt lista 12.1 Egyirányú rendezett láncolt lista A következő példában egy rendezett egyirányú láncolt listát alakítunk ki. A lista mindegyik eleme tartalmazza egy személy nevét, születési évét és egy mutatót a lista következő elemére. A listát úgy alakítjuk ki, hogy az mindig rendezett legyen a nevek szerint. Tehát az új elemet mindig a lista megfelelő helyére szúrjuk be. program Pelda33; { egyiranyu rendezett lancolt lista } uses crt; type PTElem = ^TElem; { a PTElem egy mutato, ami TElem tipusra mutat } TElem = record { TElem tipus definialasa } nev: String; szev: Integer; kov: PTElem; end; var elso,akt,uj: PTElem; i,x: integer; begin clrscr; write('Mennyi elemet akarsz megadni? '); readln(x); { elemek megadasa } for i:=1 to x do begin writeln; new(uj); write(i:2,'. Nev: '); readln(uj^.nev); write(' Szuletesi ev: '); readln(uj^.szev); uj^.kov := nil; if elso=nil then elso := uj { elso elem } else begin { mar van elso } akt := elso;
if uj^.nevnil) and (akt^.kov^.nev<=uj^.nev) do akt := akt^.kov; { majd a megfelelo helyre beszurjuk } uj^.kov := akt^.kov; akt^.kov := uj; end; end; end; writeln; { elemek kiirasa } akt := elso; while akt<>nil do begin writeln(akt^.nev:10,akt^.szev:5); akt := akt^.kov; end; { memoria felszabaditasa } akt := elso; while akt<>nil do begin elso := akt^.kov; dispose(akt); akt := elso; end; readkey; end. 13 Dinamikus adatszerkezetek - kétirányú rendezett láncolt • kétirányú rendezett láncolt lista 13.1. Kétirányú rendezett láncolt lista Az alábbi animáció szemlélteti a kétirányú (nem rendezett) láncolt listát. A kétirányú láncolt listában nem csak mindegyik elem mutat a következő elemre (ahogy az egyirányú láncolt listában volt), de mindegyik elem tartalmaz egy
mutatót az előtte levő elemre is. Így a mutatókkal nem csak a következő elemekre, de az előző elemekre is tudunk ugrani az nélkül, hogy az elejétől végig kéne járnunk a listát.
Object 6
A következő példában egy rendezett kétirányú láncolt listát alakítunk ki. A lista mindegyik eleme tartalmazza egy személy nevét, születési évét, egy mutatót a lista következő elemére és egy mutatót a lista előző elemére. A listát úgy alakítjuk ki, hogy az mindig rendezett legyen a nevek szerint. Tehát az új elemet mindig a lista megfelelő helyére szúrjuk be. Ebben a programban a beolvasás után kiírjuk az elemeket, majd beolvasunk egy nevet a listából. A beolvasott nevet megkeressük a listában és kitöröljük onnan (ha létezik). A törlés után újból kiírjuk a lista összes elemét. A program végén az előző programhoz hasonlóan felszabadítjuk a lefoglalt memóriát egy ciklus segítségével. program Pelda34; { ketiranyu lancolt lista } uses crt; type PTElem = ^TElem; { PTElem egy mutato, ami TElem tipusra mutat } TElem = record { TElem tipus definialasa } nev: String; szev: Integer; elo,kov: PTElem; end; var elso,akt,uj: PTElem; i,x: integer;
s: string; begin clrscr; write('Mennyi elemet akarsz megadni? '); readln(x); { elemek megadasa } for i:=1 to x do begin writeln; new(uj); write(i:2,'. Nev: '); readln(uj^.nev); write(' Szuletesi ev: '); readln(uj^.szev); uj^.elo := nil; uj^.kov := nil; if elso=nil then elso := uj { elso elem } else begin { mar van elso } akt := elso; if uj^.nevnil) and (akt^.kov^.nev<=uj^.nev) do akt := akt^.kov; { majd a megfelelo helyre beszurjuk } uj^.kov := akt^.kov; uj^.elo := akt; akt^.kov := uj; uj^.kov^.elo := uj; end;
end; end; { elemek kiirasa } writeln; akt := elso; while akt<>nil do begin writeln(akt^.nev:10,akt^.szev:5); akt := akt^.kov; end; { elem torlese } writeln; write('Melyik nevet szeretned torolni? '); readln(s); akt := elso; while (akt<>nil) and (akt^.nev<>s) do akt:=akt^.kov; if akt=nil then writeln('Nincs ilyen nev!') else begin if akt^.elo<>nil then akt^.elo^.kov := akt^.kov else elso := akt^.kov; if akt^.kov<>nil then akt^.kov^.elo := akt^.elo; dispose(akt); end; { elemek kiirasa } writeln; akt := elso; while akt<>nil do begin writeln(akt^.nev:10,akt^.szev:5); akt := akt^.kov; end; { memoria felszabaditasa } akt := elso; while akt<>nil do
begin elso := akt^.kov; dispose(akt); akt := elso; end; readkey; end.
