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

Doteraz sme mali len zoznam prvkov, kde každé slovo bolo zaradené toľkokrát, koľkokrát bolo v texte, a to vždy s frekvenciou 1.

Algoritmus na počítanie je nasledovný:

1. zober slovo
2. prejdi zoznam
3. ak sa slovo v zozname nenachádza, vytvor novú položku a zaraď ju [na koniec? na začiatok? uvažujme neskôr…] s frekvenciou 1
4. ak sa slovo v zozname nachádza, zvýš frekvenciu o jedna.

Vytvorenie položky

Na vytvorenie položky vytvorme separátnu funkciu:

struct polozka * new_polozka(char *slovo) {
        struct polozka * nova = NULL;

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

        strcpy(nova->slovo, slovo);

        return nova;
}

Filozofia je veľmi podobná konštruktoru z objektovo-orientovaného programovania: alokujeme pamäť, nastavíme jednotlivé podpoložky v structe a vrátime pointer na novovytvorenú položku.

Pridávanie na začiatok

Pridávanie na začiatok zoznamu má zložitosť O(1):

struct polozka * pridaj_alebo_zvys(struct polozka * zoznam, char * slovo) {
        struct polozka * kurzor = zoznam;
        while(kurzor != NULL) {
                if(strcmp(kurzor->slovo, slovo) == 0) {
                        (kurzor->pocet)++;
                        return list;
                }
                kurzor = kurzor->dalsi;
        }
        kurzor = new_polozka(slovo);
        kurzor->dalsi = zoznam;

        return kurzor;
}

Pridávanie na koniec

Pridávanie na koniec zoznamu vie využiť vyhľadávanie prvku: ak narazíme na koniec zoznamu, vieme rovno pridať prvok na koniec. S týmto prístupom je však viacero nepríjemností.

Ak máme cyklus

while(kurzor != NULL) {
    kurzor = kurzor->dalsi;
}

po prebehnutí celého zoznamu bude kurzor ukazovať na NULL, čiže “vypadne” mimo zoznamu.

Riešiť to môžeme dvoma smerníkmi: jeden bude ukazovať na aktuálne prechádzanú položku zoznamu (kurzor), druhý bude ukazovať na jej predchodcu. Vo chvíli, keď bude kurzor ukazovať na NULL, predchodca sa nasmeruje na posledný prvok v zozname.

Druhý problém spočíva v hraničnom prípade prázdneho zoznamu: to môžeme ošetriť separátnou podmienkou:

struct polozka * pridaj_alebo_zvys(struct polozka * zoznam, char * slovo) {
        struct polozka * nova = NULL;
        struct polozka * pomocny = zoznam;
        struct polozka * predosly = NULL;

        if(zoznam == NULL) {
                nova = new_polozka(slovo);
                /* nova polozka je jednoprvkovym zoznamom */
                return nova;
        }
        while( pomocny != NULL) {
                if(strcmp(pomocny->slovo, slovo) == 0) {
                        (pomocny->pocet)++;
                        return zoznam;
                }
                predosly = pomocny;
                pomocny = pomocny->dalsi;
        }

        nova = new_polozka(slovo);
        predosly->dalsi = nova;

        return zoznam;

}

Funkčné prototypy

Funkcie v C musia byť zoradená podľa poradia použitia. Ak funkcia pridaj_alebo_zvys() chce využiť funkciu new_polozka(), máme dve možnosti:

• deklarovať new_polozka() pred pridaj_alebo_zvys()
• alebo využiť funkčný prototyp, teda dodať hlavičku new_polozka() pred deklaráciou funkcie pridaj_alebo_zvys().

Funkčné prototypy sa obvykle uvádzajú na začiatku súboru:

/* ==== funkcne prototypy ========*/
struct polozka * new_polozka(char * slovo);

Možno to prirovnať k interfejsom z Javy: na začiatku uvedieme všetky (alebo vybrané funkcie) a nižšie v súbore ich implementácie.

Úprava načítavania v main()

Spracovanie riadka v main() sa tak zjednoduší:

int main() {
        struct polozka * zoznam = NULL;
        char riadok[MAX_DLZKA_SLOVA];

        while( fgets(riadok, MAX_DLZKA_SLOVA, stdin) != NULL ) {
                zoznam = pridaj_alebo_zvys(zoznam, riadok);
        }

        to_string(zoznam);
        free_zoznam(zoznam);
        return 0;
}

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

/* funkcne prototypy */
struct polozka * new_polozka(char * slovo);
/* /funkcne prototypy */

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


struct polozka * pridaj_alebo_zvys(struct polozka * zoznam, char * slovo) {
        struct polozka * kurzor = zoznam;
        while(kurzor != NULL) {
                if(strcmp(kurzor->slovo, slovo) == 0) {
                        (kurzor->pocet)++;
                        return list;
                }
                kurzor = kurzor->dalsi;
        }
        kurzor = new_polozka(slovo);
        kurzor->dalsi = zoznam;

        return kurzor;
}

struct polozka * new_polozka(char *slovo) {
        struct polozka * nova = NULL;

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

        strcpy(nova->slovo, slovo);

        return nova;
}

int main() {
        struct polozka * zoznam = NULL;
        char riadok[MAX_DLZKA_SLOVA];

        while( fgets(riadok, MAX_DLZKA_SLOVA, stdin) != NULL ) {
                zoznam = pridaj_alebo_zvys(zoznam, riadok);
        }

        to_string(zoznam);
        free_zoznam(zoznam);
        return 0;
}

Ako ladiť programy?

• použime gdb a core dumpy

• použime Valgrind

  valgrind ./freq < /tmp/babel.txt
  

• použime splint˛

  splint freq.c
  

Program splint analyzuje zdrojový kód v C a dáva mnohé rady (ale niekedy to preháňa) ku štruktúre zdrojáku. Dokáže však napríklad zdetekovať nekonečné cykly (zabudnuté kurzor = kurzor->next v cykle).

Debugger gdb vie zobrať výpis pamäte po SEGFAULTe programu a odhadnúť typický riadok pádu. Pomocou toho vieme odhaliť napríklad dereferencie NULL pointera.

Valgrind vie spustiť program v akomsi virtuálnom stroji a zistiť nelegálne prístupy k pamäti i odhaliť memory leaky (teda alokovanú a neuvoľnenú pamäť.). Vie tiež zistiť dereferencie NULL pointerov.