Dinamikus adatszerkezetek tutorial - Laptörténet

Ferrero: /* Fa rendezett kiíratása */

2013-01-29T15:44:23Z

Fa rendezett kiíratása

← Régebbi változat		A lap 2013. január 29., 17:44-kori változata
411. sor:		411. sor:
	Kezdjük már szeretni a rekúúúrziót ugye?		Kezdjük már szeretni a rekúúúrziót ugye?

	~~%CODE{"cpp"}%~~		<pre>
	void kiir(pBIFA fa) {		void kiir(pBIFA fa) {
	if (fa==NULL) return;		if (fa==NULL) return;
	if (fa->jobb) kiir(fa->jobb);		if (fa->jobb) kiir(fa->jobb);

	printf("%d ",fa->adat);		printf("%d ",fa->adat);

	if (fa->bal) kiir(fa->bal);		if (fa->bal) kiir(fa->bal);
	return;		return;
	}		}
	~~%ENDCODE%~~		</pre>

	Általában növekvő sorrendben szokták kérni a kiíratást (=> bal, printf, jobb). Ha megvan a fa==NULL vizsgálat, akkor le lehet spórolni az if(fa->irány)-t.		Általában növekvő sorrendben szokták kérni a kiíratást (=> bal, printf, jobb). Ha megvan a fa==NULL vizsgálat, akkor le lehet spórolni az if(fa->irány)-t.

Ferrero: /* Listaelem törlése: */

2013-01-29T15:43:31Z

Listaelem törlése:

← Régebbi változat		A lap 2013. január 29., 17:43-kori változata
172. sor:		172. sor:

	<pre>		<pre>

	/* A B-t akarjuk kitörölni. Eltesszük a B utáni elem címét: */		/* A B-t akarjuk kitörölni. Eltesszük a B utáni elem címét: */
	ELEM* temp = B->kov;		ELEM* temp = B->kov;
183. sor:		182. sor:

	Ilyen egyszerű.		Ilyen egyszerű.


	====Rendezés====		====Rendezés====

Ferrero: /* Dinamikus memóriafoglalás, pointerek */

2013-01-29T15:42:56Z

Dinamikus memóriafoglalás, pointerek

← Régebbi változat		A lap 2013. január 29., 17:42-kori változata
39. sor:		39. sor:
	<pre>		<pre>
	int x;		int x;
	int px = &x; // itt a 'px' az 'x' változó címét veszi fel~~. Ilyen komment nincs C89-ben, csak / */. Ne használjátok prog1-en!~~		int *px = &x; // itt a 'px' az 'x' változó címét veszi fel

	int mp = (int ) malloc ( sizeof(int)5 ); / itt kértünk egy olyan memóriaterületet, ahol elfér 5 int. Ennek a címét kapjuk vissza. */		int mp = (int ) malloc ( sizeof(int)*5 ); // itt kértünk egy olyan memóriaterületet, ahol elfér 5 int. Ennek a címét kapjuk vissza.

	int **pp = &mp;		int **pp = &mp; // igen, a pointerre mutató pointer... Értéke egy olyan memóriacím, ahol elfér egy pointer.
	/* igen, a pointerre mutató pointer... Értéke egy olyan memóriacím, ahol elfér egy pointer. */
	</pre>		</pre>

53. sor:		52. sor:
	<pre>		<pre>
	int x= ... ;		int x= ... ;
	mp = mp + x; /* FONTOS! az mp-ben tárolt memóriacím nem x-szel fog növekedni, hanem x * sizeof(mp)-vel, azaz a mutatott típus méretével. /		mp = mp + x; /* FONTOS! az mp-ben tárolt memóriacím nem x-szel fog növekedni, hanem x * sizeof(mp)-vel, azaz a mutatott típus méretével. /

	mp++; /* a pointer tipusa int , tehát az érték sizeof(int)-tel fog növekedni. Hasznos, ha egy dinamikus tömbben a következő elemre akarunk mutatni. /		mp++; /* a pointer tipusa int *, tehát az érték sizeof(int)-tel fog növekedni.
			Hasznos, ha egy dinamikus tömbben a következő elemre akarunk mutatni. */

	char *d= ... ;		char *d= ... ;
	d++; /* a következő karakterre fog mutatni */		d++; /* a következő karakterre fog mutatni */

	d--; /* ugyanez, csak visszafelé */		d--; /* ugyanez, csak visszafelé */
	</pre>		</pre>

