12. gyakorlat: listás feladatok

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


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


/* csak hogy legyen teszt adat */
Lista *lista_letrehoz(void) {
    Lista *l = NULL;
    int j=20, i=-j;
    for (i=-j; i++ != 0; j*=17) {
        Lista* u=(Lista*)malloc(sizeof(Lista));
        u->kov=l;
        u->adat=j%=23;
        l=u;
    }
    return l;
}


/* kiírja a listát előrefelé. a lista a legelső elemből,
 * és a többi részéből áll (ami úgyszintén egy lista).
 * üres listánál nem kell csinálni semmit. */
void lista_kiir_elore(Lista *l) {
    if (l==NULL)
        return;
    printf("%d ", l->adat);
    lista_kiir_elore(l->kov);
}


/* kiírja a listát visszafelé. az előző függvényhez
 * képest csak megcseréltük a két hátsó sort: előbb a
 * lista "többi részét" írjuk ki, csak utána az első elemet.
 * mivel ezt nem csak az első elemnél, hanem az összesnél így
 * csináljuk, ezért nem csak az első elem kerül a végére,
 * hanem az egész megfordul. */
void lista_kiir_hatra(Lista *l) {
    if (l==NULL)
        return;
    lista_kiir_hatra(l->kov);
    printf("%d ", l->adat);
}


/* felszabadítjuk a listát. előbb fel kell szabadítani
 * az ebből az elemből kiinduló listát, utána pedig ezt
 * az elemet. az ötlet hasonló, mint a hátrafelé kiírásnál.
 * */
void lista_felszabadit(Lista *l) {
    if (l==NULL)
        return;
    lista_felszabadit(l->kov);
    free(l);
}


int main() {
    Lista *l = lista_letrehoz();
    
    lista_kiir_elore(l); printf("\n");
    lista_kiir_hatra(l); printf("\n");
    lista_felszabadit(l); 
    
    return 0;
}

A rekurziót csak a hátrafelé kiírásnál érdemes alkalmazni. Az előrefelé történő kiírás és a felszabadítás könnyedén megoldható ciklussal is, mivel a pointerek amúgy is előrefelé mutatnak a listában. Ilyenkor nem érdemes egy O(n) memóriaigényű megoldást választani az O(1) memóriaigényű helyett!

A verem tároló lényege, hogy ha beleteszünk egy adatot, az mindig a tetejére kerül, és ha kiveszünk belőle egyet, akkor azt mindig a tetejéről vesszük ki. Amelyik legutoljára bekerült, az jön ki elsőnek (LIFO, last in, first out). Vermet egyszeresen láncolt listából nagyon könnyű csinálni. Ha mindig a lista elejére szúrjuk az új elemet, és mindig a lista elejéről vesszük el, ha ki kell venni egyet, akkor pont vermet kapunk. (Azért érdemes a lista elejét, és nem a végét kezelni ilyen módon, mivel a lista eleje mutató így épp arra mutat, amire kell, nem kell végiglépkedni a lista végéig.)

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


typedef struct Verem {
    char karakter;
    struct Verem *alatta;
} Verem;


void verembe(Verem **v, char c) {
    Verem *uj=(Verem *) malloc(sizeof(Verem));
    uj->karakter=c;
    uj->alatta=*v;             /* alatta az eddigi legfelso lesz */
    *v=uj;                     /* mostantol ez van a tetejen */
}


char verembol(Verem **v) {
    Verem *elso=*v;            /* az elsot fogjuk eldobni */
    char adat=elso->karakter;  /* kimentjuk a szamot belole */
    *v=elso->alatta;           /* a masodik lesz az elso */
    free(elso);
    return adat;
}


int verem_ures(Verem **v) {
    return *v == NULL;
}


