Info2/2008tavasz/kuka

A MathWikiből
(Változatok közti eltérés)
176. sor: 176. sor:
 
   b.bal=NULL;
 
   b.bal=NULL;
 
   b.jobb=NULL;
 
   b.jobb=NULL;
 +
  return 0;
 +
}
 +
 +
 +
 +
Célunk, hogy meg tudjuk írni a bináris keresőfába való beszúrás algoritmusát.
 +
 +
A bináris keresőfába való beszúrás (rekurzív) algoritmusa:
 +
 +
# A gyökértől, pontosabban a gyökér kezdőcímétől indulunk.
 +
# Paraméterként kapjuk az aktuálisan vizsgálandó részfa gyökerének címét. (Üres fa esetén van lényeges különbség: az üres fa gyökere ugyanis NULL, az üres fa gyökerének címe pedig az a memóriaterület, ahol a NULL-t majd átírjuk másra.)
 +
# Ha az aktuális gyökér NULL, akkor cseréljük le a beszúrandó csúcsra: a csúcs értéke a beszúrandó érték legyen, a bal és jobb mutatók pedig NULL-ok legyenek.
 +
# Ha a beszúrandó érték megegyezik az aktuális gyökérben található értékkel, és az aktuális gyökérnek nincs bal gyereke, folytassuk a jobb részfával (a 3. lépéstől). (Az algoritmus e lépés nélkül is jól működne.)
 +
# Ha a beszúrandó érték legfeljebb akkora, mint az aktuális gyökérben található érték, akkor folytassuk a bal részfával (a 3. lépéstől).
 +
# Folytassuk a jobb részfával (a 3. lépéstől).
 +
 +
Programban:
 +
 +
~/info2/fabeolv.c
 +
 +
#include <stdio.h>
 +
#include <stdlib.h>
 +
 +
struct csucs {
 +
  int ertek;
 +
  struct csucs *bal;
 +
  struct csucs *jobb;
 +
};
 +
 +
/* Beszúrja a gyoker részfába az uj csúcsot levélként (és egyben NULL-t tesz
 +
  * az uj csúcs bal és jobb mutatóiba.
 +
  */
 +
void beszur(struct csucs **gyoker, struct csucs *uj) {
 +
  while (*gyoker != NULL) {
 +
    if (uj->ertek <= (*gyoker)->ertek) {
 +
      gyoker = &(*gyoker)->bal;
 +
    } else {
 +
      gyoker = &(*gyoker)->jobb;
 +
    }
 +
  }
 +
  *gyoker = uj;
 +
  uj->bal = NULL;
 +
  uj->jobb= NULL;
 +
}
 +
 +
void kirajzol(struct csucs *gyoker, int nszokoz) {
 +
  int i;
 +
  for (i=nszokoz; i>0; i--) putchar(' ');
 +
  if (gyoker!=NULL) {
 +
    printf("%d\n", gyoker->ertek);
 +
    kirajzol( gyoker->bal,  nszokoz+2);
 +
    kirajzol( gyoker->jobb, nszokoz+2);
 +
  } else printf("-\n");
 +
}
 +
 +
int main(void) {
 +
  int i, csucsoksz=0;
 +
  struct csucs *gyoker=NULL;
 +
  struct csucs *fa;
 +
 +
  printf("Hány csúcsa lesz a fának? ");
 +
  scanf("%d", &csucsoksz);
 +
  fa = (struct csucs*) malloc(csucsoksz*sizeof(struct csucs));
 +
  if(fa == NULL) {
 +
    printf("Nincs eleg memoria!");
 +
    return 0;
 +
  }
 +
  for(i=0; i<csucsoksz; i++) {
 +
    printf("%d. csúcs értéke? ", i+1);
 +
    scanf("%d",&fa[i].ertek);
 +
    beszur(&gyoker, &fa[i]);
 +
  }
 +
  kirajzol(gyoker,1);
 
   return 0;
 
   return 0;
 
  }
 
  }

A lap 2008. március 21., 00:36-kori változata

5. előadás (2008-03-21)

Struktúrák igazítása

A 2/4/8 hosszú adatok (short/int/double/...) csak 2/4/8-cal 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;
}


Célunk, hogy meg tudjuk írni a bináris keresőfába való beszúrás algoritmusát.

A bináris keresőfába való beszúrás (rekurzív) algoritmusa:

  1. A gyökértől, pontosabban a gyökér kezdőcímétől indulunk.
  2. Paraméterként kapjuk az aktuálisan vizsgálandó részfa gyökerének címét. (Üres fa esetén van lényeges különbség: az üres fa gyökere ugyanis NULL, az üres fa gyökerének címe pedig az a memóriaterület, ahol a NULL-t majd átírjuk másra.)
  3. Ha az aktuális gyökér NULL, akkor cseréljük le a beszúrandó csúcsra: a csúcs értéke a beszúrandó érték legyen, a bal és jobb mutatók pedig NULL-ok legyenek.
  4. Ha a beszúrandó érték megegyezik az aktuális gyökérben található értékkel, és az aktuális gyökérnek nincs bal gyereke, folytassuk a jobb részfával (a 3. lépéstől). (Az algoritmus e lépés nélkül is jól működne.)
  5. Ha a beszúrandó érték legfeljebb akkora, mint az aktuális gyökérben található érték, akkor folytassuk a bal részfával (a 3. lépéstől).
  6. Folytassuk a jobb részfával (a 3. lépéstől).

Programban:

~/info2/fabeolv.c

#include <stdio.h>
#include <stdlib.h>

struct csucs {
  int ertek;
  struct csucs *bal;
  struct csucs *jobb;
};

/* Beszúrja a gyoker részfába az uj csúcsot levélként (és egyben NULL-t tesz
 * az uj csúcs bal és jobb mutatóiba.
 */
void beszur(struct csucs **gyoker, struct csucs *uj) {
  while (*gyoker != NULL) {
    if (uj->ertek <= (*gyoker)->ertek) {
      gyoker = &(*gyoker)->bal;
    } else {
      gyoker = &(*gyoker)->jobb;
    }
  }
  *gyoker = uj;
  uj->bal = NULL;
  uj->jobb= NULL;
}

void kirajzol(struct csucs *gyoker, int nszokoz) {
  int i;
  for (i=nszokoz; i>0; i--) putchar(' ');
  if (gyoker!=NULL) {
    printf("%d\n", gyoker->ertek);
    kirajzol( gyoker->bal,  nszokoz+2);
    kirajzol( gyoker->jobb, nszokoz+2);
  } else printf("-\n");
}

int main(void) {
  int i, csucsoksz=0;
  struct csucs *gyoker=NULL;
  struct csucs *fa;

  printf("Hány csúcsa lesz a fának? ");
  scanf("%d", &csucsoksz);
  fa = (struct csucs*) malloc(csucsoksz*sizeof(struct csucs));
  if(fa == NULL) {
    printf("Nincs eleg memoria!");
    return 0;
  }
  for(i=0; i<csucsoksz; i++) {
    printf("%d. csúcs értéke? ", i+1);
    scanf("%d",&fa[i].ertek);
    beszur(&gyoker, &fa[i]);
  } 
  kirajzol(gyoker,1);
  return 0;
}
Személyes eszközök