Programozás | Programozás-elmélet » Adatszerkezetek példatár

Tartalomjegyzék Bevezető .3 1. ELEMI TÍPUSOK . 4 1.1 EGÉSZEK ÁBRÁZOLÁSA 4 1.11 Mintafeladatok 4 1.12 Gyakorló feladatok 6 1.2 VALÓSAK ÁBRÁZOLÁSA 7 1.21 Mintafeladatok 7 1.22 Gyakorló feladatok 13 1.3 FELSOROLÁS TÍPUS 14 1.31 Mintafeladatok 14 1.32 Gyakorló feladatok 18 1.4 MUTATÓK 19 1.41 Általános mutatók 19 1.411 1.412 1.42 Típusos mutatók. 20 1.421 1.422 2. Mintafeladatok . 19 Gyakorló feladatok. 19 Mintafeladatok . 20 Gyakorló feladatok. 21 ÖSSZETETT TÍPUSOK . 22 2.1 TÖMBÖK 22 2.11 Mintafeladatok 22 2.12 Gyakorló feladatok 33 2.2 DIREKT SZORZAT 35 2.21 Fix hosszúságú rekord 35 2.211 2.212 2.22 Mintafeladatok . 35 Gyakorló feladatok. 36 Alternatív rekord . 36 2.221 2.222 Mintafeladatok . 36 Gyakorló feladatok. 38 2.3 HALMAZ 39 2.31 Mintafeladatok 39 2.32 Gyakorló feladatok 42 2.4 VEGYES FELADATOK 43 2.41 Mintafeladatok 43 2.42 Gyakorló feladatok 44 -1- 2.5 SOROZATOK 45 2.51 Lista 45

2.511 2.512 2.52 Verem. 54 2.521 2.522 2.53 Mintafeladatok . 60 Gyakorló feladatok. 64 Összetett aritmetikai kifejezések kiértékelése. 66 2.541 2.542 2.55 Mintafeladatok . 54 Gyakorló feladatok. 59 Sor . 60 2.531 2.532 2.54 Mintafeladatok . 45 Gyakorló feladatok. 53 Mintafeladatok . 66 Gyakorló feladatok. 69 Fák. 70 2.551 Bináris fa 70 2.5511 Mintafeladatok 70 2.5512 Gyakorló feladatok 79 2.552 Nem bináris fa 80 2.56 Gráfok. 81 2.561 2.562 Mintafeladatok . 81 Gyakorló feladatok. 91 Irodalomjegyzék.92 -2- Bevezető Immár nyolcéves tanári pályafutásomat annak kezdete óta a Paksi Atomerőmű Részvénytársaság Energetikai Szakképzési Intézetében töltöttem és töltöm, ahol számítástechnikai programozó jelölteknek tanítok programozást. Kezdettől fogva szem előtt tartottam Nicklaus Wirth sokat emlegetett kijelentését, miszerint algoritmusok plusz adatstruktúrák egyenlő

programok. Jelentős hangsúlyt fektettem rá, hogy ne csak az elemi adattípusokkal, tömbökkel és file-okkal ismerkedjenek meg diákjaink, de biztos jártasságot szerezzenek a különböző sorozat jellegű adatszerkezetek , úgymint lista, verem, sor, és legalább ismereteket a bináris fák és gráfok alkalmazásában. A kiegészítő tanári diploma megszerzéséért folytatott tanulmányaim során az Adatszerkezetek tárgy újszerű megközelítése rávilágított arra, hogy a jelen példatárak inkább algoritmikus gondolkodásmódunk csiszolására szerepeltetik az idevágó feladatokat, mintsem annak megvilágítására, hogy adott típust értékhalmaza és műveletei határozzák meg. Meglehetősen szőrmentén kezelik mind az egyszerű, mind az összetett típusok ábrázolásának kérdéseit is. Ezen a területen kevésbé jártasak nagy haszonnal forgattunk volna az iménti szempontoknak megfelelő, kidolgozott mintafeladatokat is felvonultató példatárat. Ezen

két irányból szerzett tapasztalataim indítottak arra, hogy szakdolgozat gyanánt megpróbáljak ilyet írni. A példatár a tárgyalt típusok osztályozása szerint hierarchikusan tagolódik fejezetekre. A kidolgozott mintafeladatokban igyekeztem felvonultatni a jellemző feladatokat, eszközöket, alkalmazható ismereteket. A felhasznált elméleti ismeretek megtalálhatók a μlógia sorozat 34. illetve a benne külön csoportot alkotó Szilánkok sorozat 5. és 7 tagjában Az összetett típusokra vonatkozó mintafeladatokat az általam megismert reprezentációk mindegyikében megoldottam. A gyakorló feladatok megoldására vállalkozóknak ugyanezt jó szívvel ajánlom. Aki működő programon keresztül kívánja elsajátítani a felkínált ismereteket, módszereket, a tárgyalt algoritmusokat könnyedén valósíthatja meg Pascal nyelven. Gálos György Paks, 1999 május 31 -3- 1. Elemi típusok 1.1 Egészek ábrázolása 1.11 Mintafeladatok 1. feladat:

Határozd meg a -654 egész szám memóriabeli alakját! Megoldás: 1. lépés: A szám abszolút értékét átváltjuk kettes számrendszerbe, és ha szükséges a kapott bináris alakot kiegészítjük 16 bit hosszúságúra. 654 327 163 81 40 20 10 5 2 1 0 0 1 1 1 0 0 0 1 0 1 A logikai memóriatartalom a kettes számrendszerbe váltás után: 0 0 0 0 0 0 1 0 1 0 0 0 1 1 1 0 0 1 1 1 0 0 0 1 1 0 0 1 0 2 lépés: Képezzük minden bit komplemensét ! 1 1 1 1 1 1 0 1 3. lépés: A legkisebb helyiértékű bithez hozzáadunk 1-et 1 1 1 1 1 1 0 1 0 1 1 4. lépés: A memóriabeli fizikai elhelyezkedésben a logikai alakhoz képest byte-csere érvényesül. 0 1 1 1 0 0 1 0 1 -4- 1 1 1 1 1 0 1 2. feladat: Melyik egész szám memóriabeli alakja a következő bitsorozat? 0 1 0 0 1 0 1 0 1 1 0 0 1 0 1 0 1. megoldás: 1. lépés: A memóriabeli alakhoz képest byte-cserét kell alkalmazni a logikai sorrend

előállításához. 1 1 0 0 1 0 1 0 0 1 0 0 1 0 1 0 Mivel az első bit 1, az ábrázolt szám negatív. Visszafelé hajtjuk a kettes komplemens kód képzés algoritmusát. 2. lépés: Kivonunk a legkisebb helyiértékű biten 1-et A kivonás eredménye: 1 0 1 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 1 1 3. lépés: Egy bitenkénti komplemens képzés visszaadja a szám abszolút értékének kettes számrendszerbeli alakját. 0 0 1 1 0 1 0 1 1 0 1 1 0 1 1 0 4. lépés: Előállítjuk a szám abszolút értékét decimális számrendszerben Z = 213 + 212 + 210 + 2 8 + 2 7 + 2 5 + 2 4 + 2 2 + 21 = 8192 + 4096 + 1024 + 256 + 128 + 32 + 16 + 4 + 2 = 13750 5. lépés: Az eredeti szám a Z= -13750 Megjegyzés: A 4. lépést kevesebb számolással is végre lehet hajtani az un Horner-elrendezés segítségével: Z = (((.(((0 ∗ 2 + 0) ∗ 2 + 1) ∗ 2 + 1) ∗ 2 + + 0) ∗ 2 + 1) ∗ 2 + 1) ∗ 2

+ 0 = 13750 -5- 2. megoldás: 1. lépés: Mivel pozitív szám és ellentettjének összege csupa 0 bit sorozatot eredményez, negatív szám kettes komplemens kódját vonjuk ki a csupa 0 bit sorozatból! Túlcsorduló bitek elvesznek. 0 1 0 0 1 0 0 0 1 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 0 1 0 1 0 0 0 1 0 0 1 0 1 0 0 0 1 0 1 1 0 0 0 Ez technikailag kivitelezhető úgy is, hogy jobbról az első 1 értékű bittel bezárólag mindent helyben hagyunk, a többi bitnek pedig képezzük a komplemensét. 2. lépés: A kapott bitsorozat megfelel egy kettes számrendszerbe átváltott pozitív decimális egésznek. Így a szokott módon visszaszámítjuk a számot tizes számrendszerbe. Z = 13750 3. lépés: Nem feledve, hogy a szám eredetileg negatív Z = −13750 1.12 Gyakorló feladatok 1. Határozd meg a -568 két byte-os egész szám memóriabeli alakját! 2. Határozd meg a -1005 két byte-os egész szám memóriabeli alakját! 3. Határozz meg egy egész számot az

alább látható memóriabeli alakjából! 1 0 0 1 1 0 1 1 1 0 1 1 0 1 1 0 4. Határozz meg egy egész számot az alább látható memóriabeli alakjából! 0 1 1 1 0 0 1 1 1 0 0 1 5. Milyen a legkisebb két byte-os egész memóriabeli alakja? 6. Milyen a legnagyobb két byte-os egész memóriabeli alakja? -6- 1 0 1 1 1.2 Valósak ábrázolása 1.21 Mintafeladatok 1. feladat: Határozd meg a valós -238 memóriabeli alakját! Megoldás: Megjegyzés: A számot 6 byte-os valós típusú mennyiségként ábrázoljuk. A valós számokat X = m ∗ 2 k alakban írjuk fel, ahol az m ∈ R, un. mantissza, míg k ∈ Z, m un. karakterisztika Mivel m ∗ 2 k = ∗ 2 k +1 , célszerű valamilyen feltételt szabni, 2 1 mely a végtelen sok alkalmas (m,k) párból egyet kiválaszt. E célból az ≤ m < 1 2 egyenlőtlenségrendszert alkalmazzuk. 1. lépés: a szám abszolút értékének egészrészét és törtrészét külön átváltjuk kettes

számrendszerbe. Tizedespont helyett itt természetesen kettedes pontot használunk majd. Ez lesz a mantissza abszolút értéke A mantissza abszolút értékét megszorozzuk egy alkalmas kettő-hatvánnyal, hogy teljesítse az előírt egyenlőtlenségrendszert. Ezt hívjuk normálásnak Az alkalmazott kettő-hatvány kitevőjének ellentettje a karakterisztika. Tehát váltsuk át a 23-at kettes számrendszerbe! 23 11 5 2 1 0 1 1 1 0 1 Tehát a mantissza egészrésze 10111. Most váltsuk át a 0.8-et kettes számrendszerbe! Ehhez ismételten kettővel fogjuk szorozni a törtrészt. Ez a 2-1-gyel való ismételt maradékos osztásnak felel meg. A tizedespont előtt keletkező számjegyet, mely biztosan 0 vagy 1, mindig hozzáírjuk a törtrész kettes számrendszerbeli alakjához. Ha ennek során a törtrész tizes számrendszerbeli alakja egy korábbi állapotot vesz föl, akkor e két állapot között keletkezett bitsorozattal ismételten növeljük a törtrész kettes

számrendszerbeli alakját mígnem kitöltjük a rendelkezésre álló helyet. Ha a törtrész tizes számrendszerbeli alakja 0-vá válik, a kettes számrendszerbeli alakot csupa 0-val egészítjük ki. -7- Tehát a törtrész átváltása: 0.8 0.6 0.2 0.4 0.8 1 1 0 0 Periódus Tehát a mantissza normálás előtt m = 10111.110011001100 , míg a karakterisztika k = 0 . Következik a normálás. A mantisszát láthatóan 2 −5 -tel kell szorozni, tehát a karakterisztika 5 lesz. Azaz m = 0.10111110011001100 és k = 5 2. lépés: Hol helyezzük el a mantissza előjelére utaló információt? Mivel m > 1 és a 2 1 , ha számuk 2 végtelen és értékük kivétel nélkül 1 (végtelen mértani sor összege), ellenben az említett sorozat véges, a kettedes pont utáni bit értéke mindig 1 lesz. Tehát a mantissza nagyságára nézve nem hordoz információt. Arról tájékoztat, amit tudunk Ezen a helyen ábrázoljuk a mantissza előjelét. Ha negatív, akkor 1-et

írunk, ha pozitív, akkor 0-t. Mivel az ábrázolandó szám negatív m = 1011111001 1001100 2 −1 helyiérték utáni bitek sorozatának összege csak akkor lesz 3. lépés: Hogy ábrázoljuk a karakterisztika előjelét? Lefoglalni ennek egy bitet az ábrázolható értékhalmaz felezését vonná maga után. A rendelkezésre álló memóriaterületen az összes bitsorozatok felén negatív, felén nem negatív értékeket ábrázolunk. A karakterisztikát az ábrázolt legkisebb abszolút értékével növeljük, majd egyszerűen átváltjuk kettes számrendszerbe. Ez az un eltolt nullpontú bináris alak. Tehát k = 5 , a legkisebb karakterisztika pedig − 128 . Így a 133-at kell kettes számrendszerbe átváltani. 133 66 33 16 8 4 2 1 0 1 0 1 0 0 0 0 1 -8- Így k = 10000101 4. lépés: Logikailag előbb a mantissza byte-jai, helyiértékük csökkenő rendjében, majd a karakterisztika következnek. 1 0 1 1 1 1 1 0 0 1 Mantissza1 0 1 1 0 0 1 1 1 0 0

1 0 0 1 1 0 1 0 0 1 1 0 1 0 1 0 Mantissza2 1 0 0 1 Mantissza3 0 1 1 0 0 1 Mantissza4 1 0 1 0 Mantissza5 0 0 0 1 Karakterisztika 5. lépés: A memóriában ehhez képest byte csere érvényesül 1 0 0 0 0 1 0 1 0 1 Karakterisztika 0 1 1 0 0 1 1 1 0 0 1 0 0 1 Mantissza5 1 0 0 1 Mantissza4 0 1 1 0 0 1 Mantissza3 1 0 1 0 Mantissza2 1 1 1 1 Mantissza1 2. feladat: Mely valós számot ábrázoltuk az alábbiakban? 1 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 1 1 0 0 -9- Megoldás: Visszafelé fogjuk végrehajtani a valós számok memóriabeli alakját előállító algoritmust. 1. lépés: Állítsuk vissza byte cserével a logikai sorrendet! A fizikai sorrend: 1 0 0 0 1 1 0 1 0 0 Karakterisztika 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 Mantissza5 0 0 0 Mantissza4 0

0 0 0 0 0 Mantissza3 0 0 1 0 Mantissza2 0 0 1 1 Mantissza1 A logikai sorrend: 1 0 0 0 1 1 0 0 0 0 Mantissza1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 Mantissza2 0 0 0 0 Mantissza3 0 0 0 0 0 0 Mantissza4 0 0 1 Mantissza5 0 0 0 1 1 Karakterisztika 2. lépés: Határozzuk meg a karakterisztikát! A karakterisztika bináris alakja eltolt nullpontú kódot jelent. Eszerint kettes számrendszerben ábrázolt pozitív egész decimális alakját kell meghatározni, majd levonni belőle az eltolás mértékét. Tehát az eltolt karakterisztika k , = 2 7 + 2 3 + 2 2 + 2 0 = 128 + 8 + 4 + 1 = 141 . A valódi karakterisztika k = k , − 128 = 13 . -10- 3. lépés: Írjuk fel az ábrázolt szám valódi bináris alakját! Ehhez a normált mantisszát megszorozzuk a karakterisztikával azonos kitevőjű kettő-hatvánnyal. Tehát a normált mantissza m = 0.1000110000001100 Mivel k = 13 , a szám abszolút értékének kettes számrendszerbeli

alakja 1000110000001.100 4. lépés: Számítsuk ki a szám tizes számrendszerbeli alakját! [ X ]= 2 12 { X }= 2 −1 + 2 8 + 2 7 + 2 0 = 4096 + 256 + 128 + 1 = 4481 = 0.5 Tehát X = 4481.5 5. lépés: Mivel a mantissza előjelbitje 1 volt, a szám negatív Így X = −44815 3. feladat: Milyen az ábrázolt legkisebb pozitív valós szám memóriabeli alakja? Megoldás: 1. lépés: Az X = m ∗ 2 k alakú szám annál kisebb minél kisebb m és k ezért megkiséreljük egymástól függetlenül a lehető legkisebbre csökkenteni őket. 2. lépés: Először a mantisszát minimalizáljuk Az m a legkisebb ha 1 . Ennek bináris 2 alakja a szokott kódolási eljárás eredményeképpen: 0 0 0 0 0 0 0 0 0 0 0 Mantissza1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Mantissza2 0 0 0 0 Mantissza3 0 0 0 0 0 Mantissza4 0 0 0 0 Mantissza5 Itt az előjelbit 0 lévén szó pozitív számról. -11- 0 0 1 , nincs 0 értékű 2 mantissza. Így a 0 ábrázolása

