Pokračujme v tvorbe programu na počítanie frekvencií slov v súbore!

Na rozdiel od staticky alokovaného poľa 3000 prvkov vytvoríme dynamický — nafukovací — zoznam, ktorý bude využívať len toľko pamäte, koľko treba.

Využijeme dátovú štruktúru spojový zoznam, v ktorom sa budú nachádzať jednotlivé položky, pričom každá z nich bude obsahovať:

• slovo: reťazec (pole charov)
• frekvenciu: číslo (int)
• odkaz na ďalší prvok

Odkaz na ďalší prvok vyriešime elegantne pomocou pointerov. Ak vieme pre každú položku jej adresu v pamäti, môžeme ju využiť v odkaze.

struct polozka {
        char slovo[MAX_DLZKA_SLOVA];
        int pocet;
        struct polozka * dalsi;
};

Prvotná verzia zdrojáku, ešte bez tvorby zoznamu nech vyzerá:

int main() {
        char riadok[MAX_DLZKA_SLOVA];

        while( fgets(riadok, MAX_DLZKA_SLOVA, stdin) != NULL ) {
                printf("%s", riadok);
        }
        return 0;
}

Ako budeme generovať zoznam? V Jave by to bolo:

List<Polozka> zoznam = new LinkedList<Polozka>();
while(scanner.hasNextLine()) {
    String riadok = scanner.nextLine();

    Polozka p = new Polozka();
    p.setSlovo(riadok);
    p.setPocet(1)

    zoznam.add(p);
}

V C bude pre zoznam platiť viacero špecifík:

• zoznam je stotožnený s pointerom na jeho prvý prvok
• prázdny zoznam predstavuje NULLový pointer

A veselý dôsledok: * pointer na prvok, ktorý nie je NULL, možno považovať za jednoprvkový zoznam.

Prázdny zoznam vytvoríme jednoducho:

struct polozka * zoznam = NULL;

Novú položku vytvoríme dynamicky pomocou malloc(). Vyžiadame si toľko bajtov, koľko je veľkosť structu, na čo využijeme sizeof():

p = malloc(sizeof(struct polozka));

Operátor sizeof() portabilne vracia veľkosť dátového typu, teda počet bajtov, ktoré zaberie premenná toho typu. Typicky (ale nie garantovane!) platí, že sizeof(char) je 1, sizeof(int) je 4; aj keď na iných platformách a v budúcnosti sa to môže zmeniť.

V tomto prípade sizeof() vráti zhruba 50 (dĺžka reťazca) + 4 (dĺžka intu) + pamäť, ktorú zaberie premenná typu pointer na struct polozka.

Nezabudneme overiť, že malloc() uspel!

if(p == NULL) {
    perror("Malloc() polozky zlyhal");
    return -1;
}

Ak máme novú položku, nastavíme jej vlastnosti: slovo a dĺžku na 1.

Pozor ale! Toto nefunguje:

p.pocet = 1; /* NEFUNGUJE! */

rovnako ako nefunguje

strcpy(p.slovo, riadok); /* NEFUNGUJE! */

Premenná p je totiž typu pointer na struct polozka, teda adresa (teda akési číslo v pamäti) a to samozrejme nemá vlastnosti slovo, ani pocet. Ak sa chceme dopracovať k samotnej hodnote, teda štruktúre, na ktorú premenná odkazuje, použime operátor dereferencie.

Ak p je premenná typu struct polozka * (teda pointer na štruktúru položky), po dereferencovaní cez *p získame hodnotu typu struct polozka, teda samotnú štruktúru položky.

Použitie v kóde:

(*p).pocet = 1;
strcpy( (*p).slovo, riadok); /* NEFUNGUJE! */

Operátor dereferencie v prípade pointerov na štruktúry je tak často používaný, že si vyslúžil vlastný syntaktický cukor:

(*p).pocet = 1;

/* je to isté ako */

p->pocet = 1

Teraz môžeme uvažovať, či položku pridať na koniec, alebo na začiatok: a najjednoduchšie je pridávať na začiatok zoznamu, lebo táto operácia vyžaduje len dve výmeny pointerov a konštantný čas.

• Novej položke stačí nastaviť za nasledovníka prvý prvok existujúceho zoznamu.
• Premennú ukazujúcu na prvý prvok existujúceho zoznamu presmerujeme na novú položku.

Celý zdroják pre budovanie zoznamu je:

