1. Félév végén...

13. heti laborok

  • Nagy HF beadás és bemutatás

2. nagy ZH

  • Jelentkezés majd a portálon
  • Szokásos +2 pont

2. Ismétlés – láncolt lista

Duplán láncolt lista
  • Előnyük: nagyon gyors és egyszerű a méretüket megváltoztatni. Így alkalmasak dinamikusan változó számú adat kezelésére.
  • Hátrányuk: csak lineáris keresés valósítható meg bennük.

Az ideális az lenne, ha olyan adatszerkezetünk lenne, ami

  • gyorsan nyújtható, mint egy láncolt lista,
  • gyors keresést biztosít, mint egy rendezett tömb (bináris keresés).

A bináris fák és algoritmusaik

4. A bináris keresőfa: rendezett tárolás

Minden elemnek két gyereke lehet:

  • az elemtől balra a nála kisebb, (kisebbek!)
  • tőle jobbra a nála nagyobb (nagyobbak!)

Figyeljük meg, hogy a fenti szabály nem csak a közvetlen gyermekekre igaz! Például az 5-től balra található elemek a 3, 4, 1, 2 mind kisebbek nála. Az a tény, hogy ha egy állítás igaz egy elem bal/jobb oldali gyermekére, akkor az igaz az összes az elemtől balra/jobbra elhelyezkedő elemre, egy nagyon fontos tulajdonsága a bináris fáknak.

A fa elemeinek megnevezéséhez a családfa analógiáját szoktuk használni. Minden csomópontból (node) maximum két nyíl indul ki, a csomópont két gyereke felé. A csomópont maga ilyenkor a szülő csomópont. Leszármazottaknak nevezzük egy csomópont összes gyerekét, azok gyerekeit stb. (Vagyis a gyerekek a közvetlen leszármazottak.)

A fa gyökerének a szerkezet kezdőpontját nevezzük. Ez egy olyan elem, amelyiknek nincsen már szülője. A fa levelei azok a csomópontok, amelyeknek nincsen gyerekük. A fa rekurzív adatszerkezet: egy elem bal oldali szomszédja is egy részfa, jobb oldali is egy részfa. Ezeknek természetesen további részfáik lehetnek.

A fa csomópontjainak megnevezéséhez használjuk a gráfelméletből vett szavakat is. A fa egy gráf: csúcsokból áll, amelyeket élek kötnek össze. Két elem között csak egy út létezik – nincs kör a fában. Az élek irányítottak, a nyíl egy elemtől a másikra mutat, visszafelé nem.

Egy csomópont szomszédai azok, amelyek egy éllel össze vannak kötve (vagyis az adott csomópont szülője és két gyereke). A bal oldali gyereket így nevezhetjük bal oldali szomszédnak, a jobb oldali gyereket pedig jobb oldali szomszédnak. Ilyen értelemben a szülő is szomszéd.

5. A fa reprezentációja C nyelven

typedef struct BinFa {

   …    // tetszőleges adat

   struct BinFa *bal, *jobb;
} BinFa;

A fa egy csúcsát egy struktúra írja le, amelyben az adatokon túl van két ugyanilyen strukúrára mutató pointer: a bal, illetve jobb gyermek címei.

Érdekesség: nyelvi szinten nem látszik a különbség egy duplán láncolt lista és egy bináris fa között. A különbség abban áll, hogy másra használjuk az adatok mellé tett két pointert.

6. Keresés a fában: ~log n

Az algoritmus:

  1. a gyökér elemtől indulunk,
  2. ha az aktuális elem nem létezik, akkor nincs a fában a keresett,
  3. összehasonlítjuk a keresett elemmel:
    • ha pont az, akkor végeztünk,
    • ha nagyobb, akkor balra megyünk tovább,
    • ha kisebb, akkor jobbra megyünk tovább;
  4. folytatjuk a 2. ponttól.

Elvileg minden lépésben feleződik a még megvizsgálandó elemek száma, tehát a keresés ~log2n időben fut le.

Tudjuk, merre
kell menni!
BinFa *keres(BinFa *gyoker, int adat) {
   BinFa *mozgo = gyoker;
   while (mozgo != NULL && mozgo->adat != adat) {
      if (adat < mozgo->adat) mozgo = mozgo->bal;
      else mozgo = mozgo->jobb;
   }
   return mozgo;
}

A while ciklussal addig megyünk, amíg a „mozgo” NULL nem lesz, és még nem találtuk meg a keresett elemet. A „mozgo” NULL lehet, mert:

  • a fa még üres és egy NULL pointert kaptunk argumentumként,
  • a legutóbbi összehasonlítást egy levélben végeztük és továbbindultunk egy nemlétező gyermek felé.

A logikai rövidzár miatt az while ciklus fejében az ÉS kapcsolat második fele már nem értékelődik ki, ha „mozgo” értéke NULL. Ez nagyon fontos, hiszen egy NULL pointeren a mozgo->adat kifejezés futási idejű hibát okozna. A logikai rövidzárat pontosan az ilyen jellegű kifejezések miatt vezették be a nyelvbe.

