Programozás | Programozás-elmélet » Kovács László - Programozás-elmélet, 2002

Programozás-elmélet Oktatási segédlet Összeállította: Kovács László Programozás-elmélet  K.L 2 Tartalomjegyzék A számítógépes feladatmegoldás lépései.3 A feladat meghatározása.3 Adatszerkezetek .4 Algoritmuskészítés .6 Programozási tételek .7 Rekurzió .18 Fájlkezelés.21 Programozási nyelvek osztályozása .23 Programkészítési elvek.25 Programhelyességvizsgálat.26 Hibakeresés és -javítás .27 Hatékonyságvizsgálat.28 Dokumentálás.30 Összetett adatszerkezetek megvalósítása.31 Statikus verem és műveletei .32 Dinamikus verem és műveletei.33 Statikus sor és műveletei .34 Dinamikus sor és műveletei.35 Statikus lista és műveletei.36 Dinamikus lista és műveletei .39 Statikus bináris fa .42 Dinamikus bináris fa.42 Gráf .47 Objektumorientált programozás .48 Programozás-elmélet  K.L 3 Programozás A számítógépes feladatmegoldás lépései 1. A feladat meghatározása 2. Algoritmuskészítés 3. Kódolás:

programkészítés (a szg számára érthető algoritmus írása, fordítása) 4. Tesztelés, hibakeresés, javítás 5. Hatékonyságvizsgálat 6. Dokumentálás A feladat meghatározása Elemei: 1. Bemenet -kiindulási adatok (megnevezés, típusmeghatározás) -bemenő paraméterek -felhasználható függvények, eljárások 2. Kimenet -előállítandó adatok (megnevezés, típusmeghatározás) 3. Előfeltétel -az algoritmus elkészítése során figyelembe vehető illetve veendő kiindulási körülmények -a bemenetekre vonatkozó előírások illetve megkötések 4. Utófeltétel -az algoritmussal szemben támasztott követelmények -a lefutás után a kimenetek értékére vonatkozó meghatározások, elvárások Programozás-elmélet  K.L 4 Adatszerkezetek I., Elemi típusok 1. Megszámlálható típusosztály: a., egészek: Ábrázolás: shortint integer longint byte word 1B 2B 4B 1B 2B előjeles előjeles előjeles előjel nélküli előjel nélküli kettes

komplemens kódban b., karakteres: char 1B Ábrázolás: ASCII kódtábla alapján: 0 . 31 vezérlő karakterek 32 . 127 alapkarakterek 128 . 255 kiegészítő karakterek Műveletei: chr(65), ord(A). c., logikai: Műveletei: boolean / logical 1B {false.true} NOT, AND, OR, XOR, EQU, NAND, NOR, implikáció Hasonlító operátorok: 2. Valós típusosztály: -128.+127 -32768.+32767 ± 2 milliárd 0.255 0.65535 real single double extended comp =, >, <, <>, >=, <=, IN. 5+1 B 3+1 B 6+2 B 7+3 B Ábrázolás: lebegőpontos számként: mantissza+karakterisztika Műveletei: minden matematikai művelet és függvény - pascalban nincs hatványozás, de ab = exp(b*ln(a)) Programozás-elmélet  K.L 5 II., Összetett típusok 1. Karaktersorozat: string Műveletei: s = Szövegkonstans Hossz (s) = n RészSztring (s,n,n) = sz Pozíció (s1,s2) = n Konkateráció(s1,s2) = s12 2. Tömb: array (azonos típusú elemek; hivatkozás sorszámmal) 3. Rekord:

record (különböző típusú elemek; hivatkozás mezőnévvel) III. Definiált típusok 1. Táblázat: rekordok tömbje tipus táblázat = tömbje[1.100] Rekord-nak mez ő1: tipus1 mez ő2: tipus2 mez ő3: tipus3 Rekord vége 2. Részintervallum: valamilyen megszámlálható típus résztartománya 3. Halmaz: elemek csoportja, ahol - nincsenek azonos elemek - elemek sorrendje nem értelmezhető 4. Felsorolás 5. Verem: Last In First Out (LIFO) 6. Sor: First In First Out (FIFO) 7. Lista 8. Gráf 9. Fa: körmentes gráf IV. Mutató típus: pointer V. Konstansok: const 1. Definiált konstans 2. Tipizált konstans Programozás-elmélet  K.L 6 Algoritmuskészítés Algoritmus: utasítássorozat, mely megadja egy feladat megoldásmenetének pontos leírását - véges sok utasítást tartalmaz - nem feltétlenül véges végrehajtási idejű - megfelelő sorrendű (szemantikailag helyes) - utasításonként megfelelően paraméterezett (szintaktikailag helyes) Strukturált

algoritmus elemei: a., szekvencia (soros algoritmus, blokk) b., szelekció (elágazás) - feltételes - többirányú c., iteráció (ciklus, ismétlés) - elöltesztelő - hátultesztelő - számláló d., procedura (eljárás, szubrutin) e., függvény Ugró utasítások nem elemei a strukturált algoritmusnak! Programozás alaptétele: minden algoritmus megvalósítható strukturáltan. (Böhm-Jacopini - tétel) Algoritmusleíró eszközök Rajzos: látványos, de nehezen szerkeszthető 1., folyamatábra (blokkdiagram) 2., struktogram 3., Jackson-ábra Szöveges: nem annyira látványos, de könnyen szerkeszthető 1., mondatokkal történő leírás nem egyértelmű, nem specifikus 2., programnyelven történő leírás nem mindenki számára érthető 3., mondatszerű leírás (pszeudokód, leírónyelv) előnyök ötvözése: anyanyelvű, specifikus Programozás-elmélet  K.L 7 Programozási tételek 1., Sorozatszámítás Be: X(N) f F0 - X nevű, N elemű tömb

függvény kezdőérték Ki: Y - érték Ef: -- Uf: Y=f(F0,X) Eljárás Sorozatszámítás Y:=F0 Ciklus i:=1-től N-ig Y:=f(Y,X(i)) Ciklus vége Eljárás vége 2., Megszámlálás Be: X(N) T - X nevű, N elemű tömb tulajdonság Ki: DB ∈ N - darabszám Ef: -- Uf: DB : 0<=DB<=N, X-beli T tulajdonságú elemek száma Eljárás Megszámlálás DB:=0 Ciklus i:=1-től N-ig Ha T(X(i)), akkor DB:=DB+1 Ciklus vége Eljárás vége Programozás-elmélet  K.L 8 3., Maximumkiválasztás Be: X(N) - X nevű, N elemű tömb Ki: MAX ∈ N - sorszám Ef: -- Uf: MAX : 1<=MAX<=N, X(MAX)>=X(i) minden 1<=i<=N esetén Eljárás Maximumkiválasztás MAX:=1 Ciklus i:=2-től N-ig Ha X(i)>X(MAX), akkor MAX:=i Ciklus vége Eljárás vége 4., Eldöntés Be: X(N) T - X nevű, N elemű tömb tulajdonság Ki: VAN ∈ L - logikai érték Ef: -- Uf: VAN=igaz, ha létezik olyan 1<=i<=N, melyre T(X(i)), VAN=hamis

egyébként. Eljárás Eldöntés i:=1 Ciklus amíg i<=N és nem T(X(i)) i:=i+1 Ciklus vége VAN:=(i<=N) Eljárás vége Programozás-elmélet  K.L 9 5., Keresés Be: X(N) T - X nevű, N elemű tömb tulajdonság Ki: VAN ∈ L Ha VAN, akkor S ∈ N - logikai változó sorszám Ef: -- Uf: VAN=igaz, ha létezik olyan 1<=i<=N, melyre T(X(i)), VAN=hamis egyébként. Ha VAN, akkor S : 1<=S<=N és T(X(S)) Eljárás Keresés i:=1 Ciklus amíg i<=N és nem T(X(i)) i:=i+1 Ciklus vége VAN:=(i<=N) Ha VAN, akkor S:=i Eljárás vége 6., Kiválasztás Be: X(N) T - X nevű, N elemű tömb tulajdonság Ki: S ∈ N - sorszám Ef: Létezik olyan 1<=i<=N, melyre T(X(i)) Uf: S : 1<=S<=N és T(X(S)) Eljárás Kiválasztás i:=1 Ciklus amíg nem T(X(i)) i:=i+1 Ciklus vége S:=i Eljárás vége Programozás-elmélet  K.L 10 7., Másolás Be: X(N) f - X nevű, N elemű tömb függvény Ki: Y(N) - Y nevű, N elemű