nem múlhat a mantisszán Ezért a –128 értékű karakterisztika tetszőleges mantisszával definíció szerint jelenti a 0-t. Így a legkisebb használható karakterisztika a – 127. Ezt eltolva 128-cal 1-et kapunk Ezt átváltva kettes számrendszerbe kapjuk a karakterisztika bináris alakját: 3. lépés: Legkisebb a k, ha – 128 Mivel a csupa 0 bit mantissza is 0 0 0 0 0 0 0 1 4. lépés: Tehát az ábrázolható legkisebb pozitív valós szám X = 1 ∗ 2 −127 . Ennek 2 bináris alakja: 0 0 0 0 0 0 0 0 0 0 Mantissza1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 Mantissza2 0 0 0 0 Mantissza3 0 0 0 0 0 0 Mantissza4 0 0 0 0 Mantissza5 0 0 0 0 Karakterisztika 5. lépés: Végül byte csere után a memóriabeli alak: 0 0 0 0 0 0 0 1 0 0 Karakterisztika 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Mantissza5 0 0 0 Mantissza4 0 0 0 0 0 0 Mantissza3 0 0 0 Mantissza2 0 0 0 0 0

Mantissza1 -12- 1.22 Gyakorló feladatok 1. Határozd meg a valós -1145 memóriabeli alakját! 2. Határozd meg a valós -1211875 memóriabeli alakját! 3. A következő bináris alak mely szám memóriabeli megjelenítése? 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 1 0 0 1 1 0 1 1 4. A következő bináris alak mely szám memóriabeli megjelenítése? 0 1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 1 0 1 1 0 0 1 0 0 5. Határozd meg az ábrázolható legnagyobb valós szám memóriabeli alakját! 6. Határozd meg az ábrázolható legkisebb valós szám memóriabeli alakját! 7. Határozd meg az ábrázolható legnagyobb negatív valós szám memóriabeli alakját! -13- 1.3 Felsorolás típus 1.31 Mintafeladatok 1. feladat: Magyar kártya adott lapját ciklikusan megelőző ill követő lapot add meg! 1.

megoldás: A megfelelő típust az értékek, mint egyedi azonosítók felsorolásával deklaráljuk. Ebben a megközelítésben a magyar kártyát egyetlen típusal írjuk le A lapok azonosítói rendre: M7, M8, M9, M10, MA, MF, MK, MD, Z7, Z8, Z9, Z10, ZA, ZF, ZK, ZD, T7, T8, T9, T10, TA, TF, TK, TD, P7, P8, P9, P10, PA, PF, PK, PD Használni fogjuk a Következő(típusbeli kifejezés), Előző(típusbeli kifejezés), Sorszám(típusbeli kifejezés), Típusnév(sorszám), Szöveg(Típusbeli kifejezés), Típusnév(szöveg típusú kifejezés) absztrakt műveleteket. Mivel a felsorolás típus sorszámozott - a sorszámozás 0-val kezdődik – megoldhatjuk a megelőző ill. a rákövetkező lap meghatározását a sorszámozáson keresztül. Típus KártyaTípus =(M7,M8,M9,M10,MA,MF,MK,MD, Z7,Z8,Z9,Z10,ZA,ZF,ZK,ZD, T7,T8,T9,T10,TA,TF,TK,TD, P7,P8,P9,P10,PA,PF,PK,PD) Változó AktLap,ElőzőLap,KövetőLap : KártyaTípus Lap : Szöveg AktInd,ElőzőInd,KövetőInd : Egész Program:

Be:Lap AktLap:=KártyaTípus(Lap) AktInd:=Sorszám(AktLap) KövetőInd:= AktInd+1 Ha KövetőInd>Sorszám(PD) akkor KövetőInd:=0 KövetőLap:=KártyaTípus(KövetőInd) ElőzőInd:=AktInd-1 Ha ElőzőInd<0 akkor ElőzőInd:=Sorszám(PD) ElőzőLap:=KártyaTípus(ElőzőInd) Ki:Szöveg(ElőzőLap),Szöveg(KövetőLap) Program vége -14- Megjegyzés: Akik valamilyen elterjedt magasszintű programozási nyelven, Pl. Turbo Pascal nyelven, meg is akarják velósítani az algoritmust rögtön néhány nehézségbe és egy lekűzdhetetlen akadályba utköznek. A lekűzdhető nehézséget a beolvasás ill a kiíratás támasztja, miszerint a felsorolás típusú mennyiségek nem lehetnek ezen tevékenységek argumentumai. A megoldás erre a célra szolgáló alprogramok lesznek A lekűzdhetetlen akadályt az okozza, hogy az említett nyelven nincs olyan művelet, amely a sorszámhoz rendelné a felsorolás típus megfelelő értékét. Ez utóbbi miatt készítünk egy olyan

megoldást, ami az absztrakt műveletek közül figyelmen kívül hagyja a Típusnév(Sorszám) műveletet. Utána megírjuk a beolvasó, kiírató alprogramokat. 2. megoldás: A típus- és változódeklarációk alig változnak, csak indexmennyiségeket hagyjuk el. az Típus KártyaTípus =(M7,M8,M9,M10,MA,MF,MK,MD, Z7,Z8,Z9,Z10,ZA,ZF,ZK,ZD, T7,T8,T9,T10,TA,TF,TK,TD, P7,P8,P9,P10,PA,PF,PK,PD) Változó AktLap,ElőzőLap,KövetőLap : KártyaTípus Lap : Szöveg Program: Be:Lap AktLap:=KártyaTípus(Lap) Ha AktLap=PD akkor Követőlap:=M7 különben KövetőLap:=Következő(AktLap) Ha AktLap=M7 akkor Előzőlap:=PD különben ElőzőLap:=Előző(AktLap) Ki:Szöveg(ElőzőLap),Szöveg(KövetőLap) Program vége Megjegyzés: A beolvasó ill. kiírató alprogramok lényege, hogy a beolovasott szöveghez ill. a kiírandó felsorolás típusú adathoz megkeressük a megfelelő felsorolás típusú adatot ill. szöveget A kereséshez az említett rendezett párokat mindkét sorrendben.-

ha van rá mód előre, vagy az alprogramban feltételes utaítások egymásutánjával - össze kell állítani. Mindkettőre látunk majd példát, mert a Felsorolás Szöveg leképezés megvalósítható felsorolás típuson indexelt szöveg komponensű tömb segítségével, míg a Szöveg Felsorolás leképezés csak feltételes utasítások egymásutánjával valósítható meg. Hogy a programszöveg ez utóbbi esetben se legyen olyan hosszú, a Felsorolás Szöveg leképezést fel fogjuk használni a tevékenység ciklusba szervezése érdekében. -15- 3. megoldás: Ki kell bővíteni a típusok ill változók körét a már említett tömbbel ill egy felsorolás típusú változóval, mely index ill. ciklusszámláló szerepet fog betölteni A programban csak a beolvasásban ill. a kiíratásban lesz változás A megoldás során feltételezzük, hogy a felhasználó helyes adatokat gépel be. Típus KártyaTípus =(M7,M8,M9,M10,MA,MF,MK,MD, Z7,Z8,Z9,Z10,ZA,ZF,ZK,ZD,

T7,T8,T9,T10,TA,TF,TK,TD, P7,P8,P9,P10,PA,PF,PK,PD) LapTípus =Tömb(KártyaTípus : Szöveg) Konstans Pakli : LapTípus = (’M7’,’M8’,’M9’,’M10’,’MA’, ’MF’,’MK’,’MD’,’Z7’,’Z8’, ’Z9’,’Z10’,’ZA’,’ZF’,’ZK’, ’ZD’,’T7’,’T8’,’T9’,’T10’, ’TA’,’TF’,TK’,’TD’,’P7’, ’P8’,’P9’,’P10’,’PA’,’PF’, ’PK’,’PD’) Változó AktLap,ElőzőLap,KövetőLap,i : KártyaTípus Lap : Szöveg Program: Be:Lap Ciklus i=M7-től PD-ig Ha Pakli(i)=Lap akkor AktLap:=i cv i:=M7 Ciklus amíg Pakli(i)≠Lap i:=Következő(i) cv AktLap:=i Ha AktLap=PD akkor Követőlap:=M7 különben KövetőLap:=Következő(AktLap) Ha AktLap=M7 akkor Előzőlap:=PD különben ElőzőLap:=Előző(AktLap) Ki:Pakli(ElőzőLap),Pakli(KövetőLap) Program vége -16- Megjegyzés: Megvizsgálva a magyar kártya, mint sokaság, elemeinek szerkezetét azonnal észrevehető, hogy két szempont szerint jellemezhetők.

Egyik a lap színe, másik a szám ill. a vele egy kategóriába tartozó figura Ezért ez utóbbiakat együtt figurának nevezzük. Mindkét jellemzőhöz rendelhetünk egy-egy felsorolás típust A következő ill. megelőző lap kiválasztásánál elsősorban a figurát léptetjük Ha a figurát leíró típusból kilépnénk, akkor a figura a neki megfelelő típus másik végéről kap értéket, a színt pedig egyszerűen léptetjük. Ennek során időnként a színt leíró típusból is kilépnénk. Ekkor az is típusának másik végéről kap értéket A figurát ekkor már nem kell változtatni, mert már megtörtént. 4. megoldás: Típus SzínTípus = (Makk,Zöld,Tök,Piros) FiguraTípus = (Hetes,Nyolcas,Kilences,Tizes, Alsó,Felső,Király,Ász) Változó AktSzín,ElőzőSzín,Követőszín : SzínTípus AktFigura,ElőzőFigura,KövetőFigura : FiguraTípus Szín,Figura : Szöveg Program: Be:Szín,Figura AktSzín:=SzínTípus(Szín) AktFigura:=FiguraTípus(Figura) Ha

AktFigura≠Ász akkor KövetőFigura:=Következő(AktFigura) KövetőSzín:=AktSzín különben KövetőFigura:=Hetes Ha AktSzín≠Piros akkor KövetőSzín:=Következő(AktSzín) különben KövetőSzín:=Makk Elág. vége Elág. vége Ha AktFigura≠Hetes akkor ElőzőFigura:=Előző(AktFigura) ElőzőSzín:=AktSzín -17- különben ElőzőFigura:=Ász Ha AktSzín≠Makk akkor ElőzőSzín:=Előző(AktSzín) különben ElőzőSzín:=Piros Elág. vége Elág. vége Ki:Szöveg(ElőzőSzín),Szöveg(ElőzőFigura) Szöveg(KövetőSzín),Szöveg(ElőzőFigura) Program vége Megjegyzés: A beolvasás ill. kiiratás problémájáról és a megoldás módjáról korábbiakban szóltunk. 1.32 Gyakorló feladatok További feladatokat lásd a 2.4 fejezetben, ahol a felsorolás típus egy feladaton belül más érdekes típusokkal együtt szerepel! -18- 1.4 Mutatók 1.41 Általános mutatók 1.411Mintafeladatok 1. feladat: Demonstráld annak az állításnak igazságát,

miszerint a Turbo Pascal a halmaz típus ábrázolására lehetséges halmazelemenként 1 bitet foglal le! Megoldás: Deklarálunk néhány halmazt egymás után, majd egy tetszőleges változót lezárásképpen, végül minden említett változó számára egy-egy általános mutatót. Az általános mutatóknak értékül adjuk az előbbi változók kezdőcímét, és ezek különbségének 32 byte-nak kell lennie. A szegmenscímek ráadásul egyenlők egy ilyen pusztán demonstratív feladatban, nem lévén nevezett adataink előtt más adat az adatszegmensben. Az algoritmus megírása során nem szabad elfelejteni, hogy ennél a típusnál is érvényesül a byte-csere. Változó Halmaz1 : Halmaz(0.255) Halmaz2 : Halmaz(Karakter) Point1,Point2 : Mutató Program: Point1:=@Halmaz1 Point2:=@Halmaz2 Ha alsó(Point1)=alsó(Point2) és felső(Point2)-felső(Point1)=$0020 akkor Ki:’A halmazok valóban úgy ábrázolódnak, hogy a lehetséges halmazelemeknek egy-egy bit van

lefoglalva’ Program vége Megjegyzés: @halmaz1 a halmaz1 változó első byte-jának címe. 1.412Gyakorló feladatok Turbo Pascalban Szöveg típusú változó deklarációjakor elő lehet írni a szöveg maximális hosszát. Ekkor állítólag valóban csak annyi helyet foglal le a fordító (pontosabban a generált kód) amennyit előírtunk. Ellenőrizd! -19- 1.42 Típusos mutatók 1.421Mintafeladatok 1. feladat: Tudva, hogy a byte típusban a nem negatív decimális egész kettes számrendszerbeli alakja van jelen, készíts statisztikát annak igazolására, hogy a word típusban a nem negatív decimális egészek kettes számrendszerbeli alakja byte-cserélt formában van jelen! Megoldás: Gyakorlatilag azt kell alátámasztani valamiféle mintavétellel, hogy a memóriában hátrébb lévő byte, mint byte típusú mennyiség 256-szorosához hozzáadva az előrébb lévő byte, mint byte típusú mennyiség értékét egyenlőnek találjuk azt a word típusban tárolt

mennyiséggel. Ehhez egy két byte típusú mezőből álló rekordra mutató típusos mutatót definiálunk, melyet rápozícionálunk egy word típusú változóra, hogy ezek egyszerre legyenek jelen a közös memóriaterületen. A word értékét egyenközűen léptetjük a két szélső értéke között és megszámoljuk, hányszor teljesült a kívánt egyenlőség. Típus MutatóTípus = ^Byterekord Byterekord = rekord (Felső,Alsó : byte) Változó Vizsgált : Word Mutató : MutatóTípus N,DB,i,di : Természetes Program: Be:N DB:=0 di:=65535 div (N-1) Ciklus i=0-tól N-1-ig Vizsgált:=i*di Ki:Vizsgált,Mutató^.Felső,Mutató^Alsó, 256*Mutató^.Alsó + Mutató^Felső Ha Vizsgált=256*Mutató^.Alsó + Mutató^Felső akkor DB:=DB+1 Cv Ki: N,’esetből’,DB,’alkalommal volt az eredmény a vártnak megfelelő.’ Program vége -20- 1.422Gyakorló feladatok 1. Győződj meg statisztikailag arról, hogy a kis- ill nagybetűs angol ábécé betűi valóban kódjukkal

szerepelnek-e a memóriában, és hogy a szövegek aktuális hosszát az ábrázolásra szánt memóriaterület elején ábrázolja! 1. Állítólag a Turbo Pascal Boolean típusa egy adott bitsorozatra ad igaz és a többire hamis értéket. Ellenőrizd! 2. Demonstráld a halmazok ábrázolásáról tanultakat! Megjegyzés: a későbbi fejezetek minden olyan feladata, melyet dinamikus adatkezelés eszközeivel oldunk meg, alkalmat ad a típusos mutatók alkalmazására. -21- 2. Összetett típusok 2.1 Tömbök 2.11 Mintafeladatok 1. feladat: Azonos L byte hosszúságú adatokból álló NxK-s mátrixot ábrázolunk sorfolytonosan a C címtől kezdve. Készítsd el a megfelelő címfüggvényt, mely tetszőleges (i,j) index párhoz tartozó adat kezdőcímét adja meg! Megoldás: Tömbbeli adat címét úgy állítjuk elő, hogy a tömb kezdőcíméhez – az egy kvázi abszolút cím – hozzáadjuk az adat tömbön belüli címét, ami tekinthető egyfajta relatív címnek.

Az adat relatív címe az előtte lévő adatok számának és az ismétlődő adat byte-ban mért hosszának szorzata. A tömbben korábban lévő adatok száma az aktuális adat előtti teljes sorok számának (i-1) és a sor hosszának (K) szorzata megtoldva az aktuális adat során belül megelőzők számával (j-1). Képletszerűen: Cím(M (i, j )) = C + [(i − 1) * K + ( j − 1)] L 2. feladat: Egy NxN-es mátrixban a nem nulla elemek a főátlónak és a mellékátlónak metszéspontjuktól jobbra eső része között vannak. Add meg a címfüggvényt! Megjegyzés: Nem minden esetben egyszerű egy alkalmas zárt alak megtalálása. Gyakran lesz olyan a címfüggvény, hogy az értelmezési tartomány különböző – de véges sok – részén más-más hozzárendelési szabály érvényesül. Ilyen esetekben törekedni kell - általában soronkénti pásztázás segítségével – invariáns mennyiségek találására, majd ezekből kiindulva a címfüggvény

összeállítására. Bonyolultabb esetben algoritmust írunk a címfüggvény kiszámítására. Gyakran van szükség az értékes részt határoló görbék – többnyire egyenes – egyenletének ismeretére. -22- Megoldás: 1. lépés: Ehhez a feladathoz is kell egy ilyen táblázat, ahol az oszlopok rendre a sor indexet, első nem nulla adat oszlop indexét, utolsó nem nulla adat oszlop indexét, valamint a nem nulla adatok számát tartalmazzák. I 1 2 3 (N+1) div 2 • • N-2 N-1 N jmin N N-1 N-2 (N+1) div 2 • • N-2 N-1 N jmax N N N N • • N N N DB 1 2 3 (N+1) div 2 • • 3 2 1 2. lépés: Állapítsuk meg a szükséges vektor hosszát, ha a 0 adat a vektor végére kerül. Ha N páros, akkor a nem nulla adatok soronkénti számossága: 1,2,3,., N N , ,.,3,2,1 2 2 1 N N  N N Ezek összege 2 ∗ 1 +  ∗ = 1 +  ∗ . 2 2 2  2 2 N N  Tehát páros N esetén 1 +  ∗ + 1 hosszú vektor kell majd az adatok 2