A lehetséges visszatérési értékek:

  • NULL, mert a fa üres volt és rögtön az első iteráció kilépett a while ciklusból,
  • NULL, mert az elemet nem találta meg és egy levél nemlétező gyermekén állt meg a ciklus,
  • a megtalált elem címe.

a. megvan
b. nincs benne
c. üres fa

A keresés lehetséges eredményei:

  1. megtaláljuk a keresett elemet, visszatérés az elem címével.
  2. nincs a fában a keresett elem (pl. 10), visszatérési érték: NULL,
  3. a fa üres, a visszatérési érték: NULL,

7. A fa bejárása I. – rekurzió

struct BinFa {
   int szam;
   struct BinFa *bal, *jobb;
};

A fa bejárása rekurzió nélkül csak nehézkesen oldható meg.
Ha kihasználjuk, hogy a fa egy rekurzív adatszerkezet, akkor egyszerű feladat!


8. A fa bejárása II. – algoritmus

Az algoritmus

bal–gyökér–jobb

Feladat: írjuk ki a fában tárolt számokat!

  1. Járjuk be az aktuális elem bal részfáját,
  2. Írjuk ki az aktuális csúcsban tárolt számot,
  3. Járjuk be az aktuális elem jobb részfáját.

 

A megvalósítás C-ben

A rekurzióban az a szép, hogy a leírás C-ben is egyszerű:

void sorban_kiir(BinFa *gyoker) {
   if (gyoker == NULL)   // leállási feltétel
      return;

   sorban_kiir(gyoker->bal);     // 1
   printf("%d ", gyoker->adat);     // 2
   sorban_kiir(gyoker->jobb);    // 3
}

Leállási feltétel: üres részfához értünk:

  • Vagy az egész fa üres,
  • Vagy az adott részfa üres!

A függvény meghívódik az üres részfákra is!

Megtehetnénk, hogy a rekurzív hívások előtt ellenőrizzük, hogy van-e valami az adott részfában, pl.:

if (gyoker->bal != NULL)
   sorban_kiir(gyoker->bal);

Ettől azonban hosszabb lesz a kód, hiszen a függvény első sorában mindenképpen kell ellenőrizni, hogy a gyökér pointer NULL vagy nem NULL. Az egész fa is lehet üres, és az üres fa is fa, amelyre a függvény hívható.

9. A fa bejárása III. – inorder bejárás fordítva

jobb–gyökér–bal

A megismert algoritmust inorder bejárásnak nevezik, ugyanis a fa elemein növekvő sorrendben hajtja végre a művelet.

Megcserélve a bal és a jobb részfa bejárását, csökkenő a sorrend:

  1. Járjuk be a elem jobb részfát (nagyobb elemek),
  2. Dolgozzuk fel az aktuális elemet,
  3. Járjuk be a bal részfát (kisebb elemek).

 

10. A postorder bejárás – fa felszabadítása

Ha egy teljes fát szeretnénk felszabadítani, vigyázni kell: nehogy magunk alatt vágjuk a fát, azaz nehogy elveszítsük a hozzáférést elemekhez. Felszabadításkor mindig leveleket szabad csak törölni. Olyan bejárásra van szükség, amely először a leveleket járja be, majd azokat az elemeket, amik a korábbi levelek felszabadítása után levéllé válnak és így tovább.

bal–jobb–gyökér
  1. Járjuk be az aktuális elem részfáit,
  2. Szabadítsuk fel az aktuális elemet.




Csak leveleket szabad felszabadítani!

A törlés C-ben

Előbb a részfákat felszabadítjuk, utána mehet a gyökérelem is:

void felszabadit(BinFa *gyoker) {
   if (gyoker == NULL)   // leállási feltétel
      return;

   felszabadit(gyoker->bal);     // 1
   felszabadit(gyoker->jobb);       // 2
   free(gyoker);                 // 3
}

11. A preorder bejárás I.

Tegyük fel, hogy van egy fa a memóriában, amit szeretnénk fájlba menteni, majd onnan visszaállítani!


Ha ezt az inorder bejárással tennénk:

1, 2, 3, 4, …
1, 2, 3, 4, …

A fájlban sorrendben lesznek az elemek, az újra felépített fába rendezetten, a legkisebb elemtől kezdve szúrjuk be az elemeket. Ez azt jelenti, hogy az „1” lesz a gyökér, és minden további elem nagyobb, mint az előző, tehát a fa egy láncolt listává degradálódik. Így a keresés már nem logaritmikus időben fut!

12. A preorder bejárás II.

gyökér–bal–jobb

A preorder bejárás lényege: a gyökeret vesszük előre!

  1. Vegyük sorra az aktuális elemet,
  2. Járjuk be az aktuális elem bal részfáját,
  3. Járjuk be az aktuális elem jobb részfáját.

 

A fájl pointerét, amelybe írjuk az adatokat, természetesen át kell adni paraméterként mindenhol:

void fajlba_kiir(BinFa *gyoker, FILE *fajl) {
   if (gyoker == NULL)   // leállási feltétel
      return;

   fprintf(fajl, "%d ", gyoker->adat); // 1
   fajlba_kiir(gyoker->bal, fajl);         // 2
   fajlba_kiir(gyoker->jobb, fajl);    // 3
}