tömb Ef: -- Uf: Y(N) : Y(i)=f(X(i)) minden 1<=i<=N esetén Eljárás Másolás Ciklus i:=1-től N-ig Y(i):=f(X(i)) Ciklus vége Eljárás vége 8., Kiválogatás Be: X(N) T - X nevű, N elemű tömb tulajdonság Ki: DB ∈ N Y(DB): - darabszám Y nevű, DB elemű tömb Ef: -- Uf: DB : Y(DB): 0<=DB<=N, X-beli T tulajdonságú elemek száma minden 1<=i<=DB esetén T(X(Y(i))) Eljárás Kiválogatás DB:=0 Ciklus i:=1-től N-ig Ha T(X(i)), akkor DB:=DB+1 : Y(DB):=X(i) Ciklus vége Eljárás vége Programozás-elmélet  K.L 9., Szétválogatás a., Szétválogatás két tömbbe Be: X(N) T - X nevű, N elemű tömb tulajdonság Ki: DB ∈ N Y(DB) Z(N-DB): - darabszám Y nevű, DB elemű tömb Z nevű, DB elemű tömb Ef: -- Uf: DB : Y(DB) : Z(N-DB) : 0<=DB<=N, X-beli T tulajdonságú elemek száma minden 1<=i<=DB esetén T(Y(i)) minden 1<=i<=N-DB esetén nemT(Z(i)) Eljárás Szétválogatás két tömbbe DB:=0

: DBZ:=0 Ciklus i:=1-től N-ig Ha T(X(i)), akkor DB :=DB +1 : Y(DB) :=X(i) különben DBZ:=DBZ+1 : Z(DBZ):=X(i) Ciklus vége Eljárás vége b., Szétválogatás egy tömbbe Be: X(N) T - X nevű, N elemű tömb tulajdonság Ki: DB ∈ N Y(N) - darabszám Y nevű, N elemű tömb Ef: -- Uf: DB : Y(N) : 0<=DB<=N, X-beli T tulajdonságú elemek száma minden 1<=i<=DB esetén T(Y(i)) és minden DB+1<=i<=N esetén nemT(Y(i)) Eljárás Szétválogatás egy tömbbe DB:=0 : DBZ:=0 Ciklus i:=1-től N-ig Ha T(X(i)), akkor DB :=DB +1 : Y(DB):=X(i) különben DBZ:=DBZ+1 : Y(N+1-DBZ):=X(i) Ciklus vége Eljárás vége 11 Programozás-elmélet  K.L 12 c., Szétválogatás helyben Be: X(N) T - X nevű, N elemű tömb tulajdonság Ki: DB ∈ N X(N) - darabszám Y nevű, N elemű tömb Ef: -- Uf: DB : X(N) : 0<=DB<=N, X-beli T tulajdonságú elemek száma minden 1<=i<=DB esetén T(X(i)) és minden DB+1<=i<=N esetén nemT(X(i))

Eljárás Szétválogatás helyben Y:=X(1) : E:=1 : U:=N Ciklus amíg E<U Ciklus amíg E<U és nem T(X(U)) U:=U-1 Ciklus vége Ha E<U, akkor X(E):= X(U) : E:=E+1 Ciklus amíg E<U és T(X(E)) E:=E+1 Ciklus vége Ha E<U akkor X(U):=X(E) : U:=U-1 Feltétel vége Ciklus vége X(E):=Y Ha T(Y) akkor DB:=E különben DB:=E-1 Eljárás vége Programozás-elmélet  K.L 10., Metszet Be: X(N) Y(M) - X nevű, N elemű tömb Y nevű, M elemű tömb Ki: DB Î N Z(DB) - darabszám Z nevű, DB elemű tömb Ef: X és Y Uf: DB : Z(DB) : halmazok 0<=DB<=min(N,M), X´Y halmaz elemeinek száma minden 1<=i<=DB esetén Z(i)ÎX és Z(i)ÎY Eljárás Metszet DB:=0 Ciklus i:=1-től N-ig j:=1 Ciklus amíg j<=N és X(i)<>Y(j) j:=j+1 Ciklus vége Ha j<=M akkor DB:=DB+1 : Z(DB):=X(i) Ciklus vége Eljárás vége 11., Unió Be: X(N) Y(M) - X nevű, N elemű tömb Y nevű, M elemű tömb Ki: DB ∈ N Z(DB) - darabszám - Z nevű, DB elemű tömb

Ef: X és Y Uf: DB : Z(DB) : halmazok 0<=DB<=N+M, XUY halmaz elemeinek száma minden 1<=i<=DB esetén Z(i)∈X vagy Z(i)∈Y Eljárás Unió Z:=X : DB:=N Ciklus i:=1-től M-ig j:=1 Ciklus amíg j<=N és X(j)<>Y(i) j:=j+1 Ciklus vége Ha j>M akkor DB:=DB+1 : Z(DB):=Y(i) Ciklus vége Eljárás vége 13 Programozás-elmélet  K.L 14 12., Összefuttatás, összefésülés Be: X(N) Y(M) - X nevű, N elemű tömb Y nevű, M elemű tömb Ki: Z(K) - Z nevű, K elemű tömb Ef: X és Y elemei rendezettek Uf: Z(K) : minden 1<=i<=K esetén Z(i)∈X vagy Z(i)∈Y (K a XUY halmaz elemeinek száma) Eljárás Összefuttatás i:=1 : j:=1 : k:=0 Ciklus amíg i<=N és j<=M k:=k+1 Elágazás X(i)<Y(j) esetén: Z(k):=X(i) : i:=i+1 X(i)=Y(j) esetén: Z(k):=X(i) : i:=i+1 : j:=j+1 X(i)>Y(j) esetén: Z(k):=Y(j) : j:=j+1 Elágazás vége Ciklus vége Cilkus amíg i<=N k:=k+1 : Z(k):=X(i) : i:=i+1 Ciklus vége Cilkus amíg j<=M k:=k+1

: Z(k):=Y(j) : j:=j+1 Ciklus vége Eljárás vége Eljárás Összefésülés i:=1 : j:=1 : k:=0 : X(N+1):=+∞ : Y(M+1):=+∞ Ciklus amíg i<N+1 vagy j<M+1 k:=k+1 Ha X(i)<=Y(j), akkor Z(k):=X(i) : i:=i+1 különben Z(k):=Y(j) : j:=j+1 Ciklus vége Eljárás vége Programozás-elmélet  K.L 13., Rendezés Be: X(N) - X nevű, N elemű tömb Ki: X(N) - X nevű, N elemű tömb Ef: -- Ki: X(N) : elemek sorrendje érték szerint növekvő (rendezett) a., Eljárás Egyszerű cserés rendezés Ciklus i:=1-től N-1-ig Ciklus j:=i+1-től N-ig Ha X(j)<X(i), akkor s:=X(i) : X(i):=X(j) : X(j):=s Ciklus vége Ciklus vége Eljárás vége b., Eljárás Buborékelvű rendezés Ciklus i:=N-1-től 1-ig -1-esével Ciklus j:=1-től i-ig Ha X(j)>X(j+1), akkor s:=X(j) : X(j):=X(i) : X(i):=s Ciklus vége Ciklus vége Eljárás vége c., Eljárás Minimumkiválasztásos rendezés Ciklus i:=1-től N-ig MIN:=i Ciklus j:=i+1-től N-ig Ha X(j)<X(MIN), akkor MIN:=j Ciklus

