Programozási paradigmák és technikák. Előadás: Hajnal Éva Gyakorlat: Burián Ágnes

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


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


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


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


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.


Dr. Hajnal Éva

12

Eljárás végrehajtása II.


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.


Dr. Hajnal Éva

14

Függvény visszaadott értéke • • • •

void int double Összetett adat

Eljárás

függvény

– pl. tömb


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); }


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


Dr. Hajnal Éva

17

Átadott paraméter egyeztetése


Dr. Hajnal Éva

18

Érték szerinti paraméter átadás


Dr. Hajnal Éva

19

Cím szerinti paraméter átadás • Átmenő, kimenő paraméter • Ref, out


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


Dr. Hajnal Éva

25

FileAccess értékei • Read • Write • ReadWrite


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


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).


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ó

n0

n * (n  1)! ha n  0 n!  1 ha n  0  n0


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


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


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 


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


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


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


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


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

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


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


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


"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


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!


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)


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ó


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


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


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.


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”


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.


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


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


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 { // … }


ő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


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


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


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();


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


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

//?? //?? //??


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


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.


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; }


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


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(); }


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;


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]);}}


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)


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. • HibaIndexhiba 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!!!!


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


123

Kivétel továbbadása - A finally blokk használata


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 !! }


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”)) { … }


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;


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] }…}


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(); } } }


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ó


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 }


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) ???


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; //intkomplex 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; //???


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


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


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);


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)


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.


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ű


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


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


Dr. Hajnal Éva

160

II. Heterogén adatszerkezetek • Különböző típusú adatokból épül fel. • pl.: Record


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


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


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


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


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


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


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


Dr. Hajnal Éva

169

Műveletek adatszerkezetekkel • Verem, sor: – elem be – elem ki – üres-e

• Összetett lista – Cons – Append – List


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)...


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


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


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


Dr. Hajnal Éva

175

Műveletek • • • • • •

Létesítés Megszüntet Üres Üres-e Elejére Végére


• • • • • •

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] [][]


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


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ó

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


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


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


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


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


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


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


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ő


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ő


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


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


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

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

Dr. Hajnal Éva

202

Törlés bináris fából


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 kisebbbalra 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


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.


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.


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.


Dr. Hajnal Éva

210

Műveletek • Forgatások (balra, jobbra forgat) • Beszúrás • Törlés


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


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


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


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.


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


Dr. Hajnal Éva

220

1. Az algoritmus első fázisa

Kiindulás:


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.


Dr. Hajnal Éva

222



Dr. Hajnal Éva

223



Dr. Hajnal Éva

224



Dr. Hajnal Éva

225

6. Az algoritmus első fázisa A kupac elkészült


Dr. Hajnal Éva

226

1. Az algoritmus második fázisa


Dr. Hajnal Éva

227



Dr. Hajnal Éva

228



Dr. Hajnal Éva

229

Az algoritmus második fázisa


Dr. Hajnal Éva

230



Dr. Hajnal Éva

231



Dr. Hajnal Éva

232



Dr. Hajnal Éva

233



Dr. Hajnal Éva

234



Dr. Hajnal Éva

235


Végeredmény


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


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)+….

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


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.


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


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


Dr. Hajnal Éva

250


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


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


Dr. Hajnal Éva

256

Hasítófüggvények


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.


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


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


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)


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ó


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)


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)


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.


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


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

Programozási paradigmák és technikák. Előadás: Hajnal Éva Gyakorlat: Burián Ágnes

Recommend Documents