ProgramozásMódszertan
1. előadás’2005[SzP1]
(vázlat)
1. Adatok jellemzői
1.1. Azonosító
Az a jelsorozat, amellyel hivatkozhatunk a tartalmára, amely által módosíthatjuk tartalmát.
Például:
|
i, j, n, a |
– változók nevei (szimbolikus nevek) |
|
p, -128, 3.14, "Eredmény=", IGAZ |
– konstansokat azonosító jelsorozat |
|
Megjegyzés: |
x |
:= |
x+1 |
|
|
címhivatkozás |
|
értékhivatkozás |
|
|
vagy |
|
|
|
|
Feldolgoz(x) |
– |
eljáráshívásnál
nem látszik, hogy x az adat címét vagy értékét jelenti |
|
|
Eljárás
Feldolgoz(Konstans x:TX): |
– |
Ez
már világos beszéd! |
1.2. Hozzáférési jog
Adatokat módosítani, illetve értéküket lekérdezni, használni lehet; eszerint egy adat hozzáférés szempontjából négyféle lehet:
|
|
módosítható |
lekérdezhető |
|
|
Független |
Nem |
Nem |
Független |
|
Input |
Nem |
Igen |
Konstans |
|
Output |
Igen |
Nem |
Virgin |
|
I/O |
Igen |
Igen |
Változó |
|
Háttértár-adat |
|
|
Memória-adat |
1.3. Kezdőérték
A születéskor hozzárendelt érték. Változóknál deklarációban kaphat értéket, vagy eleve van típushoz rendelt kezdőérték, esetleg speciális ’nem definiált’ érték, s így akkor mód van hivatkozás ellenőrzésre is (virgin)!
1.4. Hatáskör
A programszöveg azon tartománya, amelyben az adathoz a hozzáférés lehetséges.
Gondoljunk a blokkstruktúrájú programozási nyelvek egymásba ágyazódó adatdeklarációira! Így beszélhetünk: globális és lokális (sőt saját) adatokról.
A hatáskört „színezi” a láthatóság kérdése: ha egy adat azonosítója megegyezik egy olyan adatéval, amelynek hatáskörébe esik, akkor azt elérhetetlenné teszi a saját hatáskörében, hiszen az adott név alatt neki van elsősége.
|
Példa: |
|
… Konstans … Eljárás
E1(Változó x:TX2): … |
1.5. Élettartam
A futási időnek az az intervalluma, amelyben az adat azonosítója mindvégig ugyanazt az objektumot jelöli.
Meggondolandó a hatáskörrel való kapcsolat! (Globális, lokális adatok hatásköre és élettartama, továbbá a „dinamikus”, azaz futásközben a programozó döntése szerint születő és megszűnő adatok. L. később!)
1.6. Értéktípus
Az adatoknak az a tulajdonsága, hogy értékei mely halmazból származnak (értékhalmaz) és tevékenységeknek (eljárások, függvények, operátorok) mely „készlete, amely létrehozza, felépíti, lerombolja és részekre bontja”, alkalmazható rá (asszociált műveletek).
2. Az értéktípus
2.1. Az értéktípusról általánosságban
Összetettség (strukturáltság) szempontjából:
- skalár (vagy strukturálatlan)
- összetett (más szóval strukturált)
Adatstrukturálási módok:
|
→ |
|||
|
→ |
Rekord |
||
|
(Megkülönböztetett) egyesítés |
→ |
Alternatív rekord |
|
|
Halmazképzés |
2A |
→ |
Halmaz |
|
Iterált-képzés |
A* |
→ |
Sorozatfélék |
2.2. Az asszociált műveletek osztályozása
Az asszociálható műveleteket csoportosítjuk:
- értékadás (azonos típusúak közötti adatmozgatás: másolatkészítés, értékmegosztás),
|
Példa: |
|
… Eljárás Eltol(Változó p:TPont;Konstans D:TPont): |
· típusátviteli függvények:
o Konstrukciós műveletek (strukturált érték létrehozása)
|
Példa: |
o Szelekciós operációk
|
Példa: |
|
… |
o Azonosság és más relációk
|
Példa: |
|
… Típus Konstans SNapEn= … |
|
Példa: |
|
… Konstans |
o Min- és Max-függvény, amelyek értelemszerűen csak rendezett típusok esetén léteznek.
|
Példa: |
|
… Konstans |
- Sorszám- (vagy Rend-) függvény
|
Példa: |
|
… |
o
Be/Ki műveletek (konverzió az
input/output és belsőábrázolás között)
|
Példa: |
|
… |
- Transzformációs
(a típuson értelmezett, a típusra képező függvények)
|
Példa: |
|
… |
- egyéb függvények.
3. Egyszerű Adattípusok
Alábbiakban definiáljuk az „eredendően” szerkezetnélküli ún. skalár típusokat, megadva ezek értékhalmazát, a hozzátapadó műveletek, relációk halmazát. Két típus „lóg ki” ezek közül. A szöveg (string) és a mutató típus. A szöveg típust azért soroljuk ide, mert a programozási nyelvek majd mindegyike fölkínálja, s így hozzátartozik az ún. elemi (natív) típusokhoz, másrészt abban jócskán eltér a későbbiekben tárgyalt összetettektől (s így oda még kevésbé illik), hogy elemeinek típusa nem választható meg szabadon. A mutató típus valóban szerkezet nélküli, hisz értékhalmaza a memóriacímek egy részhalmaza (ezért tárgyaljuk itt), de az is kétségtelen, hogy oly szorosan tapad valamely összetett típushoz, amely címét tartalmazza, hogy anélkül értelme sem lenne bevezetni.
A tárgyalt típusokról a következőket adjuk meg:
- Értékhalmaz
- Kezdőérték,
amit az ilyen típusú objektum létrejövetelekor kap.[1]
- Asszociált
műveletek
- (s esetleg) tipikus ábrázolása(i)
- (s néhány esetben) példa.
A rövid leírás kedvéért időnként alkalmazni fogjuk a Típ jelölést az éppen tárgyalt típusra való hivatkozásra. (Értelemszerűen akkor, amikor a típus nevét a programozó feladata megadni.) Származtatott típus esetén pedig gyakorta a TB az ún. bázistípusra (amelyből kiindulunk) utal.
3.1. Elemi adattípusok
3.1.1. Egész
|
Értékhalmaz |
-32768..32767 Ì
Z |
|
Kezdőérték |
0 |
|
Műveletek |
+, -, *, Div (egészosztás), Mod, - (unáris mínusz), ^ (pozitív egészkitevős hatványozás) =, <, ≤, ≥, >, ≠ |
|
Ábrázolás |
ún. kettes komplemens kódú |
Megjegyzés:
A
programozási nyelvek többféle értékhalmazzal is felkínálnak efféle típusokat.
Pl. a Turbo Pascal megkülönböztet BYTE, SHORTINT (8 bites); INTEGER, WORD (16-bites);
LONGINT (24 bites)… Ennek ellenére nem tartjuk fontosnak az algoritmikus nyelvben
ezeket megkülönböztetni, annál is inkább szükségtelennek gondoljuk, mert ha
kell a „szélsőséges értékeire” tudunk hivatkozni a Min’Egész és Max’Egész
típusfüggvénnyel anélkül, hogy letennénk a voksunkat bármelyik konkrét
értékhalmaz mellett.
3.1.2. Valós
|
Értékhalmaz |
???..??? Ì
R |
|
Kezdőérték |
0.0 |
|
Műveletek |
+ , - , * ,
/, - (unáris
mínusz), ^ =,
<, ≤,
≥, >,
≠ |
|
Ábrázolás |
ún. lebegőpontos
ábrázolás (pontosabb lenne, ha e típust racionálisnak neveznénk,
mert csak racionális számot képes ábrázolni), vagy |
Megjegyzések:
Vegyük észre, hogy ugyanazok a műveleti jelek most –ha hasonló jelentéssel is, de– mégsem egészen ugyanazzal a jelentéssel bírnak. (Polimorfizmus.)
Itt már föl sem vállaltuk az értékhalmaz pontosítását, mivel ez sokkal inkább implementáció-függő, mint az egész számoké.
3.1.3. Logikai
|
Értékhalmaz |
Hamis..Igaz Ì L |
|
Kezdőérték |
Hamis |
|
Műveletek |
nem, és,
vagy =, <,
≤, ≥, >, ≠ |
|
Ábrázolás |
0 ≡ Hamis,
–1 ≡ Igaz – azaz (valamely) egész típusra visszavezetés; |
3.1.4. Karakter
|
Értékhalmaz |
0..255 -kódú jelek |
|
Kezdőérték |
Min’Karakter |
|
Műveletek |
Karakter(.) – Karakter: Egész→Karakter =, <,
≤, ≥, >, ≠ |
|
Ábrázolás |
Valamely kódrendszer szerinti kód, mint előjelnélküli szám. (Fix bitszámú kód.) |
Megjegyzés:
Sokfajta kód rendszer létezik (legismertebbek: ASCII, UNICODE). Többségük fix bitszámú (ASCII 8 bites, UNICODE 16 bites), de elképzelhető változó bitszámmal dolgozó is. (L. Huffman-kódolás.)
3.1.5. (Absztrakt)Felsorolástípus
|
Értékhalmaz |
(konstans1, konstans2, ... , konstansN) (Típ jelölje a típus azonosítóját) |
|
Kezdőérték |
Min’Típ vagy NemDef |
|
Műveletek |
Következő(Típ-típusbeli kifejezés),
– Következő:
Típ→Típ U
{NemDef} =, <,
≤, ≥, >, ≠ (a felsorolás sorrendje egyben rendezés
is) |
|
Ábrázolás |
A minimálisan szükséges bitszámú (»log2(Számosság’Típ)) kód, mint előjelnélküli szám. |
Megjegyzések:
Az értékhalmazban szereplő ismétlődés nélküli, szimbolikus nevek (a típus konstansai) nem lehetnek más típus (pl. egy másik felsorolástípus) értékhalmazában, ez a feltétel amiatt szükséges, mert a fordítóprogram így mindig egyértelműen el tudja dönteni a konstans „hovatartozását”. Természetesen „…” nem szerepelhet a felsorolásban, mivel a fordítónak nincsenek „előzetes elképzelései” arról, hogy mik lehetnének ott a felsorolásban.
Mindazon típusokat, amelyek értékkészletét konstansainak egyszerű fölsorolásával adhatunk vagy adhatnánk meg diszkrét típusnak hívjuk. Tehát ilyen az Egész, a Logikai, a Karakter, de lehet bármilyen –a program írója által kreált– absztrakt konstansokat tartalmazó fenti absztrakt felsorolástípus is.
|
Típus |
3.1.6. (Rész)Intervallumtípus
Csak diszkrét típusból származtatható egyszerű típus. Jelöljük a bázistípust TB-vel.
|
Értékhalmaz |
konstans1..konstans2 Í TB |
|
Kezdőérték |
Min’Típ vagy NemDef |
|
Műveletek |
TB-vel megegyező műveletek (korlátozva persze az értékhalmazra) |
|
Ábrázolás |
TB-vel megegyező ábrázolás |
|
Példa: |
|
Típus |
Megjegyzések:
1. Érdekes anomáliára vezet a Sorszám és Típ típuskonstrukciós függvény következetes bevezetése. Miért?
2. Ha a diszkrétségtől eltekintünk, kiterjeszthető a Valósakra is az intervallumtípus-képzés. Ez persze csak azzal a többlettel képzelhető el, hogy egy lépésközt is megadunk a származtatáshoz (amelyre vannak persze elvárások).
3. További általánosítás lehetséges: nem első és utolsó elem által meghatározott része egy értékhalmaznak, hanem valamilyen (predikátummal definiált) tulajdonságnak eleget tevő elemeinek részhalmaza.
|
Példa: |
|
Típus |
3.1.7. Szövegtípus
|
Értékhalmaz |
MaxHossz darabnyi jelből álló karakterláncok
halmaza Ì Karakter* |
|
Kezdőérték |
’’ azaz üres-szöveg (Min’Szöveg) |
|
Műveletek |
+, Hossz(.), Balrész(.),
Jobbrész(.), Jele(.) := =, <,
≤, ≥, >, ≠ |
|
Ábrázolás |
Rekord(hossz:Egész,
jel:Tömb(1..MaxHossz:Karakter)) – Pascal-stílusú |
3.2. Mutató típusok
Az alcímbeli többes szám jogos, mert valójában tetszőleges (többnyire összetett) típushoz, mint bázistípushoz (TB) szervesen tartozhat egy-egy ilyen típus. Egy konkrét mutató típusú objektum csak egyfajta (nevezetesen TB-típusú) elemek kezdőcímeit hordozhatja. E szigorúság oka: az ellenőrizhetőség, biztonságosság.
|
Értékhalmaz |
Memóriacím, amely
valamely TB-típusú elem kezdőcíme, vagy Sehova |
|
Kezdőérték |
Sehova |
|
Műveletek |
Lefoglal(Változó m:Típ, Konstans e:TB) – az eljárás létrehoz a memóriában egy TB-elemet, amelynek értéke éppen ’e’, és a címét teszi ’m’-be; ha nincs elegendő hely, akkor ’m’-be Sehova érték kerül. Elhagyható a kezdőértéket definiáló paraméter, ekkor a TB-beli iniciális értékű elem keletkezik. Típ(Konstans m:Típ):TB – a függvény az ’m’-beli címnél kezdődő TB-elemet adja vissza értékként Felszabadít(Változó m:Típ) – az eljárás felszabadítja a memória ’m’-ben lévő címtől kezdődő TB-elemnyi tartományát, majd ’m’-be a Sehova érték kerül. := =
|
|
Ábrázolás |
Memóriacím |
Megjegyzések:
A Lefoglal művelet fent taglalt szemantikája is indokolja a szigorú típusosság kívánalmát!
A Pascal-beli Lefoglal művelet, a New, nem foglalkozik kezdőértékadással, sőt a helyfoglalás sikertelenségét sem közli a Sehova, vagyis a Nil értékkel. A Felszabadít, Dispose művelet sem törli a mutatót.
|
Példa: |
|
… Változó [vajon milyen
értékek vannak a bk(2..MaxN) elemekben; |
4. Összetett adattípusok – típuskonstrukciók
Helyesebb összetett típusok helyett típuskonstrukciókról beszélni, mivel valahány összetevő típusból hozunk létre, konstruálunk egy újat; s az ilyeneket létrehozni képes eszközöket típuskonstrukciós eszközöknek hívni.
Többnyire nem magától értetődő az ilyen struktúrák rendezése, ezért sem a Min’, sem a Max’ típusfüggvényt nem jelezzük. (Megjegyezzük: természetesen nem elképzelhetetlen –sőt!–, hogy utólag valamilyen rendezést rájuk is definiáljuk. Erről később még szó esik.)
A korábbi szokásos mondanivalók mellé bekerül a „konstrukció”, amelyben tisztázzuk az alkalmazás szintaxisát.
Rövidítés miatt a bázistípusokat sorszámozzuk és így jelöljük: TB1, TB2, …
4.1. Összetett típusok osztályozásai
A bázistípusok sokfélesége szerint –
- Heterogén (rekord, alternatív rekord)
- Homogén (sorozatfélék: tömb, lista…, halmaz; rekurzív típusok: lista, fa; gráf…)
Rákövetkezési reláció az elemei között –
- Nincs (értelmetlen: rekord, alternatív rekord; lehetne, de nincs: halmaz)
- Egyértelmű, kivéve a szélső elemeket (sorozatfélék: tömb, lista,…)
- Többszörös (rekurzív típusok közül a fa; gráf)
4.2. Rekord
|
Konstrukció |
Rekord(mező1: TB1, mező2: TB2 …) |
|
Értékhalmaz |
TB1´TB2´… |
|
Kezdőérték |
Az egyes
komponensekhez tartozó kezdőérték.
|
|
Műveletek |
Típ(Konstans m1: TB1, m2: TB2 …) – létrejön egy Típ típusú konstans m1, m2… mezőértékekből (konstrukciós operáció) objTip.mezői:TBi – a „szokatlan” szintaxisú művelet értéke az adott Típ típusú objektum (objTip) mezői mezőjének értéke… (szelekciós operáció) objTip.mezői:TBi:=ei – a „szokatlan” szintaxisú értékadás eredménye az adott Típ típusú objektum (objTip) mezői mezőjének értékül adja ei-t… := =, ≠ Be:, Ki: |
|
Ábrázolás |
A mezők folytonos memóriaterületre képezve, a felsorolás sorrendjében. |
4.3. Alternatív rekord
Olyan rekordféléről van szó, amelynek valamely mezőjétől (mezőitől) függ további mezőinek típusbesorolása.
|
Konstrukció |
Rekord( |
|
Értékhalmaz |
TB1´…TBK´…È(i=1..m)TBi,1´…TBi,ki |
|
Kezdőérték |
A nem
egyértelműsége miatt NemDef.
|
|
Műveletek |
A rekordhoz hasonlóan. |
|
Ábrázolás |
A mezők folytonos memóriaterületre képezve, a felsorolás sorrendjében, a hosszat a leghosszabb alternatívával számolva. |
|
Példa: |
|
… Típus Függvény Kontroll(Konstans
n:TNem Típus TSzemSzám=Rekord( TSzemély=Rekord( Konstans |
4.4. (Hatvány-)Halmaz
Csak diszkrét (többnyire nagyon is korlátozott számosságú) típusnak definiálhatjuk a hatványhalmaz-típusát.
|
Konstrukció |
Halmaz(TB) (Min’Típ=Æ..Max’Típ=TB-értékhalmaz,
a tartalmazás alapján rendezve) |
|
Értékhalmaz |
TB* |
|
Kezdőérték |
Üres halmaz
|
|
Műveletek |
Î (eleme), Ç (metszet), È (egyesítés), \ (különbség), Æ vagy Üres (üres halmaz létrehozás), Üres? (logikai értékű függvény) := =, < (Ì), ≤ (Í), ≥ (Ê), > (É), ≠ Be:, Ki: |
|
Ábrázolás |
Tömb(TB:Logikai) – azaz bitvektor az adott elem tartalmazása vagy nem tartalmazása szerint; Lista(TB) – tartalmazott elemeinek felsorolása [l. később] |
|
Példa: |
|
… Változó Konstans |
4.5. Tömb
|
Konstrukció |
Tömb(TIndex: TElem) |
|
Értékhalmaz |
TElemSzámoság(TIndex) |
|
Kezdőérték |
TElem
típus kezdőértékei
|
|
Műveletek |
objTip(i) (a
Típ típusú objTip tömb i. TElem típusú eleme), := =, ≠ |
|
Ábrázolás |
Az elemek folytonos memóriaterületre képezve, növekvő index sorrendben. (L. később) |
5. Sorozattípusok
Sorozattípusnak hívjuk azt a típust, amely
- homogén (azaz elemei egyetlen bázistípushoz tartoznak),
- egyértelmű rákövetkezési reláció van elemei között (az adott elemét legfeljebb egy elem követheti),
- egyetlen olyan eleme van, amelyet nem előz meg másik, s egyetlen olyan, amelyet nem követ.
5.1. Sorozatműveletek
5.2. Sorozatok ábrázolásának lehetőségei
|
|
Tartalom
ProgramozásMódszertan
1. előadás’2005 (vázlat)
2.1.
Az értéktípusról általánosságban
2.2.
Az asszociált műveletek osztályozása
3.1.5.
(Absztrakt)Felsorolástípus
4.
Összetett adattípusok – típuskonstrukciók
4.1.
Összetett típusok osztályozásai
5.2.
Sorozatok ábrázolásának lehetőségei