vége s:=X(MIN) : X(MIN):=X(i) : X(i):=s Ciklus vége Eljárás vége d., Eljárás Beillesztéses rendezés Ciklus i:=1-től N-1-ig Y:=X(i+1) j:=i Ciklus amíg j>0 és X(j)>Y X(j+1):=X(j) j:=j-1 Ciklus vége X(j+1):=Y Ciklus vége Eljárás vége 15 Programozás-elmélet  K.L 16 14., Logaritmikus keresés Be: X(N) Y - X nevű, N elemű tömb érték Ki: VAN ∈ L Ha VAN, akkor S ∈ N - logikai változó sorszám Ef: X elemeinek sorrendje érték szeint növekvő (rendezett) Uf: VAN=igaz, ha létezik olyan 1<=i<=N, melyre Y=X(i), VAN=hamis egyébként. Ha VAN, akkor S : 1<=S<=N és Y=X(S) Eljárás Logaritmikus keresés E:=1 : U:=N Ciklus k:=[(E+U)/2] Elágazás X(k)<Y esetén: E:=k+1 X(k)>Y esetén: U:=k-1 Elágazás vége Mígnem E>U vagy X(k)=Y Ciklus vége VAN:=(E<=U) Ha VAN, akkor S:=k Eljárás vége Programozás-elmélet  K.L 17 15., Visszalépéses keresés (BackTrack) Be: N db sorozat T - Ki: VAN ∈ L Ha VAN,

akkor M(1), M(2), . M(N) elemszámmal tulajdonság S(N) ∈ N - logikai változó sorszámokat tartalmazó sorozat Ef: - Uf: VAN=igaz, ha létezik olyan S(N) sorozat, melyre T(S(N)) VAN=hamis egyébként. Ha VAN, akkor S(N) : az egyes sorozatok megfelelő elemei sorszámának tömbje Eljárás Visszalépéses keresés i:=1 : S(1):=0 Ciklus amig i>=1 és i<=N Ha VanJóElem(i) akkor i:=i+1: S(i):=0 kül. i:=i-1 Ciklus vége VAN:=(i>N) Eljárás vége Függvény VanJóElem(i:szám):logikai Ciklus S(i):=S(i)+1 Mignem s(i)>M(i) vagy ElemRendben(i,S(i)) Ciklus vége VanJóElem:=(S(i)<=M(i)) Függvény vége Függvény ElemRendben(i,S(i)):logikai j:=1 Ciklus amig j<i és T(i,S(i),j,S(j)) j:=j+1 Ciklus vége ElemOK:=(j=i) Függvény vége másként: (i,S(i)) nem zája ki (j,S(j))-t pl: Sakktábla királynői esetén S(i)<>S(j) és |i-j|<>|S(i)-S(j)| Programozás-elmélet  K.L 18 Rekurzió Matematikai művelet: Fakt(n)= RS T 1 n ⋅ Fakt(n −

1) ha n ≤ 1 ha n > 1 Algoritmusban: - specifikáció önmagára visszautal - eljárás saját magát is meghívhatja Programozási nyelvben: - rekurziv a nyelv, ha megengedi a változók sokszorozódását - rekurziv: Pascal, Logo - nem rekurziv: Basic Példák: 1., Faktoriális számítása Függvény Fakt(N) Ha N<=1 akkor Fakt:=1 kül. Fakt:=N*Fakt(N-1) Függvény vége Végrehajtás: Fakt(3) Ha 3≤1 kül. Fakt:=3*Fakt(3-1) Fakt(2) Ha 2≤1 kül. Fakt:=2*Fakt(2-1) Fakt(1) Ha 1≤2 akkor Fakt:=1 Függvény vége Függvény vége Függvény vége Programozás-elmélet  K.L 19 2., Fibonacci sorozat Fib(n)= RS T 1 Fib(n-1)+Fib(n-2) ha ha n = 0 vagy n =1 n >1 Függvény Fib(N) Ha N<=1 akkor Fib:=1 kül. Fib:=Fib(N-1)*Fakt(N-2) Függvény vége 3., Rendezés: QuickSort Eljárás QuickSort(E,U) SzétválogatásHelyben(E,U, vált K) Ha K-E>1 akkor QuickSort(E,K-1) Ha U-K>1 akkor QuickSort(K+1,U) Eljárás vége 4., Grafika: Területfestés Eljárás

Festés(X,Y) PontRajz(X,Y) Ha nem Festett(X-1,Y) Ha nem Festett(X,Y-1) Ha nem Festett(X+1,Y) Ha nem Festett(X,Y+1) Eljárás vége akkor akkor akkor akkor Festés(X-1,Y) Festés(X,Y-1) Festés(X+1,Y) Festés(X,Y+1) 5., Játék: Hanoi tornyai Eljárás Hanoi(N, vált A, vált B, vált C) Ha N=1 akkor AB kül. Hanoi(N-1,A,C,B) AB Hanoi(N-1,C,B,A) Elágazás vége Eljárás vége Programozás-elmélet  K.L 20 6., Rajz: Fraktálok fraktál:minden olyan görbe vagy felszín, amely a felbontástól függetlenül többékevésbé ugyanúgy néz ki - önhasonlóság: a görbe bármely részét felnagyítva az eredetivel azonos görbét kapunk a., Fa b., Koch-görbe Eljárás Koch irány:=0 Pozició1(0,0) KochRajz(4,270) Eljárás vége Eljárás KochRajz(szint, hossz: egész) Ha szint=0 akkor x:=aktX2+hossz*cos(irány) y:=aktY + hossz*sin(irány) VonalPonthoz3(x,y) különben KochRajz(szint-1,hossz/3) irány:=irány+60 KochRajz(szint-1,hossz/3) irány:=irány-120

KochRajz(szint-1,hossz/3) irány:=irány+60 KochRajz(szint-1,hossz/3) Elágazás vége Eljárás vége c., Sierpinski-csipke d., Cantor-halmaz 1 Pascalban: MoveTo Pascalban: GetX, GetY 3 Pascalban: LineTo 2 Programozás-elmélet  K.L 21 Fájlkezelés Fájltípusok: a., Szekvenciális: -soros hozzáférés -pl.: szöveges fájl b., Direkt -közvetlen hozzáférés -pl.: típusos és típus nélküli fájlok Használat: 1. Logikai fájlváltozó deklarálása text file of . file -szöveges fájl -típusos fájl -típus nélküli fájl 2. Hozzárendelés(fájlváltozó,fájlnév) assign 3. Megnyitás(fájlváltozó) 4. Fájlműveletek close 5. Bezárás(fájlváltozó) Fájl megnyitása: -létrehozással -csak olvasásra -hozzáfűzésre -módosításra rewrite reset append reset Fájlműveletek: -sor olvasása -sor írása -adat olvasása -adat írása -blokk olvasása -blokk írása -sorvége? -fájlvége? -hibakód? -fájlméret? -fájlpozíció?

-pozícionálás -fájlcsonkítás szöveges típusos típus nélküli ü ü ü ü ü ü ü típusos típus nélküli szöveges readln writeln read write blockread blockwrite seekeol,eoln seekeof eof ioresult filesize filepos seek truncate ü ü ü ü ü ü ü ü ü ü ü ü ü ü ü ü ü ü ü ü ü ü Programozás-elmélet  K.L 22 Rendezés: Probléma: a fájl nagyobb, mint amekkora adatmennyiség befér a memóriába. Megoldás: négysegédfájlos rendezés összefuttatással. FUTAM: az az adatmennyiség, ami még befér a memóriába. Eredeti fájl: 1. segédfájl: 2. segédfájl: 1. futam 1. futam rendezve 2. futam rendezve 2. futam 3. futam rendezve 4. futam rendezve 3. futam 5. futam rendezve 6. futam rendezve 4. futam ⇒ 5. futam 7. futam rendezve 8. futam rendezve 9. futam rendezve 10. futam rendezve 6. futam Ezek után futamok összefuttatása: 3. segédfájl: 4. segédfájl: 1-2. futam rendezve 3-4. futam

