Generikus lista

Ez az oldal egy olyan duplán láncolt listát mutat be, amelyik bármiféle adatot képes tárolni. Ezt úgy oldja meg, hogy a listában tárolt adat csak egy pointer – hogy a programozó azt mire használja, az már az ő dolga.

Eddig a lista elemeinek adataihoz (pl. könyv címe, szerzője, megjelenési éve) adtunk hozzá egy pointert, ami lehetővé tette, hogy az adott struktúrából láncolt lista legyen. Akármilyen elemeket viszont nem fűzhetünk így listába – a struktúra megalkotásakor már a pointerrel gondolni kellett volna arra, hogy listát kell csinálni belőle. Érezhetően problémás, hogy a struktúra egyszerre tartalmazza az adatokat, és a listába fűzéshez szükséges pointereket.

Ehelyett csináljuk most azt, hogy létrehozunk egy ListaElem nevű struktúrát, amelyben csak egy void * mutató lesz. Ez tetszőleges típusú adatokra mutathat, amelyekhez a memóriát külön foglaljuk majd le:

typedef struct ListaElem {
    struct ListaElem *elozo, *kovetkezo;
    void *adat;
} ListaElem;

Tudjuk, hogy a void * típusú mutató bármilyen adatra mutathat. Ez azt jelenti, hogy a tetszőleges típusú adatunkra mutató pointert, pl. Pont *-ot betehetjük ide. Sajnos abban a pillanatban, hogy megtörténik a Pont*→void* konverzió, a típusinformáció elveszik. Ezért amikor az adatot kiolvassuk a láncolt listából, a pointert vissza kell alakítanunk a saját típusunkra, pl. egy (Pont*) cast-tal.

Építsünk a fenti struktúra segítségével duplán láncolt, mindkét végén strázsát használó listát:

/* ezek meg strazsak lesznek  */
typedef struct Lista {
    ListaElem *eleje, *vege;
} Lista;

Tegyünk bele dinamikusan foglalt sztringeket!

char *str = (char*) malloc(5*sizeof(char));          // din. foglalt adat
strcpy(str, "alma");

ListaElem *uj = (ListaElem *) malloc(sizeof(ListaElem));  // új listaelem
uj->kovetkezo = l->eleje->kovetkezo;
uj->elozo = l->eleje;
l->eleje->kovetkezo->elozo = uj;
l->eleje->kovetkezo = uj;

uj->adat = str;                                // char* → void*

Amikor a listaelembe betesszük a pointert, a saját típusunkra mutató pointerből void* típusú pointer lesz.

A lista bejárása a következő kódrészlettel lehetséges:

ListaElem *futo;

for (futo = l->eleje->kovetkezo; futo != l->vege; futo = futo->kovetkezo)
    … l->adat …; // teendő a listaelemmel

A lista bejárása ugyan általánosságban így működik, a listával elvégzendő teendő azonban a lista adatainak konkrét típusától függ. Vegyük itt észre az ellentmondást: a listát úgy hoztuk létre, hogy ne hivatkozzon a tartalmazott adatok típusára, és így szeretnénk megoldani a lista feldolgozását is. Azonban a listaelemek feldolgozásakor szükségünk van arra, hogy tudjuk, mi a típus, különben nem tudunk vele kezdeni semmit. Ha a konkrét feldolgozási lépést is betesszük a ciklusba, akkor elveszítjük a fenti kódrészlet általános jellegét.

Ennek a problémának a megoldása úgy lehetséges, ha a listaelemek feldolgozását a programrészen kívülre száműzzük. Például úgy, hogy egy függvényt hívunk meg minden listaelem által tartalmazott pointerre:

void lista_mindegyiken(Lista *l, void (*fv)(void *)) {
    ListaElem *futo;

    for (futo = l->eleje->kovetkezo; futo != l->vege; futo = futo->kovetkezo)
        fv(futo->adat); /* amit a hivo ker */
}

