VIK Wiki

„Dinamikus adatszerkezetek tutorial” változatai közötti eltérés

← Régebbi szerkesztés
VizuálisWikiszöveges
Ferrero (vitalap | szerkesztései)
1 561 szerkesztés
Nincs szerkesztési összefoglaló
Ferrero (vitalap | szerkesztései)
1 561 szerkesztés
 
(16 közbenső módosítás ugyanattól a felhasználótól nincs mutatva)
17. sor: 17. sor:


<pre>
<pre>
  int a,b;
int a,b;
  float f;
float f;
  char '''c;  
char *c;  
  /''' FONTOS! a pointer is statikus változó, értéke pedig egy memóriacím lehet. Később látni fogjuk. */
/* FONTOS! a pointer is statikus változó, értéke pedig egy memóriacím lehet. Később látni fogjuk. */
</pre>
</pre>


29. sor: 29. sor:
Ilyenkor az operációs rendszert kérjük meg arra, hogy adjon egy olyan memóriacímet, amit szabadon használhatunk. Miután memóriát kértünk, az értéket el is tároljuk, ezekre valók a pointerek, amik maguk is statikus változók, memóriacímek tárolására szolgálnak. Méretük 32 bites rendszereken (pl. Windows 98, Linux stb.) 4 byte (mindig ugyanannyi, mint egy 'int' tipus mérete, s hasonló  műveleteket végezhetünk velük).
Ilyenkor az operációs rendszert kérjük meg arra, hogy adjon egy olyan memóriacímet, amit szabadon használhatunk. Miután memóriát kértünk, az értéket el is tároljuk, ezekre valók a pointerek, amik maguk is statikus változók, memóriacímek tárolására szolgálnak. Méretük 32 bites rendszereken (pl. Windows 98, Linux stb.) 4 byte (mindig ugyanannyi, mint egy 'int' tipus mérete, s hasonló  műveleteket végezhetünk velük).


%CODE{"cpp"}%
<pre>
  int *a;
int *a;
  char *b;
char *b;
%ENDCODE%
</pre>


Deklarálásukkor még nem mutatnak sehová, vagy érvénytelen helyre.
Deklarálásukkor még nem mutatnak sehová, vagy érvénytelen helyre.


Ha azonban helyes címet adunk neki, akkor használhatóak:
Ha azonban helyes címet adunk neki, akkor használhatóak:
%CODE{"cpp"}%
<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>
%ENDCODE%


Látjuk tehát, hogy a pointerek tulajdonképpen számokat tárolnak (memóriacímeket). Lehet használni tehát az 'int'-ekkel használatos műveleteket.
Látjuk tehát, hogy a pointerek tulajdonképpen számokat tárolnak (memóriacímeket). Lehet használni tehát az 'int'-ekkel használatos műveleteket.
51. sor: 50. sor:
Egész pontosan pointerekhez hozzá lehet adni (vagy kivonni) inteket (vagy intekhez ptr-eket). Összeszorozni vagy összeadni két pointert például már nem lehet (compiler error). Viszont pl. van <, >, == stb.
Egész pontosan pointerekhez hozzá lehet adni (vagy kivonni) inteket (vagy intekhez ptr-eket). Összeszorozni vagy összeadni két pointert például már nem lehet (compiler error). Viszont pl. van <, >, == stb.


%CODE{"cpp"}%
<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é */
%ENDCODE%
</pre>


A pointerek értékeit (mi van azon a címen, amire mutat) az elé írt '*' operátorral kaphatjuk meg.
A pointerek értékeit (mi van azon a címen, amire mutat) az elé írt '*' operátorral kaphatjuk meg.


%CODE{"cpp"}%
<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.
%ENDCODE%
</pre>


