Info2/2008tavasz/kuka
3. sor: | 3. sor: | ||
==== Struktúrák igazítása ==== | ==== Struktúrák igazítása ==== | ||
− | A | + | A 4/8 hosszú adatok (int/double/...) csak 4-ggyel osztható címen kezdődhetnek. |
~/info2/igazit.c | ~/info2/igazit.c |
A lap 2008. március 21., 01:20-kori változata
5. előadás (2008-03-21)
Struktúrák igazítása
A 4/8 hosszú adatok (int/double/...) csak 4-ggyel osztható címen kezdődhetnek.
~/info2/igazit.c
/* megnézzük, hogy a struktúrában hogy történik az igazítás */ #include <stdio.h> int main(void) { struct igazito { int a; char b; double d; char f; struct igazito *p; } ig={1, 'w', 3.4, 'f', &ig}; printf("\n%d %p, %c %p, %f %p, %c %p\n%p %p\n", ig.a, &ig.a, ig.b, &ig.b, ig.d, &ig.d, ig.f, &ig.f, ig.p, &ig.p); return 0; }
Bináris keresőfák
Bináris fa
- csúcs
- él
- gyerek
- szülő
- bináris fa (ha minden csúcsnak 0, 1 vagy 2 gyereke van)
- gyökér
- belső csúcs (akinek van gyereke -- akár a gyökér is lehet belső csúcs)
- levél (akinek nincs gyereke -- akár a gyökér is lehet levél)
- bal részfa
- jobb részfa
- részfa gyökere
A bináris keresőfa olyan bináris fa, melynek minden csúcsában egy érték szerepel, és minden csúcsára igaz, hogy a bal részfában szereplő értékek mind legfeljebb akkorák, mint a csúcsban szereplő érték, és a jobb részfában szereplő értékek mind legalább akkorák, mint a csúcsban szereplő érték. Néha kikötik, hogy egy érték csak egyszer szerepelhet (ez egyszerűsíti a bináris fában végzett műveleteket).
Példa bináris keresőfára:
0 / \ / \ -5 3 / \ \ -10 -5 42 / \ -5 -2
Alapműveletek bináris keresőfákkal:
- keresés
- új érték beszúrása
- érték törlése
Egyéb művelet bináris keresőfákkal:
- kiegyensúlyozás: a fa átalakítása a benne levő értékek megtartásával úgy, hogy a magassága (jóval) kisebb legyen.
Példa kiegyensúlyozásra:
1 / \ 0 2 3 \ / \ 3 / \ \ --> / \ 4 1 5 \ / \ / \ 5 0 2 4 6 \ 6
Kiegyensúlyozott fa (ez egy nem túl precíz fogalom): olyan bináris fa, amelynek minden csúcsára igaz, hogy a bal részfában nagyjából ugyanannyi csúcs van, mint a jobb részfában.
Részfa magassága: a részfa gyökerétől egyik leveléig menő leghosszabb úton levő csúcsok száma.
AVL-fa (precíz fogalom, a kiegyensúlyozott fák egy fajtája): olyan bináris fa, melynek minden csúcsára igaz, hogy a bal részfa magassága és a jobb részfa magassága közti különbség -1, 0 vagy +1.
Keresés bináris keresőfában: A feladat az, hogy keressünk egy olyan csúcsot a fában, ahol az adott érték szerepel. Ha több ilyen csúcs is van, akkor bármelyik jó.
A bináris fában való keresés (rekurzív) algoritmusa:
- A gyökértől indulunk.
- Ha az aktuális csúcsban a kívánt érték szerepel, készen vagyunk.
- Ha a bal részfa nem üres, és az aktuális csúcsban a kívánt értéknél nagyobb érték szerepel, a bal részfa gyökerével folytatjuk (a 2. lépéstől).
- Ha a jobb részfa nem üres, és az aktuális csúcsban a kívánt értéknél kisebb érték szerepel, a jobb részfa gyökerével folytatjuk (a 2. lépéstől).
- A keresést befejezzük, az adott érték nem található meg a fában.
Beszúrás bináris keresőfába: A feladat az, hogy szúrjunk be a fába egy új értéket úgy, hogy az továbbra is bináris keresőfa maradjon.
Látható, hogy a keresés legfeljebb annyi lépésből áll, amennyi a fa magassága. AVL-fánál (és sok egyéb kiegyensúlyozott fánál is) egy n csúcsot tartalmazó fa magassága O(log n), tehát a keresés gyors. Szélsőséges esetben, például ha a fa csúcsainak csak jobboldali gyerekük van, az egész fát be kellhet járni (O(n)).
C nyelvben a bináris fák kezeléséhez struktúrákat használunk. A kapcsolódó fogalmak:
- struktúra (struct)
- mező
- struktúra mérete
- mező kezdőcíme a struktúrában
- bájtra igazítás (alignment)
PC (i386, x86) architektúrán az igazítások:
- char esetén 1
- short esetén 2
- double esetén 8
- minden más (pl. int, long, float, struktúra és mutató) esetben 4
Példa struktúra definiálására:
struct pelda { int a, b; char c; double d; };
A példa struktúra mérete igazítás nélkül 4+4+1+8 bájt lenne, igazítással viszont 4+4+1+3+8 bájt, mivel a double típusú változónak 4-gyel osztható címen kell kezdődnie, így 4+4+1 helyett a 4+4+1+3 címen kezdődik.
Példa struktúra használatára:
struct pelda egyik, masik; egyik.a=5; egyik.b=6; egyik.c='x', egyik.d=egyik.a/2.0; masik=egyik; /* minden mezőt lemásol */ masik.a=egyik.b; masik.b=egyik.a;
Vettük még előadáson a mutató (pointer) fogalmát. A mutató egy adott típusú érték kezdőcímét tartalmazza. Mutató deklarálásához a változónév elé tegyünk egy csillagot:
-
int p;
: a p változó egy int értéket tartalmaz -
int *p;
: a p változó egy int értékre mutató mutatót tartalmaz -
int **p;
: a p változó egy int értékre mutató mutatóra mutató mutatót tartalmaz -
char **argv;
: az argv változó egy char értékre mutató mutatóra mutató mutatót tartalmaz -
struct pelda *oda;
: az oda változó egy pelda típusnevű struktúrára mutató mutatót tartalmaz
Egy adott változó kezdőcíméhez a változónév elé tegyünk egy &
jelet (ésjelet):
-
int a, *p; p=&a;
: a p mutató az a (int típusú) változó kezdőcímét tartalmazza -
int t[5], *p; p=&t[3];
: a p mutató a t (int típusú elemekből álló) tömb 3-adik elemédik kezdőcímét tartalmazza -
struct pelda egyik; int *p; p=&egyik.b;
; a p mutató az egyik (pelda típusnevű) struktúra b mezőjének kezdőcímét tartalmazza
A fordított művelethez, tehát egy mutató által mutatott memóriaterület értékéhez a mutató elé tegyünk csillagot:
-
int a=5, *p; *p=&a; a=20; *p+=22; printf("%d", *p);
: az a-t először 5-ről 20-ra változtatja, majd megnöveli 22-vel, majd kiírja (a 42-t) -
struct pelda egyik; char *p=&egyik.c; *p=5;
: az egyik (pelda típusnevű) struktúra c mezőjének értékét 5-re változtatja
Speciális mutató a NULL (#include <stdlib.h>
kell neki), ami nem mutat érvényes memóriaterületre. Példa használatára:
-
int a, *p=NULL; a=*p;
: a második értékadás Segmentation fault-ot (Szegmens hiba) okoz, a program futása megszakad. Megjegyzés: Segmentation fault más programokban máshogy is előállhat.
Vegyük észre, hogy a függvényeknél megtanult cím szerinti paraméterátadásnál mutató átadása történik (pl. a törtösszeadós példában egyszerusit(&as,&es);
), és a függvényen belül a kód csak a mutatót követi (pl. *s/=c;
).
A bináris fa egy csúcsát struktúraként definiáljuk:
struct csucs { int ertek; struct csucs *bal; struct csucs *jobb; };
Példa a fenti bináris fa azon részfájának létrehozására, ami a 3-ból indul lefele (~/szimp2/fapelda1.p):
#include <stdlib.h> /* a NULL miatt */
int main(int argc, char**argv) { struct csucs a, b; a.ertek=3; a.bal=NULL; a.jobb=&b; b.ertek=42; b.bal=NULL; b.jobb=NULL; return 0; }