Figyeljük meg a függvényre mutató pointer típusát! A paraméterként átvett fv függvény void* mutatót kell átvegyen, hiszen a listakezelő függvény nem ismeri a tartalmazott adatokat. Aki használja a listát, az viszont igen. Például ha a lista sztringeket tartalmaz, akkor egy függvény, amely a fenti bejárás rutinnak átadható, a következő formájú lehet:

void string_kiir(void *string) {
    printf("%s ", (char*) string); // void* → char*
}

Ebben a pointert a lista használója visszaalakítja char* típusúvá. (Ezt megteheti, mivel ő tudja, hogy a listába char*-okat tett.) A bejáró függvény hívása:

lista_mindegyiken(&l, string_kiir);

Ha ez a lista dinamikusan foglalt sztringeket tartalmaz, akkor a lista felszabadítása a következőképpen történhet:

lista_mindegyiken(&l, free);
lista_felszabadit(&l);

Vagyis először felszabadítjuk mindegyik tartalmazott sztringet, utána pedig magukat a listaelemeket. Vegyük észre: a free() függvény kompatibilis a várt függvényre mutató pointerrel, hiszen az is void visszatéréséi értékű, és void* paraméterrel rendelkezik!

Írjunk függvényt, amelyik rendezi a listát!

Mi alapján rendezünk, ha azt se tudjuk, mit jelentenek a listaelemek? A rendezést, vagyis az elemek kisebb-nagyobb viszonyát eldöntő függvényt is paraméterként vesszük át, függvényre mutató pointerként. Az a függvény pedig két összehasonlítandó elem memóriacímét veszi majd át, és strcmp()-konvencióval adja meg a választ (negatív: *a<*b, nulla: *a=*b, pozitív: *a>*b). Egy ilyen függvény prototípusa így néz ki:

int osszehasonlit(void const *a, void const *b);

Egy láncolt listát rendezni sok rendező algoritmussal ugyanolyan egyszerű, mint tömböt. Csak az indexeléseket kell kicserélnünk listaműveletekre (ptr=ptr->kovetkezo stb.) Vegyük észre, hogy bár általánosságban egy lista rendezése hatékonyabb úgy, ha az elemeket láncoljuk, de itt most sokkal egyszerűbb, ha nem így teszünk, hanem csak a listaelemekben tárolt void* pointereket cseréljük:

typedef int (*ListaElemHasonlito)(void const *, void const *);

void lista_rendez(Lista *l, ListaElemHasonlito hasonlit) {
    ListaElem *meddig;

    /* ures listat nem rendezzuk. ez azert is kell, mivel
       kulonben a lenti while ciklus feltetele orokke igaz lenne */
    if (l->eleje->kovetkezo == l->vege)
        return;
    /* a meddig fogja tartalmazni az utolso osszehasonlitando
       elemet (amit mar nem kell osszehasonlitani majd,
       hiszen nincs utana kovetkezo) */
    meddig = l->vege->elozo;
    /* amikor a meddig elerte a legelso elemet,
       akkor mar nem lesz mit csinalni */
    while (meddig != l->eleje->kovetkezo) {
        ListaElem *futo;

        for (futo = l->eleje->kovetkezo; futo != meddig; futo = futo->kovetkezo)
            if (hasonlit(futo->adat, futo->kovetkezo->adat)>0) {
                /* egyszerubb az adataikat megcserelni,
                   hiszen az jelen esetben csak egy pointer */
                void *temp = futo->adat;
                futo->adat = futo->kovetkezo->adat;
                futo->kovetkezo->adat = temp;
            }

        /* az utolso elem a helyere kerult; ennyivel kevesebbet
           rendezunk a kovetkezo korben */
        meddig = meddig->elozo;
    }
}

A letölthető lista.zip-ben három fájl található. A lista.c és lista.h a generikus lista megvalósítása, a listaproba.c pedig egy rövid példaprogram a függvények használatára. Érdemes megfigyelni, hogy a listakezelő függvényekben, és egyáltalán azokban a fájlokban sehol egy szó nem esik a tárolt típusról! A lista képes lenne bármilyen más típust is tárolni.