13. Műveletek fákon – általában

Sokféle kérdés feltehető egy fával kapcsolatban:

  • Hány eleme van? Hány levele van? Milyen magas?
  • Mekkora egy adott szintjén lévő elemek száma?
  • Hányadik szintig van teljesen betöltve?

A fenti feladatokat rekurzív algoritmusokkal lehet könnyen megoldani.


A megoldás sémája

  1. A feladatot megoldjuk a bal részfára (rekurzív hívás)
  2. A feladatot megoldjuk a jobb részfára (rekurzív hívás)
  3. Számbavesszük az aktuális elemet

14. Műveletek – fák elemszáma

Feladat: számoljuk meg, hogy hány eleme van egy fának!

  1. Ha üres a fa (NULL pointert kaptunk), térjünk vissza 0-val!
  2. Különben vegyük az aktuális elem bal részfájának az elemszámát!
  3. Adjuk hozzá a jobb részfa elemszámát!
  4. Adjunk hozzá 1-et (aktuális elem)! Térjünk vissza így.

A levelek
gyerekeire is
1 fut le!
int elemszam(BinFa *gyoker) {
   if (gyoker == NULL) return 0; // 1

   return elemszam(gyoker->bal)  // 2
        + elemszam(gyoker->jobb)    // 3
        + 1;                     // 4
}

Elv: amennyi a bal, plusz a jobb oldalon, meg még a gyökér.

Valójában az történik, hogy a return utáni kifejezésben bejárjuk a fát.

Ha üres fára hívjuk meg a függvényt, akkor 0-val tér vissza. De ez nem csak akkor történik, amikor az egész fa üres, hanem minden nem létező gyermeknél, sőt egy levélelemnél kétszer is, mert annak bal és jobb pointere is NULL pointer.

Ezért tér vissza egy levélnél 1-gyel a függvény. A levélben a 2-es hívás visszatér 0-val (mert a bal pointere NULL), a 3-as hívás is visszatér 0-val (mert jobb oldali gyermeke sincs a levélnek), és ehhez a 0+0-hoz adunk még egyet, ami a levél maga.

Bármelyik másik részfában hasonlóan történik a számlálás; előbb az adott csomópont bal oldali részfájának elemeit számoljuk meg, majd a jobb oldali részfájának elemeit, végül pedig hozzáadunk 1-et, mert a vizsgált csomópont egy elemnek számít.

15. Műveletek – levelek száma

Levelek száma: hasonló, de feltételhez kell kötni a számlálást:

  1. Ha üres a fa (NULL pointert kaptunk), térjünk vissza 0-val!
  2. Ha az aktuális elem levél, térjünk vissza 1-gyel!
  3. Különben vegyük az aktuális elem bal részfájában a levelek számát, adjuk hozzá a jobb részfa leveleinek számát, térjünk ezzel vissza!
int levelszam(BinFa *gyoker) {
   if (gyoker == NULL) return 0;          // 1

   if (gyoker->bal == NULL && gyoker->jobb == NULL) // 2
      return 1;

   return levelszam(gyoker->bal)          // 3
        + levelszam(gyoker->jobb);
}

Elv: ha ennek nincs gyereke, akkor levél, tehát 1.