FONTOS! A pointerek tömbként is használhatóak ( a tömbök is memóriacímre mutatnak, konkrétan oda, ahol vannak az elemei tehát ők is pointerek a maguk formájában). Így a fentebb deklarált 'mp' a következőképpen indexelhető: mp[0] ugyanaz, mint *mp vagy (mp-1)[1] (bonyolodik) mutat az első elemre. mp[1] mutat a 2. elemre, ugyanaz, mint *(mp + 1) vagy *(++mp) vagy (mp-1)[2] :)
FONTOS! A pointerek tömbként is használhatóak ( a tömbök is memóriacímre mutatnak, konkrétan oda, ahol vannak az elemei tehát ők is pointerek a maguk formájában). Így a fentebb deklarált 'mp' a következőképpen indexelhető: mp[0] ugyanaz, mint *mp vagy (mp-1)[1] (bonyolodik) mutat az első elemre. mp[1] mutat a 2. elemre, ugyanaz, mint *(mp + 1) vagy *(++mp) vagy (mp-1)[2] :)
A ++mp-nek van mellékhatása. Ügyelni kell arra, hogy a foglalt memóriatartományok elejére mindig legyen pointer, különben a program memóriát fog szivárogtatni. Egyébként nem érdemes 'kivinni' pointereket memóriaterületekről (mint pl. a (mp-1)[1]), mert a C szabvány nem minden műveletet garantál.
A ++mp-nek van mellékhatása. Ügyelni kell arra, hogy a foglalt memóriatartományok elejére mindig legyen pointer, különben a program memóriát fog szivárogtatni. Egyébként nem érdemes 'kivinni' pointereket memóriaterületekről (mint pl. a (mp-1)[1]), mert a C szabvány nem minden műveletet garantál.


*Megjegyzés*: x86-64-en az int 32 bites, de a pointerek 64 bitesek, ez vidám errorokat
'''Megjegyzés''': x86-64-en az int 32 bites, de a pointerek 64 bitesek, ez vidám errorokat
szokott okozni régebbi progrmoknál (itt egyébként épp a long ugyanakkora, mint egy pointer). Garantáltan működő viszont a következő:
szokott okozni régebbi progrmoknál (itt egyébként épp a long ugyanakkora, mint egy pointer). Garantáltan működő viszont a következő:
%CODE{"cpp"}%
<pre>
typedef union
typedef union {
{
int n;
int n;
void* p;
void* p;
} int_and_ptr;
} int_and_ptr;
%ENDCODE%
</pre>


Mondjuk ilyenre egészen biztosan nem lesz szükségetek még vizsgán sem, de nem árt tudni.
Mondjuk ilyenre egészen biztosan nem lesz szükségetek még vizsgán sem, de nem árt tudni.


Ennyit a pointerekről és a memóriáról.
Ennyit a pointerekről és a memóriáról.


==Láncolt lista==
==Láncolt lista==
95. sor: 92. sor:
Mire jó ez? Hát többek között olyan dolgok tárolására, amiből nem tudjuk, hogy mennyit kell eltárolnunk. Máskülönben ha tudnánk, használhatnánk akár sima tömböket is. A továbbiakban mindenhol a következő típusú listát fogjuk használni:
Mire jó ez? Hát többek között olyan dolgok tárolására, amiből nem tudjuk, hogy mennyit kell eltárolnunk. Máskülönben ha tudnánk, használhatnánk akár sima tömböket is. A továbbiakban mindenhol a következő típusú listát fogjuk használni:


%CODE{"cpp"}%
<pre>
typedef struct _elem  
typedef struct _elem  
{
{
int ertek;
int ertek;
struct _elem *kov;
struct _elem *kov;
} ELEM, '''pELEM;
} ELEM, *pELEM;


pELEM lista, tmp;
pELEM lista, tmp;
%ENDCODE%
</pre>


Ez azt jelenti, hogy a pELEM ugyanaz, mint az ELEM''' (vagyis egy ELEM-re mutató pointer).
Ez azt jelenti, hogy a pELEM ugyanaz, mint az ELEM* (vagyis egy ELEM-re mutató pointer).


Tehát minden lista->kov tartalmaz egy memóriacímet, ahol a lista következő eleme tárolódik. A lista végén természetesen NULL érték áll.
Tehát minden lista->kov tartalmaz egy memóriacímet, ahol a lista következő eleme tárolódik. A lista végén természetesen NULL érték áll.
113. sor: 110. sor:
Egyszerű feladat, nem is foglalkoznék vele sokat.
Egyszerű feladat, nem is foglalkoznék vele sokat.


%CODE{"cpp"}%
<pre>
  tmp=lista;
tmp=lista;
  while (tmp != NULL)
while (tmp != NULL)
  {
{
  /*
/*
  Ide írjuk, amit minden listaelemmel meg szeretnénk csinálni,
Ide írjuk, amit minden listaelemmel meg szeretnénk csinálni,
  pl. összeadni az értékeket, vagy összehasonítani őket egy
pl. összeadni az értékeket, vagy összehasonítani őket egy
  másik értékkel (= keresés);
másik értékkel (= keresés);
  '''/
*/
  tmp=tmp->next; // azaz vesszük a következő listaelem címét
tmp=tmp->next; // azaz vesszük a következő listaelem címét
// és azt használjuk tovább
// és azt használjuk tovább
  }
}
%ENDCODE%
</pre>
 
===Műveletek listaelemekkel===
===Műveletek listaelemekkel===


136. sor: 134. sor:


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


A-t és B-t szeretnénk megcserélni. Hát itt van:
A-t és B-t szeretnénk megcserélni. Hát itt van:


%CODE{"cpp"}%
<pre>
  Aprev->kov = B;
Aprev->kov = B;
  tmp1 = A->kov;
tmp1 = A->kov;
  A->kov   = B->kov;
A->kov = B->kov;
  B->kov   = tmp1;
B->kov= tmp1;
  Bprev->kov = A;
Bprev->kov = A;
%ENDCODE%
</pre>


Az eredmény:
Az eredmény:


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


====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>


Egyszerű: (C az új elem)
Egyszerű: (C az új elem)


%CODE{"cpp"}%
<pre>
  A->kov=C;
A->kov=C;
  C->kov=B;
C->kov=B;
%ENDCODE%
</pre>


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


====Listaelem törlése:====
====Listaelem törlése:====
180. sor: 171. sor:
Az előző ábrán, kitörölni B-t a következő:
Az előző ábrán, kitörölni B-t a következő:


%CODE{"cpp"}%
<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;
/* Most felszabadítjuk a B által foglalt helyet, mert már nincs rá szükség */
/* Most felszabadítjuk a B által foglalt helyet, mert már nincs rá szükség '''/
free(B);
free(B);


/''' És beállítjuk A következő mutatójátt a B utáni elemre */
/* És beállítjuk A következő mutatójátt a B utáni elemre */
A->kov=temp;
A->kov = temp;
%ENDCODE%
</pre>


Ilyen egyszerű.
Ilyen egyszerű.


====Rendezés====
====Rendezés====
198. sor: 187. sor:
Sokféle képpen végrehajtható, itt egy primitív példa. A módszer, hogy páronként összehasonlítjuk az elemeket, és ha az adott rendezése elv szerint inverzióban állnak, megcseréljük őket. Aztán kezdjük előről az egészet, mindaddig, amíg el nem értük a lista végét úgy, hogy nem kellett cserélni:
Sokféle képpen végrehajtható, itt egy primitív példa. A módszer, hogy páronként összehasonlítjuk az elemeket, és ha az adott rendezése elv szerint inverzióban állnak, megcseréljük őket. Aztán kezdjük előről az egészet, mindaddig, amíg el nem értük a lista végét úgy, hogy nem kellett cserélni:


%CODE{"cpp"}%
<pre>
   pELEM rendez(pELEM lista)
   pELEM rendez(pELEM lista)
   {
   {
  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
   }
   }


%ENDCODE%
</pre>
   
   
Az algoritmus értelemszerűen kis változtatással átírható csökkenő sorrendre, vagy más tipusu adatok rendezésére.
Az algoritmus értelemszerűen kis változtatással átírható csökkenő sorrendre, vagy más tipusu adatok rendezésére.
237. sor: 225. sor:


Ennyit a láncolt listákról.
Ennyit a láncolt listákról.


==Fák==
==Fák==
Na elérkeztünk az emberek kedvenc témájához. Gondoljuk végig! Egy bináris (de legyen tenáris, kvaternáris vagy kvináris) fa nem más, mint egy olyan láncolt lista, amelyiknek több irányban lehet láncolt következő eleme. Itt is ugyanazon az elvel gondolkodunk, mint a láncolt listánál, ám az algoritmusok bonyolódnak. A fát legtöbbször rekurzívan járjuk be. Miért? Mert szükség van egy olyan módszerre, ami képes arra, hogy egyes pozíciókba vissza tudjon lépni. Például épp serényen járunk be egy fát, amikor rájövünk, hogy vissza kell lépnünk egy szintet. Ekkor jön jól, hogy egy 'return' és máris egy szinttel feljebb vagyunk.
Na elérkeztünk az emberek kedvenc témájához. Gondoljuk végig! Egy bináris (de legyen tenáris, kvaternáris vagy kvináris) fa nem más, mint egy olyan láncolt lista, amelyiknek több irányban lehet láncolt következő eleme. Itt is ugyanazon az elvel gondolkodunk, mint a láncolt listánál, ám az algoritmusok bonyolódnak. A fát legtöbbször rekurzívan járjuk be. Miért? Mert szükség van egy olyan módszerre, ami képes arra, hogy egyes pozíciókba vissza tudjon lépni. Például épp serényen járunk be egy fát, amikor rájövünk, hogy vissza kell lépnünk egy szintet. Ekkor jön jól, hogy egy 'return' és máris egy szinttel feljebb vagyunk.


A továbbiakban a fákat a következő típusunak tekintjük.
A továbbiakban a fákat a következő típusunak tekintjük.


%CODE{"cpp"}%
<pre>
  typedef struct _bifa {
typedef struct _bifa {
  int adat;
int adat;
  struct _bifa *jobb, *bal;
struct _bifa *jobb, *bal;
  } BIFA, *pBIFA;
} BIFA, *pBIFA;
%ENDCODE%
</pre>


===Fák létrehozása, elemek felvétele===
===Fák létrehozása, elemek felvétele===
261. sor: 246. sor:
Egy példa, számok felvételére szolgáló függvény:
Egy példa, számok felvételére szolgáló függvény:


%CODE{"cpp"}%
<pre>
  // Látjuk, hogy a fára mutató pointer pointere kell, mert ha csak simán a
// Látjuk, hogy a fára mutató pointer pointere kell, mert ha csak simán a
  // fára mutató pointert adnánk át, akkor arról egy másolatot kapnánk
// fára mutató pointert adnánk át, akkor arról egy másolatot kapnánk
  // (lévén hogy a pointer is csak 1 statikus változó!)
// (lévén hogy a pointer is csak 1 statikus változó!)
  // ami értékadáskor nem elég, mert mi az eredeti fát szerenénk
// ami értékadáskor nem elég, mert mi az eredeti fát szerenénk módosítani.
módosítani.


   void felvesz ( pBIFA *bfa, int elem) {
   void felvesz ( pBIFA *bfa, int elem) {
  pBIFA fa=*bfa;
  pBIFA fa=*bfa;
  if (!fa) { // ha üres a fa, akkor felvesszük az első elemét
  if (!fa) { // ha üres a fa, akkor felvesszük az első elemét
  // emiatt kell a BIFA **bfa a fv paraméterlistájában
  // emiatt kell a BIFA **bfa a fv paraméterlistájában
  (*bfa)=(pBIFA) malloc (sizeof(BIFA));
  (*bfa)=(pBIFA) malloc (sizeof(BIFA));
  (*bfa)->adat=elem;
  (*bfa)->adat=elem;
277. sor: 261. sor:
  return;
  return;
  }
  }
  while ( true ) { // a végetelenségig tudunk menni a fában
  while ( true ) { // a végetelenségig tudunk menni a fában


  if (fa->adat==elem) {return;} // ha az elemet már előzőleg
  if (fa->adat==elem) {return;} // ha az elemet már előzőleg felvettük
felvettük
// kilépünk
  // kilépünk
  if (fa->adat > elem) { // ha az új elem kisebb, mint az aktuális
  if (fa->adat > elem) { // ha az új elem kisebb, mint az aktuális
// szint eleme
// szint eleme


  if (fa->bal!=NULL) fa=fa->bal; // ha lehet, elmegyünk balra
  if (fa->bal!=NULL) fa=fa->bal; // ha lehet, elmegyünk balra


  else {  fa->bal=(pBIFA) malloc (sizeof(BIFA));
  else {  fa->bal=(pBIFA) malloc (sizeof(BIFA));
fa->bal->adat=elem;
fa->bal->adat=elem;
fa->bal->bal=fa->bal->jobb=NULL;
fa->bal->bal=fa->bal->jobb=NULL;
return; // ha felvettük az elemet, kilépünk
return; // ha felvettük az elemet, kilépünk
  }
  }
  } else // ugyanaz, csak most az uj elem nagyobb, mint az aktuális
  } else // ugyanaz, csak most az uj elem nagyobb, mint az aktuális


  if (fa->jobb!=NULL) fa=fa->jobb;
  if (fa->jobb!=NULL) fa=fa->jobb;
303. sor: 286. sor:
   }
   }


%ENDCODE%
</pre>


''Kiegészítés:'' Juj. Hát ilyet tuti nem hoznék össze ZH-n magamtól, respect!
''Kiegészítés:'' Juj. Hát ilyet tuti nem hoznék össze ZH-n magamtól, respect!
309. sor: 292. sor:
Alternatív fgv:
Alternatív fgv:


%CODE{"cpp"}%
<pre>
void felvesz(BIFA* gy, int elem)
void felvesz(BIFA* gy, int elem)
{
{
  if(gy==NULL) return; /*Nem kell mindig, de szép.*/
  if(gy==NULL) return; /*Nem kell mindig, de szép.*/
  if(gy->adat==elem) return; /*Ilyen már van, nem tesszük be még1x.*/
  if(gy->adat==elem) return; /*Ilyen már van, nem tesszük be még1x.*/
  if(gy->adat<elem) /*Az elemünk nagyobb, akkor jobbra kell betenni.*/
  if(gy->adat<elem) /*Az elemünk nagyobb, akkor jobbra kell betenni.*/
  {
  {
  if(gy->jobb)   /*Van már jobboldalt valami, rekurzívan elmegyünk oda.*/
  if(gy->jobb)   /*Van már jobboldalt valami, rekurzívan elmegyünk oda.*/
  {
  {
   felvesz(gy->jobb,elem);
   felvesz(gy->jobb,elem);
  }else{   /*A jobboldal tök üres.*/
  }else{ /*A jobboldal tök üres.*/
   gy->jobb=(BIFA*)malloc(sizeof(BIFA));/*Csinálunk egy új elemet*/
   gy->jobb=(BIFA*)malloc(sizeof(BIFA)); /*Csinálunk egy új elemet*/
   gy->jobb->jobb=gy->jobb->bal=NULL; /*KiNULLázzuk a pointereket*/
   gy->jobb->jobb=gy->jobb->bal=NULL; /*KiNULLázzuk a pointereket*/
   gy->jobb->adat=elem;   /*Betesszük az adatot*/
   gy->jobb->adat=elem; /*Betesszük az adatot*/
   return; /*Készen vagyunk.*/
   return; /*Készen vagyunk.*/
  }
  }
  }else{ /*Az elemünk kisebb, most az előző jön, csak a baloldallal.*/
  }else{ /*Az elemünk kisebb, most az előző jön, csak a baloldallal.*/
  if(gy->bal)felvesz(gy->bal,elem);
  if(gy->bal)felvesz(gy->bal,elem);
  else{
  else{
333. sor: 316. sor:
   return;
   return;
  }
  }
  } /*Ez a <elem ifnek a vége*/
  } /*Ez a <elem ifnek a vége*/
}
}
%ENDCODE%
</pre>


ZH-n, vizsgán a rövidített verziót könnyebb leírni:
ZH-n, vizsgán a rövidített verziót könnyebb leírni:


%CODE{"cpp"}%
<pre>
void felvesz(BIFA* gy, int elem){
void felvesz(BIFA* gy, int elem){
if(gy==NULL ||| gy->adat==elem) return; /*A || bal fele ízlés szerint
if(gy==NULL ||| gy->adat==elem) return; // A || bal fele ízlés szerint kihagyható, de ha bent hagyod, biztonságosabb
kihagyható,
 
  de ha bent hagyod,
BIFA** a=gy->adat<elem?&gy->jobb:&gy->bal; // Itt is bejön sajna a duplaptr hax
biztonságosabb*/
if(*a)felvesz(*a,elem);
BIFA** a=gy->adat<elem?&gy->jobb:&gy->bal; /*Itt is bejön sajna a duplaptr
else{
hax*/
*a=(BIFA*)malloc(sizeof(BIFA));
if(*a)felvesz(*a,elem);else{
(*a)->bal=(*a)->jobb=NULL;
*a=(BIFA*)malloc(sizeof(BIFA));
(*a)->adat=elem;
(*a)->bal=(*a)->jobb=NULL;
}
(*a)->adat=elem;
}
}
}
 
</pre>
%ENDCODE%


Próbáljátok megérteni, nem bemagolni, mert az biztos bukás.
Próbáljátok megérteni, nem bemagolni, mert az biztos bukás.
369. sor: 349. 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.
395. sor: 372. sor:


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


408. sor: 385. 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===
434. 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.


==Máris vége?==
==Máris vége?==
A lap eredeti címe: „https://vik.wiki/Dinamikus_adatszerkezetek_tutorial”