Programozás | Programozás-elmélet » Fábián Zoltán - BMF-NIK szoftver szigorlat

1. oldal, összesen: 66 Szoftver Szigorlat by UFO BMF-NIK, 3. félév (2005) 1. Moduláris programozás Eljárások, függvények Láthatóság, élettartam, lokalitás, globalitás, mellékhatás. Paraméteradás A Unitok Delphiben minden formhoz szükségszerűen egy unit is tartozik, de egy unithoz nem feltétlenül kell formnak tartoznia. A unitok használata a strukturálhatóság szempontjából fontos, hiszen az egy adott feladatrész megoldását szolgáló programelemek ilyen módon különválaszthatók a főprogramtól. Deklarációja: unit unit név; A unit nevének nem kell kötelezően megegyeznie áttekinthetőség szempontjából. Módja: uses unit2 in „C: ufo.pas”; (relatív: \) a fájl nevével, de előnyös az Részei INTERFACE Itt definiálhatjuk azt, amit más programrészek is láthatnak. Az itt nem definiált részek csak az adott unit számára elérhetők. Itt lehet megadni azt is, hogy melyik más unitok tartalmát akarjuk használni. (uses) Az

interface deklarációs részében a mások számára is látható típus-, változó-, konstans- és címkedeklarációkat kell megadnunk, továbbá a globális metódusfejeket kell felsorolnunk. IMPLEMENTATION Itt kell a unitot alkotó eljárásokat, függvényeket leírnunk. Ezek közül kifelé csak azok láthatók, amelyeket az interface után felsoroltunk. (az eljárás- és függvényfejeket) Körkörös hivatkozás esetén ide kell írni a második unit uses részét. Itt kell megvalósítani a globális és a lokális metódusokat egyaránt. INITIALIZATION Inicializálás: például alaphelyzetbe hozza a változókat, vagy a dinamikusakat létrehozza, stb. A unitok initialization része abban a sorrendben hajtódik végre, ahogyan a uses után felsoroltuk őket. FINALIZATION Véglegesítés: felszabadítjuk végrehajtása fordított. a lefoglalt erőforrásokat. A finalization részek Az inicializációs és a lezáró rész elhagyható. Ha nincs lezáró rész, akkor

az initialization helyett begin is használható. Ha mindkét részt elhagyjuk, akkor az ’end’ utasítás az implementációs részt zárja. A modul inicializációja csak egyszer történik meg, függetlenül attól, hogy hányszor szerepel a modul neve a különböző uses hivatkozásokban. * Unit unitnév; Interface Uses modullista; Const konstansdefiníciók; Type típusdeklarációk; Var változódeklarációk; {Globális eljárások és függvények fejlécei} implementation Uses modullista; Label cimkelista; Const konstansdefiníciók; Type típusdeklarációk; Var változódeklarációk; {Globális és lokális metódusok törzse} initialization {Pascal utasítások} finalization {Pascal utasítások} end. 2. oldal, összesen: 66 Eljárások, Függvények Az eljárás deklarálása a procedure kulcsszóval indul, amelyet az azonosító (név) követ. A név után zárójelben paraméter(ek) is megadható(k). Az eljárás feje után a belső (lokális) változók,

típusok, konstansok és címkék felsorolása következik (de nem biztos, hogy vannak). Az utasításokat begin és end; között kell felsorolni, a záró end után is pontosvesszőt kell tenni. A függvény abban különbözik az eljárástól, hogy értéket (de csak egy értéket) ad vissza. Deklarálása a function kulcsszóval indul, amelyet az azonosító (név), a paraméterek és az eredmény típusának deklarálása követ. Az utasításblokkban adjuk meg a végrehajtandó utasításokat. A függvényt az azonosítóval kell hívni, a paraméterek típusának és sorrendjének egyeznie kell. A következő példa tetszőleges kitevőjű hatványozásra alkalmas függvényt mutat be: function Hatvany(alap,kitevo: Double):Double; begin Hatvany:=Exp(kitevo*ln(alap)); end; Hívása: Eredmeny:=2.85*hatvany(szam,4); A Paraméterek típusai ÉRTÉK SZERINTI (változó: integer) • Az eljárás létrehoz egy segédváltozót és belemásolja a paraméterként kapott értéket

(stack overflow lehetséges) • Az eredeti változó értékét csak felhasználni tudja, módosítani nem (a segédváltozót módosíthatja) • A másolás miatt nagy adatmennyiség esetén lassú • Az eljárás végeztével felszabadul a lefoglalt erőforrás • Hatóköréből a segédváltozó nem jut ki (csak itt látható) CÍM SZERINTI (var változó: integer) • Megkapja a változó címét, így közvetlenül annak értékével dolgozhat • Hatékonyabb, hiszen nincs adatmásolás • Hátránya, hogy az eljáráson belül megváltoztatható a cím szerint kapott paraméter értéke KONSTANS TÍPUSÚ (const változó: integer) • Az érték szerintinek megfelelő paraméterátadás, azzal a különbséggel, hogy a segédváltozó értéke az eljáráson belül nem változhat meg. • Ha ezen az eljáráson belül egy másikat hívunk meg, annak is konstans típusúnak kell lennie KIMENŐ (out változó: típus) • Az eljáráson belül kap értéket a változó •

Ezért változóval kell hívni, hogy abba másolhassa a belül kapott értéket TÍPUS NÉLKÜLI (const/var/out változó) • Csak const/var/out esetén használható, érték szerintinél nem • Ennek segítségével nem kell különböző típusú változókra külön eljárásokat írni (néha átláthatóbb így) Lokalitás, Globalitás Az alprogramok lokális deklarációs részében az eljárásban felhasználni kívánt címkéket, konstansokat, típusokat, változókat és alprogramokat deklarálhatjuk. A lokális deklarációs rész az eljárás fejléce és a törzse között helyezkedik el. A lokálisan deklarált azonosítók az eljáráson kívülről nem érhetők el. A lokális változók csak az eljárás hívásakor jönnek létre, és meghalnak, ha az eljárás visszatér a hívó programhoz. A legtöbb programnyelv az ilyen jellegű objektumait egy speciálisan kezelt adatterületen, a veremben (stack) tárolja. Ezzel szemben a főprogram szintjén létrehozott

változók a program adatterületén helyezkednek el, és statikus élettartamúak. Ezek a változók a program indításakor jönnek létre, és csak a programból való kilépéskor semmisülnek meg. (globálisak) Mellékhatás Egy globális változó mindenütt látszik, így értékét meg is tudjuk változtatni. A változók deklarálása csak az adott blokkon belül, valamint minden, az adott blokkon belül lévő blokkban érvényes. Ha a változót újra deklaráljuk, a külső blokkbeli deklarációtól eltérően, akkor a változó a belső blokkban az új deklarációnak megfelelő 3. oldal, összesen: 66 típust veszi fel, új, lokális változóként viselkedik. A belső blokk befejezésével, a külső blokkba visszatérve, a változó ismét a külső blokkban meghatározott deklarációnak megfelelő lesz. A változók élettartama A változók élettartama szoros kapcsolatban van a blokkszerkezettel. Egy változó akkor jön létre, amikor a programunk belép a

változót definiáló blokkba. A blokkból való kilépéskor a változó megsemmisül. Legtovább a főprogram szintjén definiált változók élnek Az Object Pascalban lokálisan elérhető, de globális élettartamú változókat is létrehozhatunk. Az ilyen objektumokat az alprogramban típusos konstansként kell deklarálni. Láthatóság Az azonosítók érvényességi tartománya (láthatósága) a program azon részeit jelöli, ahonnan elérhetjük az azonosítóval jelölt objektumot. Szabályok: - minden azonosítót a felhasználás helye előtt deklarálni kell - Egy azonosító érvényességi tartománya arra a blokkra terjed ki, amelyben az azonosítót deklaráltuk - Egy blokkon belül minden objektumot egyedi azonosítóval kell ellátni - Ugyanazzal a névvel különböző blokkokban különböző objektumokat deklarálhatunk - Ha a saját készítésű alprogram neve megegyezik valamelyik szabványos alprogram nevével, akkor a szabványos eljárás

elérhetetlenné válik abból a blokkból, amelyik a saját alprogram definícióját tartalmazza. A szabványos függvények mindig elérhetők, ha nevük előtt a System előtagot használjuk: y:=System.sin(pi/3) Megjegyzendő: attól, hogy a változó él, még nem biztos, hogy látszik is. 2. A programkészítés folyamata Programkészítési elvek és tervezési megfontolások Hibakezelési technikák (hagyományos és kivétel-kezeléses) A programok csoportosítása A program készítésének lépései • Specifikáció: a megoldandó feladat meghatározása papíron (formalizálás, pszeudokód) egy, a feladathoz értő és informatikai ismeretekkel is rendelkező szervezővel. • Tervezés: Az adott részfeladatok megoldásának módját határozzuk meg: algoritmusok, adatszerkezetek, operációs rendszer megválasztása, programnyelv, adatbázis-motor, stb. De nyitva hagyunk bizonyos kérdéseket, amelyekről nem feltétlenül kell most döntenünk. (pl felhasználói

felület, felépítés) • Kódolás: a kiválasztott programnyelv(ek)en implementáljuk az algoritmusokat, amelynek eredménye egy futtatható program. • Tesztelés, Hibakeresés: a tesztelés nem feltétlenül a programozó feladata, jobb, ha egy leendő felhasználó végzi (hiba pontos előidézési módja, javítás). Eredménye egy aránylag „jó program”. • Hatékonyság-minőség analízis: a megfelelő sebesség, ergonómia vizsgálata. Elkészül a program. Esetleges problémák A tervezés vagy a kódolás során kiderülhet, hogy a specifikáció rossz vagy nem egyértelmű. Előfordulhat, hogy a kódolásnál vesszük észre, hogy nem megfelelő adatszerkezetet választottunk. Ilyenkor vissza kell térni az adott fázishoz, és javítani a hibát. Fontos, hogy minden egyes fázis részletesen legyen dokumentálva, hogy több ember közös munkája esetén mindenki megértse a másik programrészletét. Ahol fontos döntés történt, ott indoklással: miért azt

az adatszerkezetet választottam, stb. Programkészítési elvek • Stratégiai elvek: o lépésenkénti finomítás: egyszerűbb részfeladatokra bontjuk a programot, nem törekszünk egyből a teljességre • • • • 4. oldal, összesen: 66 Taktikai elvek: o Döntések elhalasztása: a konkrét feladatot (pl. rendezést) akkor implementáljuk, amikor az feltétlenül szükséges. Hiszen később derülhet ki, hogy melyik a legmegfelelőbb. o Párhuzamos finomítás: minden feladat kb. ugyanolyan szintig legyen kidolgozva o Nyitott rendszerre való törekvés: ne csak a konkrét feladatot oldjuk meg, hanem törekedjünk az általános, újra felhasználható elemek írására. Így a programunk egyes része könnyen lecserélhetőek, vagy képesek új kódokat befogadni. Például egy rendezés legyen paraméterezhető, hátha később növelni/csökkenteni kell a rendezendő elemek mennyiségét. o Döntések nyilvántartása: feljegyezzük a módszer

megválasztásának okát o Adatok elszigetelése: törekedjünk az adatmezők védelmére, hogy akár véletlenül se lehessen belepiszkálni az értékükbe. Strukturált programozás esetén: modulok, lokalitás, globalitás. OBJ esetén: adatmezők elérése (private, protected) Technológiai elvek: o Kevés, de egyértelmű szabályok lefektetése, amelyek mindenkire érvényesek (pl. mindenki ugyanúgy tagoljon) o Bekezdéses leírás: a forma utaljon a tartalomra o Beszédes azonosítók használata a könnyű megértés miatt Technikai elvek: o Barátságos felhasználói felület: de ne nézzük idiótának a felhasználót o A hibaüzenetek szövegezésének közérthetősége (+magázódás) o A hiba kijelzése már az első felismerési lehetőség során történjen meg o Minden lehetséges hasznos információ közlése o Bolondbiztosság: ne lehessen sehogyan kárt okozni: kivéve persze a kivédhetetlen eseteket (Task Manager) o Olvashatóság, ergonómia: emeljük ki a

fontos dolgokat: például a kötelezően kitöltendőeket o Színkezelés: alapszíneket használjunk, hogy aránylag beállítás-kompatibilis maradjon (minden oprendszeren ugyanúgy nézzen ki) o Konfigurációs beállítások készítése (kis munka, de hasznos) Esztétikai elvek: o Menükezelés megvalósítása: összetartozó dolgok egy helyen legyenek o Ne legyen túlzsúfolt a képernyő, de túl ritka se o Ne kelljen sokat kattintani egy mezősor kitöltéséhez (automatizálás billentyűzettel: pl. Tab) o Optimális felbontás megválasztása: kis felbontásra írt program nagyon túl kicsi, fordítva meg nem fér el. Hagyományos hibakezelés Például ellenőrzött adatbevitel segítségével kontrolláljuk a felhasználó által bevitt adatokat (case, if). Ha a bevitt adat hibás, a felhasználót saját hibaüzenettel tájékoztatjuk. Ha mindezt helyesen oldottuk meg, kivétel nem keletkezik A valóságban azonban nehéz minden lehetséges esetre felkészülni, főleg,

ha a program már igen bonyolult. (nincs rá idő, a hibák összeadódása új hibákat hozhat létre) Kivétel-kezeléses hibakezelés A kivételek segítségével viszont szabványos módon választhatjuk el a kód magját a hibakezelő kódtól. A program áttekinthetőbbé, könnyebben átalakíthatóvá válik Futásidőben a Delphi könyvtárak akkor váltanak ki kivételeketm ha valami hiba történik a futásidejű kódban, a komponensben vagy az operációs rendszerben. Ha a kódot jól írtuk meg, akkor az felismeri a problémát és megpróbálja megoldani. Ellenkező esetben a kivétel átadódik a hívó kódnak; végül, ha kódunk egy része sem tudta kezelni a kivételt, a Delphi jelenít meg egy szabványos hibaüzenetet, majd megpróbálja folytatni a program futását. A kivételkezelést csak a normálistól eltérő vagy előre nem látható helyzetekben érdemes használni. (például, ha csak arra kell figyelni, hogy egy szám ne legyen nulla, akkor felesleges)

A kivételkezelés négy kulcsszóra épül: - Try: kijelöli a védett kódblokk kezdetét - Except: kijelöli a védett kódblokk végét - Finally: akkor is végrehajtódik, ha hiba történt, és akkor is, ha nem (tisztogató műveletek: adatbázis lezárása, memória felszabadítása) - Raise: mi magunk is kiválthatunk vele kivételeket, például továbbadhatjuk a kivételt a következő kezelőnek 5. oldal, összesen: 66 Példa a helyes használatra Hagyományos esetben a következő kód miatt elképzelhető, hogy az eredeti kurzor nem áll vissza. Screen.Cursor := crHourGlass; //hosszú, hibás algoritmus Screen.Cursor := crDefault; Kivételkezeléssel azonban mindenképpen visszaáll. A try blokk után except vagy finally utasítás állhat, mindkettő egyszerre azonban nem; ha tehát kezelni szeretnénk a kivételt, két beágyazott try blokkra lesz szükségünk. Try Try //hosszú, hibás algoritmus finally Screen.Cursor := crHourGlass; end; except on E: DivByZero do

. end; A kivételek kezelése általában nem olyan fontos, mint a finally blokk megírása, mivel a Delphi a legtöbb kivételt túléli. A sok kivételkezelő kód a program vezérlésének hiányosságait jelzi. Kivételkezelés az IDE-ben Amikor a hibakeresőben futtatunk egy programot, a hibakereső alapértelmezés szerint leállítja a program futását, ha valamilyen kivételt észlel. A Delphi Stack Trace szolgáltatásával azt is megnézhetjük, milyen függvényhívások sorozata okozta a kivételt. 3. Tesztelés (alapelvek, módszerek tesztadatok kiválasztására) Példa Egy Algoritmus (a program egy konkrét értékre mást csinál) Beolvas(A,B) Ha A=171.555432189 akkor ki(A*B2) különben ki (AB) Tesztelési elvek • Szisztematikus tesztelés o Például az összes bemeneti számot megvizsgálni nagyon sok idő, és teljesen felesleges is. Az eredmény nehezen elemezhető • Az a teszt jó, amely eddig fel nem fedett típusú hibát talál (pl. ha páros számra nem

jó, ne próbáljuk végig őket) • A teszt legyen rekonstruálható, hogy a hiba újra előállítható legyen (így tudjuk csak javítani) • A teszt ne csak az érvényes adatokra terjedjen ki, hanem a lehetséges bemenetek közül válogasson • A tesztelést ne a program írója végezze, hanem tesztelők vagy a felhasználó maga • Próbáljunk találgatni, mi a hiba oka Tesztelési módszerek • Statikus tesztelés (a program még nem fut) o A kód ellenőrzése o Formai ellenőrzés (kezdőértékek) o Kereszt-referencia tábla (melyik változó hol kap értéket, hol használjuk) • Dinamikus tesztelés (a program futása során) o Fekete-doboz módszer (nem látjuk mit, csinál, csak az eredményt) o Ekvivalencia osztályokra osztás (azonos típusú adatok különválasztása) o Határeset-elemzés (Pl. 1-6 String lehet, nézzük: 0,3,6,7) o Fehér-doboz módszer (a forrás ismeretében választjuk ki a bemenő adatokat)  Próbáljunk úgy bemenő adatokat