int main() {
    Verem *v=NULL;
    int c;
    
    printf("Kedves draga jo felhasznalo! Irj egy tetszolegesen hosszu szoveget, EOF-ig!\n");
    while ((c=getchar()) != EOF)
        verembe(&v, c);
    
    printf("Kedves draga jo felhasznalo! A szoveged visszafele:\n");
    while (!verem_ures(&v))
        putchar(verembol(&v));

    return 0;
}

A beérkező számokat el kell tárolnunk. Egészen addig, amíg egy művelet nem érkezik; amikor is pedig a legutóbbi két számon el kell végeznünk a műveletet. „Mindig a legutóbbi kettő”: ezt egy veremmel lehet megvalósítani. Ha pl. látunk egy összeadás jelet, akkor a verem tetejéről levett két számot összeadjuk, és az eredményt visszatesszük a verem tetejére (hiszen az később egy további művelet egyik operandusa lehet). Amikor a kifejezésnek vége van, elvileg egy szám kell legyen a veremben, és az maga az eredmény. Pl. az 5 7 9 * + kifejezés feldolgozása:

bejövő      verem
5         → [5]
7         → [7 5]
9         → [9 7 5]
*         → [63 5]
+         → [68]

A lenti program nem tartalmaz hibakezelést, csak helyes bemenetek esetén működik jól!

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


typedef struct Verem {
    double szam;
    struct Verem *alatta;
} Verem;


void verembe(Verem **v, double adat) {
    Verem *uj=(Verem *) malloc(sizeof(Verem));
    uj->szam=adat;
    uj->alatta=*v;    /* alatta az eddigi legfelso lesz */
    *v=uj;            /* mostantol ez van a tetejen */
}


double verembol(Verem **v) {
    Verem *elso=*v;            /* az elsot fogjuk eldobni */
    double adat=elso->szam;    /* kimentjuk a szamot belole */

    *v=elso->alatta;           /* a masodik lesz az elso */
    free(elso);                /* az elso meg nem kell */

    return adat;
}


int main() {
    Verem *v=NULL;
    char szo[50];
    double d;

    printf("Ird be a kifejezest, aztan adj egy fajl vege jelet!\n");
    printf("Pl.: 3 4 +\n\n");

    /* amig sikerul szot beolvasni */
    while (scanf("%s", szo) == 1) {
        /* nezzuk, hatha kulcsszo */
        if (strcmp(szo, "+")==0) {
            double tag1=verembol(&v);
            double tag2=verembol(&v);
            verembe(&v, tag1+tag2);
        }
        else if (strcmp(szo, "*")==0) {
            double tenyezo1=verembol(&v);
            double tenyezo2=verembol(&v);
            verembe(&v, tenyezo1*tenyezo2);
        }
        else if (strcmp(szo, "-")==0) {
            double kivonando=verembol(&v);
            double kisebbitendo=verembol(&v);
            verembe(&v, kisebbitendo-kivonando);
        }
        else if (strcmp(szo, "/")==0) {
            double oszto=verembol(&v);
            double osztando=verembol(&v);
            verembe(&v, osztando/oszto);
        }
        else {
            /* ha nem kulcsszo, probaljuk szamkent. */
            if (sscanf(szo, "%lf", &d)==1) {
                /* ha szam, berakjuk a verembe */
                verembe(&v, d);
            } else
                printf("Nem ertem: %s\n", szo);
        }
    }
    printf("%g\n", verembol(&v));

    return 0;
}

Az összeadás és a szorzás műveleténél elég lenne egy ilyen sort írnunk:

verembe(&v, verembol(&v)+verembol(&v));

Ez azonban nincs így a kivonásnál és az osztásnál. Azoknál ehhez hasonlót írni súlyos kódolási hiba lenne, mivel nem lehetne tudni, hogy előbb a kisebbítendőt (osztandót) vagy a kivonandót (osztót) venné ki a veremből a kódrészlet – hiszen a szabvány nem határozza meg, hogy melyik operandust kell előbb kiértékelni. A fenti módszerrel, külön utasításként leírva a veremből kivételeket azonban kényszeríthető a megfelelő kiértékelési sorrend. (Az összeadásnál és a szorzásnál, lévén kommutatív műveletek, teljesen mindegy, hogy melyik szám kerül ki a veremből először. Hiszen a+b=b+a, és a*b=b*a.)

