12. labor: Duplán láncolt listák

Akinek elmaradt az előző heti labor, először azzal a feladatsorral foglalkozzon!

A mai órán ismét listák kezelésével foglalkozunk, ezúttal két irányban láncolt, mindkét végén strázsával lezárt lista a feladat. A lista ezúttal szöveges adatokat (is) tartalmaz, tehát szövegfeldolgozás is része a feladatnak. Javasolt az összes függvény kidolgozása előtt rajzot készíteni: melyik pointer hova mutat a művelet előtt, és hogyan módosulnak azok a művelet hatására stb.

Adott a lenti programkód. Ez létrehoz egy dinamikusan foglalt, két irányban láncolt, mindkét végén strázsával lezárt listát. A lista könyvek szerzőit és címeit tárolja, valamint egy egész értéket darabszám tárolására.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
typedef struct ListaElem {
    char szerzo_kereszt[51];
    char szerzo_vezetek[51];
    char cim[101];
    int db;
    struct ListaElem *kovetkezo, *elozo;
} ListaElem;

typedef struct Lista {
    ListaElem *eleje, *vege;
} Lista;
 
void lista_letrehoz(Lista *lista) {
    char *konyvtomb[][3]={
        {"Rick", "Riordan", "The Son of Neptunen"},
        {"Jeff", "Kinney", "Cabin Fever"},
        {"Rick", "Riordan", "The Throne of Fire"},
        {"Rick", "Riordan", "The Lost Hero"},
        {"Shel", "Silverstein", "Every Thing On It"},
        {"J. K.", "Rowling", "Harry Potter Paperback Boxed Set"},
        {"John", "Flanagan", "The Outcasts"},
        {"Dorling", "Kindersley", "The LEGO Ideas Book"},
        {"J. K.", "Rowling", "Harry Potter Hardcover Boxed Set"},
        {"James", "Patterson", "Middle School, the Worst Years of My Life"},
        {"Rick", "Silverstein", "The Outcasts"},
        {"Brian", "Selznick", "Wonderstruck"},
        {"Jeff", "Kinney", "The Ugly Truth"},
        {NULL}
    };
    ListaElem *akt;
    int i;
 
    /* kezdő strázsa */
    lista->eleje = (ListaElem*) malloc(sizeof(ListaElem));
    lista->eleje->elozo = NULL;
    lista->vege = (ListaElem*) malloc(sizeof(ListaElem));
    lista->vege->kovetkezo = NULL;
 
    /* feltöltés */
    akt=lista->eleje;
    for (i=0; konyvtomb[i][0]!=NULL; i++) {
        ListaElem *uj = (ListaElem*)malloc(sizeof(ListaElem));
        strcpy(uj->szerzo_kereszt, konyvtomb[i][0]);
        strcpy(uj->szerzo_vezetek, konyvtomb[i][1]);
        strcpy(uj->cim, konyvtomb[i][2]);
        uj->db = 1;

        akt->kovetkezo=uj;
        uj->elozo = akt;
        akt=uj;
    }
 
    /* záró strázsához pointerek */
    akt->kovetkezo = lista->vege;
    lista->vege->elozo = akt;
}

int main() {
    Lista konyvek;
 
    lista_letrehoz(&konyvek);
 
    ...
    
    return 0;
}

Másold be egy új projektbe a kódot, és bontsd rögtön több forrásmodulra az előző labornál megadott módon!

Írj függvényt, amely kiírja a képernyőre a listában tárolt könyvek adatait! Ügyelj arra, hogy a strázsaelemek nem tartalmaznak adatot, ezért ezeket nem szabad kiírni!

Írj függvényt, amely paraméterként kapja a listát, és kiírja az abban tárolt adatokat visszafelé (a végétől az elejéig haladva)!

Írj egy függvényt, amely felszabadítja a listát! (Ne használj rekurziót!)

Írj függvényt, amely paraméterként kapja egy listát, valamint a szerző vezetéknevét, keresztnevét és a mű címét, és visszaadja annak a listaelemnek a címét, amelyben a szerző műve található! Ha a keresett elem nincs a listában, adjon vissza NULL pointert! (Mindhárom adat egyezését vizsgálni kell!)