67. sor:		67. sor:
	<pre>		<pre>
	int a=2006 , b;		int a=2006 , b;
	int *p=&a; // ilyenkor 'p' mutat 'a'-ra		int *p=&a; // ilyenkor 'p' mutat 'a'-ra
	int b=(*p); // 'b' = a 'p' által mutatott címen lévő érték (2006).		int b=(*p); // 'b' = a 'p' által mutatott címen lévő érték (2006).
	(*p)=26; // a 'p' által mutatott címre beírunk 26-ot.		(*p)=26; // a 'p' által mutatott címre beírunk 26-ot.
	</pre>		</pre>

Ferrero: /* Egyszerű fabejárás, műveletekkel */

2013-01-29T15:39:27Z

Egyszerű fabejárás, műveletekkel

← Régebbi változat		A lap 2013. január 29., 17:39-kori változata
351. sor:		351. sor:
	A következő fv megszámolja, hány elemnek van jobb oldali gyermeke!		A következő fv megszámolja, hány elemnek van jobb oldali gyermeke!

	~~%CODE{"cpp"}%~~		<pre>
	int gyerekek (pBIFA fa) {		int gyerekek (pBIFA fa) {
	int n=0;		int n=0;

	if (fa==NULL) return -1; // üres a fa!		if (fa==NULL) return -1; // üres a fa!

	if (fa->jobb !=NULL ) { // el lehet menni jobbra		if (fa->jobb !=NULL ) { // el lehet menni jobbra
			n = n + 1; // a fának van jobb oldali gyereke, így növeljük a számlálót
			n = n + gyerekek(fa->jobb); // megszamoljuk a jobb oldali reszt (n=n+ rövidebb verziója az n+=)
			}

	~~n = n + 1; // a fának van jobb oldali gyereke, így növeljük a~~		if (fa->bal !=NULL ) // el lehet menni balra
	~~// számlálót~~		n = n + gyerekek(fa->bal); // megszamoljuk a bal oldali reszt
			return n; // visszaterunk az eredmennyel
	~~n = n + gyerekek(fa->jobb); // megszamoljuk a jobb oldali reszt (n=n+ rövidebb verziója az n+=)~~		}
			}
	}		</pre>
	if (fa->bal !=NULL ) // el lehet menni balra
	n = n + gyerekek(fa->bal); // megszamoljuk a bal oldali reszt

	return n; // visszaterunk az eredmennyel
	}
	~~%ENDCODE%~~

	Mit csináltunk itt? Fontos először is tudnunk, hogy a függvény egyszerre csak az aktuális elemmel törődik, s nem látja annak gyerekeinek gyerekeit. Annyit tud, hogy jobbra és balra el lehet-e menni. Ennyi elég, mert ha egyik irányba el lehet menni, akkor meghívja önmagát azzal az elemmel, ami a kívánt irányban van. Amikor visszatér, az előző függvényhíváshoz tér vissza, s ezzel átadja a lentebb fekvő gyerekek értékeit. Bonyolult.		Mit csináltunk itt? Fontos először is tudnunk, hogy a függvény egyszerre csak az aktuális elemmel törődik, s nem látja annak gyerekeinek gyerekeit. Annyit tud, hogy jobbra és balra el lehet-e menni. Ennyi elég, mert ha egyik irányba el lehet menni, akkor meghívja önmagát azzal az elemmel, ami a kívánt irányban van. Amikor visszatér, az előző függvényhíváshoz tér vissza, s ezzel átadja a lentebb fekvő gyerekek értékeit. Bonyolult.
377. sor:		374. sor:

	<pre>		<pre>
	(a)		(a)
	/ \		/ \
	(b) (c)		(b) (c)
	/ \		/ \
	(d) (e)		(d) (e)
	\		\
	(f)		(f)
	</pre>		</pre>