2  tárolásához. Ha N páratlan, akkor soronként a nem nulla adatok száma: 1,2,3,., N −1 N +1 N −1 , , ,.,3,2,1 2 2 2 Ezek összege: 2∗ 1  N − 1 N − 1 N + 1  N −1 N − 1 N + 1 ∗ 1 + + = 1 + + = ∗ ∗ 2  2  2 2 2  2 2  N − 1 N − 1 N − 1 N −1 N + 1   + + 1 = 1 + ∗  1 + 2  2 2 2  2   -23- N − 1 N + 1  Tehát páratlan N esetén 1 + + 1 hosszúságú vektor kell a ∗ 2  2  mátrix adatainak elhelyezésére. Vegyük észre, hogy N páros N páratlan Megjegyzés: a N  2   N 2 N −1 2 Ndiv 2 N  2   N 2 N +1 2 (N + 1)div 2   az alsó egészrész, a   a felső egészrész jele. Tehát a szükséges helyek száma: (1 + Ndiv 2 )(( N + 1)div 2 ) + 1 3. lépés: Készítsük el a címfüggvényt! A megoldás során még eldönthetjük, hogy 0tól vagy 1-től indexeljük-e az egyindexű tömböt Először azt

határozzuk meg, hogy a mátrix (i,j) index párhoz tartozó eleme hol lesz az új tömbben. Ha i ≤ (N+1) div 2 és j ≤ N-i vagy i > (N+1) div 2 és j < i akkor M(i,j)=0, tehát a tömb utolsó helyének indexe lesz a címfüggvény értéke. Ha előbbi feltétel nem teljesül, akkor a mátrix nem nulla elemeinek egyikéről van szó. Ezen belül ha i ≤ (N+1) div 2, azaz a mátrix felső felében lévő nem nulla elemről van szó. Vegyük a betöltött sorokban lévő nem nulla adatok számát Ez a i −1 i −1 táblázat alapján ∑ k = ∗ i . Adjuk hozzá az aktuális elem sorában előtte lévő 2 k =0 nem nulla elemek számát. A táblázatból látszik, hogy ez a mátrix felső felében i + jmin=N+1, ahol jmin előtt 0 db nem nulla adat van. Tehát ez utóbbiak száma i+j – (N+1). Tehát a mátrix felső felében lévő (i,j) index párral jellemzett nem nulla elem i −1 címe a vektorban : ∗ i + (i + j ) − ( N − 1) + 1 . 2 Határozzuk meg a mátrix alsó

felében lévő nem nulla elemek helyét a tömbben! Ezt három részből rakjuk össze. A mátrix felső felében lévő nem nulla elemek száma, az aktuális elemig lévő további sorok nem nulla elemeinek száma, az aktuális elemet saját sorában megelőző nem nulla elemek száma. Végül nyilván 1-et még hozzáadunk ezekhez, hogy az aktuális elem helyét megkapjuk. -24- Tehát az összeg első része: A már korábban felírt i −1 ∑k = k =0 i −1 ∗ i képletbe 2 i = ( N + 1)div 2 + 1 -et írva 1 ∗ [( N + 1)div 2] ∗ [( N + 1)div 2 + 1] -et kapunk. 2 Az összeg második részéhez vegyuk észre, hogy az ide tartozó sorokban a nem nulla elemek száma soronként N-i-1. Ezek a sorok az (N+1)div2+1 –től terjednek az i-1 –ig. Tehát a nem nulla elemek száma ezekben a sorokban: i −1 ∑ k = ( N +1)div 2 +1 N − k +1= i −1 ∑ [(N + 1) − k ] = k = ( N +1)div 2 +1 i −1 ∑ N +1− k = ( N +1)div 2 +1 i −1 ∑k k = ( N +1)div 2 +1 = (N

+ 1) ∗ {i − [(N + 1)div 2 + 1]} − 1 ∗ {i − [(N + 1)div 2 + 1]} ∗ {(i − 1) + [(N + 1)div 2 + 1]} 2 Végül az összeg harmadik része a táblázatból észrevehető összefüggés alapján egyszerűen j − i . j min − i = 0 Tehát az aktuális elem miatti 1 hozzáadásával a mátrix alsó felébe eső nem nulla értékű (i,j) indexű mátrixelem tömbbeli indexe 1 ∗ [( N + 1)div 2] ∗ [( N + 1)div 2 + 1] + 2 (N + 1) ∗ {i − [(N + 1)div 2 + 1]} − 1 ∗ {i − [(N + 1)div2 + 1]}∗ {(i − 1) + [(N + 1)div 2 + 1]} + 2 j − i +1. A gondolatmenetből nyilvánvaló, hogy 1-től indexeltük a tömböt. Megjegyzés: egy sv := ( N + 1)div 2 helyettesítéssel, gyorsabb lesz az algoritmus. -25- 4. lépés: Írjuk meg az algoritmust! Azaz egy függvényt írunk, melynek argumentuma a mátrixbeli index pár, értéke a tömbbeli index. Konstans N= Típus ElemTípus Mátrix SorMátrix = = Tömb(1.N,1N:ElemTípus) = Tömb(1.(Ndiv2 +1)*((N+1)div2)+1: ElemTípus)

IndexTípus = 1.(Ndiv2 +1)*((N+1)div2)+1 A SorMátrix típusra a címfüggvény megírásához nincs szükség, de jól látszik a Mátrix tárolásához szükséges méret. Változó i,j : 1.N Index : IndexTípus Adat : SorMátrix Függvény Cím(N;i,j:IndexTípus) Függvény: Ha i≤(N+1)div2 és j≤N-i vagy i>(N+1)div2 és j<i akkor Cím:=(Ndiv2+1)*((N+1)div2)+1 különben Ha i≤(N+1)div2 akkor Cím:=i*(i-1)div2+(i+j)-N különben Cím:=((N+1)div2)*((N+1)div2+1)div2+ (N+1)*(i-((N+1)div2+1))(i-((N+1)div2+1))((i-1)(N+1)div2+1)div2 elág vége elág vége Függvény vége Megjegyzés: Mint érzékelhető elég nehéz volt összehozni a címfüggvényt, és igen bonyolultra sikerült. Talán néhány összevonás még elvégezhető, de munkát azzal nem takarítunk már meg magunknak. Készíthetünk teljesen algoritmikus megoldást is. Felhasználva a nulla a datokat a nem nulla adatoktól elválasztó görbék egyenleteit, végigpásztázva az aktuális elemig a sorokat

egyszerűen megszámoljuk a nem nulla elemeket. -26- 3. feladat: Adj össze két mátrixot! Megjegyzés: Két mátrix összeadása csak akkor merülhet fel, ha méreteik és elemeik típusa egyenlők. Ennek megfelelően két NxM-es mátrixot adunk össze A két mátrix összeadása rendre az azonos indexű elemek összeadását jelenti. 1. megoldás: Először a szokásos indexelt típuskonstrukciós ábrázolás mellett oldjuk meg a feladatot. Feltételezzük a típus beolvashatóságát, kiírhatóságát és a memória elégséges voltát. Konstans N = M = Típus ElemTípus = MátrixTípus = Tömb(1.N,1M:ElemTípus) Változó A,B,C : MátrixTípus Eljárás Összead(A,B : MátrixTípus; Vált C : MátrixTípus) Változó i : 1.N j : 1.M Eljárás: Ciklus i=1-től N-ig Ciklus j=1-től M-ig C(i,j):=A(i,j)+B(i,j) Cv Cv Eljárás vége -27- 2. megoldás: Sorfolytonosan láncolt ábrázolás mellett oldjuk meg a feladatot. A beolvashatóságot, kiírathatóságot és a

memória elégséges voltát feltételezzük. Konstans N = M.= Típus ElemTípus MátrixElemMut MátrixElemTípus (Adat Köv MátrixTípus = = = : : = ^MátrixElemTípus rekord ElemTípus MátrixElemMut) MátrixElemMut Változó A,B,C:MátrixTípus Eljárás Összead(A,B : MátrixTípus; Vált C : MátrixTípus) Változó AktA,AktB,AktC,Új : MátrixElemMut K : Természetes Eljárás: AktA:=A AktB:=B Lefoglal(C) AktC:=C AktC^.Adat:=AktA^Adat+AktB^Adat Ciklus k=1-től N*M-1-ig AktA:=AktA^.Köv AktB:=AktB^.Köv Lefoglal(Új) Új^.Adat:=AktA^Adat+AktB^Adat AktC^.Köv:=Új AktC:=Új Cv AktC^.Köv:=NIL Eljárás vége -28- 3. megoldás: Átlagosan rövidebb ideig tart sorra venni a mátrix elemeit, ha a sorok elemeit láncoljuk dinamikusan, majd a sorok kezdőelemeit tömbben tároljuk. Ilyen ábrázolás mellett is feltételezzük a mátrix beolvashatóságát és kiírathatóságát, valamint a memória elégséges voltát. Konstans N = M = Típus ElemTípus MátrixElemMut

MátrixElemTípus (Adat Köv MátrixTípus = = = : : = ^MátrixElemTípus rekord ElemTípus MátrixElemMut) Tömb(1.N:MátrixElemMut) Változó A,B,c : MátrixTípus Eljárás Összead(A,B : MátrixTípus; Vált C : MátrixTípus) Változó AktA,AktB,AktC,Új : MátrixElemMut i : 1.N j : 1.M Eljárás: Ciklus i=1-től N-ig AktA:=A(i) AktB:=B(i) Lefoglal(C(i)) AktC:=C(i) Ciklus j=1-től M-ig AktC^.Adat:=AktA^Adat+AktB^Adat AktA:=AktA^.Köv AktB:=AktB^.Köv Lefoglal(Új) AktC^.Köv:=Új AktC:=Új Cv Felszabadít(AktC) Cv Eljárás vége -29- 4. megoldás: Az adatszegmens szempontjából még helytakarékosabb ábrázolást kapunk az előbbiből, ha a sorok első elemére külön adat mutat, és ezek is egymás után vannak láncolva. A mátrix azonosítható ez utóbbi lánc fejével Továbbra is feltételezzük a mátrixok beolvashatóságát, kiírathatóságát valamint a memória elégségessé voltát. A típusdefiníciókhoz nem kell ismernünk a mátrixok méretét, de

inicializálásukat a méretek beolvasásával kell kezdeni. Típus ElemTípus = MátrixElemMut MátrixElemTípus (Adat Köv MátrixSorMut MátrixSorFej (Kövelem KövSor MátrixTípus = = : : = = : : : ^MátrixElemTípus rekord ElemTípus MátrixElemMut) ^MátrixSorFej rekord MátrixElemMut MátrixSorMut) MátrixSorMut Változó A,B,C : MátrixTípus N,M : Természetes Eljárás Összead(A,B : MátrixTípus; Vált C : MátrixTípus) Változó SorAktA,SorAktB,SorAktC,ÚjSor : MátrixSorMut AktA,AktB,AktC,Új : MátrixElemMut i,j : Természetes Eljárás: SorAktA:=A SorAktB:=B Lefoglal(C) SorAktC:=C Ciklus amíg SorAktA≠NIL és SorAktB≠NIL AktA:=SorAktA^.KövElem AktB:=SorAktB^.KövElem Lefoglal(AktC) SorAktC^.KövElem:=AktC -30- Ciklus amíg AktA≠NIL és AktB≠NIL AktC^.Adat:=AktA^Adat+AktB^Adat AktA:=AktA^.Köv AktB:=AktB^.Köv Lefoglal(Új) AktC^.Köv:=Új AktC:=Új Cv Felszabadít(AktC) SorAktA:=SorAktA^.KövSor SorAktB:=SorAktB^.KövSor Lefoglal(ÚjSor)

SorAktC^.KövSor:=ÚjSor SorAktC:=ÚjSor Cv Felszabadít(SorAktC) Eljárás vége 5. megoldás: Végül a faladatot az un. listák listája reprezentáció mellett oldjuk meg Ebben az ábrázolásban egy elem nemcsak a sorban rákövetkezőre mutat, hanem az oszlopában rákövetkezőre is. A mátrix a bal felsőként emlegetett elemmel azonosítható A típusdefiníciók most sem igénylik a mátrixok méreteinek ismeretét, de az inicializálás már igen. Ezen ábrázolás a korábbi láncolt ábrázolásoktól eltérően hatékonyan elősegíti az oszlopfolytonos feldolgozást is. Továbbra is feltételezzük a mátrixok beolvashatóságát, kiírathatóságát valamint a memória elégséges voltát. Típus ElemTípus = MátrixElemMut = ^MátrixElemTípus MátrixElemTípus = rekord (Adat : ElemTípus SorKöv,OszlopKöv : MátrixElemMut) MátrixTípus : MátrixElemMut Változó A,B,C : MátrixTípus N,M : Természetes Eljárás Összead(A,B : MátrixTípus; Vált C :

MátrixTípus) Változó SorAktA,SorAktB,SorAktC, AktA,AktB,AktC,Régi,új : MátrixElemMut -31- Eljárás: SorAkt:=A SorAktB:=B Lefoglal(C) SorAktC:=C AktA:=SorAktA AktB:=SorAktB AktC:=SorAktC Ciklus amíg AktA≠NIL ésAktB≠NIL AktC^.Adat:=AktA^Adat+AktB^Adat AktA:=AktA^.OszlopKöv AktB:=AktB^.OszlopKöv Lefoglal(Új) AktC^.OszlopKöv:=Új AktC:=Új Cv Felszabadít(AktC) Ciklus amíg SorAktA^.SorKöv≠NIL és SorAktB^.SorKöv≠NIL Lefoglal(Új) SorAktC^.SorKöv:=Új Régi:=SorAktC SorAktC:=Új SorAktA:=SorAktA^.SorKöv SorAktB:=SorAktB^.SorKöv AktA:=SorAktA AktB:=SorAktB AktC:=SorAktC AktC^.Adat:=AktA^Adat+AktB^Adat Ciklus amíg AktA^.OszlopKöv≠NIL és AktB^.OszlopKöv≠NIL AktA:=AktA^.OszlopKöv AktB:=AktB^.Oszlopköv Lefoglal(Új) Régi:=Régi^.OszlopKöv AktC^.OszlopKöv:=Új Régi^.SorKöv:=Új AktC:=Új AktC^.Adat:=AktA^Adat+AktB^Adat Cv AktC^.OszlopKöv:=NIL Cv AktC:=SorAktC Ciklus amíg AktC≠NIL AktC^.SorKöv:=NIL AktC:=AktC^.OszlopKöv Cv Eljárás vége -32-

Megjegyzés: A feladat megoldása során elég volt alkalmas módon sorra venni az előállítandó mátrixelemeket, és ennek megfelelően az operandus mátrixok egy-egy elemét. Azaz mindegyik mátrixban volt aktuális elem A konkrét feladatban az aktuális elemek saját mátrixukban ugyanott voltak ezért egyszerűen mindegyikben sorfolytonosan és azonos ütemben léptettük az aktuális elem helyét. Bonyolultabb feladatok esetében, mint mátrixok kompozíciója, érdemes megfontolni minden egyes reprezentációhoz címfüggvény készítését. 2.12 Gyakorló feladatok 1. Egy NxN-es felsőháromszögmátrixot ábrázolunk sorfolytonosan Add meg a címfüggvényt! 2. Egy NxN-es tridiagonális mátrixot ábrázolunk úgy, hogy előbb a főátló fölötti átlót, majd a főátlót, végül az alatta lévő átlót. Add meg a címfüggvényt! 4. Egy NxN-es tridiagonális mátrixot ábrázolunk sorfolytonosan Add meg a címfüggvényt! 5. Egy NxN-es mátrixban a nem nulla

elemek a főátló és a mellékátló metszéspont alá eső része között vannak. Add meg sorfolytonos ábrázoláshoz a címfüggvényt! 6. Egy NxN-es Toeplitz-mátrixot ábrázolunk a lehető leghatékonyabban Add meg a címfüggvényt! 7. Egy NxN-es Hankel-mátrixot ábrázolunk a lehető leghatékonyabban Add meg a címfüggvényt! 8. Ábrázold sorfolytonosan egy Vandermonde-mátrix rekonstrukcióhoz szükséges adatait és add meg a címfüggvényt! 9. Két hézagosan kitöltött mátrixot úgy ábrázolunk, hogy a nem nulla elemek mellé felvesszük a sor- és oszlopindexüket és azokat egy N1x3-as ill. N2x3-as mátrixban tároljuk. Sorfolytonosan add össze a két mátrixot és az eredményt a leírt módon tárold! 10. Állítsd elő két mátrix sor-oszlop szorzatát! 11. Állítsd elő két mátrix oszlop-sor szorzatát! 12. Állítsd elő két mátrix sor-oszlop kompozícióját! 13. Állítsd elő két mátrix oszlop-sor kompozícióját! 14. Szorozz meg egy mátrixot

sorvektorral! -33- 15. Szorozz meg egy mátrixot oszlopvektorral! 16. Képezd egy mátrix rotációját ill divergenciáját! -34- 2.2 Direkt szorzat 2.21 Fix hosszúságú rekord 2.211Mintafeladatok 1. feladat: Egy nyilvántartásban szereplőkről felvették a nevüket, életkorukat, személyi számukat, és lakhelyük nevét. Válogasd ki a nem Budapesten élő, nyugdíjas férfiakat! Megoldás: Típus SzemélyTípus = rekord (Név : Szöveg SzemSzám : Szöveg[11] Kor : Természetes Lakhely : Szöveg) Konstans MaxMinta = Változó Nyilvántartás : Tömb(1.MaxMinta:SzemélyTípus) Kiválasztottak : Tömb(1. MaxMinta:SzemélyTípus) N,DB : 1.MaxMinta Program: Be:N,Nyilvántartás() DB:=0 Kiválasztottak():=0 Ciklus i=1-től N-ig Ha Nyilvántartás(i).SzemSzám<’20000000000’ és Nyilvántartás(i).LakHely≠’Budapest’ és Nyilvántartás(i).Kor≥65 akkor DB:=DB+1 Kiválasztottak(DB):=Nyilvántartás(i) elág vége Ki:DB,Kiválasztottak() cv Program vége