választani, hogy minden utasítás végrehajtódjon, legalább egyszer  Döntés lefedés: minden döntés hajtódjon végre (if-ek)  Feltétel lefedés: az összetett feltételek vizsgálata (H és I, I és H, stb.) 6. oldal, összesen: 66 4. Hibakeresés (alapelvek, módszerek) Bemenet: hibalista Bemenő adat - Hibás program adata Mi lett volna jó Tervezés hibái kiderülnek Ki végzi a hibakeresést? (A programozó, a Megbízó vagy a feladat kitűzője (szakember) Általános elvek: - A hiba okát próbáljuk meg az algoritmus alapján kitalálni - Csoportosítsuk a hibákat funkcionális működés szerint, a nyomkövetés megkezdése előtt - Próbáljuk megtalálni a hiba tényleges okát - Óvakodjunk a tüneti kezeléstől - Ha egy hibát kijavítottunk, várható újabb hibák előkerülése, ezért újabb alapos teszt szükséges (dokumentált adatokra) - A hibák száma és súlyossága nem a program méretével arányosan, hanem gyorsabban nő Módszerek

- Indukciós technika (az első hiba kijavítása maga után vonja a többi hiba megszűnését is?) - Dedukciós technika (visszafelé gondolkodva a hiba típusából próbálunk következtetni a hiba okára) Esetfüggő hogy melyik technika a hatékonyabb. Hibakeresési eszközök: - Debugger (nyomkövető) ­ lépésenkénti végrehajtás (F7: függvényhívást is követ, F8: nem követ függvényhívást) - Töréspontok elhelyezése: ettől a ponttól kezdve lesz csak lépésenkénti a végrehajtás (F9: fut tovább) - Run/Add breakpoint ­ F4: ha a forrásszöveg egy pontjára rámutatunk, akkor a program végrehajtása addig megy, amíg a mutatott sorra nem érünk ­ Nyomkövetés közben változó értékének kimutatása ­ A Változók értékének módosítása nyomkövetés közben (az optimalizálás miatt nem mindig alkalmazható) - Add Watch - Visszafelé nyomkövetés: melyik változó okozta a hibát? 5. Dokumentálás A felhasználói dokumentáció A felhasználó

• Nem informatikus • Minimális mértékben ismeri az adott operációs rendszert • Ismeri az egér és a billentyűzet használatát • Beszéli az adott nyelvet, IQ-ja mérhető (pozitív) • Ismeri azt a szakterületet, amelyre a program készült A dokumentáció tartalma • A program célja, hogyan oldja meg a feladatot • Minimális és ajánlott hardverigény (CPU,RAM,HDD, CD, egyéb) • Felbontás, fontméret (small/large) • Szükséges szoftverkörnyezet (OPrendszer, Service Pack, DirectX) • Aktuális verziószám • Segédprogram a működéshez: ODBC, BDE (liszensz-díj) • Telepítési utasítások (nyelvi beállítás, program inkompatibilitás) • Részletes használati információk az elindítástól A program használatáról • Screenshot-ok magyarázattal • Korlátozások az adatbevitel során • • • • • • • • • • 7. oldal, összesen: 66 Menü felépítése: blokkvázlat Hotkey és szokásos billentyűzetkiosztás

leírása Hiba esetén mi történjen (mit írjon fel, kihez forduljon) +Legyen megkülönböztetett hibaüzenet: lehessen tudni, hogy a hibát a mi programunk okozta-e ha speciális vagy nem általánosan ismert algoritmust használunk egy feladat megoldásához, ismertessük, hogy a felhasználó ellenőrizni tudja a program számításait A számításigényes műveletek kiemelése, feltüntetni, a tesztgépen meddig futott; progressbar is használható (lassít) A programmal kapcsolatos jogok (freeware, ad-ware, stb.) Továbbfejleszthető (forráskód), hány gépre telepíthető Hardverkulcs van-e (érthető módon utálják) Config állományok tartalmának leírása, hogy backup-olható legyen A fejlesztői dokumentáció A fejlesztő • Informatikus szakember (mi magunk, a team-tagjai) • Ismeri az adott programnyelvet és az oprendszert, az alapvető adatszerkezeteket, technikákat, stb. A dokumentáció tartalma • A tesztgép hardver és szoftverkörnyezete olyan

részletességgel, hogy az a továbbfejlesztéshez szükséges módon reprodukálható legyen (Service Pack, hálózat, adatbázis-motor, ODBC beállítások, kódlap, fejlesztői környezet beállításai, DLL, egyéb szoftverek) • Ha komponenseket töltöttünk le, írjuk le ezek elérhetőségét a neten és a szerzőjük nevét • Feladatspecifikáció és a megvalósított részek leírása • Verziókövetés (mi az új az előzőhöz képest): egy fájlban mindig felülre • Felhasznált algoritmusok leírása (főleg a saját fejlesztésűek), pszeudo-kód, a programban hol van az implementáció • Felhasznált adatszerkezetek, a döntés okai • Objektum-hierarchia • Adatbázis-terv (kapcsolatok) • Forráskód • Trükkös megoldások részletes leírása (pl Assembly betétek sorról sorra) • *Ha kis aljasságokat teszünk bele, legalább magunknak írjuk le • Írjuk le a forráskód tagolásakor használt konvenciót (tagolás, változónevek) • A program

korlátai (csak 1000 elemre – miért?) • Ha bizonyos feladatot nem sikerült megfelelően vagy egyáltalán megoldani, írjuk le • Tesztelési eredmények (igazolja a jó működést) • Ha tovább kell fejleszteni, megnézzük, hogy az újabb verzión ugyanazt az eredményt adja-e • Továbbfejlesztési tanácsok, lehetőségek (pl. ha gyorsabb lenne a gép) • A dokumentáció ne legyen se túl hosszú, se túl rövid 6. Hatékonyság Szempontok • Sebesség (szubjektív) • Tárterület, erőforrás-felhasználás • Kód bonyolultsága, átláthatóság A sebesség mérése stopperrel vagy ún. profiler-rel lehetséges, amelyre sorról sorra statisztikát, hogy a program egyes részei mennyi ideig futottak. A memóriafoglalás mérés Task Managerrel lehetséges. Példa (eltolás) Adott N elemű tömb. Léptessük k elemmel balra az összes elemet A, Algoritmus /k*(n+1) lépés, n+1 tárfoglalás/ Ciklus i=1-től k-ig X=A(i) //az első elemet elmentjük 8. oldal,

összesen: 66 Ciklus j=2-től n-ig A(j-1)=A(j) Ciklus vége //visszavezetjük az eggyel balra feladatra A(n)=X Ciklus vége B, Algoritmus /(n+k) lépés, 2n tárfoglalás/ Ciklus i=1-től k-ig X(i)=A(i) Ciklus vége //kimentjük az első k elemet egy másik tömbbe Ciklus j=k+1-től n-ig A(j-k)=A(j) Ciklus vége //a többit előremásoljuk az eredeti tömbben Ciklus i=1-től k-ig A(n-k+i)=X(i) Ciklus vége //az eredeti hátuljára beírjuk a kimentett elemeket //Gyorsabb, de nagyobb a tárfoglalása C, Algoritmus (n+1 lépés, n+1 tárfoglalás) Felhasználjuk, hogy n és k relatív prímek. Két szám relatív prím, ha legnagyobb közös osztójuk egy. /(n,k)=1/ Eljárás X=A(1) L1=1 Ciklus i=1-től n-1-ig //csak az ismétléshez kell L2=L1+k Ha L2>n akkor L2=L2-n //ha túllépnénk n-et, csökkentjük A(L1)=A(L2) //megfelelő elemek felcserélése L1=L2 //index eltárolása (lényegében növelése) Ciklus vége A(L1)=X Eljárás vége //utolsó elem behelyezése, amely

még kimaradt Hatékonyság-növelő eszközök • Matematikai ismeretek: Például prímszámkeresés esetén az erasztothenész-i szita. (egy tömbben vizsgáljuk a számokat: ha prímszámot találunk, többszöröseit kihúzzuk, ha nem prímszámot találunk, azt is, és többszöröseit is kihúzzuk) (prímvizsgálat: n − ig ) A hagyományos prímszámkeresés esetén, ha A> n és B> n , akkor A*B>N. Így elég vizsgálni. Tovább gyorsítás: szitával előállított prímosztókkal vizsgáljuk n -ig Példa (rendezés) A(n) rendezendő tömb + X(k) tömb, összes eleme nulla. K a legnagyobb elem Algoritmus (n lépés, k tárfoglalás) Ciklus i=1-től n-ig Inc(X(A(i))) Ciklus vége //X indexei adják a számokat, sorrendben (ahol 1 van) X értelmezése Ciklus i=1-től k-ig Ha X(i)=1 akkor Ki(i) Ciklus vége Példa (keresés) • Szekvenciális keresés: végignézi az összeset, nem áll meg. (kivéve ha break-et használunk) While segítségével megállási

feltételt is adhatunk. • Logaritmikus keresés: gyors, de csak rendezett tömbre működik • Átrendezéses keresés: csak kis elemszám esetén gyors (ha használunk egy elemet, utána mindig a vektor elejére tesszük, így a gyakran használtak elöl lesznek) 9. oldal, összesen: 66 Lokális hatékonyság (ha sokszor kell végrehajtani) A2 2*A A:=A+1 A:=A+K • • • • • helyett helyett helyett helyett A*A A+A Inc(A) Inc(A,K) //A növelése K konstans értékével sin(x)/cos(x) helyett tan(x) gyors típusok használata (valós helyett egész, ha lehet) kisebb típusok esetén (byte, smallint) is integerrel számol a gép, nem érdemes ezek használatára törekedni sokszori végrehajtás előtt jó, ha a részeredményeket kiszámoljuk előre, és egy változóban tároljuk. Ha gyorsulást szeretnénk elérni, a ciklusok belsejében vizsgálódjunk: ha lehet, ne legyen függvényhívás, egyszerűsítsük a kifejezéseket Példa (Fibonacci) Ha nem kell az

összes számot eltárolni n-ig, hanem csak az n-edik számot keressük, elég három változó: hatékonyabb tárfoglalás. n   1  1 + 5   Fib(n) = round  ⋅   5  2     Áttekinthetőség • Eljárások, függvények használata (programsor-csökkenés) • Ciklusok összeolvasztása, ha a megállási feltétel vagy a lépésszám megegyezik (kevesebb ciklus – jobb átláthatóság) • Adatok előfeldolgozása (kiszámoljuk, és változóban tároljuk, hátha később szükség lesz rá) Program transzformációk Példa (feltételvizsgálat) (Ha A és B akkor ’valami’) Tippek: • csak akkor értékeljük ki B-t, ha A igaz, mivel ha A hamis, az eredmény nem lehet igaz – ne vizsgáljunk feltételt feleslegesen • Helyette: Ha A akkor Ha B akkor ’valami’ (azt tegyük előre, ami gyakrabban hamis, így időben leáll a feltétel) • Delphi-ben beállítható a kiértékelés módja: balról jobbra, vagy teljes

További példák • (Ha A akkor ’valami1’ különben Ha B akkor ’valami2’) esetén, ha tudjuk, hogy valamelyik igaz, akkor hatékonyabb: (Ha A akkor ’valami1’ különben ’valami2’ • (Ha A akkor ’valami1’; Ha A akkor ’valami2’) helyett (Ha A akkor ’valami1’,’valami2’) • (Ciklus Ha f akkor ’valami’ Ciklus vége) helyett (Ha f akkor ciklus ’valami’ ciklus vége). Ez csak akkor jó, ha f értéke állandó • (Ciklus A B Ciklus vége) helyett, ha A független a ciklustól (A ciklus B ciklus vége) 7. Az OO programozás általános elvei (előnyök és hátrányok) Az OOP fejlesztés összehasonlítása a strukturált fejlesztéssel Objektum Orientált Programozás Tulajdonképpen a rekord fogalom általánosítását jelenti. 1. var nev1, nev2 : String; mag1, mag2 : Integer; 2. type SzemRec = record nev : String mag : Integer; end; Cél: ne kelljen külön-külön változókat létrehozni, egy egységbe összefogható legyen 10. oldal,

összesen: 66 Egységbezárás: - Adattagok - Metódusok van olyan szerkezet, amibe ezeket együttesen tárolhatjuk. Ez az osztály - az egységbezárással a változók láthatósági szabályai remekül állíthatók Öröklődés: - Az objektum az osztály egy példánya - Az osztály örököl tulajdonságokat a szülőjétől - Öröklődéskor a leszármazott örökli az adattagokat és a metódusokat, de képes arra, hogy - Új adattagokat vegyen hozzá - Új metódusokat vegyen hozzá - A szülőosztályban megírt metódusokat felülírja saját szintjén - Örökölni csak egy szülőtől lehet (Delphi, Java) - Több szülő: C Polimorfizmus - Sokoldalúság - Előny: ugyanolyan névvel lehet hívni a metódust, s ezzel különböző szinten különböző funkciókat valósíthatunk meg var a : ember; /értékadás szintjén kompatibilis a szülő leszármazottjával a.megy / nem tudni, hogy férfi vagy nő, de megy Ez a típus-kompatibilitás lehetővé teszi, hogy

ha a szülőosztály egyik példánya értéket kap, akkor dőljön el, hogy ténylegesen melyik metódus hajtódjon végre Unit Unit1; INTERFACE osztály neve berakja Uses ; Type TForm1 = class(TForm) Button1 : TButton; szülő(Ha itt nincs semmi, akkor a Delphi a legáltalánosabbat: TObject) adattag metódusnév Procedure Button1Click(Sender:TObject) end; Var Form1:TForm1; IMPLEMENTATION Procedure TForm1.Button1Click(Sender: TObject) begin end; Az OO programozás tulajdonságai Előnyök - Védett, újrafelhasználható objektumok készíthetők - Az objektum képességeihez való hozzáférés pontosan szabályozható - Egy objektum használatához nem szükséges ismerni annak belső működését (pl. komponensek az IDE-kben) - Kiterjesztett képességek a hagyományos programozáshoz képest (öröklődés, polimorfizmus, konstruktorok, destruktorok – ezekre strukturált esetben is szükség van, csak más elv szerint valósulnak meg) - A különálló objektumok

működése anélkül változtatható, hogy hatással lennének a programkód többi részére - Megkönnyíti a csapatmunkát, a feladatok könnyebben részekre oszthatók - Nagyobb programok esetén megkönnyíti a módosítást, növeli az áttekinthetőséget - A nagyobb szoftverrendszerek tervezése könnyebbé, áttekinthetőbbé válik (kisebb a hibajavítás költsége) - Előre megírt kódok könnyebb felhasználása – gyorsabb fejlesztés, nagyobb hangsúlyt lehet fektetni az egyedi igényekre 11. oldal, összesen: 66 Hátrányok - Az egységbe zárt objektumokkal történő műveletek több erőforrást igényelnek: több memória és CPU-idő (pl. objektumok paraméterül adása, ld Java) - A mások által elkészített, általunk nem módosítható objektumok működését nem vagyunk képesek befolyásolni. Pl a Windows beépített komponenseinek esetleges hibás működésével együtt kell élnünk. (vagy átírjuk a VCL-t ) A strukturált programozás

tulajdonságai Előnyök - A metódusokkal és unitokkal megvalósítható az összetartozó elemek elkülönítése - Egyszerű feladatokhoz egyszerű kód - Erőforrás-takarékosság, nagy sebesség Hátrányok - Nehéz a kód újrafelhasználása (a unitokat persze lehet hordozni), a forrás nem védhető - Bonyolult szoftverek esetében nehéz a módosítás, illetve a tervezés 8. Vizuális és komponens alapú szoftverfejlesztés A komponens alapú programozás A komponens egy olyan bináris (lefordított) szoftver egység, amely által megvalósított funkció jól definiált formában, a komponens interfészén keresztül érhető el. Kialakulását és elterjedését a következő tényezők tették szükségessé. A rövid elkészülési határidő, kitűnő minőség, gazdaságosság, skálázhatóság, integrálhatóság, modellekhez való könnyű illeszthetőség. Ezeket a megnövekedett igényeket azonban egyre kevésbé sikerült kielégíteni a „hagyományos”

szoftverfejlesztési eszköztárral új alapfilozófiára volt szükség. Alapgondolat A komponens alapú szoftverfejlesztés az OO paradigmának mintegy továbbfejlesztett változata. Az alapötlet, hogy a már elkészített, és több helyen is szükséges szoftver egységeket ne kelljen megírni, azok egy új alkalmazásba beilleszthetők legyenek. Különösen igaz az újrafelhasználhatóságra való igény, ha olyan bonyolult, komplex funkciókat valósít meg egy komponens, amiket kifejleszteni meglehetősen időigényes, és ennek megfelelően költséges is. Ezek alapján a komponensek definiálása, elkészítése, tesztelése, továbbfejlesztése végül el is különül az egyes alkalmazásoktól, a komponens, mint funkcionális egység külön életet él. Típusok A „komponens alapú szoftverfejlesztés” többféle szoftverfejlesztési folyamatra utalhat, melyeket érdemes megkülönböztetni. Az egyik eset, amikor a saját magunk (cégünk, stb.) által

kifejlesztett komponensekből építkezünk. Ezzel élvezünk bizonyos előnyöket, például a skálázhatóság, a változó modellekhez való könnyebb illeszthetőség, ugyanakkor egy bonyolult komponens esetében jelentős ráfordítást jelenthet a komponens kifejlesztése. Egy teljesen más szemléletmódot jelent, ha rendszerünket megvásárolható, mások által készített egységekből építjük fel. De a kereskedelemben beszerezhető komponensek nem pontosan a mi igényeinket elégítik ki, hanem egy „átlagos” igényt, ezen kívül ezek a komponensek könnyen változhatnak, de ezt a változást is a piacon megjelenő újabb igények okozzák inkább, mint a mi konkrét igényünk. Ezekbe a komponensekbe nem látunk bele, létezhetnek nem dokumentált, vagy nem szabványos tulajdonságai is, és a komponensek integrálhatósága általában az adott gyártó által készített egyéb komponensekkel könnyű, a többi esetben általában nem garantált. Azt sem szabad

elfelejtenünk, hogy ezekhez az állandón változó, igen bonyolult komponensekhez naprakész tudás szükséges, aminek megszerzése szintén ráfordítást igényel, és a helyzet csak bonyolódik, ha figyelembe vesszük, hogy a különböző komponensek újabb és újabb verzióival valószínűleg frissíteni szeretnénk alkalmazásunkat. Komponens infrastruktúrák Az analízis vizsgálatakor elmondhatjuk, hogy ahelyett, hogy az egyes, megvásárolható komponenseknek „jól definiált” lenne az interfészük, egy csomó lefedetlen tulajdonság marad: nem illetve nem jól dokumentált tulajdonságok, a viselkedés nem kielégítő leírása, minőségre vonatkozó dokumentáció (sebesség, memóriahasználat) hiánya. A tervezésnél gondot jelenthet, hogy az együttműködő komponenseink és komponens csoportjaink tulajdonságai jelentősen változhatnak az újabb verziók során, valamint, hogy bizonyos, tényleges működéssel kapcsolatos tulajdonságok csak az

implementáció alatt derülnek ki. A .NET és a COM+ a Microsoft által fejlesztett komponens futtató környezet 12. oldal, összesen: 66 1. Programozási tételek Hagyományos rendezések TÉTELEK Összegzés tétele Általános feladat: Adott egy N elemű számsorozat. Számoljuk ki az elemek összegét! Eljárás S:=0 Ciklus I=1-től N-ig S:=S+A(I) Ciklus vége Eljárás vége. Eldöntés tétele Általános feladat: Adott egy N elemű sorozat és egy, a sorozat elemein értelmezett T tulajdonság. Az algoritmus eredménye: annak eldöntése, hogy van-e a sorozatban legalább egy T tulajdonsággal rendelkező elem. Eljárás I:=1 Ciklus amíg I<=N és A(I) nem T tulajdonságú I:=I+1 Ciklus vége VAN:=I<=N //a VAN egy logikai változó, amely csak akkor igaz értékű, ha I<=N Eljárás vége Kiválasztás tétele Általános feladat: Adott egy N elemű sorozat, egy, a sorozat elemein értelmezett T tulajdonság, valamint azt is tudjuk, hogy a sorozatban van

legalább egy T tulajdonságú elem. A feladat ezen elem sorszámának meghatározása Eljárás I:=1 Ciklus amíg A(I) nem T tulajdonságú I:=I+1 Ciklus vége SORSZ:=I Eljárás vége. A megszámlálás tétele Általános feladat: A T tulajdonsággal rendelkező elemek megszámlálása a feladat. Eljárás S:=0 Ciklus I=1-től N-ig Ha A(I) T tulajdonságú, akkor S:=S+1 Ciklus vége Eljárás vége A maximum kiválasztás tétele Általános feladat: Egy sorozat legnagyobb elemét kell megtalálni. (Minimum kiválasztásnál csak a feltételes utasítás feltétele fordul meg: ’<’ helyett ’>’ lesz) Eljárás INDEX:=1 Ciklus I=2-től N-ig Ha A(INDEX) < A(I) akkor INDEX:=I Ciklus vége MAXINDEX:=INDEX Eljárás vége 13. oldal, összesen: 66 Kiválasztás tétele Általános feladat: Tudjuk, hogy a sorozatban van legalább egy T tulajdonságú elem. A feladat ezen elem sorszámának meghatározása. Eljárás I:=1 Ciklus amíg A(I) nem T tulajdonságú I:=I+1

Ciklus vége SORSZ:=I Eljárás vége. Szétválogatás tétele (helyben) Általános feladat: Rendelkezésre áll egy sorozat, valamint egy kijelölt eleme. Cseréljük fel úgy a sorozat elemeit, hogy az B-nél kisebbek B előtt legyenek, a nála nagyobbak pedig utána. Eljárás BDB:=0; CDB:=0 Ciklus i:=1-től n-ig Ha A(I) T tulajdonság akkor BDB:=BDB+1; B(BDB):=A(I) Különben CDB:=CDB+1; B(N-CDB+1):=A(I) Ha vége Ciklus vége Eljárás vége Szétválogatás tétele (külön) Általános feladat: Szétválogatjuk a T tulajdonságú elemeket az egyik tömbbe, a nem T tulajdonságúakat egy másikba. Eljárás BDB:=0; CDB:=0 Ciklus i:=1-től N-ig Ha A(I) T tulajdonság akkor BDB:=BDB+1; B(BDB):=A(I) Különben CDB:=CDB+1; C(CDB):=A(I) Ha vége Ciklus vége Eljárás vége RENDEZÉSEK Rendezés közvetlen kiválasztással A módszer lényege: A rendezendő számok legyenek az A vektor elemei. Az első menetben kiválasztjuk a vektor legkisebb elemét úgy, hogy az A(1)-et

összehasonlítjuk A(2). A(N) mindegyikével. Ha A(1)-nél kisebb elemet találunk, felcseréljük őket, vagyis ezt a kisebbet tesszük A(1)-be. A(2)-vel folytatjuk N-1 lépésben a vektor rendezett lesz Eljárás Ciklus I=1-től N-1-ig Ciklus J=I+1-től N-ig Ha A(J)<A(I) akkor A:=A(J) ; A(J):=A(I) ; A(I):=A Ciklus vége Ciklus vége Eljárás vége. Rendezés minimum kiválasztással A módszer lényege: A felesleges cserék kiküszöbölése érdekében két segédváltozót vezetünk be. Az ÉRTÉK tartalmazza az adott menetben legkisebb számot, az INDEX pedig annak lelőhelyét a vektorban. Eljárás Ciklus I=1-től N-1-ig INDEX:=I ; ÉRTÉK:=A(I) Ciklus J=I+1-től N-ig Ha ÉRTÉK>A(J) akkor ÉRTÉK:=A(J) ; INDEX:=J Ciklus vége A(INDEX):=A(I) ; A(I):=ÉRTÉK Ciklus vége Eljárás vége. 14. oldal, összesen: 66 Buborékos rendezés A buborékos rendezés alapgondolata a szomszédos elemek cseréje. Az első menetben a rendező A vektor végéről indulva minden

elemet összehasonlítunk az előtte lévővel. Amennyiben rossz sorrendben vannak, felcseréljük őket. Az első menet végére a legkisebb elem biztosan a helyére kerül. Minden további menetben ismét a vektor végéről indulunk, de egyre kevesebb hasonlításra van szükségünk, mert a vektor eleje fokozatosan rendezetté válik. Javított Algoritmus: Algoritmus: Eljárás Eljárás i:=n; Ciklus I=2-től N-ig While i>1 do Ciklus J=N-től I-ig (-1-esével) begin Ha A(J-1)>A(J) akkor A:=A(J-1) cs:=0; A(J-1):=A(J) for j:=1 to i-1 do A(J):=A begin Elágazás vége if a[j]>a[j+1] then Ciklus vége begin Ciklus vége cs:=j; Eljárás vége. csere(a[j],a[j+1]) Eljárás vége Egyszerű beillesztéses rendezés A rendezést úgy végezzük, mintha kártyáznánk, és kezünkbe egyesével vennénk fel az asztalról a kiosztott lapokat. Az éppen felvett lapnak megkeressük a kezünkben lévő, már rendezett sorozatban a helyét úgy, hogy közben a nála nagyobbakat egy

hellyel elcsúsztatjuk, végül beillesztjük a felvett lapot a neki megfelelő helyre. N elem esetén a végső sorrend kialakításához N-1 menetre van szükség. Eredeti: 64 56 8 42 5 12 16 1. menet után: 56 64 8 42 5 12 16 2. menet után: 8 56 64 42 5 12 16 3. menet után: 8 42 56 64 5 12 16 4. menet után: 5 8 42 56 64 12 16 5. menet után: 5 8 12 42 56 64 16 . 15. menet után: 3 5 7 8 12 16 22 40 40 40 40 40 40 3 3 3 3 3 3 31 31 31 31 31 31 47 47 47 47 47 47 22 22 22 22 22 22 24 24 24 24 24 24 33 33 33 33 33 33 7 7 7 7 7 7 46 46 46 46 46 46 24 31 33 40 42 46 47 56 64 Javított Algoritmus: Eljárás for i:=2 to n do begin j:=i-1; x:=a[i]; while (j>0) and (a[j]>x) do begin a[j+1]:=a[j]; j:=j-1; end; if j<>i-1 then a[j+1]:=x; Eljárás vége Algoritmus: Eljárás Ciklus J=2-től N-ig I:=J-1 ; A:=A(J) Ciklus amíg I>0 és A<A(I) A(I+1):=A(I) ; I:=I-1 Ciklus vége A(I+1):=A Ciklus vége Eljárás vége. 2. Haladó rendezési módszerek (Quicksort,

Shell-rendezés, Kupacrendezés, Radix-rendezés, Bingó-rendezés, Mergesort) Quicksort Igen gyors és hatékony rendezésről van szó, amelynek alapja az, hogy egymástól távol lévő elemeket hasonlítunk össze egymással, és szükség esetén felcseréljük azokat. Válasszuk ki az A vektor első elemét, és vegyük ki a vektorból. A helye üres marad A vektor végéről indulva keresünk egy ennél kisebb elemet. Ha találunk, azt betesszük a felszabadult helyre. Most a lyuk ott keletkezik, ahonnan ezt az elemet kivettük Ide a vektor elejéről keresünk egy, a kiválasztott elemnél nagyobb elemet. Ha találunk, beillesztjük, ha nem, akkor oda éppen a kiválasztott elem illik. 64 64 64 56 46 46 8 42 56 8 56 8 56 8 5 12 42 5 42 5 42 5 16 12 12 12 40 16 16 16 3 31 40 3 40 3 40 3 47 31 31 31 22 47 47 47 24 22 22 22 33 24 24 24 7 46 33 7 46 33 7 33 7 64 15. oldal, összesen: 66 A konkrét példában nem sikerült a vektort nem sikerült két részre

vágni, mert a 64 éppen a legnagyobb elem. A következő lépésben a 46-ot emeljük ki a vektor elejéről, és hátulról haladva keressünk nála kisebb elemet, és így tovább. 46 46 46 46 46 46 7 7 7 7 7 7 56 56 33 33 33 33 8 8 8 8 8 8 8 42 42 42 42 42 42 42 5 5 5 5 5 5 5 12 12 12 12 12 12 12 16 16 16 16 16 16 16 40 40 40 40 40 40 40 3 3 3 3 3 3 3 31 31 31 31 31 31 31 47 47 47 47 24 24 22 22 22 22 22 22 22 24 24 24 24 24 46 33 33 33 47 47 47 7 56 56 56 56 56 64 64 64 64 64 64 64 A 46 most a végleges helyére került. Tőle balra a nála kisebb, jobbra a nála nagyobb elemek helyezkednek el. Az eljárást az így kettévágott vektor egyik részének elemeivel a fent leírt módon folytatjuk tovább. Eljárás Quick(AH, FH) Szétválogat(AH, FH, E) Ha AH<E-1 akkor Quick(AH, E-1) Ha E+1<FH akkor Quck(E+1, FH) Eljárás vége A szétválogató eljárás a vektor elemeit úgy rendezi át, hogy az E-edik elem elé kerülnek a nála kisebbek,

mögé pedig a nagyobbak. Eljárás gyorsrendezés (n, A) Eljárás rendez(also, felso) I:=also; J:=felso; X:=A[(also+felso) div 2]; {n – elemszám, A - tömb} {az intervallumok szélei} {a középső elem, div – egész osztás} Ciklus Ciklus amíg A[I]<x I:=I+1 ciklus vége {elölről} Ciklus amíg A[J]>x J:=J-1 ciklus vége {hátulról} Ha I<=J akkor csere(A[I];A[J]); I:=I+1; J:=J-1; Amíg I>J Ha also<J akkor rendez(also,J); {addig áll fenn, amíg a különbségük} Ha I<felso akkor rendez(I, felso); {legalább 1. 1-hosszúra már nem hívjuk meg} Eljárás vége Begin Rendez(1,N); End; {a főprogram} Megjegyzések: A középső elem mindig más, amíg a két határ össze nem ér. Az algoritmus sebessége függ az elemek rendezettségétől Akkor a leglassabb, ha a középső elem a legkisebb vagy a legnagyobb Akkor igazán gyors, ha nagy méretű tömbbel dolgozik Nem ismeri fel, ha a tömb rendezett, de ekkor is gyors. A rekurzív újrahívás

megtörténik. • A kis méretű tömbökre azért nem jó, mert a rekurzió lassít Hibrid megoldás: Ha a tömbméret lecsökken mondjuk 100 elemre, akkor egy hagyományos rendező algoritmust használunk. • • • • • Tipp: a quicksort algoritmus lefutása előtt egyszerűen ellenőrizhetjük, hogy a tömb neme rendezett már. A Shell-rendezés Alapötlet: jó, ha az elemek gyorsan a helyük közelébe kerülnek. Például először minden hetediket, majd minden másodikat, stb. rendezzük, egy rendezési algoritmussal (átlagosan n/2 idő alatt) eljárás Shell(L,D) ciklus i=1 to n do Beilleszteses(L,D[i]) ciklus vége eljárás vége 16. oldal, összesen: 66 eljárás Beilleszteses(L,K) //K – ahányadik elemmel kell dolgozni ciklus i=k+1 to n do //K-val visszafelé lépked, amíg el nem éri az egyet C=L[i] //C a korlátozó változó pos=i-k //Ha k helyére 1-et írunk, megkapjuk a sima beill. rendezést ciklus amíg (pos>=1) és (C<L[pos]) L[pos+k]=L[pos]

pos=pos-k ciklus vége L[pos+k]=c ciklus vége eljárás vége A Kupacrendezés A Kupac A (bináris) kupac adatszerkezet úgyis szemlélhető, mint egy majdnem teljes bináris fa egy tömbben reprezentálva. A fa minden csúcsa megfelel a tömb egy elemének, mely a csúcs értekét tárolja. A fa minden szintjén teljesen kitöltött, kivéve a legalacsonyabb szintet, ahol balról jobbra haladva csak egy adott csúcsig vannak elemek. A körök belsejébe írt szám a fa csúcsához tartozó érték, a kör mellé írt szám a csúcsnak megfelelő tömbelem indexe. A kupac minden i, gyökértől különböző elemére igaz a következő kupac tulajdonság: A[SzüLő(i)] > A[i] azaz az elem értéke kisebb vagy egyenlő mint a szülőjének értéke. Így a kupac legnagyobb eleme a gyökér és egy adott csúcs alatti részfa minden elemének értéke kisebb vagy egyenlő az adott csúcsban lévő elem értékénél. Eljárás Kupacolo (I,J) Ha (I nem levél) és (I valamelyik

fiának az eleme nagyobb mint az I eleme) akkor K legyen az I nagyobbik elemű fia; //a tömbben lévő számnak az indexe Csere (A[i], A[K]); Kupacolo(K,J); //rekurzív újrahívás, így biztosítja hogy pl.: ne csak a felső két elemre Elágazás vége //maradjon meg a kupactulajdonság, hanem végigmenjen a részfán Eljárás vége Eljárás Kupacépit Ciklus I:=N/2 to 1 Kupacolo(I,N); Ciklus vége Eljárás vége //azért csak N/2-ől mert utána mindenképpen csak levélelem van amit a Kupacolo úgyis visszadob. Azért van ciklus, hogy a fa aljáról visszafelé, az összes részfára végigmenjen. Eljárás Kupacrendezés Kupacépit //rendezett kupac kell a meghívásához! Ciklus I:=N to 2 //utolsó elem úgyis a helyén van Csere (A[1], A[I]); //azért mondhatom, mert a tömb elején van a legnagyobb elem, ha a Kupacolo (1,I-1); végére teszem és N-1-re, nézem tovább, akkor a legnagyobb elem a Ciklus vége helyén van. Így egy csökkenő sorrendbe alakítom ki a

növekvő Eljárás vége sorrendet. A Radix-rendezés Mindegyik elemet (x) a megfelelő helyre tesszük egy tömbben (T): (T[x]). Ha a beszúrandó elemből már van a tömbben, az adott elem után láncoljuk. Tegyük fel, hogy mindegyik elem ugyanolyan hosszú (számjegyek, betűk). A rendezendő sorozat: 45242, 45230, 97432, 74239, 12335, 43239, 40122, 98773, 41123, 61230 17. oldal, összesen: 66 Az elemeket az utolsó karakterük szerint rendezzük sorba. Tehát, ha az utolsó karakter 0, akkor a nulladik helyre kerül a tömbben. Ahova több elem kerül, azokat fűzzük láncba, majd írjuk le a sorozatot: 45230, 61230, 45242, 97432, 40122, 98773, 41123, 12335, 74239, 43239 Ugyanígy hátulról előrefelé haladva, az első számjegyig: 40122, 41123, 45230, 61230, 97432, 12335, 74239, 43239, 45242, 98773 40122, 41123, 45230, 61230, 74239, 43239, 45242, 12335, 97432, 98773 . 12335, 40122, 41123, 43239, 45230, 45242, 61230, 74239, 97432, 98773 Megjegyzések: • Elölről

hátrafelé haladva nem működne • Különböző hosszú számok esetén először hosszuk szerint kell őket sorba rendezni I. Algoritmus (összesen n+m művelet) Ha (a1, a2, , an) számok (0m-1) között vannak: 1. Az összes (0m-1) számhoz vegyünk fel egy üres sort 2. Balról jobbra végighaladva a1an számokon, helyezzük az ai elemet az i-edik sorba 3. Kapcsoljuk össze a sorokat II. Azonos hosszúságú számok esetén Bemenet: A1An sorozat, amelyben minden Ai pontosan k hosszú. Az Ai sorok 0m-1 közé esnek Kimenet: B1Bn sorozat, ami A1An sorozat egy permutációja. 1 ≤ i ≤ n –re Bi ≤ Bi+1 Eljárás Tegyük A1.An-t a SOR-ba ciklus j=k to 1 (-1-esével) do ciklus L=0-tól M-ig kiürítés(Q[L]) ciklus vége ciklus amíg a SOR nem üres inc(i) Legyen Ai a SOR első eleme Tegyük az Ai SORból Q[aij] helyre ciklus vége ciklus L=0 to M-1 do csatoljuk a SOR végére: Q[L] ciklus vége ciklus vége eljárás vége III. Különböző hosszúságú láncok lexikografikus

rendezése Eljárás ürítsük ki a SOR-t ciklus j=0 to m-1 do ürítés (Q[j]) ciklus vége ciklus L=Lmax to 1 (-1-esével) do Hosszúság(L) csatolása a SOR elejére ciklus amíg a SOR nem üres Ai legyen első a SOR-ban Tegyük Ai elemet a Q[aij] helyre ciklus vége ciklus minden j-re és nem üres L-re csatoljuk Q[J] elemet a SOR végére kiürítés (Q[J]) ciklus vége ciklus vége Eljárás vége 18. oldal, összesen: 66 A Bingo-rendezés Eljárás MaxMin3 (L, MaxValue, MinValue) Bingo=MinValue NextAvail=1 NextBingo=MaxValue //Min és Max érték Ciklus amíg Bingo<MaxValue StartPos=NextAvail Ciklus i=Startpos to n do //annyiszor fut le, ahány különböző elem van Ha L[i]=Bingo akkor //A belső rész a kicsi elemeket egyből a helyére rakja csere(L[i],L[NextAvail]) //nem veszi észre, ha a tömb rendezett inc(NextAvail) különben ha L[i]<NextBingo akkor //az aktuális min beállítása NextBingo=L[i] //m x n -el arányos lépésszám (maximum m2+n) ciklus

vége //1<m<<n esetben működik jól Bingo=NextBingo NextBingo=MaxValue ciklus vége eljárás vége A MergeSort rendezés Eljárás MergeSort (L, Low, High) Ha Low<High akkor Mid = ((Low+High)/2) //az alsó egészrész MergeSort(L,Low,Mid) MergeSort(L,Mid+1,High) MergeSort(L,Low,Mid,High) eljárás vége Eljárás Merge (L,Low,X,High) C1=Low C2=x+1 Count=Low //az ideiglenes tömb indexét jelöli ki ciklus amíg (C1<X) és (C2<=High) //valamelyik tömbrészlet elfogyhat Ha L[C1]<=L[C2] akkor //Ha C1>X, akkor az első tömbrészlet elemei a helyükön vannak, Temp(count)=L[C1] //a ciklus a temp tömbbe másolja a második megmaradt elemeit inc(C1) //a maradék elemek között van egy, amely az előző legnagyobb különben //eleménél is nagyobb Temp(count)=L[C2] C2=C2+1 inc(count) ciklus vége Ha C1>X akkor //kiindulásként a két résztömb rendezett volt Ciklus k=C2 to High do Temp(count)=L[k] inc(count) ciklus vége különben ciklus k=C1 to X do

Temp(count)=L[k] inc(count) ciklus vége ciklus k=Low to High do L[k]=Temp(k) ciklus vége Eljárás vége //A már feldolgozott tömbrészt visszamásoljuk a helyére //A merge összefűzi az elemeket (rendezett összefűzés) 3. Dinamikus memóriakezelés Egyirányú lánc (rendezett, nem rendezett) strázsa-technika Dinamikus memóriakezelés A strukturált típusú változók mérete a program fordításkor dől el, így a futás során nem módosítható. A memóriafoglalás és felszabadítás műveleteivel a memória dinamikus felhasználását valósítjuk meg. 19. oldal, összesen: 66 A mutató típus és a dinamikus változók A pointer (mutató) olyan speciális változó, amely memóriacímet tartalmaz. A mutatók típussal rendelkeznek. A típus kijelöli, hogy a dinamikus helyfoglalás során mekkora területet kell a mutatóhoz hozzárendelni. A mutatók deklarálásának általános formája: var változónév: ^típusnév, ahol a típusnév tetszőleges

szabványos vagy felhasználói típus lehet. A mutató a deklaráció után meg sehova sem mutat. A programon belüli helyfoglalás elvégzésére a new utasítás használható, amely a lefoglalt terület címét a paraméterben adott mutatóba tölti. Ha nincs elég hely a memóriafoglalás elvégzésére, akkor ezt az EOutOfMemory kivétel jelzi. Az üres mutató jelölésére a nil konstans való. A mutató által kijelölt területre a nevével és utána egy ^ jellel hivatkozunk: p^:=10; Felszabadítás: dispose(p); A dinamikus helyfoglalás előnye akkor tűnik ki igazán, ha több kilobájtos dinamikus változót (rekord, tömb) használunk. A strukturált típusokhoz csak akkor definiálhatunk mutatót, ha a típushoz egyetlen típusnevet rendelünk, a deklarációs rész type szekciójában. A mutatók közötti értékadás lehetséges new utasítás nélkül is, azonban értéket így nem adhatunk a mutatónak. Például: Q:=P akkor is működik, ha nem volt new(Q) De

Q^.nev:=P^nev esetén nem tudjuk, hova fog mutatni, hibákhoz vezet De a terület lefoglalása után ez megengedett. Ha egy változót felszabadítunk, utána még ugyanoda fog mutatni, de a terület újra felhasználhatóvá válik. Ezért a dispose utasítás után állítsuk a mutató értékét nil-re Ha egy nem létező változóra dispose-t adunk ki, programhibához vezet. Type pelem=^TFa; TFa=record tart: integer; bal: pelem; jobb: pelem; end; var Form1: TForm1; gyoker,p: pel; További memóriakezelő metódusok A pointer típussal általános mutatót is deklarálhatunk, amely nem rendelkezik konkrét típussal, ezért a new eljárást nem használhatjuk. Ebben az esetben az adott bájtméretű memóriaterület lefoglalását a GetMem, felszabadítását pedig a FreeMem eljárások segítségével végezhetjük el. Procedure GetMem (var p: pointer; meret: integer); Procedure FreeMem (var p: pointer [; meret: integer]); Az AllocMem függvénnyel is lefoglalható a terület,

amelyet 0 értékű bájtokkal tölt fel. Function AllocMem (meret: cardinal): pointer; A lefoglalt memóriablokk mérete a ReAllocMem eljárással módosítható. Procedure ReAllocMem(var p: pointer; ujmeret: integer); Az alkalmazás által lefoglalt memóriablokkok számát az AllocMemCount, míg a lefoglalt terület összméretét az AllocMemSize egész típusú globális változók tartalmazzák. A pointer típusú mutatókat dinamikus pufferterületek kijelölésére használjuk, amelyek méretét a program futása során adjuk meg. A mutatók léptetése az Inc és a Dec függvények segítségével lehetséges. A léptetés során a mutató értéke annyi bájttal módosul, amennyi a típusának megfelelő adatméret. Azonos típusú mutatók esetén használhatjuk az = és a <> műveleteket. A nil konstansmutató és a pointer típussal deklarált mutatók bármely más mutatóval összehasonlíthatók. Pl. if (ip=p) and (ip<>nil) then halt; A mutató típusa

típuskonverzióval megváltoztatható. Ily módon a pointer típusú mutatókhoz is rendelhetünk konkrét típust. Pl longint(p ^):=123456; 20. oldal, összesen: 66 Az Addr függvény, illetve az ennek megfelelő @ operátor segítségével bármely objektum címét lekérdezhetjük, és tetszőleges típusú mutatóba tölthetjük. Pl. i:=5; ip:= @i; ip ^:=i+6; ki(i); //i=11 lesz LÁNCOLT LISTA Az egyirányú láncolt lista Ez egy nagyon egyszerű dinamikus adatszerkezet, amely egy eleje mutatóból, és rekordokból áll. A rekordok azonos típusúak: egy tartalom mezőből és egy következő mutatóból állnak Attól, hogy a mutatók egyértelműen meghatározzák a végighaladás sorrendjét, az adatok a memóriában össze-vissza helyezkednek el. Az utolsó elem nil-re mutat Ez jelzi a láncolt lista végét. A tömbbel összehasonlítva Új elem felvétele egyszerű, mert csak két mutatót kell beállítani. Törölni is gyorsan lehet: a törlendő előtti elem

mutatóját a következőre állítjuk, őt pedig felszabadítjuk. Hátránya a tömbhöz képest: átlagosan n/2 lépésben találunk meg egy elemet, mert csak szekvenciálisan tudunk keresni egy rendezetlen listában. Akkor érdemes láncolt listát használni, ha az elemek mennyisége változik, mert a memória dinamikusan foglalható. Rendezni nem érdemes, mert az elemek közvetlen elérése nem valósítható meg, és csekély sebességnövekedést eredményez. Műveletek Lista létrehozása type Pelem=^Elem; Elem=record tartalom: integer; kovetkezo: Pelem; end; Itt megengedett, hogy előbb használjuk a típus (Elem), mint deklarálva lenne. Eleje:=nil; //nem hagyható el Lista bejárása P:=eleje; //segédváltozó While p<>nil do begin Kiir(P^.nev); P:=P^.kov; End; Új elem felvétele Lehetséges az elejére beszúrni vagy rendezett lista esetén egy megfelelő helyre. (előbb egy keresési feladat) Láncol listában nem tudunk visszalépni, ezért tárolni kell az

előző címét. Elejére szúrás New(Q); //elem létrehozása Q^.tart:=x; //tartalommal való feltöltés Q^.kov:=eleje; //beláncolás az eleje mutató elé Eleje:=Q; //Q lesz az eleje a listának Rendezett beszúrás Elejére: ha az első elemnél kisebb a beszúrandó, vagy üres a lista. Középre: meg kell keresni az elem helyét. Végére: ha nagyobb, mint az utolsó Lánc végére szúrás While p^.kov<>nil do P:= P^kov; P^.kov:=R; R^kov:=nil; //a végéig lépkedés //beláncolás, vége nil Mutatott elem elé való beszúrás New(R); R^.tart:=p^tart; //kimentjük a felülírandót P^.tart:=x; //új elem R^.kov:=P^kov; //a mutatókat utánaállítjuk P^.kov:=R; 21. oldal, összesen: 66 procedure TForm1.Button fel rendClick(Sender: TObject); begin //Rendezett P:=eleje; X:=strtoint(edit1.Text); if (P=nil) then begin new(eleje); //ha üres a lista, eleje mtató létrehozása eleje^.tartalom:=X; //és az első elem feltöltése eleje^.kovetkezo:=nil; //nincs

következő elem end else begin new(Q);new(R); P:=eleje; //P mutató az első elemre mutat if (X<P^.tartalom) then begin //P elé fűzűnk R^.tartalom:=P^tartalom; //P mentése R^.kovetkezo:=P^kovetkezo; //R-be P^.tartalom:=X; //P-be az adat P^.kovetkezo:=R; //R beláncolása end else begin //ha <X lenne, nem tudnánk egyelemű lista esetén egy //ugyanekkora X elemet beszúrni, mert be sem lép //a while ciklusba while (P<>nil) and (P^.tartalom<=X) do begin Q:=P; //Q felülírása P-vel P:=P^.kovetkezo; //P már a következőre mutat end; end; new(R); R^.tartalom:=X; Q^.kovetkezo:=R; R^.kovetkezo:=P; end; end; Keresés procedure TForm1.Button keresClick(Sender: TObject); var n: integer; begin P:=eleje;X:=strtoint(edit2.Text); n:=0; if P^.tartalom=X then listbox1Itemindex:=0; while (p<>nil) and (P^.tartalom<>X) do begin p:=p^.kovetkezo; n:=n+1; if (p=nil) then begin listaz; beep; end else listbox1.Itemindex:=n; end; end; Törlés procedure TForm1.Button

torolClick(Sender: TObject); var kijelolt,sorszam: integer; begin P:=eleje; sorszam:=listbox1.itemindex; if sorszam<>-1 then begin kijelolt:=strtoint(listbox1.items[listbox1itemindex]); while ( P^.tartalom<>kijelolt ) and (P<>nil) do begin Q:=P; P:=P^.kovetkezo; end; if (P=eleje) then eleje:=P^.kovetkezo else Q^.kovetkezo:=P^kovetkezo; P:=nil; listaz; end; end; 22. oldal, összesen: 66 Strázsa-technika Alapelv: definiálható két olyan elem (max és min), amelyek a lánca berakható elemek intervallumának széleit képezik. Ezek a megállási feltételek Így a lista soha nem lesz üres, az ebből származó problémák megoldódtak. Nem rendezett keresés While (p<>nil) and (P^.tart<>x) do P:=P^kov; If p=nil then nincs else van Kör adatszerkezet A lista utolsó eleme nem nilre, hanem egy másik lista elejére mutat. A másik lista vége pedig ennek az elejére. Így csak a belépési pontot kell megjegyezni A kétirányú láncolt lista

Visszafelé is van mutató, oda-vissza is tudunk lépkedni. Rendezettségnél jól használható Felszabadítás P:=eleje; eleje:nil; While p<>nil do begin Q:=P; P:=P^.kov; Dispose(Q); End; 4. Bináris Fa (adatszerkezet, felépítés, bejárások, törlés, gyakorlati haszna, alkalmazási példák) Adatszerkezet A fa egy összefüggő körmentes gráf, tehát bárhonnan bárhová el lehet jutni rajta. Irányított, mert van egy gyökérpontja és ágai is. A gyökérpontba nem megy él, csak innen indulhat ki. A bináris fa egy dinamikus (és rekurzív) adatszerkezet. Egy-egy levélpontja áll egy tartalom mezőből, egy bal –és egy jobb mutatóból. Felépítése: Az első elemfelvételnél a gyökérponthoz viszonyítva balra tesszük az elemet ha a gyökérnél kisebb, és jobbra, ha nagyobb. A többi elemfelvételnél ugyanígy először a gyökérponthoz viszonyítunk, majd elmegyünk az egyik irányba. Ha itt van már elem, azzal is összehasonlítjuk az új elemet, és

elrakjuk annak a megfelelő oldalára. Elfajult eset: ha növekvő sorrendben vesszük fel az elemeket, egyágú bináris fát kapunk, amellyel a bináris fa már értelmét veszti, hiszen egy ilyen fában átlagosan n/2 lépésben találunk meg egy elemet, ellentétben a kiegyensúlyozott fával, amelyben egy keresés átlagosan log2N ideig tart. 17 8 5 Például ilyen fa esetén az elemek felvitelének egy lehetséges sorrendje: 17, 8, 5, 9, 20, 40. De nem tudhatjuk mindig biztosan, hogy az elemeket milyen sorrendben vették fel. 20 9 40 Bejárások InOrder (bal, gyökér, jobb); PreOrder (gyökér, bal, jobb); PostOrder (bal, jobb, gyökér). Az In/Pre/Post a gyökér feldolgozásának idejére utal. InOrder procedure InOrder(p: pelem); //param.-ként kapott gyökér begin if P<>nil then begin //megállási feltétel InOrder(P^.bal); //rekurzív hívások Kiír(P^.tart); //Tevékenység InOrder(P^.jobb); end; end; A rekurzív hívás mindig eltárolja, hogy P hova

mutatott. Működése: az összes bal oldali elemet feldolgozza, mielőtt a gyökérre kerülne a sor. Rendezett, növekvő listát állít elő. Az előbbi példa esetén: 5, 8, 9, 17, 20, 40 Ha csökkenő, rendezett listát szeretnénk, felcseréljük a bal mutatót a jobbra. 23. oldal, összesen: 66 PreOrder procedure PreOrder(p: pelem); begin if P<>nil then begin Kiír(P^.tart); PreOrder(P^.bal); PreOrder(P^.jobb); end; end; Az ezzel a módszerrel kapott lista alapján a fa rekonstruálható. (Ha ilyen sorrendben vesszük fel az elemeket egy új, üres fába) A példa alapján: 17, 8, 5, 9, 20, 40. PostOrder procedure PostOrder(p: pelem); begin if P<>nil then begin PostOrder(P^.bal); PostOrder(P^.jobb); Kiír(P^.tart); end; end; Először a levélelemeket dolgozza fel. A fa felszabadítása így lehetséges Ha paraméterként nem a gyökérelemet kapja, hanem egy levélpontot, akkor az ez alatti elemeket szabadítja fel, beleértve a levélelemet is. (A

részfa-törlő algoritmust lásd az 5. tételben) A példa alapján: 5, 9, 8, 40, 20, 17. A bináris fa alapja Type pelem=^TFa; TFa=record tart: integer; bal: pelem; jobb: pelem; end; var Form1: TForm1; gyoker, p: pelem; Keresés (a beszúrás algoritmus mutációja) procedure beszuras(x: integer; var p: pelem); begin if p=nil then begin new(P); P^.tart:=x; P^.bal:=nil; P^.jobb:=nil; end else begin if (x<P^.tart) then beszuras(x,P^bal) else if (x>P^.tart) then beszuras(x,P^jobb) else begin Kiír(Már van ilyen elem); beep; end; end; end; Működése: a rekurzív újrahívások során az algoritmus mindig elmegy balra, vagy jobbra, aszerint, hogy kisebb vagy nagyobb a beszúrandó elem az éppen vizsgáltnál. Az újrahívás után a gyökérelem (p) például a bal oldali mutató lesz. Így lehetséges annak a vizsgálata, hogy ez az új gyökérelem mutat-e valahová. Ha nem mutat sehová, ide be lehet 24. oldal, összesen: 66 láncolni az új elemet. Az eljárás

befejeződik Az algoritmus mindaddig lépeget a fán lefelé, amíg kisebb vagy nagyobb az új elem az éppen vizsgáltnál. Ha egyenlőséget talál, hibát jelez. A keresés annyiban módosul, hogy a beláncolás művelete elhagyható, és a hibajelzéshez tesszük azt a tevékenységet, amely a keresett elem megtalálásakor történjen. Például egy függvény visszatérési értéke lehet, hogy egy típusos fájlban hol helyezkedik el a tartalom mezőhöz tartozó adatrekord. A megállás a tevékenység végrehajtása után következik be, mivel nem történik újabb rekurzív eljáráshívás. Iteratív keresés While (P<>nil) and (P^.tart<>X) do begin If P^.tart<X then P:=P^jobb else P:= P^.bal; end; Egy elem törlése Cél: egy elem törlése minimális munkával. A levélelemeket könnyű törölni, mert nincs alattuk semmi. Dispose(p) után a „szülő” elem mutatóit nil-re állítjuk. Az egy leszármazottal rendelkező elemeket is könnyű törölni:

kiláncolás. Nehéz törölni azokat az elemeket, amelyeknek két leszármazottjuk van, mert feltétel a fa tulajdonságainak megtartása. Ebben az esetben a törlendő elem bal oldali részfájának legjobboldalibb elemével kell felülírni a törlendő elemet. Sorrendben ez a kisebb a törlendőnél. Az eljárás hívása: Torol(törlendő, gyökér) procedure torol(x: integer; var p: pelem); var q: pelem; procedure tor(var R: pelem); begin if R^.jobb<>nil then tor(R^jobb) else begin Q^.tart:=R^tart; Q:=R; R:=R^.bal; end; end; //a részfa legjobboldalibb eleméig megy //törlendő eltárolása //R mutatóinak eltárolása //ráláncoljuk a balra lévő elemeket begin if p=nil then form1.Label1Caption:=Nincs ilyen elem else if (x<P^.tart) then torol(x,P^.bal) else if (x>P^.tart) then torol(x,P^.jobb) else begin //ha nem kisebb és nem nagyobb a törlendő elem Q:=P; //az éppen nézettnél, akkor ki kell láncolni if (Q^.jobb=nil) then P:=P^.bal else if (Q^.bal=nil)

then P:=P^.jobb //ha egyik mutatója sem nil, else tor(Q^.bal); //2 elem van alatta, TOR elj dispose(Q); //a korábban eltárolt törlendő elemet felszabadítjuk end; end; Részfa törlése Procedure reszfa(var p: pelem); Begin If P<>nil then begin If P^.bal<>nil then reszfa(P^bal); If P^.jobb<>nil then reszfa(P^jobb); Dispose(P); P:=nil; End; End; 25. oldal, összesen: 66 Működése: kap egy csomópontot, amely alatt törli a részfát. (PostOrder típusú bejárás) Gyakorlati haszna: a bevezetőben foglalt előnyök alapján Alkalmazási példák: binfa+típusos fájl összekapcsolás Bináris Fa és Típusos Fájl Összekapcsolás Cél: nagyobb adatmennyiség gyors elérése háttértárról, a keresés megvalósítása log 2N lépésben. Módszer: Legyen egy név szerint rendezett típusos fájl. Ebben a logaritmikus keresés használható. Hátránya, hogy csak egy szempont szerint lehet egy időben rendezett a fájl (fizikailag). Új elem felvétele,

törlése a rendezettség megtartásának kényszere miatt lassú. A bináris fa tulajdonságai: gyors keresés, törlés, beszúrás; a memóriában van, ezért gyors a többi művelet is; ugyanakkor a memória véges, az összes adatot nem tárolhatjuk itt (könnyen is sérülhet); csak egy szempont építhető fel egyszerre; ha nem kulcsmező alapján keresünk, lassú. Megoldás: indexelés. A bináris fában csak egy kulcsmező szerepel (amely szerint rendezett a fa), továbbá egy index, amely a kulcsmezőhöz tartozó adatrekord helyét mutatja meg a típusos fájlban. A típusos fájl így lehet rendezetlen. Így megvalósul a két adatszerkezet előnyeinek ötvözete: gyorsaság, nagy tárolókapacitás. A gyakorlatban annyi bináris fát rendelünk a fájlhoz, ahány szempont szerint kell majd keresni. A keresés megindításakor dinamikusan bomlik le a régi, és épül fel az új fa Inicializálás gyoker:=nil; for i:=1 to filesize(f) do begin read(f,rec);

beszuras(rec.marka,gyoker,i-1); end; A fenti példában (i-1) az adatrekordnak a fájlban elfoglalt helyét mutatja meg. Így előnyösebb, hiszen a típusos fájl nullától indexelődik. Az első „beszúrás” eljáráshívás után lehetne írni a többi fa felépítését, ha szükséges. Keresés Megjegyezzük egy változóban, hogy hol helyezkedik el az adatrekord a fájlban. procedure KeresFaban(var p: pelem; keresett: string); begin if P<>nil then begin KeresFaban(P^.bal,keresett); if P^.tart=keresett then begin number:=P^.sorszam; end; KeresFaban(P^.jobb,keresett); end; end; Új elem felvétele Meg kell nézni, hogy van-e már ilyen elem a fán. Ha van, hibaüzenet, egyébként felfűzzük a fára és a fájlba (a végére) is. A beszúrás eljárásban megvan már az egyenlőségvizsgálat, ezzel külön foglalkozni nem kell. Törlés Az indexeléses törlés annyiban bővül ki a hagyományos bináris fás törléshez képest, hogy a fából való elemtörlés

előtt megjegyezzük az adatrekordjának helyét, és azt is kitöröljük a fájlból. Konkrét módszer: a keresés eljárással megnézzük, hogy van-e egyáltalán ilyen elem. Ha van, akkor kitöröljük a „töröl” eljárással a fából majd a fájlban a hozzá tartozó adatrekordhoz lépünk, majd az utolsó adatrekorddal felülírjuk azt. Listázás adatrekordokkal együtt A bejárások segítségével a Tevékenység részben a megfelelő adatrekordhoz lépünk, és kiírjuk a tartalmát. /seek(f, P^.sorszam); read(f,rec); kiír(rec);/ Fontos, hogy ne a rekurzív eljárásban legyen a fájlnyitás, mert feleslegesen lassítja a végrehajtást. 26. oldal, összesen: 66 Módosítás Ha nem kulcsmezőt kell módosítani, egyszerűen rákeresünk a fában, megkapjuk a fájlbeli helyét, majd itt módosítjuk. Ha kulcsmezőt kell módosítani, megnézzük, hogy a módosított változat rajta van-e a fán (ilyenkor nem fűzhetjük fel). Ha nincs, kitöröljük a fából,

majd újra felfűzzük Az index változatlan marad, csak a fájlban kell megváltoztatni a kulcsmező értékét. Tippek Ha kénytelenek vagyunk azonos nevű elemeket felvinni a fára (például azonos felhasználónév: Kovács Alajos), akkor lássuk el ezeket egyedi azonosítókkal, amelyeket a felhasználó nem lát (pl. Kovács2) Módszer: a bináris fában nem csak a név mező szerepel azonosítóként, hanem a cím is. Ebben az esetben pontosabban tudunk keresni (bár lehet, hogy ez a cím is megegyezhet). A logikai törlés megvalósítása pakolás segítségével: az eredeti fájlt *.bak kiterjesztéssel elmentjük, majd a nem törölt elemeket átmásoljuk az új fájlba, amely a régi nevét örökli. Így a teljes adatállomány csak manuális törléssel távolítható el 5. B-fa (alapvető szabályok, új elem felvitel, keresés, törlés) A bináris fa hátrányai • Ha rendezett adatokat feszünk fel, akkor egy része elfajulhat, a keresés lelassul • Ha sok adatot

szeretnénk tárolni a fában, lehetséges, hogy nem fér el a memóriában. Ekkor lemezen kéne tárolni: a lemezről olvasás sokkal lassabb A B-fa (Bayer, 1972) A B-fákban a csúcsoknak sok gyerekük lehet, akár több ezer is. A B-fák elágazási tényezője sokkal nagyobb, mint a bináris fáké, ezért magasságuk lényegesen kisebb. Ha a B-fa egy X csúcsa N[X] kulcsot tartalmaz, akkor az X-nek N[X]+1 gyereke van. Ha a B-fákban egy kulcsot keresünk, akkor (N[X]+1)-féle választásunk lehet, mert a keresett kulcsot N[X] kulccsal hasonlítjuk össze. A B-fa magassága a benne lévő csúcsok számának növelésekor csak a csúcsszánok logaritmusával nő. Tulajdonságai • A kitöltöttségi faktor (a redundáns adatok száma) 50%-nál jobb a B-fa esetében • Egy lemez-szektorba bele kell férjen a fa egy mezejének tartalma, így pl. a BlockRead eljárással gyors adatkezelés valósul meg • Minden lap legfeljebb 2n tételt tartalmaz (n jelenti a B-fa rendjét) •

Minden lapon -a gyökérlapot kivéve- legalább n tétel van • Egy lap lehet levél (utód nélküli) vagy n+1 utóddal rendelkezik, ahol n a kulcsok száma • Minden levél-lap ugyanazon a szinten helyezkedik el 19.3 ábra Egy 2 magasságú B-fa, amelynek több, mint egymilliárd kulcsa van Mindegyik belső csúcsnak és levélnek 1000 kulcsa van. Az 1 mélységben 1001 csúcs van, a 2 mélységben több, mint egymillió levél található. Minden x csúcsban n[x], azaz az x-ben levő kulcsok száma is látható. 27. oldal, összesen: 66 Beszúrás A B-fa t minimális fokszáma 3, ezért egy csúcsnak legfeljebb 5 kulcsa lehet. Azokat a csúcsokat, amelyeket a beszúrás alatt módosítottunk, halványabban sötétítettük. (a) A példában szereplő fa kezdeti állapota. (b) A B beszúrásának az eredménye; ez egy egyszerű eset, egy levélbe kellett beszúrni. (c) Az előző fába egy Q kulcsot szúrtunk be Az RSTUV csúcs két részre bomlott, az RS és az UV

csúcsokra, a T a gyökércsúcsba ment, és a Q a baloldali új csúcsba (RS-be) került. (d) Az előző fába egy L kulcsot szúrtunk be A gyökércsúcsot fel kellett bontani, mivel már telített volt, így a B-fa magassága eggyel nőtt. Ezután az L kulcsot a JK-t tartalmazó levélbe szúrtuk be (e) Az előző fába az F kulcsot szúrtuk be. Az ABCDE csúcsot szétvágtuk, és ezután az F kulcsot a jobboldali új csúcsba (DE-be) szúrtuk be. Törlés 28. oldal, összesen: 66 29. oldal, összesen: 66 A B-fa minimális fokszáma t = 3, így a csúcsoknak (a gyökércsúcsot kivéve) nem lehet kettőnél kevesebb kulcsa. A módosított csúcsokat kevésbé sötétítettük be (a) A 197(e) ábrán látható B-fa. (b) Az F törlése Ez az leset: egy egyszerű törlés a levélből (c) Az M törlése. Ez a 2a eset: L-t, ami az M megelőzője, felvisszük az M helyére (d) A G törlése. Ez a 2c eset: A G-t levisszük, és elkészítjük a DEGJK csúcsot, majd a G-t

kitöröljük ebből a csúcsból. (e) A D törlése Ez a 3b eset: a rekurziót nem lehet levinni a CL csúcsba, mivel annak csak 2 kulcsa van, ezért a P-t kell levinni, egyesíteni a CL-t és a TX -et a CLPTX csúcsba; ezután a D törölhető a levélből (1. eset) (e) A (d) után a fa gyökércsúcsát töröljük, ezzel a fa magassága eggyel csökken. (f) A B törlése Ez a 3a. eset: A C elfoglalja a B helyét, E pedig a C pozícióját 1. Ha a k kulcs az x csúcsban van, és x egy levél, akkor az x kulcsot töröljük az x-ből 2. Ha a k kulcs az x csúcsban van, és x a fa egy belső csúcsa, akkor a következőket kell végrehajtani: a. Ha y az x-nek gyereke, y tartalmaz egy k-t megelőző kulcsot, és y-nak legalább t kulcsa van, akkor keressük meg az y gyökércsúcsú részfában a k-t közvetlenül megelőző k kulcsot. Rekurzívan töröljük k-t, és helyettesítsük k-t k -vel az xben (A k megkereséséhez és törléséhez egy lefelé haladó menet elegendő) b.

Szimmetrikusan, ha a z gyerek következik az x-beli k után, és z-nek legalább t kulcsa van, akkor keressük meg a z gyökércsúcsú részfában a k-t közvetlenül követő k kulcsot. Rekurzívan töröljük k -t, és helyettesítsük k -t k -vel az x -ben (A k megkereséséhez és törléséhez egy lefelé haladó menet elegendő.) c. Egyébként, ha mind y -nak, mind z -nek csak t - 1 kulcsa van, akkor egyesítsük k-t és a z kulcsait y-ba, úgy, hogy x-ből töröljük a k-t és a z-re mutató pointert. Ekkor y -nak 2t - 1 kulcsa lesz. Ezután szabadítsuk fel z -t és rekurzívan töröljük k -t az y -ból. 3. Ha a k kulcs nincs benne az x belső csúcsban, akkor határozzuk meg annak a megfelelő részfának a ci[x] gyökércsúcsát, amelyben a k biztosan benne van, ha egyáltalán benne van k a fában. Ha ci[x] -nek csak t - 1 kulcsa van, akkor hajtsuk végre a 3a vagy a 3b pontban leírtakat, mivel biztosítani kell azt, hogy annak a csúcsnak, amelyre lelépünk,

legalább t kulcsa legyen. Ezután a műveletet az x megfelelő gyerekén rekurzióval befejezhetjük. a. Ha ci [x] -nek csak t- 1 kulcsa van, de van egy testvére, melynek t kulcsa van, akkor vigyünk le ci[x]-be egy kulcsot x-ből, a ci[x] közvetlen baloldali vagy jobboldali testvérétől pedig vigyünk fel egy kulcsot x-be, és vigyük át a megfelelő gyereket a testvértől a ci [x] -be. b. Ha c2 [x] -nek, és a ci [x] minden testvérének t - 1 kulcsa van, akkor egyesítsük ci -t az egyik testvérével, és utána vigyünk le egy kulcsot x -ből ebbe az egyesített csúcsba, ez a kulcs lesz az egyesített csúcs középső kulcsa. Mivel egy B-fában a kulcsok többsége levelekben van, valószínű, hogy a törlés műveletek nagy része levelekből töröl kulcsot. Ekkor a B-FábóL-TÖRÖL eljárás a fában lefelé haladó, egymenetes, visszalépés nélküli procedúra. Azonban, ha egy belső csúcsból kell egy kulcsot törölni, az eljárás egy lefelé haladó menetben

megy le a fában, de utána visszatér abba a csúcsba, ahonnan egy kulcsot törölt, azért, hogy ezt a megelőző vagy követő kulccsal helyettesítse (2a. és 2b eset) Bár ez az eljárás bonyolultnak tűnik, egy h magasságú B-fára a lemezműveletek száma 0(h), mivel csak 0(1) LEMEZRŐL-OLVAS és LEMEZRE-ÍR műveletet hajt végre az eljárás rekurzív hívásai között. A szükséges központi egység idő O(th) = O(t logt n) 6. Sor és verem adattípus és műveletei (statikus és dinamikus megvalósítás) A sor A sor olyan sorozat, amelynek az egyik végére lehet tenni új elemeket, a másik végéről pedig el lehet venni őket. Amit először tettem be, azt veszem ki először Angolul First In First Out (FIFO). Így működik pl a billentyűzet puffere A sor jellegű adatszervezés során általában ugyanolyan típusú adatokat használunk. A HOVA azt mutatja meg, hogy melyik helyre rakhatunk elemet, a HONNAN pedig, hogy hol van a következő kivehető elem. u 5 4 3

2 1 S(N): n elemet tartalmazó sor Műveletek: Eljárás (Üresre állítás) HOVA:=1 ; HONNAN:=1 Eljárás vége. /Ha 30. oldal, összesen: 66 HOVA=HONNAN akkor a sor üres./ Eljárás (SORBA(x)) Ha HOVA>N akkor HIBA(„betelt a sor”) különben S(HOVA):=x ; HOVA:=HOVA+1 Ha vége Eljárás vége. /x az új elem/ Problémák: csak egyszer megyünk végig a soron, ezért nem veszi észre ha berak-kivesz, hogy vannak szabad helyek. Nem hatékony Ez kiküszöbölhető ha léptetjük a tömböt (lassú) vagy, ha új változót vezetünk be, ami a sor elemszámát tartalmazza (db). Javítva: Eljárás (SORBA(x)) Ha db>=MAX akkor HIBA Különben S(HOVA):=S(HONNAN); db:=db+1; Ha (HOVA=MAX) akkor HOVA:=1 (visszaáll az elejére) Eljárás(SORBÓL(x)) Ha HONNAN=HOVA akkor HIBA(„üres a sor”) különben x:=S(HONNAN) ; HONNAN:=HONNAN-1 Ha vége Eljárás vége. Javítva: Eljárás(SORBÓL(x)) Ha db=0 akkor üres Különben MIBE:=S(HONNAN) MIBE:=MIBE-1; Ha (HONNAN=MAX) akkor

HONNAN:=1 (visszaáll az elejére) A Verem A verem olyan sorozat, amelynek csak az egyik végét tudjuk kezelni, oda tehetünk be új elemet és onnan vehetünk ki elemet. Amit legutoljára tettünk be, azt kell kivenni először. Ez angolul Last In First Out (LIFO) A vele végezhető műveletek: a verem tetejére való ráhelyezés és a verem tetejéről való levétel. Megszakítások kezelésekor, és eljáráshívások visszatérési címének tárolásakor használjuk. d c b a PUSH(x): tegyünk be adott elemet POP(x): kiveszünk egy elemet úgy hogy fizikailag is kikerüljön TOP(x): A verem tetején lévő elem vizsgálata V: array[1.max] of integer; (a verem tömbös megvalósítása) VM: A veremmutató (ha a következő szabad helyet mutatja, akkor a leghatékonyabb) Ha VM=1, a verem üres. Minden beírás előtt meg kell nézni, hogy nem fogunk-e túlcsordulni. Műveletek: Eljárás (TOP(x)) (Üresre állítás) VM:=1 Eljárás vége. 31. oldal, összesen: 66 Eljárás

(PUSH(x)) Ha VM>max akkor HIBA („betelt a verem”) különben V(VM):=x ; VM:=VM+1 (berakjuk az új elemet(x) és növeljük a veremmutató értékét) Ha vége Eljárás vége. Eljárás (POP(x)) Ha VM:=1 akkor HIBA („üres a verem”) különben VM:=VM-1 ; x:=V(VM) (csökkentjük a mutatót, majd kivesszük az elemet) Ha vége Eljárás vége. 13. Rekurzió, visszalépéses keresés (8 királynő, huszár útja a sakktáblán) Rekurzió A programozási nyelvekben a rekurzióról akkor beszélünk, amikor egy program saját magát hívja (önrekurzió), vagy ha több alprogram hívja egymást (kölcsönös rekurzió). A rekurzív problémák rekurzív alprogrammal viszonylag egyszerűen megoldhatók, azonban ez a megoldás idő és memóriaigényes. Minden rekurzív problémának létezik iteratív megoldása is (és fordítva), amely általában nehezebben programozható, de több szempontból hatékonyabb a rekurzív megoldásnál. A program futása során az alprogram minden

újabb hívásakor újabb memóriaterületet foglal le a veremben a paraméterek és a változók tárolására, ami a memória elfogyásához vezethet. Az ismétlődő hívások miatt pedig a számítási idő nő meg Ha egy feladat rekurzív megoldásának létezik egy viszonylag jól programozható iteratív (ciklusos) párja, akkor mindig az utóbbi használata javasolt. A rekurzió végrehajtása során egy úgynevezett báziskritériumot (megállási feltételt) adunk meg, amikor a függvény vagy eljárás már nem hívja meg önmagát. Faktoriális A rekurzív működés jól tanulmányozható a faktoriális számítás algoritmusán (nem tipikusan rekurzív feladat). A faktoriális rekurzív definíciója n! = 1, ha n=0 n*(n-1)!, ha n>0 Pl. 4! Kiszámítása 4! = 4*3! 3! = 3*2! 2! = 2*1! 1! = 1*0! 4! = 4*321 = 24 Az általános függvény Function fakt rek(n: integer): integer; Begin If (n=0) then result:=1; Else result:=n*fakt rek(n-1); End; A fenti példában az n=0

feltétel a rekurzió befejezésének feltétele. Ekkor az utoljára hívott függvénypéldány 1 értéket ad vissza. Ezt követően a hívási lánc tagjai sorban visszatérnek a megfelelő részeredménnyel. Utoljára a lánc első eleme, az általunk hívott függvény fejezi be működését, megadva a kívánt faktoriális értéket. A faktoriális iteratív definíciója 0! = 1 n! = n(n-1)(n-2).(n-k+1) Az általános függvény Function fakt it(n:integer): longint; Begin S:=1; For i:=1 to n do S:=S*i; Result:=s; End; 32. oldal, összesen: 66 Fibonacci A Fibonacci-féle számsorozat 0,1,1,2,3,5,8,13,21,34,. (a sorozat egy új eleme az előző kettő összegéből képezhető) Megoldás rekurzióval Lefelé haladva egyszerűsítjük az értékeket, amíg Fib(0)=0 vagy Fib(1)=1 nem lesz az eredmény. Ezen megoldás hátránya, hogy nem veszi észre, ha már egy részeredményt kiszámolt. Function Fib(n: integer): integer; Begin If (n=0) then result:=0 Else If (n=1) then

result:=1 Else Result:=Fib(n-1)+Fib(n-2); End; Ha a sorozat 1-ről indul, és nem 0-ról, akkor: if (n=0) or (n=1) then result:=1; Vagy: if (n<2) then result:=1; Megoldás iterációval Funtion Fib it(n: integer): integer; Begin UE:=1; U:=1; {Utolsó Előtti, Utolsó elem} {A sorozat 1-ről indul} For i:=3 to n do begin F:=U+UE; UE:=U; U:=F; End; Ackermann A kétváltozós Ackermann-függvény: A(x,y). Már A(10,10) esetén is nagy számokat generál, és egyre több számítást igényel. Ha (m=0) akkor A(0, n)=n+1 Ha (m>0) és (n=0) akkor A(m, 0):=A(m-1, 1) Ha (m>0) és (n>0) akkor A(m, n):=A(m-1, A(m, n-1)) Visszaléptetéses keresés (egy megoldás, összes megoldás) Általános feladat: adott N sorozat, amelyek rendre M(1), M(2), . elemszámúak Ki kell választani mindegyikből egy-egy elemet úgy, hogy az egyes sorozatokból való választások más választásokat befolyásoljanak. Tulajdonképpen ez egy bonyolult keresési feladat: egy adott tulajdonsággal

rendelkező szám N-est kell keresni. A megoldást úgy készítjük el, hogy ne kelljen az összes lehetőséget végignézni! Először megpróbálunk az első sorozatból választani egy elemet, ezután a következőből, s ezt mindaddig csináljuk, amíg a választás lehetséges. Amikor áttérünk a következő sorozatra, akkor jeleznünk kell, hogy ebből még nem próbáltunk elemet választani. X(I) jelöli az első sorozat kiválasztott elemének sorszámát, ha még nem választottunk, akkor értéke 0 lesz. Ha nincs jó választás, akkor visszalépünk az előző sorozathoz, s megpróbálunk abból egy másik elemet választani. Ez az egész eljárás vagy úgy ér véget, hogy minden sorozatból sikerült választani (ekkor megkaptuk a megoldást), vagy pedig úgy, hogy a visszalépések után már az első sorozatból sem lehet újabb elemet választani (ekkor a feladatnak nincs megoldása). A megoldás egyszerűbbé válik, ha tudjuk, hogy van megfelelő tulajdonságú

elemsorozat. Általános algoritmus Eljárás I:=1 Ciklus amíg I>=1 és I<=N Ha VAN JÓ ESET(I) akkor I:=I+1 ; X(I):=0 különben I:=I-1 Elágazás vége 33. oldal, összesen: 66 Ciklus vége Ha I>N akkor VAN Eljárás vége. Az első sorozatból úgy választunk elemet, hogy próbálunk mindaddig új elemet venni, amíg van további elem, és az éppen vizsgáltat nem lehet választani. Ha a keresgélés közben a sorozat elemei nem fogytak el, akkor az előző szintnek mondhatjuk azt, hogy sikeres volt a választás. Ha pedig az utolsó sem felelt meg, akkor azt, hogy vissza kell lépni az előző sorozathoz. VAN JÓ ESET(I): Ciklus X(I):=X(I)+1 amíg X(I)<=M(I) és ROSSZ ESET(I,X,(I)) Ciklus vége Ha X(I)<=M(I) akkor VAN JÓ ESET Eljárás vége. ROSSZ ESET(I,X(I)): J:=1 Ciklus amíg J<I és (J,X(J)) nem zárja ki (I,X(I))-t J:=J+1 Ciklus vége Ha J<I akkor ROSSZ ESET Eljárás vége. A backtrack algoritmusra alapozva a keresési feladatokhoz hasonlóan

el lehet készíteni eldöntési, kiválasztási, megszámolási, kiválogatási feladatok megoldását, sőt még a valamilyen szempontból legjobb megoldás megkeresését is. 8 királynő Adott nxn-es sakktáblán helyezzünk el n vezért úgy, hogy semelyik kettő sem üsse egymást. Nem lehet: 2,3. Lehet: 1,4,5 A megoldás módjai: valamely szisztéma szerint lépésről lépésre az összes lehetőséget kipróbáljuk (szisztematikus); vagy próbálgatással (heurisztikus). Algoritmus (egy megoldás) Procedure Probal(i: integer, var Q: boolean) Var J: integer; Begin Repeat J:=J+1; If Y[J] and A[I+J] and B[I-J] then begin X[I]:=J; Y[J]:=false; A[I+J]:=false; B[I-J]:=false; If (I < 8) then begin Probal(I+1, Q); If not Q then begin Y[J]:=true; A[I+J]:=true; B[I-J]:=true; End; End; Else Q:=true; End; Until Q or (J=8); End; Magyarázat Q: ha találtunk megoldást, igazzá válik I: a szintet tárolja, és megőrzi az értéket J: lokális változó, az utolsó próbálkozás

helyének sorát tárolja Y,A,B,X: globális változók 34. oldal, összesen: 66 J:=J+1: végigmegy az összes lehetséges soron, egészen J=8-ig Y[J]: logikai változókat tartalmazó tömb A[I+J]: mellékátlók (az indexek összege) B[I-J]: főátlók (az indexek különbsége) X[I]:=J: Letesszük az elemet. Így X tömb I-edik eleme J lesz Az (I,J) pozícióba tettünk elemet Y[J]:=false: megjegyzi, hogy a J-edik sor foglalt A[I+J]:=false: megjegyzi, hogy a mellékátlókba már nem tehetünk elemet B[I-J]:=false: megjegyzi, hogy a főátlókba már nem tehetünk elemet If (i<8): Mivel még nem jutottunk el a 8. Oszlopba (csak ott találhatunk megoldást), nem vagyunk készen. Egy szinttel feljebb lépünk {probal(i+1,Q)} a globális keretekkel If not Q: ellenőrzi, hogyan léptünk vissza. Ha nincs találtunk, akkor is visszalépünk, de Q értéke igaz lesz. megoldás, Q értéke hamis. Ha Y[J]:=true; A[I+J]:=true; B[I-J]:=true: Ha nem találtunk megoldást (Q

értéke hamis), levesszük a tábláról a most felhelyezett elemeket, mivel ez az elrendezés nem ad megoldást. A sorok és átlók felszabadulnak Else Q:=true: Ha Q értéke igaz, elértünk a 8. oszlopba, megoldást találtunk Until Q or (J=8): Mivel Q igaz, befejeződik a repeat ciklus, és az eljárás is. Visszalép egészen az 1-es szintig, az eredmény pedig az X tömbben jelenik meg. Ha Q hamis volt, a következő sorral próbálkozik, egészen 8-ig, s a ciklus emiatt áll le. Megvalósítás Y: array[1.8] of boolean; A: array[2.16] of boolean; B: array[-7.7] of boolean; Mindegyiket for ciklusok segítségével kell igazra állítani. A Q kezdőértéke hamis Grafika: If Q then ’X tömb kirajzolása’ Algoritmus (összes megoldás) Aránylag gyorsan megoldható az összes megoldása keresése. Procedure probal(i: integer) Var j: integer; Begin Ciklus k=1-től n-ig {k az adott szint, minden lehetőséget végigpróbál} k-adik jelölt kiválasztása ha megfelel, akkor

jegyezzük fel ha i<n akkor probal(i+1); {ha nem vagyunk kész, következő szint} különben a megoldás kinyomtatása {ha elértük n-t} feljegyzés törlése {mindenképp töröljük, ha találtunk megoldást, akkor is} ciklus vége end; A huszár útja a sakktáblán (egy megoldás) Procedure probal(i: integer; x,y: integer; var Q:boolean); Var k,u,v: integer; Begin k:=0; Repeat k:=k+1; u:=x+A[k]; v:=y+B[k]; if (u>=1) and (u<=8) and (v>=1) and (v<=8) and H[u,v]=0 then begin H[u,v]:=i; If (i<n*n) then begin Probal(i+1,u,v,Q) If not Q then H[u,v]:=0; End; Else Q:=true; End; Until Q or k=8 End; 35. oldal, összesen: 66 Magyarázat Az i változó tárolja, hogy hányadik szinten vagyunk. Megoldás esetén i=n*n lesz, leraktuk az összes elemet. Az x és y jelöliazt a pozíciót, ahova letettünk elemet A H tömb tárolja a megoldást, a Q értéke true, ha találtunk megoldást, u és v pedig az utolsó próbált hely koordinátái. A k változó tárolja, hogy

az adott szinten hányadik próbálkozásnál tartunk. (a szisztematikus próbálkozás változója) Egy pontból maximum 8 lépés lehet (ha pont középen van), így ha ezt végigpróbáltuk, új szintre lépünk. (k:=k+1) Az x+A[k] a k által kijelölt pozícióba lép, ide fog mutatni u és v (v:=y+B[k]). If (i<n*n): Ha rajta vagyunk a sakktáblán, és szabad H[u,v]:=i, feljegyezzük a megoldást, hogy hányadik lépéssel kerültük oda. If not Q: ha még nem vagyunk készen, újrahívjuk az eljárást. Töröljük az előző lépést Ha Q igaz, megnéztük a 64. helyet is, az until visszalép a legfelső szintre Ha k<8, próbálja a következőt. Az A és B tömb a relatív elmozdulásokat tárolja: hova tud a huszár elmozdulni. Ez maximum 8 lehetséges irányt jelent. Algoritmus (összes megoldás) Procedure probal(i: integer) Var k: integer; Begin For k:=1 to 8 do begin If (A[k]) and (B[i+k]) and (C[i-k]) then begin X[i]:=k; A[k]:=false; B[i+k]:=false; C[i-k]:=false;

If i<8 then probal(i+1); End Else kiírás(x) A[k]:=true; B[i+k]:=true; C[i-k]:=true; End; End; Kezdeti értékek Q:=false, H tömb nullázása, H[1,1]:=-1 (az első huszárt le kell tenni 1,1 pozícióra) Probal(2,1,1,Q): először az i értéket (2) írja be az első elmozdított pozícióba 8. Hasító táblázatok Hasító függvények HASÍTÓ TÁBLÁZATOK A hasító táblázat a tömb fogalom egyszerű általánosítása. A tömbelemek közvetlen címzése lehetővé teszi, hogy egy tetszőleges pozíción levő elemet hatékonyan vizsgálhassunk meg. Amikor az aktuálisan tárolt kulcsok száma a lehetséges kulcsok számához képest viszonylag kicsi, akkor a hasító táblázatok igen hatékonyak, mivel a legtöbb esetben a tárolt kulcsok számával arányos méretű tömböt használnak. A tömb elemeinek közvetlen címzésére a kulcs helyett egy, a kulcsból kiszámított érték szolgál. Megjegyzések Ha például az egyes kulcsokat úgy képezzük, hogy a karakterek

ASCII kódjait összeadjuk, akkor nem kapunk egyértelmű megoldást, mivel több kulcs ugyanoda mutathat, ha ugyanolyan (de más sorrendben levő) karakterekből áll. Az ütközés feloldása: az egy kulcshoz tartozó elemeket láncolt listába fűzzük fel. 36. oldal, összesen: 66 Egy hasító függvény akkor jó, ha egyenletesen képez le, sűrűsödéseket, csomókat a táblázatban. (a címtér mérete korlátozott) és nem hoz létre Közvetlen címzésű táblázatok A közvetlen címzés akkor alkalmazható, amikor lefoglalhatunk egy akkora tömböt, amelyben minden lehetséges kulcsnak megfelel egy tömbelem. Ez a technika viszonylag kis méretű kulcsuniverzumokra jól működik. Tegyük fel, hogy egy alkalmazáshoz olyan dinamikus halmazra van szükségünk, melyben az elemek kulcsai az U={0,1,,m-1} univerzumból valók, ahol m nem túl nagy. Tegyük fel még, hogy nincs két egyforma kulcsú elem. A dinamikus halmaz megvalósítására egy T[0m-1] tömböt

használunk, amely maga a közvetlen címzésű táblázat. A táblázat minden helye (rés) megfelel az U univerzum egy kulcsának. Pl a k rés a halmaz k kulcsú elemére mutat Ha a halmaz nem tartalmaz k kulcsú elemet, akkor T[k]=nil. Műveletek KÖZVETLEN CÍMZÉSŰ KERESÉS Return T[k] (T,k) KÖZVETLEN CÍMZÉSŰ BESZÚRÁS (T,x) T[kulcs(x)]=x KÖZVETLEN CÍMZÉSŰ TÖRLÉS (T,k) T[kulcs(x)]=NIL Ha az elemeket magukban a résekben tároljuk, akkor valamilyen módon el kell tudnunk dönteni, hogy egy rés üres-e. Hasító táblázatok Ha az U univerzum nagy, akkor egy |U| méretű T táblázat tárolása a gépek memóriájában nem célszerű vagy lehetetlen. Fennáll továbbá, hogy az aktuálisan tárolt elemek K halmaza az U-hoz képest olyan kicsi lehet, hogy a T által elfoglalt hely nagy része kihasználatlan. Amikor a szótárban tárolt kulcsok K halmaza sokkal kisebb a lehetséges kulcsok U univerzumánál, akkor a hasító táblázatnak jóval kisebb memóriára

van szüksége, mint a közvetlen címzésű táblázatnak. A hasító függvény célja, hogy csökkentsük a szükséges tömbindexek tartományát. |U| számú index helyett most csak m-re van szükség. A memóriaigény is ennek megfelelően csökken. Megtörténhet, hogy két elem ugyanoda képződik le, vagyis ütközés van. Az ütközések kiküszöböléséhez a H hasító függvényt kell megfelelően megválasztani. Természetesen egy hasító függvénynek determinisztikusnak kell lennie: egy adott k elemre ugyanazt a h(k) kulcsot kell előállítania. Ütközésfeloldás láncolással A láncolásnál az ugyanarra a résre leképeződő elemeket összefogjuk egy láncolt listába. A j. rés egy mutatót tartalmaz, amely a j címre leképződő elemek listájának fejére mutat Amennyiben ilyen elemek nincsenek, akkor a j. rés a NIL-t tartalmazza Műveletek LÁNCOLT-HASÍTÓ-BESZÚRÁS (T,x) Beszúrás a T[h(kulcs(x))] lista elejére 37. oldal, összesen: 66

LÁNCOLT-HASÍTÓ-KERESÉS (T,k) A k kulcsú elem keresése a T[h(k)] listában LÁNCOLT-HASÍTÓ-TÖRLÉS (T,x) X törlése a T[h(kulcs(x))] listából HASÍTÓ FÜGGVÉNYEK Jó egy hasító függvény akkor, ha minden kulcs egyforma valószínűséggel képződik le az m rés valamelyikére. A gyakorlatban heurisztikus technikákat használhatunk a jól működő hasító függvények készítésére. A hasító függvény értékét úgy állítjuk elő, hogy várhatóan független legyen az adatokban esetleg meglévő szabályszerűségektől. A kulcsok természetes számokkal való megjelenítése A legtöbb hasító függvény azt tételezi fel, hogy a kulcsok univerzuma a természetes számok halmaza. Ekkor keresnünk kell egy módszert arra, hogy a kulcsokat természetes számokként jelenítsük meg. Például a karaktersorozat kulcsokat tekinthetjük megfelelő számrendszerben felírt egészeknek. A pt azonosítót (112,116) ASCII kódokkal felírva, és a 128-as

számrendszerben felírt egészként tekintve pt a (112x128)+116=14452 számmal azonosítható. Mivel a legtöbb esetben található hasonlóan egyszerű módszer, a továbbiakban felételezzük, hogy a kulcsok természetes számok. Az osztásos módszer Egy k kulcsot úgy képezünk le az m rés valamelyikére, hogy vesszük k m-mel való osztásának maradékát. Azaz a hasító függvény a következő: h(k)=k mod m Ha például a hasító táblázat mérete m=12 és a kulcs k=100, akkor h(k)=4. Mivel ez a módszer egyetlen osztást igényel, ezért igen gyors. Ne legyen például m 2 hatvány, mert ilyenkor h(k) éppen k legalacsonyabb helyértékű bitje. A 10 hatványok elkerülendők akkor, ha decimális számokat használunk kulcsként, mivel ilyenkor a hasító függvény nem függne a k összes decimális jegyétől. Jó értékek m számára a 2 hatványokhoz nem túl közeli prímek. Pl a 701 A szorzásos módszer Két lépésben működik. Az elsőben beszorozzuk a k

kulcsot valamely A (0<A<1) állandóval, és vesszük a kA törtrészét. Ezután ezt az értéket beszorozzuk m-mel és vesszük az eredmény alsó egészrészét. Röviden a hasító függvény értéke a következő: h(k)=[m(kA mod 1)], ahol kA mod 1 a kA törtrészét, vagyis (kA-[kA])-t jelenti. A szorzásos módszer előnye, hogy itt az m értéke nem kritikus. Általában valamely 2 hatványnak választjuk. Így a legtöbb gépen könnyen megvalósíthatjuk a függvényt Bár ez a módszer az A állandó minden értékére működik, bizonyos értékekre jobban. Az optimális választás a tárolt adatok jellegétől függ. Knuth azt írja, hogy az A≈ 5 −1 ≈ 0,6180339887. 2 érték valószínűleg jól fog működni. 38. oldal, összesen: 66 Például legyen k=123456, m=10000, és A a Knuth-féle érték. Ekkor: h(k) = [10000 x (123456 x 0,61803 mod 1)] = [10000 x (76300.0041151 mod 1)] = ε[10000 x (0,0041151)] = [41,15] = 41 Az univerzális hasítási

technika Ha a kulcsokat szándékosan úgy választjuk, hogy mindig ugyanarra a résre képződjenek le, akkor a keresés átlagos ideje a legrosszabb. A hasonló esetek elkerülésére az egyedüli hatásos megoldás, ha a hasító függvény véletlenül, azaz a kulcsoktól független módon működik. Ez az univerzális hasítási technika, amely jó átlagos teljesítményhez vezet Alapgondolata az, hogy a hasító függvényt egy megtervezett függvényosztályból a futás során, véletlenül választjuk ki. A véletlenség garantálja, hogy ne legyen egy olyan előre megadható bemenet, amely mindig a legrosszabb viselkedést váltja ki. Legyen H hasító függvények egy véges rendszere, melyek ez adott U kulcsuniverzumot a {0,1,,m-1} tartományba képeznek le. Egy ilyen kollekciót univerzálisnak hívunk, ha tetszőleges x, y ε U különböző elemekből álló kulcspár esetében azoknak a hε H hasító függvényeknek a száma, melyekre h(x)=h(y) pontosan |H|/m. Tehát

a kulcsok közötti ütözés valószínűsége ugyanaz, mint a {0,1,,m-1} halmazból véletlenül kiválasztott h(x) és h(y) egyenlőségének valószínűsége. Egy megfelelő univerzális hasító függvény: r ha ( x) = i = 0 aixi mod m ∑ A nyílt címzés A nyílt címzés esetében az elemeket magában a hasító táblázatban tároljuk. A táblázat elemeinek tartalma vagy a dinamikus halmaz egy eleme vagy pedig a NIL. Egy elem keresésénél rendre végignézzük a táblázat réseit mindaddig, amíg vagy megtaláljuk a kívánt elemeit, vagy rájövünk, hogy az elem nincs a táblázatban. Ez egy idő után betelhet. A beszúrást úgy hajtjuk végre, hogy a hasító táblázat réseit egymás után megvizsgáljuk, amíg ürest nem találunk, amibe a kulcsot betehetjük. HASÍTÓ-BESZÚR(T,k) I=0 Ciklus j=H(k,i) Ha (T[j]=nil )vagy (törölt) akkor T[j]=k Kilépés Különben i=i+1 Amíg i=m Ha (i=m) akkor túlcsordulás, nem lehet berakni az új elemet HASÍTÓ-KERES I=0

Ciklus J=H(k,I) Ha T[J]=k akkor result=J Kilépés Különben i=i+1 Amíg (I=m) vagy (T[J]=NIL) Ha (T[J]=k) akkor Megvan A nyílt címzéses törlés kissé nehezebb. Amikor töröljük az i résben lévő kulcsot, nem elegendő a NIL beírása, mert ha csak ezt tennénk, akkor lehetetlen lenne minden olyan kulcs visszakeresése, melynek beszúrása során az i. rést kipróbáltuk és foglaltnak találtuk. Egy lehetséges megoldás az, hogy a töröltség jelölésére a NIL helyett egy másik értéket, a TÖRÖLT-et használjuk. Ennek megfelelően a HASÍTÓ-BESZÚR eljárást úgy kell módosítani, hogy a TÖRÖLT értékű réseket is kezelje; megengedve hogy kulcs kerüljön beléjük. Három olyan technika van, amit a nyílt címzésnél széles körben használnak kipróbálási sorozatok előállítására: a lineáris kipróbálás, a négyzetes kipróbálás és a dupla hasítás. Mindegyikük garantálja, hogy bármely k kulcs esetében az (h(k,0),h(k,1),,h(k,m1)) sorozat

a (0,1,,m-1) sorozat permutációja legyen Ezen technikák egyike sem teljesíti az egyenletes hasítási feltételt, hiszen egyikük sem tud m 2-nél több kipróbálási sorozatot létrehozni (az egyenletes esetben elvárt m! helyett). A dupla hasító adja a legtöbb kipróbálási sorozatot, és a legjobb eredményt. A lineáris kipróbálás 39. oldal, összesen: 66 Ha adott egy h : U {0,1, .,m - 1 } közönséges hasító függvény, akkor a lineáris kipróbálás módszere az alábbi hasító függvényt használja (i = 0,1, . m - 1): h(k,i) = (h(k) + i) mod m. Egy adott k kulcs esetén az első kipróbált rés T[h(k)]. A következő kipróbált elem a T[h(k)+1], és így tovább egészen a T[m - 1] résig. A lineáris kipróbálást könnyű megvalósítani, de kellemetlen hátránya is van, az elsődleges klaszterezés jelensége. Hosszú, elemek által teljesen kitöltött sorozatok jönnek létre; melyek megnövelik az átlagos keresési időt. A négyzetes

kipróbálás A négyzetes kipróbálás a következő alakú hasító függvényt használja: h(k.i) = (h(k) + c1i + c2i2) mod m, ahol (ahogy a lineáris kipróbálásnál) segédállandók és i = 0,1, . , m - 1 későbbi pozíciók az őket megelőzőkből a eltolással kaphatók meg. Ez a módszer kipróbálás. h egy kisegítő hasító függvény, c1 és c2 ≠ 0 Az először kipróbált pozíció itt is T[h(k)]:, a próbaszámtól négyzetesen függő mennyiséggel való sokkal hatékonyabban működik, mint a lineáris A dupla hasítás A dupla hasítás az egyik legjobb nyílt címzéses módszer; mivel az általa használt kipróbálási sorozatok a véletlen permutációk sok tulajdonságával rendelkeznek. A dupla hasítás a következő alakú hasító függvényt használja: h(k,i) = (h1(k) + i∙h2(k)) mod m, ahol hl és h2 kisegítő hasító függvények. A h2(k) értéknek relatív prímnek kell lennie a táblázat m méretéhez képest. Beszúrás dupla hasítási

technika esetén. Hasító táblázatunk legyen 13 hosszú, hl(k) = k mod 13 és h2(k) = 1 + (k mod 11). Mivel 14 ≡ mod 13 és 14≡3 mod 11, ezért a 14 kulcsot a 9. résbe szúrjuk be, mivel az 1. és 5. rés megvizsgálásakor azokat már foglaltnak találtuk. 9. Gráfok ábrázolási módjai Szélességi keresés Mélységi keresés Topologikus rendezés A Gráf - - pontok és élek halmaza o irányított ( ) o súlyozott (az élekhez számértéket rendelünk) csak az a fontos, hogy két pontot összeköt –e él vagy nem Szomszédsági lista : - irányított gráfnál csak azt írjuk fel, akit el lehet írni súlyozott kiegészítjük egy költséggel o pl.: tárolás láncolt lista előny: hatékony, tömör tárolás hátrány: nehéz meghatározni, hogy két pontot összeköt-e él csúcsmátrix : 1 2 3 4 5 1 2 3 4 5 0 1 0 0 1 1 0 1 1 0 0 1 0 1 0 0 1 1 0 0 1 0 0 0 0 1 1 2 5 3 2 4 5 40. oldal, összesen: 66 főátlóra szimmetrikus tárolás

főátló + alatti vagy feletti elemek irányított nem szimmetrikus ha nem súlyozott, akkor a tárolás igaz, hamis (1 bit) súlyozott beírjuk a költségeket - Gráfból fa - úgy építjük fel a fát, hogy minden elemnek az elődjét fogjuk tárolni - kitüntetett pont kezdőpont - szinezés : o fehér : ahol még nem jártunk o szürke : ahol már jártunk, de még nem jártuk be az összes szomszédját o fekete : bejártuk minden szomszédját B C D A E J I F H G 1.) minden elem fehér - szomszédsági listás megoldás / ADJ(u) soradatszerkezet / //u lista 2.) beírjuk, hogy „J” 1 távolságra van „A” –tól d[u] –melyik szinten vagyunk T[u] – ki volt az elődje 3.) [A, J, D, B] /kivesszük (befeketítjük) az A-t 4.) [J, D, B] 5.) fehér keresés( I ) ( J fekete) 6.) [D, B, I, C] Szélességi Keresés Ciklus minden U∈V [G] – S kezdőpont minden csúcsra Szín(U) ← fehér D(U) ← 0 T(U) ← NIL Csúcs D(S) ← 0 T(S) ← NIL Q ← {sor, amit

kiinduló állapotban S-re állítottunk} /V[G] : csúcsok halmaza /← : jelentése := Ciklus amíg Q nem üres U ← Fej (Q) Ciklus minden V∈ Adj(U) /U minden szomszédjára Ha Szín (V) := fehér Akkor Szín (V) ← szürke d(V) := d(U) +1 π(V) ← U /mutasson U-ra, megjelöljük, hogy honnan jöttünk SORBA (Q, V) elágazás vége Ciklus vége SORBÓL (Q) /kivesszük az első elemet a sorból Szín Q ← fekete Ciklus vége UtKiir (G, S, V) If V = S Then /két csúcs között megtalálja az utat Print S Else If π (V) = NIL Then 41. oldal, összesen: 66 Print nincs út S és V között Else UtKiir(G, S π(V)) Print V End. Mélységi Keresés gráfban d(U) elérési ideje f(U) elhagyási ideje (ha ezt az elhagyási időt zárójelezésre használjuk, akkor szintaktikailag helyes) d(U) időpont előtt a csúcs színe fehér d(U) f(U) között a csúcs színe szürke f(U) után a csúcs színe fekete MK (G) /MK : mélységi keresés, G : gráf Ciklus minden U∈V (G)