390. sor:		387. sor:
	hozzáadódik (a) számlálójához, ami így már 3.		hozzáadódik (a) számlálójához, ami így már 3.

	Ha fenti bírod követni, akkor nem érted a rekurziót, ülj neki, és ha megvan, akkor gyere vissza. (~~_Ahhoz~~ hogy megértsd a rekurziót, előbb meg kell értened a rekurziót :D_)		Ha fenti bírod követni, akkor nem érted a rekurziót, ülj neki, és ha megvan, akkor gyere vissza. (''Ahhoz hogy megértsd a rekurziót, előbb meg kell értened a rekurziót :D'')

	Remélem érthető tehát a bináris fák bejárása. Ha nem a gyerekek számát, hanem mondjuk a fában tárolt adatok összegét kell meghatározni, akkor értelemszerűen azokat kell az n-hez adni, s azzal kell visszatérni. Pl.:		Remélem érthető tehát a bináris fák bejárása. Ha nem a gyerekek számát, hanem mondjuk a fában tárolt adatok összegét kell meghatározni, akkor értelemszerűen azokat kell az n-hez adni, s azzal kell visszatérni. Pl.:

	~~%CODE{"cpp"}%~~		<pre>
	int osszeg (pBIFA fa) {		int osszeg (pBIFA fa) {
	int n;		int n;
	if (fa==NULL) return -1;		if (fa==NULL) return -1;

	n=fa->adat;		n=fa->adat;

	if (fa->jobb !=NULL ) n = n + osszeg(fa->jobb);		if (fa->jobb !=NULL ) n = n + osszeg(fa->jobb);
	if (fa->bal !=NULL ) n = n + osszeg(fa->bal);		if (fa->bal !=NULL ) n = n + osszeg(fa->bal);

	return n; // visszaterunk az eredmennyel		return n; // visszaterunk az eredmennyel
	}		}
	~~%ENDCODE%~~		</pre>

	===Fa rendezett kiíratása===		===Fa rendezett kiíratása===

Ferrero: /* Listaelem beszúrása (C-t B és A közé) */

2013-01-29T15:33:12Z

Listaelem beszúrása (C-t B és A közé)

← Régebbi változat		A lap 2013. január 29., 17:33-kori változata
155. sor:		155. sor:
	====Listaelem beszúrása (C-t B és A közé)====		====Listaelem beszúrása (C-t B és A közé)====
	<pre>		<pre>
	~~/-----\ /-----\~~		... ----> \| A \| ----> \| B \| ----> ...
	... ---->\| A \|---->\| B \|----> ...
	~~\-----/ \-----/~~
	</pre>		</pre>

168. sor:		166. sor:

	...és kész.		...és kész.


	====Listaelem törlése:====		====Listaelem törlése:====

Ferrero: /* Elemcsere */

2013-01-29T15:32:31Z

Elemcsere

← Régebbi változat		A lap 2013. január 29., 17:32-kori változata
134. sor:		134. sor:

	<pre>		<pre>
	~~/-----\ /-----\ /-----\~~ ~~/-----\~~		\| Aprev \| ----> \| A \| ----> ... \| Bprev \| ----> \| B \| ----> ...
	\|Aprev \|---->\| A \|----> ... \| Bprev \|---->\| B \|----> ...
	~~\-----/ \-----/ \-----/ \-----/~~
	</pre>		</pre>

152. sor:		150. sor:

	<pre>		<pre>
	~~/-----\ /-----\ /-----\~~ ~~/-----\~~		\| Aprev \| ----> \| B \| ----> ... \| Bprev \| ----> \| A \| ----> ...
	\|Aprev \|---->\| B \|----> ... \| Bprev \|---->\| A \|----> ...
	~~\-----/ \-----/ \-----/ \-----/~~
	</pre>		</pre>

Ferrero: /* Fák */

2013-01-29T15:30:14Z

Fák

Változtatások megtekintése

Ferrero: /* Rendezés */

2013-01-29T15:19:34Z

Rendezés

