Programozási paradigmák és technikák Előadás: Hajnal Éva Gyakorlat: Burián Ágnes
Paradigma •
Egy tudományterület általánosan elfogadott nézetei (fogalmai, szakkifejezései) egy adott korszakban, időpontban.
•
Egy szó összes ragozott alakjának rendszerezett leírása. (például igeragozási tábla)(lásd: Magyar Értelmező Kéziszótár) Egy mondat szakasz helyettesítésére alkalmas kifejezések osztálya, gyűjteménye (nem azonos értelmű, jelentésű (szinonímák), hanem azonos módon használható szavak).
•
•
A paradigma a gondolkodásoknak, vélekedéseknek, értékeknek és módszereknek egy adott társadalom vagy szűkebben egy tudományos közösség minden tagja által elfogadott összegzését jelenti. Programozási paradigmák és technikák
Dr. Hajnal Éva
2
Adatbázisok Programnyelvek C#, Java, Assembly…
Adatszerkezetek
Algoritmusok
Programozási paradigmák és technikák Hogyan kell programot írni UML
Alapismeretek
Szoftver ismeretek
Informatikus tudása
Hogyan kell tervezni
Hogyan kell dokumentálni Rendszertervezés Gazdasági ismeretek
Hardver ismeretek
Programozási paradigmák és technikák
Dr. Hajnal Éva
3
Tematika Rekurzió: Fibonacci (rekurzív és nem rekurzív), QuickSort (rekurzív és nem rekurzív) 2 OO programozás C# nyelven 2012.02.20 Osztályok, objektumok. Konstruktor, destruktor, this. Beágyazott osztályok. Egyszerű típuskonverziók Mezők, metódusok. Átdefiniálás (overloading) Névterek. Láthatóság. Felbontott típusok (partial types) 3 Öröklés 2012.02.27 Többszörös öröklés lehetőségei a különböző nyelvekben. Konstruktorok az öröklésben. Hívási, végrehajtási sorrend. Paraméterezett őskonstruktor hívása. Különböző konstansok és inicializálásuk Metódusok elrejtése. Az ősosztály azonos nevű metódusának hívása. Öröklés és értékadás. Explicit típuskonverzió. Az Object.GetType(). Az is, as operátorok.. 4 Polimorfizmus 2012.03.05 Nem virtuális metódusok, elrejtés. Virtuális metódusok, felüldefiniálás. Futásidejű kötés, polimorfizmus. Virtuális Metódus Tábla. Konstruktorok, destruktorok feladata. Virtual, override, new, new virtual. Virtuális metódus elrejtése. A virtualitás újrakezdése. Statikus és virtuális metódusok. Lezárt metódus, lezárt osztály Delegált függvények 5 Absztrakt osztály és interfész. Absztrakt metódus. Absztrakt osztály 2012.03.12 Generikus osztályok Interfész. Metódusok implementációja. Láthatóság interfész esetén. Explicit implementált interfész. Absztrakt osztály vagy interfész . 6 Iterátorok. Kivételkezelés. Kivétel dobása, elkapása. Kezeletlen kivétel. Kivételek 2012.03.19 egymásba ágyazása. Az osztálykönyvtár és a kivételkezelés. Operátor overloading. Operátor. Átdefiniálható operátorok. Precedencia. Implicit, explicit 4 Programozási paradigmák Dr. Hajnal Éva konverzió. és technikák 1 2012.02.13-
7 2012.03.26
Dinamikus memóriakezelés. Verem/sor. Statikus megvalósítás, dinamikus megvalósítás.
8
2012.04.02
ZH
9
Gráfok, Gráfalgoritmusok Szünet
10 2012.04.16
Láncolt listák létrehozása Láncolt listák bejárása. Keresés, beszúrás, törlés, hulladékgyűjtés. Fejelt listák. Kétirányú listák
11 2012.04.23
Fa adatszerkezetek. Fát reprezentáló adatstruktúrák. Adatmodell, eljárásmodell. Adatszerkezetek rendszerezése. Absztrakt társzerkezetek. Vektor, lista. Bináris fák. Megvalósításuk a memóriában. Bináris fák bejárása, keresés. Beszúrás, törlés. BST fák, AVL fák. Általánosított fák, piros-fekete fa, B-fa
12 2012.04.30
Rendezések. A rendező algoritmusok bonyolultsága. Radix rendezés. Kupacrendezés (HeapSort). Kupacrendezés bonyolultsága. Útvonalak hosszúsága, a Huffman algoritmus.
13 2012.05.07
A tábla, mint adatszerkezet. Hasítás. Hasító függvények. Az összeütközések feloldása. Hasítás és keresőfák. Hasítás alkalmazásai
Programozási paradigmák és technikák
Dr. Hajnal Éva
5
Követelmények • Az aláírás megszerzésének feltétele: A két gépes ZH, és az elméleti ZH megírása, a házi feladat beadása. A ZH-k és házifeladatból megszerezhető pontok 50%-nak teljesítése, vagyis a megszerezhető 120 pontból minimum 60 pontot kell elérni. • A vizsga jegy: A gyakorlatokon a 2., 3., 4., 5., 8., 10., 11., 12. héten egy-egy 5 pontos, a 6., 13. héten egy-egy 20 pontos gépes ZH megírása, a 13. héten 20 pontos önálló feladat beadása és ebből beszámoló. Az előadás anyagából a 8. héten egy 20 pontos elméleti ZH lesz. Összesen elérhető 120 pont. A vizsgán további 120 pont érhető el. A hozott pontszám a vizsga pontszámához hozzáadódik. Osztályozás: 193-240 jeles 169-192 jó 145-168 közepes 121-144 elégséges
Programozási paradigmák és technikák
Dr. Hajnal Éva
6
Teszt (igaz-hamis) 1. 2. 3. 4. 5. 6.
7. 8.
Szintaktika a szabályok összesége, amely megszabja a forráskód felépítését. A C# programnyelv nem különbözteti meg a kis- és a nagy betűket: Consol.WriteLine ugyanaz mint consol.writeline Az if egy kulcsszó, azaz a forráskódban a saját meghatározott jelentésén kívül nem lehet másra használni. //Ezt a programsort a C# fordítója nem fordítja le. A C# erősen típusos nyelv, ami azt jelenti, hogy minden egyes változó típusának már fordítási időben ismertnek kell lennie. Az int és a System.Int16 ugyanazt jelenti, egymással helyettesíthetők. Egy változó abban a blokkban használható, amelyben definiálva lett. if(a
Dr. Hajnal Éva
7
Teszt (igaz-hamis) 9.
Az alábbi értékadás helyes: 10=++a;
10. Teljesen mindegy, hogy a programban mit írok: a++ vagy ++a, ugyanaz történik 11. int x=10; int y=3; int z=x/y; esetén z értéke 3,333… 12. for (int i=0;i<10;i++){k } k utasítás 10-szer lesz végrehajtva
Programozási paradigmák és technikák
Dr. Hajnal Éva
8
Programozási paradigmák • Oszd meg és uralkodj paradigma – A nagyobb feladat kisebb egymástól független részfeladatokra bontása
• Dinamikus programozás paradigma – Ha a feladat nem bontható fel egymástól független részfeladatokra – Az egymástól függő részfeladatok behatárolása, és a részeredmények tárolása
Programozási paradigmák és technikák
Dr. Hajnal Éva
9
Függvények A függvény utasítások logikailag összefüggő csoportja, mely önálló névvel és visszatérési értékkel rendelkezik. • Hívása printf(„Hello”); Console.Clear(); Consol.WriteLine(„Hello”); a=sin(x); Consol.WriteLine(sin(x));
• Szerkezete Visszatérésiértéktípusa FüggvényNeve(paraméterlista) { Utasítások; Return visszatérési érték; } Programozási paradigmák és technikák
Dr. Hajnal Éva
10
Függvény végrehajtása, és definíciója static void terulet() { Console.WriteLine("Kérem a négyzet oldalát:"); int t = Int32.Parse(Console.ReadLine()); Console.WriteLine( t * t); } static void Main(string[] args) { terulet(); Console.ReadLine(); } 1. Program belépési pontja (Entry point) Programozási paradigmák és technikák
Dr. Hajnal Éva
11
Eljárás végrehajtása I.
Programozási paradigmák és technikák
Dr. Hajnal Éva
12
Eljárás végrehajtása II.
Programozási paradigmák és technikák
Dr. Hajnal Éva
13
Változók hatásköre • A változók hatásköre az őket tartalmazó blokkra terjed ki. • Ha több eljárás közt „osztunk meg „ egy változót: Static módosítóval rendelkező eljáráshoz static módosítójú változót kell definiálni.
Programozási paradigmák és technikák
Dr. Hajnal Éva
14
Függvény visszaadott értéke • • • •
void int double Összetett adat
Eljárás
függvény
– pl. tömb
Programozási paradigmák és technikák
Dr. Hajnal Éva
15
Paraméter átadás static void Kiiras(int a,int b) { Console.WriteLine("A {0}+{1}={2}",a,b,a+b); }
Programozási paradigmák és technikák
Dr. Hajnal Éva
16
Függvény paraméterei
• Bemenő-Kimenő paraméterek • Érték szerinti – cím szerinti paraméter átadás • Paraméterek, helyi változók tárolása
Programozási paradigmák és technikák
Dr. Hajnal Éva
17
Átadott paraméter egyeztetése
Programozási paradigmák és technikák
Dr. Hajnal Éva
18
Érték szerinti paraméter átadás
Programozási paradigmák és technikák
Dr. Hajnal Éva
19
Cím szerinti paraméter átadás • Átmenő, kimenő paraméter • Ref, out
Programozási paradigmák és technikák
Dr. Hajnal Éva
20
Paraméterátadás • Szignatúra: függvény neve, és paraméterlistája az abban levő típusokkal • Írhatunk azonos nevű függvényeket, ha a szignatúrájuk különböző. Polimorfizmus. • Kérdés: Lehet-e egy programon belül definiálni az alábbi függvényeket? void mozgat(int x, int y); void mozgat (int x); void mozgat (int y); Programozási paradigmák és technikák
Dr. Hajnal Éva
21
File kezelés • C#-an többszintű file kezelés létezik egymás mellett. – Form alapú filekezelés (OpenFileDialog, SaveFileDialog)
–File-ok streamek, adatfolyamok – Bináris file kezelés byte-ról byte-ra olvasható, írható a file – XML fileok használata, szerializáció – Konfigurációs file-ok használata Programozási paradigmák és technikák
Dr. Hajnal Éva
22
File kezelés • Magas szintű file kezelés: a fileokat adatfolyamnak stream-nek tekintjük akárcsak a Console I/O-t. A stream a definíciója és a megnyitása után írható, olvasható. Használat végén be kell zárni!!!! • System.IO névtér használata Programozási paradigmák és technikák
Dr. Hajnal Éva
23
File stream példa
//névtér megadása Using System.IO; //FileStream megadása FileStream fs=new FileStream(„c:\\eva\\text.txt”, FileMode.Open); //Stream megadása olvasáshoz, íráshoz StreamWriter StreamReader rs=new StreamReader(fs); String s=rs.ReadLine(); While(s!=null) { Console.WriteLine(s); s=rs.ReadLine(); } rs.Close(); fs.Close(); Programozási paradigmák és technikák
Dr. Hajnal Éva
24
FileMode értékei Create
LÉTREHOZ (ha van törli)
CreateNew
LÉTREHOZ (ha van akkor hiba)
Open
Megnyit (ha nincs akkor hiba)
OpenOrCreate
Megnyit, ha nincs létrehozza
Append
Megnyit hozzáfűzésre
Truncate
Megnyit és töröl
Programozási paradigmák és technikák
Dr. Hajnal Éva
25
FileAccess értékei • Read • Write • ReadWrite
Programozási paradigmák és technikák
Dr. Hajnal Éva
26
A file vizsgálata • Létezik-e File.Exists() • Elértük-e a végét : a beolvasott sor értéke null
Programozási paradigmák és technikák
Dr. Hajnal Éva
27
File-ba írás Using System.IO; StreamWriter sw=new StreamWriter(@”c:\teszt.txt”,FileMode.Open, FileAccess.Write, FileShare.None); For (int i=0; i<10;++i) { sw.Write(i.ToString()); sw.Write(„\n”); } Sw.Close(); Programozási paradigmák és technikák
Dr. Hajnal Éva
28
Teszt
Static int szamol(int a, double b) {return b/a;}
1. A szamol() egy eljárás 2. Az „a” és „b” formális paraméterek 3. Console.WriteLine(„{0}”,szamol(5,6)); programsor helyes 4. Az int c=szamol(2,5) eredménye 2.5 5. Cím szerinti paraméterátadás van a 4. feladatban 6. A Main függvénynek is lehet paramétere 7. Lehet készíteni static int szamol( int a, int b) fejlécű függvényt is ugyanebben a programban 8. A függvény szignatúrája a neve és paramétereinek típusa Programozási paradigmák és technikák
Dr. Hajnal Éva
29
Rekurzió fogalma • A rekurzió a ciklusnál bonyolultabb programszerkezet, de ugyanarra való – egy tevékenység ismételt végrehajtására. • Rekurzió: Egy függvény saját magát hívja meg (közvetve, vagy közvetlenül).
Programozási paradigmák és technikák
Dr. Hajnal Éva
30
Definíció (Specifikáció) 1. feladat: Számítsuk ki N
• Iteratív definíció
i n ! i 1 1 n
faktoriálist
• Rekurzív definíció
n0
n * (n 1)! ha n 0 n! 1 ha n 0 n0
Programozási paradigmák és technikák
Dr. Hajnal Éva
31
Rekurzió fogalma 1. feladat: Számítsuk ki N faktoriálist static int faktor(int n) { if (n == 0) return 1; int f=1; for (int i = 1; i <= n; i++) { f = f * i; } return f; } Programozási paradigmák és technikák
static int frek(int k) { if (k > 0) return k*frek(k-1); return 1; }
Dr. Hajnal Éva
32
Kérdések 1. Hogy kerül ugyanazzal a kóddal megvalósított eljáráshoz mindig más bemenő érték? – Bemenő érték problémája 2. Hogy kerül a hívó eljárásban a függvényérték „felszínre”? – Értékvisszaadás problémája 3. Lokális a k változó. Melyik a sok közül? – A lokális változók problémája
Programozási paradigmák és technikák
Dr. Hajnal Éva
33
Rekurzív algoritmus készítése • Közvetlen rekurzió: Ha az A algoritmus egyik lépése az A algoritmus végrehajtását írja elő. • Közvetett rekurzió: Ha az A algoritmus egyik lépése a B algoritmus végrehajtása, a B algoritmus előírja az A algoritmus végrehajtását.
• Rekurzív algoritmusok végességének kritériumai – Az algoritmusnak tartalmaznia kell egy alapesetet, amely közvetlenül megvalósítható – Minden hivatkozásnál közelebb kell kerülni ehhez az alapesethez Programozási paradigmák és technikák
Dr. Hajnal Éva
34
Rekurzió alkalmazása a feladatmegoldásban • Rekurzív specifikáció • Nemrekurzív specifikáció • Rekurzív algoritmus
• Nemrekurzív algoritmus
• Rekurzív programnyelv
• Nemrekurzív programnyelv • Számítógép
Programozási paradigmák és technikák
Dr. Hajnal Éva
35
2. Feladat A Fibonacci-számok • Nyúlpár szaporodását írja le • 0,1,1,2,3,5,8,13,21,34,55… • Def: 0 ha n 0
Fib( n) 1 ha n 1 Fib( n 1) Fib( n 2) ha
Programozási paradigmák és technikák
Dr. Hajnal Éva
n 1
36
Faktoriális számítás sebességének vizsgálata N
Iteratív
Rekurzív
10
0,04
0,2
20
0,08
0,42
50
0,2
1,05
70
0,28
1,5
Programozási paradigmák és technikák
Dr. Hajnal Éva
37
RekurzióIteráció Fibonacci sor, faktoriális számítás, Pascalháromszög 1. Rekurzió helyettesíthető iterációval 2. Az f(n-1), f(n-2)… értékek tárolhatók tömbben Fib(N) F[0]=0, F[1]=1 Ciklus I=2 –től N-ig F[I]=F[I-1]+F[I-2] Ciklus vége Fib=F[N] Eljárás vége Programozási paradigmák és technikák
Dr. Hajnal Éva
38
Jobbrekurzió Példa: Egy szöveg betűinek kiírása Betűk(X) Ha X nem üres akkor Ki: Első(X) Betűk(Elsőutániak(X)) Eljárás vége
• A rekurzív hívás a függvény végén van, utána már nincs szükség a függvény lokális változóira. A paraméterek az eredményt tartalmazzák, vagy a rekurzió szervezését segítik. Programozási paradigmák és technikák
Dr. Hajnal Éva
39
Balrekurzió Példa: Egy bekért számnál kisebb 2 hatványok kiírása visszafelé (Szöveg kiírása betűnként visszafelé) Hatványok(K,M) Ha K<=M akkor Hatványok(2*K,M); Ki:K
Eljárás vége
• A Rekurzív hívás az eljárás elején van • Sorozat megfordítása igényli, hogy az elemeket valamilyen adatszerkezetben tároljuk (verem, de lehet tömb is). Programozási paradigmák és technikák
Dr. Hajnal Éva
40
Nevezetes feladatok rekurzióra • • • •
Hanoi tornyai Pascal háromszög Koch-fraktál Backtrack algoritmus – 8 királynő problémája
Programozási paradigmák és technikák
Dr. Hajnal Éva
41
Programtranszformációk Rekurzió-iteráció Elöltesztelő ciklus R_iteratív(x) Ciklus amig xxx S(x) Ciklus vége Eljárás vége
R_rekurziv(x) Ha xxx akkor S(x) R_rekurziv(x) Elágazás vége Eljárás vége FeltételUtasításRekurzív hívás
Programozási paradigmák és technikák
Dr. Hajnal Éva
42
Programtranszformációk Rekurzió-iteráció Hátultesztelő ciklus R_it(x)
R_rek
Ciklus s(x) Amíg xxx Ciklus vége Eljárás vége
s(x) Ha xxx akkor R_rek(x) Eljárás vége
UFR
Programozási paradigmák és technikák
Dr. Hajnal Éva
43
Programtranszformációk Rekurzió-iteráció számlálós ciklus~előltesztelős i=kezdet Rek_it(i,n) Ciklus amíg i<=vég Ha i
Programozási paradigmák és technikák
Dr. Hajnal Éva
44
Programtranszformációk ItElj(X) Y=g(X) ciklus amíg p(X,Y) S(X,Y) ciklus vége X=h(X,Y) Eljárás vége
Programozási paradigmák és technikák
Rek0Elj(X,Y) Ha p(X,Y) akkor S(X,Y) Rek0Elj(X,Y) Eljárás vége Rek1Elj(X) Y=g(X) Rek0Elj(X,Y) X=h(X,Y) Eljárás vége
Dr. Hajnal Éva
45
Iteráció rekurzió Miez Eljárás(A,X,K,E,V) K=(E+V)div 2 Ha A[K]<X akkor E=K+1 Ha A[K]>X akkor V(K-1) Ha A[K]!=X akkor Miez(A,X,K,E,V) Eljárás vége
Programozási paradigmák és technikák
Dr. Hajnal Éva
46
Programozási tételek rekurzív megvalósítása:Összegzés 1. Szumma(I,N) Ha I<=N akkor Szumma=A[I]+Szumma(I+1,N) Különben Szumma=0; Függvény vége 2. Szumma(N) Ha N>0 akkor Szumma=Szumma(N-1)+A(N) Különben Szumma=0 Függvény vége Programozási paradigmák és technikák
Dr. Hajnal Éva
47
A Quicksort rendezés Hoare (1960) Módszer: A() a rendezendő sorozat, X kulcs 1. Lépés: Válasszuk az első elemet kulcsnak. X=A(0) 2. Felosztás. A tömböt két részre bontjuk úgy, hogy egy K előtt ne legyen nála nagyobb, K után ne legyen nála kisebb elem 3. A K előtti, és a K utáni részt ugyanezzel a módszerrel külön-külön rendezzük. Programozási paradigmák és technikák
Dr. Hajnal Éva
48
Rendezés menete X=5
5
3
2
6
9
1
4
i
7
X=4
3
2
6
9
1
i
5
3
2
3
2
j 2
1
9
6
1
9
6
5
7
j
1
7
4
9
6
5
7
j< i X=1
4
3
i
j 4
4
5
7
1
3
2
4
9
6
5
7
j= i
j< i 4
3
2
1
9
6
5
7
X=3
1 i
K=j 1 Programozási paradigmák és technikák
3
Dr. Hajnal Éva
2
4
9
6
5
7
4
9
6
5
7
j 2
3
49
Algoritmus Quick(A, E,V) Szétválogat(A,E,V,K) Ha K-E>1 akkor Quick(A,E,K-1) Ha V-K>1 akkor Quick(A, K+1,V) Eljárás vége
Szétválogat1(A,E,V,K) K=E; J=V; I=E; X=A[J] Ciklus amíg J>I Ciklus amíg A[J]>X J=J-1 Ciklus vége Ciklus amíg A[I]<X i=I+1 Ciklus vége Ha J>I akkor csere(A[I],A[J]) K=J Ciklus vége
Egyszerű szétválogatás sok cserével Programozási paradigmák és technikák
Szétválogat2(A,E,V,K) K=E; J=V; X=A[K] Ciklus amíg K<J és A[J]>=X J=J-1 Ciklus vége Ha K<J akkor A[K]=A[J]; K=K+1 Ciklus amíg K<J és A[K]<=X K=K+1 Ciklus vége Ha K<J akkor A[J]=A[K]; J=J-1 Elágazás vége Ciklus vége A[K]=X X a helyére kerül Eljárás vége az eljárásban Dr. Hajnal Éva
50
Quicksort rendezés jellemzői • Rendezés stabilitása: Az azonos értékű elemek ugyanabban a sorrendben jelennek meg a kimeneti tömbben, ahogy a bemeneti tömbben szerepeltek. • Quicksort nem stabil rendezés • Keressünk példákat stabil rendezésekre! Programozási paradigmák és technikák
Dr. Hajnal Éva
51
Quicksort algoritmus időbonyolultsága • Legjobb eset:O(n*log(n)) • Legrosszabb eset:O(n2) • Átlagos eset:O(k*n*log(n)) n 1 10 100 1000
log2(n!) 0 21 524 8 526
Programozási paradigmák és technikák
"n*log(n) "n2" 0 1 33,21928 100 664,3856 10 000 9 965,784 1 000 000
Dr. Hajnal Éva
52
Quicksort iteratív algoritmusa veremmel 5
3
2
6
9
1
4
7
4
3
2
1
9
6
5
7
1
3
2
4
9
6
5
7
1
2
3
4
9
6
5
7
Verem: eleje, vége
1
2
4
7
0
0
Változók értékei:
Eleje
0
0
0
1
Vége
7
3
2
2
Közepe 3
2
0
2
Programozási paradigmák és technikák
Dr. Hajnal Éva
53
Gyorsrendezés iterációval verem segítségével lehet Quick(A,E,V) Verembe(0,0) Ciklus Ciklus Szétválogat(A,E,V,K) Ha V-K>1 akkor Verembe(K+1,V) V=K amíg V-E>0 Ciklus vége Veremből(E,V) Amíg E>0 Ciklus vége
Eljárás vége Programozási paradigmák és technikák
Dr. Hajnal Éva
54
Teszt • Készítsen rekurzív maximumkiválasztási algoritmust, és specifikációt! • Készítsen rekurzív megszámolási algoritmust és specifikációt!
Programozási paradigmák és technikák
Dr. Hajnal Éva
55
Objektum Orientált paradigma • A szoftver krízis a szoftverfejlesztés válsága, miszerint egy hagyományos módszer (strukturált programozás) már nem képes az igényeknek megfelelő, minőségi szoftver előállítására. • Cél: – – – – –
Olcsó Jó minőségű szoftver Szoftver elemek újrafelhasználhatósága Szoftver fejlesztés csapatmunkában (design és kód különválasztása)
Programozási paradigmák és technikák
Dr. Hajnal Éva
56
Objektum definíció • Elv: Legkisebb modul az objektum, melyben adatok és eljárások össze vannak zárva. • Objektumok jellemzője: – Egységbe zárás (Encapsulation) • Felelősség • Zártság • Osztályozás
– Polimorfizmus – Öröklődés – Futás alatti kötés Programozási paradigmák és technikák
Dr. Hajnal Éva
57
Előzmények • SIMULA67: Algol verzió , hajók modellezése objektumokkal • 1969 Alan Kay egyetemista szakdolgozata az objektum orientált programozásról. • 1970 Xerox Smalltalk az első tiszta objektumorientált nyelv • 80-as évek: OO paradigma általánosan elfogadottá vált Programozási paradigmák és technikák
Dr. Hajnal Éva
58
Objektum • Elv: Legkisebb modul az objektum, melyben adatok és eljárások össze vannak zárva. • Objektumok jellemzője: – Zártság : a mezők tárolják az információt, a metódusok kommunikálnak a külvilággal. Az osztály változóit csak a metódusokon keresztül változtathatjuk meg. – Felelősség – Polimorfizmus – Osztályozás – Öröklődés – Futás alatti kötés Programozási paradigmák és technikák
Dr. Hajnal Éva
59
UML feladata • Egységesített modellező nyelv • A program osztályainak és objektumainak megtervezését, és elemzését segítő modellező nyelv • Jogilag is szabványos jelölésrendszer • Grafikus nyelv, azaz a modellt diagramok segítségével ábrázolja • Alkalmazható a vállalatok közötti információcsere eszközeként • Nincs matematikailag bizonyítva a helyessége Programozási paradigmák és technikák
Dr. Hajnal Éva
60
UML Unified Modeling Language 1.0 1997.01.13. Rumbaugh Booch Jacobsen • Az Objektumorientált rendszer saját feladattal bíró, egymással kommunikáló objektumok összesége. – – – –
Felhasználói interfész Kontroll Implementáció objektum – konténer Információ hordozó
Programozási paradigmák és technikák
Dr. Hajnal Éva
61
Osztály fogalma • Az osztály: Névvel ellátott típus, ami az adattagokat és a rajtuk végzett műveleteket egységben kezeli. UML
adatta Class Kutya g { private int lábszám; private int kg; public int Ugat(paraméterek) {kód} } Metódus Felület: műveletek összesége Programozási paradigmák és technikák
Dr. Hajnal Éva
Osztály -lábszám int -kg int + Ugat()
62
Programnyelvek csoportosítása • Tiszta OO nyelv pl. C# - Programozás csak oo alapon képzelhető el. Minden komponens objektum. Feladat a saját osztályok elhelyezése a hierarchiában. • Hibrid nyelvek pl. Turbo Pascal, C++ kétféle paradigma mentén is elképzelhető a programozás. • Objektum alapú nyelvek pl. Programozási paradigmák és technikák
Dr. Hajnal Éva
63
Objektum • • • •
Az osztály példányosításával keletkezik Referencia típusú változó Kutya k=new Kutya(); Általában az Osztály nevét nagy kezdőbetűvel, az objektum nevét kis kezdőbetűvel írjuk
Programozási paradigmák és technikák
Dr. Hajnal Éva
64
Láthatóságok - Privát- „private” csakis az osztályon belül elérhető # Védett – „protected” hasonló mint a private, de a leszármazott osztályok módosíthatják + Nyilvános - „public” mindenki láthatja Zárt – „sealed” –Nem lehet örökítéssel továbbadni Belső – „internal” Védett, belső – „protected internal” Osztály szintű adat vagy metódus – „static” Programozási paradigmák és technikák
Dr. Hajnal Éva
65
Adattagok módosítói • const – értékadás deklarációkor – Minden példányban ugyanaz az értéke
• readonly – értékadás konstruktorban – Példányonként lehet más-más értéke
Programozási paradigmák és technikák
Dr. Hajnal Éva
66
Átdefiniálás (overloading) • Függvények túlterhelése • Ugyanolyan nevű, de különböző szignatúrájú függvényeket létrehozhatunk osztályon belül is.
Programozási paradigmák és technikák
Dr. Hajnal Éva
67
Konstruktor • kötött a neve –ugyanaz mint az osztály neve (C++, Java, C#) • nincs visszatérési típusa • fő feladata az objektum mezőinek inicializálása • végrehajtódik, mielőtt bármely metódus meghívódhatna • Túlterhelhető • Egyik konstruktor hívhatja a másikat • Másoló konstruktor Programozási paradigmák és technikák
Dr. Hajnal Éva
68
Destruktor • Ezen metódusok gondoskodnak arról, hogy az objektum használatának befejeztekor az objektum által lefoglalt erőforrások (memória, file- ok, háttértároló, csatolt eszközök, stb.) felszabadításra kerüljenek. • Destruktor neve ~jellel kezdődik, nincs visszatérési értéke és nincs paramétere, nincs hozzáférés módosítója • Nincs destruktor túlterhelés • A destruktorok meghívásának három módja lehet: – a. explicit módon (programozó által // desktruktor jelleg)dispose – b. implicit módon (objektum megszűnésekor (ref. számláló))null – c. automatikusan (objektum nincs már használatban (garbage collector = gc))referencia „elveszett”
Programozási paradigmák és technikák
Dr. Hajnal Éva
69
GC • A destruktor automatikus meghívásának a folyamatát szemétgyűjtési algoritmusnak nevezzük (garbage collection, GC). • A garbage collector az osztály Finalize függvényét hívja meg – a destruktor függvényt a fordító egy Finalize függvényre alakítja • Determinált destrukciós folyamatot az ún. Dispose metódus implementálásával 70 Programozási paradigmák és technikák Dr. Hajnal Éva oldhatjuk meg.
Szemétgyűjtő algoritmus • Nemdeterminisztikus • GC működésbe lép, ha a processzor kihasználtsága csökken • GC működésbe lép, ha a rendelkezésre álló memória lecsökken • GC működésbe lép, ha „hívjuk”. • A felszabadítás „sorban” történik Programozási paradigmák és technikák
Dr. Hajnal Éva
71
Dispose() használata bool disposed=false; … protected void Dispose( bool disposing ) { if( !disposed ) {if (disposing) {// ide jön az erőforrás felszabadító kód } this.disposed=true; // nem kell több hívás ha van ősosztály, akkor annak dispose hívása base.Dispose( disposing );//Ős destruktor hívása GC.SupressFinalize(this);///GC kikapcsolása } Programozási paradigmák és technikák Dr. Hajnal Éva }
72
Tanács • C#: Általában szükséges minden általunk létrehozott osztályhoz konstruktort/kat definiálni. • C#: Általában nem szükséges desktruktort definiálni, megelégedhetünk az alapértelmezettel.
Programozási paradigmák és technikák
Dr. Hajnal Éva
73
Tulajdonság public int X { get { return x; } set { this.x = value; } } • Tulajdonság egy speciális függvény • Nincs paramétere • Használata értékadás formájú • Set és get blokk • Speciális változó value • Figyelem X!=x • Privát adattagok hozzáférhetők biztonságos módon • Csak írható, csak olvasható tulajdonságok beállíthatók
Programozási paradigmák és technikák
Dr. Hajnal Éva
74
Felbontott típusok (partial types) //file1.cs partial class PClass { public PClass() { }
?
Hol találkozhatunk
felbontott típusokkal
} //file2.cs partial class PClass { public void…. } Programozási paradigmák és technikák
Dr. Hajnal Éva
75
Beágyazott osztályok • Egy osztály tartalmazhat más osztályokat is. • A beágyazott osztály hozzáfér az őt tartalmazó osztály minden adatához. • Úgy viselkedik, mint egy lokális változó • Pl. form és a rajta levő vezérlők class Outer {private class Inner //a beágyazott osztály nem látható { } } class Outer //de most már igen {public class Inner {} } Outer.Inner innerClass = new Outer.Inner(); //pélányosítás
Programozási paradigmák és technikák
Dr. Hajnal Éva
76
Fogalmak • • • • • • • • • •
Osztály Objektum Attributum Metódus Példányosítás Inicializálás Felület Tulajdonság Konstruktor Destruktor Programozási paradigmák és technikák
Dr. Hajnal Éva
77
Tanácsok • Ha egy programelem önálló értelmezéssel, feladattal, tulajdonságokkal rendelkezik, akkor definiáljuk ezt az elemet önálló osztályként. • Ha egy programrész adata önálló objektumként értelmezhető, akkor definiáljuk őt a kívánt osztálytípus objektumaként. • Ha két osztály közös tulajdonságokkal rendelkezik, akkor használjuk az öröklés lehetőségét. • Általában is elmondható, hogy ha a programokban az osztályok közös vonásokkal rendelkeznek, akkor törekedni kell univerzális bázisosztály létrehozására. Gyakran ezt absztrakt bázisosztálynak is nevezzük. • Az osztályok definiálásakor kerüljük a „nyitott” (publikus) adatmezők használatát. 78 Programozási paradigmák és technikák
Dr. Hajnal Éva
Öröklődés - Inheritance • Egy, már létező típust terjeszthetünk ki, vagy bővíthetjük tetszőleges szolgáltatással. • Az eredeti osztályt ősosztálynak nevezzük (szülő – base class) • Az továbbfejlesztett osztályt származtatott osztálynak (gyerek – derived class) • Egy ősből több származtatott osztályt készíthetünk (C++) vagy, • Egy származtatott osztálynak egy őse van (C#), viszont lehetőség van interfész definiálásra. Programozási paradigmák és technikák
Dr. Hajnal Éva
79
Öröklés példa class utódnév: ősnév { // … }
Programozási paradigmák és technikák
ősnév
utódnév
Dr. Hajnal Éva
80
class ős { private int i; // privát mező protected int j; // protected mezőtag public int k; // publikus mezők public void f(int j) { i=j; }; } class utód: ős { … }; Programozási paradigmák és technikák
Dr. Hajnal Éva
81
Öröklés típusai • Más programnyelvben: public, protected, privát – csak szűkíteni lehet a láthatóságot! • C# - csak publikus öröklés, a mezők változatlan láthatósággal adódnak tovább
Programozási paradigmák és technikák
Dr. Hajnal Éva
82
Konstruktor, destruktor végrehajtási sorrendje • Konstruktor nem öröklődik, hanem hívódik • Ős. konstruktor() // ha nincs direkt őskonstruktor hívás (base) • Utód.konstruktor • … • Utód.destruktor • Ős.destruktor • Paraméteres konstruktor hívása: utod(paraméterek):base(paraméterek) { Programozási } paradigmák és technikák Dr. Hajnal Éva
83
Lezárt osztály Sealed kulcsszó • Megtiltjuk, hogy új osztályt származtassunk belőle (public sealed class kutya:allat) • Lezárt függvény - nem lehet a későbbiekben átdefiniálni public sealed override void eat(){} Programozási paradigmák és technikák
Dr. Hajnal Éva
84
„Zárt osztály” – nem lehet belőle leszármaztatni
sealed class végleges { public végleges() { Console.WriteLine( "A konstruktor" ); } class utód:végleges // fordítási hiba { } Programozási paradigmák és technikák Dr. Hajnal Éva
85
Korai kötés • A példányváltozó típusa fordítási időben rögzül • Metódustábla e=m; e.kiir(); //Mi történik? m.kiir(); //?? A döntést a fordító még akkor meghozza, amikor a „class elso” osztályt fordítja le. A döntést később már nem másíthatja meg, hiába definiáljuk felül a visszaad metódust. Programozási paradigmák és technikák
Dr. Hajnal Éva
86
Korai kötés • A példányváltozó típusa fordítási időben rögzül • Metódustábla • E e=new E(); H h=new H(); • E ős és H az utód, vagy H ős és E az utód? e=h; e.kiir(); //Mi történik? h.kiir() Programozási paradigmák és technikák Dr. Hajnal Éva
87
Késői kötés • Az OOP viselkedését, hogy egy metódus belsejében szereplő másik metódushívás másmás viselkedést mutat (más-más tényleges eljárás hívás történik a futtatás során) – sokalakúságnak, polimorfizmusnak nevezzük. • A példányváltozó típusa futás alatt változhat – virtual-override – new - sealed
Programozási paradigmák és technikák
Dr. Hajnal Éva
88
Késői kötés • A példányváltozó típusa futás alatt változhat • Virtuális metódus tábla – virtual-override – sealed-new
http://www.scribd.com/doc/26458586/Programozas-Cnyelven
Programozási paradigmák és technikák
Dr. Hajnal Éva
89
Késői kötés class elso { public virtual int visszaad() { return 1; } public void kiir() { System.Console.WriteLine("Érték={0}", visszaad()); } } class masodik:elso { override public int visszaad() { return 2; } } Elso a=new elso(); Mi kerül a képernyőre? masodik b = new masodik(); a.kiir(); b.kiir();
Programozási paradigmák és technikák
Dr. Hajnal Éva
90
Típuskonverzió • Típus lekérdezése object.GetType() • Is és as – Típusazonosság lekérdezéséhez (is) if (a is object) – Típuskonverzióhoz (as) referenciatípusnál
• Castolás (Button)sender – Pl. (sender as Button) referencia és érték típusnál object
Button
Programozási paradigmák és technikák
Dr. Hajnal Éva
91
Absztrakt osztály – megköveteljük, hogy a leszármazott osztály implementálja a metódust abstract class os {private int e;… public abstract int szamol();} class szamolo:os { public szamolo():base(3) {…} public override int szamol() {} Dr. Hajnal Éva } Programozási paradigmák és technikák
92
TESZT
Mit csinál az alábbi program?
public new void Close() { i++; this.Text = i.ToString(); System.Threading.Thread.Sleep(5000); if (i < 5) Close(); else { MessageBox.Show("Most zárom!"); base.Close(); } } private void button1_Click(object sender, EventArgs e) { this.Close(); } Programozási paradigmák és technikák
Dr. Hajnal Éva
93
Öröklődés - Adattagok • A származtatott osztály Tartalmazza (örökli) a public mezőket és fel is használhatja • Tartalmazza (örökli) a protected mezőket és fel is használhatja • Tartalmazza a private mezőket, a memóriaigénybe beszámít, de nem használhatja azokat. De!! Az örökölt metódusok használhatják a privát mezőket. Programozási paradigmák és technikák
Dr. Hajnal Éva
94
Példa class TPont{ private int x,y; public void Balra_tol(){if(x>0) x--;} … }
class Tkor:Tpont{ public void KorBalratol(){ Balra_tol(); //működik? X--; }
//működik??
} Programozási paradigmák és technikák
Dr. Hajnal Éva
95
Új adatok a származtatott osztályban class elso {private int x; protected int y; public int z; } class masodik:elso { int x; //?? int y; //?? int z; //?? } Programozási paradigmák és technikák
vagy class masodik:elso { int x; //?? new int y; //?? new int z; //?? } • new kulcsszóval jelezzük a fordítóprogramnak: szándékos átdefiniálás! Dr. Hajnal Éva
96
Örökölt mezők II. • Nem lehetséges a típus megváltoztatása • De new kulcsszóval újra bevezethetjük. • Átdefiniálással a mezők hatáskörét változtatjuk meg. Az örökölt mezők hatásköre az ősosztály, az átdefiniált az utódra vonatkozik. class elso {private int x; protected int y; Public int z; } Class masodik:elso { int x; new float y; new double z; }
Régi mezők elérése minősített
//?? //?? //??
Programozási paradigmák és technikák
névvel:
… new float z; Public akarmi() { z=1.1; //float elso.z=1; //örökölt z }
Dr. Hajnal Éva
97
Öröklődés - metódusok class elso { public int visszaad() { return 1;} public void kiir() { System.Console.WriteLine(„érték:{0}”, visszaad()) } } class masodik:elso Mi kerül a képernyőre? 1 v 2 { new public int visszaad(){return2;} } Class Test { Static void Main(){ Masodik a=new masodik(); a.kiir(); } } Programozási paradigmák és technikák
Dr. Hajnal Éva
98
Örökölt metódusok II. • A gyerekosztályban lehet ugyanolyan nevű metódust létrehozni • Ha a paraméterezése ugyanaz, használni kell a new kulcsszót • Ha a szignatúra nem ugyanaz akkor nem kell a new (overloading) • Az új metódust az ős osztály metódusai nem látják Programozási paradigmák és technikák
Dr. Hajnal Éva
99
Virtuális Metódus Tábla (VMT) • Késői kötésre csak a virtuális metódusok meghívásakor kerülhet sor. • Ilyenkor a fordító nem egy konkrét eljáráshívást fordít le, hanem egy utasítássorozatot, amely futás közben egy keresést hajt végre, hogy meghatározza, melyik metódusverziót kell konkrétan meghívni. (az elérhető legfrissebbet) • A nyilvántartást végzi a VMT • A táblázatban a metódusok indításához szükséges információk vannak eltárolva (pl. a metódusok memóriacímei, amely alapján azokat el lehet indítani) • Mindig egy osztályhoz tartozik VMT Algoritmus 1. Induláskor megegyezik az ős VMT-jével. 2. Virtual kulcsszóval bevezetett metódusok bekerülnek a VMT-be (a végére) 3. Ha override kulcsszóval felüldefiniáltunk egy létező virtuális metódust, akkor a VMT bejegyzés kicserélődik az új metódusra. 100 Programozási paradigmák és technikák
Dr. Hajnal Éva
VMT Class elso VMT Int visszaad()
Elso.visszaad()
Void kiir()
Elso.kiir()
Class masodik VMT Int visszaad()
Masodik.visszaad()
Void kiir()
Elso.kiir()
• Előny: – A késői kötést feloldó programkód rövid, egyszerű, gyors
• Hátrány – VMT tábla készítése – fordítási idő – A példányokhoz a VMT táblát hozzá kell rendelni - futási időben a konstruktor – Memóriaigény Programozási paradigmák és technikák
Dr. Hajnal Éva
101
class elso { public virtual int metodus_ a() { ... } public virtual int metodus_ d() { ... } public void metodus_ c() { metodus_ a(); } } class masodik: elso { public override int metodus_ a() { ... } public virtual int metodus_ b() { ... } } class elso VMT. Int metodus_ a() elso. metodus_ a Int metodus_ d() elso. metodus_ d class masodik VMT Int metodus_ a() masodik. metodus_ a Int metodus_ d() elso. metodus_ d Int metodus_ b() masodik. metodus_ b Programozási paradigmák és technikák
Dr. Hajnal Éva
102
• A késői kötés fordítása során olyan programkód kerül fordításra, amely a VMT táblázat alapján hozza meg a döntést, hogy melyik konkrét metódust kell meghívni. • Az „e.metodus_c()” esetén az „e” példányhoz az „class elso” VMT tábla tartozik, hiszen az „e” példány az „elso” osztály egy példánya! Ezért a késői kötés a „class elso” VMT tábla szerint a „metodus_a()” hívás esetén az elso.metodus_a()” metódust kell meghívni. • A „m.metodus_c()” esetén az „m” példányhoz az „class masodik” VMT tábla tartozik, hiszen az „m” példány az „masodik” osztály egy példánya! Ezért a késői kötés a „class masodik” VMT tábla szerint a „metodus_a()” hívás esetén a „masodik.metodus_a()” metódust kell meghívni. Programozási paradigmák és technikák
Dr. Hajnal Éva
103
Dinamikus Metódus Tábla • A szerepe megfelel a VMT-nek (késői kötés feloldását támogatni) • Kevesebb memóriaigénye van, mint a VMT-nek • Lassúbb a kezelése Felépítése: – – – –
Hasonló, mint a VMT Osztályhoz van hozzárendelve A DMT induláskor üres Ha az osztályban bevezetünk egy új virtuális metódust a „virtual” kulcsszóval, akkor ezen metódus bekerül a táblázatba (a végére) – Ha az osztályban felüldefiniáltunk egy már létező virtuális metódust az „override” kulcsszóval, akkor ez is bekerül a táblázatba 104
Programozási paradigmák és technikák
Dr. Hajnal Éva
Virtualitás újrakezdése • New virtual kulcsszavakkal ellátott metódus lesz az új metódussorozat gyökere. A fordító új sor kezd, amikor felépíti a VMT táblát.
Programozási paradigmák és technikák
Dr. Hajnal Éva
105
Absztrakt osztály • Az absztrakt osztály létrehozásának célja az, hogy közös felületet biztosítsunk a leszármazottainak. – Abstrakt osztályt nem lehet példányosítani – Absztrakt metódusnak nem lehet definíciója – Leszármazottnak definiálni kell az öröklött absztrakt metódusokat
Abstract class Animal {abstract public void eat();} Class dog:Animal {Animal(){} Public override void eat() {Console.WriteLine(„Kutya eszik”); }} Programozási paradigmák és technikák
Dr. Hajnal Éva
106
TESZT public class Dimensions { public const double PI = Math.PI; protected double x, y; public Dimensions() { } public Dimensions(double x, double y) { this.x = x; this.y = y; }
}
public virtual double Area() { return x * y; }
public class Circle : Dimensions { public Circle(double r) : base(r, 0) { }
}
public override double Area() { return PI * x * x; }
Programozási paradigmák és technikák
Dr. Hajnal Éva
107
Interfész definiálása
• Igény: Általánosabb leírás érdekében ne egy osztály keretében fogalmazzuk meg a leírást, hanem kisebb tulajdonságcsoportokat fogjunk össze • Az interface nem tartalmaz konkrétumot, hanem a kívánt előírásokat tartalmazza (nincs függvény definíció) • Megegyezés szerint I-vel kezdődik a nevük • Interface előírásai közé: függvények, tulajdonságok, indexer megadása is beletartozhat • Interface-nek megadhatunk láthatóságot, az adattagokra is ez a láthatóság vonatkozik Módosító interface név { //deklarációs fejlécek
} Programozási paradigmák és technikák
Dr. Hajnal Éva
108
Interface használata • Class osztálynév: implementálandó név • Pl. class jonatan:IAlma { Private int kor; …. } • Ha egy osztályból másik osztályt származtatunk, ami megvalósít interfészeket is, Class jonatan:gyumolcs,Ialma,… { } Programozási paradigmák és technikák
Dr. Hajnal Éva
109
Interface kompozíció
• Az interface egységek tervezésekor lehetőség van egy vagy több már meglevő interface felhasználásával ezekből újabbat definiálni. Public interface Ialma { Bool nyári(); Double termésátlag(); } Public interface Iszállítható { Bool szállit(); } Public interface szállítható_alma:Ialma,Iszállítható { String csomagolás_módja(); }
Programozási paradigmák és technikák
Dr. Hajnal Éva
110
Típuskonverzió • A definiált új típusra vonatkozóan használhatjuk mind az is mind az as operátort. If (j is IALMA) Console.WriteLine(„Ez alma volt!”); Ialma a=j as Ialma; //Ialma típusra konvertálás a.termesatlag(); Implicit konverzió: Ialma ia=new jonatan(); // működik, ahogy az osztályoknál is Explicit konverzió: MyClass mc=new Myclass(); Ione iface=(Ione)mc;
Programozási paradigmák és technikák
Dr. Hajnal Éva
111
foreach Olyan ciklus ami végigiterál egy tömbön, gyűjteményen ill. minden olyan objektumon ami megvalósítja az Ienumerable és Ienumerator intefészeket. Foreach(int x in a) { Console.WriteLine(x); } Programozási paradigmák és technikák
Dr. Hajnal Éva
112
Iterátor példa public class Animal { private string name; public Animal(string _name){} public Name { get{return this.name;}}} public class AnimalContainer:IEnumerable,IEnumerator { private Animal[] container=new Animal[10]; private int currPosition=-1; public AnimalContainer() {container[0]=new Animal(„Rex”);… …//MoveNext, Current,Reset, Ienumerator GetEnumerator() Foreach(Animal a in ac){ } Programozási paradigmák és technikák
Dr. Hajnal Éva
113
Index függvény • Az indexer függvény definiálása a vektorhasználat és a tulajdonság függvény kombinációja. – Paraméter: index – Neve: this
• Az aktuális példányt indexeli, soha nem lehet statikus class valami {int [] v=new int[10]; Public int this[int i] {get {return v[i];} set{v[i]=value;}}} //Main Valami a=new valami(); A[2]=5; Console.WriteLine(a[2]);}}
Programozási paradigmák és technikák
Dr. Hajnal Éva
114
Indexer és a vektor különbsége • Az indexer függvény, paramétere nem csak egész lehet • Az indexer átdefiniálható (overloading)
Programozási paradigmák és technikák
Dr. Hajnal Éva
115
Kivételkezelés • Programrész végrehajtása eredményesség szempontjából – Semmilyen rendellenesség nincs – Programrész paraméterei nem teljesítik az előírásainkat, hibás végrehajtás – Előre nem látható hibajelenség lép fel.
• Az előre nem megjósolható hiba kivételt (exception) okoz, ezeknek a programkódban történő kezelése a kivételkezelés (exception handling). • A kivétel kezelés elegáns megoldás, ami futási időben biztosítja a hibák kezelését. • A C# kivételkezelés az aszinkron kivételek kezelését nem támogatja (hardver megszakítások…) Programozási paradigmák és technikák
Dr. Hajnal Éva
116
Kivételkezelés használata • • • • •
Alapszavak try mely után a kritikus programrész következik catch ha probléma van, mit kell csinálni throw kifejezés, kivételkezelés átadása (dobás) finally a kritikus blokk végén biztosan végrehajtódik try
{
… } Catch (típus[név]) { .. } Finally
{
… } Programozási paradigmák és technikák
Dr. Hajnal Éva
117
Kivétel dobása • Nemcsak a keretrendszer generálhat kivételt, hanem maga a programozó is. • Chacked és unchecked • Throw • A dobott kivételt példányosítani kell! • Kivételkezelések egymásba ágyazhatók • A kivétel a következő catch-nek, vagy a keretrendszer kivételkezelőjének továbbadható (throw paraméter nélkül). Programozási paradigmák és technikák
Dr. Hajnal Éva
118
Kivétel elkapása • A try blokkot követheti legalább egy catch • Ha nincs catch, vagy a catch blokk típusa nem egyezik a keletkezett kivétellel, akkor a keretrendszer kivételkezelő felügyelete veszi át a vezérlést • A catch típusa az Exception osztálytípus vagy ennek utóda lehet. • Saját típust is lehet az Exception osztályból származtatni Programozási paradigmák és technikák
Dr. Hajnal Éva
119
Saját hibatípus definiálása • Az öröklődés lehetőségét kihasználhatjuk az egyes hiba lehetőségek szétválasztására. • HibaIndexhiba vigyázni kell a hibakezelő paraméterezésére • A catch blokkokat az öröklődés fordított sorrendjében kell definiálni!!!! public class Hiba:Exception {public Hiba():base(){ } public Hiba(string s):base(s) { } } Public class IndexHiba:Hiba { public IndexHiba():base() { } public IndexHiba(string s):base(s){ } } Programozási paradigmák és technikák
Dr. Hajnal Éva
120
Kivételek egymásba ágyazása • A catch blokkokat az öröklődés fordított sorrendjében kell definiálni!!!!
Programozási paradigmák és technikák
Dr. Hajnal Éva
121
Kivételosztályok System.Object
System.Exception
System.SystemException
System.ArgumentException
System.ArgumentNullException
System.ArgumentOutOfRangeException
System.ArithmeticException
System.DivideByZeroException
System.OverflowException
System.FormatException
System.IndexOutOfRangeException
System.IO.IOException
System.NotImplementedException
System.NullReferenceException
System.ApplicationException
J.Zs.Cs.: Vizuális programozás (c) 2010
122
Felkészülés többfajta kivétel kezelésére • Minden hibatípushoz külön catch blokk • Közös catch blokk általánosabb kivételosztállyal
• Általános catch blokk
J.Zs.Cs.: Vizuális programozás (c) 2010
123
Kivétel továbbadása - A finally blokk használata
J.Zs.Cs.: Vizuális programozás (c) 2010
124
Kivételek előidézése if (perc < 1 || perc >= 60) { throw new InvalidTimeException(perc + " érvénytelen percérték"); // !! ide már nem jut el a vezérlés !! }
J.Zs.Cs.: Vizuális programozás (c) 2010
125
Aritmetikai túlcsordulás • alapértelmezés szerint nincs ellenőrizve • programban utasításra checked { int szam = int.MaxValue; Console.WriteLine(++szam); // OverflowException } unchecked { int szam = int.MaxValue; Console.WriteLine(++szam); //-2147483648 } • programban kifejezésre: (checked(++szam)) J.Zs.Cs.: Vizuális programozás (c) 2010
126
using használata • Akkor használhatjuk, ha az osztály megvalósítja az IDisposable felületet (interfészt) • Érdemes használni, ha az osztálynak maradhatnak lezáratlan erőforrásai. using(StreamReader sr=new StreamReader(„szoveg.txt”)) { … }
Programozási paradigmák és technikák
try { StreamReader sr=new StreamReader(„szoveg.txt”); … } finally { sr.Close(); } Dr. Hajnal Éva
127
Generikus függvények • A kód újra felhasználás egyik módszere, osztály, interface vagy metódus általános formában • T(Template) az aktuális típus, generikus paraméter • Felhasználáskor a fordító felismeri, hogy melyik típust használjuk,vagy megadhatjuk explicit módon • A C# a specializált metódusokat futási időben készíti el. • A fordító formailag ellenőriz, és csak a biztonságosan végrehajtható függvényeket fogadja el. static public void Swap
(ref T x, ref T y) {
T tmp=x; x=y; y=tmp;
} Programozási paradigmák és technikák
Dr. Hajnal Éva
128
Generikus osztályok • Általános definíció – object típusú adattagok vagy paraméterek, mert az object minden objektum őse • Generikus osztály class Tomb { T[] t; public Tomb(int meret) { t=new T[meret] }…}
Programozási paradigmák és technikák
Dr. Hajnal Éva
129
Generikus osztály jellemzői • Nem kasztolhatók az őstípusra (cast!) • Generikus megszorítások – Típus szűkítése where kulcsszóval – Szűkítés: alaposztály, interface, osztály, new(), U – Az osztály csak akkor példányosítható, ha a megadott típusra igaz a feltétel class NewClass where T:BaseClass, IFace, new() { } Programozási paradigmák és technikák
Dr. Hajnal Éva
130
Generikus gyűjtemények • System.Collections.Generic névtérben találhatóak – List, SortedList, LinkedList – HashSet – SortedList – Dictionary, SortedDictionary – Stack, Queue
• Generikus interfészek – Pl. IEnumerable és IEnumerator segítségével lehet megvalósítani a generikus osztályokban metódusokat Programozási paradigmák és technikák
Dr. Hajnal Éva
131
ZH 04.02 • • • •
50% elmélet 50% feladat megoldás Elmélet: Függvények, rekurzió:órai vázlatok, kiadott prezentációk • Objektumorientált programozás: órai vázlatok, kiadott prezentációk, C#.pdf 54.o-117.o • Tanulás papír, toll Programozási paradigmák és technikák
Dr. Hajnal Éva
132
TESZT
C# programozás állásinterjú kérdések Tegnap volt szerencsém egy hazánkban is fejlesztőket foglalkoztató multi állásinterjúkon alkalmazott C# tesztsorával egészen közelről megismerkedni. 12 papíron megválaszolandó kérdés, a szintidő 40 perc. Meg tudod oldani? A teszt eredetileg angol, a fordítás tőlem származik. 1. Mire jó a new kulcsszó? 3. Nevezzen meg négy hozzáférés módosítót (access modifier) és magyarázza meg a jelentésüket! Van-e ötödik? 4. Mi a különbség az absztrakt osztály és az interfész között elsősorban implementáció és öröklés szempontjából? 5. Írjon kódot, amelyben: Definiál egy IDoSomething interfészt egy f() metódussal. Definiál egy IDoSomethingElse interfészt egy f() és egy g() metódussal. Készítsen egy osztályt, amelyikben implementálja az IDoSomething és az IDoSomethingElse interfészeket úgy, hogy mindegyik metódus kiírja a konzolra a az interfész és a metódus nevét. Készítsen egy példányt az osztályból és hívja meg a metódusait. 6. Nevezzen meg legalább négy különbséget az érték típus és a referencia típus között! 8. Írja le, hogyan működik a szemétgyűjtő (garbage collector)! Programozási paradigmák és technikák
Dr. Hajnal Éva
133
12. Mit ír ki: { class Base { public Base() { Console.WriteLine( "Base()" ); } static Base() { Console.WriteLine( "static Base()" ); } } class Child : Base { public Child() { Console.WriteLine( "Child()" ); } static Child() { Console.WriteLine( "static Child()" ); } } class Program { static void Main( string[] args ) { Child b = new Child(); } } }
Programozási paradigmák és technikák
Dr. Hajnal Éva
134
Operátor átdefiniálás (overloading) • Az értékadás = és az index [ ] operátor nem újradefiniálható • Újradefiniálható: Egyoperandusú: + - ! ~ ++ -- true false Kétoperandusú: + - * / % & | ^ << >><= >= == != < > • Típuskonverziós függvény definiálható
Programozási paradigmák és technikák
Dr. Hajnal Éva
135
Operátor átdefiniálás • Precedencia nem változtatható • Operandusok száma nem változtatható Static visszatérési_érték operator?(argumentum) { //függvénytörzs }
Programozási paradigmák és technikák
Dr. Hajnal Éva
136
Példa: + komplex számhoz egész hozzáadása Public static komplex operator+(komplex k, int a) { komplex y=new komplex(0,0); y.Re=a+k.Re; y.Im=k.Im; return y; } y=4+k;
//(y és k komplex) ???
Programozási paradigmák és technikák
Dr. Hajnal Éva
137
Implicit konverziós operátor • Implicit konvrzió: a forráskódban nem jelöljük a konverzió műveletét • Pl. k=4+y; //intkomplex konverzió public static implicit operator komplex(int a) { komplex y=new komplex(0,0); y.Re=a; return y; } Programozási paradigmák és technikák
Dr. Hajnal Éva
138
Explicit konverziós operator public static explicit operator komplex(int a) { komplex y=new komplex(0,0); y.Re=a; //lehetne a kód más mint az implicit konverziónál return y; }
• Explicit konverzió: konverzió a forráskódban is jelölve van • Pl. komplex k=(komplex) 5; Programozási paradigmák és technikák
Dr. Hajnal Éva
139
++ operator újradefiniálása Public static komplex operator++(komplex a) { a.Re=a.Re+1; a.Im=a.Im+1; Return a; }
K++; vagy ++K; //???
Programozási paradigmák és technikák
Dr. Hajnal Éva
140
True, false definiálása • Megkötés: mindkettőt egyszerre újra kell definiálni public static bool operator true(komplex x) { return x.Re>0; } public static bool operator false(komplex x) { return x.Re<=0; } Programozási paradigmák és technikák
Dr. Hajnal Éva
141
Párban újradefiniálható operátorok • • • •
==, != <,> <=, >= True, false
Programozási paradigmák és technikák
Dr. Hajnal Éva
142
Main függvény paraméterei • Ha a programot paraméterekkel indítjuk a parancssorból (pl. type autorun.inf), a paramétereket parancssor argumentumoknak nevezzük • Indításkor a Main függvény az operációs rendszertől átveszi a vezérlést • Main függvénynek 1 paramétere van, egy string tömb (args) Programozási paradigmák és technikák
Dr. Hajnal Éva
143
Main paraméterei (példa) static void Main(string[ ] args) { int i=0; while (i<args.Length) { Consol. WriteLine(args[i]); i++; } { -------------------------------------------------------C:\parancs.exe Kellemes húsvéti ünnepeket! Project/Properties/Configuration Properties/Debugging/Command Line Arguments
Programozási paradigmák és technikák
Dr. Hajnal Éva
144
•
Függvények változó számú paraméterrel Ha nem tudjuk a függvény készítésekor, hogy hány
paramétere lesz a függvénynek, a params kulcsszóval egy vektorparamétert definiálunk. public static void intparaméterek(params int[] list) { for(int i=0;i<list.Length;i++) Console.WriteLine(list[i]); Console.WriteLine(); ? Ha különböző típusú } paramétert szeretnénk Hívása: átadni? intparaméterek(1,2,3,4); int[] myarray=new int[3]{10,11,12}; intparaméterek(myarray); Programozási paradigmák és technikák
Dr. Hajnal Éva
145
Függvények változó és fix paraméterrel • A fixen megadott paramétereknek kötelezően meg kell előzni a változó paramétereket. public static void valtozo(int x, params object[] list) { Console.WriteLine(x); foreach (object o in list) Console.WriteLine(o); } //Main valtozo(20,”alma”,”barack”); Programozási paradigmák és technikák
Dr. Hajnal Éva
146
Delegáltak - Metódusreferencia • Feladat: egy menüponthoz függvényhívást rendelni • Megoldás: – Hagyományos C vagy C++ programban a függvénymutató segítségével lehet – C#-ban a mutatók használata nem engedélyezett – delegált
• A delegált egy függvénytípus-definíció • Mindig a fogadó osztályban kell elhelyezni! delegate típus delegáltnév(típus paraméternév,…); Programozási paradigmák és technikák
Dr. Hajnal Éva
147
Delegált példa
Public static int negyzet(int i)
//statikus
függvény
{ Console.Writeline(„A négyzet területe:”); return i*i; } delegate int pelda(int x); delegált def.hiányzik a kódblokk //
Használata: pelda f=new pelda(negyzet); Console.WriteLine(f(5)); Vagy Pelda f=negyzet; int result=f(5); Programozási paradigmák és technikák
Dr. Hajnal Éva
Mi az eredmény?
148
Delegált visszatérési értéke • Ha a visszatérési érték void, akkor egy delegált több végrehajtandó függvényt tud meghívni (multicast – összetett delegált) • Ha a visszatérési érték nem void, akkor egy delegált csak egy végrehajtandó függvényt tud meghívni (single cast – egyszerű delegált) MyDelegate d=MethodOne; d+=MethodTwo; d(); Programozási paradigmák és technikák
Dr. Hajnal Éva
149
Windows alkalmazás - eseménykezelés
• Button1.click – delegált függvény • System.EventHandler - eseménykezelő this.button1.Click += new System.EventHandler(this.button1_Click);
Programozási paradigmák és technikák
Dr. Hajnal Éva
150
Eseménykezelés • Esemény (event): az osztály saját állapota megváltozásáról értesít más osztályokat • A „megfigyelő” osztály feliratkozik a „megfigyelt” osztály eseményére – eseménykezelő metódus • Az esemény megtörténtekor ezek a metódusok futnak le (speciális delegate)
Programozási paradigmák és technikák
Dr. Hajnal Éva
151
public delegate void LenyomásEseményKezelo(); class Gomb {public event LenyomásEseményKezelo EseményKezelo; public void Lenyomás() { { for (int i = 0; i < 10; i++) ; Random vél = new Random(); if (vél.Next(100) <= 50 && EseményKezelı != null) EseményKezelı(); } } } Programozási paradigmák és technikák
class Program { void GombKattintásKezelı() {Console.WriteLine("Itt történt vmi!");} void run() { Gomb obj = new Gomb(); obj.EseményKezelı+= new LenyomásEseményKezelı(GombKattintásKe zelı); obj.Lenyomás(); } static void Main(string[] args) { new Program().run(); } }
Dr. Hajnal Éva
152
Dinamikus memóriakezelés • Segédeszközei: mutatók (pointer) – unsafe módban • C# arraylist – Object típusú elemeket tárol - típuskonverzió az elemeire hivatkozásnál – Változó elemszámú tömböt kezel – Alapértelmezett kapacitása 16, ha betelik, akkor 16-ként növeli a kapacitást. – System.Collections névtér tartalmazza ArrayList list=new ArrayList(); //nem kell megadni az elemszámot For(int i=0;i<10;i++) list.Add(i); if (list.Count>4) //elemszám lekérdezése int x=(int)list[4]; //explicit konverzió Programozási paradigmák és technikák
Dr. Hajnal Éva
153
Adatszerkezet Az adatszerkezet az adatelemek egy olyan véges halmaza, amelyben az adatelemek között szerkezeti összefüggések vannak. Az összekapcsolódás módja határozza meg az elemek egymáshoz való viszonyát, illetve azokat a műveleteket, amelyeket rajta végezhetünk. (Adatelem az a legkisebb adategység, amelyre hivatkozni lehet. ) Programozási paradigmák és technikák
Dr. Hajnal Éva
154
Matematikai adatszerkezet rendezett pár, ahol – A: adatelemek halmaza – R: az A halmazon értelmezett valamilyen reláció
• A matematikai adatszerkezetek az R reláció bonyolultsága alapján csoportosíthatók Programozási paradigmák és technikák
Dr. Hajnal Éva
155
Az adatszerkezetek osztályozása Szerkezet szerinti csoportosítás I. Homogén adatszerkezetek (Azonos típusú adatelemekből épül fel)
• I.A Struktúra nélküli adatszerkezet – Az egyes adatelemek között nincs kapcsolat. Nem beszélhetünk az elemek sorrendjéről.
Programozási paradigmák és technikák
Dr. Hajnal Éva
156
Az adatszerkezetek osztályozása Szerkezet szerinti csoportosítás • I. B Asszociatív adatszerkezet – Az adatelemek között lényegi kapcsolat nincs. Ez az adatszerkezet valamilyen közös tulajdonság alapján összeállított halmaz, amelyekből részismérvek alapján részhalmazokat választhatunk ki. Az adatszerkezet elemei tartalmuk alapján címezhetők. pl.: tömb, ritka mátrixok, táblák. • Közvetlen elérésű • Véletlen elérésű
Programozási paradigmák és technikák
Dr. Hajnal Éva
157
Az adatszerkezetek osztályozása Szerkezet szerinti csoportosítás • I. C Szekvenciális adatszerkezetek – A szekvenciális adatszerkezet olyan rendezett pár amelynél az R reláció tranzitív lezártja teljes rendezési reláció – Szekvenciális adatszerkezetben az egyes adatelemek egymás után helyezkednek el. Az adatok között egyegy jellegű a kapcsolat: minden adatelem csak egy helyről érhető el és az adott elemről csak egy másik látható. Pl. egyszerű lista
Programozási paradigmák és technikák
Dr. Hajnal Éva
158
Az adatszerkezetek osztályozása Szerkezet szerinti csoportosítás • I.D Hierarchikus adatszerkezetek – A hierarchikus adatszerkezet olyan rendezett pár, amelynél van egy kitüntetett elem a gyökérelem úgy, hogy – A gyökér nem lehet végpont Bármely gyökértől különböző elem egyszer és csak egyszer lehet végpont Bármely gyökértől különböző elem a gyökértől elérhető – A hierarchikus adatszerkezeteknél az adatelemek között egy-sok jellegű kapcsolat áll fenn. Minden adatelem csak egy helyről érhető el, de egy adott elemből tetszés szerinti számú adatelem látható. Pl. fa, összetett lista Programozási paradigmák és technikák
Dr. Hajnal Éva
159
Az adatszerkezetek osztályozása Szerkezet szerinti csoportosítás • I.E Hálós adatszerkezetek – A hálós adatszerkezet olyan rendezett pár, amelynél az R relációra semmilyen kikötés nincs. – A hálós adatszerkezetek adatelemei között a kapcsolat sok-sok jellegű: bármelyik adatelemre több helyről is eljuthatunk, és bármelyik adatelemtől elvileg több irányban is mehetünk tovább. – Pl. gráf, irányított gráf
Programozási paradigmák és technikák
Dr. Hajnal Éva
160
II. Heterogén adatszerkezetek • Különböző típusú adatokból épül fel. • pl.: Record
Programozási paradigmák és technikák
Dr. Hajnal Éva
161
Memóriában történő helyfoglalás szerinti csoportosítás • I. Statikus adatszerkezetek – Véges számú adatelemből épül fel és ezek csak értéküket változtathatják hosszukat nem – pl.: Tömb, rekord, halmaz
Programozási paradigmák és technikák
Dr. Hajnal Éva
162
Memóriában történő helyfoglalás szerinti csoportosítás • II. Dinamikus adatszerkezetek – Adatelemek száma tetszőleges, az adatelemek száma változhat. – pl.: Lista, Fa, Gráf
Programozási paradigmák és technikák
Dr. Hajnal Éva
163
Továbbá • Lehet rekurzív, melynek definíciója önmagára való hivatkozást tartalmaz. Nem lineáris, ha több ilyen hivatkozás van. • file-ok: nem rekurzív • láncolt lista: rekurzív lineáris • összetett lista, fa, gráf: rekurzív, nem lineáris
Programozási paradigmák és technikák
Dr. Hajnal Éva
164
Összetett adattípusok • Tömb • Füzér • Lista – Verem – Sor
• Bináris fa • Kupac, halmaz... Programozási paradigmák és technikák
Dr. Hajnal Éva
165
Műveletek adatszerkezetekkel • Az adatszerkezetek meghatározzák, a rajtuk végezhető műveleteket • Lehetnek konstrukciós vagy szelekciós műveletek
Programozási paradigmák és technikák
Dr. Hajnal Éva
166
Műveletek adatszerkezetekkel – Tömb: Műveletek, csak az egyedi összetevőkön végezhetők (kivétel a paraméterátadás) – Rekord: A mezőkön, a mező típusának megfelelő műveletek végezhetők
Programozási paradigmák és technikák
Dr. Hajnal Éva
167
Műveletek adatszerkezetekkel Halmaz: • Csak a teljes halmazon végezhetők műveletek: – létrehozás: (feltétellel, felsorolással) – in: az adott elem benne van-e a halmazban – +: unió – *: metszet – -: különbség összehasonlítás
Programozási paradigmák és technikák
Dr. Hajnal Éva
168
Műveletek adatszerkezetekkel • Láncolt lista: – beszúrások – törlések – bejárás, – feldolgozás (pozícionálás, érték kiolvasása) – jelzés: üres-e, van-e következő elem
Programozási paradigmák és technikák
Dr. Hajnal Éva
169
Műveletek adatszerkezetekkel • Verem, sor: – elem be – elem ki – üres-e
• Összetett lista – Cons – Append – List
Programozási paradigmák és technikák
Dr. Hajnal Éva
170
Műveletek adatszerkezetekkel • fa: elem hozzáadása (levél, gyökér) törlés (levél, 1 leágazású csúcs, 2 leágazású csúcs) bejárás (preorder, postorder, inorder) tesztek (levél-e, van-e adott oldali részfája)...
Programozási paradigmák és technikák
Dr. Hajnal Éva
171
Műveletek adatszerkezetekkel Mindegyiken elvégezhető: üres szerkezet inicializálása • Adatelemeken végezhető műveletek (ahol ez engedélyezett) – csere - egy adatelem értékének megváltoztatása – rendezés – keresés - egy adott értékű vagy adott feltételt kielégítő adatelemek helyének megkeresése – bejárás - valamennyi adatelem egyszeri elérése, feldolgozás
Programozási paradigmák és technikák
Dr. Hajnal Éva
172
Absztrakt társzerkezetek • A matematikai adatszerkezetek elméleti adataszerkezetek –le kell őket képezni a tárolókra • címezhető tárolókra (lemez, memória) • Nem címezhetőkre, ha csak sorosan szekvenciálisan járjuk be
Programozási paradigmák és technikák
Dr. Hajnal Éva
173
Címezhető absztrakt társzerkezetek • 1. Vektor 1
2
3
n
Elemei direkt elérhetők Kezelése egyszerű, megfelel az egydimenziós tömbének Ha a matematikai adatszerkezet és a társzerkezet rokon, akkor jó Asszociatív és szekvenciális , konstans méretű, kevésbé átszervezendő adatszerkezet Programozási paradigmák és technikák
Dr. Hajnal Éva
174
2. Lista (sorozat) • Elemtípusa bármi, akár lista is • [a1, a2,…ai-1][ai, ai+1,…an] • Fejrész, farok-rész
Programozási paradigmák és technikák
Dr. Hajnal Éva
175
Műveletek • • • • • •
Létesítés Megszüntet Üres Üres-e Elejére Végére
Programozási paradigmák és technikák
• • • • • •
Tovább Kiolvas Módosít Bővít töröl kapcsol
Dr. Hajnal Éva
176
Műveletek • Létesítés
[][] [a1, a2,…ai-1][ai, ai+1,…an] • Megszűntet [a1, a2,…ai-1][ai, ai+1,…an] [][]
Programozási paradigmák és technikák
Dr. Hajnal Éva
177
Verem és a sor • Olyan dinamikus adatszerkezetek, amelyekben előre meghatározott az az elem, amelyet a Töröl művelettel eltávolíthatunk. • Verem: a legutoljára beszúrt elemet törölhetjük LIFO (last in first out) stratégia • Sor: mindig a legrégebben beérkezett elemet lehet törölni, FIFO (first in first out) stratégia Programozási paradigmák és technikák
Dr. Hajnal Éva
178
Verem statikus megvalósítása tömb segítségével 1 2 3 4 5 6
1 2 3 4 5 6
1 2 3 4 5 6
15 2
15 2 3 9
15 2 3 9
Push(3)
VM=3
Push(9)
• Jellemző adatok:
VM=5
Pop() VM=4
– Veremmutató – stack pointer- az első üres elemre mutat – Veremméret – capacity
• Jellemző műveletek – – – – –
Pop – (veremből)egy elem kivétele a veremből Push – (verembe)egy elem verembe helyezése Top – (tető) a következő kivehető adat olvasása Empty – (üres) van-e adat a veremben Full - (tele) tele van-e a verem
Programozási paradigmák és technikák
Dr. Hajnal Éva
179
Verem műveletek megvalósítása Logikai függvény Üres() ha veremmutató=0 akkor return igaz különben return hamis Függvény vége Eljárás verembe(mit) // push() ha veremmutato>=veremmeret akkor hiba „túlcsordulás” ha veremmutató
Programozási paradigmák és technikák
Függvény veremből() //pop ha Üres() akkor hiba „alulcsordulás” ha nem Üres() akkor veremmutató=veremmutató-1; return verem[veremmutató] elágazás vége Függvény vége
Dr. Hajnal Éva
180
Sorok • Jellemző adat – Sor feje : a kiolvasható adatra mutat – Sor vége: az első üres helyre mutat – Sor mérete //kapacitás
• Jellemző műveletek – Sorból – Sorba
Programozási paradigmák és technikák
Dr. Hajnal Éva
181
Sor statikus megvalósítása tömb segítségével 1
2
3 15
4 4
5
6
Fej=3 vége=5 1 1
2
3 15
vége=2
4 4
5 6
sorba
6 3
Fej=3 sorból
1 1
2
3 15
4 4
vége=2
5 6
6 3
Fej=5
Programozási paradigmák és technikák
Dr. Hajnal Éva
182
Sorműveletek megvalósítása Eljárás sorba(mit) ha Vége=Fej akkor hiba „túlcsordul” különben Sor[vége]=mit ha Vége=Méret-1 akkor Vége=0 egyébként Vége=Vége+1 Elágazás vége Eljárás vége Függvény sorból ha Üres akkor hiba „alulcsordulás” Különben ha Fej=Méret-1 akkor Fej=0 különben Fej=Fej+1 return S[Fej] //üres sor kezelése
ha Fej=Vége akkor Fej=Méret-1 Vége=0 Elágazás vége Függvény vége
Programozási paradigmák és technikák
Dr. Hajnal Éva
183
Klasszikus feladatok veremmel • Matematikai kifejezések kiértékelése verem segítségével – lengyel forma létrehozása és kiértékelése 1. Lengyel forma létrehozása verem segítségével(prefix, infix, postfix alak) 5+6 lengyelformája 5 6 + 5+6*2 lengyelformája 5 6 2 * + 5+6*2-3 lengyelformája 5 6 2 * + 3 – 2. Kiértékelés verem segítségével 2 6 5
*
-
+ 12 5
3 17
Programozási paradigmák és technikák
14
Dr. Hajnal Éva
A veremben lévő utolsó szám: végeredmény
184
Lengyel forma létrehozásának szabályai • • •
A lengyelforma lényege, hogy nincsenek benne zárójelek és prioritási sorrendek, verem segítségével balról jobbra egyszerűen kiértékelhető. Az összetevőket szóköz választja el, a műveleti jel az operandusokat követi. Prioritási sorrend – – – – –
•
0 nem műveleti jelek 1( 2+3*/ 4)
5+6*2-3 lengyelformája 5 6 2 * + 3 –
Szabály (az input és az output is string)
1. Az input sztring balról jobbra karakterenként kerül feldolgozásra. 2. A számok változatlan formában átkerülnek az outputra szóközzel elválasztva 3. A ( bekerül a verembe 4. A ) esetén a legelső (-ig kiürítjük a vermet, és a zárójeleken kívüli jelek az output sztringbe kerülnek 5. Egyéb műveleti jelnél a veremből kivesszük az összes, a jelenlegi jelnél nem kisebb prioritású műveletet, és az otput sztringbe írjuk, a jelenlegi műveleti jel a verembe kerül 6. Ha az input sztring végére értünk a verem tartalmát az outputhoz185 Programozási Dr. Hajnal Éva hozzáírjukparadigmák és technikák
class Stack { T[] t; int veremmutato; //stack pointer readonly int veremmeret; //stack size public Stack(int meret) { t = new T[meret]; veremmeret = meret; veremmutato = 0; } public void Push(T _in) { if (veremmutato >= veremmeret) {throw (new StackOverflowException("Tele van a verem")); } t[veremmutato] = _in; ++veremmutato; } Programozási paradigmák és technikák
Dr. Hajnal Éva
186
public object Pop() { --veremmutato; if (veremmutato >= 0) {return t[veremmutato]; } veremmutato = 0; throw(new InvalidOperationException("Üres a verem, nem lehet kivenni")); } public object Top() { if (veremmutato <= 0) {throw (new InvalidOperationException("Üres a verem")); } return t[veremmutato - 1]; } public bool Empty() { if (veremmutato > 0) return false; return true; } } Programozási paradigmák és technikák
Dr. Hajnal Éva
187
Listák
Egyszerű láncolt lista Mutató a következő elemre
Adat tartalom fej
Vége NULL
1
2
ø
3
Törlés a listából fej
1
2
3
ø
Általában nem szükséges tényleges törlés Programozási paradigmák és technikák
Dr. Hajnal Éva
189
Láncolt lista • Olyan adatszerkezet, amelyben az elemek lieáris sorrendben követik egymást • A lineáris sorrendet mutatók (C# referenciák) segítségével valósíthatjuk meg.
Típusai: • Szerkezet szerint – Egyszeresen láncolt – Kétszeresen láncolt – Ciklikus
• Szervezés szerint – Rendezett – Nem rendezett
Programozási paradigmák és technikák
Dr. Hajnal Éva
190
Kétirányú láncolt lista előző L (fej)
ø
vége
adat következő 1
2
3
ø
• A lánc minden eleme két hivatkozást tartalmaz, az előző és az őt követő elemre • A lánc végét az utolsó elem következő részének kitüntetett értéke jelzi • A lánc elejét az első elem előző részének kitűntetett értéke jelzi • Az első elem címét a listafej tartalmazza • Az utolsó elem címét érdemes tárolni (vége) • Előny az egyirányú listához képest: kevesebb műveletigény a keresés, törlés, beszúrásnál • Hátrány: helyfoglalás, bonyolultabb algoritmus
Programozási paradigmák és technikák
Dr. Hajnal Éva
191
Keresés listában (az első k kulcsú elem keresése) Listában-keres(L,k) //L lista fej referenciája X=L //L a lista feje Ciklus amíg x<>null és x.kulcs<>k x=x.következő Ciklus vége Return x
Programozási paradigmák és technikák
Dr. Hajnal Éva
192
Beszúrás lista elejére Listába-beszúr(L,x) K=Elemfoglal(x) K.következő=L Ha L<>null L.előző=K L=K K.előző=null Programozási paradigmák és technikák
Dr. Hajnal Éva
193
Törlés láncolt listából Listából-töröl(L,x) //x referencia Ha x.előző<>null Akkor (x.előző).következő=x.következő Különben L=x.következő Ha x.következő<>null Akkor (x.következő).előző=x.előző
Programozási paradigmák és technikák
Dr. Hajnal Éva
194
Strátzsa (őrszem, sentinel) technika • Strázsa elemek: a lista elejére és/vagy a végére felvett kiegészítő elemek. Értékes adatot nem tárolnak, csak technikai szerepük van. Kiküszöbölik az első, utolsó elemek problémáját • Előnyök: egyszerűbb, gyorsabb beszúrás és törlés • Hátrány: helyfoglalás, bejárás körülményesebb Programozási paradigmák és technikák
Dr. Hajnal Éva
195
Ciklikus kétirányú strázsás lista következő
előző adat 1
üres
2
3
L
Törlés(L,x) (X.előző).következő=x.következő (X.következő).előző=x.előző
Programozási paradigmák és technikák
Dr. Hajnal Éva
196
Klasszikus feladatok listákra • Polinomok műveletei • Feladat: Két polinom összeadása – Adjunk össze két x,y,z változójú polinomot! – ExAyBzC polinom a kitevők szerint csökkenően rendezettek
Programozási paradigmák és technikák
Dr. Hajnal Éva
197
Bináris keresőfák (BST Binary Searching Tree)
• Definíció: Olyan bináris fa, amelyben minden csúcsra igaz, hogy a baloldali részfájában a kulcsok(adattartalom) kisebbek vagy egyenlőek, a jobb oldali részfábanpedig nagyobbak vagy egyenlőek. • Tetszőleges kulcs elérhető a gyökértől induló keresőútvonalon úgy, hogy minden csúcsból a bal, vagy a jobb részfa felé haladunk, és a döntéshez csak a csúcsot vizsgáljuk. 25 • Gyökérközepű bejárása? 10 43 5 Programozási paradigmák és technikák
Dr. Hajnal Éva
33
50 48 198
Keresőfa építése • 42,30,37,70,50,20,61,57,90,25 elemekből 42
42 30
42
42
30
30 37
Programozási paradigmák és technikák
70 37
Dr. Hajnal Éva
199
Beszúrás keresőfába Függvény beszúrás (x,k) ha x=null akkor elemlétrehozás(x) x.kulcs=k x.bal=null x.jobb=null return x különben ha x.kulcs>k akkor return beszúrás(x.bal,k) különben ha x.kulcs
Programozási paradigmák és technikák
Dr. Hajnal Éva
200
Keresés BST-ben Fában-keres(x,k)
//x a gyökér, k a keresett
kulcs
Ha x=null vagy k=kulcs[x] akkor return x Ha k
Dr. Hajnal Éva
201
Iteratív keresés Fában-i-keres(x,k) Cilkus amíg x!=null vagy k!=kulcs[x] Ha k
Programozási paradigmák és technikák
Dr. Hajnal Éva
202
Törlés bináris fából
Programozási paradigmák és technikák
Dr. Hajnal Éva
203
Törlés keresőfából
25 2. 10 5
•
43 50
1. 33
Feladat: adott kulcsú elem törlése a keresőfából Esetek 1. elemnél kisebbbalra le 2. Elemnél nagyobb jobbra le 3. = akkor
48
52
49 3.
1. Ha levélelem törlés (1.eset) 2. Ha nem levélelem törlés, és a részfák kapcsolása (2. és 3. eset) Programozási paradigmák és technikák
Dr. Hajnal Éva
204
Tökéletesen kiegyensúlyozott fák •
Def. Ha minden csúcsnak a bal és a jobb oldali részfájában lévő csúcsok száma legfeljebb eggyel tér el. Kiegyensúlyozás Ha N=0 a fa üres Ha N>0 1. Használjunk el egy csúcsot gyökérnek 2. Készítsük el az N/2 csúcsból álló bal részfát 3. Készítsük el az N-(N/2)-1 csúcsból álló jobb részfát Programozási paradigmák és technikák
Dr. Hajnal Éva
205
Kiegyensúlyozás
Programozási paradigmák és technikák
Dr. Hajnal Éva
206
Kiegyensúlyozott fák • Def. Ha minden csúcsra legfeljebb egy a különbség a bal és a jobboldali részfa magassága között. • Ha a keresőfában nagy a magasságbeli különbség a szintek között, akkor a keresés időigénye függ a keresendő elem értékétől.
Programozási paradigmák és technikák
Dr. Hajnal Éva
207
Piros-fekete fák • Piros-fekete fa olyan bináris keresőfa,melynek minden csúcsa egy extra bit információt hordoz. • A színek korlátozásával biztosítható, hogy a gyökértől a levélig vezető út hossza nem lehet nagyobb, mint a legrövidebb ilyen út hosszának a kétszerese • Piros-fekete fák megközelítőleg kiegyensúlyozottak. • Csúcs adatai: szín, kulcs, bal, jobb, szülő Programozási paradigmák és technikák
Dr. Hajnal Éva
208
Tulajdonságok 1. 2. 3. 4. 5.
Minden csúcs színe piros vagy fekete Gyökér színe fekete Levél:fekete (gyakran nem is ábrázoljuk) Piros csúcs mindkét gyereke fekete Bármely csúcsból bármely levélig vezető úton ugyanannyi fekete csúcs van.
Programozási paradigmák és technikák
Dr. Hajnal Éva
209
Piros-fekete fa Fekete mélység: Adott csúcsból, ahol ő maga nem számít az eredménybe, a levélig vezető úton a fekete csúcsok száma.
Programozási paradigmák és technikák
Dr. Hajnal Éva
210
Műveletek • Forgatások (balra, jobbra forgat) • Beszúrás • Törlés
Programozási paradigmák és technikák
Dr. Hajnal Éva
211
AVL-fa • Az AVL fa olyan bináris keresőfa amely magasság kiegyensúlyozott: – A bal és jobb részfa magassága legfeljebb 1gyel különbözik.
• Megvalósítás +mező :magasság
Programozási paradigmák és technikák
Dr. Hajnal Éva
212
B-fa • Nagyméretű keresőfák esetén előfordul, hogy az egész fa nem fér el az operatív tárban. • A fát részfákra bontjuk, és a részfákat (lapoknak nevezzük) olyan egységként ábrázoljuk, amelyek elemeire együtt hivatkozhatunk. • Minden lap n és 2n közötti tételt tartalmaz Programozási paradigmák és technikák
Dr. Hajnal Éva
213
B-fa definíciója
Programozási paradigmák és technikák
Dr. Hajnal Éva
214
B-fa tulajdonságai 1. Minden lap legfeljebb 2n tételt tartalmaz 2. Minden lapon a gyökér lapjának kivételével legalább n tétel van. 3. Egy lap lehet levéllap(utód nélküli), vagy m+1 utóddal rendelkezik, ahol m a lapon levő kulcsok száma 4. Minden levéllap ugyanazon a szinten helyezkedik el. Programozási paradigmák és technikák
Dr. Hajnal Éva
215
Teszt • Adja meg egy adott elem listába beszúrásának algoritmusát • Építsen BST fát a következő elemekből 12, 35, 3, 4, 89, 12, 56, 20
Programozási paradigmák és technikák
Dr. Hajnal Éva
216
Radix rendezés • Legtermészetesebb rendezés, ha sok névből álló, vagy sokjegyű számokból álló listát kell rendezni. • Pl. decimális számokra • Először az utolsó számjegy szerint csoportokba szétválogatom, és a csoportokat újra összevonom • Utána az utolsó előtti számjegy szerint szétválogatom stb. Programozási paradigmák és technikák
Dr. Hajnal Éva
217
A radix rendezés bonyolultsága Ha A1, A2…An az n elemet tartalmazó lista. d az alap, vagyis a válogatás során kialakítandó csoportok száma (d=10 decimális számoknál, d=26 betűknél stb.) s a számjegyek száma, karakterek száma stb., ennyi menetben kell végezni a szétválogatást
• • • •
Összehasonlítások száma<=d*s*n d független n értékétől, de s függ tőle: log n<=s<=n O(n*log(n)) Tárigénye: d*n, ezt dinamikus helyfoglalással 2*n-ig lehet csökkenteni.
Programozási paradigmák és technikák
Dr. Hajnal Éva
218
Kupac adatszerkezet definíciója • Kupac • Olyan (bináris) fa, amely teljesíti a kupactulajdonságot.
• Kupactulajdonság • Ha B A gyereke, akkor a (maximális) kupactulajdonság: kulcs(A) ≥ kulcs(B) Vagyis
Minden elem kisebb kell legyen mint a szülő Programozási paradigmák és technikák
Dr. Hajnal Éva
219
Rendezések - Kupac rendezés • Kupac: – Olyan tömb, melynek elemeit egy bináris fa csomópontjaiként képzeljük, – K(1) a fa gyökere, – ahol a j indexű szülő gyerekei a 2*j és 2*j+1 indexű elemek (K(2*j) és K(2*j+1) – K([j/2])>=K(j) 1<=[j/2]<j<=n-re
Programozási paradigmák és technikák
Dr. Hajnal Éva
220
1. Az algoritmus első fázisa
Kiindulás:
Programozási paradigmák és technikák
Dr. Hajnal Éva
221
2. Az algoritmus első fázisa Az elemeket egyesével bevonjuk a kupacba A levélelemekre automatikusan teljesül a kupac tulajdonság Az m=j/2 esetre kell biztosítani a kupac tulajdonság teljesülését az elemek cseréjével, úgy, hogy mindig csak az m csúcs gyökerű részfán dolgozunk.
Programozási paradigmák és technikák
Dr. Hajnal Éva
222
3. Az algoritmus első fázisa
Programozási paradigmák és technikák
Dr. Hajnal Éva
223
4. Az algoritmus első fázisa
Programozási paradigmák és technikák
Dr. Hajnal Éva
224
5. Az algoritmus első fázisa
Programozási paradigmák és technikák
Dr. Hajnal Éva
225
6. Az algoritmus első fázisa A kupac elkészült
Programozási paradigmák és technikák
Dr. Hajnal Éva
226
1. Az algoritmus második fázisa
Programozási paradigmák és technikák
Dr. Hajnal Éva
227
2. Az algoritmus második fázisa
Programozási paradigmák és technikák
Dr. Hajnal Éva
228
3. Az algoritmus második fázisa
Programozási paradigmák és technikák
Dr. Hajnal Éva
229
Az algoritmus második fázisa
Programozási paradigmák és technikák
Dr. Hajnal Éva
230
4. Az algoritmus második fázisa
Programozási paradigmák és technikák
Dr. Hajnal Éva
231
5. Az algoritmus második fázisa
Programozási paradigmák és technikák
Dr. Hajnal Éva
232
6. Az algoritmus második fázisa
Programozási paradigmák és technikák
Dr. Hajnal Éva
233
7. Az algoritmus második fázisa
Programozási paradigmák és technikák
Dr. Hajnal Éva
234
8. Az algoritmus második fázisa
Programozási paradigmák és technikák
Dr. Hajnal Éva
235
9. Az algoritmus második fázisa
Végeredmény
Programozási paradigmák és technikák
Dr. Hajnal Éva
236
Algoritmus I. Kupacrendezés
algoritmusa KupacRend(T/*tömb*/, int n /*hossz*/) { // épít egy kupacot for (int i = n / 2; i >= 0; --i) Sullyeszt(T, i, n); // a kupac legnagyobb elemét kicseréli az utolsó elemmel // majd kijavítja a kupacot, ami mostmár nem a teljes, hossz, hanem csak az "utolsó" előtti elemtől számít
for (int i = n; i >= 0; --i) { csere(T[0], T[i]); Sullyeszt(T, 0, i - 1); } } Programozási paradigmák és technikák
Dr. Hajnal Éva
237
Algoritmus I. Kupac tulajdonság fenntartása Sullyeszt(T /*kupac*/, int pont, int m) int apa = pont; int fiu; temp = kupac[pont]; Ciklus amíg ((fiu = 2*apa + 1) < m ) //a nulla indexelés miatt a 2*apa + 1 adja a bal gyereket //pelda: 8, 2, 5, 7, 6. a 0 indexelés szerinti 1. elem azaz a "2" bal gyermeke a "2*1 + 1 = 3" indexű elem, azaz a "7".
//
jobb gyerek > bal gyerek, akkor átlép jobb gyerekre
ha (T[fiu + 1] > T[fiu]) fiu++;//
ha
teljesül a kupac tulajdonság, akkor megáll
ha (temp >= T[fiu]) break;
// a gyereket
feljebb hozza
T[apa] = T[fiu]; apa = fiu; Ciklus vége // a javítandó elemet beteszi az utolsó
emelt gyerek
helyére
T[apa] = temp; Eljárás vége Programozási paradigmák és technikák
Dr. Hajnal Éva
238
Algoritmus II. Kupac-építése Kupacot épít(T ) // T tömb m=n-1 //utolsó index értékét kapja ciklus i=(n-1)/2-től 0-ig maximum-kupacol(T,i) ciklus vége Eljárás vége
Programozási paradigmák és technikák
Dr. Hajnal Éva
239
Algoritmus II. (rekurzív) Kupactulajdonság fenntartása Maximum-kupacol(T,i) L=i*2+1 //bal R=i*2+2 //jobb ha L<=m és T[L]>T[i] //m a kupacméret akkor legnagyobb=L különben legnagyobb=i ha r<=m és T[R]>T[legnagyobb] akkor legnagyobb=r ha legnagyobb!=i akkor csere(T[i], T[legnagyobb]) Maximum-kupacol(T,legnagyobb) elágazás vége Eljárás vége Programozási paradigmák és technikák
Dr. Hajnal Éva
240
Algoritmus II. Rendezés Kupacrendezés(T) Kupacot épít(T) ciklus i=n-1-től 1-ig csere(T[0],T[i]) m=m-1 //kupac méret csökkentése maximum-kupacol(T,0) ciklus vége Eljárás vége Programozási paradigmák és technikák
Dr. Hajnal Éva
241
Rendezés jellemzői • Tárigény: n (helyben rendező algoritmus) • Időbonyolultság: – Kupac kialakítása: • Legjobb eset: 0 mozgatás • Legrosszabb eset: n/2 mozgatás
– Kupac lebontása: • log(n-1)+log(n-2)+….
Programozási paradigmák és technikák
Dr. Hajnal Éva
242
Huffman-kód • Széles körben használt, nagyon hatékony módszer állományok tömörítésére • Az állomány karaktereinek gyakoriságát alapul vevő, állandó vagy változó hosszúságú kód. • Prefix kód: olyan kódszavakat tartalmaz, amelyekre igaz az, hogy egyik kód sem kezdőszelete a másiknak. – Pl.ha a = 0 akkor a többi karakter kódja csak 1-gyel kezdődhet – pl. b=10 akkor 10 –val több nem kezdődhet
Programozási paradigmák és technikák
Dr. Hajnal Éva
243
Huffman-kódhoz tartozó bináris fa
Azonos hosszúságú kódok, minden levélelem ugyanazon a szinten helyezkedik el.
Programozási paradigmák és technikák
Változó hosszúságú prefix kódot tartalmazó bináris fa
Dr. Hajnal Éva
244
2-es Fa jellemzői: • Külső csomópontok száma eggyel több mint a belső csomópontok száma • A kód hossza a levélelemek magassága • Ha az egyes csomópontokban a karakterek gyakorisága, vagy a bal és jobb gyerek súlyának összege a súly, akkor a legtömörebb kódolást a legkisebb súlyozott külső útvonalhosszúságú fával érhetjük el. Programozási paradigmák és technikák
Dr. Hajnal Éva
245
Huffmann-algoritmus • Tegyük fel, hogy adott az n darab súly (karakterek gyakorisága), w1,w2…wn növekvő sorrendben. • T minimális súlyozott útvonal-hosszúságú fa előállítása: w1+w2 külső csomópontot helyettesítjük a részfával w1 w2
Programozási paradigmák és technikák
Dr. Hajnal Éva
246
Példa • Tegyük fel, hogy az A, B, C, D, E, F, G, H karakterekhez az alábbi súlyok tartoznak: A 22 B5 C 11 D 19 E2 F 11 G 25 H5
1.
2.
22 A
5 B
22 A
11 C
11 C
7
5 B
19 D
2 E
19 D
11 F
11 F
25 G
25 G
5 H
5 H
2 E
... Programozási paradigmák és technikák
Dr. Hajnal Éva
247
Algoritmus Huffman(C) Karaktergyakoriságok megállapítása Q kupac létrehozása (minimum-kupacol eljárással) Ciklus i=1 től n-1 ig új z csúcs létesítése bal[z]=x kivesz-min(Q) jobb[z]=y kivesz-min(Q) beszúr(Q, x gyakorisága+y gyakorisága) Ciklus vége Return kivesz-min(Q) Programozási paradigmák és technikák
Dr. Hajnal Éva
248
Emlékeztető - Tematika Teszt • Építsen maximum-kupacot a következő elemekből 12, 35, 3, 4, 89, 56, 20 A rendezés i=4. lépésében írja fel a kupacot és a vektorból képzett bináris fát! Programozási paradigmák és technikák
Dr. Hajnal Éva
249
Hasító táblázat • Tömb adatszerkezet általánosítása • Jól alkalmazható adatszerkezet, ha Beszúr(), Keres() és Töröl() műveleteket megvalósító dinamikus halmazra van szükség. • Beszúr(), Keres(), Töröl()szótárműveletek
Programozási paradigmák és technikák
Dr. Hajnal Éva
250
Programozási paradigmák és technikák
Dr. Hajnal Éva
251
Halmaz megvalósítása közvetlen címzésű táblázattal
Feltételek: Kisméretű kulcsuniverzum Nincs két egyforma kulcsú elem Programozási paradigmák és technikák
Dr. Hajnal Éva
252
Közvetlen címzésű táblázat • • • • •
T[0…m-1] tömb segítségével Táblázat helyei – rés – megfelelnek a kulcsoknak K. rés a halmaz k kulcsú elemére mutat. Ha nincs k kulcsú elem akkot T[k]=null Műveletek – Közvetlen címzéssel – végrehajtási idő O(1) Keres(T,k) return T[k]
Beszúrás(T,x /*adat*/) T[kulcs[x]] x
Törlés(T,x/*adat*/) T[kulcs[x]]=null
Programozási paradigmák és technikák
Dr. Hajnal Éva
253
Adatelemek tárolása • Magában a közvetlen címzésű táblázatban, gyakran a kulcsmező tárolása sem szükséges – Visszakeresés index alapján – Ha nem tároljuk a kulcsmezőt, el kell tudni dönteni, hogy a rés üres-e
• A réshez mutatóval kapcsolt külső objektumban Programozási paradigmák és technikák
Dr. Hajnal Éva
254
Közvetlen címzés problémája • Ha az U univerzum nagy és a tárolt elemek K halmaza U-hoz képes kicsi, akkor a T táblázat nagy helyet foglal, de nagy része üres, a kihasználtság kicsi • Memóriaigény leszorítható egy alkalmasan választott függvény segítségével, amely a k kulcsú elemet egy k’ résben tárolja ahol k’=h(k), vagyis hasító függvényt használunk a k’ kiszámításához. • h:U{0,1,…m-1} • Új probléma: kulcsütközés Programozási paradigmák és technikák
Dr. Hajnal Éva
255
Kulcsütközés
Programozási paradigmák és technikák
Dr. Hajnal Éva
256
Hasítófüggvények
Programozási paradigmák és technikák
Dr. Hajnal Éva
257
Kulcsütközés • Ha két kulcs ugyanarra a résre képződik le • Kulcsütközés elvileg sem küszöbölhető ki, mert U>m, tehát mindenképp kell lennie legalább két kulcsnak, amelyek ugyanarra a résre képződnek le.
Programozási paradigmák és technikák
Dr. Hajnal Éva
258
Kulcsütközés feloldása I. • Túlcsordulási terület használatával • Csak akkor alkalmazható ha nagyon kevés a kulcsütközés • Beszúrás: a, T[h(k)] =null → beszúrás T[h(k)]-ba b, T[h(k)] ≠ null → beszúrás túlcsordulási területre
•
Keresés: a, T[h(k)] = keresett → megvan b, T[h(k)] = Ø → nincs c, T[h(k)] ≠ keresett keresett túlcsordulási terület → megvan keresett túlcsordulási terület → nincs Programozási paradigmák és technikák
Dr. Hajnal Éva
259
Kulcsütközés feloldása láncolással
Programozási paradigmák és technikák
Dr. Hajnal Éva
260
Példa • Kövessük végig láncolásos ütközésfeloldás esetén az 5,28,19,15,20,33,12,17,10 kulcsok hasító táblázatba való beszúrását. Legyen a rések száma 9 és a hasító függvény h(k)=k mod 9
Programozási paradigmák és technikák
Dr. Hajnal Éva
261
Ütközésfeloldás láncolással II. • Ugyanarra a résre leképződő elemeket összefogjuk egy láncolt listába Láncolt-hasító-beszúrás(T,x) 1 beszúrás a T[h(kulcs[x])] lista elejére
Rendezés?
Láncolt-hasító-keresés(T,k) 1 a k kulcsú elem keresése a T[h(k)] listában
Láncolt-hasító-törlés 1 x törlése a T[h(kulcs[x])] listából. Beszúrás és törlés műveletigénye: O(1)
Programozási paradigmák és technikák
Dr. Hajnal Éva
262
Keresés időigénye • Legrosszabb esetben a keresés időigénye O(n) • Jó esetben: – Legyen =n/m ( a kitöltési tényező, vagyis a láncba fűzött elemek átlagos száma) – Egyenletes hasítás esetén O(1+), vagyis a keresés átlagos ideje állandó
Programozási paradigmák és technikák
Dr. Hajnal Éva
263
Hasító függvények • Hogyan működik egy jó hasító függvény? – Egyenletességi feltétel: egyenletesen ossza szét a kulcsokat • Ehhez ismerni kellene a kulcsok eloszlás függvényét
– A hasonló kulcsokat véletlenszerűen ossza szét – Kevés kulcsütközést produkáljon – Egyszerűen kiszámítható legyen – A hasítófüggvény kötelezően determinisztikus Programozási paradigmák és technikák
Dr. Hajnal Éva
264
A kulcsok természetes számokkal való megjelenítése • A kulcsokat természetes számként kezeljük, • Ha nem természetes szám akkor természetes számmá kell alakítani pl. ASCII kódok… • h(k) = ΣKarakterkód(ki) (k є Szöveg)
Programozási paradigmák és technikák
Dr. Hajnal Éva
265
Osztásos módszer • h(k)=k mod m • Jellemzői – Gyors hasítás – Jó, ha m egy kettőhatványhoz nem közeli prim. – Rések száma m
– Példa:2000 db adat van a kitöltési tényező lehet ~3, tervezzük meg a hasítófüggvényt! Programozási paradigmák és technikák
Dr. Hajnal Éva
266
Szorzásos módszer • h(k)=KözepeM(A*k) • KözepeM(x) visszaadja az x középső M darab helyiértékét • Nevezetes módszer a négyzetközép módszer: h(k)=KözepeM(k*k)
Programozási paradigmák és technikák
Dr. Hajnal Éva
267
Az univerzális hasítás • Véletlenszerűen kiválasztott hasítófüggvénnyel próbálja minimalizálni a kulcsütközést.
Programozási paradigmák és technikák
Dr. Hajnal Éva
268
Kulcsütközés feloldása – Nyílt címzés III. A duplikátumot egy előre definiált szisztematikus üres hely kereséssel helyezzük el! • Beszúrás: Ha T[h(uj)] foglalt, egy/több lépés előre/hátra amíg nem találunk egy üres helyet, ide elmentjük • Keresés: Ha T[h(keresett)] nem a keresendő elem, a beszúrásnál használt azonos lépések végrehajtása,amíg nem találjuk meg, vagy az első üres helyig. Ha az induló vagy bármelyik elem üres, akkor nincs a táblázatban • Törlés:Keresés után az elem bejelölése töröltnek (nem üres!) Programozási paradigmák és technikák
Dr. Hajnal Éva
269
Kulcsütközés feloldása IV. – Dupla hasítás • Használjunk két hasító függvényt (h1, h2)! • Beszúrás: Ha a h1 függvény alkalmazásával kulcsütközés lépne fel, próbáljuk egy másik h2 függvénnyel, ami máshova képez • Keresés: Ha a h1 által megadott helyen nem találjuk a keresett elemet, keressük a h2 szerint is • Törlés: A fenti kereséssel megtalált elemet töröljük Programozási paradigmák és technikák
Dr. Hajnal Éva
270
Hasítótáblák felhasználása • Adatbázisokban • Fordítóprogramok szimbólumtábláiban
Programozási paradigmák és technikák
Dr. Hajnal Éva
271
Példa • Egy bitvektor egy biteket tartalmazó, egydimenziós tömb. Egy m hosszúságú bitvektor sokkal kevesebb helyet foglal el, mint egy m mutatót tartalmazó tömb. Írjuk le, hogyan lehetne egy dinamikus halmazt bitvektorral megvalósítani, ha tudjuk, hogy az elemek mind különbözők és nincs kisérő adat. Programozási paradigmák és technikák
Dr. Hajnal Éva
272
Példa • Készítsünk 3 jegyű számok rendezésére alkalmas radix rendező algoritmust. A szétválogatáshoz foglaljunk egy int[10,n] T mátrixot, az egyes sorokban levő elemszám tárolására alkalmazzunk egy int[10] index vektort. Javasoljon más, hatékony adatszerkezetet a feladat megoldásához. Programozási paradigmák és technikák
Dr. Hajnal Éva
273