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

Felkészülés a gyakorlatra:

• A listákról szóló előadás anyagának megértése.
• A listákról szóló első gyakorlat átismétlése.

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

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!

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.

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!

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!