A megoldásban egy fésűs listát kell alkalmazni: kívül a tankörök listája, és mindegyik tankör tartalmaz egy névsort (hallgatók listája).

Minden beolvasott hallgatónál előbb meg kell keresni a tankört (vagy létrehozni, ha még nincs), és utána abba a listába betenni. Mivel a feladat nem határozza meg a sorrendet, egyszerűen az elejére szúrjuk be az adatokat.

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


/* egy hallgato adatai - lancolt listaban */
typedef struct Hallgato {
    char neptun[6+1];       /* a neptun kodja, max 6 */
    char nev[30+1];         /* a neve, max 30 */
    double atlag;           /* az atlaga */
    struct Hallgato *kov;
} Hallgato;


/* egy tankor adatai: egy nevsor */
typedef struct Tankor {
    int szam;               /* sorszama */
    Hallgato *nevsor;       /* nevek */
    struct Tankor *kov;
} Tankor;


/* beolvassa a megadott nevu fajlbol az adatokat.
 * visszater egy új Tankor listaval. */
Tankor *tklista_beolvas(char const *fajlnev) {
    Tankor *tklista = NULL; /* ez lesz a kimenet */
    Hallgato temp;          /* a fajlbol olvasashoz */
    FILE *fp;
    int tk;
    
    fp = fopen(fajlnev, "rt");
    if (fp == NULL) return NULL;
    /* %[^\n] - sztring enterig */
    while (fscanf(fp, "%d %s %lf %[^\n]", &tk,
            temp.neptun, &temp.atlag, temp.nev)==4) {
        Tankor *iter;       /* tankorlista bejarashoz */
        Hallgato *ujh;      /* uj hallgato */
        
        for (iter=tklista; iter!=NULL && iter->szam!=tk; iter=iter->kov)
            ;   /* ures, csak keres */
        if (iter==NULL) {   /* ha null, nem lett meg, uj kell */
            iter = (Tankor*) malloc(sizeof(Tankor));
            iter->szam = tk;
            iter->kov = tklista;
            iter->nevsor = NULL;
            tklista = iter; /* elejere */
        }
        ujh = (Hallgato*) malloc(sizeof(Hallgato));
        *ujh = temp;        /* minden adatot bemasolunk! */
        ujh->kov = iter->nevsor;
        iter->nevsor = ujh; /* elejere */
    }
    return tklista;
}


/* kilistazza a tankort es a nevsorokat. */
void tklista_listaz(Tankor *tklista) {
    Tankor *tkiter;         /* tankorok iteratora */
    Hallgato *hgiter;       /* hallgatok iteratora */
    
    for (tkiter = tklista; tkiter!=NULL; tkiter=tkiter->kov) {
        printf("%2d. tankor -- \n", tkiter->szam);
        for (hgiter = tkiter->nevsor; hgiter!=NULL; hgiter=hgiter->kov)
            printf("%6s %-30s %g\n", hgiter->neptun, hgiter->nev, hgiter->atlag);
    }
}


void tklista_felszabadit(Tankor *tklista) {
    while (tklista != NULL) {
        Tankor *kov = tklista->kov;     /* kimentjuk */
        
        Hallgato *nevsor = tklista->nevsor;
        while (nevsor != NULL) {
            Hallgato *kov = nevsor->kov;   /* kimentjuk */
            free(nevsor);
            nevsor = kov;
        }
        
        free(tklista);
        tklista = kov;
    }
}


int main() {
    Tankor *tklista;        /* az osszes adat listaja */
    
    tklista = tklista_beolvas("nevek.txt");
    tklista_listaz(tklista);
    tklista_felszabadit(tklista);
    
    return 0;
}