csúcs Szín (U) := fehér /nem előd fával állunk szemben, π (U) ← NIL hanem diszjunkt fákkal idő ← 0 Ciklus vége Ciklus minden U∈V (G) csúcsra Ha szín (U) = fehér /ha ilyen színű Akkor MK Bejár (U) Elágazás vége Ciklus vége Eljárás vége MK Bejár (U) Szín (U) ← szürke d(U) ← idő; idő := idő +1 Ciklus minden V∈ Adj(U) –ra Ha szín (U) = fehér Akkor π (V) ← U MK Bejár (V) Elágazás vége Ciklus vége Szín (U) ← fekete f(U) ← idő; idő := idő + 1 eljárás vége /beállítjuk szürkére /elérés időpontja / V csúcs fekete bármikor zokni karóra alsónadrág cipő Topologikus Rendezés : - irányított gráf (nincs kör) - a topológikus gráf csak erre értelmezett pl.: konvencionális divat - nadrág ing öv nyakkendő nincs megkötve, hogy összefüggő legyen a gráf a mélység és a sem Topológikus Rendezés (G) MK (G) minden V csúcsra meghatározzuk az f(V) elhagyási időt Az egyes csúcsok elhagyásakor /ezeket

a csúcsokat/ egy láncolt lista elejére szúrjuk be ezt a V csúcsot eredmény ez a láncolt lista Szomszédsági lista : zokni alsónadrág nadrág zakó cipő karóra 42. oldal, összesen: 66 10. Prim algoritmus, Kruskal algoritmus Minimális feszítőfák Adott egy G irányítatlan, összefüggő, súlyozott gráf. A G gráf egy feszítőfája tartalmazza G összes csúcsát, valamint az élek egy olyan részhalmazát, amelyre teljesül az, hogy a keletkező gráf összefüggő, és nem tartalmaz kört. Nyilvánvalóan ilyen fából több is lehet. A minimális feszítőfa probléma az, hogy meg kell találni a minimális összsúlyú feszítőfát. Ha súlyozatlan gráfról van szó (azaz mindegyik élnek a súlya egységnyi), akkor nyilván mindegyik feszítőfa összsúlya ugyan akkora, mégpedig V-1. Tehát ezentúl feltesszük azt, hogy a gráf súlyozott. Példa: V={a,b,c,d,e,f,g,h,i} E={(a,b,4), (a,h,8), (b,c,8), (b,h,11), (c,d,7), (c,f,4), (c,i,2), (d,e,9),

(d,f,14), (e,f,10), (f,g,2), (g,h,1), (g,i,6), (h,i,7)} Egy minimális feszítőfája: {(a,b), (b,c), (c,d), (c,f), (c,i), (d,e), (f,g), (g,h)}, aminek az összsúlya 37. A minimális feszítőfa növelése: A minimális feszítőfa algoritmusok mohó jellegűek. Az algoritmus működés közben mindig az egyik minimális feszítőfa egy részét tartja nyilván. Ezt a feszítőfát nyilván előre nem ismerjük, viszont egy tétel alapján biztosak lehetünk abban, hogy ez valóban minimális feszítőfa. Minden lépésben meghatározunk egy (u,v) élt, amely még nem része az aktuális feszítőfa-kezdeménynek, viszont ha hozzávesszük, akkor továbbra is teljesülni fog az, hogy van olyan minimális feszítőfa, amelynek része a most keletkezett fa. Az ilyen élt biztonságos élnek nevezzük, mivel a feszítőfa-kezdeményhez hozzávéve továbbra is feszítőfa-kezdemény marad, nem rontja el azt. Az alap algoritmus tehát nagyon egyszerű: MFF() A=üres while az A nem

