Tripla indirekció

Feladat a következő: adott egy bináris keresőfa, amely egész számokat tartalmaz. Minden bal oldali részfában a gyökérnél kisebb elemek, jobb oldali részfákban pedig a gyökérnél nagyobb elemek vannak. A feladat az, hogy építsünk egy egész számokból álló listát, amely ugyanazokat a számokat tartalmazza, mint a fa – természetesen növekvő sorrendben.

typedef struct Fa {
    int adat;
    struct Fa *bal, *jobb;
} Fa;

typedef struct Lista {
    int adat;
    struct Lista *kov;
} Lista;

A feladat megoldása tulajdonképpen két részből áll. Először is, be kell járnunk a fát úgy, hogy növekvő sorrendben megkapjuk az elemeket. Eközben minden számot a keletkező lista végére kell fűznünk:

void fat_bejar(Fa *gyoker, Lista **peleje) {
    if (gyoker == NULL)
        return;
    fat_bejar(gyoker->bal, peleje);
    listaba(peleje, gyoker->adat);
    fat_bejar(gyoker->jobb, peleje);
}

Ez egyszerű, a szokásos bal→gyökér→jobb bejárás, az előadás kiírás (printf) példája lecserélve egy lista végére fűzésre. A lista építése is a szokásos, lista eleje mutató, megváltozik, kettős indirekció, utolsó elem megkeresése stb.:

void listaba(Lista **peleje, int adat) {
    Lista *uj = (Lista*) malloc(sizeof(Lista));
    uj->adat = adat;
    uj->kov = NULL;
    if (*peleje == NULL)
        *peleje = uj;
    else {
        Lista *iter;
        for (iter = *peleje; iter->kov != NULL; iter = iter->kov)
            ;
        iter->kov = uj;
    }
}

A feladatot már meg is oldottuk. A függvény használatához a hívónak rendelkeznie kell egy fával, és egy üres listával. A listának azért kell üresnek lennie (vagyis a pointernek, amit átad a hívó a fát bejáró függvénynek, NULL pointernek), mivel a fenti listaba() függvény mindig egy már meglévő listához fűz hozzá. A fa bal szélső elemét pedig egy üres listához kell hozzáfűzni. Hogy még ilyen elvárásunk se legyen a hívóval szemben, azaz ezzel se neki kelljen törődnie, írhatunk egy csomagoló (wrapper) függvény erre:

Lista *fabol_lista(Fa *gyoker) {
    Lista *ujlista = NULL;       // üres listával indulunk
    fat_bejar(gyoker, &ujlista);
    return ujlista;
}

Példa ennek használatára:

Fa *fa = valahonnan_van_egy_fa();

Lista *szamok;
szamok = fabol_lista(fa);

Észrevehetjük, hogy a létrehozott algoritmusunk Θ(n²) időben fut, mivel a fa minden elemére (n darab) újra megkeressük a lista végét (újabb n-es szorzó). Ha kicsit gondolkodunk, akkor rájöhetünk, két lehetőség is kínálkozik arra, hogy sokkal gyorsabb, Θ(n) időben futó algoritmust adjunk:

1. Megjegyezhetjük, hogy hol van a lista vége, és akkor nem kell minden lépésben újra megkeresni.
2. Vagy trükközünk: nem a lista végére, hanem a lista elejére szúrjuk be az elemeket, hiszen az sokkal egyszerűbb, Θ(1) lépésben megtehető. Ettől ugyan a sorrendjük megfordul, de nem gond, járjuk be a fát is fordítva, jobb→gyökér→bal sorrendben.

A fordított bejárás az igazán trükkös, hiszen nem csak gyorsabb, hanem még rövidebb is, mint az előbb adott. A másik, listavéget nyilvántartó módszernek viszont elvi és nyelvi érdekességei is vannak. Nézzük meg azt!