rendezve 5-6. futam rendezve 7-8. futam rendezve 9-10. futam rendezve 1. segédfájl: 1-4. futam rendezve 9-12. futam rendezve Végül előáll a rendezett fájl. 2. segédfájl: 5-8. futam rendezve Programozás-elmélet  K.L Programozási nyelvek osztályozása I. Felhasználó szerinti csoportosítás a., amatőr nyelv - párbeszédesség - gyors fejlődés - sok nyelvi elem - egyszerű programszerkezet - gépfüggőség b., professzionális nyelv - modularitás - stabilitás - kevés nyelvi elem - összetett programszerkezet - gépfüggetlenség II. Emberközeliség szerinti csoportosítás a., gépi nyelv b., alacsonyszintű c., magasszintű III. Számítási modell (működés) szerinti csoportosítás a., Neumann-elvű nyelvek - címezhető memória - adatok kezelése: változók, értékadás, beolvasás, kiírás - program: strukturált felépítés b., automata-elvű nyelvek (pl Logo) - állapotváltoztató működés - állapotátmenet-függvény -

állapotváltoztató és -lekérdező utasítások - fix felosztású memória - nincsenek változók - bemenet: kiindulási állapot + paraméterezés - kimenet: állapotváltozás eredménye (kimeneti állapot) - párhuzamosság - elágazás, ciklus + rekurzió c., logikai nyelvek (pl Prolog - Programming in logic) - program: paraméterezhető logikai formula, logikai függvény - f(x,y,z) ⇒ {igaz, hamis} - f(?,?,3) ⇒ megadja, mi lehet a ? helyén, hogy igaz legyen d., funkcionális (függvényszerű) nyelvek - program: paraméterezhető függvény - nincs: memória, változó, értékadás - van: paraméter, függvényérték, függvénykompozíció - f(g(x)) - ciklus helyett rekurzió 23 Programozás-elmélet  K.L 24 IV. Alkalmazás szerinti csoportosítás a., számítások - sok számtípus, num. műveletek, jól kidolgozott tömbhasználat - csekély rekord- és fájlkezelés b., adatfeldolgozás (dBase) - adatstrukturálás széles lehetősége - formátumozás

képernyőn, nyomtatón c., rendszerprogramozás (C) - hardverkihasználás - operációs rendszerrel kommunikálás d., szövegfeldolgozás - sztringkezelés, fájlkezelés e., folyamatvezérlés - párhuzamos működés - portkezelés f., szimuláció - gyors - grafikus g., oktatás (Basic, Pascal, Elan) - jól stukturált, erősen típusos - szintaktikai ellenőrzés beíráskor h., általános célú nyelvek Programnyelv-generációk 1GL: - elemi adattípusok - beolvasás, kiírás, műveletek 50s 2GL: - kifejezések, szintaxis - zárójelezés - összetett típusok - fájlkezelés 60s 3GL: - stukturált programozás - programozási tételek 70s 4GL: - moduláris programozás - objektumorientált programozás - programkódgenerátor 80s 5GL: - párhuzamosság 90s Programozás-elmélet  K.L 25 Programkészítési elvek I. Stratégiai elvek 1. frontális: "nekiesünk", és egyszerre mindent fejlesztünk (kerülendő) 2. felülről lefelé: részekre

bontással 3. alulról felfelé: nyelvi elemek prog tételek rutinok modulok II. Taktikai elvek (a részletekre vonatkozólag) 1. párhuzamos finomítás 2. döntések elhalasztása (hátha később egyértelműsödik) 3. döntések nyilvántartása (folyamatos dokumentálás) 4. vissza az ősökhöz (strukturában felette állók módosíthatók) 5. nyílt rendszerfelépítés (program általánosítása) 6. párhuzamos ágak függetlensége 7. strukturálás (célszerű méretű rutinok használata) 8. szintenkénti teljes kifejtés (elvileg önállóan is működőképes modulok) 9. adatok elszigetelése (lokális változók használata) III. Technológiai elvek (forráskód formai követelményei) 1. strukturák zárójelezése (beginend) 2. bekezdések alkalmazása 3. értelmes azonosítók használata (konvencionális és beszédes változónevek) 4. sorokra tördelés értelmesen (üres sorok is) 5. kommentek alkalmazása IV. Esztétikai elvek (felhasználó esztétikai

elvárásai) 1. lapkezelés módja - felhasználóra bízott megjelenítési időtartam - célszerű mennyiségű és elhelyezésű kitöltés, látványos adatcsoportosítás - kiemelések használata (villogás kerülése) 2. menühasználat - hierarchikus, szintenként néhány menüponttal - fajtái: állandó (fix) menü, legördülő menü helyi menü - választás: aktuális jelölésével, kezdőbetűvel, vagy egérrel 3. ikonok alkalmazása 4. funkcióbillentyűk és forróbillentyűk használata 5. következetesség 6. hibakezelés - jelzés azonnal (indoklással) - hangjelzés kerülendő 7. help biztosítása 8. naplózás (fájlba írható: ki, mikor, mit csinált) Programozás-elmélet  K.L 26 Programhelyességvizsgálat A program helyes, ha az előfeltételek teljesülése esetén a program futtatásának eredményeként az utófeltétel teljesül. A helyességvizsgálat módszerei: 1. Tesztelés (kipróbálás jellemző adatokkal) 2. Érvényesítés (valódi

kipróbálás éles környezetben) 3. Bizonyítás (ez az elvi módszer a gyakorlatban nem mindig kivitelezhető) 4. Levezetés (formális módszer, a bizonyítás ellentettje) 5. Hibakeresés és -javítás Tesztelés I. Statikus tesztelés: szg nélküli forráskódellenőrzés 1. szintaktikai ellenőrzés - nyelvhelyesség - paraméterezés - típusellenőrzés 2. szemantikai ellenőrzés - ellentmondások keresése - kezdőérték hiánya - felhasználatlan változók - feltételek ellenőrzése II. Dinamikus tesztelés: programfuttatás 1. fekete doboz módszer (feladatorientált teszt): nem néz bele a prg forráskódjába - ekvivalenciaosztályok módszere - határértékvizsgálat módszere 2. fehér doboz módszer (strukturavezérelt teszt): forráskód alapján - utasításlefedés elve minden utasítás kerüljön kipróbálásra - feltétellefedés elve minden feltétel legyen igaz is és hamis is - részfeltétellefedés elve minden elemi feltételrész külön-külön

legyen igaz is és hamis is 3. speciális tesztek - volumenteszt: mennyiségi teszt nagy mennyiségű adattal - stresszteszt: gyorsan érkező bemenő adatokkal - biztonsági teszt: rossz adatokkal - hatékonysági teszt: futási idő és helyfoglalás mérése Programozás-elmélet  K.L Hibakeresés és -javítás Hibajelenségek: - fordítási hiba: szintaktikai hiba miatt a program el sem indul - futási hiba: a program hiba miatt megszakad - nem áll le a program futása (nem üzemszerűen lelet kilépni) - nem ír ki semmit (vagy nem mindent) - rosszat ír ki Hibajavítási alapelvek: - "érdemes" gondolkodni - miért nem azt csinálja, amit várunk? - miért azt csinálja, amit kapunk? - csak akkor javítsunk, ha megvan a hiba - javítani hibát kell, és nem a tüneteit - egy hiba több hibajelenséget is okozhat: minden egyes javítás után teszteljünk újra Módszerek: 1. feltételkeresés - mire ad jó és mire rossz eredményt? ez mitől függ? 2.