feszítőfa keressünk egy biztonságos (u,v) élet A-ra nézve A=A U {(u,v)} return A A biztonságos (u,v) él keresésekor ilyen él biztosan létezik, mivel feltétel az volt, hogy A része egy minimális feszítőfának. Az algoritmus legérdekesebb része, hogy hogyan ismerjük fel a biztonságos éleket, és hogyan találjuk egy ilyet hatékonyan. Definíciók: • Vágás: V-nek egy (S,V-S) kettéosztása • Az (u,v) él keresztezi a vágást, ha annak egyik végpontja S-ben van, a másik pedig (V-S)-ben • Egy vágás kikerüli az A élhalmazt, ha az A egyetlen éle sem keresztezi a vágást • Egy él könnyű a vágásban, ha a vágást keresztező élek közül neki van legkisebb súlya Tétel, amire az algoritmusok épülnek: Adott egy irányítatlan, súlyozott gráf. Legyen A a gráf élhalmazának egy olyan részhalmaza, amely része valamely minimális feszítőfának. Legyen (S, V-S) tetszőleges, A-t kikerülő vágása a gráfnak. Legyen (u,v) könnyű él az (S,

V-S) vágásban. Ekkor az (u,v) él biztonságos él A-ra nézve A Kruskal algoritmus Egy erdőt fogunk addig élekkel bővíteni, amíg fát nem kapunk. Alapból a gráf minden egyes pontja külön fát alkot, tehát nincs él az erdőben. A főciklus minden egyes lépésében kiválasztjuk a legkisebb súlyú olyan élet, amely két különböző fát köt össze. Ehhez könnyedén találunk olyan vágást, amely kielégíti a tétel feltételeit, tehát az biztonságos él lesz. Ezért ezzel az éllel bővítjük az erdőt Ezt addig ismételjük, amíg kész nem lesz a fa. KRUSKAL() A=üres for minden v eleme V-re HALMAZT-KÉSZÍT(v) rendezzük az E éleit súlyuk szerint nemcsökkenő sorrendbe for minden (u,v) eleme E élre, az előbb kapott sorrendben if HALMAZT-KERES(u)!=HALMAZT-KERES(v) A=A U {(u,v)} EGYESÍT(u,v) return A 43. oldal, összesen: 66 A halmazműveleteket sokféleképpen meg lehet valósítani. A HALMAZT-KERES(u) azt a halmazt adja vissza, amelyben az u