-35- 2.212Gyakorló feladatok 1. Egy könyvtárban nyilvántartják a könyvekről a szerző nevét, a mű címét, a kiadás évét és a leltári számot. Írj programot, mely tetszés szerint választható szempont szerint keres! 2. Zsebtolvajokról vezetett nyilvántartásban szerepel hajuk színe, szemük színe, magasságuk, hányszor buktak le és hány napot ültek eddig foglalkozásuk jutalmaként. Csoportosítsd őket! Azok kerüljenek egy csoportba, akiknek a szemük színe és a testmagasságuk 10 cm-ekre kerekítve azonos! 2.22 Alternatív rekord 2.221Mintafeladatok 1. feladat: Tudva, hogy a byte típusban a nem negatív decimális egészek kettes számrendszerbeli alakja van jelen, készíts statisztikát annak igazolására, hogy a word típusban nem negatív decimális egészek kettes számrendszerbeli alakja byte-cserélt formában van jelen! Megoldás: Gyakorlatilag azt kell alátámasztani valamiféle mintavétellel, hogy a memóriában hátrébb lévő byte,

mint byte típusú mennyiség 256-szorosához hozzáadva az előrébb lévő byte, mint byte típusú mennyiség értékét egyenlőnek találjuk azt a word típusban tárolt mennyiséggel. Ehhez olyan rekordot definiálunk, melyben a word és a két byte típusú mezők egyszerre vannak jelen a közös memóriaterületen. A word típusú mező értékét egyenközűen léptetjük a két szélső értéke között és megszámoljuk, hányszor teljesült a kívánt egyenlőség. Típus WordByte = rekord Alternatívák byte 0 esetén (Szám : word) 1 esetén (Felső,Alsó : byte) Alternatívák vége Változó Vizsgált : WordByte N,DB,i,di : Természetes -36- Program: Be:N DB:=0 di:=65535 div (N-1) Ciklus i=0-tól N-1-ig Vizsgált.Szám:=i*di Ki:Vizsgált.Szám,VizsgáltFelső,VizsgáltAlsó, 256*Vizsgált.Alsó + VizsgáltFelső Ha Vizsgált.Szám=256*Vizsgált.Alsó + Vizsgált.Felső akkor DB:=DB+1 Cv Ki: N,’esetből’,DB,’alkalommal volt az eredmény a vártnak

megfelelő’ Program vége 2. feladat: Egy iskolában a tanárok fizetést, a diákok ösztöndíjat kapnak A tanárok kompetenciája társadalom-, természettudományi, műszaki, testnevelő, kollégiumi nevelő lehet. A diákok által tanulható szakmák programozó, software üzemeltető, manager-asszisztens, könyvelő lehetnek. Készíts statisztikát a tanári átlagfizetések kompetencia-, ill. a diákösztöndíjak szakmafüggéséről! Típus CímSzóTípus KompTípus = (Tanár,Diák) = (Társadalomtudomány, Természettudomány, Műszaki,Testnevelő, Kollégiumi nevelő) SzakmaTípus = (Programozó,Software üzemeltető, Manager asszisztens,Könyvelő) JellegTípus = (Fizetés,Ösztöndíj) SzemélyTípus = rekord (Név : Szöveg; Alternatívák Státusz : CímSzóTípus; Tanár esetén (Terület : KompTípus; Fizetés : Valós) Diák esetén (Szakma : SzakmaTípus; Ösztöndíj : Valós) Alternatívák vége) Konstans MaxLétszám= Változó IskolaPolgár TanárÁtlag

DiákÁtlag TanárDB DiákDB N,i : : : : : : Tömb(1.MaxLétszám:SzemélyTípus) Tömb(KompTípus:Valós) Tömb(SzakmaTípus:Valós) Tömb(KompTípus:1.MaxLétszám) Tömb(SzakmaTípus:1.MaxLétszám) 1.MaxLétszám -37- Program: Be:N,IskolaPolgár() TanárÁtlag():=0 DiákÁtlag():=0 TanárDB():=0 DiákDB():=0 Ciklus i=1-től N-ig Ha IskolaPolgár(i).Státusz=Tanár akkor TanárDB(IskolaPolgár(i).Terület):= TanárDB(IskolaPolgár(i).Terület)+1 TanárÁtlag(IskolaPolgár(i).Terület):= TanárÁtlag(IskolaPolgár(i).Terület)+ IskolaPolgár(i).Fizetés különben DiákDB(IskolaPolgár(i).Szakma):= DiákDB(IskolaPolgár(i).Szakma)+1 DiákÁtlag(IskolaPolgár(i).Szakma):= DiákÁtlag(IskolaPolgár(i).Szakma)+ IskolaPolgár(i).Ösztöndíj elág vége Cv Ciklus j=Társadalomtudomány-tól Kollégiumi nevelő-ig TanárÁtlag(j):=TanárÁtlag(j)/TanárDB(j) Cv Ciklus k=Programozó-tól Könyvelő-ig DiákÁtlag (k):=DiákÁtlag (k)/DiákDB(k) Cv Ki:TanárÁtlag(),DiákÁtlag()

Program vége 2.222Gyakorló feladatok 1. Győződj meg statisztikailag arról, hogy a kis- ill nagybetűs angol ábécé betűi valóban kódjukkal szerepelnek-e a memóriában, és hogy a szövegek aktuális hosszát az ábrázolásra szánt memóriaterület elején ábrázolja! 2. Állítólag a Turbo Pascal Boolean típusa egy adott bitsorozatra ad igaz és a többire hamis értéket. Ellenőrizd! 3. Demonstráld a halmazok ábrázolásáról tanultakat! -38- 2.3 Halmaz 2.31 Mintafeladatok 1. feladat: Készíts lottószám húzó algoritmust! Megoldás: A már kihúzott lottószámokat halmazban tároljuk. Ötször húzatunk addig mígnem a húzott szám még nem szerepel a halmazban. Használni fogjuk az absztrakt halmaz-műveleteket. Típus Számok = Halmaz(1.90) Változó Öttalálatos : Számok ÚjSzám,i : Természetes Program: Öttalálatos:=Üres Ciklus i=1-től 5-ig Ciklus Újszám:=Véletlen(90)+1 amíg Eleme-e?(Öttalálatos,ÚjSzám)

Öttalálatos:=Öttalálatos+Halmaz(Újszám) Cv Ciklus i=1-től 90-ig Ha Eleme-e?(Öttalálatos,i) akkor Ki:i Cv Program vége Megjegyzés: Véletlen(x) ∈ [0,x), ha x ∈ N. 2. feladat: Készíts 4 fős ultitársaság számára osztóalgoritmust! Az osztás végén az algoritmus jelezze a talonbeli tisztek (tizesek és ászok) számát, adja meg az ultira vállalkozhatók nevét, ultijuk színét, a leosztást és a talont! Megoldás: A 32 lapos magyar kártyából három játékos véletlenszerűen kap 10-10 lapot. Az osztás után az osztó szerepét játszó negyedik játékos megnézheti a kezében maradt – többieknek egyelőre titkos – két lapot, és jelzi a benne lévő tisztek számát. Ezután következik a licit, melynek során az vállalkozhat ultira, akinek kezében hetes lap van. Az ulti színe azonos a hetes színével A megoldás során a lapokat sorszámozzuk, és ezen sorszámok halamazaival írjuk le a leosztást és a talont. -39- Típus KártyaTípus

OsztásTípus PakliTípus SzínTípus JátékosTípus = = = = = Halmaz(1.32) Tömb(1.3:KártyaTípus) Tömb(1.32:Szöveg) Tömb(0.3:Szöveg) Tömb(0.3:Szöveg) Konstans Pakli : PakliTípus = (’M7’,’M8’,’M9’,’M10’,’MA’, ’MF’,’MK’,’MD’,’Z7’,’Z8’,’Z9’, ’Z10’,’ZA’,’ZF’,’ZK’,’ZD’, ’T7’,’T8’,’T9’,’T10’,’TA’, ’TF’,TK’,’TD’,’P7’,’P8’, ’P9’,’P10’,’PA’,’PF’,’PK’, ’PD’) Szín : SzínTípus = (’Makk’,’Zöld’,’Tök’,’Piros’) Változó Osztás Talon Játékosok i,j,Lap : : : : OsztásTípus KártyaTípus JátékosTípus Természetes Program: Inicializálás(Játékosok,Talon,Osztás) Laposztás(Talon,Osztás) TalonVizsgálat(Talon) UltiLehetőség(Osztás,Szín,Játékosok) Lapok(Játékosok,Osztás,Pakli) Program vége Eljárás Inicializálás(Vált Játékosok : JátékosTípus; Vált Talon : KártyaTípus; Vált Osztás : OsztásTípus) Változó i :

Természetes Eljárás: Be:Játékosok Talon:=KártyaTípus(1.32) Ciklus i=1-től 3-ig Osztás(i):=üres Cv Eljárás vége -40- Eljárás Laposztás(Vált Talon : KártyaTípus; Vált Osztás : OsztásTípus) Változó i,j,Lap : Természetes Eljárás: Ciklus i=1-től 3-ig Ciklus j=1-től 10-ig Ciklus Lap:=Véletlen(32)+1 amíg nem Eleme-e?(Talon,Lap) Osztás(i):=Osztás(i)+KártyaTípus(Lap) Talon:= Talon- KártyaTípus(Lap) Cv Cv Eljárás vége Eljárás TalonVizsgálat(Talon : KártyaTípus) Változó i,DB : Természetes Eljárás: DB:=0 Ciklus i=1-től 8-ig Ha Eleme-e?(Talon,4*i) akkor DB:=DB+1 Cv Ki:DB Eljárás vége Eljárás Ultilehetőség(Osztás : OsztásTípus; Szín : SzínTípus; Játékosok : JátékosTípus) Változó i,j,DB : Természetes UltiSzínek : Tömb(1.4:Természetes) Eljárás: Ciklus i=1-től 3-ig DB:=0 UltiSzínek():=0 Ciklus j=0-tól 3-ig Ha Eleme-e?(Osztás(i),8*j+1) akkor DB:=DB+1 UltiSzínek(DB):=j Elág vége Cv -41- Ha DB>0 akkor

KI:Játékosok(i),Szín(UltiSzínek()) Cv Eljárás vége Eljárás Lapok(Játékosok : JátékosTípus; Osztás : OsztásTípus; Pakli : PakliTípus); Változó i,j : Természetes Eljárás: Ciklus i=1-től 3-ig Ki:Játékosok(i) Ciklus j=1-től 32-ig Ha Eleme-e?(Osztás(i),j) akkor Ki:Pakli(j) Cv Cv Eljárás vége 2.32 Gyakorló feladatok További feladatokat lásd a 2.4 fejezetben, ahol a halmaz típus egy feladaton belül más érdekes típusokkal együtt szerepel! -42- 2.4 Vegyes feladatok 2.41 Mintafeladatok 1. feladat: Az egyetemi oktatókról nyilvántartjuk nevüket, besorolásukat (gyakornok, tanársegéd, adjunktus, docens, egyetemi tanár), fizetésüket. Határozd meg minden besorolási kategóriában az oktatók átlagfizetését! (Felsorolás és rekord) Megoldás: Minden oktatóról háromféle adatot tartunk nyilván. Mindenkiről ugyanazt a hármat. Tehát egy oktatót fix szerkezetű rekord ír le A mezők név, besorolás, fizetés. A második tulajdonság

lehetséges értékeit ismerjük Számuk véges, és diszkrétek. Ezért ez legyen felsorolt! Ezen indexelt tömbben tároljuk majd az egyes oktatói kategóriák átlagfizetését. Típus BesorolásTípus = (Gyakornok,Tanársegéd,Adjunktus, Docens,Egyetemi tanár) StatTípus = Tömb(BesorolásTípus:Valós) DBTípus = Tömb(BesorolásTípus:egész OktatóTípus (Név Besorolás Fizetés Változó Oktatók Átlagfizetés DB Kategória Oktatószám,i : : : : : = : : : rekord Szöveg BesorolásTípus Valós) Tömb(1.1000:OktatóTípus) StatTípus DBTípus BesorolásTípus Természetes Program: Be:Oktatószám,Oktatók() DB():=0 ÁtlagFizetések():=0 Ciklus i=1-től Oktatószám-ig DB(Oktatók(i).Besorolás):= DB(Oktatók(i).Besorolás)+1 ÁtlagFizetés(Oktatók(i).Besorolás):= ÁtlagFizetés(Oktatók(i).Besorolás)+ Oktatók(i).Fizetés Cv -43- Ciklus Kategória=Gyakornok-tól Egyetemi tanár-ig Ha DB(Kategória)≠0 akkor ÁtlagFizetés(Kategória):=

ÁtlagFizetés(Kategória)/DB(Kategória) Cv Ki:ÁtlagFizetés() Program vége 2.42 Gyakorló feladatok 1. Francia kártya egy-egy színéből 13 lap van A számlapok 3 pontot, a figurásak 5 pontot érnek. Készíts algoritmust mely leoszt 8-at a 13 lapból, majd kiszámítja a leosztás pontértékét! (Felsorolás és halmaz) 2. Az iskolában N tanítási naponként vagyunk kapuügyeletesek Nincs tanítás szombaton, vasárnap és ünnepnap. Írj algoritmust, mely beolvassa a hónap napjainak számát, hanyadikára esnek az ünnepek, a hónap elseje a hét mely napjára esik, hanyadikán leszünk először kapuügyeletesek, majd megadja, hogy mely napokon leszünk kapuügyeletesek! (Felsorolás és halmaz) 3. Egy dolgozóról nyilvántartjuk a nevét, a munkaviszony kezdetének évét, a munkaviszonyban eltöltött évek számától függő besorolást (gyakornok 0-, előadó 3-, főelőadó 7-, tanácsos 12-, főtanácsos 18 évtől). Készíts algoritmust, mely az aktuális évre

elvégzi a besorolást és megadja, hogy hányan tartoznak az egyes kategóriákba! (Felsorolás és rekord) 4. Nyelvvizsgaközpontokban nyilvántartják a vizsgázó nevét, a választott nyelvet (angol, német, olasz, orosz, latin, egyéb), választott szintet (alap-, közép-, felsőfok), írásbelizik-e, szóbelizik-e, fizetendő vizsgadíj. Szóbeli és írásbeli vizsga díjszabása megegyezik. Az egyes nyelvekhez és vizsgaszintekhez tartozó díjszabást külön tárolják. Készíts algoritmust, mely kiszámítja a fizetendő vizsgadíjat! (Felsorolás és rekord) -44- 2.5 Sorozatok 2.51 Lista 2.511Mintafeladatok 1 feladat: Fordítsd meg egy lista sorrendjét a) Az eredeti lista változatlanul hagyásával b) Az eredeti lista transzformációjával. Megjegyzés az a variánshoz: Végighaladunk a régi listán és az elemeket rendre az eredetileg üres új lista elejére tesszük. 1. megoldás: A feladatot az absztrakt műveletekkel oldjuk meg. Típus ElemTípus=

Változó ÖregLista,ÚjLista : ListaTípus ÚjElem : ElemTípus Program: Be:ÖregLista Ha nem Üres-e?(ÖregLista) akkor Üres(ÚjLista) Elsőre(ÖregLista) Ciklus amíg nem Tele-e?(ÚjLista) és nem Végén-e?(ÖregLista) ÚjElem:=ElemÉrték(ÖregLista) BeszúrElé(ÚjLista,ÚjElem) Következőre(ÖregLista) Cv Ha Végén-e?(ÖregLista) akkor ÚjElem:=ElemÉrték(ÖregLista) BeszúrElé(ÚjLista,ÚjElem) Ki:ÚjLista különben Ki:’Menetközben megtelt az új lista’ -45- különben Ki:’Nincs mit megfordítani’ Program vége Megjegyzés: A legtöbb programozási nyelv , mint a turbo Pascal is, természetesen nem engedi meg összetett adattípus beolvasását billentyűzetről. Ezért listára vonatkozó beolvasó és kiírató eljárást kell írni. A beolvasó eljárásban az ElemTípus Üres értékéig olvassuk az adatokat és fűzzük azokat hozzá az eredetileg üres ÖregListához. Kiíratásnál végighaladunk az ÚjListán és kiírjuk az adatokat Feltételezzük,

