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
Ferrero (vitalap | szerkesztései)
1 561 szerkesztés
 
(8 közbenső módosítás ugyanattól a felhasználótól nincs mutatva)
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>


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>


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


172. sor: 166. sor:


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


====Listaelem törlése:====
====Listaelem törlése:====
179. 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;
190. sor: 182. sor:


Ilyen egyszerű.
Ilyen egyszerű.


====Rendezés====
====Rendezés====
202. sor: 193. 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: 206. 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
   }
   }


236. sor: 227. 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: 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;
273. 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;
299. 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!
305. 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{
329. 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.
365. 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.
391. sor: 372. sor:


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


404. 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===
430. 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”