Bánsághi Anna 2014 Bánsághi Anna 1 of 33

Absztrakt adattípus

7. előadás

IMPERATÍV PROGRAMOZÁS © Bánsághi Anna [email protected]

7. ELŐADÁS - ABSZTRAKT ADATTÍPUS

2014 © Bánsághi Anna

1 of 33


7. előadás

TEMATIKA I. ALAPFOGALMAK, TUDOMÁNYTÖRTÉNET II. IMPERATÍV PROGRAMOZÁS Imperatív paradigma Procedurális paradigma Generikus paradigma III. STRUKTÚRÁLT PROGRAMOZÁS Objektumorientált paradigma Moduláris paradigma


2 of 33


7. előadás

III. OBJEKTUMORIENTÁLT PARADIGMA 1. Absztrakt adattípus Adatabsztrakció Konstruktorok Operátorok túlterhelése 2. Objektumok, osztályok 3. OOP tervezés 4. Öröklődés 5. Adatszerkezetek megvalósítása


3 of 33


7. előadás

AZ ABSZTRAKCIÓ MÁSODIK SZINTJE a végrehajtás irányából utasításabsztrakció

lényeges, hogy mit csinál az algoritmus lényegtelen, hogyan van implementálva

az adatok irányából adatabsztrakció

lényeges a való világ modellezése lényegtelen a reprezentáció, az implementáció

objektumorientált paradigma absztrakt adattípusok


4 of 33


7. előadás

1. ABSZTRAKT ADATTÍPUS


5 of 33


7. előadás

ELEMI TÍPUSOK szerkezet nélküliek, logikailag felbonthatatlanok (int, char, ...)

ÖSSZETETT TÍPUSOK meglévő típusokból tevődnek össze típuskonstrukciók segítségével (rekord, tömb és unió)

ABSZTRAKT ADATTÍPUSOK meglévő típusokból tevődnek össze típuskonstrukciókkal és új műveletek megvalósításával


6 of 33


7. előadás

ABSZTRAKT ADATTÍPUS a típus definiálása két részből áll meg kell adni az értékhalmazt, mely véges, mert a lefoglalható memória területe is véges meg kell adni a művelethalmazt, az értékhalmazon értelmezett műveleteket, esetleg más értékhalmazokat is felhasználva int = ( Z, { + - * / } )

bool = ( { true, false }, { ¬ ∧ ∨ → } )


7 of 33


7. előadás

ŰRTELESZKÓP FELADAT Számoljuk meg, hány ismeretlen tárgy tartózkodik a Hubble űrteleszkóp 10 km-es környezetében

VISSZAVEZETÉS VALAMELY ISMERT PROGRAMOZÁSI TÉTELRE azt sejtjük, hogy a Számlálás tétellel megoldható, hogyha az alábbi megfeleltetéseket alkalmazzuk: tulajdonság ~ űrteleszkóp 10 km-es környezetébe esik tömb[1..n] ~ ismeretlen tárgyak darab = 0 ciklus i = 1-től n-ig ha űrteleszkóp 10 km-es környezetébe esik( ismeretlen tárgyak[i] ) akkor darab += 1 elágazás vége ciklus vége


8 of 33


7. előadás

PROBLÉMAFELVETÉS tovább már nem tudjuk finomítani a feladatot, hiszen egy programozási tételre vezettük vissza, amely nem bontható fel további részfeladatokra mégis baj van, mert nincsen olyan megvalósítása a Számlálás tételnek, amely ismeretlen tárgyak tömbjének elemeit vizsgálná aszerint, hogy azok beleesnek-e egy űrteleszkóp 10 km-es környezetébe induljunk el az adatok irányából


9 of 33


7. előadás

A FELADAT ABSZTRAKCIÓJA űrteleszkóp 10 km-es környezete ~ 10 km sugarú gömb ismeretlen tárgy ~ térbeli pont Számoljuk meg, hány pont esik egy adott 10 km sugarú gömbbe