hogy az ÖregLista számára van elég hely. A Be:Öreglista utasítás helyett használjuk az alábbi algoritmusrészletet! Üres(ÖregLista) Be:ÚjElem Ciklua amíg ÚjElem≠Üres BeszúrMögé(ÖregLista,ÚjElem) Be:ÚjElem cv A Ki:ÚjLista utasítás helyett használjuk az alábbi algoritmusrészletet! Elsőre(ÚjLista) Ciklus amíg nem Végén-e?(ÚjLista) Ki:ElemÉrték(ÚjLista) Következőre(ÚjLista) Cv Ki:ElemÉrték(ÚjLista) 2. megoldás: Oldjuk meg a feladatot statikusan láncolt ábrázolás mellett a reprezentáció szintjén! A stratégia nem változik az absztrakt műveletekkel megalkototthoz képest. Lista beolvasásaként, a listát reprezentáló összetevőket olvassuk be, különben egy túldokumentált sorszerűséget hoznánk csak létre. Lista kiíratása egy lista szekvenciális feldolgozásával azonos elven történik. Konstans MaxHossz= Típus ElemTípus IndexTípus ListaElemTípus (Adat Köv ListaTípus (Fej,SzFej,Akt Elemek = = = : : = : : 0.MaxHossz

rekord ElemTípus IndexTípus) rekord IndexTípus Tömb(1.MaxHossz:ListaElemTípus)) -46- Megjegyzés: Szokásos a ListaTípus-ban egy logikai típusú mezőt is elhelyezni hiba jelzése céljából. Mivel azonban reprezentáció szintjén írjuk meg az algoritmust, gondoskodni fogunk a hibák megelőzéséről. Statikus láncolásnál nem vizsgáljuk, hogy van-e elég hely, mert ha nem lenne, le sem fordítaná a programot a fordító. Változó ÖregLista,ÚjLista : ListaTípus ÚjElem : ElemTípus I,Új : IndexTípus Program: Be:ÖregLista.Fej,ÖregListaSzFej,ÖregListaElemek() Ha ÖregLista.Fej≠0 akkor ÚjLista.SzFej:=1 ÚjLista.Fej:=0 ÚjLista.Akt:=0 Ciklus i=1-től MaxHossz-1-ig ÚjLista.Elemek(i)Köv:=i+1 Cv ÚjLista.Elemek(MaxHossz)Köv:=0 ÖregLista.Akt:=ÖregListaFej Ciklus amíg ÖregLista.Akt≠0 Új:=ÚjLista.SzFej ÚjLista.SzFej:=ÚjListaElemek(ÚjListaSzFej)Köv ÚjLista.Elemek(Új)Adat:= ÖregLista.Elemek(ÖregListaAkt)Adat ÚjLista.Elemek(Új)Köv:=ÚjListaFej

ÚjLista.Fej:=Új ÖregLista.Akt:= ÖregLista.Elemek(ÖregListaAkt)Köv Cv ÚjLista.Akt:=ÚjListaFej Ciklus amíg ÚjLista.Akt≠0 Ki:ÚjLista.Elemek(ÚjlistaAkt)Adat Újlista.akt:=ÚjlistaElemek(ÚjListaAkt)Köv Cv különben Ki:’Nincs minek a sorrendjét megfordítani’ Program vége -47- 3. megoldás: Oldjuk meg a feladatot dinamikusan láncolt ábrázolás mellett a reprezentáció szintjén! Ezen reprezentáció esetén végig figyelni kell, hogy van- e hely újabb listaelem számára. Típus ElemTípus ListaElemMut ListaElemTip (Adat Köv ListaTípus (Akt,Fej = = = : : = : ^ListaElemTip rekord ElemTípus ListaElemTip) rekord ListaElemMut) Megjegyzés: Szokás a ListaTípus rekordba felvenni egy logikai típusú mezőt a hibák detektálására. Mivel azonban reprezentáció szintjén oldjuk meg a feladatot, igyekszünk előre kiküszöbölni minden hibalehetőséget. Változó ÖregLista,ÚjLista : ListaTípus Új : ListaElemMut ÚjElem : ElemTípus Program:

Öreglista.Fej:=NIL ÖregLista.Akt:=NIL Be:ÚjElem Ciklus amíg Méret(ListaElemTip)≤SzabadMemória és ÚjElem≠Üres Lefoglal(Új) Új^.Adat:=ÚjElem Új^.Köv:=NIL Ha ÖregLista.Fej=NIL akkor ÖregLista.Fej:=Új különben ÖregLista.Akt^Köv:=Új elág vége ÖregLista.Akt:=Új Be:ÚjElem Cv Ha ÖregLista.Fej≠NIL akkor ÖregLista.Akt:=ÖregListaFej ÚjLista.Fej:=NIL ÚjLista.Akt:=NIL -48- Ciklus amíg Méret(ListaElemTip)≤SzabadMemória és ÖregLista.Akt≠NIL Lefoglal(Új) Új^.Adat:=ÖregListaAkt^Adat Új^.Köv:=ÚjListaFej ÚjLista.Fej:=Új ÖregLista.Akt:=ÖregListaAkt^Köv Cv Ha ÖregLista.Akt=NIL akkor ÚjLista.Akt:=ÚjlistaFej Ciklus amíg ÚjLista.Akt≠NIL Ki:ÚjLista.Akt^Adat ÚjLista.Akt:=ÚjListaAkt^Köv Cv különben Ki:’Menetközben elfogyott a memória!’ elág vége különben Ki:’Nincs minek a sorrendjét megfordítani’ elág vége Program Vége Megjegyzés a b variáns megoldásaihoz: Mivel az eredeti listát transzformáljuk, fel sem merülhet

a kérdés, hogy van-e elég hely, ha már az eredeti lista a memóriában van. Beolvasó és kiírató eljárásokat nem írunk, inkább úgy teszünk mintha a lista típus lehetne ilyen uatsítások argumentuma. 1. megoldás: A feladatot az absztrakt műveletek segítségével oldjuk meg A lista elemeit az alábbi ábra szerint pakoljuk át. 1 2 3 4 Típus ElemTípus= Változó Hossz,i : Természetes Lista : ListaTípus AktElem : ElemTípus -49- Program: Be:Lista Ha nem Üres-e?(Lista) akkor Hossz:=1 Elsőre(Lista) Ciklus amíg nem Végén-e?(Lista) Hossz:=Hossz+1 Következőre(Lista) Cv Ciklus i=1-től (Hossz-1)-ig Elsőre(Lista) Ciklus j=1-től Hossz-i-1-ig Következőre(Lista) Cv AktElem:=ElemÉrték(Lista) Kihagy(Lista) Ciklus amíg nem Végén-e?(Lista) Következőre(Lista) Cv BeszúrMögé(Lista,AktElem) Cv Ki:Lista különben Ki:’Nincs mit átlácolni’ Program vége 2. megoldás: A feladatot statikus láncolás mellett oldjuk meg a reprezentáció szintjén. Nem kell

mozgatnunk az adatokat, csak át kell írni a mutatók értékét A folyamatot az alábbi ábrán szemléltetjük. 0. lépés: 0 1. lépés: 0 0 2. lépés: 0 0 3. lépés: 0 0 k. lépés: 0 -50- Konstans MaxHossz= Típus ElemTípus = IndexTípus = ListaElemTípus = (Adat : Köv : ListaTípus = (Fej,SzFej, Akt : Elemek : 0.MaxHossz rekord ElemTípus IndexTípus) rekord IndexTípus Tömb(1.MaxHossz:ListaElemTípus)) Megjegyzés: Szokás a ListaTípusban elhelyezni egy logikai típusú mezőt hibajelzés céljából. Mivel azonban a reprezentáció szintjén oldjuk meg a feladatot gondoskodhatunk az algoritmusban a hibák megelőzéséről. Változó Lista : ListaTípus Akt,AktE,AktU : IndexTípus Program: Be:Lista Ha Lista.fej≠0 akkor AktE:=0 Akt:=Lista.Fej Ciklus amíg Akt≠0 AktU:=Lista.Elemek(Akt)Köv Lista.Elemek(Akt)Köv:=AktE AktE:=Akt Akt:=AktU Cv Lista.Fej:=AktE Ki:Lista különben Ki:’Nincs mit megfordítani’ Elág vége Program vége Megjegyzés: Akt

helyett használhattuk volna a Lista.Akt mezőt, De ekkor a következetesség kedvéért AktE és AktU változókat is a Lista egy-egy mezőjeként kellett volna elhelyezni. -51- 3. megoldás: A feladatot dinamikusan láncolt ábrázolás mellett a reprezentáció szintjén oldjuk meg. A megoldás stratégiája azonos az előzővel Típus ElemTípus ListaElemMut LiataElemTípus (Adat Akt,Fej ListaTípus (Akt,Fej = = ^LitaElemTípus = rekord : ElemTípus : ListaElemMut) = rekord : ListaElemMut) Megjegyzés: Szokás a ListaTípusban elhelyezni egy logikai típusú mezőt hibajelzés céljából. Mivel azonban a reprezentáció szintjén oldjuk meg a feladatot gondoskodhatunk az algoritmusban a hibák megelőzéséről. Változó Lista : ListaTípus Akt,AktE,AktU : ListaElemMut Program: Be:Lista Ha Lista.Fej≠NIL akkor AktE:=NIL Akt:=Lista.Fej Ciklus amíg Akt≠NIL AktU:=Akt^.Köv Akt^.Köv:=Akt AktE:=Akt Akt:=AktU Cv Lista.Fej:=AktE Ki:Lista különben Ki:’Nincs mit

megfordítani’ Elág vége Program vége Megjegyzés: Akt helyett használhattuk volna a Lista.Akt mezőt, de ekkor a következetesség kedvéért AktE és AktU változókat is a Lista egy-egy mezőjeként kellett volna elhelyezni. -52- 2.512Gyakorló feladatok 1. Személyi számokat tárolunk növekvő sorrendű listába fűzve Készítsd el a férfiak ill. nők személyi számának növekvő listáját, ha a) csak eszázadban született magyar állampolgárok b) nem csak eszázadban született és nem csak magyar állampolgárok szerepelnek az eredeti listában! 2. Rendezz egy listát, a) új listát generálva; b) helyben! 3. Egy osztály tanulói matematika ill fizika versenyen vettek részt A két verseny résztvevői nevük szerinti növekvő rendben listákba vannak fűzve. Készítsd el a csak egy versenyen ill. mindkét versenyen indultak növekvő listáját! 4. Néhány többtag szorzataként előállt polinomban az azonos kitevőjű tagokat még nem vontuk össze. Az

egyes tagok nem nulla együtthatójából és kitevőjéből képzett rendezett párok kitevő szerint csökkenő rendben listába vannak fűzve. Készítsd el az összevonások utáni listát! 5. Az előbbi feladat eredményeként leírt polinomból vonj ki kettőt egymásból! 6. Egy polinomot összes együtthatójának kitevők szerint csökkenő rendű listájával ábrázolunk. Számítsd ki adott helyen vett helyettesítési értékét! 7. A felvételi vizsgák lezajlása után a jelöltek pontszámának, nevének, értesítési címének rendezett hármasa pontszám szerint rendezett listába vannak fűzve. Adott a biztos felvétel ponthatára, valamint a fellebezés alsó ponthatára. Készítsd el a fellebbezésre jogosultak név szerint rendezett listáját! 8. Listában tároljuk egy kosárlabda-szakosztály tagjainak nevét és magasságát, magasság szerinti csökkenő sorrendben. Készíts két új listát, melyek egyikében minden második kosaras, másikában a

maradék szerepel! A két új lista magasság szerint rendezett legyen! Az eredeti lista alakuljon át a két új listává! -53- 2.52 Verem 2.521Mintafeladatok 1. feladat: Ellenőrizd egy összetett kifejezés zárójelezésének helyességét, ha kerek, szögletes, kapcsos zárójelek mindegyike előfordulhat! Megjegyzések: A zárójel-helyesség ellenőrzésének elvei: • • • Csukó zárójel nem lehet megelőző nyitózárójel nélkül. A kifejezés vizsgálatának végén nem maradhat bezáratlan nyitózárójel. Nem lehet keresztzárójelezés, azaz egy fajta nyitózárójel után nem következhet másfajta csukó zárójel. Ennek megfelelően célszerű a kifejezés elemzése során a nyitózárójeleket verembe tenni, csukó zárójel esetén az utolsó nyitózárójelet kivenni. Hibás a kifejezés, ha bármely csukó zárójel esetén a verem tetején nem neki megfelelő nyitózárójel van, vagy üres a verem, ill. a kifejezés levizsgálása után nem üres

a verem. 1. megoldás: A feladatot a verem adatszerkezet absztrakt műveleteivel oldjuk meg Nem foglalkozunk annak lehetőségével, hogy elfogyhat a hely. Konstans Zárójelek : Halmaz(Karakter) = [’{’,’}’,’[’,’]’,’(’, ’)’] Nyitók : Halmaz(Karakter) = [’{’,’[’,’(’] Csukók : Halmaz(Karakter) = [’)’,’]’,’}’] Típus ElemTípus=Karakter Változó ZárójelVerem : VeremTípus Kifejezés : Szöveg i : Természetes VanHiba : Logikai Eldob : ElemTípus Program: Be:Kifejezés Üres(ZárójelVerem) i:=1 VanHiba:=↓ -54- Ciklus amíg i≤Hossz(Kifejezés) és nem VanHiba Ha nem Elelme-e?(Zárójelek,Kifejezés[i]) akkor i:=i+1 különben Ha Eleme-e?(Nyitók,Kifejezés[i]) akkor Verembe(ZárójelVerem,Kifejezés[i]) i:=i+1 különben Ha Üres-e?(ZárójelVerem) akkor VanHiba:=↑ különben Ha Kifejezés[i]=’)’ és Tető(ZárójelVerem)≠’(’ vagy Kifejezés[i]=’]’ és Tető(ZárójelVerem)≠’[’ vagy Kifejezés[i]=’}’