int main() {
        struct polozka * zoznam = NULL;

        struct polozka * docasna = NULL;

        char riadok[MAX_DLZKA_SLOVA];

        while( fgets(riadok, MAX_DLZKA_SLOVA, stdin) != NULL ) {
                docasna = malloc(sizeof(struct polozka));
                if(docasna == NULL) {
                        perror("Malloc() polozky zlyhal");
                        return -1;
                }
                docasna->pocet = 1;

                strcpy( docasna->slovo , riadok);
                docasna->dalsi = zoznam;
                zoznam = docasna;
        }
        return 0;
}

Vybudovali sme teda dátovú štruktúru, ale nevieme ju vypísať. Dodajme teda metódu na výpis.

Využime filozofiu kurzora: budeme mať premennú kurzor, ktorou budeme pobehovať po zozname od začiatku až kým nenarazíme na NULL.

void to_string( struct polozka * zoznam  ) {
    struct polozka * kurzor = zoznam;

    while( kurzor != NULL ) {
        printf("%d %s", kurzor->pocet, kurzor->slovo );
        kurzor = kurzor->dalsi;
    }
}

Posledná vec súvisí s uvoľnovaním pamäte: vždy, keď alokujeme pamäť cez malloc(), mali by sme sa postarať o dealokáciu. V opačnom prípade si koledujeme o memory leak, teda uniknutú pamäť.

Otestovať si to môžeme nástrojom Valgrind:

valgrind ./ptrfreq < ~/babel.txt

Uvidíme výpis behu programu a sumár uniknutej pamäte: 64 stratených bajtov a dodatočných nepriamo stratených 188544 bajtov.

==20153==
==20153== HEAP SUMMARY:
==20153==     in use at exit: 188,608 bytes in 2,947 blocks
==20153==   total heap usage: 2,947 allocs, 0 frees, 188,608 bytes allocated
==20153==
==20153== LEAK SUMMARY:
==20153==    definitely lost: 64 bytes in 1 blocks
==20153==    indirectly lost: 188,544 bytes in 2,946 blocks
==20153==      possibly lost: 0 bytes in 0 blocks
==20153==    still reachable: 0 bytes in 0 blocks
==20153==         suppressed: 0 bytes in 0 blocks
==20153== Rerun with --leak-check=full to see details of leaked memory
==20153==
==20153== For counts of detected and suppressed errors, rerun with: -v
==20153== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 4 from 4)

Dopracujme uvoľnovanie zoznamu:

• iterujeme cez zoznam,
• vždy si zapamätáme pointer na začiatok zoznamu do separátnej pomocnej premennej,
• premennú s pointerom na začiatok zoznamu zmeníme na pointer na druhý prvok,
• a zapamätaný niekdajší začiatok zoznamu uvoľníme cez zabudovanú funkciu free().

Funkcia bude vyzerať takto:

void free_zoznam(struct polozka * zoznam) {
        struct polozka * pomocny = zoznam;

        while( zoznam != NULL ) {
                pomocny = zoznam;
                zoznam = zoznam->dalsi;
                free(pomocny);
        }
}

Celý zdroják:

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

#define MAX_DLZKA_SLOVA 50

struct polozka {
        char slovo[MAX_DLZKA_SLOVA];
        int pocet;
        struct polozka * dalsi;
};

void to_string( struct polozka * zoznam  ) {
        struct polozka * kurzor = zoznam;

        while( kurzor != NULL ) {
                printf("%d %s", kurzor->pocet, kurzor->slovo );

                kurzor = kurzor->dalsi;
        }
}

void free_zoznam(struct polozka * zoznam) {
        struct polozka * pomocny = zoznam;

        while( zoznam != NULL ) {
                pomocny = zoznam;
                zoznam = zoznam->dalsi;
                free(pomocny);
        }
}

int main() {
        struct polozka * zoznam = NULL;

        struct polozka * p = NULL;

        char riadok[MAX_DLZKA_SLOVA];

        while( fgets(riadok, MAX_DLZKA_SLOVA, stdin) != NULL ) {
                printf("%s", riadok);

                p = malloc(sizeof(struct polozka));
                if(p == NULL) {
                        perror("Malloc() polozky zlyhal");
                        return -1;
                }
                p->pocet = 1;

                strcpy(p->slovo, riadok);
                p->dalsi = zoznam;
                zoznam = p;
        }

        to_string(zoznam);

        free_zoznam(zoznam);

        return 0;
}