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

Czirkos Zoltán · 2023.11.17.

Láncolt listák használata algoritmusokban.

Felkészülés a gyakorlatra:

1. Hatodik kis ZH

Ezen az órán van a hatodik kis ZH.

2. Hány különböző szó?

Adott az alábbi struktúrájú, szavakat tároló láncolt lista:

struct ListaElem {
    char szo[50 + 1];
    struct ListaElem *kov;
};

Készítsünk programot, amely megszámolja, hogy a listában hány különböző szó van! Az eredeti listát ne változtassuk meg!

Megoldás

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;
}

3. Milyen adatszerkezet?

Gondoljuk végig, az alábbi problémákhoz milyen adatszerkezetet érdemes használni.

  1. Átlagnál kisebbek. Egy program számokat olvas be, amelyek közül ki kell írni az átlagnál kisebbeket. Nem tudjuk, hány szám lesz.
  2. Prímszámok. Egy program számokat olvas be, és a beolvasottak közül csak a prímszámokat írja ki.
  3. Visszafelé. Számokat olvasunk be, és visszafelé sorrendben ki kell írni az átlagnál kisebbeket.
  4. Százezer. Számokat olvasunk be, maximum százezret. Ki kell írni az átlagnál kisebbeket.
  5. Szöveg. Be kell olvasnunk egy tetszőlegesen hosszú sort a bemenetről (karakterek enterig).
  6. Buszok. A programunk egy közlekedési társaság buszjáratait tárolja. Minden járatnak van egy száma, illetve van két végállomása, és közte tetszőlegesen sok megálló.
  7. Amőba. Amőba játékot írunk. A 13×13-as pályára a játékosok felváltva o és x jeleket tesznek, amelyek száma így változik. Nem tudjuk előre, mennyi lesz, hiszen lehet hogy hamar vége van a játéknak, lehet mindkét játékos ügyes, és szinte megtelik a pálya.
  8. Számok. Beolvasunk számokat a billentyűzetről, és meg kell mondanunk, hogy melyik szám hányszor szerepelt.
  9. Betűk. Beolvasunk karaktereket a billentyűzetről, és meg kell mondanunk, hogy melyik kisbetű (abc…z) hányszor szerepelt.
Megoldás
  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.

4. Prímtényezős felbontás

Régebbi
NZH feladat

Definiáljunk típust, mely alkalmas prímtényezők (alap, kitevő) láncolt listában való tárolására!

  • Írjunk függvényt, mely átvesz egy ilyen listát, és kiír egy prímtényezős felbontást a következő alakban: 2^2 * 3^1 * 5^1. (Ha gondolod, ezen a ponton írj egy rövid programrészt, amellyel teszt adatokat tudsz előállítani. Később ez a programrész eldobható.)
  • Írjunk függvényt, mely átvesz egy pozitív egészet, és visszaadja a prímtényezős felbontását tényezők szerint növekvő sorrendben egy listában!
  • Írjunk függvényt, mely paraméterként átvesz két prímtényezős felbontást, és a legnagyobb közös osztó prímtényezős felbontását adja vissza egy új listában! (Ehhez meg kell keresni azokat az alapokat, amelyek mindkét felbontásban szerepelnek, és mindig a kisebbik kitevőt választani.)

Egészítsük ki a fentieket teljes programmá, melyben két pozitív egész felbontásán és legnagyobb közös osztójának meghatározásán keresztül példát mutatunk az elkészült függvények alkalmazására!

Tipp

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!

Megoldás

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;
}

5. A teljes szöveg visszafelé

Az alábbi program beolvas egy szöveget fájl vége jelig, majd kiírja azt visszafelé. Elmélkedjünk rajta, miért!

#include <stdio.h>

void forditva_kiir(void) {
    char c;
    if (scanf("%c", &c) == 1) {
        forditva_kiir();
        printf("%c", c);
    }
}


int main(void) {
    forditva_kiir();
    return 0;
}

Írjunk meg ezt a programot úgy, hogy nem használunk rekurziót, hanem magunk építünk vermet!

Megoldás

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;
}