Info2/2008tavasz/kuka

A MathWikiből
(Változatok közti eltérés)
1. sor: 1. sor:
== 4. előadás (2008-03-14) ==
+
== 5. előadás (2008-03-21) ==
  
=== Tömbök és függvények átadása paraméterként (csak mutatókkal) ===
+
==== Struktúrák igazítása ====
  
==== Index jelölés ====
+
A
  
ld. a gyakorlaton: ~/info2/mx.c
+
~/info2/igazit.c
 
+
==== Mutató jelölés, típuskényszerítés (casting) ====
+
 
+
~/info2/mx2.c
+
  
 +
/* megnézzük, hogy a struktúrában hogy történik az igazítás */
 
  #include <stdio.h>
 
  #include <stdio.h>
 
   
 
   
#define SOROKSZ 10
+
  int main(void) {
#define OSZLOPOKSZ 10
+
   struct igazito {
+
    int a;
  int legnagyobb(int *a, int oszsz, int ssz, int osz)
+
    char b;
{
+
    double d;
   int i, j;
+
     char f;
  int mx = *a;
+
    struct igazito *p;
 
+
   } ig={1, 'w', 3.4, 'f', &ig};
  for( i = 0; i < ssz; i++)
+
     for( j = 0; j < osz; j++)
+
      if (  *(a + i*oszsz + j) > mx)
+
        mx =  *(a + i*oszsz + j);
+
   return mx;
+
}
+
 
   
 
   
int main()
+
   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);
   int t[SOROKSZ][OSZLOPOKSZ] = { {21, 42, 13},
+
                                  {35, 20, 15} };
+
  int ssz = 2;
+
  int osz = 3;
+
  int m;
+
 
+
  m = legnagyobb( (int *)t, OSZLOPOKSZ, ssz, osz);
+
 
+
  printf("A legnagyobb érték %d.\n", m);
+
 
   return 0;
 
   return 0;
 
  }
 
  }
  
==== Függvény átadása ====
 
  
Függvénymutató deklarálása:
 
int (*mutfv)( int )
 
Ez így még nem mutat sehová, csak egy mutatót deklarál, mely csak olyan függvényre mutathat majd, amelynek egyetlen egész argumentuma van, és amely egy egészt ad vissza.
 
  
A zárójel kell, mert
+
=== Bináris keresőfák ===
int *mutfv( int )
+
olyan függvényt deklarálna, mely egészre mutató mutatót ad vissza.
+
  
~/info2/fvmut.c
 
#include <stdio.h>
 
 
int ossz(int, int);        // fv prototípusok
 
int szor(int, int);
 
 
int main(void)
 
{
 
  int a = 4;
 
  int b = 3;
 
  int e = 0;                // eredmény
 
  int (*fvm)(int, int);    // függvény mutató deklaráció
 
 
  fvm = ossz;              // az ossz() függvényre mutat
 
  e = fvm(a, b);            // ossz(a, b) meghívása
 
  printf("Az összeg = %d\n", e);
 
 
 
  fvm = szor;
 
  e = fvm(a, b);
 
  printf("A szorzat = %d\n", e);
 
 
  return 0;
 
}
 
 
int ossz(int x, int y) {
 
  return x + y;
 
}
 
 
int szor(int x, int y) {
 
  return x * y;
 
}
 
  
 +
'''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
  
=== Véletlen sorozat generálása ===
+
'''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).
  
Véletlen számok generálása: rand() az stdlib.h betöltése után egy [0,RAND_MAX] = [0,INT_MAX] intervallumba eső egészt generál. '''random seed''': srand( '''<szám>''' ) hívással befolyásolható az elsőnek generált -- és ezzel az összes -- szám, mivel ez csak álvéletlen sorozat. Valódi véletlenség látszatához használjuk a time( NULL ) függvényt.
+
Példa bináris keresőfára:
  
~/info2/rand.c
+
      0
