Info2/2008tavasz/kuka

A lap 2008. március 14., 08:41-kori változata (lapforrás) Wettl (vitalap | szerkesztései) ← Régebbi szerkesztés		A lap 2008. március 21., 01:14-kori változata (lapforrás) Wettl (vitalap | szerkesztései) Újabb szerkeszté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;	+	/ \
−		+	-5  -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., 01: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;
}