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
 
(4 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>


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:====
175. 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;
186. sor: 182. sor:


Ilyen egyszerű.
Ilyen egyszerű.


====Rendezés====
====Rendezés====
354. 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.
380. sor: 372. sor:


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


393. 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===
419. 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.
A lap eredeti címe: „https://vik.wiki/Dinamikus_adatszerkezetek_tutorial”