#include <stdio.h>
+
      / \
#include <stdlib.h>
+
    /   \
  #include <time.h>
+
    -5    3
   
+
  / \    \
int main (void) {
+
  -10 -5   42
   int i;
+
    / \
+
    --2
  srand( (unsigned int) time( NULL ));        // seed
+
  for (i=0; i<5; ++i) printf("%d ",rand()%64); // [0..RAND_MAX]
+
  printf("\n");
+
+
  return 0;
+
  }
+
  
=== Struktúra ===
+
Alapműveletek bináris keresőfákkal:
  
#include <stdio.h>
+
* keresés
#include <stdlib.h>
+
* új érték beszúrása
+
* érték törlése
int main(void)
+
 
{
+
Egyéb művelet bináris keresőfákkal:
  struct allat                  // struktúra deklaráció
+
 
  {
+
* 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.
    char nev[20];
+
    int db;
+
    struct allat *kov;          // mutató a következőre
+
  };
+
+
  struct allat *elso = NULL;    // mutató az első állatra
+
  struct allat *ez  = NULL;    // mutató erre az állatra
+
  struct allat *utso = NULL;    // mutató az előzőre
+
+
  char c = '\0';
+
+
  for( ; ; )
+
  {
+
    printf("\nBeviszed egy allat adatait? (i/n) ");
+
+
    scanf(" %c",&c);
+
    if(c == 'n' || c == 'N') break;
+
+
    // memóriaallokáció
+
    ez = (struct allat*) malloc(sizeof(struct allat));
+
+
    if(elso == NULL) elso = ez; // mutató az első állatra
+
+
    if(utso!= NULL) utso -> kov = ez;
+
+
    printf("\nAz allat neve? ");
+
    scanf("%s", ez -> nev);
+
+
    printf("\nHany %s lesz a hajon? ", ez -> nev);
+
    scanf("%d", &ez -> db);
+
+
    ez->kov = NULL;            // lehet, hogy ez az utolsó
+
    utso = ez;                  // áttesszük az utso-ba
+
  }
+
+
                                // állatok listájának kiírása
+
  ez = elso;
+
+
  while (ez != NULL)            // amíg ez egy érvényes mutató
+
  {
+
    printf("\n%d darab %s,\n", ez->db, ez->nev);
+
    utso = ez;                  // mentés memóriafelszabadításhoz
+
    ez = ez->kov;              // mutató a következőre
+
    free(utso);                // memóriafelszabadítás
+
  }
+
  return 0;
+
}
+
  
 +
Példa kiegyensúlyozásra:
  
==== Struktúra átadása paraméterként ====
+
  1
 +
  / \
 +
0  2                          3
 +
      \                        / \
 +
      3                      /  \
 +
        \            -->    /    \
 +
        4                  1      5
 +
          \                / \    / \
 +
          5              0  2  4  6
 +
            \
 +
            6
  
#include <stdio.h>
+
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.
#include <stdlib.h>
+
 
+
Részfa magassága: a részfa gyökerétől egyik leveléig menő leghosszabb úton levő csúcsok száma.
struct allat *uj_allat(void);
+
 
+
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.
struct allat                  // struktúra deklaráció
+
 
  {
+
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ó.
  char nev[20];
+
 
   int db;
+
A bináris fában való keresés (rekurzív) algoritmusa:
   struct allat *elozo;       // mutató az előzőre
+
 
   struct allat *kov;         // mutató a következőre
+
# 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;
 
  };
 
  };
   
+
 
  int main(void)