Írj függvényt, amely egy paraméterként kapott lista végéhez láncol egy új elemet, amely az ugyancsak paraméterként kapott vezetéknevet, keresztnevet és címet tartalmazza! Ha az új elem már megtalálható a listában, akkor ne fűzze hozzá, hanem csak a darabszámot növelje eggyel!

Írj olyan függvényt is, amely egy nevével és címével megadott könyvet töröl a listából! Ha az adott elem db adattaagja 0-nál nagyobb, a törlés a számláló értékének csökkentését jelentse, ha 0, akkor az elem tényleges eltávolítását a listából!

Írj függvényt, amely egy paraméterként kapott listát rendez a mű címe szerinti ABC sorrendbe!

Lista rendezésére kétféle megoldás létezik: első, hogy a lista elemei megmaradnak, és a bennük lévő adatokat cseréljük ki (mint a tömböknél); a második, sokkal hatékonyabb megoldás pedig az, hogy az átláncolásukkal rendezzük a listát. Ilyenkor ugyanis nincsen szükség adatok cserélgetésére, hanem csak a pointerek módosulnak. A feladat ezért az utóbbi megvalósítása.

Tipp a megvalósításhoz:

• Segédfüggvény készítése, amely paraméterként kap egy rendezett, strázsákkal lezárt listát, valamint egy listaelem címét, és a listaelemet a megfelelő helyre befűzi a listába. (Memóriafoglalás tehát nem történik, csak a pointerek állítgatása.)
• A rendezőfüggvény emelje ki a rendezetlen listából a két strázsa közötti elemeket egy strázsa nélküli listába, a két strázsa pedig mutasson egymásra (azaz üres lista jön létre, ez lesz a rendezett lista).
• Egy ciklusban vegye le a rendezetlen lista első elemét, és hívja meg a segédfüggvényt, amely ezt az elemet beszúrja a rendezett listába! A ciklus addig menjen, amíg van elem a rendezetlen listában!

Írj függvényt, amely paraméterként kapja egy rendezett lista címét, valamint a szerző vezetéknevét, keresztnevét és a mű címét, es visszaadja annak a listaelemnek a címét, amelyben a szerző műve található! Ha a keresett elem nincs a listában, adjon vissza NULL pointert! (Mindhárom adat egyezését vizsgálni kell!)

Írj függvényt, amely egy paraméterként kapott nevű szöveges fájlba kiírja egy lista tartalmát; minden könyvet egy külön sorba, az egyes adatrészeket (vezetéknév, keresztnév, stb.) pontosvesszővel elválasztva! (Ha a fájl kiterjesztésének csv-t adsz meg, meg tudod nyitni a magyar nyelvű Excellel is.)

Írj egy másik függvényt, amely egy paraméterként kapott nevű fájlból új listát épít, és az elejére mutató pointert egy cím szerint átvett üres listába teszi. (Figyelj arra, hogy a lista a kiírás és beolvasás hatására ne forduljon meg!)

• A rendezés függvény az összes „The” kezdetű könyvcímet egy helyre gyűjti az ABC-ben. Könyvek, filmek címénél a kezdeti névelőket („The”, vagy magyarban „A”, „Az”) nem szokás figyelembe venni. Írd meg úgy a rendező függvényt, hogy így tegyen! (Tipp: ehhez egy segédfüggvényt érdemes írni, amely a sztringeket így hasonlítja össze.)
• Írj függvényt, amely lemásol egy duplán láncolt listát!
• Írj függvényt, amely megfordít egy duplán láncolt listát! Vajon elég ehhez csak megcserélni a kezdő- és a végstrázsát? Rajzold le!
• Írj függvényt, amely egy paraméterként kapott, duplán láncolt listához hozzáfűz egy másikat! (Az első lista ezáltal hosszabb lesz, a második pedig megszűnik létezni. Figyelj arra, hogy a második lista strázsáit ilyenkor fel kell szabadítani!)
• Nagyobb lélegzetű feladat: dolgozd át úgy az óra eleji „szerzők, könyvek” programot, hogy fésűs listát alkalmazzon! A fő listában a szerzők legyenek, amely szerzőkhöz további listákat, a könyvek listáit rendeljük hozzá.