VIK Wiki

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

← Régebbi szerkesztésÚjabb szerkesztés →
VizuálisWikiszöveges
Ferrero (vitalap | szerkesztései)
1 561 szerkesztés
Ferrero (vitalap | szerkesztései)
1 561 szerkesztés
236. sor: 236. sor:


==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===
257. sor: 255. 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;
273. sor: 270. 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;
299. sor: 295. 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!
305. sor: 301. 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{
329. sor: 325. 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.
443. sor: 436. sor:


Á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”