+
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.
{
+
 
  struct allat *elso = NULL;   // mutató az első állatra
+
Példa struktúra használatára:
  struct allat *ez  = NULL;   // mutató erre az állatra
+
 
  struct allat *utso = NULL;   // mutató az előzőre
+
  struct pelda egyik, masik;
  char c = '\0';
+
  egyik.a=5; egyik.b=6; egyik.c='x', egyik.d=egyik.a/2.0;
+
masik=egyik; /* minden mezőt lemásol */
  for(;;)
+
masik.a=egyik.b; masik.b=egyik.a;
  {
+
 
    printf("\nBeviszed %segy allat adatait? (i/n) ",  
+
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:
            elso == NULL ? "" : "meg " );
+
 
    scanf(" %c",&c);
+
* <code>int p;</code>: a p változó egy int értéket tartalmaz
    if(c == 'n' || c == 'N') break;
+
* <code>int *p;</code>: a p változó egy int értékre mutató mutatót tartalmaz
+
* <code>int **p;</code>: a p változó egy int értékre mutató mutatóra mutató mutatót tartalmaz
    // memóriaallokáció
+
* <code>char **argv;</code>: az argv változó egy char értékre mutató mutatóra mutató mutatót tartalmaz
    ez = uj_allat();
+
* <code>struct pelda *oda;</code>: az oda változó egy pelda típusnevű struktúrára mutató mutatót tartalmaz
+
 
    if(elso == NULL)
+
Egy adott változó kezdőcíméhez a változónév elé tegyünk egy <code>&</code> jelet (ésjelet):
    {
+
 
      elso = ez;
+
* <code>int a, *p; p=&a;</code>: a p mutató az a (int típusú) változó kezdőcímét tartalmazza
      utso = ez;
+
* <code>int t[5], *p; p=&t[3];</code>: a p mutató a t (int típusú elemekből álló) tömb 3-adik elemédik kezdőcímét tartalmazza
    }
+
* <code>struct pelda egyik; int *p; p=&egyik.b;</code>; a p mutató az ''egyik'' (pelda típusnevű) struktúra ''b'' mezőjének kezdőcímét tartalmazza
    else
+
 
    {
+
A fordított művelethez, tehát egy mutató által mutatott memóriaterület értékéhez a mutató elé tegyünk csillagot:
      utso->kov = ez;
+
 
      ez->elozo = utso;
+
* <code>int a=5, *p; *p=&a; a=20; *p+=22; printf("%d", *p);</code>: az a-t először 5-ről 20-ra változtatja, majd megnöveli 22-vel, majd kiírja (a 42-t)
      utso = ez;
+
* <code>struct pelda egyik; char *p=&egyik.c; *p=5;</code>: az ''egyik'' (pelda típusnevű) struktúra ''c'' mezőjének értékét 5-re változtatja
    }
+
 
  }
+
Speciális mutató a NULL (<code>#include <stdlib.h></code> kell neki), ami nem mutat érvényes memóriaterületre. Példa használatára:
+
 
  /* KIÍRÁS */
+
* <code>int a, *p=NULL; a=*p;</code>: 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.
  ez = elso;
+
 
  while (ez != NULL)           // amíg ez egy érvényes mutató
+
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 <code>egyszerusit(&as,&es);</code>), és a függvényen belül a kód csak a mutatót követi (pl. <code>*s/=c;</code>).
   {
+
 
    printf("%d darab %s,\n", ez->db, ez->nev);
+
A bináris fa egy csúcsát struktúraként definiáljuk:
    utso = ez;                 // mentés memóriafelszabadításhoz
+
 
    ez = ez->kov;               // mutató a következőre
+
struct csucs {
    free(utso);                 // memóriafelszabadítás
+
  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;
 
   return 0;
}
 
 
struct allat *uj_allat(void)
 
{
 
  struct allat *a;
 
 
  a = (struct allat*) malloc(sizeof(struct allat));
 
 
  printf("\nAz allat neve? ");
 
  scanf("%s", a -> nev);
 
 
  printf("\nHany %s lesz a hajon? ", a -> nev);
 
  scanf("%d", &a -> db);
 
 
  a->kov = a->elozo = NULL;
 
 
  return a;
 
 
  }
 
  }

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

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

Struktúrák igazítása

A

~/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