visszalépéses hibakeresés - hiba helyéből kell kiindulni, és onnan haladni visszafelé a jó részig Hibakeresés (debug) eszközei: 1. Kiírás 2. Lépésenkénti végrehajtás (programnyomkövetés) - meghívott eljárások végrehajtása egy lépésként (step over - F8) - meghívott eljárások végrehajtása soronként (trace into - F7) 3. Töréspont (breakpoint - Ctrl+F8) 4. Adatnyomkövetés (watch) 27 Programozás-elmélet  K.L 28 Hatékonyságvizsgálat A hatékonyvizsgálat szempontjai: - végrehajtási idő - helyfoglalás - bonyolultság A hatékonyság megközelítése: - globális (algoritmushatékonyság - az algoritmust vizsgálja) - lokális (kódhatékonyság - elemi utasításokat, típusokat, műveleteket vizsgálja) Globális hatékonyság Végrehajtási idő szempontjából Ciklus ⇒ ciklus ideje = lépésszám * egyszeri végrehajtási idő I. Ciklus lépésszámának csökkentés 1. sorozat elemszámának csökkentése pl.:

prímszámvizsgálat N helyett N -ig 2. sorozat részekre bontása pl.: líneáris keresés helyett logaritmikus keresés 3. sorozatok párhuzamos feldolgozása pl.: összefuttatás, unió 4. gyakoriság szerinti elrendezés - gyakoriakat előre rakjuk egy sorozatban Eljárás Keresés i:=1 Ciklus amíg i<=N és nem X(i)=Y i:=i+1 Ciklus vége VAN:=(i<=N) Ha VAN és I>1 akkor csere (X(i),X(i-1)) Eljárás vége - lemezen: leggyakoribb adatok középen, ritkábbal széleken. II. Ciklusmag végrehajtási idejének csökkentése 1. elágazástranszformálás indexeléssé pl.: 100 kockadobás esetén miből hányat dobtak? 2. feltételek egyszerűsítése, szétválasztása 3. adatok előfeldolgozása pl.: sok keresés előtt rendezés 4. adatmozgatások megszüntetése pl.: buborékelvű rendezés helyett minimumkiválasztásos Programozás-elmélet  K.L Helyfoglalás szempontjából Adatok ⇒ elemszám * elemméret Programszöveg I.a, Elemszámcsökkentés 1. sorozatok

elemeinek tárolása helyett azok számítása pl.: faktoriális 2. hézagos strukturák pl. x 23 + 3 ⋅ x 7 + 7 ⋅ x kétdimenziós tömbben pl. mátrixok sok 0 elem esetén I.b, Elemméretcsökkentés 1. elemek számítása 2. elemek kódolása II. Programszöveg csökkentése (fordítókhoz is!) 1. eljárások használata 2. programozási tételek összeépítése 3. kód adattá formálása (önálló adatállományok használata) Lokális hatékonyság Végrehajtási idő szempontjából 1. gyors műveletek használata 2. gyors típusok használata 3. függvények megszüntetése pl.: i < N helyett i ⋅ i < N pl.: sin(x)/cos(x) helyett tg(x) 4. részkifejezések külön kiszámolása 5. konstanskifejezések 1 pl.: E = mv 2 helyett E = 0 5 ⋅ mv 2 2 6. algebrai átalakítások pl.: kiemelés Helyfoglalás szempontjából 1. kis típusok használata 2. részeredmény megszüntetése 3. elágazás- és ciklusösszevonás 4. utasításkiemelés elágazásból 29

Programozás-elmélet  K.L 30 Dokumentálás 1. Felhasználói dokumentáció 1.1 A program célja és leglényegesebb funkciói 1.2 Minimális és optimális konfiguráció (HW, SW) 1.3 Használat 1.31 Telepítés lépései - kiindulási állományok - opciók (meghajtó és könyvtár, teljes/részleges, .) - helyes telepítés eredményének könyvtárai, állományai 1.32 Indítás - feltételei - lehetőségei 1.33 Átfogó ismertetés - menünként, képernyőnként, opciókként 1.34 Menüszerkezet (menüfa) - célszerűen egy oldalon megvalósítva, forróbillentyűk feltüntetésével 1.35 Gyakran ismétlődő kérdések (GyIK, FAQ, frequently askes questions) 1.4 Hibalehetőségek - helytelen használatból adódó hibák és magyarázatuk 1.5 Információkérés - saját help - könyvek - WEB-oldalak - a program készítőjének elérhetősége (pl. e-mail címe) - tájékozódás az újabb változatról 2. Fejlesztői dokumentáció 2.1 Célkitűzés,

feladatmeghatározás 2.2 Fejlesztőkörnyezet (HW, SW) 2.3 Adatszerkezet, típusok, változók 2.4 Algoritmusok 2.5 Tesztelés (tesztdokumentáció) 2.6 Fejlesztési lehetőségek 2.7 Melléklet - forráskód - irodalomjegyzék - történeti áttekintés (korábbi verziók újdonságai) 3. Reklám / Demo Programozás-elmélet  K.L Összetett adatszerkezetek megvalósítása Mutatótípus használata Pascalban: dinamikus memóriakezelés program MutatoTipus Demo; type MemCim=^LongInt; var Cim: MemCim; begin If MaxAvail>=SizeOf(LongInt) Then Begin New(Cim); WriteLn(Seg(Cim)); WriteLn(Ofs(Cim)); Dispose(Cim); End; end. program dinamikus tomb; type var MemCim elem = ^elem; = record adat: word; mut: MemCim; end; dintomb = record fej, akt: MemCim; end; t: uj: db: x: dintomb; MemCim; byte; word; begin writeln; writeln(Adj meg néhány poz. egész számot (vége:0)!); db:=0; t.fej:=nil; t.akt:=nil; repeat db:=db+1; write(db); write(. ); readln(x); if x>0 then begin

new(uj); if db=1 then t.fej:=uj else takt^mut:=uj; uj^.adat:=x; uj^.mut:=nil; t.akt:=uj; end; until x=0; writeln; writeln(A megadott értékek:); t.akt:=tfej; while t.akt<>nil do begin writeln(t.akt^adat); t.akt:=takt^mut; end; end. 31 Programozás-elmélet  K.L 32 Statikus verem és műveletei Konstans MaxHossz = X Tipus ElemTip Index Verem : Y : 0.MaxHossz : Rekord tető : Index adat : [1.MaxHossz] tömbje ElemTipnek hiba : logikai Vége Eljárás Üres(vált v:verem) v.tető:=0 v.hiba:=hamis Eljárás vége Függvény Üres-e?(v:verem):logikai Üres-e?:=(v.tető=0) Függvény vége Függvény Tele-e?(v:verem):logikai Tele-e?:=(v.tető=MaxHossz) Függvény vége Függvény Hibás-e?(vált v:verem):logikai Hibás-e?:=(v.hiba) v.hiba:=hamis Függvény vége Függvény TetőElem(vált v:verem):ElemTip Ha v.tető=0 akkor vhiba:=igaz kül. TetőElem:=vadat[vtető] Függvény vége Eljárás Verembe(vált v:verem; konstans e:ElemTip) Ha Tele-e?(v) akkor v.hiba:=igaz

kül. vtető:=vtető+1 v.adat[vtető]:=e Elágazás vége Eljárás vége Eljárás Veremből(vált v:verem; e:ElemTip) Ha Tele-e?(v) akkor v.hiba:=igaz kül. e:=vadat[vtető] v.tető:=vtető-1 Elágazás vége Eljárás vége Programozás-elmélet  K.L Dinamikus verem és műveletei Tipus ElemTip : Y MemCim : ^VElem VElem : Rekord adat : ElemTip mut : MemCim Vége Verem : Rekord tető : MemCim hiba : logikai Vége Eljárás Üres(vált v:verem) v.tető:=Nil v.hiba:=hamis Eljárás vége Függvény Üres-e?(v:verem):logikai Üres-e?:=(v.tető=Nil) Függvény vége Függvény Tele-e?(v:verem):logikai Tele-e?:=(MaxSzabadBlokk<ElemMéret(VElem)) Függvény vége Függvény Hibás-e?(vált v:verem):logikai Hibás-e?:=(v.hiba=igaz) v.hiba:=hamis Függvény vége Függvény TetőElem(vált v:verem):ElemTip Ha v.tető=Nil akkor vhiba:=igaz kül. TetőElem:=vtető^adat Függvény vége Eljárás Verembe(vált v:verem; konstans e:ElemTip) vált uj : MemCim Ha Tele-e?(v) akkor

