Rekord adattípus
Rekord típusok¶
Amikor ugyanolyan típusú adatokból kell egyszerre többet kezelni, akkor láttuk, hogy megoldást jelentett a tömb adattípus, ahol a tárolandó elemek típusának és darabszámának függvényében meg tudtuk adni azt az adat típust, amivel egyszerűen tudtuk hivatkozni az összefogott több változót. A különböző problémák megoldása közben gyakran előfordul, hogy különböző típusú, de logikailag összetartozó adatelemek együttesével kell dolgoznunk. Az ilyen adatok tárolására szolgálnak a rekord típusok, ezek létrehozása pedig a rekord típusképzések.
Szorzat-rekord adattípus¶
Legyen egy személyünk, akit szeretnénk jellemezni az adataival, mint amilyen a neve, telefonszáma, címe. Az egyes adatok típusa különböző, de minden esetben együtt kell őket kezeljük, adott személyhez rendelve. Jó lenne ilyenkor, ha ezek az adatok valahogy össze lennének fogva, és világosan látszódjon, hogy adott név, cím, illetve telefonszám melyik személyhez tartozik. Az ilyen esetek kezelésére való a szorzat-rekord adattípus.
Szorzat-rekord absztrakt adattípus¶
Legyenek \(T_1, \dots, T_k\) tetszőleges típusok. Képezzük ezek direktszorzatát, azaz a \(T= T_1\times \dots \times T_k=\{(a_1, \dots ,a_k) | a1\in T_1, \dots ,a_k\in T_k\}\) értékhalmazt. Azaz a típus elemi olyan \(k\)-s adatkupacok, amelyekben az \(i\). adat a \(Ti\) típus egy eleme.
A \(T\) halmazon is értelmezhetünk kiolvasó és módosító műveletet, mint a tömb típus esetén, de a k eltérő típus miatt most k számú kiolvasó és módosító műveletetre lesz szükségünk. Az új adattípusra a \(T\)=Rekord(\(T_1,\dots,T_k)\) jelölést használjuk és szorzat-rekordnak vagy struktúrának nevezzük.
A szorzat-rekord absztrakt adattípus műveleteit az alábbi táblázat foglalja össze:
Művelet megnevezése | Művelet leírása |
---|---|
Kiolvas_i (\(\rightarrow\) A : T , \(\leftarrow\) x :Ti ) |
Az A T típusú szorzat rekord i . mezőjét kiolvasó művelet, amely az i . mező típusának megfelelő x változóba teszi a kiolvasott mező értékét. |
Módosít_i (\(\leftrightarrow\) A : T ; \(\rightarrow\) x :Ti ) |
Az A T típusú szorzat rekord i . mezőjét módosító (beállító) művelet, amely az i . mező típusának megfelelő x változót értékül adja az i . mezőnek. |
Értékadás ( \(\leftarrow\) A :T ; \(\rightarrow\) X : T ) |
Az A T típusú szorzat rekord változónak értékül adja az X T típusú szorzat rekord változót. |
A szorzat-rekord, avagy a struct
virtuális adattípus¶
A \(T\)=Rekord(\(T_1,\dots,T_k)\) típust C-ben a struct
kulcsszóval definiáljuk:
1 2 3 4 5 |
|
Amikor egy struktúra típust definiálunk, akkor tulajdonképpen felsoroljuk a struktúrában az őt alkotó mezőket.
A fenti típusdefiníciónál azt látjuk, hogy a struct
kulcsszó után is van egy T
elnevezés, illetve magát a típust is T
-vel neveztük el.
Az első T
a struktúra neve, ami akár el is maradhatna, a második T
viszont az újonnan, a typedef
által bevezetett típus neve.
E kettő akár lehetne más is. Miért szükségesek ezek egyáltalán?
Ha a struktúrának nem adunk nevet, és nem is definiálunk hozzá egy új típust, akkor mindannyiszor, amikor adott elemeket tartalmazó struktúra változót szeretnénk létrehozni, le kell írni a teljes struktúra definícióját.
Ez persze már túl hosszú ahhoz, hogy ezt többször megadjuk.
Így ha van neve a struktúrának, akkor a következő esetben már struct T
is elég a megadásához, ha pedig típust is képeztünk belőle, akkor a típusképzés után már a T
típusazonosító is egyértelműen hivatkozza az adott struktúrát.
A fenti típusképzésben az M1
,\(\dots\), Mk
azonosítókat mezőazonosítóknak (tagnak, membernek) hívjuk és lokálisak a típusképzésre nézve.
Az absztrakt típus műveletei mezőhivatkozások segítségével valósíthatóak meg.
A mezőhivatkozásra a .
operátort használjuk. Ez egy olyan rekordokon értelmezett művelet C-ben, ami nagyon magas precedenciával rendelkezik és balasszociatív (azaz előbb meg kell határozni, hogy mely struktúra változóra hivatkozunk, és csak azáltal tudjuk elérni a konkrét mezőt).
Egy rekordra a mezőkiválasztás operátort (megfelelő mezőnévvel) alkalmazva a rekord mezőjét változóként kapjuk vissza.
Művelet absztrakt szinten | Művelet virtuális megvalósítása |
---|---|
Kiolvas_i (\(\rightarrow\) A : T , \(\leftarrow\) x :Ti ) |
x = A.Mi |
Módosít_i (\(\leftrightarrow\) A : T ; \(\rightarrow\) x :Ti ) |
A.Mi = x |
Értékadás ( \(\leftarrow\) A :T ; \(\rightarrow\) X : T ) |
A = X |
Példa szorzat-rekord megvalósításra¶
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
|
A fenti példában láthatjuk, hogy a struct
kulcsszó után nem kell feltétlenül megadni egy nevet, illetve az sem kell, hogy adott struktúrához mindig definiáljunk egy külön típust.
A SzemelyTip
be beágyazott struktúránál nincs is erre szükség, hacsak nem akarjuk a név adatokat külön, a beágyazó típusoktól független is használni.
A struct
fizikai típus¶
Mivel a struktúra egy összetett adat, így az, hogy ő konkrétan mekkora részt foglal a memóriában függ attól, hogy a benne levő típusok megkorák, illetve tudnunk kell azt, hogy ezek hogy tárolódnak.
Mivel egy struktúra adatai összetartoznak, akárcsak a tömb elemei, így számukra egy összefüggő memóriaterület kerül lefoglalásra deklarációkor.
Mivel minden mezőt tudni kell eltárolni, így éretlemszerűen csak az egyes mezők méretének ismeretében tudjuk megadni az E
struktúra teljes méretét: sizeof(E) = sizeof(T1) + ...+ sizeof(Tk)
+ igazítás.
Valamennyi mező a deklaráció sorrendjében egymást (a mezők méretét és az esetleges igazítást is figyelembe véve) követő, növekvő memóriacímen kezdődik.
Az első mező memóriacíme megegyezik a teljes struct
típusú érték címével (az eltolása, offset-je 0).
Példa: eltelt idő struktúrával¶
- Problémafelvetés és specifikáció: A korábbi eltelt idő problémához térjünk vissza, de úgy készítsük el a megoldásunkat, hogy abban az összetartozó óra és perc adatokat egyben ábrázoljuk.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
|
A megoldásban létrehoztunk egy ido_t
nevű struktúra adattípust.
Ennek két mezője van, egy ora
és egy perc
, amik az adott nap egy konkrét időpontját írják le.
Az eredeti programot úgy kell átírnunk, hogy mindenhol, ahol ilyen összetartozó óra-perc adatok voltak, ott egy ido_t
változóval helyettesítjük a korábbi két adatot.
Bitmezők¶
Sok esetben egy-egy információt jóval kisebb tárhelyen el lehetne tárolni, ha nem kellene a használt adattípus valamennyi bitjét felhasználni. A C nyelv lehetővé teszi egy bájton belüli bitek elérését magas szinten, bitmezős struktúrák segítségével. Használhatjuk pl. hardver-programozáshoz szükséges bitsorozatok magas szintű kezelésére (driverek írásához), vagy jelzőbitek (flag-ek) tömör elhelyezésére. A fizikai megvalósítás gépfüggő.
A bitmezőket a struktúrákon belül használhatjuk (akár a "normális" mezőkkel kombinálva is). A különbség az, hogy meg kell adni a tároláshoz szükséges bitek számát.
Például:
1 2 3 4 5 6 7 8 9 10 |
|
Miért jó ez?
Bitmezők nélkül az alábbi struktúra legalább 6 bájt lenne, így viszont csak 2 (1+1+2+4+2+6=16 bit az pontosan 2 bájt, ami pont egy unsigned short int
mérete):
1 2 3 4 5 6 7 8 |
|
A ->
operátor¶
Legyen tp
egy struktúra típusú változóra mutató pointer.
Ilyenkor ha a struktúra egy mezőjére szeretnénk hivatkozni, azt a (*tp).mezonev
alakban tudunk.
A zárójelezés fontos, mivel a mezőkiválasztás .
művelete magasabb precedenciájú, mint a *
dereferencia művelet.
Mivel a C nyelvben sokszor van szükség az ilyen jellegű hivatkozásokra, ezért bevezettek egy olyan műveletet, amely hatása a fentivel egyenértékű, de egyszerűbb alakban írható.
Ennek a műveletnek a jele a ->
, és egy pointer által megmutatott struktúra egy mezőjének kiválasztására alkalmas.
A prioritási sorban legfelül, a .
művelet mellett helyezkedik el.
Ezzel a művelettel a fenti mezőkiválasztás tp->mezonev
alakban írható.
Egyesített-rekord adattípus¶
Elképzelhető, hogy úgy szeretnénk egységesen hivatkozni adatokra, hogy a konkrét megvalósításban még nincs fogalmunk arról, hogy a program adott futásakor milyen típusú adatot kapunk az adott ponton. Legegyszerűbb példa talán erre egy olyan geometriai feladat, ahol egy alakzat területét kell meghatároznunk. Nyilván tetszőleges alakzatnak meghatározható a területe, de hogy konkrétan hogy, az csak akkor derül ki, amikor tudjuk, hogy milyen alakzatról beszélünk (körről, háromszögről, téglalapról...). Általában igaz az, hogy a felhasználót (aki kíváncsi az alakzat területére), nem illik terhelni azzal, hogy ő döntse el az alakzat típusát és annak megfelelően kérje el annak területét, neki elég annyit kérni, hogy szeretné a területét meghatározni az aktuális alakzatának. Ilyen esetben lehet jó, ha a különböző típusú alakzatokat egységesen tudjuk kezelni és hivatkozni, és csak akkor foglalkozzunk a konkrét típussal, amikor az elengedhetetlen. Erre való az egyesített-rekord adattípus.
Egyesített-rekord absztrakt adattípus¶
Ha az egyes típusú adatokat nem kell tehát egyszerre tárolni, egyesített-rekordról beszélünk. Legyenek \(T_0=\{c_1,\dots,c_k\}\) és \(T_1, \dots, T_k\) tetszőleges típusok. Ezekből képezzük a \(T= T_1+\dots+T_k=\cup_{c_i\in T_0}(\{c_i\}\times T_i)=\{(i, a) | i\in T_0, a\in T_i\}\) értékhalmazt, tehát a \(T_1, \dots, T_k\) típusok értékhalmazainak \(T_0\) szerinti diszjunkt egyesítését. \(T\) elemei tehát olyan rendezett párok, amelyeknek első komponense meghatározza, hogy a második komponens melyik típusból való érték. A \(T\) halmazon is a szorzat rekordhoz hasonló módon értelmezhetünk kiolvasó és módosító műveletet. Az új adattípust a \(T_0\) változati típusból és \(T_1,\dots,T_k\) egyesítési-tag típusokból képzett egyesített-rekord típusnak nevezzük.
Az egyesített-rekord absztrakt adattípus műveletei között találunk egy olyan műveletet, ami adott esetben eldönti, hogy az éppen aktuális változatnak mi a típusa. Így absztrakt szinten a következő műveleteket határozhatjuk meg:
Művelet megnevezése | Művelet leírása |
---|---|
Változat (\(\rightarrow\) A : T ; \(\leftrightarrow\) V :T0 ) |
Változat kiolvasása. A művelet végrehajtása után \(V=c_i\), ha \(A=(c_i,a)\). |
Kiolvas_i (\(\rightarrow\) A : T , \(\leftarrow\) x :Ti ) |
Adott i \(\in\) {1\(\dots\) k}$-ra az A rekord i. komponensének kiolvasása adott x , Ti típusú változóba. A művelet végrehajtása után x =a , ha A =(c_i,a) . A művelet hatástalan, ha A első komponense nem ci . |
Módosít_i (\(\leftrightarrow\) A : T ; \(\rightarrow\) x :Ti ) |
Adott i \(\in\) {1\(\dots\) k}$-ra az A rekord i. komponensének módosítása adott x , Ti típusú értékre. A művelet végrehajtása után A =(c_i,x) . |
Értékadás ( \(\leftarrow\) A :T ; \(\rightarrow\) X : T ) |
Az A T típusú szorzat rekord változónak értékül adja az X T típusú szorzat rekord változót. |
Az union
virtuális adattípus¶
Az egyesített-rekord típust C-ben azunion
kulcsszó segítségével valósíthatjuk meg.
Ez az union
kulcsszó nagyon hasonlít a struct
-hoz:
1 2 3 4 5 |
|
Ebben a típusképzésben is az M1
,\(\dots\) ,Mk
azonosítókat mezőazonosítóknak (tagnak, member-nek) hívjuk és lokálisak a típusképzésre nézve.
Illetve az union
szó utáni névre és a típus nevére hasonlóak igazak, mint a struct
esetében.
Az absztrakt típus műveletei itt is mezőhivatkozások (.
operátor) segítségével valósíthatóak meg, ami szintén ugyanúgy működik, mint a struct
típusnál.
Megjegyzendő, hogy a C megvalósításában (megfelelő környezetben) mindig hivatkozhatunk bármelyik mezőre, függetlenül attól, hogy az union
aktuálisan melyik mező értékét tárolja (az absztrakt típusleírás ettől szigorúbban fogalmazott).
Önmagában a C union
típusképzésében nem adhatunk meg változati mezőazonosítót (\(T_0\)), így nincs lehetőségünk az aktuális változatról információ tárolására.
Éppen ezért, ha ez a változati mezőazonosítót is el szeretnénk tárolni, akkor kombináljuk a struct
és union
lehetőségeit:
1 2 3 4 5 6 7 8 |
|
Azaz vegyünk egy olyan struktúrát, aminek két mezője van.
Az első mező megadja, hogy a második változónak, azaz az union
által meghatározott változónak, mely mezője szerint történik az adat tárolása.
Jelzőmezőnek felsorolás (vagy valamilyen egész) típust érdemes használni.
Művelet absztrakt szinten | Művelet virtuális megvalósítása |
---|---|
Változat (\(\rightarrow\) A : T ; \(\leftrightarrow\) V :T0 ) |
V = A.Milyen |
Kiolvas_i (\(\rightarrow\) A : T , \(\leftarrow\) x :Ti ) |
if (A.Milyen == ci) { x = A.Mi; } |
Módosít_i (\(\leftrightarrow\) A : T ; \(\rightarrow\) x :Ti ) |
{ A.Milyen = ci; A.Mi = x ; } |
Értékadás ( \(\leftarrow\) A :T ; \(\rightarrow\) X : T ) |
A = X |
Példa egyesített-rekordra¶
A példa bemutatja a kiinduló feladat megvalósítását. Ehhez, hogy az alakzatokat definiálni, illetve megnevezni tudjuk, felveszünk egy típust, amely a különböző síkidom fajtákat sorolja fel.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|
Hogy jobban látszódjanak a részletek, két külön típust is felvettünk a példában, amelyek nagyjából ugyanazt a szerepet hivatottak betölteni, de megvalósításbeli különbségek vannak köztük.
Ami közös, hogy mind az Idom
, mind az Alakzat
típus tartalmazza az a változati mezőt, amelynek típusa Sikidom
, amely megadja, hogy adott Idom
, illetve Sikidom
milyen fajta síkidomot implementál.
Míg az Idom
egyszerűen oldalhosszaikkal adja meg a nevezett síkidomokat, addig az Alakzat
eltárolja az alakzatok középpontjait is.
Mivel ez a középpont független a konkrét síkidom típusától, így ezt az adatot nem kell az union
-ba rejtenünk.
Technikai különbség a két típusnál még, hogy míg az Idom
union
-ja létrehoz külön egy-egy struktúra változót a háromszögek és négyszögek esetére, az alakzat csak definiálja ezen struktúrákat, amelyek mezőit így közvetlen az Alakzat
típusú változón keresztül tudunk elérni.
Egyesített rekord, avagy az union
, mint fizikai adattípus¶
Láttuk, hogy az union
-on belül egy adott időpillanatban egy mező lesz az érvényes, így egyszerre nem szükséges minden mezőt eltárolni.
Így ha a legnagyobb mező méretének megfelelő memória foglalódik az union
számára, abban valamennyi mezőn tárolt érték elfér majd.
Azaz egy T
union
típus mérete a következő módon alakul: sizeof(T) = max{sizeof(T1), ..., sizeof(Tk)}
.
Valamennyi változati mező ugyanazon a memóriacímen kezdődik, ami megegyezik a teljes union
típusú érték címével (azaz minden mező eltolása, offset-je 0).
A struct és union típusok inicializálása¶
Mind a struct
, mind az union
változók kaphatnak kezdőértéket, az adattagok értékeit a {}
-ek között kell felsorolni.
Az értékek szimpla felsorolásával struct
-ban az adattagok sorrendjében kell megadni az egyes tagok értékét, de nem kötelező mindet, az union
esetében viszont csak az első mező típusának megfelelően inicializálható.
1 2 3 4 5 6 7 8 9 10 11 12 |
|
A \(C^{99}\) szabvány lehetővé teszi tetszőleges mezők inicializását a mezők neveit felhasználva.
Ekkor a {}
zárójelek között az egyes értékek elé a .mezo =
-t írva jelezhetjük, hogy az adott érték mely mező kezdőértéke lesz:
1 2 3 4 5 6 7 8 |
|
Példa: síkidomok területe és kerülete¶
- Problémafelvetés: Határozzuk meg kör, téglalap és háromszög alakú síkidomok területét és kerületét.
- Specifikáció:
- A probléma inputja több sor
kor(r)
,teglalap(a, b)
vagyharomszog(a, b, c)
alakú szöveggel, aholr
,a
,b
ésc
valós számok. - Az inputot a fájl vége (ctrl+D) zárja.
- Az output a megadott síkidom területe és kerülete két sorban, vagy egy hibajelzés, ha a sor nem megfelelő formátumú.
- A probléma inputja több sor
- Algoritmustervezés:
- Az inputot soronként olvassuk be, és ha megfelel valamelyik síkidom leírásának, akkor feltöltünk egy síkidom adattípust (
union
-ok ésstruct
-ok kombinációja) a megfelelő adatokkal. - A fő algoritmusban csak az input adatokat olvassuk be, majd meghívjuk a terület és kerületszámító függvényeket, és kiírjuk a kiszámolt értékeket.
- A terület- és kerületszámítást egy-egy függvény végezze, ami egy síkidomot kap.
- Az inputot soronként olvassuk be, és ha megfelel valamelyik síkidom leírásának, akkor feltöltünk egy síkidom adattípust (
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 |
|