Strukture podataka

Autor zadatka: Relja Mihić <relja.mihic@uns.ac.rs>

Ime ulazne datoteke učitati argumentom komandne linije. Ulazna datoteka sadrži podatke strukturama podataka:

• naziv (jedna reč, do 40 karaktera)

• memorija_elementa (ceo broj, u bajtima)

• prosecno_trajanje_pretrage (jedna reč, do 3 karaktera)

Učitati podatke u jednostruko spregnutu listu dodavanjem novih elemenata na kraj liste. U izlaznu datoteku pod nazivom memorija.txt ispisati imena i ukupno memorije potrebno za čuvanje broja elemenata učitanog preko argumenta komandne linije. Memoriju izraziti u kilobajtima (kB), ako važi da je 1kB = 1024bajta. Za uneti broj elemenata, ispisati na standardnom izlazu za svaku strukturu vreme prosečne pretrage, ako:

• 1 - je potrebna jedna operacija, otpr. 5 nanosekundi

• log - je potrebno 5 * log(n) nanosekundi

• n - je potrebno 5 * n nanosekundi

U slučaju uspešnog izvršavanja programa, izaći sa status kodom 0 (EXIT_SUCCESS). Ukoliko program ne može da se izvrši do kraja usled sledećih nedostataka, izaći iz programa sa sledećim status kodovima:

• U slučaju nedovoljnog ili suvišnog broj argumenata komandne linije, izaći iz programa status kodom 1 (EXIT_FAILURE)

• Ako nije uspešno otvorena ulazna datoteka, izaći iz programa sa status kodom 2

• Ako nije uspešno otvorena izlazna datoteka, izaći iz programa sa status kodom 3

• Ako nije uspešno alocirana memorija za elemente, izaći iz programa sa status kodom 4

Primer poziva programa:

./a.out strukture.txt 1000

Primer ulazne datoteke strukture.txt:

Niz 52 n
Binarno_stablo_pretrage 72 log
Jednostruko_spregnuta_lista 64 n
Hes_tabela 64 1
Dvostruko_spregnuta_lista 72 n
AVL_stablo 80 log

Ispis programa na standardnom izlazu:

Prosecno vreme pretrage:
Niz - 5000 ns
Binarno_stablo_pretrage - 34.54 ns
Jednostruko_spregnuta_lista - 5000 ns
Hes_tabela - 5 ns
Dvostruko_spregnuta_lista - 5000 ns
AVL_stablo - 34.54 ns

Primer izlazne datoteke memorija.txt:

Niz 50.78kB
Binarno_stablo_pretrage 70.31kB
Jednostruko_spregnuta_lista 62.50kB
Hes_tabela 62.50kB
Dvostruko_spregnuta_lista 70.31kB
AVL_stablo 78.12kB

Primer rešenja

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

#define MAX_NAZIV 41
#define MAX_SEARCH 4

typedef struct cvor_st {
    char naziv[MAX_NAZIV];
    int mem;
    char search[MAX_SEARCH];
    struct cvor_st *sledeci;
} CVOR;

FILE *safe_fopen(char *ime, char *rezim, int kod_greske);
void inicijalizacija(CVOR **glava);
void ucitavanje(CVOR **glava, FILE *pf);
CVOR *napravi_cvor(char *ime, int m, char *alg);
void dodaj_na_kraj(CVOR **glava, CVOR *novi);
void ispis_memorija(FILE *pf, CVOR *glava, int uneta_vel);
void ispis_trajanja(CVOR *glava, int uneta_vel);
void obrisi_listu(CVOR **glava);

int main(int argc, char **argv) {

    if (argc != 3) {
        printf("Primer poziva programa: %s strukture.txt 1000\n", argv[0]);
        exit(1);
    }

    CVOR *glava;
    FILE *ulazna, *izlazna;

    inicijalizacija(&glava);
    ulazna = safe_fopen(argv[1], "r", 2);
    ucitavanje(&glava, ulazna);
    fclose(ulazna);

    izlazna = safe_fopen("memorija.txt", "w", 3);
    ispis_memorija(izlazna, glava, atoi(argv[2]));
    fclose(izlazna);

    ispis_trajanja(glava, atoi(argv[2]));
    obrisi_listu(&glava);

    return 0;
}

FILE *safe_fopen(char *ime, char *rezim, int kod_greske) {
    FILE *pf = fopen(ime, rezim);

    if (pf == NULL) {
        printf("Nije otvoren %s", ime);
        exit(kod_greske);
    }

    return pf;
}

void inicijalizacija(CVOR **glava) {
    *glava = NULL;
}

void ucitavanje(CVOR **glava, FILE *pf) {
    char ime[MAX_NAZIV], alg[MAX_SEARCH];
    int m;
    
    while(fscanf(pf, "%s %d %s", ime, &m, alg) != EOF) {
        CVOR *novi = napravi_cvor(ime, m, alg);
        dodaj_na_kraj(glava, novi);
    }
}

CVOR *napravi_cvor(char *ime, int m, char *alg) {
    CVOR *novi = (CVOR *)malloc(sizeof(CVOR));

    if (novi == NULL) {
        printf("Nema dovoljno memorije!\n");
        exit(4);
    }

    strcpy(novi->naziv, ime);
    strcpy(novi->search, alg);
    novi->mem = m;
    novi->sledeci = NULL;

    return novi;
}

void dodaj_na_kraj(CVOR **glava, CVOR *novi) {
    if (*glava == NULL) {
        *glava = novi;
    } else {
        CVOR *trenutni = *glava;
        while(trenutni->sledeci != NULL) {
            trenutni = trenutni->sledeci;
        }
        trenutni->sledeci = novi;
    }
}

void obrisi_listu(CVOR **glava) {
    while(*glava != NULL) {
        CVOR *trenutni = *glava;
        *glava = trenutni->sledeci;
        trenutni->sledeci = NULL;
        free(trenutni);
    }
}

void ispis_memorija(FILE *pf, CVOR *glava, int uneta_vel) {
    CVOR *tr = glava;
    while(tr != NULL) {
        fprintf(pf, "%s %.2lfkB\n", tr->naziv, tr->mem * uneta_vel / 1024.0);
        tr = tr->sledeci;
    }
}

void ispis_trajanja(CVOR *glava, int uneta_vel) {
    CVOR *trenutni = glava;
    printf("Prosecno vreme pretrage:\n");
    while(trenutni != NULL) {
        if(strcmp(trenutni->search, "1") == 0) {
            printf("%s - %d ns\n", trenutni->naziv, 5);
        } else if(strcmp(trenutni->search, "log") == 0) {
            printf("%s - %.2f ns\n", trenutni->naziv, 5.0 * log(uneta_vel));
        } else if(strcmp(trenutni->search, "n") == 0) {
            printf("%s - %d ns\n", trenutni->naziv, 5 * uneta_vel);
        }
        trenutni = trenutni->sledeci;
    }
}