Info2/2008tavasz/kuka

A MathWikiből
(Változatok közti eltérés)
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., 00: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:

  1. A gyökértől indulunk.
  2. Ha az aktuális csúcsban a kívánt érték szerepel, készen vagyunk.
  3. 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).
  4. 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).
  5. 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;
}
Személyes eszközök