és Tető(ZárójelVerem)≠’{’ akkor VanHiba:=↑ különben Veremből(zárójelVerem,Eldob) i:=i+1 elág vége elág vége elág vége elág. vége Cv VanHiba:=(i≤Hossz(Kifejezés)) vagy nem Üres-e?(ZárójelVerem) Ha VanHiba akkor Ki:’A kifejezés zárójelezése hibás’ különben Ki:’A kifejezés zárójelezése helyes’ Program vége 2. megoldás: A feladatot szekvenciális ábrázolás mellett oldjuk meg a reprezentáció szintjén. Továbbra sem vizsgáljuk, hogy elég nagy-e a verem Konstans MaxMélység = Zárójelek : Halmaz(Karakter) = [’{’,’}’,’[’,’]’, ’(’,’)’] Nyitók : Halmaz(Karakter) = [’{’,’[’,’(’] Csukók : Halmaz(Karakter) = [’)’,’]’,’}’] -55- Típus ElemTípus VeremTípus (Elemek Tető = = : : Karakter rekord Tömb(1.MaxMélység:ElemTípus) 0.MaxMélység) Megjegyzés: Szokás a VeremTípus-ban egy logikai típusú mezőt elhelyezni a veremkezelés során fellépő hibák jelzésére. Mivel a

reprezentáció szintjén oldjuk meg a feladatot, az algoritmusban előre gondoskodunk a hibák elkerüléséről. A VanHiba változó a kifejezés zárójelezésére vonatkozik, semmi köze a verem műveletekhez. Változó ZárójelVerem Kifejezés i VanHiba : : : : VeremTípus Szöveg Természetes Logikai Program: Be:Kifejezés i:=1 VanHiba:=↓ ZárójelVerem.Tető:=0 Ciklus amíg i≤Hossz(Kifejezés) és nem VanHiba Ha nem Elelme-e?(Zárójelek,Kifejezés[i]) akkor i:=i+1 különben Ha Eleme-e?(Nyitók,Kifejezés[i]) akkor ZárójelVerem.Tető:=ZárójelVeremTető+1 ZárójelVerem.Elemek(ZárójelVeremTető):= Kifejezés[i] i:=i+1 különben Ha ZárójelVerem.Tető=0 akkor VanHiba:=↑ különben Ha Kifejezés[i]=’)’ és Tető(ZárójelVerem)≠’(’ vagy Kifejezés[i]=’]’ és Tető(ZárójelVerem)≠’[’ vagy Kifejezés[i]=’}’ és Tető(ZárójelVerem)≠’{’ akkor VanHiba:=↑ -56- különben ZárójelVerem.Tető:=ZárójelVeremTető-1 i:=i+1 elág

vége elág vége elág vége elág. vége Cv VanHiba:=(i≤Hossz(Kifejezés)) vagy (ZárójelVerem.Tető≠0) Ha VanHiba akkor Ki:’A kifejezés zárójelezése hibás’ különben Ki:’A kifejezés zárójelezése helyes’ Program vége 3. megoldás: A feladatot dinamikusan láncolt verem segítségével oldjuk meg a reprezentáció szintjén. A verem elemei rendre mutatóval mutatnak egymásra a tetejétől lefelé. A verem alján lévő elem NIL-re mutat Továbbra sem vizsgáljuk, hogy elég-e a hely a verem számára. Erre módszert láttunk már dinamikusan láncolt lista esetében. Konstans Zárójelek : Halmaz(Karakter) = [’{’,’}’,’[’,’]’,’(’, ’)’] Nyitók : Halmaz(Karakter) = [’{’,’[’,’(’] Csukók : Halmaz(Karakter) = [’)’,’]’,’}’] Típus ElemTípus VeremElemMut VeremElemTípus (Adat Köv VeremTípus (Tető Hiba = = = : : = : : Karakter ^VeremElemTípus rekord ElemTípus VeremElemMut) rekord VeremElemMut Logikai)

Megjegyzés: VeremTípus.Hiba a veremkezelés során fellépő hibák jelzésére szolgál Mivel reprezentáció szintjén oldjuk meg a feladatot az algoritmusban gondoskodunk a hibák elkerüléséről. Így az említett mező szerepét veszti Ha elhagynánk a típusból, a VeremTípus egyetlen típusos mutatóvá fajulna. Változó ZárójelVerem Kifejezés i VanHiba Új,Kidob : : : : : VeremTípus Szöveg Természetes Logikai VeremElemMut -57- Program: Be:Kifejezés ZárójelVerem.Tető:=NIL i:=1 VanHiba:=↓ Ciklus amíg i≤Hossz(Kifejezés) és nem VanHiba Ha nem Elelme-e?(Zárójelek,Kifejezés[i]) akkor i:=i+1 különben Ha Eleme-e?(Nyitók,Kifejezés[i]) akkor Lefoglal(Új) Új^.Adat:=Kifejezés[i] Új^.Köv:=ZárójelVeremTető ZárójelVerem.Tető:=Új i:=i+1 különben Ha ZárójelVerem.Tető=NIL akkor VanHiba:=↑ különben Ha Kifejezés[i]=’)’ és Tető(ZárójelVerem)≠’(’ vagy Kifejezés[i]=’]’ és Tető(ZárójelVerem)≠’[’ vagy

Kifejezés[i]=’}’ és Tető(ZárójelVerem)≠’{’ akkor VanHiba:=↑ különben Kidob:=ZárójelVerem.Tető ZárójelVerem.Tető:=ZárójelVeremTető^Köv Felszabadít(Kidob) i:=i+1 elág vége elág vége elág vége elág. vége Cv VanHiba:=(i≤Hossz(Kifejezés)) vagy ZárójelVerem.Tető≠NIL Ha VanHiba akkor Ki:’A kifejezés zárójelezése hibás’ különben Ki:’A kifejezés zárójelezése helyes’ Program vége -58- 2.522Gyakorló feladatok 1. Készíts szintaktikus elemző algoritmust csak számlálós ciklust ismerő nyelven írt program ciklusainak ellenőrzésére. Az algoritmus új ciklus esetén ellenőrzi, hogy a ciklusváltozó foglalt-e már. Ha nem, akkor a ciklusváltozó nevét és a ciklus kezdetének címét tárolja. Ciklus zárásakor ellenőrzi, hogy az utoljára megkezdett ciklust zárja-e le, s ha igen, akkor annak adatait kiveszi a veremből. 2. Egy szójátékban csak olyan karaktersorozatokat fogadunk el, melyekben szimmetrikus

betücsoportok vannak és a teljes szöveg eleje és vége egymás tükörképei. Készítsd el a próbálkozásokat ellenőrző algoritmust! -59- 2.53 Sor 2.531Mintafeladatok 1. feladat: Szimuláld egy mozgólépcső működését! A napi működés kezdetén üres a lépcső. Egy időegység alatt a mozgólépcső elejére érő lépcsőfokról lelépnek a rajta állók, minden lépcsőfok továbbhalad egy fázist, a végén felbukkanó lépcsőfokra véletlenszerűen lép föl maximum két ember. A napi működés végén fázisokon keresztül ürül ki a mozgólépcső. Jelenítsd meg fázisonként a lelépők , a lépcsőfokokon állók, fellépők számát! Megjegyzés: A nap elején üres a mozgólépcső. Nyitás után elkezd feltöltődni a lépcső. Mire az első fellépő lépcsőfoka felér a mozgólépcső tetejére, a lépcső ugyan hézagosan, de kitöltődik. Innen zárásig a tetejéről lelép valaki, a lépcsőfokok egyet feljebb lépnek, alul belép egy üres

lépcsőfok, erre lép(nek) fel valaki(k). Záráskor alul nem engednek senkit fellépni, pontosabban a folyamat forrása elapad, az utasok a mozgólépcső tetején lépcsőfokonként távoznak. 1. Megoldás: A feladatot absztrakt sorkezelő műveletekkel oldjuk meg Ekkor persze nem tudjuk kiírni az egyes lépcsőfokokon állók számát. Típus ElemTípus = Természetes Változó Mozgólépcső : SorTípus Belépő,Kilépő : ElemTípus VégeNap : Szöveg Program: Üres(Mozgólépcső) Ciklus amíg nem Tele-e?(Mozgólépcső) Belépő:=Véletlen(3) Sorba(Mozgólépcső,Belépő) Ki:Belépő Cv Ciklus Sorból(Mozgólépcső,Kilépő) Ki:Kilépő Belépő:=Véletlen(3) Sorba(Mozgólépcső,Belépő) Ki:Belépő Be:VégeNap amíg VégeNap≠’Vége’ -60- Ciklus amíg nem Üres-e?(Mozgólépcső) Sorból(Mozgólépcső,Kilépő) Ki:Kilépő cv Program vége 2. megoldás: A feladatot ciklikusan működő szekvenciális ábrázolás mellett a reprezentáció szintjén oldjuk meg.

Mivel hozzáférünk az adatszerkezetet megvalósító eszközökhöz, az absztrakt műveletekhez képest direkt műveleteket is végezhetünk. Így a sor tartalmát ki tudjuk írni. Konstans MaxHossz= Típus ElemTípus = Természetes SorTípus = rekord (Adat : Tömb(1.MaxHossz:ElemTípus) Eleje, Vége, DB : 0.MaxHossz Hiba : Logikai) Megjegyzés: Mivel a feladatot reprezentáció szinten oldjuk meg, a SorTípus.Hiba mennyiség elhagyható lenne, mert az algoritmus megírása során gondoskodunk a hibák elkerüléséről. Eleje és Vége a következő kivevés ill betevés helyére mutatnak Változó Mozgólépcső Belépő,Kilépő VégeNap N,i,j : : : : SorTípus ElemTípus Szöveg 1.MaxHossz Program: Mozgólépcső.Eleje=1 MozgóLépcső.Vege:=1 Mozgólépcső.DB:=0 Mozgólépcső.hiba:=↓ Be:N Ciklus amíg Mozgólépcső.DB<N Belépő:=Véletlen(3) Mozgólépcső.Adat(MozgólépcsőVége):=Belépő Mozgólépcső.Vége:= MozgólépcsőVége+1

Mozgólépcső.DB:=MozgólépcsőDB+1 Ki:Belépő i:=Mozgólépcső.Eleje -61- Ciklus j= 1-től Mozgólépcső.DB-ig Ki:Mozgólépcső.Adat(i) Ha i=N akkor i:=1 kúlönben i:=i+1 cv Cv Ciklus Kilépő:=Mozgólépcső.Adat(MozgólépcsőEleje) Ha Mozgólépcső.Eleje=N akkor Mozgólépcső.Eleje:=1 különben Mozgólépcső.Eleje:=MozgólépcsőEleje+1 Ki:Kilépő Belépő:=Véletlen(3) Mozgólépcső.Adat(MozgólépcsőVége):=Belépő Ha Mozgólépcső.Vége=N akkor Mozgólépcső.Vége:=1 különben Mozgólépcső.Vége:=MozgólépcsőVége+1 i:=Mozgólépcső.Eleje Ciklus j=1-től Mozgólépcső.DB-ig Ki:Mozgólépcső.Adat(i) Ha i=N akkor i:=1 különben i:=i+1 Cv Be:VégeNap Amíg VégeNap≠’Vége’ Ciklus amíg Mozgólépcső.DB>0 Kilépő:=Mozgólépcső.Adat(MozgólépcsőEleje) Ha Mozgólépcső.Eleje=N akkor Mozgólépcső.Eleje:=1 különben Mozgólépcső.Eleje:=MozgólépcsőEleje+1 Ki:Kilépő Mozgólépcső.DB:=MozgólépcsőDB-1 i:=Mozgólépcső.Eleje

Ciklus j=1-től Mozgólépcső.DB-ig Ki:Mozgólépcső.Adat(i) Ha i=N akkor i:=1 különben i:=i+1 Cv Cv Program vége -62- 3. megoldás: A feladatot dinamikusan láncolt ábrázolás mellett oldjuk meg a reprezentáció szintjén. Be kell olvasni a mozgólépcső hosszát Feltételezzük, hogy elég hely van a memóriában, különben érdemi szimulációba nem is kezdhetünk. A sor elemeinek menet közbeni lefoglalása és felszabadítása miatt Eleje és Vége mutatók a sor első és utolsó elemére mutatnak. Típus ElemTípus SorelemMut SorElemTípus (Adat Köv SorTípus (Eleje, Vége Db = = = : : = 0.3 ^SorElemTípus rekord ElemTípus SorelemMut) rekord : SorElemMut : Egész) Megjegyzés: Az eredeti SorTípus-ból elhagytuk a Hiba mezőt, ami a sor-műveletek megvalósítása során fellépő hibák detektálására szolgálna. Mivel azonban reprezentáció szintjén oldjuk meg a problémát, az algoritmussal kikerüljük az esetleges hibalehetőségeket.

Feltételezzük, hogy elég a memória a sor megvalósításához. Ezt egyébként csak akkor kellene vizsgálni, amikor beolvassuk a mozgólépcső hosszát. Nyilván ennyi SorElemTípus felépítésű rekordnak el kell férnie a heap-ben. Változó Mozgólépcső Akt,Belépő,Kilépő i VégeNap : : : : SorTípus SorelemMut Természetes Szöveg Program: Be:Mozgólépcső.DB Lefoglal(Belépő) Belépő^.Adat:=Véletlen(3) Belépő^.Köv:=NIL Mozgólépcső.eleje:=Belépő Mozgólépcső.Vége:=Belépő Ki:Belépő^.Adat Ciklus i=1-től Mozgólépcső.DB-1-ig Lefoglal(Belépő) Belépő^.Adat:=Véletlen(3) Mozgólépcső.Vége^Köv:=Belépő Belépő^.Köv:=NIL Mozgólépcső.Vége:=Belépő Akt:=Mozgólépcső.Eleje Ciklus amíg Akt≠NIL Ki:Akt^.Adat Akt:=Akt^.Köv Cv Cv -63- Ciklus Kilépő:=Mozgólépcső.Eleje Mozgólépcső.Eleje:=MozgólépcsEleje^Köv Ki:Kilépő^.Adat Felszabadít(Kilépő) Lefoglal(Belépő) Belépő^.Adat:=Véletlen(3) Belépő^.Köv:=NIL

Mozgólépcső.Vége^Köv:=Belépő Mozgólépcső.Vége:=Belépő Akt:=Mozgólépcső.Eleje Ciklus amíg Akt≠NIL Ki:Akt^.Adat Akt:=Akt^.Köv Cv Be:VégeVan amíg VégeVan≠’Vége’ Ciklus i=1-től Mozgólépcső.DB-ig Kilépő:=Mozgólépcső.Eleje Mozgólépcső.Eleje:=MozgólépcsőEleje^Köv Ki:Kilépő^.Adat Felszabadít(Kilépő) Akt:=Mozgólépcső.Eleje Ciklus amíg Akt≠NIL Ki:Akt^.Adat Akt:=Akt^.Köv Cv Cv Felszabadít(Mozgólépcső.Eleje) Felszabadít(Mozgólépcső.Vége) Program vége 2.532Gyakorló feladatok 1. Színházi előadás után a parkoló kapuját fő- ill mellékúton közelíthetik meg az autók. A kapuőr a főútvonalról 3, a mellékútvonalról 1 autót enged ki, de időegységenként csak egyet. A két út gyakorlatilag megtelik, mire a kapuőr elkezdi kiengedni az autókat, tekintve, hogy kifelé kell fizetni. Írj algoritmust a kapuőr számára! 2. Gyűrűbe fűzött n ember közül mondóka segítségével minden k-adikat kihúzzuk mígnem

már csak egyvalaki marad. Készítsd el a kiszámoló algoritmust! A mondókának csak a szótagszáma érdekes. 3.Futtasd össze két rendezett sor tartalmát egy harmadikba! -64- 4. :Szimuláld egy fizető autópályabejáró forgalmát! K db sor van, melyekhez időegységenként véletlenszerűen érkezik maximum L db autó. Igyekeznek a legrövidebb sorba állni. Ezalatt minden sort egy-egy autó hagyja el Helyfoglalás szempontjából némiképp hatékony reprezentációt válassz! -65- 2.54 Összetett aritmetikai kifejezések kiértékelése 2.541 Mintafeladatok 1. feladat: Képezd az alábbi kifejezés post fix formáját! x := (a + 3 / m ∗ n ) + (b − c + 1) ∗ (u + 2 ∗ 5 − v ) Add meg a verem és a post fix forma állapotát minden lexikális egység feldolgozása után! Megoldás: Mint az ismeretes a post fix forma infix formához viszonyított jellemzői: • • • Zárójel mentes alakot ad. Az operandusok sorrendje változatlan. Az operandusok

megelőzik az operátorukat. Egy ilyen alak előállításának főbb elvei a következők lesznek: • • • Mind a post fix, mind az infix forma un. lexikális egységek sorozata, mely lexikális egység fogalom magába foglalja az operandusokat és az operátorok legtágabb értelmezésű körét. A post fix formát az infix forma egyszeri szekvenciális feldolgozásával állítjuk elő. A lexikális egységek feldolgozásának szabályai vannak. Lexikális egység feldolgozásának szabályai: • • • • • Operandus – a post fix forma végére kerül. Nyitózárójel – a verembe kerül. Csukózárójel- - az első nyitózárójelig minden operandust kiveszünk a veremből és rendre a post fix alak végéhez írjuk. A zárójelpárt eldobjuk Operátor – A nála nem alacsonyabb prioritású műveleteket kivesszük a verem tetejéről és rendre a post fix forma végéhez írjuk. Az aktuális operátor a verembe kerül. Feldolgozás után a verem tetején

lévőket rendre a post fix forma végéhez írjuk. Operátorok precedenciája (A legmagasabb prioritásútól haladunk az alacsonyabb prioritású felé.) • • • • Függvények Egyoperandusú Kétoperandusú multiplikatív Kétoperandusú additív operátorok. -66- Megjegyzés: Elhelyezhetnénk a precedenciarendben a zárójeleket is. Mindkét zárójel precedenciája a lehető legkisebb. A folyamatot táblázat segítségével jegyezzük le. A táblázat fejlécének mezői: lépés sorszáma (S), post fix forma, aktuálisan feldolgozott elem (A.E), a verem állapota (a verem szája jobbra lesz), infix formából még fel nem dolgozott rész. Minden sor a benne előírt lépés végeredményét tartalmazza. S 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 Post fix forma A A a3 a3 a3m a3m/ a3m/n a3m/n*+ a3m/n*+ a3m/n*+ a3m/n*+b a3m/n*+b a3m/n*+bc a3m/n*+bc+ a3m/n*+bc+1 a3m/n*+bc+1+ a3m/n*+bc+1+ a3m/n*+bc+1+ a3m/n*+bc+1+u a3m/n*+bc+1+u

a3m/n*+bc+1+u2 a3m/n*+bc+1+u2 a3m/n*+bc+1+u25 a3m/n*+bc+1+u25 a3m/n*+bc+1+u25v a3m/n*+bc+1+u25v-+ a3m/n*+bc+1+u25v-++ A.E Verem . ( a + 3 / m * n ) + ( b c + 1 ) * ( u + 2 * 5 v ) ( ( (+ (+ (+/ (+/ (+* (+* + +( +( +(+(+(+ +(+ + +* +*( +*( +*(+ +*(+ +*(+ +*(+ +*(++(++ Infix forma (a+3/m*n)+(b-c+1)(u+25-v) a+3/m*n)+(b-c+1)(u+25-v) +3/m*n)+(b-c+1)(u+25-v) 3/m*n)+(b-c+1)(u+25-v) /m*n)+(b-c+1)(u+25-v) m*n)+(b-c+1)(u+25-v) *n)+(b-c+1)(u+25-v) n)+(b-c+1)*(u+25-v) )+(b-c+1)*(u+25-v) +(b-c+1)*(u+25-v) (b-c+1)*(u+25-v) b-c+1)*(u+25-v) -c+1)*(u+25-v) c+1)*(u+25-v) +1)*(u+25-v) 1)*(u+25-v) )*(u+25-v) *(u+25-v) (u+2*5-v) u+2*5-v) +2*5-v) 2*5-v) *5-v) 5-v) -v) v) ) Tehát az előállított post fix forma: a,3,m,/,n,*,+,b,c,+,1,+,u,2,5,,v,-,+,,+ -67- 2. feladat: Értékeld ki az alábbi post fix formát! a,p,r,s,*,2,/,-,/,k,m,-,6,+,,e,f,g,,/,+ a=3, p=11, r=4, s=5, k=3, m=2, e=10, f=5, g=2 Megoldás: A post fix forma kiértékelésének alapelvei a következők lesznek: • A post fix forma

un. lexikális egységek sorozata, mely lexikális egység fogalom magába foglalja az operandusokat és az operátorok legtágabb értelmezésű körét. A post fix formát egyszeri szekvenciális feldolgozással értékeljük ki. A lexikális egységek feldolgozásának szabályai vannak. • • Lexikális egység feldolgozásának szabályai: • • Operandus – verembe kerül. Operátor – operandusait kivesszük a verem tetejéről, elvégezzük a műveletetet (a második operandust vesszük ki előbb) és az eredményt visszatesszük a verembe. Feldolgozás végeztével az eredmény a verem alján található. • A folyamatot táblázat segítségével jegyezzük le. A táblázat fejlécének mezői: lépés sorszáma (S), a verem állapota (a verem szája jobbra), aktuálisan feldolgozott elem (A.E), a post fix formából még fel nem dolgozott rész Minden sor a benne előírt lépés végeredményét tartalmazza. S 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Verem 3

3,11 3,11,4 3,11,4,5 3,11,20 3,11,20,2 3,11,10 3,1 3 3,3 3,3,2 3,1 3,1,6 3,7 21 21,10 A.E . Post fix forma a,p,r,s,*,2,/,-,/,k,m,-,6,+,,e,f,g,,/,+ 3,11,4,5,*,2,/,-,/,3,2,-,6,+,,10,5,2,,/,+ 3 11,4,5,*,2,/,-,/,3,2,-,6,+,,10,5,2,,/,+ 11 4,5,*,2,/,-,/,3,2,-,6,+,,10,5,2,,/,+ 4 5,*,2,/,-,/,3,2,-,6,+,,10,5,2,,/,+ 5 *,2,/,-,/,3,2,-,6,+,,10,5,2,,/,+ * 2,/,-,/,3,2,-,6,+,,10,5,2,,/,+ 2 /,-,/,3,2,-,6,+,*,10,5,2,,/,+ / -,/,3,2,-,6,+,*,10,5,2,,/,+ - /,3,2,-,6,+,*,10,5,2,,/,+ / 3,2,-,6,+,*,10,5,2,,/,+ 3 2,-,6,+,*,10,5,2,,/,+ 2 -,6,+,*,10,5,2,,/,+ - 6,+,*,10,5,2,,/,+ 6 +,*,10,5,2,,/,+ + *,10,5,2,,/,+ * 10,5,2,,/,+ 10 5,2,*,/,+ -68- 17 18 19 20 21 21,10,5 21,10,5,2 21,10,10 21,1 22 5 2 * / + 2,*,/,+ *,/,+ /,+ + Tehát a kifejezés értéke 22. 2.542Gyakorló feladatok 1. Képezd az alábbi kifejezés post fix formáját! a := (i + h ) / (k + (l + m ) ∗ j ) ∗ 5 − g + b − (d − c / e ) ∗ f 2. Add meg a verem és a post fix forma állapotát minden lexikális egység feldolgozása

után! 3. Értékeld ki az alábbi post fix formát! a,b,c,d,-,e,*,+,,f,/,a,b,+,e,,+, ahol a=8, b=9, c=7, d=5, e=3, f=2. -69- 2.55 Fák 2.551Bináris fa 2.5511 Mintafeladatok 1. feladat: Készítsd el az alábbi bináris fa szintfolytonos ábrázolását! A B C D E F G Megoldás: Szintfolytonos ábrázolás lényegiösszetevői: • • • • • 0. szinten van a fa gyökere Minden további i. szintre igaz, hogy rajta az (i-1) szinten lévők rákövetkezői vannak. Így minden szintnek van maximális elemszáma (2i). A szinteknek sorfolytonosan foglalunk helyet. Hiányzó elem helyére speciális, flag jellegű értéket írunk. Megkezdett szinteket teljesen kitöltjük. Válasszunk most egy, az angol ábécébe nem illő karaktert speciális értéknek! A fenti fa szintfolytonos ábrázolással tehát: A B C D E # # # -70- F G # # # # # 2. feladat: Az alábbi szintfolytonos ábrázolásból rekonstruáld a bináris fát! A B C # D E # # #

F # # G # # Megoldás: A szintfolytonos ábrázolásról szerzett ismereteink alapján minden elemhez nyilakkal hozzárendeljük a rákövetkezőit: A B C # D E # # # F # # G # # Akit zavarnak a nemlétező elemekből induló nyilak, utólag letörölheti őket, de eleve kihagyni, nagy odafigyelést és gyakorlatot igényel. Az utóbbi kialakul, de az előbbit célszerű megtakarítani egy ugyan redundáns, de automatikus módszerrel. A B C # D E # # # -71- F # # G # # Végül ábrázoljuk a fát: A B C D E E F 3. feladat: Adottak egy ember felmenői szintfolytonos ábrázolással, az anyák mindig megelőzve az apákat. Ismeretlen ősök neve helyén az anonim szó szerepel Írj algoritmust, mely kiválogatja x-nek apja y formában a férfi ősöket, és megadja az ismert férfi ősöknek a lehetséges férfi ősökre vonatkoztatott arányát! 1. Megoldás: Nem foglalkozunk azzal a kérdéssel, hogy ismeretlen személynek lehetnek-e

ismert felmenői. Most csak igyekszünk megtalálni az ábrázolásban azokat a helyeket, ahol férfi ősöknek kellett lenniük, majd megvizsgáljuk, hogy ismertek-e vagy sem. Mivel az adott ábrázolásban az i. helyen lévő felmenői a (2i) és a (2i+1) helyen szerepelnek, az apát a (2i+1). helyen keressük Konstans N= Típus ApaTípus = rekord (Gyermek,Apa : Szöveg) Változó Családfa : Tömb(1.N:Szöveg) ApjaFia : Tömb(1.N:ApaTípus) DBF,DB,i : 1.N Program: Be:Családfa() DBF:=(N-1) div 2 DB:=0 i:=1 -72- Ciklus amíg 2*i<N Ha Családfa(2*i+1)<>’Anonim’ akkor DB:=DB+1 ApjaFia(DB).Gyermek:=Családfa(i) ApjaFia(DB).Apa:=Családfa(2*i+1) elág vége i:=i+1 Cv Ki:ApjaFia(),DBF,DB/DBF Program vége 2. megoldás: Ebben a megoldásban feltételezzük, hogy ismeretlennek egyetlen felmenője sem lehet ismert. 1. Következménye, hogy Családfa(2*i+1)<>’Anonim’ feltétel helyett Családfa(i)<>’Anonim’ és Családfa(2*i+1)<>’Anonim’

feltételt kell majd írni. 2. Következménye, hogy ismeretlennek talált személy összes felmenőit ki lehet venni a vizsgálatból. Ezt nem célszerű megtenni, mert ez egy részfa megtalálását és bejárását jelentené, és elbonyolítaná az algoritmust. Ehelyett csak a két szülőt töröljük a vizsgálandók közül. A még vizsgálandók indexét halmazban tároljuk. Konstans N= Típus ApaTípus = rekord (Gyermek,Apa : Szöveg) Változó Családfa : Tömb(1.N:Szöveg) Ismert : Halmaz(1.N) DBF,DB : 1.N Program: Be:Családfa() DBF:=(N-1) div 2 DB:=0 Ismert:=Üres Ciklus i=1-től N-ig Halmazba(Ismert,i) Cv i:=1 Ciklus amíg 2*i<N és Ismert≠Üres Ha nem Eleme-e?(Ismert,i) akkor Halmazból(Ismert,2*i) Halmazból(Ismert,2*i+1) -73- különben Ha Családfa(i)=’Anonim’ akkor Halmazból(Ismert,i) Halmazból(Ismert,2*i) Halmazból(Ismert,2*i+1) különben Ha Családfa(2*i+1)≠’Anonim’ akkor DB:=DB+1 ApjaFia(DB).Gyermek:=Családfa(i)

ApjaFia(DB).Apa:=Családfa(2*i+1) különben Halmazból(Ismert,2*i+1) Elág vége Halmazból(Ismert,i) elág vége elág vége i:=i+1 Cv. Ki: ApjaFia,DBF,DB/DBF Program vége 4. feladat: Ábrázold statikus láncolással az F1 feladatban szerepeltetett bináris fát! Index Elem 1 A 2 B 3 C 4 D 5 E 6 F 7 G 8 9 10 11 12 13 14 15 Bal Jobb Gyökér SzabadFej Megoldás: Gyökérelem az 1 indexű lesz most. Minden elemhez beírjuk a rákövetkező indexét. Ha ilyen nincs, 0-t írunk A nem használt elemek a bal mutatójukkal egymásre mutatnak, SzabadFej a 8 indexű lesz, hiszen statikusan láncolt ábrázolású bináris fák között az üres fa úgy néz ki, hogy SzabadFej az 1 indexű, az elemek bal mutatójukkal egyre hátrébb lévőkre mutatnak, az utolsó mutatója és a gyökér a 0. Index Elem Bal Jobb 1 A 2 3 Gyökér SzabadFej 2 B 4 5 3 C 0 0 4 D 0 6 5 E 7 0 6 F 0 0 7 G 0 0 8 9 9 1 8 -74- 9 10 11 12 13 14 15 10 11 12 13 14 15 0 5.

feladat: Rekonstruáld az alábbi reprezentációból a bináris fát! Index Elem Bal Jobb 1 A 2 3 Gyökér SzabadFej 2 B 0 4 3 C 5 0 4 D 6 0 5 E 0 7 6 F 0 0 7 G 0 0 8 9 10 11 12 13 14 15 9 10 11 12 13 14 15 0 1 8 Megoldás: Mivel gyökérelem az 1 indexű, csak végig kell haladni a láncoláson és rajzolni kell. Célszerű törekedni a szintek kitöltésére, mert úgy könnyű nyilvántartani, hol van még lehetőség folytatásra. Íme az eredmény: A B C D E F G De hiszen ez a fa szerepelt az F2. feladatban! 6. feladat: Döntsd el egy számokat tartalmazó bináris fáról, hogy piramis-e! Piramis a fa, ha minden részfában a gyökér értéke nagyobb, mint a bal- ill. jobb részfabeli elemek. Megjegyzés : Mivel a bináris fa egy tipikusan rekurzív típus, ráadásul egy állapotból két rekurzív folytatás van, célszerű a feladat megoldására rekurzív algoritmust írni. Ha csak egy rekurzív rákövetkező lenne, az iteratív és a

rekurzív módszer között nem lenne számottevő különbség. Tehát a feladat rekurzív átfogalmazása így szólna. Piramis a fa, ha gyökéreleme nagyobb mindkét oldali rákövetkezőjénél, és a rákövetkezőkhöz tartozókét részfa is piramis. A részfák között kitüntetett szerepű a levélelem, mert ő olyan részfa, melynek csak gyökere van. Így egyik irányban sincs olyan rákövetkezője, mely nála nagyobb lehetne. Így a levélelem triviálisan piramis -75- Már látszik, hogy logikai értékű rekurzív függvényt kell készíteni, ahol a rekurzív ágban megvizsgáljuk a gyökérelem és a kétoldalt rákövetkező elemek viszonyát, továbbá hivatkozunk a részfák piramis voltára mindezek eredményét és művelettel kapcsoljuk össze. A nemrekurzív ágon levélelem van, így azt kijelentjük piramisnak. A rekurzív ágat finomítani kell azzal, hogy nem biztosan van mindkét irányban részfa. 1. megoldás: A feladatot absztrakt bináris fa

műveletekkel oldjuk meg Mivel nem kell új fát létrehozni, hanem egy meglévőt kell feldolgozni, nem vizsgáljuk a memória elégségességét. Úgy tekintjük, hogy a bináris fa lehet beolvasó ill kiírató utasítás argumentuma valamint, hogy a fa legalább egyelemű. Típus ElemTípus = Valós Változó BinFa : BinFaTípus Piramis : Logikai Függvény Piramis-e?(vált F:BinFaTípus) : Logikai Változó Sv : Logikai Ha nem (Üres-e?(BalGyerek(F)) és Üres-e?(JobbGyerek(F))) akkor Ha nem Üres-e?(BalGyerek(F)) akkor Sv:=GyökérElem(F)>GyökérElem(BalGyerek(F)) és Piramis-e?(BalGyerek(F)) elág vége Ha nem Üres-e?(JobbGyerek(F)) akkor Sv:=GyökérElem(F)>GyökérElem(JobbGyerek(F)) és Piramis-e?(JobbGyerek(F)) elág vége Piramis-e?:=Sv különben Piramis-e?:=↑ elág vége Függvény vége Program: Be:BinFa Piramis:=Piramis-e?(BinFa) Ha Piramis akkor Ki:’A fa egy piramis.’ különben Ki:’A fa nem piramis’ Program vége -76- 2. Megoldás: A feladatot

statikusan láncolt ábrázolás mellett oldjuk meg Továbbra is feltételezzük a memória elégséges voltát és a bináris fa beolvashatóságát valamint, hogy a fa legalább egyelemű . Konstans MaxElem = Típus ElemTípus CímTípus BinFaElemTípus (Adat Bal,Jobb BinFaTípus (Gyökér Elemek = = = : : = : : Valós 0.MaxElem rekord ElemTípus CímTípus) rekord CímTípus Tömb(1.MaxElem : BinFaElemTípus) Változó BinFa : BinFaTípus Piramis : Logikai AktCím : CímTípus Megjegyzés: A bináris fa elemének típusába a korábbiaktól eltérően egyáltalán nem szokás logikai típusú mezőt integrálni a fakezelő műveletek alkalmazása során fellépő hibák típuson belüli detektálására. Ezt algoritmusban kell lekezelni Függvény Piramis-e?(vált F:BinFaTípus, Akt:CímTípus):Logikai Változó Sv : Logikai Ha nem (F.Elemek(Akt)Bal=0 és F.Elemek(Akt)Jobb=0) akkor Ha F.Elemek(Akt)Bal≠0 akkor Sv:=F.Elemek(Akt)Adat> F.Elemek(FElemek(Akt)Bal)Adat és

Piramis-e?(F,F.Elemek(Akt)Bal) elág vége Ha F.Elemek(Akt)Jobb≠0 akkor Sv:=F.Elemek(Akt)Adat> F.Elemek(FElelmek(Akt)Jobb)Adat és Piramis-e?(F,F.Elemek(Akt)Jobb) elág vége Piramis-e?:=Sv -77- különben Piramis-e?:=↑ elág vége függvény vége Program: Be:BinFa AktCím:=BinFa.Gyökér Piramis:=Piramis-e?(BinFa,AktCím) Ha Piramis akkor Ki:’A fa egy piramis.’ különben Ki:’A fa nem piramis’ Program vége 3. megoldás: A feladatot dinamikusan láncolt ábrázolás mellett oldjuk meg Továbbra is feltételezzük a memória elégséges voltát és a bináris fa beolvashatóságát valamint, hogy a fa legalább egyelemű. Típus ElemTípus BinFaCímTípus BinFaElemTípus (Adat Bal,Jobb BinFaTípus = = = : : = Valós ^BinFaElemTípus rekord ElemTípus BinFaCímTípus) BinFaCímTípus Változó BinFa : BinFaTípus Piramis : Logikai Függvény Piramis-e?(vált F:BinFaTípus):Logikai Változó Sv : logikai Ha nem (F^.Bal=NIL és F^Jobb=NIL) akkor Ha F^.Bal≠NIL

akkor Sv:=F^.Adat>F^Bal^Adat és Piramis-e?(F^Bal) elág vége Ha F^.Jobb≠NIL akkor Sv:=F^.Adat>F^Jobb^Adat és Piramis-e?(F^Jobb) elág vége Piramis-e?:=Sv különben Piramis-e?:=↑ elág vége függvény vége -78- Program: Be:BinFa Piramis:=Piramis-e?(BinFa) Ha Piramis akkor Ki:’A fa egy piramis.’ különben Ki:’A fa nem piramis’ Program vége 2.5512 Gyakorló feladatok 1. Készítsd el az alábbi bináris fa szintfolytonos és statikusan láncolt ábrázolását! A B C D E F G 2. Az alábbi szintfolytonos ábrázolásból rekonstruáld a bináris fát! A B C D # # E # F # # # # G # 3. Rekonstruáld az alábbi reprezentációból a bináris fát! Index Elem Bal Jobb 1 A 2 3 Gyökér SzabadFej 2 B 0 4 3 C 5 0 4 D 6 7 5 E 8 9 6 F 0 0 7 G 0 0 8 H 0 0 9 I 0 0 10 11 12 13 14 15 11 12 13 14 15 0 1 10 4. Egy bináris fa leveleiben számok vannak Add meg a számok minimumát! -79- 5. Furcsa fánknak megfeleltethető

egy bináris fa A bináris fa csomópontjai az ágelágazásoknak felelnek meg. Adott a fa törzsének hossza és keresztmetszete Minden elágazásnál az új ág hossza és keresztmetszete az előző p hányada. Mekkora a fa térfogata, az ágak és törzs összhossza? Add meg a legtávolabbi levélig vezető út csomópontjait és hosszát! 2.552Nem bináris fa 1. Adott egy fa, melynek minden éléhez és minden leveléhez értéket rendeltünk Add meg a gyökértől egy tetszőleges levélig vezető utat és az élek értékének összegét! 2. Egy nem bináris fát, melyben minden elemnek maximum K rákövetkezője van úgy ábrázolunk, hogy minden elemhez egy mutatóvektort rendelünk. Járd be úgy a fát, hogy először a gyökeret dolgozzuk fel aztán rákövetkezőit jobbról balra! 3. Egy nembináris fát úgy tárolunk, hogy minden elemhez megadjuk a baloldali első leszármazottját és jobboldali első rákövetkezőjét. Feleljenek meg a pontoknak emberek, a balodali

első leszármazottja a legidősebb gyermeke, jobboldali első rákövetkezője legidősebb kisebb testvére. a) b) c) d) Add meg a legfiatalabb olyan elsőszülöttet, akinek minden őse elsőszülött! Add meg egy tetszőleges ember gyerekeinek számát! Add meg a gyermektelenek számát! Add meg egy tetszőleges ember legkisebb gyermekét, feltéve, hogy van! Megjegyzés: A feladatok a reprezentáció szerint vagy bináris fákra vagy gráfokra vonatkozó eszközökkel oldhatók meg. -80- 2.56 Gráfok Megjegyzés: Kész gráffal kapcsolatos feladatok egy része gyakorlatialag azt kérdezi a megoldótól, hogy van-e két pont között adott tulajdonságú út. Ezek a feladatok az un szélességi bejárás stratégiájával megoldhatók. A feladatok másik része adott tulajdonságú utak megadását kéri. Ezek a feladatok az un. mélységi bejárás stratégiájával oldhatók meg Mivel ez utóbbi kicsit nehezebb, ilyen feladatot fogunk mintaként kidolgozni. Hogy az

