Naloge - 8. dan

Naloga  1

(5 točk)

Napišite program 1_seznam.c, ki prebere besedilno datoteko in vsebovane besede shrani v podatkovno strukturo povezan seznam. Seznamu v nadaljevanju dodajte možnost iskanja s preskakovanjem, ki pri sprehodu preko elementov seznama omogoča preskok vseh besed na isto črko. Natančneje so navodila zapisana spodaj.

1) Deklarirajte strukturo beseda:

typedef struct bes {   
    char beseda[MAX];  
    struct bes *nasl; // kazalec na naslednji element seznama
} beseda;     

Pri tem je MAX definirana "konstanta" (#define MAX _____) .

2) Napišite kodo, ki prebere besedilno datoteko (primeri: besede.txt, slovenija.txt) in ustvari seznam vseh različnih besed. Ne razlikujemo med malimi in velikimi črkami - vse besede pred vstavljanjem v seznam pretvorite v male črke. Seznam naj bo urejen po abecedi. Namig: za branje zgolj določenega nabora znakov (in ignoriranje ostalega) lahko uporabite (predpostavimo, da je MAX definiran kot 100):

fscanf(_____, "%99[a-zA-Z]%*[^a-zA-Z]", ______);

3) Napišite funkcijo za izpis celotnega seznama in jo uporabite v glavnem programu.

void izpisi(beseda* zac)

4) Napišite funkcijo

int poisci(beseda *zac, char *word)

ki v seznamu poišče dano besedo word in vrne število skokov, ki jih je potrebovala, da je v seznamu prišla do te besede oziroma vrne -1, če besede ni v seznamu.

5) Napišite funkcijo

int povprecnoIskanje(beseda *zac)

ki se sprehodi po celotnem seznamu, za vsako besedo kliče funkcijo poisci() in vrne povprečno število korakov za iskanje besed v seznamu.

6) Dopolnite strukturo beseda tako, da bo vsebovala še kazalec na besedo naslednje črke (prva beseda na “a” kaže na prvo besedo na “b”, ta kaže na prvo besedo na “c”, …). Napišite funkcijo

void dopolniSeznam(beseda *zac)

ki besedam v seznamu doda preskočne povezave.

7) Napiši funkcijo

int poisciHitreje(beseda *zac, char *word)

ki poišče besedo word v seznamu s preskakovanjem. Hitrost delovanja primerjaj s pomočjo spodnje kode:

while(1) {    
    char trb[MAX];
    scanf("%s", trb);
    printf("%d\n", poisci(zacetek, trb));
    printf("%d\n", poisciHitreje(zacetek, trb));
}

8) Deklariraj tip funkcije

typedef int fIsci(beseda *, char *);

in popravi funkcijo povprecnoIskanje() tako, da bo kot parameter prejela  tudi  funkcijo:

int povprecnoIskanje(fIsci *isci, beseda *zac)     

Nato novo funkcijo kliči na dva načina:

printf("PI1: %d\n", povprecnoIskanje(poisci, zacetek));
printf("PI1: %d\n", povprecnoIskanje(poisciHitreje, zacetek));

9) Napiši in uporabi funkcijo pocistiSeznam(), ki sprosti ves dinamično dodeljen pomnilnik (free).
 

Dodatna naloga za vajo

Razpršena matrika je matrika velikosti m x n, ki ima večino elementov ničelnih. Ker je hranjenje velikega števila ničelnih elementov v dvodimenzionalni tabeli potratno, je primerneje razpršeno matriko zapisati v obliki kazalčnega seznama neničelnih elementov. Pri tem vsak element seznama poleg vrednosti vsebuje še oba indeksa tega elementa v matriki in kazalec na naslednji element:

struct element {
    int mind, nind;
    int vrednost;
    struct element *nasl;
}

Napišite program 2_matrike.c za delo z razpršenimi matrikami v obliki kazalčnega seznama, ki bo omogočal branje matrike iz datoteke, seštevanje dveh matrik in izpis matrike v urejenem vrstnem redu (od prve proti zadnji vrstici ter od prvega proti zadnjemu stolpcu) na zaslon. Program naj prebere datoteki, ki sta podani v prvih dveh argumentih, ju sešteje in izpiše. Podatki v vhodni datoteki niso urejeni. Velikost matrike je zapisana v prvi vrstici vhodne datoteke (število vrstic in stolpcev).

Primer: matrika m1 vsebuje neničelne elemente na pozicijah (3,0), (1,1), (2,2) in (0,3), matrika m2 pa na pozicijah (2,0), (1,1), (2,2) in (0,3). Pravilen (urejen) izpis vsote teh dveh matrik je

2 0 2
3 0 8
2 2 10
0 3 4

Opomba: na poziciji (1,1) sta se vrednosti -5 in 5 sešteli v 0, zato te vrednosti v rezultatu ne izpišemo.