AZ ALGORITMUS AKTUALIZÁLÁSA darab = 0 ciklus i = 1-től n-ig ha pontok[i] ∈ gömb akkor darab += 1 ciklus vége


10 of 33


7. előadás

ABSZTRAKT TÍPUSOK Ha lennének Pont és Gömb típusaink, és a Gömb típuson lenne egy BennevanE egy pont a gömbben művelet, akkor kész lennénk Tegyük fel, hogy olyan programozási nyelvet használunk, amely biztosít nyelvi eszközt absztrakt adattípusok létrehozására, és fogjuk fel két kisebb programozási feladatként a Pont és a Gömb típusok létrehozását


11 of 33


7. előadás

PONT TÍPUS SPECIFIKÁCIÓJA értékhalmaz művelethalmaz

térbeli pontok halmaza -

GÖMB TÍPUS SPECIFIKÁCIÓJA értékhalmaz művelethalmaz

gömbök halmaza { BennevanE }

gondoljuk át, hogyan tudnánk elemi, összetett és absztrakt típusok segítségével megvalósítani a két típusspecifikációt


12 of 33


7. előadás

PONT TÍPUS REPREZENTÁCIÓJA egy térbeli pont három koordinátával jellemezhető valamely 3 dimenziós koordinátarendszerben értékhalmaz művelethalmaz

R × R × R = R3 ∅

Pont = ( R

3

,∅)

Pont ∋ p = ( p.x, p.y, p.z )


13 of 33


7. előadás