De előtte nézzünk meg egy egyszerűbb feladatot. Tegyük fel, nem listát, hanem tömböt kell építeni egy fából, pontosan ugyanilyen módszerrel. Hogyan tesszük azt? Először is, megszámoljuk, hány eleme van a fának, és foglalunk egy akkora tömböt. Aztán pedig, a fát bejáró függvénynek tudnia kell a tömb helyét (ez egy pointer a tömb elejére), és egyben kapnia kell egy tömbindexet is, hogy a tömbben hova kell tenni a következő elemet. Azonban ezt a tömbindexet módosítania is kell tudni, hogy később a további elemek is jó helyre kerüljenek. Ezért azt cím szerint adjuk át neki.

Miért? A lényeg az, hogy ez az int n nem lehet a bejáró függvénynek lokális változója, mert akkor annyi példány lenne belőle, amilyen mély a rekurzió – viszont csak egy kell legyen belőle. Tehát a függvényen kívül kell léteznie. Ezt úgy oldhatjuk meg, ha valahol máshol létrehozzuk azt a változót, és csak egy pointert kap rá a függvény. Ugyan a rá mutató pointerből (pn) sok másolat képződik a rekurzív hívások során, de azok mind ugyanarra az egyetlen egy int-re mutatnak: mindig ugyanaz az int indexel és az növelődik:

void fat_bejar_tombbemasol(Fa *gyoker, int *tomb, int *pn) {
    if (gyoker == NULL)
        return;

    fat_bejar_tombbemasol(gyoker->bal, tomb, pn);

    tomb[*pn] = gyoker->adat;
    ++*pn;

    fat_bejar_tombbemasol(gyoker->jobb, tomb, pn);
}

Bár ennek az n számank a bejáró függvényen kívül kell lennie, ez nem jelenti azt, hogy globális kell legyen. Elég, ha van egy másik függvény, amely létrehozza azt a bejárás idejére. Tehát kell legyen egy másik függvény is, amely létrehozza ezt az egész számot és nullára inicializálja (első tömbindex), és ad egy pointert a bejáró függvénynek erre a számra. Azért is kell neki pointert adni, mivel a bejáró függvénynek ezt módosítania kell tudni.

int *fabol_tomb(Fa *gyoker) {
    int *tomb = (int*) malloc(sizeof(int) * elemszam(gyoker));
    int n;

    n = 0;
    fat_bejar_tombbemasol(gyoker, tomb, &n);

    return tomb; /* meg a méretét is vissza kellene adni */
}

Mire a bejáró végez, éppen annyi elem kerül bele a tömbbe, ahány csomópontja a fának van. Vagyis annyiszor növelődik meg *pn.

Ott tartottunk a listás verzió kapcsán, hogy jegyezzük meg, hol van a lista vége. Jó ötletnek tűnik az utolsó listaelemet nyilvántartani, de ez a gondolat mégsem vezet messzire, ugyanis üres listánál az még nem is létezik. Ehelyett azt kell tudnunk mindig, hova kell tennünk az újonnan létrejött elem pointerét: ez lehet a lista eleje pointer, de lehet valamelyik listaelemnek a kov pointere is.

Egy új elem hozzáfűzése a következőképpen néz ki. Adott egy beszúrandó adat, és egy *phova pointer, ahova a beszúrt elem címe kell kerüljön.

1. Lefoglaljuk a memóriát a csillaggal jelölt új elem számára, amire az uj pointer mutat.
2. Belemásoljuk az adatot.
3. NULL pointert teszünk a kov pointerébe (hiszen lista végi elem lesz).
4. Beállítjuk a pointert, amelynek erre az elemre kell mutatnia: *phova. (Ha ez a legelső elem, akkor ez különálló a lista eleje pointer; ha egy későbbi, akkor pedig egy listaelem által tartalmazott.)
5. A phova pointert végül átállítjuk az új elem kov pointerére, mert a következő elem uj pointerét (ha lesz még olyan) ide kell majd másolni.

C nyelven a kódkezdeményünk:

void fat_bejar_hozzafuz(Fa *gyoker, Lista **phova???) {
    Lista *uj;
    
    if (gyoker == NULL)
        return;
    
    fat_bejar_hozzafuz(gyoker->bal, phova???);

    uj = (Lista*) malloc(sizeof(Lista)); /* 1 */
    uj->adat = gyoker->adat;             /* 2 */
    uj->kov = NULL;                      /* 3 */
    *phova = uj;                         /* 4 */
    phova??? = &uj->kov;                 /* 5 */

    fat_bejar_hozzafuz(gyoker->jobb, phova???);
}

A ??? jelű részeknél látszik, hogy ez egyelőre még sántít. Miért? Elvileg a phova munkaváltozóból, amely pointerként azt mutatja, hogy hova kell majd tenni a következőleg létrehozott listaelem pointerét, az egész listaépítés során egy darabnak kell lennie. Akármilyen mélyre is megyünk a rekurzióban, ebből nem jöhet létre több, és mindegyik rekurzív függvénypéldának ugyanarról a phova pointerről kell beszélnie. Emiatt ez lokális változója nem lehet a fat_bejar_hozzafuz függvénynek, és így érték szerint átvett paramétere sem, mert akkor hívásonként több lenne belőle.

Vagyis ezt a változót a függvényen kívül kell létrehoznunk. Ugyanakkor e függvény képes kell legyen arra is, hogy megváltoztassa ennek a pointernek az értékét, hiszen mindig más helyre (mindig egy új listaelemben lévő kov pointerre) kell mutasson. Mi következik ebből? (Ha kizárjuk a globális változót, amit természetesen elvből megteszünk, hiszen nem arról van szó, hogy sok függvény és sok modul kell lássa ezt a pointert, hanem csak ez az egyetlen egy!) Az, hogy kell legyen egy hívó függvény, amely létrehozza a phova változót, és a fát bejáró függvény ezt cím szerint kapja! Na és mi a típusa annak a pointernek, amely egy Lista** típusú változóra mutat? Természetesen Lista***!

A fát bejáró függvény, és a bejárást elindító, phova változót létrehozó függvény:

void fat_bejar_hozzafuz(Fa *gyoker, Lista ***pphova) { // OMG 3× indirekció
    Lista *uj;

    if (gyoker == NULL)
        return;

    fat_bejar_hozzafuz(gyoker->bal, pphova);

    uj = (Lista*) malloc(sizeof(Lista));
    uj->adat = gyoker->adat;
    uj->kov = NULL;
    **pphova = uj;
    *pphova = &uj->kov;

    fat_bejar_hozzafuz(gyoker->jobb, pphova);
}

Lista *fabol_lista(Fa *gyoker) {
    Lista *eleje = NULL;       /* a keletkező lista */
    Lista **phova = &eleje;    /* a lépegető pointer */

    fat_bejar_hozzafuz(gyoker, &phova);

    return eleje;
}

A phova változó természetesen lehet lokális, de a bejárást indító függvény lokálisa kell legyen. A bejárás előtt létrejön, és a bejárás alatt van rá csak szükség, tehát a bejárás után megszűnhet.

Egy dolgot érdemes még megfigyelni. A fát bejáró függvény, amikor az újonnan létrejött listaelemet beilleszti a listába, nem figyeli, hogy mi van az adott pointerben. Csak simán felülírja azt: **pphova=uj. Emiatt az indító függvényben felesleges NULL pointerrel inicializálni a lista eleje pointert. Mindegy, mi van ott, mert úgyis felül lesz írva.