v.hiba:=igaz kül. Lefoglal(uj) uj^.adat:=e uj^.mut:=vtető v.tető:=uj Elágazás vége Eljárás vége Eljárás Veremből(vált v:verem; vált e:ElemTip) vált sv : MemCim Ha Üres-e?(v) akkor v.hiba:=igaz kül. e:=vtető^adat sv:=v.tető v.tető:=vtető^mut Felszabadít(sv) Elágazás vége Eljárás vége 33 Programozás-elmélet  K.L 34 Statikus sor és műveletei Konstans MaxHossz = X Tipus ElemTip : Y Index : 0.MaxHossz Sor : Rekord adat : [1.MaxHossz] tömbje ElemTipnek első : Index hossz : Index hiba : logikai Vége Eljárás Üres(vált s:sor) s.első:=1 s.hossz:=0 s.hiba:=hamis Eljárás vége Függvény Üres-e?(s:sor):logikai Üres-e?:=(s.hossz=0) Függvény vége Függvény Tele-e?(s:sor):logikai Tele-e?:=(s.hossz=MaxHossz) Függvény vége Függvény Hibás-e?(vált s:sor):logikai Hibás-e?:=s.hiba s.hiba:=hamis Függvény vége Függvény ElsőElem(vált s:sor):ElemTip Ha Üres-e?(s) akkor s.hiba:=igaz kül. Első:=sadat[selső] Függvény vége

Eljárás Sorból(vált s:sor; e:ElemTip) Ha Üres-e?(s) akkor s.hiba:=igaz kül. e:=sadat[selső] s.első:=(selső mod MaxHossz)+1 s.hossz:=shossz-1 Elágazás vége Eljárás vége Eljárás Sorba(vált s:sor; konstans e:ElemTip) vált új:Index Ha Tele-e?(s) akkor s.hiba:=igaz kül. új:=első+hossz Ha új>MaxHossz akkor új:=új-MaxHossz s.adat[új]:=e s.hossz:=shossz+1 Elágazás vége Eljárás vége Programozás-elmélet  K.L 35 Dinamikus sor és műveletei Tipus ElemTip : Y MemCim : ^SElem SElem : Rekord adat : ElemTip mut : MemCim Vége Sor {következőre mutat} : Rekord első : MemCim utolsó : MemCim hiba : logikai Vége Eljárás Üres(vált s:sor) s.első:=Nil s.utolsó:=Nil s.hiba:=hamis Eljárás vége Függvény Üres-e?(s:sor):logikai Üres-e?:=(s.első=Nil) Függvény vége Függvény Tele-e?(s:sor):logikai Tele-e?:=(MaxSzabadBlokk<ElemMéret(SElem)) Függvény vége Függvény Hibás-e?(vált s:sor):logikai Hibás-e?:=s.hiba s.hiba:=hamis

Függvény vége Függvény ElsőElem(vált s:sor):ElemTip Ha Üres-e?(s) akkor s.hiba:=igaz kül. Első:=selső^adat Függvény vége Eljárás Sorból(vált s:sor; e:ElemTip) vált smut: MemCim Ha Üres-e?(s) akkor s.hiba:=igaz kül. e:=selső^adat smut:=s.első s.első:=selső^mut Felszabadít(smut) Ha s.első=Nil akkor sutolsó:=Nil Elágazás vége Eljárás vége Eljárás Sorba(vált s:sor; konstans e:ElemTip) vált új: MemCim Ha Tele-e?(s) akkor s.hiba:=igaz kül. Lefoglal(új) új^.adat:=e új^.mut:=Nil Ha s.első=Nil akkor selső:=új kül. sutolsó^mut:=új s.utolsó:=új Elágazás vége Eljárás vége Programozás-elmélet  K.L 36 Statikus lista és műveletei Konstans MaxHossz = X Tipus ElemTip Index LElem : Y : 0.MaxHossz : Rekord adat : ElemTip mut : Index Vége Lista : Rekord fej, szfej, akt : Index elem : [1.MaxHossz] tömbje LElemnek hiba : logikai Vége Eljárás Üres(vált L:lista) l.fej:=0 : lhiba:=hamis : lszfej:=1 : lakt:=0 Ciklus i:=1-től

MaxHossz-1-ig l.elem[i]mut:=i+1 Ciklus vége l.elem[MaxHossz]mut:=0 Eljárás vége Függvény Üres-e?(L:lista):logikai Üres-e?:=(l.fej=0) Függvény vége Függvény Tele-e?(L:lista):logikai Tele-e?:=(l.szfej=0) Függvény vége Függvény Hibás-e?(L:lista):logikai Hibás-e?:=(l.hiba=igaz) l.hiba:=hamis Függvény vége Függvény ElemÉrték(vált L:lista):ElemTip Ha l.akt=0 akkor lhiba:=igaz kül. ElemÉrték:=lelem[lakt]adat Függvény vége Függvény Végén-e?(vált L:lista):logikai Ha l.akt=0 akkor lhiba:=igaz kül. Végén-e?:=(lelem[lakt]mut=0) Függvény vége Programozás-elmélet  K.L Eljárás Elsőre(vált L:lista) l.akt:=lfej Eljárás vége Eljárás Következőre(vált L:lista) Ha l.akt=0 akkor lhiba:=igaz kül. lakt:=lelem[lakt]mut Eljárás vége Eljárás ElemMódosit(vált L:lista; konstans e:ElemTip) Ha l.akt=0 akkor lhiba:=0 kül. lelem[lakt]adat:=e Eljárás vége Eljárás BeszúrElsőnek(vált L:lista; konstans e:ElemTip) Ha tele-e?(L) akkor

l.hiba:=igaz kül. lelem[lszfej]adat:=e sv:=l.szfej l.szfej:=lelem[sv]mut l.elem[sv]mut:=olakt l.fej:=sv l.akt:=sv Elágazás vége Eljárás vége Eljárás BeszúrMögé(vált L:lista; konstans e:ElemTip) Ha tele-e?(L) akkor l.hiba:=igaz kül. Ha üres-e? akkor BeszúrElsőnek(l,e) kül. Ha lakt=0 akkor l.hiba:=igaz kül. lelem[lszfej]adat:=e sv:=l.szfej l.szfej:=lelem[lszfej]mut sv2:=l.elem[lakt]mut l.elem[lakt]mut:=sv l.elem[sv]mut:=sv2 l.akt:=sv Elágazás vége Elágazás vége Elágazás vége Eljárás vége 37 38 Programozás-elmélet  K.L Eljárás BeszúrElé(vált L:lista; konstans e:ElemTip) Ha tele-e?(L) akkor l.hiba:=igaz kül. Ha lakt=lfej akkor BeszúrElsőnek(l,e) kül. Ha lakt=0 akkor l.hiba:=igaz kül. lelem[lszfej]adat:=e sv:=l.szfej l.szfej:=lelem[lszfej]mut l.elem[sv]mut:=lakt előző:=l.fej Ciklus amig l.elem[előző]mut<>lakt előző:=l.elem[előző]mut Ciklus vége l.elem[előző]mut:=sv l.akt:=sv Elágazás vége Elágazás vége Elágazás