PONT TÍPUS MEGVALÓSÍTÁSA rekorddal, melynek három mezeje van struct Pont { // mezők: double x; double y; double z; }

// a pont rekordja // x koordináta // y koordináta // z koordináta

public static void Main() { Pont pont;

// pont típusú változó deklarálása

// a pont mezőinek értékadása Console.Write( "x: " ); pont.x = double.Parse( Console.ReadLine() ); Console.Write( "y: " ); pont.y = double.Parse( Console.ReadLine() ); Console.Write( "z: " ); pont.z = double.Parse( Console.ReadLine() ); Console.WriteLine( "A pont: ({0}, {1}, {2})", pont.x, pont.y, pont.z ); }


14 of 33


7. előadás

PONTOK DINAMIKUS LISTÁJA a listát dinamikusan hozzuk létre public static void Main() { var pontok = new List(); for( int i = 0; i < 3; ++i ) { Pont pont;

// pontok listája konstruktorral létrehozva // három elemű lista lesz

// a ciklusra lokális változó

Console.Write( "x: " ); pont.x = double.Parse( Console.ReadLine() ); Console.Write( "y: " ); pont.y = double.Parse( Console.ReadLine() ); Console.Write( "z: " ); pont.z = double.Parse( Console.ReadLine() ); pontok.Add( pont );

// a pont hozzáfűzése a listához

} foreach( Pont pont in pontok ) { Console.WriteLine( "A pont: ({0}, {1}, {2})", pont.x, pont.y, pont.z ); } }


15 of 33


7. előadás

GÖMB TÍPUS REPREZENTÁCIÓJA egy gömb középpontjával és sugarával jellemezhető valamely 3 dimenziós koordinátarendszerben értékhalmaz művelethalmaz

Pont ×R { BennevanE : Gömb × Pont →

L}

Gömb = ( Pont ×R, { BennevanE } ) Gömb ∋ g = ( g.c, g.r )


16 of 33


7. előadás

BENNEVAN-E EGY PONT EGY GÖMBBEN ezt a műveletet fogjuk fel egy újabb részfeladatként Számítsuk ki a gömb középpontjának és a pontnak a távolságát, és döntsük el, hogy ez a távolság kisebb-e, mint a gömb sugara

A FELADAT ABSZTRAKCIÓJA Számítsuk ki két térbeli pont távolságát, és döntsük el, hogy ez a távolság kisebb-e, mint egy adott nemnegatív valós szám

FINOMÍTOTT REPREZENTÁCIÓ BennevanE :


R3 × R3 × R → L

17 of 33


7. előadás

AZ ABSZTRAKT FELADAT MEGOLDÁSA BennevanE :

R3 × R3 × R → L

SPECIFIKÁCIÓ

p, c : R3 és r : R kimenet bennevan : L előfeltétel r ≥ 0 bemenet

utófeltétel

−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−− bennevan = √(p. x − c. x)2 + (p. y − c. y)2 + (p. z − c. z)2 < r


18 of 33


7. előadás

GÖMB TÍPUS MEGVALÓSÍTÁSA rekorddal, melynek két mezeje és egy metódusa van public struct Gomb { // mezők: public Pont c; public double r; // metódus: public bool BennevanE( Pont pont ) { double tavolsag = Math.Sqrt( Math.Pow(( pont.x - c.x ), 2 ) + Math.Pow(( pont.y - c.y ), 2 ) + Math.Pow(( pont.z - c.z ), 2 )); return tavolsag < r; } }


19 of 33


7. előadás

Főprogram - gömb létrehozása public static void Main() { Gomb gomb; Pont kozeppont; kozeppont.x = 1; kozeppont.y = 4; kozeppont.z = 2; gomb.c = kozeppont; gomb.r = 12; Console.WriteLine( "Középpont: ({0}, {1}, {2})", gomb.c.x, gomb.c.y, gomb.c.z ); Console.WriteLine( "Sugár: {0}", gomb.r );


20 of 33


7. előadás

Főprogram - pont létrehozása és vizsgálat Pont pont; Console.Write( "x: " ); pont.x = double.Parse( Console.ReadLine() ); Console.Write( "y: " ); pont.y = double.Parse( Console.ReadLine() ); Console.Write( "z: " ); pont.z = double.Parse( Console.ReadLine() ); Console.WriteLine( "A pont: ({0}, {1}, {2})", pont.x, pont.y, pont.z ); Console.WriteLine( "A pont bennevan a gömbben: {0}", gomb.BennevanE( pont )); }


21 of 33


7. előadás

A Számlálás tételét most már alkalmazhatjuk pontokra és gömbökre is darab = 0 ciklus i = 1-től n-ig ha gömb.BennevanE( pontok[i] ) akkor darab += 1 ciklus vége

static int Szamlalas( List pontok, Gomb gomb ) { int darab = 0; foreach( var pont in pontok ) { if( gomb.BennevanE( pont )) { ++darab; } } return darab; }


22 of 33


7. előadás

2. KONSTRUKTOROK a rekordok mezőit egyesével inicializálni körülményes egyszerűsíthető, ha készítünk egy beállító metódust, amely a paraméterek alapján értéket ad a mezőknek nem kötelező az összes mezőt paraméteren keresztül beállítani, de mindegyiket inicializálni kell ezt a metódust is meg kell hívni egyszer van egy olyan speciális metódus, amely akkor hívódik meg, amikor létrehozunk egy változót a rekord típusból, ez a példány konstruktor


23 of 33


7. előadás

PÉLDÁNY KONSTRUKTOR speciális metódus, melyet egy adott típusú érték (példány) létrehozására használunk hívásakor lefoglalódik a hely a memóriában a példány számára, és a mezők alapértelmezett értékeket kapnak a konstruktor neve megegyezik a típus nevével nincs visszatérési típusa, arra szolgál, hogy a rekord mezőit kezdőértékkel lássa el akkor is létezik egy paraméter nélküli változata, ha nem írjuk meg, nem végez inicializáló tevékenységet tetszőlegesen paraméterezhető és túlterhelhető (rekordok struct esetén nem definiálható felül a paraméter nélküli konstruktor)


24 of 33


7. előadás

PONT TÍPUS KONSTRUKTOROKKAL értékhalmaz művelethalmaz

R × R × R = R3 { Pont : R → Pont, Pont : R × R → Pont, Pont : R × R × R → Pont }

Pont = ( R

3


, { Pont } )

25 of 33


7. előadás

BŐVÍTETT PONT TÍPUS public class Teglalap { // mezők: public double a; public double b; // konstruktorok: public Teglalap() { a = 10; b = 10; } public Teglalap( double oldal1, double oldal2 ) { a = oldal1; b = oldal2; } // metódusok: public double Kerulet() { return 2 * a + 2 * b; } public double Terulet() { return a * b; } }


26 of 33


7. előadás

GÖMB TÍPUS KONSTRUKTOROKKAL értékhalmaz művelethalmaz

Pont ×R { Gömb : R → Gömb, Gömb : Pont → Gömb, Gömb : Pont ×R → Gömb, BennevanE : Gömb × Pont →

L}

Gömb = ( Pont ×R, { Gömb, BennevanE } )


27 of 33


7. előadás

BŐVÍTETT GÖMB TÍPUS public struct Gomb { // mezők: public Pont c; public double r; // konstruktorok: public Gomb( Pont kozeppont ) { c = kozeppont; r = 10; } public Gomb( double sugar ) { c = new Pont( 0, 0, 0 ); r = sugar; } public Gomb( Pont kozeppont, double sugar ) { c = kozeppont; r = sugar; } // metódus: public bool BennevanE( Pont pont ) { ... } }


28 of 33


7. előadás

PÉLDÁNYOSÍTÁS public static void Main() { // változó deklaráció, nem történik memóriafoglalás, "p0" még nem létezik, // nem lehet a pontra hivatkozni addig, amíg az összes mezeje értéket nem kap Pont p0; // objektum létrehozása az alapértelmezett konstruktorral, memóriafoglalással // "p1" létrejött, lehet a pontra és mezőire hivatkozni, bár a mezők a // fordítóprogram által adott értékekkkel lettek inicializálva var p1 = new Pont(); // objektum létrehozása a 2 paraméteres konstruktorral var p2 = new Pont( 3, 3 ); // objektum létrehozása a 3 paraméteres konstruktorral var p3 = new Pont( 1, 4, 2 ); // gömb létrehozása konstruktorral var gomb = new Gomb( 12 ); }


29 of 33


7. előadás

3. OPERÁTOROK TÚLTERHELÉSE lehetőségünk van arra, hogy a műveleteinket operátorokkal valósítsuk meg úgy használhatók, mint a beépített operátorok, de a működésüket mi határozzuk meg kötött a paraméterek száma éa a visszatérési érték megléte, de a típusok tetszőlegesek az unáris, a matematikai, a logikai és a relációs operátorok terhelhetők túl


30 of 33


7. előadás

PONT TÍPUS == ÉS != OPERÁTORAI értékhalmaz művelethalmaz

R × R × R = R3 { Pont : R → Pont, Pont : R × R → Pont, Pont : R × R × R → Pont, == : Pont × Pont → L, != : Pont × Pont → L }

Pont = ( R

3


, { Pont, ==, != } )

31 of 33


7. előadás

AZ OPERÁTOROK MEGVALÓSÍTÁSA public struct Pont { // mezők: public double x; public double y; public double z; // konstruktorok: public Pont( double p2 ) {...} public Pont( double p1, double p2 ) {...} public Pont( double p1, double p2, double p3 ) {...} // operátorok: public static bool operator ==( Pont p1, Pont p2 ) { return ( p1.x == p2.x && p1.y == p2.y && p1.z == p2.z ); } public static bool operator !=( Pont p1, Pont p2 ) { // itt már az imént definiált == operátort hívjuk meg a két ponton return ! ( p1 == p2 ); } }


32 of 33


7. előadás

FELADAT Ellenőrizzük, hogy ütközött-e valamely ismeretlen tárgy az űrteleszkóppal Használjuk az Eldöntés (létezik) programozási tételt public static void Main() { ... bool utkozes = LetezikE( pontok, gomb ); ... } static bool LetezikE( List pontok, Gomb gomb ) { int i = 0; while( i < pontok.Count && pontok[i] != gomb.c ) { ++i; } return ( i < pontok.Count ); }


33 of 33

Bánsághi Anna 2014 Bánsághi Anna 1 of 33

Recommend Documents