algoritmusok egyszerűek legyenek, gráf alatt irányított, összefüggő, körmentes gráfot értünk a fejezetben. Ha nem garantálnánk a körmentességet, akkor vizsgálni kellene minden egyes pontnál továbblépés előtt, hogy korábban abból a pontból mely éle mentén léptünk már tovább. Ezek közül nem választhatnánk 2.561Mintafeladatok 1. feladat: :Adott egy gráf és annak A, B, X pontjai Keress A és B közötti olyan utat, mely áthalad X-en! Megjegyzés: Kiválogathatnánk az összes utat A-ból B-be, majd megvizsgálhatnánk, hogy van-e köztük olyan, amelyre illeszkedik az X pont. Kevesebbet kell dolgoznia a programozónak, ha keres utat A-ból X-be, majd X-ből B-be. Mivel utat kell keresni, a mélységi bejárás algoritmusát használjuk a megoldás kivitelezésére. A generátor pontot előbb A, majd X „játsza el”. A keresést abbahagyjuk, ha célhoz értünk, vagy lehetőségeinket kimerítettük. 1. megoldás: A feladatot csúcs-, avagy

szomszédsági mátrix segítségével oldjuk meg Feltételezzük, hogy a gráf lehet beolvasó utasítás argumentuma és a memória elég a gráf ábrázolásához. Konstans MaxPont = Típus Mátrix = Tömb(1.MaxPont,1MaxPont:Logikai) Sorozat = Tömb(1.MaxPont:1MaxPont) Változó N,A,B,X,DB1,DB2 CsúcsMátrix Pontok1,Pontok2 Van : : : : 1.MaxPont Mátrix Sorozat Logikai -81- Eljárás MélyBejár(P,Q,N CsúcsMátrix Vált Van Vált DB Vált Pontok : : : : : 1.MaxPont; Mátrix; Logikai; 1.MaxPont; Sorozat) Változó Pont,KövPont : 1.MaxPont KövPontok : Sorozat Megjegyzés: Az eredeti algoritmushoz képest nem az él prioritását jegyezzük itt fel, hanem a rákövetkezők közül választott csúcsot, különben mindig újra meg kellene keresni az él végén lévő csúcsot. Eljárás: Pont:=P KövPont:=1 Ciklus amíg KövPont≤N és nem CsúcsMátrix(P,KövPont) KövPont:=KövPont+1 Cv DB:=1 Pontok(DB):=Pont KövPontok(DB):=KövPont Ciklus amíg DB>0 és Pont≠Q