← Régebbi változat		A lap 2013. január 29., 17:19-kori változata
203. sor:		203. sor:
	while ( tmp->kov!=NULL) { // elértük a lista végét?		while ( tmp->kov!=NULL) { // elértük a lista végét?
	if (tmp->ertek > tmp->kov->ertek) { // ha inverzio, akkor csere		if (tmp->ertek > tmp->kov->ertek) { // ha inverzio, akkor csere
	if (prev==NULL) { // ez az elso elem?		if (prev==NULL) { // ez az elso elem?
	n1=tmp->kov; // lementjük az egyik végét		n1=tmp->kov; // lementjük az egyik végét
	tmp->kov=tmp->kov->kov; // és cseréljük		tmp->kov=tmp->kov->kov; // és cseréljük
	n1->kov=tmp;		n1->kov=tmp;
	lista=n1; /* Ez itt nagyon haxos. Én külön változót		lista=n1; /* Ez itt nagyon haxos. Én külön változót
	használnék erre ZH-n.*/		használnék erre ZH-n.*/
	} else { // nem az első elem		} else { // nem az első elem
	prev->kov=tmp->kov; // ekkor figyelembe vesszük		prev->kov=tmp->kov; // ekkor figyelembe vesszük
	n1=tmp->kov->kov; // az előző elemet is		n1=tmp->kov->kov; // az előző elemet is
215. sor:		215. sor:
	tmp->kov=n1;		tmp->kov=n1;
	}		}
	prev=NULL; // csere volt, szal kezdjük		prev=NULL; // csere volt, szal kezdjük
	tmp=lista; // előről az egész vizsgálatot		tmp=lista; // előről az egész vizsgálatot
	} else {		} else {
	prev=tmp; // nem kell cserélni, így		prev=tmp; // nem kell cserélni, így
	tmp=tmp->kov; // megyünk tovább		tmp=tmp->kov; // megyünk tovább
	}		}
	}		}
	return lista; // visszatérünk a rendezett		return lista; // visszatérünk a rendezett
	// lista első elemért mutató		// lista első elemért mutató
	// pointerrel		// pointerrel
	}		}

Ferrero: /* Rendezés */

2013-01-29T15:18:32Z

Rendezés

← Régebbi változat		A lap 2013. január 29., 17:18-kori változata
202. sor:		202. sor:

	while ( tmp->kov!=NULL) { // elértük a lista végét?		while ( tmp->kov!=NULL) { // elértük a lista végét?
	if (tmp->ertek > tmp->kov->ertek) { // ha inverzio, akkor csere		if (tmp->ertek > tmp->kov->ertek) { // ha inverzio, akkor csere
	if (prev==NULL) { // ez az elso elem?		if (prev==NULL) { // ez az elso elem?
	n1=tmp->kov; // lementjük az egyik végét		n1=tmp->kov; // lementjük az egyik végét

Ferrero: /* Rendezés */

2013-01-29T15:18:19Z

Rendezés

← Régebbi változat		A lap 2013. január 29., 17:18-kori változata
201. sor:		201. sor:
	pELEM tmp=lista, n=NULL,n1=NULL, prev=NULL;		pELEM tmp=lista, n=NULL,n1=NULL, prev=NULL;

	while ( tmp->kov!=NULL) { // elértük a lista végét?		while ( tmp->kov!=NULL) { // elértük a lista végét?
	if (tmp->ertek > tmp->kov->ertek) { // ha inverzio, akkor csere		if (tmp->ertek > tmp->kov->ertek) { // ha inverzio, akkor csere
	if (prev==NULL) { // ez az elso elem?		if (prev==NULL) { // ez az elso elem?
	n1=tmp->kov; // lementjük az egyik végét		n1=tmp->kov; // lementjük az egyik végét
	tmp->kov=tmp->kov->kov; // és cseréljük		tmp->kov=tmp->kov->kov; // és cseréljük
	n1->kov=tmp;		n1->kov=tmp;
	lista=n1; /*~~@@@@~~ Ez itt nagyon haxos. Én külön változót		lista=n1; /* Ez itt nagyon haxos. Én külön változót
	használnék erre ZH-n.*/		használnék erre ZH-n.*/
	} else { // nem az első elem		} else { // nem az első elem
	prev->kov=tmp->kov; // ekkor figyelembe vesszük		prev->kov=tmp->kov; // ekkor figyelembe vesszük
	n1=tmp->kov->kov; // az előző elemet is		n1=tmp->kov->kov; // az előző elemet is
	tmp->kov->kov=tmp;		tmp->kov->kov=tmp;
	tmp->kov=n1;		tmp->kov=n1;
	}		}
	prev=NULL; // csere volt, szal kezdjük		prev=NULL; // csere volt, szal kezdjük
	tmp=lista; // előről az egész		tmp=lista; // előről az egész vizsgálatot
	vizsgálatot
	} else {		} else {
	prev=tmp; // nem kell cserélni, így		prev=tmp; // nem kell cserélni, így
	tmp=tmp->kov; // megyünk tovább		tmp=tmp->kov; // megyünk tovább
	}		}
	}		}
	return lista; // visszatérünk a rendezett		return lista; // visszatérünk a rendezett
	// lista első elemért mutató		// lista első elemért mutató
	// pointerrel		// pointerrel
	}		}