Sőt ez az összes többi pointerre is igaz! Bár a fenti kódban minden létrejövő listaelem kov pointerét NULL-ra állítjuk, ezt az utolsó elem kivételével mindegyiknél feleslegesen tesszük, mert azok is felül lesznek írva a következő elem létrehozása után. Így azokat sem kell NULL-ra állítani, hanem ott lehet hagyni őket inicializálatlanul, mert a következő listaelemnél felülíródnak majd. Csak a legutolsóba kell NULL-t tenni. Ezt a bejárás után könnyedén meg tudjuk tenni a fabol_lista() csomagoló függvényben is, kérdés csak, hogy hol is van az a pointer, amit most NULL-ra kéne állítani?! Elvileg a lista végén, de ezt nem kell megkeresni. Észrevehetjük, hogy ez pont az a pointer, ahova a következő listaelem pointere is került volna… Azt pedig tudjuk, hol van, hiszen a fat_bejar_hozzafuz() függvény mindvégig kezelte a phova változót, és az most pont oda mutat, ahova kell! Tehát egy *phova = NULL megoldja a dolgot.

A függvények teljes pompájukban:

void fat_bejar_hozzafuz(Fa *gyoker, Lista ***pphova) {
    Lista *uj;

    if (gyoker == NULL)
        return;

    fat_bejar_hozzafuz(gyoker->bal, pphova);

    uj = (Lista*) malloc(sizeof(Lista));
    uj->adat = gyoker->adat;
    **pphova = uj;
    *pphova = &uj->kov;

    fat_bejar_hozzafuz(gyoker->jobb, pphova);
}

Lista *fabol_lista(Fa *gyoker) {
    Lista *eleje;
    Lista **phova = &eleje;

    fat_bejar_hozzafuz(gyoker, &phova);
    *phova = NULL;

    return eleje;
}

Vegyük észre: ha a fa üres, a bejáró függvény nem csinál semmit. Ilyenkor a phova pointer az eleje változóra mutat, amit rajta keresztül NULL-ra állítunk… És visszatérünk egy üres listával.

A program letölthető innen: fabol_lista.c.

A tanulság ebből az is, hogy a kettős indirekció segítségével is könnyedén építhetünk Θ(n) időben nem megfordított listát. Az alábbi program számokat olvas be -1-ig, és a beolvasás sorrendjében teszi őket egy listába:

#include <stdio.h>
#include <stdlib.h>

typedef struct Lista {
    int szam;
    struct Lista *kov;
} Lista;

int main(void) {
    Lista *eleje;

    /* beolvasás */
    {
        int i;
        Lista **pmozgo = &eleje;
        while (scanf("%d", &i) == 1 && i != -1) {
            Lista *uj = (Lista *) malloc(sizeof(Lista));
            uj->szam = i;
            *pmozgo = uj;
            pmozgo = &uj->kov;
        }
        *pmozgo = NULL;
    }

    /* csak teszt: kiírás és felszabadítás */
    {
        for (Lista *iter = eleje; iter != NULL; iter = iter->kov)
            printf("%d ", iter->szam);
        while (eleje != NULL) {
            Lista *temp = eleje->kov;
            free(eleje);
            eleje = temp;
        }
    }

    return 0;
}

A *pmozgo = uj kifejezés mindig azt a pointert írja felül, ahova a következő listaelem kerül; vagy a lista elejét mutató pointert, vagy a legutóbbi listaelem következő pointerét. Az új elemek kov pointerét a cikluson belül nem is kell NULL-ra állítani, mert úgyis lesz következő elem; vagy ha nem volt, akkor a ciklus utáni *pmozgo = NULL fogja ezt megtenni. Az eleje pointer sem kap értéket a program legelején, hiszen úgyis felül lesz írva, vagy az első listaelemmel, vagy ha egyáltalán nincs, a NULL pointerrel.

Az Θ(n) idejű „előrefelé” listaépítésre jó megoldás a visszafelé építés és utólagos megfordítás (az is Θ(n) idejű). Jó az is, ha külön esetként kezeljük az üres listát, illetve azt, ha már volt beszúrt elem (és az utóbbi pointerét tartjuk nyilván). Az utóbbiak is szép megoldások, sőt könnyebben megérthetőek, mint a fenti. Csak az a buta megoldás, ha minden beszúrásnál megkeressük a legutolsó elemet, hiszen az nem Θ(n), hanem Θ(n²) ideig tart – nagyobb listáknál vészesen belassul.