Ciklus amíg KövPont≤N és nem CsúcsMátrix(Pont,KövPont) KövPont:=KövPont+1 Cv Ha KövPont≤N akkor DB:=DB+1 Pontok(DB):=Pont KövPontok(DB):=KövPont Pont:=KövPont KövPont:=1 különben Pont:=Pontok(DB) KövPont:=KövPontok(DB) DB:=DB-1 KövPont:=KövPont+1 Elág vége Cv Van:=(Pont=Q) Eljárás vége -82- Program: Be:N,CsúcsMátrix(),A,B,X MélyBejár(A,X,N,CsúcsMátrix,Van,DB1,Pontok1) Ha Van akkor MélyBejár(X,B,N,CsúcsMátrix,Van,DB2,Pontok2) Ha Van akkor Ki:Pontok1(),Pontok2() különben Ki:’Nincs út X és B között.’ különben Ki:’Már A és X között sincs út.’ Program vége 2. megoldás: A feladatot Csúcslistával ábrázolt gráfra oldjuk meg Továbbra is feltételezzük a memória elégségességét és a gráf beolvashatóságát. Most az eredeti stratégia szerint az élek prioritását fogjuk tárolni, mert az él végén lévő csúcs közvetlenül kiolvasható a gráf reprezentációjából. Konstans MaxPont = MaxÉl = Megjegyzés:

Maxél≤Maxpont-1 Típus Mátrix = Tömb(1.MaxPont,1MaxÉl:1MaxPont) Sorozat = Tömb(1.MaxPont:1MaxPont) Változó N,A,B,X,DB1,DB2 CsúcsLista Pontok1,Pontok2 Van : : : : 1.MaxPont Mátrix Sorozat Logikai Eljárás MélyBejár(P,Q,N ÉlLista Vált Van Vált DB Vált Pontok : : : : : 1.MaxPont; Mátrix; Logikai; 1.MaxPont; Sorozat) Változó Pont : 1.MaxPont Él : 1.MaxÉl Élek : Tömb(1.MaxPont:1MaxÉl) -83- Eljárás: Pont:=p Él:=1 DB:=1 Pontok(DB):=Pont Élek(DB):=Él Ciklus amíg DB>0 és Pont≠Q Ha Él≤MaxÉl és CsúcsLista(Pont,Él)>0 akkor DB:=DB+1 Pontok(DB):=Pont Élek(DB):=Él Pont:=CsúcsLista(Pont,Él) Él:=1 különben Pont:=Pontok(DB) Él:=Élek(DB) DB:=DB-1 Él:=Él+1 Elág vége Cv Van:=(Pont=Q) Eljárás vége Program: Be:N,CsúcsLista(),A,B,X MélyBejár(A,X,N,CsúcsLista,Van,DB1,Pontok1) Ha Van akkor MélyBejár(X,B,N,CsúcsLista,Van,DB2,Pontok2) Ha Van akkor Ki:Pontok1(),Pontok2() különben Ki:’Nincs út X és B között.’ különben

Ki:’Már A és X között sincs út.’ Program vége 3. megoldás: A feladatot éllistás gráfábrázolás mellett oldjuk meg Továbbra is feltételezzük a memória elégségességét és a gráf beolvashatóságát. Az él prioritása helyett az éllistában, mint mátrixban elfoglalt sor indexét jegyezzük meg. Ha megjegyeznénk az aktuális pontból induló 1 prioritású él sorát az éllistában, akkor mintegy relatív indexként a prioritás használható. Ehelyett mi a kellő helyen a keresés programozási tétellel élünk. Konstans MaxPont = MaxÉl = Megjegyzés: Maxél≤Maxpont-1 -84- Típus Mátrix = Tömb(1.MaxPont*MaxÉl,1.2:1MaxPont) Sorozat = Tömb(1.MaxPont:1MaxPont) Változó N,A,B,X,DB1,DB2 ÉlLista Pontok1,Pontok2 Van : : : : 1.MaxPont Mátrix Sorozat Logikai Eljárás MélyBejár(P,Q,N ÉlLista Vált Van Vált DB Vált Pontok : : : : : 1.MaxPont; Mátrix; Logikai; 1.MaxPont; Sorozat) Változó Pont : 1.MaxPont ÉlInd : 1.MaxPont*MaxÉl Élek :

Tömb(1.MaxPont:1MaxPont*MaxÉl) Eljárás: Pont:=p ÉlInd:=1 Ciklus amíg ÉlInd≤N*(N-1) és ÉlLista(ÉlInd,1)>0 és ÉlLista(ÉlInd,1)≤Pont ÉlInd:=ÉlInd+1 Cv DB:=1 Pontok(DB):=Pont Élek(DB):=ÉlInd Ciklus amíg DB>0 és Pont≠Q Ciklus amíg ÉlInd≤N*(N-1) és ÉlLista(ÉlInd,1)>0 és ÉlLista(ÉlInd,1)≤Pont ÉlInd:=ÉlInd+1 Cv Ha ÉlInd≤N*(N-1) és ÉlLista(ÉlInd,1)=Pont akkor DB:=DB+1 Pontok(DB):=Pont Élek(DB):=ÉlInd Pont:=ÉlLista(ÉlInd,2) ÉlInd:=1 különben Pont:=Pontok(DB) ÉlInd:=Élek(DB) DB:=DB-1 ÉlInd:=ÉlInd+1 Elág vége Cv -85- Van:=(Pont=Q) Eljárás vége Program: Be:N,ÉlLista(),A,B,X MélyBejár(A,X,N,ÉlLista,Van,DB1,Pontok1) Ha Van akkor MélyBejár(X,B,N,ÉlLista,Van,DB2,Pontok2) Ha Van akkor Ki:Pontok1(),Pontok2() különben Ki:’Nincs út X és B között.’ különben Ki:’Már A és X között sincs út.’ Program vége 4. megoldás: Ábrázolás mutatókkal Ez a fajta ábrázolás kíméli egy kicsit az adatszegmenst, de

nem túl tömör. Minden egyes csúcs leíró rekordját a heap-ben helyezzük el. Szerepel benne a csúcs sorszáma, a belőle ténylegesen induló élek száma, valamint prioritási rendben tömbbe gyűjtve a rákövetkező csúcsokra mutató pointerek. Ezek általános pointerek A gráf az egyes csúcsok leíró rekordjaira mutató típusos mutatók tömbje. Azért nem egyetlen generátorponttal írjuk le a gráfot, hogy tetszőleges csúcs lehessen generátorpont. Továbbra is feltételezzük a memória elégségességét és a gráf beolvashatóságát. Él helyett a választott következő pontot tároljuk Konstans MaxPont = MaxÉl = Megjegyzés: Maxél≤Maxpont-1 Típus GráfElemMut GráfElemTípus (Csúcs AktÉlSzám Köv GráfTípus Sorozat = = : : : = = Változó N,A,B,X,DB1,DB2 Gráf Pontok1,Pontok2 Van ^GráfElemTípus rekord 1.MaxPont 1. MaxÉl Tömb(1.MaxÉl:Mutató)) Tömb(1.MaxPont:GráfElemMut) Tömb(1.MaxPont:1MaxPont) : : : : 1.MaxPont GráfTípus Sorozat

Logikai -86- Eljárás MélyBejár(P,Q,N Gráf Vált Van Vált DB Vált Pontok : : : : : 1.MaxPont; GráfTípus; Logikai; 1.MaxPont; Sorozat) Változó Pont,Él : 1.MaxPont Élek : Sorozat KövPont : GráfElemMut Eljárás: Pont:=P Él:=1 DB:=1 Pontok(DB):=Pont Élek(DB):=Él Ciklus amíg DB>0 és Pont≠Q Ha Él≤Gráf(Pont)^.AktÉlSzám akkor KövPont:=Gráf(Pont)^.Köv(Él) DB:=DB+1 Pontok(DB):=Pont Élek(DB):=Él Pont:=KövPont^.Csúcs Él:=1 különben Pont:=Pontok(DB) Él:=Élek(DB) DB:=DB-1 Él:=Él+1 Elág vége Cv Van:=(Pont=Q) Eljárás vége Program: Be:N,Gráf,A,B,X MélyBejár(A,X,N,Gráf,Van,DB1,Pontok1) Ha Van akkor MélyBejár(X,B,N,Gráf,Van,DB2,Pontok2) Ha Van akkor Ki:Pontok1(),Pontok2() különben Ki:’Nincs út X és B között.’ különben Ki:’Már A és X között sincs út.’ Program vége -87- Megjegyzés: Lehet a Pontok tömbben 1.MaxPont típusú adatok helyett GráfElemMut típusú adatokat tárolni. Ekkor a GráfElemTípus és a

GráfTípus típusokban is ez a típusos mutató szerepel. Ilyen reprezentáció mellett a MélyBejár eljárás sokkal egyszerűbb lesz. Íme: 5. megoldás: Konstans MaxPont = MaxÉl = Megjegyzés: Maxél≤Maxpont-1 Típus GráfElemMut GráfElemTípus (Csúcs AktÉlSzám Köv GráfTípus Sorozat = = : : : = = Változó N,A,B,X,DB1,DB2 Gráf Pontok1,Pontok2 Van ^GráfElemTípus rekord 1.MaxPont 1. MaxÉl Tömb(1.MaxÉl:GráfElemMut)) Tömb(1.MaxPont:GráfElemMut) Tömb(1.MaxPont:GráfElemMut) : : : : 1.MaxPont GráfTípus Sorozat Logikai Eljárás MélyBejár(P,Q,N Gráf Vált Van Vált DB Vált Pontok : : : : : 1.MaxPont; GráfTípus; Logikai; 1.MaxPont; Sorozat) Változó Pont : GráfElemMut Él : 1.MaxÉl Élek : Tömb(1.MaxPont:1MaxÉl) Eljárás: Pont:=Gráf(P) Él:=1 DB:=1 Pontok(DB):=Pont Élek(DB):=Él -88- Ciklus amíg DB>0 és Pont^.Csúcs≠Q Ha Él≤Pont^.AktÉlSzám akkor DB:=DB+1 Pontok(DB):=Pont Élek(DB):=Él Pont:=Pont^.Köv(Él) Él:=1 különben

Pont:=Pontok(DB) Él:=Élek(DB) DB:=DB-1 Él:=Él+1 Elág vége Cv Van:=(Pont^.Csúcs=Q) Eljárás vége Program: Be:N,Gráf,A,B,X MélyBejár(A,X,N,Gráf,Van,DB1,Pontok1) Ha Van akkor MélyBejár(X,B,N,Gráf,Van,DB2,Pontok2) Ha Van akkor Ki:Pontok1()^.Csúcs,Pontok2()^Csúcs különben Ki:’Nincs út X és B között.’ különben Ki:’Már A és X között sincs út.’ Program vége 6. megoldás: A feladatot végül az un listák listája reprezentáció mellett oldjuk meg Szinte minden eszközt a heap-ben helyezünk el. A csúcsokat olyan rekord írja le, mely tartalmazza a csúcs sorszámát és egy mutatót, mely nem a csúcs típusára mutat, hanem egy más típusra, mely az első rákövetkezőre utal. Ez a másik rekord típus mutat az előbb említett rákövetkező csúcsra ill. mutat az eredeti csúcs következő ilyen módon rákövetkezőjére. Ezzel az élek szerepét is típusos mutatók veszik át Így a deklarációkhoz nem kell tudni a csúcsokból indítható

élek maximális számát. Konstans MaxPont = Típus KövetőMut GráfElemMut KövetőTípus (GráfElem Követő = = = : : ^KövetőTípus ^GráfElemTípus rekord GráfElemMut KövetőMut)) -89- GráfElemTípus (Csúcs Követő GráfTípus Sorozat = : : = = Változó N,A,B,X,DB1,DB2 Gráf Pontok1,Pontok2 Van rekord 1.MaxPont KövetőMut) Tömb(1.MaxPont:GráfElemMut Tömb(1.MaxPont:GráfElemMut) : : : : 1.MaxPont GráfTípus Sorozat Logikai Eljárás MélyBejár(P,Q,N Gráf Vált Van Vált DB Vált Pontok : : : : : 1.MaxPont; GráfTípus; Logikai; 1.MaxPont; Sorozat) Változó Pont : GráfElemMut Él : KövetőMut Élek : Tömb(1.MaxPont:1MaxÉl) Eljárás: Pont:=Gráf(P) Él:=Pont^.Követő DB:=1 Pontok(DB):=Pont Élek(DB):=Él Ciklus amíg DB>0 és Pont^.Csúcs≠Q Ha Él≤NIL akkor DB:=DB+1 Pontok(DB):=Pont Élek(DB):=Él Pont:=Él^.GráfElem Él:=Pont^.Követő különben Pont:=Pontok(DB) Él:=Élek(DB) DB:=DB-1 Él:=Él^.Követő Elág vége Cv

Van:=(Pont^.Csúcs=Q) Eljárás vége -90- Program: Be:N,Gráf,A,B,X MélyBejár(A,X,N,Gráf,Van,DB1,Pontok1) Ha Van akkor MélyBejár(X,B,N,Gráf,Van,DB2,Pontok2) Ha Van akkor Ki:Pontok1()^.Csúcs,Pontok2()^Csúcs különben Ki:’Nincs út X és B között.’ különben Ki:’Már A és X között sincs út.’ Program vége 2.562Gyakorló feladatok 1. Adott egy N csúcsú irányított körmentes gráf és annak egy pontja Add meg a csúcsból induló összes utat! 2. Határozd meg egy gráf két pontja közötti különböző utak számát! 3. Ismerjük Magyarország városait összekötő úthálózatot, az egyes településeket összekötő utak hosszát is. Add meg az összes várospárra, hogy hány km autóútra vannak egymástól! 4. Az előbbi feladatban adott úthálózatban keress olyan kört, mely minden várost egyszer és csak egyszer érint! Kezd a kör összeállítását Budapesttel! 5. N város közötti telefonhálózatot csúcsmátrixszal ábrázolunk

Döntsd el, hogy két adott város között létesíthető-e telefonkapcsolat! 6. Egy város úthálózatát irányított gráffal ábrázoljuk Az egyirányú utca két végét jelentő pont között egy él van, kétirányú utca esetén két ellentétes irányú él. a) Döntsd el, hogy A pontból el lehet-e jutni B pontba! b) Adj meg egy utat, melyen A-ból B-be lehet jutni! c) Adj meg egy zsákutcát! -91- Irodalomjegyzék Pap Gáborné-Szlávi Péter-zsakó László: Módszeres programozás: adattípusok µlógia 34, Budapest, 1998 Szlávi Péter: Előadás a sorozattípusokról Szilánkok 7, Budapest, 1992-1995 Szlávi Péter: Előadás a gráftípusról Szilánkok 5, Budapest, 1992-1997 Számítástechnikai feladatok 2000-ig I. Szerkesztette: Dr. Hetényi Pálné, OMIKK Budapest, 1988 -92-