Itt is bejárjuk a fát.

  • Ha egy levélhez jutunk, akkor egyet adunk vissza, hiszen neki már nem lehetnek gyermekei, ahonnan egyéb érték érkezhetne. Ilyenkor függvényhívásra sincs már szükség (hiszen nincsenek részfák, amelyekben számolni kellene bármit is).
  • Ha nem levélen állunk, akkor megszámláljuk a bal részfában a leveleket (rekurzívan meghívjuk a függvényt a bal gyermekre, majd ugyanezt megtesszük a jobb részfában és a kettő összegével térünk vissza.
  • Üres fa, vagy nemlétező gyermek esetén 0-val térünk vissza.

Figyeljük meg, hogy csak akkor nem hívjuk meg a gyermekekre a függvényt, ha levélben vagyunk. Olyankor ha csak az egyik gyermek NULL, meghívjuk rá, tehát ilyenkor is az (1) feltétel fut le.

16. Műveletek – elemek adott szinten

Feladat: adott szinten hány elem van?

  1. Üres fa esetén a visszatérési érték 0.
  2. Ha az átvett szint értéke 0, akkor azt a szintet kell megszámolni: visszatér 1-gyel.
  3. Különben megszámolja a bal és jobb részfában a megfelelő elemeket. Ehhez a szintet eggyel csökkentve hívja magát.
int szint_elemei(BinFa *gyoker, int szint) {
   if (gyoker == NULL) return 0;   // 1
   if (szint == 0) return 1;   // 2

   return szint_elemei(gyoker->bal,  szint-1)  // 3
        + szint_elemei(gyoker->jobb, szint-1);
}

A fontos mozzanat itt az, hogy ennek a függvénynek nem csak, hogy van egy paramétere, de azt a paramétert a rekurzióban változtatja is. Hogy hány csúcs van az ötödik szinten, ahhoz azt kell összeadni, hogy hány csúcs van a bal és a jobb oldali részfában a negyedik szinten. Az ő gyökerükhöz képest negyedik szinten!

Az algoritmus hasonló a levelek számának meghatározásához: az adott szinten „elvágjuk a fát”, az ott található elemeket levélnek tekintjük, mélyebbre már nem megyünk. Az adott szintre visszaszámlálással jutunk, amikor a szint értéke 0, akkor regisztráljuk, hogy találtunk egy elemet (és nem nézzük tovább a gyerekeket).

17. Keresőfa építése

Rekurzívan könnyű az új elem hozzáadása a keresőfához:

  • Ha a fa üres, akkor gyökér lesz az új.
  • Ha a gyökérnél kisebb az új, a bal oldali részfába kell beszúrni.
  • Ha a gyökérnél nagyobb, a jobb oldaliba.
  • Amúgy pedig már benne van.

Csakhogy közben változhat a fa gyökere pointer!

Ez ugyanúgy probléma, mint a láncolt listába beszúráskor. Ott is a mellékhatás volt a lényeg, hogy változik a lista, és itt is az: változik a fa. Ezt a problémát megoldhatjuk a listáknál megismert módszerrel: mindig visszatérünk a fa gyökerét mutató pointerrel, és a hívóra bízzuk, hogy írja ezt be az azt tároló változóba.

BinFa *gyoker = NULL;

gyoker = beszur(gyoker, 5);
gyoker = beszur(gyoker, 3);
gyoker = beszur(gyoker, 8);

Megoldás: térjünk vissza vele, mint a listáknál.

BinFa *beszur(BinFa *gyoker, int adat) {
    if (gyoker == NULL) {                        // üres?
        BinFa *uj = (BinFa*) malloc(sizeof(BinFa));
        uj->bal = uj->jobb = NULL;    /* levél lesz */
        uj->adat = adat;
        return uj;     /* vissza kell térni vele! */
    }

    if (adat < gyoker->adat)                // kisebb?
        gyoker->bal = beszur(gyoker->bal, adat);
    else if (adat > gyoker->adat)                // nagyobb?
        gyoker->jobb = beszur(gyoker->jobb, adat);
    else
        ; /* benne van */

    return gyoker;
}

Fontos végiggondolni, mi történik az egyes mutatókkal. Tegyük fel, hogy a függvényt a következő formában hívták meg:

gyoker = beszur(gyoker, 5);
  • Ha a fa üres, akkor gyoker=NULL. Ilyenkor az 1-es feltétel igaz lesz, és keletkezik egy új elem. A paraméterként kapott gyökér pointert, amely egy lokális változó, felülírjuk az új elem címével. Végülis pedig majd visszatérünk ezzel, és az eredeti gyökér mutatót a hívás után az értékadás fogja átállítani.
  • Ha a fa nem üres, akkor a gyökerében van egy elem. Ennek értékétől függ, hogy az új elemet a bal vagy a jobb oldali részfába kell szúrni. Ha a gyökérnél kisebb a beszúrandó, oda kell kerülnie (2).
  • Ha a jobb oldali részfába kerül az elem, akkor ugyanez a helyzet.
  • Ha se nem kisebb, se nem nagyobb, akkor a gyökérelemben azt látjuk, amit amúgy is be kell szúrni. Ilyenkor simán visszatérünk, nincs teendő, hiszen az elem már szerepel a fában. A gyökér pointer változatlan.

Fontos mozzanat az utolsó: hogy visszatérünk a változatlan gyökér pointerrel. A hívó ugyanis az értékadást mindenképpen elvégzi, és ilyenkor azt kell biztosítani, hogy a teljes fa gyökér pointere ne változzon – ehhez pedig egyszerűen visszaadjuk ugyanazt a gyökér pointert, amit kaptunk.

Ha a gyökér létezik, és annak a bal oldali részfájába szúrunk be, akkor hasonlóan megy minden. Ha ott NULL pointer van, akkor az felülíródik. Ha nem NULL, akkor az ott meghívott függvény változatlan gyoker pointerrel tér vissza, azaz az értékadásból gyoker->bal=gyoker->bal lesz végül. Minden helyen ez lesz a helyzet, kivétel ott, ahol valamelyik részfa üres fa!

Ebből következik a függvény hívásának módja a függvény belsejében is. Ha azt mondtuk, hogy a függvényt így kell használni:

gyoker = beszur(gyoker, 5);

Akkor a bal oldali részfába beszúrásnál ezt kell írnunk:

gyoker->bal = beszur(gyoker->bal, 5);

18. Példa – szavak statisztikája

Feladat: készítsünk beolvasott szavakról statisztikát! Melyik, hányszor szerepel?


kutya 2
cica 6
mérési 4
hiba 1

Megoldás: sorban haladunk a fájl szavain; ha az aktuális szó még nincs benne a fában, akkor betesszük és a darabszámot 1-re állítjuk; Ha már benne van, akkor megnöveljük a darabszámot.

A fák ideálisak erre a feladatra, hiszen gyors a beszúrás és az „eleme-e” művelet. Bónusz: ábécé rendben kapjuk meg az eredményt. A feladathoz szükséges adatstruktúra:

typedef struct SzoStat {
   char szo[51];
   int db;
   struct SzoStat *bal, *jobb;
} SzoStat;
Letölthető:
szostat.c

A szabványos bemeneten érkező szöveg statisztikájának az elkészítése:

Kihasználjuk, hogy
a scanf %s
whitespace-ig olvas
int main(void) {
   SzoStat *fa = NULL; // üres fa
   char szo[51];

   while (scanf("%s", szo) == 1)
      fa = beszur(fa, szo);

   kiir(fa);
   felszabadit(fa);

   return 0;
}

A szükséges módosítás a beszúró algoritmuson: le kell kezelni azt az esetet, amikor az elem már benne van a fában, és strcmp()-vel kell végezni a sztringek összehasonlítását.

SzoStat *beszur(SzoStat *gyoker, char *szo) {
    if (gyoker == NULL) {
        SzoStat *uj = (SzoStat*) malloc(sizeof(SzoStat));
        strcpy(uj->szo, szo);
        uj->db = 1;
        uj->bal = uj->jobb = NULL;
        return uj;     /* vissza kell térni vele! */
    }
    int er = strcmp(szo, gyoker->szo);
    if (er < 0)
        gyoker->bal = beszur(gyoker->bal, szo);
    else if (er > 0)
        gyoker->jobb = beszur(gyoker->jobb, szo);
    else
        gyoker->db++;

    return gyoker;
}

19. Fák alkalmazásai – hierarchia

Hierarchia tárolása.
Műveletek, pl. (2+3)*5.
Nincs szükség zárójelezésre!
Dekódoló fa.
Morze: ti = balra, tá = jobbra.

20. Fák alkalmazásai – további alakok

struct TriFa {
   …

   struct TriFa *bal,
                *kozep,
                *jobb;
};
háromágú fa

Az elvek ugyanazok, mint a bináris fánál. Pl. elemek száma:

  1. Ha NULL pointer, akkor 0.
  2. Egyébként be kell járni az összes részfát.
  3. Az elemek száma azok elemszámának összege + 1.
struct BinFa {
   …

   struct BinFa *szulo;
   struct BinFa *bal, *jobb;
};
szülőkre mutató pointerrel

Így egyszerűbb:

  • Iteratív bejárás „jobbra tapogatózva”
  • Törlés

Érdemes megfigyelni: nyelvileg nem különbözik a két struktúra egymástól. Csak máshogyan használjuk a pointereket!

A bináris fából törlés sem triviális művelet – főleg, ha a törlendő csúcsnak bal és jobb oldali szomszédja is van. Ilyenkor a fát át kell rendezni, ha a keresőfa tulajdonságot meg szeretnénk tartani. Ezzel is az Algoritmuselmélet tárgy fog foglalkozni.

21. Fák alkalmazásai – hatékonyság

B-fák, AVL-fák, …
„Algoritmuselmélet” tárgy

Kiegyensúlyozott fa: bármely csúcspont részfáinak magassága közötti különbség legfeljebb egy. (A bal oldali nem ilyen.)


Ha a fa nem kiegyensúlyozott, akkor a keresés lassabb. Az ebben az előadásban bemutatott faépítő algoritmusok nem kiegyensúlyozott fát építenek. Az általuk épített fa kiegyensúlyozottsága attól függ, mennyire érkeznek szerencsésen a beszúrandó adatok. A kiegyensúlyozott építéshez összetettebb algoritmusok szükségesek – ezeket majd az Algoritmuselmélet nevű tárgy fogja bemutatni.

Kettős indirekcó

23. Indirekció – cím szerinti paraméterátadás

C-ben csak érték szerinti paraméterátadás van. A függvények a paraméterek másolatát kapják.

A cím szerinti paraméterátadás megoldható pointerrel:

void novel(int *pi) {
    (*pi)++;       // a mutatott integert
}


int x = 5;
novel(&x);         // x-re mutat

printf("%d", x);

A listás, fás algoritmusaink megváltoztatják a lista eleje, fa gyökere mutatót. Ötlet: azt ugyanígy kellene átadni!

Ez azért lehetséges, mert a pointer ugyanolyan változó, mnint a többi. Vegyük példának a lenti függvényt. Ez két VALAMI-t cserél meg. Hogy a cseréket el tudja végezni, a függvény nem érték szerint várja a paramétereit (azaz a változók másolatát), hanem cím szerint (pointereket az eredeti változókra). A kódban VALAMI helyére bármilyen típust beírhatunk: kapunk egy függvényt, amely két adott típusú dolgot kell megcserélni.

p1: mutató egy VALAMI-re
*p1: egy VALAMI
void csere(VALAMI *p1, VALAMI *p2) {
   VALAMI temp = *p1;
   *p1 = *p2;
   *p2 = temp;
}

Ha két int-et szeretnénk cserélni, akkor a VALAMI helyre int-et írunk. Ha két int*-ot, akkor a VALAMI helyére int* kerül.

void int_csere(int *p1, int *p2) {
   int temp = *p1;
   *p1 = *p2;
   *p2 = temp;
}

int x = 29; int y = 17;
int_csere(&x, &y); /* x=17, y=29 */
void ptr_csere(int **p1, int **p2) {
   int *temp = *p1;
   *p1 = *p2;
   *p2 = temp;
}

int *px = &x; int *py = &y;
ptr_csere(&px, &py); /* px=&y, py=&x */

24. Kettős indirekció: lista építése – használat

Eddig a listák építésekor a visszaadott mutatót bemásoltuk a változóba:

ListaElem *eleje = NULL;

eleje = elore_beszur(eleje, 2);
eleje = elore_beszur(eleje, 3);

A mostani tervünk: adjuk át cím szerint, rábízva a változtatást!

Sokkal jobb
megoldás!
ListaElem *eleje = NULL;

elore_beszur_ptr(&eleje, 2);
elore_beszur_ptr(&eleje, 3);

A nagy előny: így nem lehet kifelejteni az értékadást!

Figyeljük meg a használatok közötti különbséget! Az utóbbi megoldás kényelmetlennek tűnik, mert mindig ki kell tenni a címképző operátort. Viszont éppen ez az előnye! A lista eleje pointert tároló változó címe nem Lista*, hanem Lista** típusú adat; ha lefelejtjük a címképző operátort, a fordító szólni fog*, hiszen rossz típusú pointert adunk a függvénynek! A pointerrel visszatérős megoldásnál viszont nem szól, hiszen teljesen szokásos és elfogadott dolog az, ha egy függvény visszatérési értékét nem használjuk semmire. Egyébként az utóbbi megoldással felszabadult a visszatérési érték is, amit bármire használhatunk.

* A rendes fordítók szólnak.

25. Kettős indirekció: lista építése

A lista elejére beszúró függvény a múltkori módon:

ListaElem *elore_beszur(ListaElem *eleje, int adat) {
   ListaElem *uj = (ListaElem*) malloc(sizeof(ListaElem));
   uj->adat = adat;
   uj->kovetkezo = eleje;
   return uj;
}

A másik változata, ami az „eleje” pointer címét veszi át:

A függvénynek meg kell tudnia változtatni a lista eleje mutatót:

void elore_beszur_ptr(ListaElem **peleje, int adat) { // !
   ListaElem *uj = (ListaElem*) malloc(sizeof(ListaElem));
   uj->adat = adat;
   uj->kovetkezo = *peleje; // *peleje – az első elem címe
   *peleje = uj;
}

A függvény belsejében:

peleje
Annak a változónak a címe, amely a lista elejét tárolja. Ez képződik a hívás helyén, amikor ott azt írjuk, hogy &eleje. Ez a main() lokális váltózójának címe.
*peleje
A lista elejének (első elemének, vagyis az első struktúrának) címe. Ez a hívó változójának értéke.
**peleje
Ez lenne a lista első eleme maga (a struktúra), de most nem használjuk.

26. Kettős indirekció – lista végéhez fűzés

Beszúrás lista végére, és az „eleje” mutató címének átvétele:

void vegere(ListaElem **peleje, int adat) {
   ListaElem *uj = (ListaElem*) malloc(sizeof(ListaElem));
   uj->adat = adat;
   uj->kov = NULL;

   if (*peleje == NULL)
      *peleje = uj;     // eleje ptr változik
   else {
      ListaElem *iter;
      for (iter = *peleje; iter->kov != NULL; iter = iter->kov)
         ; /* üres ciklus */
      iter->kov = uj;  // az utolsó „következő”-je változik
   }
}

Vegyük észre: van valahol egy ListaElem* mutató, amit be kell állítani. Vagy az utolsó elemben (az egyik listaelemen belül), vagy kívül, a hívónál (nem listaelemben)!

27. Kettős indirekció – lista végéhez fűzés 2.0

Egy lehetséges módosított algoritmushoz az előző felismerés adja az ötletet – nevezetesen az, hogy a lista végére szúrás azt jelenti, hogy meg kell keresni a lista végén azt a NULL pointert, amelyik lezárja azt. Mindegy, hogy ez a lista végi elemben van, vagy a lista eleje pointer a NULL (üres lista esetén) – a feladat az, hogy felülírjuk azt a mutatót az új elem címével.

void vegere(ListaElem **peleje, int adat) {
   ListaElem **pmozgo, *uj;

   pmozgo = peleje;        // pointer megkeresése
   while (*pmozgo != NULL)
      pmozgo = &(*pmozgo)->kov; // !

   uj = (ListaElem*) malloc(sizeof(ListaElem)); // új elem
   uj->adat = adat;
   uj->kov = NULL;
   *pmozgo = uj;           // a megtalált NULL pointer felülírása
}

A függvény elején a ciklus ezért ezt teszi: megkeresi azt a NULL pointert. A pmozgo pointer ennek a pointernek a címét tárolja. Először a lista eleje pointerre mutat, utána pedig minden lépésben a mutatott listaelem következő pointerére állítjuk át. Fontos az indirekciók számában a különbség: a pmozgo pointer itt nem a listaelemre mutató pointer, hanem a listaelemre mutató pointerre mutató pointer. Vagyis a listaelem címét tároló változó címe. Így először a hívó eleje pointerének címét tárolja, utána az első listaelem kov pointerének címét stb. Ezért van szükség a címképző operátorra is a ciklustörzsben: *pmozgo a listaelemre mutató pointer, (*pmozgo)->kov az abban tárolt „következő” pointer, &(*pmozgo)->kov pedig annak a címe.

28. Kettős indirekció – keresőfa építése

A keresőfába beszúráshoz meg kell keresni azt, hogy hol kell legyen a beszúrandó elemre mutató pointer. Ha a fa üres lenne, akkor a legfelső, azaz a gyökérpointert kellene úgy módosítani, hogy az az új elemre mutasson. Ha a 0-t szeretnénk beszúrni, akkor az 1-es csomópont bal pointerét (amely jelenleg NULL pointer) kell úgy módosítani, hogy az az új elemre mutasson. Ha a 4-est keressük, az benne van a fában – a 3-as csomópont jobb pointere az, amely rá mutat, és ilyenkor a beszúráshoz nem kell tenni semmit.

Azt keressük, hogy hol az a pointer, amely majd mutat rá.
Ez valamelyik csomópont bal/jobb pointere, vagy a gyökér pointere.

Ha van egy ilyen keresőalgoritmusunk, amely nem a keresett elemre mutató pointert adja vissza, hanem a keresett elemre mutató pointer címét, akkor könnyű a beszúrás. Ha nincs meg a keresett elem, ez akkor is értékes választ ad: a visszaadott pointer egy olyan pointerre mutat, amely értéke NULL, de ott kellene legyen a keresett elemre mutató pointer. A beszúrás:

/* új csomópontot szúr a keresőfába.
 * A gyökerpointert cím szerint veszi át. */
void beszur(BinFa **pgyoker, int adat) {
   /* megkeresi a helyét */
   BinFa **ptr = beszurashoz_keres(pgyoker, adat);

   if (*ptr == NULL) {                   // ha még nincs
      BinFa *uj = (BinFa*) malloc(sizeof(BinFa));
      uj->adat = adat;

      uj->bal = uj->jobb = NULL;
      *ptr = uj;                         // beszúrás
   }
}

A *ptr=uj; kifejezés

  • üres fa esetén a függvényen kívüli, a fa gyökerére mutató pointert változtatja meg,
  • nem üres fában valamelyik csomópont bal vagy jobb mutatóját változtatja meg, amely eddig NULL értékű volt, és ahová új levélként bekerül a beszúrandó elem.

Fontos, hogy ez a beszúró függvény cím szerint vegye át a gyökér címét is: BinFa **pgyoker. Ha egy teljesen üres fába szúrunk be elemet, akkor az meg kell változzon:

BinFa *gyoker = NULL;
beszur(&gyoker, 5);

Ugyanezért kell a kereső algoritmusnak is cím szerint átadni a pointert: ha a fa üres, a kereső algoritmus a gyökérelem pointer címével kell visszatérjen (annak címével amely egyelőre még NULL, és az ebben a példában az egész, üres fa gyökere).

A kettős indirekció a keresésben:

/* Megkeresi az adott elem (leendő) helyét a fában.
 * Egy olyan címet ad vissza, ahol a leendő elem címének
 * kell tárolódnia, vagy ahol a megtalált elem címe tárolódik. */
BinFa **beszurashoz_keres(BinFa **pgyoker, int adat) {
   BinFa **pmozgo = pgyoker;

   while (*pmozgo != NULL && (*pmozgo)->adat != adat) {
      if (adat < (*pmozgo)->adat)
         pmozgo = &(*pmozgo)->bal;
      else
         pmozgo = &(*pmozgo)->jobb;
   }

   return pmozgo;
}

Mivel mutatók címével tér vissza, azok értékét felül tudjuk írni.

Emlékeztetőül itt a kétszeres indirekció nélküli keresés. Érdemes összehasonlítani – lényegében annyi a különbség, hogy egyikben mindenhol mozgo van, másikban mindenhol *pmozgo. Ahol a lentiben konkrét érték van (mozgo), ott a fentiben cím, amelyet dereferálni kell (*pmozgo). Ahova a lentiben konkrét érték kerül (mozgo=), oda a fentiben cím kell (pmozgo=), ezért címet kell képezni (pmozgo=&...).

BinFa *keres(BinFa *gyoker, int adat) {
   BinFa *mozgo = gyoker;

   while (mozgo != NULL && mozgo->adat != adat) {
      if (adat < mozgo->adat)
         mozgo = mozgo->bal;
      else
         mozgo = mozgo->jobb;
   }

   return mozgo;
}

Hash táblák

30. A tanult adatszerkezetek


Eddig az alábbi adatszerkezetekkel ismerkedtünk meg:

  • tömbök,
  • láncolt listák,
  • bináris fák.

Mindnek megvannak az előnyei és a hátrányai. Alaposan ismerni kell a felépítésüket, működésüket, algoritmusaikat ahhoz, hogy képesek legyünk eldönteni, egy adott feladathoz melyik illik a legjobban.

 ElérésKeresésBeszúrásTörlés
Tömb1nnn
Listann11
Falog nlog nlog nlog n

Tömb

Mikor használjuk: ha az adatok száma keveset változik és kritikus a rendkívül gyors adatelérés. A rendezett tömbök esetén lehetséges bináris keresés, de a rendezés költséges művelet.

Előnyök:

  • gyors, tetszőleges sorrendű adatelérés (a leggyorsabb),
  • csak annyi helyet foglalnak el a memóriában, amennyi a hasznos adat,
  • hatékony rendező algoritmusok léteznek tömbökre.

Hátrányok:

  • az átméretezésük költséges – gyakran változó mennyiségű adathoz nem alkalmasak,
  • a feltöltés közbeni rendezésük költséges.

Láncolt lista

Mikor használjuk: ha az adatok száma gyakran változik és a keresés nem időkritikus, vagy nem is kell keresni (pl. ha mindig a feltöltés (fordított) sorrendjében van szükség az elemekre: vermek, sorok).

Előnyök:

  • egyszerű bővíthetőség (rendezetlennél a leggyorsabb),
  • egyszerű törlés (nem kell mozgatni az elemeket),
  • egyszerű (bár nem a leghatékonyabb) rendezve építés.

Hátrányok:

  • az elemek csak lineárisan kereshetőek.

Bináris fa

Mikor használjuk: ha az adatok száma gyakran változik és a fontos rendezettség, illetve a gyors keresés. Előnyös halmazok, asszociatív tömbök (sztring alapján „indexelhető”) megvalósítására.

Előnyök:

  • egyszerű bővíthetőség (a rendezettnél a leggyorsabb),
  • egyszerű és hatékony rendezve építés,
  • nagyon gyors keresés (kb. a tömbök sebességével megegyező).

Hátrányok:

  • egy elem törlése bonyolult feladat (át kell rendezni a fát).

Hogyan lehetne Θ(1) lépésben keresni?

Honnan tudjuk, hogy hol keressük? Onnan, hogy tudjuk, hova raktuk!

31. A hasító táblázatok röviden

A hasító táblázatok (hash table) ötlete az, hogy foglalunk egy nagy tömböt, amelybe az adatokat tesszük, és kitalálunk egy olyan függvényt, amely a tárolandó adatokat (értékek, pl. telefonszám) a keresés kulcsa (pl. név) szerint szétszórja a tömbben (to hash = összekever, összezagyvál). Így bármikor, ha adott a kulcs, akkor a függvény megmondja a tömbindexet, és egyből, keresés nélkül látjuk is az elemet.

Láthatóan így a hash() függvény gyorsaság fogja meghatározni a keresés idejét: ha az visszatért, onnan már csak egy tömbindexelés van hátra, és megtaláltuk az adatot.

A használat elve:

Adat hash_tabla[MERET]; // a hash tábla: tömb

printf("Telefon: %s\n", hash_tabla[hash("Taz")].telszam);

32. A hasító függvény

A kulcsot le kell képezni a 0 … MÉRET-1 tartományra. Példa hash függvények (nem túl jók):

int egesz_hash(int i) {
   return i % MERET;
}
int sztring_hash(char *nev) {
   return ((nev[0]-'A')*26+(nev[1]-'a')) % MERET;
}

Ütközések: ha két kulcs ugyanoda „hashelődik”:

kulcs % MÉRET == (kulcs + MÉRET) % MÉRET

Pl. a fenti függvénnyel Taz és Tapsi Hapsi.

33. Ütközések kezelése – egymás után téve

Az ütköző adatokat egymás után helyezhetjük el a táblában.

Így az adatok elcsúszhatnak a helyükről. Az egymás utániaknál, ahol nem üres, lineárisan kell keresünk. Ez a törlésnél problémás: meg kell maradnia a törölt elemnek (különben megállna a keresés az üres elemnél), így nem szabad törölni, csak megjelölni, hogy törölt az elem. A tábla így szép lassan töredezetté válik, és időnként karbantartást igényel.

34. Ütközések kezelése – láncolt listával

Az ütköző elemeket láncolt listába is tehetjük. Kevés ütköző elem → néhány elem a listákban. Gyors keresés!

Az adatszerkezet:

typedef struct ListaElem {
    char nev[51];
    char telefonszam[20];
    struct ListaElem *kovetkezo;
} ListaElem;

ListaElem *hashtabla[MERET];  /* listák tömbje */

A használata:

char keresett[] = "Tapsi Hapsi";
index = hash(keresett);
talalt = listakeres(hashtabla[index], keresett);
if (talalt != NULL)
    printf("Telefonszáma: %s\n", talalt->telefonszam);
else
    printf("Nincs ilyen név!\n");

35. Hash tábla – további felhasználások

Google keresés?

  • Kulcs = keresett szó
  • Érték = weboldalak listája
  • Az ütközés természetes: egy szó több helyen megtalálható

Fájlcserélő: elosztott tábla

  • Kulcs = fájlnév, érték = fájl (vagy hivatkozás a fájlra)
  • Hasító függvény kimenete: mely gépen tároljuk az adatot
  • Pl. BitTorrentnél: fájl darabjai kinél találhatóak meg