található. Az EGYESÍT(u,v) egyesíti azt a két halmazt, amelyben az u és a v található. A Prim algoritmus Ebben az esetben egy fát bővítünk addig, amíg nem kapjuk meg az eredeti gráf egy feszítőfáját. Egy tetszőleges pontból indulunk ki; kezdetben csak ebből az egy pontból fog állni a fa. A vágást a fában levő pontok határozzák meg: azok kerülnek az egyik osztályba, a többi pont meg a másikba. E két osztály közötti egy könnyű élet választunk Technika: mindegyik pont mellé írunk egy kulcsértéket. Ez alapértelmezésben mindegyik pont esetén végtelen lesz, kivéve egy tetszőleges kezdőpontot, ahol 0. Mindegyik pontnak lesz egy ős mezője, amely a kezdőpont esetében NIL lesz. Egy prioritási sorba (pl kupac) beletesszük az összes pontot. A KIVESZ-MIN a kulcsérték szerinti minimális pontot fogja visszaadni. Amíg a prioritási sor nem üres, addig minden egyes lépésben kivesszük a minimális értékű pontot, és azon szomszédjait

fogjuk megvizsgálni, amely benne van még Qban, azaz a vágás másik oldalára esik. A vizsgált ponthoz egyébként biztosan illeszkedik olyan él, amely minimális a vágásban, ugyanis pont emiatt minimális. A szomszédjainak az ős és kulcs mezőit aktualizáljuk. Az ős nyilván a vizsgált pont lesz, a kulcs pedig az aktuális kulcsérték és a két pontot összekötő él súlyának a minimuma. Pszeudokód (r a kezdőpont, w a súlyfüggvény): PRIM(r) Q=V for minden v eleme Q-ra kulcs[v]=végtelen kulcs[r]=0 ős[r]=NIL while Q nem üres u=KIVESZ-MIN(Q) for u minden v szomszédjára if v eleme Q és w(u,v)<=kulcs[v] ős[v]=u kulcs[v]=w(u,v) return ős // JAVA // 11. Osztályok és objektumok Osztály- és példányváltozók Osztály- és példánymetódusok Heap, konstruktorok, objektumok felszabadítása Példányváltozók és metódusok leírása Az osztály példányosításával keletkezik az objektum, egyed vagy példány. Az adatokat és az őket kezelő