vége Eljárás vége Eljárás Előzőre(vált L:lista) Ha l.akt=0 akkor lhiba:=igaz kül. sv:=lakt l.akt:=lfej Ciklus amig l.elem[lakt]mut<>sv l.akt:=lelem[lakt]mut Ciklus vége Elágazás vége Eljárás vége Eljárás BeszúrEléV(vált L:lista, konstans e:ElemTip) Ha l.akt=lfej akkor BeszúrElsőnek(l,e) kül. Előzőre(l) BeszúrMögé(l,e) Elágazás vége Eljárás vége Eljárás Töröl(vált L:lista) Ha l.akt=0 akkor lhiba:=igaz kül. Ha lakt=lfej akkor lelem[lfej]mut:=lszfej l.szfej:=lfej l.fej:=lelem[lfej]mut l.akt:=lfej Elágazás vége Eljárás vége Programozás-elmélet  K.L 39 Dinamikus lista és műveletei Tipus ElemTip MemCim LElem Lista : Y : ^LElem : Rekord adat : ElemTip mut : MemCim Vége : Rekord fej, akt hiba Vége {következőre mutat} : MemCim : logikai Eljárás Üres(vált L:lista) l.fej:=Nil l.akt:=Nil l.hiba:=hamis Eljárás vége Függvény Üres-e?(vált L:lista):logikai Üres-e?:=(l.fej=Nil) Függvény vége Függvény

Tele-e?(vált L:lista):logikai Ha MaxSzabadBlokk<ElemMéret(LElem) akkor Tele-e?:=igaz kül. Tele-e?:=hamis Függvény vége Függvény Hibás-e?(vált L:lista):logikai Hibás-e?:=(l.hiba=igaz) l.hiba:=hamis Függvény vége Függvény ElemÉrték(vált L:lista):ElemTip Ha l.akt=Nil akkor lhiba:=igaz kül. ElemÉrték:=lakt^adat Függvény vége Függvény Végén-e?(vált L:lista):logikai Végén-e?:=(l.akt=Nil) Függvény vége 40 Programozás-elmélet  K.L Eljárás Elsőre(vált L:lista) l.akt:=lfej Eljárás vége Eljárás Következőre(vált L:lista) Ha l.akt=Nil akkor lhiba:=igaz kül. lakt:=lakt^mut Eljárás vége Eljárás ElemMódosit(vált L:lista; konstans e: ElemTip) Ha l.akt=Nil akkor lhiba:=igaz kül. lakt^adat:=elem Eljárás vége Eljárás BeszúrMögé(vált L:lista; konstans e: ElemTip) vált uj : MemCim Ha Tele-e?(l) vagy l.akt=Nil akkor l.hiba:=igaz kül. Lefoglal(uj) uj^.adat:=e Ha Üres-e?(l) akkor uj^.mut:=Nil l.fej:=uj kül. uj^mut:=lakt^mut

l.akt^mut:=uj Elágazás vége l.akt:=uj Elágazás vége Eljárás vége Eljárás BeszúrElsőnek(vált L:lista; konstans e: ElemTip) vált uj: MemCim Ha Tele-e?(l) akkor l.hiba:=igaz kül. Lefoglal(uj) uj^.adat:=e uj^.mut :=lfej l.fej:=uj l.akt:=uj Elágazás vége Eljárás vége Programozás-elmélet  K.L Eljárás BeszúrElé(vált L:lista; konstans e: ElemTip) {bárhová} vált uj: MemCim Ha Tele-e?(l) akkor l.hiba:=igaz kül. Lefoglal(uj) Ha Üres-e?(l) vagy Végén-e?(l) akkor uj^.adat:=e uj^.mut :=Nil Ha Üres-e(l) akkor l.fej:=uj kül. lakt:=lfej Ciklus amig l.akt^mut<>Nil l.akt:=lakt^mut Ciklus vége l.akt^mut:=uj Elágazás vége l.akt:=uj kül. uj^adat:=lakt^adat l.akt^adat:=e uj^.mut:=lakt^mut l.akt^mut:=uj Elágazás vége Elágazás vége Eljárás vége Eljárás Töröl(vált L:lista) vált smut: MemCim Ha l.akt=Nil akkor l.hiba:=igaz kül. Ha lakt=lfej akkor lfej:=lakt^mut Felszabadit(l.akt) l.akt:=lfej kül. smut:=lfej Ciklus amig

smut^.mut<>lakt smut:=smut^.mut Ciklus vége smut^.mut:=lakt^mut Felszabadit(l.akt) l.akt:=smut^mut Elágazás vége Elágazás vége Eljárás vége 41 Programozás-elmélet  K.L 42 Statikus bináris fa Konstans MaxHossz = X Tipus ElemTip Index BinFaElem : Y : 0.MaxHossz : Rekord bal : Index adat : ElemTip jobb : Index Vége BinFa : Rekord fa fej szh hiba Vége : : : : tömbje[1.MaxHossz] BinFaElemnek Index Index logikai Dinamikus bináris fa Tipus ElemTip MemCim BinFaElem : Y : ^BinFaElem : Rekord bal : MemCim adat : ElemTip jobb : MemCim Vége BinFa : Rekord fej, akt : MemCim hiba : logikai Vége vagy egyszerűbben: BinFa : MemCim Programozás-elmélet  K.L Eljárás Üres(f:BinFa) f=Nil Függvény vége Függvény Üres-e?(f:BinFa):logikai Üres-e?:=(f=Nil) Függvény vége Függvény EgyelemüFa(e:ElemTip):BinFa vált f:BinFa Ha MaxSzabadBlokk>=ElemMéret(BinFa) akkor Lefoglal(f) f.adat:=e f.bal:=Nil f.jobb:=Nil EgyelemüFa:=f különben

EgyelemüFa:=Nil Elágazás vége Függvény vége Eljárás BalraIlleszt(vált mihez:BinFa; konst mit:BinFa) Ha mihez^.bal=Nil akkor mihez^bal:=mit Eljárás vége Függvény BalGyerek(f:BinFa):BinFa BalGyerek:=f^.bal Függvény vége Függvény GyökérElem(f:BinFa):ElemTip GyökérElem:=f^.elem Függvény vége Eljárás GyökérMódosit(vált f:BinFa; konst e:ElemTip) f^.elem:=e Eljárás vége Eljárás FaTörlés(vált f:BinFa) Ha nem Üres-e?(f) akkor FaTörlés(BalGyerek(f)) FaTörlés(JobbGyerek(f)) Felszabadit(f) f:=Nil Elágazás vége Eljárás vége 43 44 Programozás-elmélet  K.L Fabejárások Eljárás BKJ(f:BinFa) Ha nem Üres-e?(BalGyerek(f)) akkor BKJ(BalGyerek(f)) Feldolgoz(GyökérElem(f)) Ha nem Üres-e?(JobbGyerek(f)) akkor BKJ(JobbGyerek(f)) Eljárás vége Eljárás BJK(f:BinFa) Ha nem Üres-e?(BalGyerek(f)) akkor BKJ(BalGyerek(f)) Ha nem Üres-e?(JobbGyerek(f)) akkor BKJ(JobbGyerek(f)) Feldolgoz(GyökérElem(f)) Eljárás vége Eljárás

