Ebben a leckében gyakorlatiasan vetjük föl az összetett adattípusok kérdését. Megvizsgáljuk, hogy miként könnyíti meg egyes nevezetes összetett típusok (rekord, vektor, a mátrix, illetve a szöveges fájl) ismerete a programozó dolgát, és miként kell beépíteni ezeket a programba. Hogyan bukkannak föl a feladat specifikációjában és az algoritmikus nyelvben.
Ebben a leckében gyakorlatiasan vetjük föl az összetett adattípusok kérdését. Azt vizsgáljuk főképpen, hogy miként könnyíti meg a programozó dolgát ezek ismerete és fölhasználása.
Újdonságnak csak a szöveges fájlok számítanak. A rekordok, vektorok miben létét már a korábbi leckék során tisztáztuk. A mátrixok fogalmáról ugyan nem esett szó, de – mint látni fogjuk – a tömbökről (azaz vektorokról) szerzett tudásunk jól alkalmazható ennek megismerésénél.
Mit is tudunk a rekordról? Dióhéjban ennyit a lényegéről: a rekord segítségével több (akár különböző) típusú adatot „egyesíthetünk” egyetlen egésszé. A rekord felhasználásával létesíthetünk egy új típust, amely a definiáláskor felhasznált típusokból tevődik össze.
Matematikai fogalmainkkal úgy is fogalmazhatnánk: az összetevők direktszorzatával definiáljuk a keletkezett új típust.
Egy ilyen rekordtípusú adat kezeléséhez bevezettünk ún. konstrukciós és szelekciós műveleteket. Az előbbivel létre tudunk hozni ilyen típusú adatot, az utóbbiakkal az egyes összetevők hozzáférését biztosítjuk. Az egyes összetevőknek egyedi nevet kell adni a definiáláskor, ami egyben a hozzáférést lehetővé tevő műveletben is elő fog bukkanni. Ezt hívják mezőnévnek, amit azonosít, azt mezőnek.
Definiálás:
Típus
TDátum=Rekord(év,hó,nap:Egész)
TSíkPont=Rekord(x,y:Valós)
THallgató=Rekord(kód:Egész, név:Szöveg, szül:TDátum)
Nem rossz szokás a típusokat „T” betűvel kezdeni, mert így „ránézésre” is világos a funkciója.
A további példákban felhasználjuk az imént definiált típusokat.
Konstruálás:
Konstans
isz0:TDátum(1900,1,1) [az időszámítás „kezdete”]
NeumannJános:TDátum(1903,12,28)
O0:TSíkPont(0,0) [origó]
GipszJakab:THallgató(1234567890,’Gipsz Jakab’,TDátum(1990,1,1))
Változó
ma:TDátum [kezdőérték explicit megadása nélküli létrehozás]
fiktívHallgató:THallgató(0,’’,isz0) [változó deklaráció kezdőértékadással]
A példában elképzelhető lenne a mezőnevek explicit kiírása is. Pl. így:
GipszJakab:THallgató(kód:1234567890,név:’Gipsz Jakab’,szül:TDátum(év:1999,hó:1,nap:1))
Ha nincsenek a mezőnevek kiírva, akkor a konstansok felsorolása követi a definiálásbeli sorrendet.
Szelekció (mezőelérés):
… NeumannJános.év … [Neumann János születési éve]
… O0.y … [az origó y-koordinátája]
… GipszJakab.szül.hó … [GipszJakab születési idejének hónapja]
A programozásban a vektor a tömb más néven. A lényege, hogy sok azonos típusú elemet egyesítünk a vektor fogalmában egy adategységgé. Itt is egy típuskonstrukciós eszközről van szó, hasonlóan a rekordhoz, és éppúgy kell, legyen konstrukciós és szelekciós műveletének.
Nézzünk összefoglalóan néhány példát!
Konstrukció:
Típus
TSíkPont=Tömb[1..2:Valós] [a korábbi síkbeli pontok egy másfajta tipizálása]
TNevek=Tömb[1..MaxN:Szöveg] [MaxN db nevet tartalmazó vektorok típusa]
Konstans
O0:TSíkPont(0,0) [konstans deklaráció: origó]
Változó
Névsor:TNevek [kezdőérték explicit megadása nélküli létrehozás]
Egyes nyelvek (pl. C++) előszeretettel kínálják föl a programozóknak a típusdefiniálás nélküli deklarálás lehetőségét. Ilyen esetben név nélküli (ún. anonim) típus „jön létre”, amelyre persze egyebütt sem lehet hivatkozni. Ez megnehezítheti a paraméterátadást.
Konstrukció:
Konstans
O0:Tömb[1..2:Valós](0,0) [konstans deklaráció: origó]
Változó
Névsor:Tömb[1..MaxN:Szöveg] [kezdőérték explicit megadása nélküli létrehozás]
Nem ördögtől való feltételezés, hogy ne csak az adatok deklarációja során létesülhessen tömb. Nyilvánvaló, hogy ehhez egy olyan művelet definiálására van szükség, amelyet a végrehajtás során adhatunk ki, s amelynek a létrehozandó tömbváltozó és a kívánt elemszáma a paramétere. Vannak programozási nyelvek (pl. a C++), amelyek tartalmaznak ilyen dinamikus konstrukciós műveletet.
Végezetül lássuk a vektor indexelés operátorát!
Szelekció (elemelérés):
… O0[1] … [az origó 1. koordinátája]
… Névsor[i] … [a névsor i. eleme]
A mátrix „különlegessége” – a vektorhoz képest – az, hogy nem egy, hanem kettő indexszel jelölhetők ki az elemei, azaz beszélhetünk a mátrix sorairól (ezt jelöltük ki az első indexével) és oszlopairól (ezt a második indexe határozta meg). Nyilván a definiáláskor (de legkésőbb létrehozásakor) kell megadni a sorainak és oszlopainak a számát.
Be kell valljuk, hogy van olyan elképzelésű vektor-, s így mátrixfogalom is, amely megengedi a méret változtatását a program végrehajtása során, akár többször is. Ez különleges figyelmet igényel a használat során, amely most indokolatlanul vonná el a figyelmünket a lényegtől, ezért a továbbiakban a „statikusan”, azaz a deklaráció során létrejövő (s így a futás során már nem változó hosszúságú) tömbökkel (azaz vektorokkal, mátrixokkal …) fogunk csak foglalkozni.
Konstrukció:
Típus
TMárix=Tömb[1..MaxN,1..MaxM:Valós] [egy MaxN*MaxM-es mátrix tipizálása]
TKeresztRejvény=Tömb[1..10,1..10:Karakter] [egy 10*10-es keresztrejtvény típusa]
Változó
m:TMátrix [kezdőérték explicit megadása nélküli létrehozás]
rejtvény:TKeresztRejtvény [kezdőérték explicit megadása nélküli létrehozás]
Szelekció (elemelérés):
… rejtvény[1,1] … [a rejtvény 1,1 jele]
Egyes programozási nyelvek (pl. a C++) azt a „filozófiát” követve, hogy a mátrix tekinthető vektorok vektorának, a fentitől eltérő szintaxissal írják elő az elemhivatkozást:
… rejtvény[1][1] … [a rejtvény 1,1 jele]
A szöveges fájlok olyan, háttértárolón tartózkodó adattömeg, amely minden eleme karakter típusú, és szekvenciális (elejétől a vége felé haladó) feldolgozást tesz lehetővé. Ehhez az adattípushoz is tartoznak konstrukciós és szelekciós műveletek. A szöveges fájlok kezeléséről elsőként azt kell tudnunk, hogy csak olvasni vagy írni tudunk belőle/belé. E miatt beszélhetünk input szövegfájlról és output szövegfájlról.
A konstrukciós művelet során létrejön egy „memóriaablak” (puffer), amelyen keresztül kezelhetjük a fájlt. A szelekciós műveletekkel ebből olvashatunk, vagy ebbe írhatunk (persze csak az egyiket tehetjük egy időben), az operációs rendszer gondoskodik arról, ahogy az ablak mindig a fájl megfelelő, soron következő része „fölött” legyen, vagyis a fájl és az ablak tartalmi szinkronjáról. Egyszerűen szólva mindig a fájl elejéről (az első, eddig még el nem olvasott karakterrel kezdve) tudunk olvasni, és mindig a fájl végére (az utoljára kiírt mögé) tudunk írni.
A konstrukció szokatlan módon két lépésben zajlik le: az első során helyet foglalunk a memóriában a fájlkezeléshez (a puffernak), a második lépésben a tényleges fájlhoz kapcsoljuk a programunkat (a puffert). Ezt látjuk az alábbi példában.
Konstrukció:
Változó
iF:InputSzövegFájl [létrejön a memóriában input céljára a puffer]
oF:OutputSzövegFájl [létrejön a memóriában output céljára a puffer]
iFN,oFN:Szöveg [a fájlneveket tartalmazó változók]
…
Megnyit(iF,iFN) [az iF pufferen keresztül olvassuk az iFN nevű fájlt]
Megnyit(oF,oFN) [az oF pufferen keresztül írjuk az oFN nevű fájlt]
…
Az nyilvánvaló, hogy az iFN és az oFN nem lehet azonos, mert ez azt jelentené, hogy egyidejűleg akarnánk olvasni a fájlból, és írni a fájlba, amit nem lehet!
Vegyük észre, hogy itt elmaradt az összetett típusoknál eddig szokásos típusdefiniálás! Ez nyilvánvaló ok miatt történt; hiszen a tárgyalt szöveges fájltípusok nem típuskonstrukciós eszközökként üzemelnek (mint a Rekord, vagy a Tömb), hanem teljesen konkrét típusok (mint az Egész, a Szöveg vagy a Logikai), amelyeknek a nevük előre rögzített (InputSzövegFájl, ill. OutputSzövegFájl).
Szelekció (elemelérés):
Változó
s:Szöveg
k:Karakter
…
SorOlvas(iF,s) [az s-be bekerül az aktuális sor (sorvégjelig, sorvégjel nélkül)]
Olvas(iF,s) [az s-be bekerül az aktuális sor tartalma az első elválasztó jelig]
Olvas(iF,k) [a k-ba bekerül az aktuális karakter]
… Vége?(iF) … [válaszol arra a kérdésre, hogy beolvastuk-e már az utolsó karaktert]
…
SorÍr(oF,s) [sorvégjellel lezárva a fájl végére írja s-et]
Ír(oF,s) [a fájl végére írja s-et, elválasztójelet nem ír ki]
Ír(oF,k) [a fájl végére írja k-t, elválasztójelet nem ír ki]
…
Ahogy a fájlhasználat egy nyitó „szertartással” kezdődött, ugyanígy egy záró „szertartással” zárul. Ehhez tartozik a Lezár művelet.
Szelekció (elemelérés):
…
Lezár(iF) [megszünteti a program-fájl kapcsolatot]
Lezár(oF) [kiírja a fájlba a puffer maradékát, és megszünteti a program-fájl kapcsolatot]
…
A kapcsolat megszüntetése után lehetővé válik, hogy ugyanazt a fájlt akár ez a program, akár másik (újra)használhassa.
Most egy feladat megoldásán keresztül bemutatjuk a rekord-fogalom használatának „hétköznapjait”. Megadjuk az alább kitűzött feladat megoldását rekord felhasználása nélkül és annak felhasználásával.
Adott N ember vezeték- és keresztneve, valamint a születési éve. Melyik évben született az, akinek a legtöbb betűből áll a neve?
Először a rekord ismerete nélküli megoldást vázoljuk. Íme a specifikáció:
Bemenet
N:Egész
VezNevek:Tömb[1..N:Szöveg], KerNevek:Tömb[1..N:Szöveg]
SzülÉvek:Tömb[1..N:Egész]
Kimenet
LhnÉv:Egész
Előfeltétel
N≥1 és ∀i∈[1..N]: Hossz(VezNevek[i])>0 és Hossz(KerNevek[i])>0
Utófeltétel
∃i∈[1..N]: LhNév=VezNevek[i]+KerNevek[i] és ∀j∈[1..N]: Hossz(LhNév)≥Hossz(VezNevek[j]+KerNevek[j]) és
LhnÉv=SzülÉv[i]
Vegye észre, hogy a kis- és nagybetűk megkülönböztetendők az azonosítókban! Az LhNév „lokális” változó a leghosszabb nevet tartalmazza, amíg az LhnÉv a „leghosszabb nevű évét”.
„Ordít”, hogy az alkalmazandó tétel a maximumkiválasztás. Az algoritmus tehát az alábbi:
Figyeljük meg, hogyan alakul át a specifikáció és az algoritmus, ha rekordokból álló tömbként képzeljük el a bemeneti adatokat!
Bemenet
N:Egész
NevekÉvek:Tömb[1..N:TNévÉv], TNévÉv=Rekord(vez,ker:Szöveg,év:Egész)
Kimenet
LhnÉv:Egész
Előfeltétel
N≥1 és ∀i∈[1..N]: Hossz(NevekÉvek[i].vez)>0 és Hossz(NevekÉvek[i].ker)>0
Utófeltétel
∃i∈[1..N]: LhNév=NevekÉvek[i].vez+NevekÉvek[i].ker és ∀j∈[1..N]: Hossz(LhNév)≥Hossz(NevekÉvek[j].vez+NevekÉvek[j].ker) és
LhnÉv=NevekÉvek[i].év
… és az algoritmus:
Az előző feladatban egy tömbnek rekordok voltak az elemei. Miért ne lehetne ez fordítva is, azaz egy rekordba tömbök ágyazva? Erre példa az alábbi feladat.
Egy ember a vagyonát többféle pénznembe fektette. Adjuk meg, mennyi most a vagyona forintban! Ismerjük az egyes pénznemek közötti átváltás pillanatnyi állását.
Bemenet
Pénzek:Rekord(pnDb:Egész, pnemek:Tömb[1..pnDb:Szöveg], mennyek:Tömb[1..pnDb:Valós])
Konstans PénzNemek:Tömb[1..MaxPnDb:Szöveg]=(…), Átvált:Tömb[1..MaxPnDb,1..MaxPnDb:Valós]=(…)
Talán segít a megértésben a mezőnév-magyarázat. pnDb: az ember által birtokolt pénznemek száma; pnemek: a pénznemek neveit tartalmazó tömb; mennyek: az egyes pénznemek mennyiségét tartalmazó tömb. A PénzNemek tömbben tároljuk az összes (MaxPnDb) lehetséges pénznem nevét, amik közül van pnDb≤MaxPnDb darab a vizsgált személynek; az átvált mátrix minden pénznem-pár közötti átváltás szorzóját tartalmazza.
A konstans adatokat most – egyszerűség kedvéért – nem láttuk el kezdőértékkel. De nyilvánvaló, hogy ez – valós esetben – nem elkerülhető.
Kimenet
vagyon:Valós
Az előfeltételben formalizálni kell a következőket:
Ennek formalizálását az Olvasóra bízzuk.
Hasonlóképpen házi feladatként meggondolandó az utófeltétel is! Segítségként eláruljuk, hogy az összes vagyon kiszámítása a forinttá konvertált valutaátváltások összegezésével történik, ami tehát a sorozatszámítás tétellel valósítható meg. A valutaátváltásokhoz megtalálni a szorzót, egy kiválasztás tételre emlékeztető részfeladat. (Az előző feladatpár utófeltételében ez utóbbihoz található minta.)
Ne keseredjen, ha esetleg most beletört a bicskája ebbe a feladatba! Ilyen, több programozási tétel egymásba ágyazását tartalmazó feladat megoldását csak a későbbiekben várunk el. Most az adatok ábrázolása szempontjából volt érdekes ez a feladat.
Az előző feladat megoldása után az algoritmus elkészítése már nem okozhat gondot. Kérem, készítse el a megfelelő struktogramot!
Súgás gyanánt: két egymásba ágyazott ciklus végzi a lényegi számítást. A külső ciklus a sorozatszámításhoz tartozik, az összegzést végzi; a belső ciklus – még a növelés előtt – a valutasorszám kiválasztását végzi.
Ne keseredjen, ha esetleg most beletört a bicskája ebbe a feladatba! Ilyen, több programozási tétel egymásba ágyazását tartalmazó feladat megoldását csak a későbbiekben várunk el. Most az adatok ábrázolása szempontjából volt érdekes ez a feladat.
Természetesen a rekordban – esetlegesen – tárolt tömbök mérete nem feltétlenül azonosak. Most a feladat miatt véletlenül ilyenek.
A mátrixos feladatok megoldása sokszor semmi ötletet nem igényelnek a „hasonmás” vektoros feladatpárjához képest. Amíg a vektoros feladatban az adatsoron egyetlen ciklussal haladunk végig, addig a mátrix esetén az elemeken való végighaladást két, egymásba ágyazott ciklus végzi: például úgy, hogy a külső ciklus a sorokon haladást szervezi, a belső pedig (az éppen rögzített indexű) sor elemeit veszi sorra.
Igaz, ha a feladat olyan, hogy a megoldáshoz nem feltétlenül kell az összes elemen végigmenni, azaz egy közbülső elemnél is vége lehet az algoritmusnak, akkor már kérdések vetődnek föl a szervezést illetően. Ilyenek:
Nos, a válasz megadásához legjobb, ha pl. az eldöntés tétel mátrixos változatát elemezzük!
Induljunk ki abból, mi is történik az alap algoritmus végrehajtása közben! Madártávlatból szemlélve, ezt érzékelhetjük:
Nem tudnánk ugyanezt tenni akkor, ha az adatokat mátrixban helyeztük el? Dehogyis nem!
Ezt az átalakítást foglaljuk össze az alábbi ábrapárban:
Tömbös, alapváltozat | ⇒ | Mátrixos változat |
---|---|---|
Az 'eldöntés tétel' alap algoritmusa, struktogrammal. | ⇒ | Az 'eldöntés tétel' mátrixos algoritmusa, struktogrammal. |
Abból indulunk ki ebben a tantárgyunkban, hogy a szöveges fájlok célja a hagyományos, klaviatúra-bemenet, illetve képernyő-kimenet helyettesítése (a kényelmes tesztelés megvalósítása kedvéért).
Ebből a feltevésből következik, hogy be kell iktassunk a fájlokkal dolgozó programunkba kétféle kóddarabot, annak nyitó és záró „szertartásaként”. A szertartás közi kód a szokásos transzformációkat végzi most is, de már fájlok nélkül. Azaz a beolvasás a program lényegi paramétereit megtestesítő változókba történik, egyszerre, egyetlen, összefüggő fázisban; majd a számítások után a program lényegi kimeneti változóit kell – szintén – egyszerre, egyetlen, összefüggő fázisban fájlba írni.
A többlet meggondolni való összesen annyi, hogy a fájlok szerkezete milyen legyen. Ha ezt a döntést meghoztuk, el kell készítenünk azt az eljárást, amely a program megfelelő paraméterváltozóit vagy feltölti a már ismert szerkezetű fájlból, vagy kiírja a megadott szerkezetűbe.
A bemeneti fájlok szerkezete akkor válik érdekessé, ha egy vagy több sorozatot tartalmaz. Erre javaslunk lehetőségeket az alábbiakban.
Tegyük föl, hogy egy N-elemű X számsorozat alkotja a bemenetet. Továbbá a céljainknak megfelelően feltesszük a bemenet helyességét.
sorindex | tartalom | megjegyzés |
---|---|---|
1. | N | a sorozat hossz |
2. | X[1] | a sorozat első elem |
… | … | |
i. | X[i-1] | a sorozat i-1. eleme |
… | … | |
N+1. | X[N] | a sorozat utolsó eleme |
A beolvasás egy skalárbeolvasásból, és egy olyan N-es, számlálós ciklusból áll, amely ciklusmagja egyetlen sorban elhelyezkedő számot olvas be.
A leírtak alapján készítse el a beolvasó eljárás struktogramját!
sorindex | tartalom | megjegyzés |
---|---|---|
1. | X[1] | a sorozat első elem |
.. | … | |
i. | X[i-1] | a sorozat i-1. eleme |
… | … | |
N. | X[N] | a sorozat utolsó eleme |
Ebben az esetben a beolvasás addig tart, amíg a fájlban van még adat.
A leírtak alapján készítse el a beolvasó eljárás struktogramját!
sorindex | tartalom | megjegyzés |
---|---|---|
1. | N | a sorozat hossz |
2. | X[1]•X[2]•…•X[i]•… •X[N] | a sorozat összes eleme |
A számok közötti elválasztó jelet a „•” jel szimbolizálja. Ez leggyakrabban a szóköz jel, de programozási nyelvektől függően lehet más is. Az algoritmus az első változat algoritmusától abban tér el, hogy az itteni ciklusban nem sorolvasás (SorOlvas), hanem elemolvasás (Olvas) található.
A leírtak alapján készítse el a beolvasó eljárás struktogramját!
Bonyolódhat a beolvasás, ha a tömbelem nem skaláradat, hanem például rekord, vagy maga is tömb (azaz végső soron mátrix). A bonyolódás egyik oka, hogy amíg a számbeolvasás esetében általános megállapodás, hogy a szóköz elválasztójelként működik, addig szöveg típusú adatok esetén van olyan programozási nyelv, amely csak a sorvégjelet tekinti ilyennek. (A C++ esetében a szöveg típusú adatok közt is a szóköz elválasztójelként funkcionál.)
A kimeneti fájlok szerkezete akkor válik érdekessé, ha egy vagy több sorozatot tartalmaz.
Az előbbi fájlszerkezet-ajánlatok itt is megismételhetők, sőt lényegében az algoritmusok szerkezete is nagyban hasonlít majd az ott megalkotottakra.
Készítse el a fentiek mintájára a kiíró eljárások struktogramjait!