műveleteket egységbe zárjuk. Az adatokat elrejthetjük más osztályok műveletei elől (adatelrejtés) Egyszerű példa public class Alkalmazott { // Az osztály tagjai: adattagok és metódusok // A class elott módosítók szerepelhetnek String nev; int fizetes; void fizetesDuplaz() { fizetes *=2; } void fizetesEmel(int nov) { fizetes += nov; } } Alkalmazott alk; // Deklaráció alk = new Alkalmazott(); // Példányosítás a konstruktor meghívásával alk.nev = "Harapós Kutya"; // Hivatkozás a példányváltozókra alk.fizetes = 30000; alk.fizetesDuplaz(); // Metódus meghívása 44. oldal, összesen: 66 Példányváltozók Változók deklarációja int fizetes= 30000, potlekok, levonasok = fizetes/5; // inicializálni lehet a példányváltozókat final double ADOKULCS = 20; // A final módosítóval konstanst hozunk létre. Változók használata Az osztály metódusaiban az adattagokra a nevükkel hivatkozunk Más objektum adattagjára minősített névvel

hivatkozhatunk: masik.fizetes Pl. Az alkalmazott osztályban definiált tobbetKeresMint metódus: boolean tobbetKeresMint(Alkalmazott masik) { return fizetes > masik.fizetes; } Metódusok Metódusok definíciója Fej + törzs Fej: visszatérés típusa (ha nincs, akkor void), név, formális paraméterek. Metódus szignatúrája: név és a formális paraméterek listája típusokkal és sorrendhelyesen Metódus név előtt módosítók lehetnek: public , protected, private, abstract. Pl. boolean kozepesJovedelmu (int minimum, int maximum) { return fizetes >= minimum && fizetes < maximum; } Formális paraméterek: lokális változók (érték paraméterek) (final módosító használható) Minden paraméternek külön kell megadni a típusát. Paraméterlista lehet üres is, () akkor is kell. Ha nincs visszatérési típus, a void szót kell a metódus név elé tenni. Metódusok meghívása Mindig konkrét példányra hívjuk meg. alk.fizetesDuplaz(); A metóduson

belül minősítés nélkül hívhatjuk meg az osztály metódusait: void automatikusFizetesEmel() { if (kozepesJovedelmu(30000, 60000)) fizetesEme;(5000); } A this pszeudováltozó Metódustörzsben az aktuális objektumra a this pszeudó változóval hivatkozhatunk. Metódusnevek túlterhelése Több azonos nevű metódus is írhatunk az osztály definíción belül, de ezeknek szignatúrájukban különbözniük kell. Ezt a metódus nevek túlterhelésének nevezzük class Alkalmazott { . . void fezetesEmel(int nov) { fizetes += nov; } void fezetesEmel() { fizetes += 5000; } void fezetesEmel(Alkalmazott masik) { if (kevesebbetKeresMint(masik)) fizetes = masik.fizetes; } } Alkalmazott a = new Alkalmazott(), b = new Alkalmazott(); a.fezetesEmel(5000); a.fezetesEmel(); a.fezetesEmel(b); 45. oldal, összesen: 66 Fordítás közbeni adatfolyam ellenőrzés A példányváltozók mindig kapnak kezdőértéket, de a metódusok lokális változói nem feltétlenül, ezért a

fordítóprogram ellenőrzi, hogy adtunk-e kezdőértéket. A nem void típusú metódusokban értékkel bíró return utasítást kell elhelyezni. Ha a fordító számára nem egyértelmű a kezdőértékek megadása, hibát jelez, ekkor explicite meg kell adni. Objektumok használata Az objektum a példányosítással születik meg. Alkalmazott a = new Alkalmazott(); // new után konstruktor Az a referencia az objektumra (referencia típusú változó). Több változó is mutathat ugyanarra az objektumra: Alkalmazott a, b; a = new Alkalmazot(); b = a; a.fizetes = 50000; System.outprintln(bfizetes); // 50000 -t ír ki! Objektumok paraméterként való átadásakor az objektumra 2 referencia van. A formális paraméter referenciája az eljárásból kilépéskor megszűnik. Ha egy változó nem mutat objektumra, a referenciája: null. Ha az objektumra nincs szükségünk, null-ra állítjuk, vagy más értéket adunk neki. Magát az objektumot a szemétgyűjtő mechanizmus (garbage

collector) szabadítja fel. Statikus tagok Az osztály egészére vonatkozó változókat osztályváltozóknak, a metódusokat pedig osztálymetódusoknak nevezzük. Ezeket a static módosító jelöli. Osztályváltozók Egyetlen példányhoz sem kötődnek. Csak 1 létezik belőlük public class Alkalmazott { . static int nyugdijKorhatar = 62; // Osztályváltozó int eletkor; . int hatraVan() { return nyugdijKorhatar - eletkor; } } Alkalmazott a = new Alkalmazott(); a.nyugdijKorhatar = 65; // helyes Alkalmazott.nyugdijKorhatar = 65 // ez is helyes Osztálymetódusok Osztálymetódus csak az osztályváltozókhoz férhet hozzá, a példányváltozókhoz nem! static void nyugdijKorhatarEmel() { nyugdijKorhatar++; } Hívása: a.nyugdijKorhatarEmel(); Alkalmazott.nyugdijKorhatarEmel(); Foprogram public class paramKiir { public static void main(String [] args) { if (args.length > 0) { System.outprintln("Program paraméterek:"); for (int i= 1; i<args.length; i++)

System.outprintln(args[i]); } else { System.outprintln("Nincsenek program paraméterek!"); } } } Konstruktorok Példányosításkor fut le. Ha nem készítünk konstruktort, akkor is van ún implicit konstruktor Konstruktorok definíciója: 46. oldal, összesen: 66 Majdnem olyan, mint egy metódus definíció. Az azonosító kötött, nincs visszatérési típus (void sincs). Csak hozzáférési módosító használható Pl. public class Alkalmazott { . public Alkalmazott (String nev, int fizetes) { this.nev = nev; this.fizetes = fizetes; } public Alkalmazott (String nev) { this.nev = nev; this.fizetes = 20000; } } Az aktuális paraméterek típusa határozza meg, hogy melyik konstruktort kell hívni. Pl. konstruktorból hívható egy másik konstruktor: public Alkalmazott (String nev) { this(nev, 20000); } Példányosítás paraméterekkel Csak olyan paraméter listát adhatunk át a konstruktornak, amelynek megfelelő konstruktort készítettünk. Ha nem írtunk

konstruktort, csak paraméter nélkülit használhatunk. Ha nem írtunk paraméter nélküli konstruktort, csak paraméterezettet hívhatunk Alkalmazott a = new Alkalmazott("Kis Kutya", 50000); Alkalmazott b = new Alkalmazott("Nagy Kutya"); Inicializáló blokkok A változódeklaráció és a metódusdefiníció közé tehető. Lehetnek osztály-inicializátorok és példány-inicializátorok. Az osztály-inicializátor az osztály szintű konstruktort pótolja (mivel ilyen nincs). Példa az osztályinicializátorra: public class Alkalmazott { . static int[] evesSzabadsag = new int [60]; static { for (int i= 0; i<30; i++) evesSzabadsag[i] = 15; for (int i= 30; i<40; i++) evesSzabadsag[i] = evesSzabadsag[i-1] + 1; for (int i= 40; i<50; i++) evesSzabadsag[i] = evesSzabadsag[i-1] + 2 ; for (int i= 50; i<60; i++) evesSzabadsag[i] = evesSzabadsag[i-1] + 1; } . public int evesSzabadsag() { if (eletkor < 60) return evesSzabadsag[eletkor]; else return

evesSzabadsag[59]; } } Destruktor jellegű metódusok Az objektumok megszűnésekor a szemétgyűjtő felszabadítja a lefoglalt helyet, de lehet, hogy bizonyos feladatokat el kell végezni előtte. Erre való a finalize metódus Ez az ősosztály (object) metódusa Az adott osztályban csak felüldefiniáljuk: protected void finalize() throws Throwable ( . } A tárterület felszabadítása elott hívódik meg, de nem lehet tudni, hogy mikor! A finalize metódus osztály színtű megfelelője a classFinalize: 47. oldal, összesen: 66 static void classFinalize() throws Throwable ( . } 12. OOP: egységbe zárás, öröklődés, polimorfizmus Absztrakt osztályok és metódusok Metódusnevek túlterhelése Öröklődés Osztály kiegészítése új tagokkal. Egy létező osztály kiterjesztése: új változók, új metódusok bevezetése. Pl. a Fonok osztály bevezetése az Alkalmazott osztály kiterjesztésével A Fonok osztály rendelkezik mindazon adatokkal és műveletekkel,

amellyel az Alkalmazott osztály, csak kiegészül új adatokkal és műveletekkel. public class Fonok extends Alkalmazott { final int MAXBEOSZT = 20; Alkalmazott [] beosztottak = new Alkalmazott[MAXBEOSZT]; int beosztottakSzama = 0; public void ujBeosztott(Alkalmazott b) ( beosztottak[beosztottakSzama++] = b; ) } Szülő osztály: Alkalmazott (Ős) Gyermek osztály: Fonok (Leszármazott) A gyermek rendelkezik a szülő adattagjaival is, azonban ha azok private típusúak, akkor a gyermek csak az örökölt metódusok segítségével érheti el őket, ha azok nem private-ok. A metódusok öröklése révén kódmegosztás jön létre a szülő és a gyermek között. A konstruktotrok és az öröklődés A konstruktorokat a gyermek nem örökli. Ha nem írunk a gyermekhez új konstruktort, a szülőé hajtódik végre Ha írunk, és nem hívjuk meg explicit a szülő valamelyik konstruktorát, a szülő argumentum nélküli konstruktora hívódik meg. public class Fonok extends