KBJ(f:BinFa) Feldolgoz(GyökérElem(f)) Ha nem Üres-e?(BalGyerek(f)) akkor BKJ(BalGyerek(f)) Ha nem Üres-e?(JobbGyerek(f)) akkor BKJ(JobbGyerek(f)) Eljárás vége Programozás-elmélet  K.L 45 Postfix forma előállítása Infix alakból Tipus Változó LexEgys = Rekord fajta : (OPERANDUS,MUVJEL) adat : szöveg Vége InFix PostFix v le c : : : : : Sor(LexEgys) Sor(LexEgys) verem(karakter) LexEgys karakter <- bemenet <- kimenet Eljárás PostFixKészít Üres(v) : Üres(PostFix) Ciklus amig nem Üres-e?(InFix) Sorból(InFix,le) Elágazás le.fajta = OPERANDUS esetén le.adat = ( esetén le.adat = ) esetén egyébként Elágazás vége Ciklus vége VeremÜrit Eljárás vége Sorba(PostFix,le) Verembe(v,le.adat) NyitóigKivesz NemKisebbeketKivesz Eljárás NyitóigKivesz Ciklus amig Tetö(v)<>( Kivesz(v,c) Sorba(PostFix,LexE(MUVJEL,c) Ciklus vége Veremböl(v,c) Eljárás vége Eljárás NemKisebbeketKivesz Ciklus amig nem Üres-e?(v) és

Prec(Tetö(v))>=Prec(le.fajta) Veremböl(v,c) Sorba(PostFix,LexE(MUVJEL,c)) Ciklus vége Verembe(v,le.fajta) Eljárás vége Függvény Prec(jel:szöveg):szám Elágazás jel=+ vagy jel=- esetén Prec:=1 jel=* vagy jel=/ esetén Prec:=2 jel=^ esetén Prec:=3 jel=( esetén Prec:=4 Elágazás vége Függvény vége Programozás-elmélet  K.L 46 Eljárás VeremÜrit Ciklus amig nem Üres-e?(v) Veremböl(v,c) Sorba(PostFix,LexE(MUVJEL,c)) Ciklus vége Eljárás vége Függvény LexE(ffajta:(OPERANDUS,MUVJEL);fadat:szöveg):LexEgys LexE.fajta:=ffajta LexE.adat:=fadat Függvény vége Postfix forma kiértékelése Tipus Változó LexEgys = Rekord fajta : (OPERANDUS,MUVJEL) adat : szöveg Vége PostFix Eredm v le op1,op2 : : : : : Sor(LexEgys) valós verem(valós) LexEgys valós <- bemenet <- kimenet Eljárás PostfixÉrték Üres(v) Ciklus amig nem Üres-e?(PostFix) Sorból(PostFix,le) Ha le.fajta=OPERANDUS akkor Verembe(v,Érték(le.adat) kül. Veremböl(v,op2)

Veremböl(v,op1) Verembe(v,KiSzámol(le.adat,op1,op2) Elágazás vége Ciklus vége Veremböl(v,Eredm) Eljárás vége Programozás-elmélet  K.L Gráf Eljárás SzélességiBejárás(x:pont) vált s: sor h: halmaz p,sp: pont él: élsorszám ÜresSor(s) ÜresHalmaz(h) Sorba(s,x) Halmazba(h,x) Feldolgoz(x) Ciklus amig nem Üres-e?(s) Sorból(s,p) Ciklus él:=1-től KiindulóÉlekSzáma(p)-ig sp:=KövetkezőPont(p,él) Ha nem Eleme(h,sp) akkor Sorba(s,sp) Halmazba(h,sp) Feldolgoz(sp) Elágazás vége Ciklus vége Ciklus vége Eljárás vége Eljárás MélységiBejárás(x:pont) vált v: verem ∈ (pont,élsorszám) h: halmaz sp,p: pont él: élsorszám ÜresVerem(v) ÜresHalmaz(h) p:=x : él:=1 Halmazba(h,p) Feldolgoz(p) Ciklus Ciklus amig él<=KiindulóÉlekSzáma(p) sp:=Következőpont(p,él) Ha nem Eleme(h,sp) akkor Verembe(v,(p,él)) p:=sp : él:=1 Halmazba(h,p) Feldolgoz(p) különben él:=él+1 Elágazás vége Ciklus vége Veremből(v,(p,él)) él:=él+1 Mígnem

Üres-e?(v) és él>KiindulóÉlekSzáma(x) Ciklus vége Eljárás vége 47 Programozás-elmélet  K.L 48 Objektumorientált programozás Az objektum-orientált programozás (röviden OOP) a természetes gondolkodást, cselekvést közelítő programozási mód, amely a programozási nyelvek tervezésének természetes fejlődése következtében alakult ki. Az így létrejött nyelv sokkal strukturáltabb, sokkal modulárisabb és absztraktabb, mint egy hagyományos nyelv. Egy OOP nyelvet három fontos dolog jellemez Ezek a következők: • Az egységbezárás (encapsulation) azt takarja, hogy az adatstruktúrákat és az adott struktúrájú adatokat kezelő függvényeket (Smalltalk, illetve a TURBO Pascal terminológiával élve metódusokat) kombináljuk; azokat egy egységként kezeljük, és elzárjuk őket a külvilág elől. Az így kapott egységeket objektumoknak nevezzük Az objektumoknak megfelelő tárolási egységek típusát a C++-ban osztálynak

(class) nevezzük. • Az öröklés (inheritance) azt jelenti, hogy adott, meglévő osztályokból levezetett újabb osztályok öröklik a definiálásukhoz használt alaposztályok már létező adatstruktúráit és függvényeit. Ugyanakkor újabb tulajdonságokat is definiálhatnak, vagy régieket újraértelmezhetnek. Így egy osztályhierarchiához jutunk • A többrétűség (polymorphism) alatt azt értjük, hogy egy adott tevékenység (metódus) azonosítója közös lehet egy adott osztályhierarchián belül, ugyanakkor a hierarchia minden egyes osztályában a tevékenységet végrehajtó függvény megvalósítása az adott osztályra nézve specifikus lehet. Az ún virtuális függvények lehetővé teszik, hogy egy adott metódus konkrét végrehajtási módja csak a program futása során derüljön ki. Ugyancsak a többrétűség fogalomkörébe tartozik az ún. overloading, aminek egy sajátságos esete a C nyelv standard operátorainak átdefiniálása

(operator overloading). Ezek a tulajdonságok együtt azt eredményezik, hogy programkódjaink sokkal struktúráltabbá, könnyebben bővíthetővé, könnyebben karbantarthatóvá válnak, mintha hagyományos, nem OOP-technikával írnánk őket. Programozás-elmélet  K.L Objektum = adattagok + metódusok tipus téglalap = objektum a,b: valós; függvény kerület: valós; függvény terület: valós; objektum vége függvény téglalap.kerület: valós; kerület:=2*(a+b); függvény vége; függvény téglalap.terület: valós; terület:=a*b; függvény vége; tipus téglatest = objektum t: téglalap; m: valós; függvény térfogat: valós; objektum vége; függvény téglatest.térfogat: valós; térfogat:=t.terület*m; függvény vége; vált. t1, t2: téglalap; tt: téglatest; Eljárás demo t1.a:= 5; t1b:= 2; t2.a:=10; t2b:=25; ki(t1.kerulet); ki(t1.terulet); ki(t2.kerulet); ki(t2.terulet); tt.ta:=3; tttb:=5; ttm:=4; ki(tt.terfogat); Eljárás vége 49

Programozás-elmélet  K.L 50 program oop teglalap; type teglalap = object a,b: real; function kerulet: real; function terulet: real; end; function teglalap.kerulet: real; begin kerulet:=2*(a+b); end; function teglalap.terulet: real; begin terulet:=a*b; end; type teglatest = object t: teglalap; m: real; function terfogat: real; end; function teglatest.terfogat: real; begin terfogat:=t.terulet*m; end; var t1, t2: teglalap; tt: teglatest; begin t1.a:= 5; t1b:= 2; t2.a:=10; t2b:=25; writeln(t1.kerulet); writeln(t1.terulet); writeln(t2.kerulet); writeln(t2.terulet); tt.ta:=3; tttb:=5; ttm:=4; writeln(tt.terfogat); end. Programozás-elmélet  K.L #include <stdio.h> typedef class { public: float a,b; float kerulet(); float terulet(); } teglalap; float teglalap::kerulet() { return 2*(a+b); }; float teglalap::terulet() { return a*b; } typedef class { public: teglalap t; float m; float terfogat(); } teglatest; float teglatest::terfogat() { return t.terulet()*m; } teglalap

teglatest t1, t2; tt; void main() { t1.a= 5; t1b= 2; t2.a=10; t2b=25; printf("%f ",t1.kerulet()); printf("%f ",t1.terulet()); printf("%f ",t2.kerulet()); printf("%f ",t2.terulet()); tt.ta=3; tttb=5; ttm=4; printf("%f ",tt.terfogat()); } 51