Gyakorlat, 12. hét: láncolt listák II.

Két kézenfekvő megoldás kínálkozik:

• Építünk egy másik listát, amit halmazként használunk: csak akkor teszünk bele egy elemet, ha még nincs benne. Ennek a listának a hossza adja a megoldást.
• Vagy: végigmegyünk a listán, és minden elemnél megvizsgáljuk, hogy az előtte lévőek között szerepel-e. Ha nem, megnövelünk egy számlálót.

A második bonyolultabbnak hangzik, de valójában sokkal egyszerűbb megoldást ad:

int hany_kulonbozo(ListaElem *eleje) {
    int db = 0;
    for (ListaElem *iter = eleje; iter != NULL; iter = iter->kov) {
        /* van-e előtte ugyanilyen elem? */
        bool van = false;
        ListaElem *elozo = eleje;
        while (elozo != iter && !van) {
            if (strcmp(elozo->szo, iter->szo) == 0)
                van = true;
            elozo = elozo->kov;
        }
        /* ha nincs, bevesszük a számlálásba*/
        if (!van)
            db += 1;
    }
    return db;
}

1. Átlagnál kisebbek. Ehhez a számokat el kell tárolnunk, mivel az összes szám ismeretében tudjuk meg az átlagot, és akkor kezdhetjük csak el a kiírást. Láncolt listát kell alkalmazni, ha nem szeretnénk minden számnál újra és újra nyújtani, lemásolni a tömböt.
2. Prímszámok. Ehhez nem kell eltárolni a számokat, így a kérdés értelmetlen.
3. Visszafelé. Láncolt lista. Két lehetőségünk van: duplán láncolt listát használunk, mert visszafelé is szeretnénk haladni rajta; vagy egyszeresen láncoltat használunk veremként, hiszen annak eleve adott ez a tulajdonsága, hogy fordított sorrendben látszanak a betett elemek.
4. Százezer. Ehhez ugyan jó lenne a tömb, de ha arra számítunk, hogy jóval kevesebb szám lesz csak, akkor pazarlás a 100000 elem, és így jobb a láncolt lista. (Különösen igaz ez akkor, ha nem csak számok tárolandók, hanem valami nagyobb adatok.)
5. Szöveg. Dinamikus tömb, amelyet időnként átméretezünk. A listás megoldás pazarlás lenne (minden karakter mellé egy pointer!), és a keletkező adatszerkezetet nem tudnánk sztringként sem használni sehol (strlen, printf %s stb.)
6. Buszok. Fésűs lista, azaz listák listája. A „külső” listában a buszjáratok vannak, amelyekhez járatszámok, és darabonként egy megállólista („belső” listák) tartoznak.
7. Amőba. Átverés, ez 13×13-as tömb. Ha a letett o és x bábukat listában tárolnánk (mindegyik mellé felírva, hogy mely (x;y) koordinátára kerültek), akkor borzasztóan elbonyolódna egy elem „indexelése”, és így pl. a játékállás ellenőrzése.
8. Számok. Bináris fa, mert abban gyorsan lehet keresni.
9. Betűk. Ez viszont tömb. Mivel a számolandó elemek száma előre ismert és kicsi (mindössze 'z'-'a'+1=26 darab), nem érdemes a listával bajlódni.

A legnagyobb közös osztó a prímtényezős felbontások ismeretében O(n) lépésben is meghatározható, az összefésülés algoritmusával. Ha nem ilyen lett a kódod, oldd meg így is a feladatot!

Az alábbi mintamegoldás az O(n) lépésben futó összefésülést alkalmazza. A listát mindkét esetben (felbontás, osztó keresése) a végénél hozzáfűzve építi, nyilvántartva a lista végét.

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

typedef struct Tenyezo {
    int alap, kitevo;
    struct Tenyezo *kov;
} Tenyezo;

Tenyezo *felbontas(int n) {
    Tenyezo *lista = NULL;          /* ures lista */
    Tenyezo *vege = NULL;
    int oszto = 2;
    while (n > 1) {
        int kitevo = 0;
        while (n % oszto == 0) {    /* amig osztja, leosztjuk */
            n /= oszto;
            kitevo++;               /* es szamoljuk, hanyszor */
        }
        if (kitevo > 0) {           /* ha ez oszto volt, listaba vele */
            Tenyezo *uj = (Tenyezo *) malloc(sizeof(Tenyezo));
            uj->alap = oszto;
            uj->kitevo = kitevo;
            uj->kov = NULL;
            if (lista == NULL)
                lista = uj;
            else
                vege->kov = uj;
            vege = uj;
        }
        oszto++;
    }
    return lista;
}

void kiir(Tenyezo *l) {
    Tenyezo *iter;
    for (iter = l; iter != NULL; iter = iter->kov) {
        printf("%d^%d", iter->alap, iter->kitevo);
        if (iter->kov != NULL)
            printf(" * ");
    }
    printf("\n");
}

int min(int a, int b) {
    return a < b ? a : b;
}

Tenyezo *lnko(Tenyezo *egyik, Tenyezo *masik) {
    Tenyezo *lista = NULL;
    Tenyezo *vege = NULL;
    while (egyik != NULL && masik != NULL) {    /* amig mindket listabol van, potencialis kozos oszto */
        if (egyik->alap == masik->alap) { /* egyenlo alapok? kozos oszto resze! */
            Tenyezo *uj = (Tenyezo *) malloc(sizeof(Tenyezo));
            uj->alap = egyik->alap;
            uj->kitevo = min(egyik->kitevo, masik->kitevo);
            uj->kov = NULL;
            if (lista == NULL)
                lista = uj;
            else
                vege->kov = uj;
            vege = uj;
            egyik = egyik->kov;
            masik = masik->kov;
        }
        else
        if (egyik->alap < masik->alap) /* vagy kisebb az egyik? azzal lepunk, hatha elerunk egy kozoset */
            egyik = egyik->kov;
        else
            masik = masik->kov;        /* se nem kisebb, se nem egyenlo, akkor nagyobb - a masik ptr lep */

    }
    return lista;
}

void felszab(Tenyezo *l) {
    while (l != NULL) {
        Tenyezo *kov = l->kov;
        free(l);
        l = kov;
    }
}

int main(void) {
    Tenyezo *egyik = felbontas(360);
    Tenyezo *masik = felbontas(80);
    Tenyezo *kozososzto = lnko(egyik, masik);

    kiir(egyik);
    kiir(masik);
    kiir(kozososzto);

    felszab(egyik);
    felszab(masik);
    felszab(kozososzto);

    return 0;
}

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>
#include <stdbool.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;
}


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


int main(void) {
    Verem *v = NULL;

    printf("Irj egy tetszolegesen hosszu szoveget, fajl vegeig!\n");
    char c;
    while (scanf("%c", &c) == 1)
        verembe(&v, c);

    printf("A szoveged visszafele:\n");
    while (!verem_ures(&v))
        printf("%c", verembol(&v));

    return 0;
}