Alkalmazott { . public Fonok(String nev, int fizetes) { super(nev, fizetes); // a szülo kiválasztott konstruktorának végrehajtása } public Fonok(String nev) { this(nev, 50000); // a Fonok másik konstruktorának végrehajtása } } A szülő konstruktorának meghívása megelőzi a gyermek példány változóinak inicializálását, és az inicializáló blokk végrehajtását. Polimorfizmus A gyermek őseinek minden változójával és metódusával rendelkezik. Ezért minden olyan környezetben használható, ahol az ősei használhatók. Egy Alkalmazott típusú változónak értékül adható egy Fonok típusú objektum. Azt a lehetőséget, hogy egy adott típusú változó nemcsak szigorúan a típusának megfelelő, hanem a leszármazott objektumokra is hivatkozhat, polimorfizmusnak (sokalakúság) nevezzük. A változóknak így van statikus és dinamikus típusa. A statikus típus a deklarált típus, a dinamikus, pedig a változó által hivatkozott objektum tényleges

típusa. A változó dinamikus típusa a program során változhat. A polimorfizmus igazi erejét a metódusok felüldefiniálásának lehetősége adja. Példánymetódusok felüldefiniálása: A leszármazottakban szükség lehet bizonyos metódusok átírására, mivel lehet, hogy valamit máshogyan kell tenni, mint az ős példányban. Pl. Az Alkalmazott osztályban és a leszármazottaiban van egy potlek metódus, amely a fizetés kiegészítéseket határozza meg: public class Alkalmazott { . int nyelvekSzama; . public int potlek() { 48. oldal, összesen: 66 return nyelvekSzama*5000; } public int fizetesPotlekokkal () { return fizetes() + potlek(); } } public class Fonok extends Alkalmazott { . public int potlek() { return super.potlek() + beosztottakSzama+1000; } } A Fonok osztály felüldefiniál egy példánymetódust. Oszálymetódusokat nem lehet felüldefiniálni, csak átfedni A gyermek a super minősítővel hivatkozhat a szülő eredeti metódusaira. A

super.potlek() az Alkalmazott osztály potlek metódusát hívja A polimorfizmus tulajdonsága, hogy mindig a dinamikus típus szerinti metódus lesz meghívva. Alkalmazott a = new Fonok("Kovács János"); int p, fp; . p = a.potlek(); fp = a.fizetesPotlekokkal(); // az örökölt fizetesPotlekokkal() metódust hívja, ez azonban a // Fonok potlek() metódusát hívja. A dinamikus kötés lehetővé teszi, hogy a statikus típustól függetlenül, mindig a megfelelő metódus fusson le. Osztálymetódusok elfedése Osztálymetódust nem lehet felüldefiniálni, csak elfedni. Osztálymetódus elfedi az ősökben deklarált, vele megegyező szignatúrájú metódusokat. Az osztálymetódusok hívása nem dinamikus, hanem statikus kötés szerint történik. Változók elfedése Az osztály kiterjesztésekor az ősökben deklarált példány- vagy osztályváltózókat elfedhetjük, azonos nevű változókkal. A gyermek csak minősítéssel férhet hozzá az elfedett

változókhoz. A protected hozzáférési kategória Az ősök public tagjaihoz a leszármazott ugyanúgy hozzáférhet, mint minden más osztály. Az örökölt fél-nyilvános tagokhoz a gyermek csak akkor férhet hozzá, ha az őssel azonos csomagba tartozik. A private tagok el vannak zárva a leszármazottak elől. A protected tagokhoz hozzáférhetnek az azonos csomagban definiált osztályok. Más csomagból csak a leszármazott osztályok férhetnek hozzá a protected tagokhoz. Az osztályhierarchia Az osztályok rokonsági viszonyainak összességét osztályhierarchiának nevezzük. A java.langObject osztály implicit módon minden más osztálynak szülője, amely nem más osztályból származik, vagyis amelynek definíciójában nem adtuk meg az extends tagot. Közvetve minden osztály az Object leszármazottja Az Object osztály azokat a metódusokat tartalmazza, amelyekkel minden osztálynak rendelkeznie kell. Absztrakt osztályok és metódusok Az osztályhierarchia

tetejét alkotó osztályoknak inkább az a szerepük, hogy definiáljanak egy metódus készletet, amelyek a leszármazottakat egysége keretbe foglalják. Ezek többnyire csak specifikálják a metódusokat, de nem implementálják azokat Az ilyen osztályokat absztrakt osztályoknak nevezzük. Ezek tartalmaznak implementáció nélküli metódusokat Az absztakt osztályok nem példányosíthatók. Az absztakt osztályok absztrakt metódusai kiterjesztéskor juthatnak implementációhoz. Az absztakt osztályok annak ellenére, hogy nem példányosíthatók, lehetséges absztrakt típusú változókat deklarálni. Az ilyen változók mutathatnak a leszármazottak objektumaira. public abstract class Sikidom { public abstract double kerulet(); public abstract double terulet(); } public class Kor extends Sikidom { public double r; 49. oldal, összesen: 66 public double kerulet() { return 2*Math.PI*r; } public double terulet() { return r*rMath.PI; } } public class Teglalap extends

Sikidom { public double a, b; public double kerulet() { return 2*ab; } public double terulet() { return a*b; } } Végleges osztályok és metódusok Ha nem akarjuk, hogy egy osztály kiterjeszthető, vagy egy metódus felüldefiniálható legyen, a final módosítót használjuk. Metódusnevek túlterhelése: pl. amikor több konstruktort írunk, a különböző inicializálás érdekében 13. Interfészek implementálása Gyűjtemények, Java csomagok Hozzáférési kategóriák Interfész = új referencia típus, amely absztrakt metódusok és konstansok deklarációjának összessége. Különbség az osztályokhoz képest, hogy hiányoznak a valódi, változtatható adattagok és a metódusok implementációi. Az interfész tehát egy felületet definiál. Ez egy új absztakciós szint bevezetését jelenti A feladat megoldásának bizonyos színtjén el lehet vonatkoztatni a konkrét implementációtól. Ez növeli a megbízhatóságot, könnyíti a tervezést, könnyebb

újrafelhasználható programokat (osztályokat) készíteni. Az interfészt implementációján keresztül használjuk. Egy osztály implementál egy interfészt, ha annak az összes metódusát implementálja. Minden olyan helyen, ahol interfész szerepel típusként, az interfészt implementáló bármilyen osztály példánya felhasználható. Az interfészek közötti öröklődés Az interfészek között is létrehozható szülő-gyermek kapcsolat, ezt kiterjesztésnek nevezzük. Interfészek között többszörös öröklődés (kiterjesztés) is lehetséges (ellentétben az osztályok–kal). Az interfészeknek nincs közös ősinterfésze, mint az osztályoknak az object. Interfészek implementálása class osztálynév [extends ősosztály] implements interfész1, interfész2,* { adattagok konstruktorok metódusok interfész metódusainak implementációja (a metódus feje megegyezik az interfészben deklarálttal) } * a többszörös "öröklést" valósítja meg

Az összes absztrakt metódust implementálni kell! Interfész használata deklarációban Az interfésznév szerepelhet deklarációban, formális paraméterként. A változónév olyan referenciát jelent, amely az interfészt implementáló osztály valamelyik példányára mutat. Interfész deklarációja [interfész módosítók] interface interfésznév [kiterjesztett interfészek] { konstansok deklarációi absztrakt metódusok (csak a metódus fejfe!) } Az interfész neve lehetőleg -ható, -hető -re végződjön, jelezve, hogy az interfész képes megvalósítani a nevében jelzett műveletet. Az -able végződésű nevek interfészt jelölnek. Interfész módosítók abstract (alapértelmezett, nem kell használni) public ( az interfész más csomagból is elérhető) 50. oldal, összesen: 66 Interfész törzs konstans definíciók metódus deklarációk // implicit publikus // implicit publikus Konstansok: [módosítók] típus azonosító inicialzáló

módosítók: típus: alapértelmezés = public, static, final létező típus. Pl char [] c = {a, b, c, d} Absztrakt metódusok Olyan, mint az osztály metódusainak deklarációja törzs nélkül: [] visszatérési típus metódusnév() [kiváltható kivételek] metódus módosítók: public, abstract // nem kell megadni Példa az interfészek kiterjesztésére interface Gyumolcs { void egyedMeg(int i); }; interface Alma extends Gyumolcs{ int színe(); void színÁllít(int i); }; class Jonatan implements Alma { int szín; public void színÁllít(int i) { szín=i; } public int színe() { return szín; } public void egyedMeg(int i) { System.outprintln("Finom volt"); } }; Gyűjtemények (Collections) Java.util csomag: gyűjtemények, gyűjtemény keretrendszer interfészei és osztályai Gyűjtemény keretrendszer (Collections Framework) A Gyűjtemény keretrendszer interfészek és osztályok halmaza, amely lehetővé teszi adatcsoportok egy egységként,

gyűjteményként való tárolását és kezelését. A Gyűjtemény keretrendszer osztályai definiálják objektumok viselkedését, amelyek más objektumokat tárolnak. A gyűjtemények adatelemei Object típusúak, így bármely leszármazottját tárolhatják. Kinyerve az adatelemeket a gyűjteményből az adatok típusa természetesen Object. Típuskényszerítéssel lehet az eredeti típust visszaállítani. A gyűjtemények adatelemei nem lehetnek primitív típusok! Primitív típusú adatokat a csomagoló osztályok objektumaival tároljuk a gyűjteményekben. A gyűjtemények dinamikusan növekednek, rendezett (sorted) adattárolás is lehetséges. Bejárhatjuk az elemeket, miközben hatékonyan adhatunk új elemeket a gyűjteményhez vagy távolíthatunk el elemeket belőlük. 1. Tárolási technológia  Tömb  Láncolt lista (Kétirányú láncolt lista)  Fa  Hash tábla 2. A gyűjtemények tulajdonsága  Rendezett (Sorted) A tárolt objektum valamilyen

tulajdonsága vagy tulajdonságai szerint rendezve vannak tárolva vagy érhetők el az elemek. A rendezéshez az equals() és a compareTo() metódusokat használják.    51. oldal, összesen: 66 Sorrendtartó/nem sorrendtartó (Ordered/Unordered) A tárolt objektumok megtartják a tároláskor kialakult egymáshoz képesti sorrendjüket. Duplikált elemek előfordulhatnak Két azonos értékű (az equals() metódus szerint) objektum előfordulhat a gyűjteményben. Kulcsot használ az azonosításhoz A gyűjteményben tárolt objektumot egy kulcs objektum alapján lehet hatékonyan előkeresni. 3. A gyűjtemény objektumok típusai  Listák (List) A List rendezetlen, sorrendtartó, duplikált objektumok előfordulhatnak. Fizikai tárolás tömbben, láncolt listában lehetséges. Lehetséges osztályok: Stack, ArrayList, LinkedList, Queue (ilyen nincs az API-ban).  Halmazok (Set) A Set nem sorrendtartó és duplikált objektumok nem fordulhatnak elő. 

Leképzések (Map) A Map kulcs és érték objektum-párokat tárol. Az érték objektumokat a kulcs objektum azonosítja. Például Hallgató objektumokat tárolunk a Map-ben és a kulcs objektum lehet a hallgató azonosítója (ID objektum). A Map nem sorrendtartó, duplikált kulcs-elemek nem fordulhatnak elő. Gyűjtemény interfészek és osztályok A négy alapvető interfész származási kapcsolata:     A Collection interfész olyan objektumokat képvisel, amelyek megengedik objektumok duplikálását. A Set a Collection-ből származik, de nem teszi lehetővé a duplikált objektumok tárolását. A List szintén a Collection-ből származik, megengedi a duplikált tárolást és bevezeti az indexelést (sorrend tartó). A Map nem kiterjesztése a Set-nek és a Collection-nak. A Collection interfész (add, remove, size, stb.) Iterator interfész (next, remove, hasnext) Collection collection = .; Iterator iterator = collection.iterator(); while

(iterator.hasNext()) { Object element = iterator.next(); if (removalCheck(element)) { iterator.remove(); // az elemek eltávolíthatók } } Absztrakt gyűjtemény osztályok Lehetővé teszik, hogy új gyűjtemény osztályok készítésekor csak az absztrakt metódusokat kelljen megírni. Az implementált metódusokat megtarthatjuk A Set interfész (add, remove, contains, clear) A Set a Collection-ből származik, de nem teszi lehetővé a duplikált objektumok tárolását. Nincsenek új metódusok. A duplikáltság elkerülését az equals() metódus segítségével végzi. A HashSet és a TreeSet osztályok implementálják a Set interfészt import java.util*; public class SetExample { public static void main(String args[]) { Set set = new HashSet(); 52. oldal, összesen: 66 set.add("Katalin"); set.add("Erzsébet"); set.add("Júlia"); set.add("Márta"); set.add("KLára"); System.outprintln(set); Set sortedSet = new

TreeSet(set); System.outprintln(sortedSet); } } A List interfész és a A Map interfész (clear, get, add) A List szintén a Collection-ből származik, megengedi a duplikált tárolást és bevezeti az indexelést (pozíció orientált). Az ArrayList és a LInkedList osztályok implementálják a List interfészt. import java.util*; public class ListExample { public static void main(String args[]) { List list = new ArrayList(); list.add("Katalin"); System.outprintln(list); System.outprintln("2: " + listget(2)); LinkedList queue = new LinkedList(); queue.addFirst("Katalin "); System.outprintln(queue); queue.removeLast(); System.outprintln(queue); } } Hozzáférési kategóriák Az adattagok és metódusok elérhetősége szabályozható. Félnyilvános tagok A jelöletlen tagokat (adat és metódus) fél-nyilvános tagoknak nevezzük. Ezekre csak az azonos csomagban lévő osztályokból hivatkozhatunk. Nyilvános tagok (public) A public módosítóval

ellátott tagokra bármely osztályból hivatkozhatunk. Ha egy adattagot csak olvasni engedünk meg a csomagon kívülről, az adattagot private-nak jelöljük, és egy public metóduson keresztül tesszük az adatot hozzáférhetővé a csomagon kívülről. Privát tagok (private) A private adattagok csak a példánymetódusokból érhetők el. A private metódusok is csak az osztályból érhetők el. Leszármazottban hozzáférhető tagok (protected) Az ősök public tagjaihoz a leszármazott ugyanúgy hozzáférhet, mint minden más osztály. Az örökölt fél-nyilvános tagokhoz a gyermek csak akkor férhet hozzá, ha az őssel azonos csomagba tartozik. A private tagok el vannak zárva a leszármazottak elől. A protected tagokhoz hozzáférhetnek az azonos csomagban definiált osztályok. Más csomagból csak a leszármazott osztályok férhetnek hozzá a protected tagokhoz. 53. oldal, összesen: 66 14. Kivételkezelés A kivétel keletkezésének módjai, a megfelelő

kivételkezelő keresése, ellenőrzött és nem ellenőrzött kivételek. A kivétel elkapása és specifikálása Object A program futása közben fellépő hibákat kezelni kell: 1. 2. A programot olyan állapotba kell hozni, hogy folytatható legyen. Azt kell tudnunk jelezni a programban, hogy mi történjék bizonyos hiba előfordulása esetén (a kivételes esemény kezelése), és hogy hol folytatódjék a program végrehajtása. Ezt akár többszörös metódushívás esetén is meg kell tudnunk tenni. Pl. ▪ Tömb indextúlcsordulás esetén egy nagyobb tömböt készítünk, az eredeti tömb elemeit átmásoljuk az új tömbbe, majd az eredeti tömböt megszüntetjük. Ezután folytatjuk a program végrehajtását. Throwable Error Exception RuntimeException Nem ellenőrzött Ellenőrzött Nem ellenőrzött ▪ Grafikus kezelői felületet használva egy adatbeviteli mezőbe számot kell bekérnünk. Hibás adat bevitele esetén jelzést adunk, és az adat

helyesbítéséig nem engedjük elhagyni az adatbeviteli mezőt. ▪ Fájlból adatokat olvasunk be a fájl végéig. Ha a fájl vége után is olvasni akarunk, hiba keletkezik Ezt a várható hibát, amely voltaképpen a beolvasás normális befejezését jelzi, kezelnünk kell, majd folytathatjuk a feldolgozást. A kilépés előtt a tisztességes befejezés érdekében néhány dolgot el kell végezni. A Java hibakezelése a kivételkezelésen alapszik (Exception) A kivétel olyan esemény, amely megszakítja a program normális futását, és kivételes módon fut tovább. A kivételt okozhat pl.: háttértároló megtelik, nullával osztunk, tömb indexhatárát túllépjük, illegális konverziót hajtunk végre, nem létező objektum metódusát hívjuk, verem megtelik, fájl vége után tovább olvasunk, fájl olvasása közben hiba keletkezik, a hivatkozott fájl nem létezik, stb. A kivételek kezelése is az osztályokon alapul. Ez a hiba típusától függő

feldolgozást tesz lehetővé A kivétel kezelése Hiba keletkezésekor a futó metódus, amelyben a hiba keletkezett, kiváltja a kivételt: throwing exception (kivétel kiváltása). Ekkor egy kivétel objektum jön létre, amely információt tartalmaz a kivétel fajtájáról és a program állapotáról. Ezután ez az objektum a Java futtató környezet felügyelete alá kerül, amely eljuttatja a programnak arra a pontjára, ahol a kivétel lekezelhető. A kivétel keletkezésének módjai: 1. 2. 3. Futás közben rendellenes dolog történik (pl. osztás 0-val) A program egy throw utasítása váltja ki a kivételt (lehet a könyvtári csomagban vagy a saját osztályainkban) Aszinkron kivétel lép fel, ha a program több szálon fut, és egy szál működése megszakad Az 1. bárhol, 2 és 3 a programnak csak meghatározott helyén léphet fel Ha egy metódus kiváltja az eseményt, a futása megszakad, és a vezérlés nem tér vissza a hiba keletkezésének helyére.

Megfelelő kivételkezelő keresése A kivétel kiváltása után a JVM olyan helyet keres a programban, ahol a kivétel kezelése megtörténhet. A kivételt az a kivételkezelő kódblokk fogja lekezelni, amelynek a hatókörében keletkezett, és amely megfelelő típusú. A kivételkezelő megfelelő típusú, ha az általa kezelt kivétel típusa azonos a kiváltott kivétel típusával vagy őse annak. A kivételkezelő hatókörét a programozó határozza meg. 54. oldal, összesen: 66 Működési mód 1. 2. 3. 4. A kivételkezelő hatókörében hiba lép fel, és egy, a hibának megfelelő típusú kivételobjektum keletkezik. (Ez a kivétel kiváltása) A Java virtuális gép (JVM) megkeresi a megfelelő kivételkezelőt: − először megnézi, hogy a kiváltott kivétel típusa azonos-e vagy leszármazottja a kivétel típus1-nek. Ha igen, akkor az ehhez tartozó kivételkezelő blokk kapja meg a vezérlést. − ha nem, akkor a kivétel típus2-vel, majd kivétel

típus3-mal próbálkozik. A kivételkezelő blokk végrehajtása után végrehajtja a finally blokk utasításait (ha van ilyen) A program a catch, finally blokkok utáni utasítással folytatódik. A try { } blokk végrehajtásának esetei 1. 2. 3. Nem lép fel hiba. A finally blokk ekkor is végrehajtódik (ha van) Hiba lép fel, és valamelyik catch ág lekezeli a hibát. Ezután a finally blokk végrehajtódik (ha van) Hiba lép fel, de nincs alkalmas kivételkezelő. A finally blokk végrehajtódik, majd a hívó metódus kivételkezelőjének adódik át a vezérlés A kivételkezelés alkalmazási köre A Java nyelvnek sok kivételtípusa van: pl. ArithmeticException, ArrayIndexOutOfBoundsException, NumberFormatException, EmptyStackException, EOFException, FileNotFoundException, IOException, NullPointerException A programozó saját típusokat hozhat létre. A kivételek alapvetően 2 csoportba oszthatók: 1. Ellenőrzött kivételek 2. Nem ellenőrzött kivételek Az

ellenőrzött kivételeket: 1. Elkapni, vagy 2. Specifikálni kell, különben fordítási hiba lép fel. Azért vannak nem ellenőrzött kivételek is, mert vannak olyan hibák, amelyek szinte bárhol felléphetnek, kezelésük a Java nyelven belül lehetetlen. Ez csak gondot okozna a programozóknak A kivételek specifikálása Az olyan ellenőrzött kivételeket, amelyeket a metódusban nem kapunk el, specifikálni kell: a metódus fejében ezeket felsoroljuk, jelezve, hogy a metódus hívásakor fel kell készülni ezek elkapására. Pl. metódus () throws kivétel1, kivétel 2, { metódus törzs } Kivételek hiba keletkezésekor váltódnak ki, vagy throw utasítással is kiválthatók! try { kiir(g, tk); } catch (IOException io) {System.outprintln(io + " hiba"); } finally {g.close();} } // ---------------------------------------static void kiir (PrintWriter g, String [] tk) throws IOException { for (int j = 0; j < tk.length; j++) { g.println(tk[j]);

System.outprintln(tk[j]); if (j == 3) throw new IOException(); } } } Kivételosztályok java.lang Throwable java.langError a kiváltható osztályok hierarchiájának csúcsa. Ez és ennek a leszármazottjai a throw utasítással kiválthatók. komoly hiba esetén lép fel. Pl OutOfMemoryError (elfogyott a mermória) Ritkán fordulnak elő. Több leszármazottja van. Az Error leszármazottjai nem ellenőrzött kivételek. 55. oldal, összesen: 66 Ez, és ezek leszármazottai ellenőrzött kivételek (a RunTimeException kivételével). A program teljes hibakezelését lényegében az Exception és leszármazottai segítségével oldjuk meg. A saját kivétel osztályinkat is az Exception-ból célszerű származtatni java.langException Saját kivételosztály létrehozása class VeremMegteltException extends Exception { public int egesz; public VeremMegteltException(int egesz) { this.egesz = egesz; } } 15. Grafikus kezelői felület létrehozása (Java AWT) Komponensek,

konténerek, elhelyezési stratégiák, eseménykezelés. Grafikus kezelői felület létrehozása. A Java Abstract Window Toolkit (AWT) osztály könyvtár támogatja a grafikus kezelői felület létrehozását. Az AWT platform független, de nem olyan kifinomult, mint más fejlesztő rendszerek GUI interfészei. A grafikus felület A grafikus felület komponensekből áll (a komponens osztályok példányai). A komponens osztályok a Component osztály leszármazottai. A komponenseket a konténer osztályok foglalják egységbe. Tehát a komponesek a konténerek egy csoportját kezelik és vezérlik A konténerek a felhasználói eseményeket a komponenseikhez továbbítják. A konténer osztályok a Container osztály leszármazottai. A Container a Component leszármazottja, ezért egy konténer további konténereket tartalmazhat. A konténerek a rendelkezésükre álló helyet a képernyőn az ún. pakolási stratégia alapján osztják fel, vagyis, hol helyezkedjen el a

komponens, és hogyan változzon a mérete, ha a konténer mérete változik. Egy pakolási stratégia a LayoutManeger interfész megvalósítása. A konténerekbe a komponenst a konténer add() metódusával lehet felvenni, és a remove() metódusával lehet eltávolítani. Ha egy konténer komponens listája változik, a validate() metódus hívásával a megjelenítést aktualizálni kell. Konténer osztályok A java.appletApplet a Panel-ből származik A Window keret nélküli, a Frame kerettel rendelkező különálló ablak Egyetlen komponenst tartalmazhat, görgető sávokkal rendelkezik Kommunikáció a felhasználóval dialógus ablakok segítségével: adatbekérés, hiba kijelzés. Mindig egy másik ablakhoz tartoznak Lehetnek modálisak is Panel/Applet Window/Frame ScrollPane Dialog/FileDialog Layout menedzserek FlowLayout: addig pakolja a komponenseket egymás mellé, amíg elférnek, majd a következő sorban folytatja. (Ez az applet alapértelmezett Layout

menedzsere.) BorderLayout: az égtájak szerint és középre helyezhetjük az egyes komponenseket. North West Center South panel.add(komponens, "East"); konténe East GridLayout: 56. oldal, összesen: 66 a komponensek négyzetrácsba kerülnek, amelyeknek a mérete azonos. panel.setLayout(new gridLayout(5, 4)); panel.add(new Button ("1")); panel.add(new Button ("2")); GridBagLayout: egy milliméter papírhoz hasonló rácson minden komponensek egy vagy több cellát foglalhat el. A komponensek kezdő poziciója megadható. List CheckBox TextField Label A kezelése bonyolult. A Layout menedzsert le is lehet tiltani, a komponensek abszolút poziciója is megadható. Eseménykezelés Az eseményeket egy osztályhierarchia kezeli, amelynek gyökere a java.utilEventObject Egy bizonyos típusú eseményhez a gyökérosztály egy neki megfelelő leszármazottja tartozik. Az AWT-beli események a java.awtAWTEvent osztályba tartoznak Az

események egy forrás objektumból származnak, és egy vagy több fogadó objektumnak adódnak át a fogadó objektum megfelelő metódusának meghívásán keresztül. Az eseménykezelés osztályai a java.awtevent csomagban vannak (importálni kell!) Az eseményfajták fogadására interfészeket készítettek. Ha egy osztály megvalósít egy ilyen interfészt, akkor a példányai fogadó objektumok lesznek, vagyis feldolgozzák az ennek megfelelő eseményeket. Ahhoz, hogy a fogadó objektumok megkapják az eseményeket, regisztrálniuk kell magukat az esemény forrásánál. Pl.: Ablak: az eseméy fogadója Bezár Nyomógomb: eseméy forrás Az ablak a Frame osztály leszármazottja. Implementálja az ActionListener interfészt Ez az esemény fogadója Az interfész összes metódusát implementálni kell. Ez esetben csak az ActionPerformed metódust A Bezár nyomógomb az esemény forrása. Ennél kell regisztrálni az ablakot, hogy adja át neki az ActionEvent típusú

objektumot: bezarButton.addActionListener(this) FocusListener interfész metódusai:  focusGained(FocusEvent e)  focusLost(FocusEvent e) 57. oldal, összesen: 66 FocusEvent eseményosztály konstruktora: public FocusEvent(Component source, int id, boolean temporary) a java.utilEventObjectgetSource() metódusával kérdezhető le, hogy kitől származik az esemény ( source.getSource() ) ActionListener interfész metódusai: source:  actionPerformed(ActionEvent e) ActionEvent eseményosztály konstruktora: public ActionEvent(Object source, int id, String command, int modifiers) source: id: command: modifiers: esemény forrása esemény azonosítása parancs sztring billentyűk kombinációja, amelyeket lenyomva tartottunk az esemény keletkezésekor ActionEvent metódusai:   String getActionCommand() int getModifiers() Eventlistener interfészek (java.utilEventListener) ActionListener, AdjustListener, ComponentListener, ContainerListener, FocusListener,

ItemListener, KeyListener, MouseListener, MouseMotionListener, TextListener, WindowListener 16. Java Input/Output Csatornák, leképzés fizikai adatszerkezetre, szűrők, kapcsolat a fájlrendszerrel A Bemenet/Kimenet a Stream (csatorna) fogalmához kapcsolódik. A csatorna olyan adatsorozat, amelyet feldolgozhatunk olvasó műveletekkel, vagy előállít–hatunk író műveletekkel. Lényegében szekvenciális Input/Output. A csatorna egy absztrakciós szint. amely a bemenet/kimenet kezelését függetleníti  az operációs rendszertől,  az eszközöktől, amelyen az adatokat tároljuk (bill., képernyő, file-ok, párhuzamos szálak közti csőcsatorna) Témák: Csatornák Leképzés fizikai adatszerkezetre Szűrők Véletlen elérésű file-ok Kapcsolat a file rendszerrel Kivétel kezelése Csatornák 1. Byte szervezésűek (legkisebb egység a byte) Az osztályok az InputStream és az OutputStream absztrakt osztályok leszármazottai. Pl.: OutputStream: public void

write(byte b []) throws IOException 2. Karakter szervezésűek (karakterek, sztringek) (legkisebb egység a Unicode char) Az osztályok az Reader és a Writer absztrakt osztályok leszármazottai. Pl.: Writer: public void write(char c []) throws IOException Csatorna megnyitása és lezárása Megnyitás: csatorna objektum létrehozása konstruktorral. Írás/Olvasás: a csatorna objektumon kell végrehajtani. Lezárás: a csatorna objektum close() metódusával. import java.io*; FileWriter fout = new FileWriter("adat.txt"); // Kiírás fout.close(); // megnyitás // lezárás 58. oldal, összesen: 66 Kiíró műveletek Karakter csatornára (OutputStreamWriter) write(int c) throws IOException write(char c [], int off, int len) throws IOException write(String s, int off, int len) throws IOException write(char c []) throws IOException write(String s) throws IOException Byte csatornára (Output Stream) absztrakt write(int b) throws IOException (absztrakt) write(byte b[])

throws IOException write(byte b[], int off, int len) throws IOException Kivételek: IOException NullPointerException ArrayIndexOutOfBoundException Olvasó műveletek Karakter csatornára (Reader) int read() throws IOException// 1 karakter beolvasása, blokkolódik,ha nincs //karakter a csatornán; -1, ha csatorna vége int read (char c []) throws IOException int read (char c [], int off, int len) throws IOException beolvasott karakterek Byte csatornára (InputStream) int read() throws IOException// 1 byte beolvasása (absztrakt) int read (byte b []) throws IOException int read (byte c [], int off, int len) throws IOException beolvasott byte-ok Üres csatorna: Nem tartalmaz adatot. Ha beolvasás közben a csatorna kiürül, a read blokkolódik, amíg adat érkezik Végetért csatorna A csatorna vége jelet tartalmazza. Pl.: public static void masol (InputStream in, OutputStream out) throws IOException { int b; while (b = in.read() != -1) outwrite(b); out.flush(); } Leképzés fizikai

adatszerkezetre File-ok (pl.: FileInputStream) Csövek (pl.:, PipedInputStream, PipedOutputStream) Byte- és karaktertömbök, sztringek (pl.: CharArrayWriter) File-ok Karaktercsatorna: FileReader, FileWriter Byte csatorna: FileInputStream, FileOutputStream Konstuktor pl. FileReader(String file név) throws FileNotFoundException FileReader(File file) throws FileNotFoundException FileReader(FileDescriptor fd) Csövek Szálak közti kommunikáció megszervezésére való PipedInputStream- PipedOutputStream vagy PipedReader - PipedWriter összekapcsolásával jön létre 59. oldal, összesen: 66 A csőcsatorna összekapcsolását a bemenet és a kimenet is kezdeményezheti! Pl.: PipedInputStream in = new PipedInputStream(out); // a bemeneti csatorna rákapcsolódik a kimeneti catornára // a kimeneti csatornát előbb létre kell hozni Byte- és karaktertömbök, sztringek byte[] és char[] típusú objektumok adják a csatorna fizikai reprezentációját. Byte csatorna felett

létrehozott karakter csatornák Az InputStreamReader és az osztélyok OutputStreamWriter byte csatorna felett vannak definiálva. Olvasáskor, íráskor a byte-ok automatikusan Unicode-dá (és viszont) konvertálódnak. A konstruktor paramétere dönti el, hogy milyen szabvány szerint kell a konverziót elvégezni. Pl.: Billentyűzetről olvasunk WindowsEE/ISO Latin-2 karaktereket: InputStreamReader in = new InputStreamReader(System.in, "Cp1250"); A File Reader és a FileWriter a fenti osztályok leszármazottai ugyanúgy byte csatorna felett vannak definiálva, de a konstruktoruknak nem adható meg, hogy milyen kódolást használjanak. Az op rendszer alapértelmezett kódolását használja Szűrők Az osztályai nem azt írják le, hogy honnan olvasunk, vagy hová írunk, hanem azt, hogy ezt hogyan csináljuk. Ezekkel egy már meglévő csatornát ruházunk fel különleges tulajdonságokkal. Például a DataOutputStream-mel int-eket írhatun ki (bináris alakban):

FileOutputStream fout = new FileOutputStream("adat.txt"); DataOutputStream dout = new DataOutputStream(fout); dout.writeInt(51); // dout-on keresztül az fout-ra írunk dout.close(); // rekurzíven mindkét csatornát lezárja read() DataInputStream read() a konstruktor paramétere: csatorna InputStream write() DataOutputStream write() OutputStream Szűrőfolyamok A szűrők egymásba ágyazhatók, mivel ezek maguk is csatornák. A szűrőknek ezt a működési elvét delegációnak nevezzük. A szűrőkre meghívott műveleteket úgy hajtják végre, hogy igénybe veszik a szűrendő csatrona szolgáltatásait. Adattípus értéke beolvasása és kiírása A DataInputStream és a DataOutputStream szűrőkkel a Java adattípusait tudjuk beolvasni/kiírni. (Szabványos, gépfüggetlen reprezentáció) DataInputStream int read(byte b[]) throws IOException int read(byte b[], int off, int len) short readShort() int readInt() long readLong() DataOutputStream flush() throws

IOException int size()// eddig kiírt byte-ok writeShort(int v) writeInt(int v) writeLong(long v) Sor beolvasása: a BufferedReader osztály readLine() metódusával javasolt! Véletlen elérésű file-ok (RandomAccessFile) 60. oldal, összesen: 66 Felfogható, mint egy file rendszerben tárolt byte-vektor. Bármelyik pozicióján lévő byte olvasható/írható. File-mutató: ettől kezdődően olvasunk/írunk (automatikusan továbblép!) Lekérdezése: getFilePointer() Beállítása: seek() Tetszőleges adattípus olvasható/írható. Ugyanúgy használható, mint a DataInputStream és a DataOutputStream Kivételek: EOFException IOException A RandomAccessFile konstruktorának a 2. paramétere: "r": csak olvasás "rw": írás/olvasás Kapcsolat a file rendszerrel (File osztály) Információt tartalmaz egy file-ról vagy könyvtárról, és file- és könyvtár kezelési műveleteket lehet végrehajtani a segítségével. Az file tartalmát nem ezzel

dolgozzuk fel! Létrehozása konstruktorral: File f = new File("munka/adat.txt"); File f = new File("adat.txt"); Nem létező állományhoz is létrehozható File objektum! Konstruktorok: File(String út); File(String út, String név); File(File út, String név); 17. Szálak megvalósítása Java-ban Szálak (Thread) Konkurencia megvalósítása folyamaton (programon) belül. A processzor látszólag párhuzamosan futtatja a program szálait. A szálak ütemezését az operációs rendszer végzi a szálakhoz rendelt prioritások alapján. A szálak ütemezése lehet preemptív vagy időosztásos. Preemptív ütemezés esetén mindig a legnagyobb prioritású szál fut, és mindaddig nem adja át a vezérlést más szálnak, amíg be nem fejeződik, blokkolódik (pl. I/O miatt) vagy magasabb prioritású szál kezdi meg életét. Időosztásos (time-sliced) ütemezés esetén azonos prioritású szálak ciklikusan (roundrobin) megkaphatják a vezérlést. Szálak

alkalmazásának értelme lehet egy és több processzoros gépeken is. A program minden szála hozzáférhet a program által ismert valamennyi objektumhoz. A program eljárásai szinkronizálhatók, megakadályozva a szálak összeakadását, azaz lehetővé teszik atomi műveletek elvégzését. Az atomi műveletek elvégzése alatt más szálak nem vehetik át a vezérlést. Például egy banki tranzakció esetén, egy számla megterhelése egy bizonyos összeggel, majd annak jóváírása egy másik számlán atomi műveletnek kell lennie. A folyamatoknak együttműködését biztosítani kell:  Kommunikáció: a folyamatok átadnak egymásnak információt  Szinkronizáció: Ugyanazon az objektumon végzett atomi műveletek nem szakíthatók meg más atomi műveletekkel  Ütemezés: A végrehajtási sorrend szabályozása. Prioritás, lemondás a futásról, szálak összekapcsolása, stb. Példák szálak alkalmazására: Szerver alkalmazások. Több kliens alkalmazás

kiszolgálása hálózaton keresztül Web böngésző több szál segítségével tölti le a képeket a szerverről. Olyan párhuzamosítható alkalmazások, amelyek gyakran blokkolódnak be/kivitel miatt. 61. oldal, összesen: 66 Az alkalmazás egyidejűleg futtatható szálainak számát az operációs rendszer korlátozhatja. Szálak készítése 1. A szál osztályát a javalangThread osztályból származtatjuk Át kell írnunk a Thread osztály run() metódusát. Ez a metódus tartalmazza a szál által végrehajtott kódot. A szál-osztályt példányosítanunk kell, majd az objektum start() metódusával indíthatjuk a szálat. E módszer hátránya, hogy ha a Thread osztályból származtatunk, más osztályból már nem származtatunk az egyszeres öröklés miatt. Lásd: ExtendedThread.java class MyThread extends Thread { MyThread () { super(); } MyThread (String nev) { super(nev); } public void run() { System.outprintln("Helló, ez itt a " + getName()); } }

public class ExtendedThread { static public void main(String args[]) { MyThread a, b; a = new MyThread("1. szal"); b = new MyThread("2. szal"); a.start(); b.start(); } } 2. A szál osztályát úgy készítjük el, hogy implementáljuk a Runnable interfészt Ebben az esetben egyúttal más osztályból is származtathatjuk osztályunkat. Applet szálak készítésekor például csak ezt a módszert használhatjuk. Az interfész run() metódusát kell implementálnunk. E megoldás hátránya, hogy a run() metódust implementáló osztály csak a run() metódushoz férnek hozzá, a Thread osztály metódusaihoz nem. A szál készítése: példányosítjuk a Runnable interfészt implementáló osztályt. Példányosítjuk a Thread osztályt, de a konstruktorának paraméterként átadjuk a Runnable objektumot. A szálat a Thread objektum start() metódusával indíthatjuk el Lásd: RunnableThread.java import java.io*; class Run Thread implements Runnable { public void

run() { System.outprintln("Hell˘, ez itt a " + Thread.currentThread()getName() + " sz l"); } } public class RunnableThread { static public void main(String args[]) { Run Thread szal; Thread a, b; szal = new Run Thread(); a = new Thread(szal); b = new Thread(szal); a.start(); b.start(); } } 62. oldal, összesen: 66 Szálak felfüggesztése A Thread osztály suspend() metódusával lehetséges, és egy másik szál tudja újra futtaható állapotba hozni a szál resume() metódusának meghívásával. A suspend() és a resume() metódusok elavultak (deprecated), használatuk nem javasolt. Szálak megszakítása Hosszú időre blokkolt állapotú szálak megszakítása válhat szükségessé. Erre az interrupt() metódus használható. Szálak leállítása A stop() metódussal lehetséges, de ennek használata nem támogatott (deprecated). Helyette a run() metódus befejezésével célszerű megoldani a szál leállítását. A szál objektumban egy

segédváltozót lehet beállítani, ha a szálat le kell állítani, majd a szál run() metódusa ennek a váltózónak az állapotától teheti függővé, hogy leálljon-e vagy tovább fusson. Szálak prioritása A Jáva tíz prioritási szintet különböztet meg a Thred.MIN PRIORITY - ThredMAX PRIORITY tartományban. Három konstans használható: Thred.MIN PRIORITY = 1 Thred.MAX PRIORITY = 10 Thred.NORM PRIORITY = 5 (alapértelmezett) A szálak prioritása a setPriority() metódussal futás közben is állítható. Szálak összekapcsolása (join) Egy szál megvárhatja, amíg egy másik szál befejezi működését. A Thread osztály join() metódusa használható erre a célra. Használata: xjoin(), ahol x annak a szálnak a referenciája, amely szál futásának befejezését kell megvárnunk. Lásd: JoinTest.java Lemondás a futás jogáról (yield) A Thread osztály yield() metódusának használatával az adott szál lemond a futásról a többi, azonos prioritású szál

javára. Ennek használata nélkül a szál addig fut, amíg le nem telik az időszelete, blokkolódik vagy magasabb prioritású szál futtatható állapotba kerül. Nem minden szálkezelő csomag képes időszeletek használatára a szál-ütemezésben. Ilyen esetben csak a yield() használatával lehet átadni a vezérlést más, azonos prioritású szálnak. Szálak állapotai sleep done sleeping suspend blocked resume new start wait runnable notify block on I/O dead stop Thread állapotok I/O complete Szinkronizáció A szálak osztoznak az adatszegmensen, vagyis a szálak hozzáférnek minden olyan objektumhoz, amelyhez referenciával rendelkeznek. Mivel a szálak egyidejűleg hozzáférhetnek ugyanahhoz az objektumhoz, ütközhetnek egymással. Például egyszerre akarják írni ugyanazt a fájlt, vagy egyszerre hívják egy objektumnak ugyanazt a metódusát és módosítják az objektum állapotát. Ebből hibás objektumok keletkezhetnek, amelyet szinkronizációs

problémának neveznek. Ennek megoldása a közösen használt objektumok szinkronizációjával lehetséges. A szinkronizációs mechanizmus működésének összefoglalása 1. Ha egy osztály egy vagy több szinkronizált metódussal rendelkezik, minden objektumához egy sor lesz hozzárendelve, amely azon a szálakat tartalmazza, amelyek az objektum valamelyik szinkronizált metódusát kívánják végrehajtani. 63. oldal, összesen: 66 2. Két okból kerülhet egy szál a várakozó sorba:   metódust hív, miközben egy másik szál használja az objektumot az objektum használata közben meghívja a wait() metódust. 3. Amikor egy szinkronizált metódus futása befejeződik, vagy egy metódus wait()-et hív, egy másik szál jut futási lehetőséghez. 4. Mint mindig, az ütemező a legmagasabb prioritású szálat választja a futtathatók közül 5. Ha egy szál a wait()-tel került a várakozó sorba, a notify() vagy a notifyAll() metódussal kell ismét

beütemezhető állapotba hozni. A szinkronizáció alkalmazásának gyakorlata 1. Ha két vagy több szál módosít egy szinkronizálni kell. objektumot, a módosítást végző metódust 2. Ha egy szálnak várakoznia kell, hogy egy objektum állapota megváltozzék, az objektumon belül kell várakoznia, belépve egy szinkronizált metódusba, és meghívva a wait()-et. 3. Valahányszor egy metódus megváltoztatja egy objektum állapotát, meg kell hívnia a notifyAll()-t. Ez megadja a várakozó szálaknak az esélyt, hogy megnézzék, vajon a körülmények megváltoztak-e. Deadlock Azt a helyzetet nevezzük deadlock-nak, amikor az összes szál blokkolva mindegyik arra vár, hogy több pénz legyen az általa kezelt folyószámláján. van, mert Ez esetben ez nem következhet be, mivel legalább egy folyószámlán 10000-nél nagyobb összeg van, és az átutalható összeget 10000-ben korlátoztuk. Ha ezt a korlátot megszüntetjük a deadlock hamar bekövetkezik. Egy

másik egyszerű változtatással, amikor az i. szál az i számlára tesz pénzt, ahelyett hogy az i. száláról utalna pénzt, szintén előállítható a deadlock Ez esetben előfordulhat, hogy mindegyik szál ugyanarról az egy száláról akar pénzt leemelni, de nincs elegendő. Thread osztály A szálakat valósítja meg. Konstansok: public final static int MIN PRIORITY: a szál legkisebb prioritása MAX PRIORITY: a szál legnagyobb prioritása NORM PRIORITY: a szál alapértelmezett prioritása Példák Szerver – Kliens alkalmazás egyidejűleg több kliens kiszolgálására ParhuzamosSzerver ParhuzamosClient Óra – Grafikus kezelő felületen a dátum és az idő megjelenítése és frissítése másodpercenként CloseableFrame Idozit Ora 18. Hálózatkezelés Összeköttetés alapú kommunikáció a Java-ban A java.net csomag a kommunikációval és a hálózati erőforrások elérésével kapcsolatos osztályokat tartalmazza Két részre csoportosítható:  

Socket-ekkel kapcsolatos osztályok - A Jáva Socket interfészének segítségével elérhetjük az Interneten használt alapvető hálózati protokollokat URL (Uniform Resource Locator) kezeléssel kapcsolatos osztályok - Segítséget nyújt a hálózati erőforrások eléréséhez. (Pl dokumentumok, programok, egyéb adatállományok) 64. oldal, összesen: 66 Socket-ek  A socket-ek alacsony szintű programozási interfészt nyújtanak a hálózati kommunikációhoz.  A programok közti adatcserét folyamokon keresztül oldják meg.  A Jáva különböző típusú socket-eket biztosít a két alapvetően elkülönülő hálózati protokollra: - kapcsolat-orientált protokoll (Socket osztály) A két program, mint egy telefonon keresztül kommunikálhat egymással, míg a kapcsolatot az egyik fél meg nem szünteti. - kapcsolat nélküli protokoll (DatagramSocket osztály) A kommunikáció csak rövid üzenetek formájában zajlik. Kliensek és szerverek  Azt a

programot nevezzük kliensnek, amelyik a kapcsolatot kezdeményezi, szervernek pedig azt, amely a kapcsolatkérést fogadja.  A Socket osztály egy példánya reprezentálja a kapcsolat egy végpontját a kliens és a szerver oldalon is.  A szerver alkalmazások a ServerSocket osztály egy példányának accept() metódusát használják arra, hogy a kliensek kapcsolatkéréseire várjanak. Ez a metódus hozza létre a klienssel való adatcseréhez szükséges Socket típusú objektumot A szerveralkalmazás egyetlen ServerSocket típusú objektumot használ a különböző kliensekkel való kapcsolatfelvételre, de ezt követően minden egyes klienskapcsolatot már külön Socket típusú objektum jelképez. A kliensek  A klienseknek két információra van szükségük, hogy megtaláljanak, és kapcsolatot teremtsenek egy szerveralkalmazással: - a kiszolgáló gép hálózati címére, és - a kiszolgáló gép azon portcímére, melyen a szerver a kapcsolat-felvételi

kérelmeket várja.  Kapcsolat nyitása a kliens oldalon: try { Socket s = new Socket("donat.bankihu", 25); } catch (UnknownHostException e) { System.outprintln("A szerver nem válaszol!");} catch (IOException e) { System.outprintln("Sikertelen kapcsolatfelvétel!");}  Ha egyszer egy kapcsolatot sikerült felépíteni, akkor kinyerhetjük belőle a kommunikációhoz szükséges folyamokat: try { Socket s = new Socket("donat.bankihu", 5318); OutputStream out = s.getOutputStream(); out.write(33); PrintWriter pr = new PrintWriter(out); pr.println("Helló"); BufferedReader br = new BufferedReader( new InputStreamReader(s.getInputStream())); String st = br.readLine(); s.close(); } catch (UnknownHostException e) { System.outprintln("A szerver nem válaszol!");} Szerverek Miután egy kapcsolat felépült, a szerver ugyanolyan típusú Socket objektumokat használ, mint a kliensalkalmazás, bár a kapcsolat felépítéséhez

először egy ServerSocket objektumot kell telepítenie valamelyik portra. try { ServerSocket ss = new ServerSocket(6111); while (!vege) { Socket s = ss.accept(); BufferedReader br = new BufferedReader( new InputStreamReader(s.getInputStream())); PrintWriter pr = new PrintWriter( s.getOutputStream(), true); // AutoFlush String st = br.readLine(); System.outprintln("Klienstől érkezett: " + st); pr.println("Viszlát!"); s.close(); } ss.close(); } catch (IOException io) {} 65. oldal, összesen: 66 Biztonság A biztonság felügyeletét a SecurityManager osztály végzi.  Applet-ek - Egy applet csak azzal a kiszolgálógéppel kezdeményezhet kapcsolatot, ahonnan a böngészőprogram letöltötte. - Applet nem hozhat létre magának ServerSocket típusú objektumot.  Alkalmazások - Számukra bármely kiszolgálón futó szerveralkalmazás elérhető. - Létrehozhatnak ServerSocket típusú objektumot. A ServerSocket metódusai   public ServerSocket(

int port ) throws IOException - a megadott porton létrehozza az objektumot public Socket accept() throws IOException - várakozik egy kliens kapcsolatkeresési kérelmére, ha megérkezik, akkor visszatér a hozzá tartozó Socket tipusú objektummal A Socket osztály metódusai  public Socket (String host, int port) throws UnknownHostException, IOException  public InputStream getInputStream() throws IOException  public OutputStream getOutputStream() throws IOException Az InetAddress metódusai  public String getHostName() - visszaadja az ehhez az Internet címhez tartozó host-nevet  public byte[] getAddress() - visszaadja az Internet címet 4 byte-os formátumban  public int hashCode() - az Internet címhez tartozó hash-kódot adja vissza  public String toString() - String reprezentációban adja vissza az Internet címet  public static InetAddress getLocalHost() throws UnknownHostException - visszaadja a helyi (programot futtató) host Internet címét 

public static InetAddress getByName(String host) throws UnknownHostException - az argumentumban megadott nevű host Intemet címét adja vissza  public static InetAddress[] getAllByName(String host) throws unknownHostException - az argumentumban megadott nevű host összes Internet címét visszaadja URL-ek     Az URL-ek Interneten elhelyezett objektumokra (bármilyen típusú adatforrásra) mutatnak. Azonkívül, hogy meghatározzák egy adattömeg helyét az Interneten, információt tartalmaznak az adatok kinyeréséhez használható protokollról is. Az URL-ek többnyire sztring-reprezentációban jelennek meg. Legáltalánosabb formája: protokoll://kiszolgáló/hely/objektum Az URL osztály  A Java nyelvben az URL-eket az URL osztály egy példánya reprezentálja.  Egy URL objektum alkalmas valamely URL-lel kapcsolatos összes információ kezelésére, valamint segítséget nyújt az általa meghatározott objektum kinyeréséhez.  URL objektum

létrehozása - karaktersorozatból: URL homePage = new URL("http://www.bankihu/doc/homepagehtml" ) ; - részekből: URL homePage = new URL("http", "www.bankihu", "doc/homepagehtml ); Az URL objektum  Az URL objektum létrejön függetlenül attól, hogy az általa reprezentált objektum létezik-e vagy sem.  A létrehozás során az URL objektum nem teremt hálózati kapcsolatot a kiszolgáló géppel.  A létrehozás alatt a Java elemzi az URL specifikációját és kiemeli belőle a használni kívánt protokollt, majd megvizsgálja, hogy ismeri-e. Abban az esetben ha nem ismeri MalformedURLException kivétel generálódik Tartalomkezelők  A Java - a hagyományos folyamon keresztüli adatletöltésen kívül - lehetőséget biztosít URL-ek tartalmának, mint objektumoknak a kinyerésére.  Az objektumkénti letöltés a tartalomkezelők (Content Handler ) használatával valósul meg.   66. oldal, összesen: 66 Egy URL

objektumkénti letöltését az URL getContent() metódusának meghívásával kezdeményezhetjük. A getContent() meghívásával az URL a következőket teszi: - felveszi a kapcsolatot a kiszolgáló géppel, - letölti az adatokat a kliens gépre a megadott protokoll segítségével, - megállapítja az adatok formátumát, és - meghívja az adatformátumhoz tartozó tartalomkezelőt az objektum előállítására Protokollkezelők  Az adatok letöltése a kiszolgáló gépről a protokollkezelők (Protocoll Handler) segítségével történik.  A megfelelő protokollkezelő meghatározása az URL specifikációjában történik (pl. "http", ftp" )  Az URL az adatok letöltése előtt megvizsgálja, hogy hozzáférhető-e a megadott protokollhoz tartozó protokollkezelő, ha igen, átadja neki a vezérlést. Tartalom- és protokollkezelők  A tartalomkezelő tevékenysége a protokollkezelő objektum kimenetére épü1.  A protokollkezelő az adatok

hálózati átvitelért, míg a tartalomkezelő a protokollkezelő által dekódolt adatokból való objektum létrehozásért felelős, így működésük közt nincs átfedés.  A tartalomkezelő ugyanolyan inputból ugyanazt az objektumot készíti el, számára lényegtelen, hogy az ő bemenete milyen protokollon keresztül érkezik meg.  Így teljesen más protokollon alapuló URL-ek is használhatják ugyanazt a tartalomkezelőt (ha azt a tartalom indokolja). A kapott objektum feldolgozása  A tartalomkezelő által kapott objektum típusa ismeretlen, ezért cast-olni kell a tényleges típusra. (A cast-olás során ClassCastException kivétel váltódhat ki!) try { String s = (String)myURL.getContent(); } catch (Exception e) { }