Zadatak „Namirnica sa najviše vitamina C”

Section author: Petar Marić <petarmaric@uns.ac.rs>

Iz zadate ulazne datoteke učitati podatke u binarno stablo, gde struktura namirnica_st sadrži sledeća polja:

  • naziv namirnice (jedna reč, do 13 karaktera)
  • količina vitamina C u namirnici (mg/100g)
  • vrsta namirnice (jedna reč, do 10 karaktera)

Naravno, struktura namirnica_st sadrži i polja potrebna za pravilno formiranje binarnog stabla.

Binarno stablo urediti po ključu „količina vitamina C”, u opadajućem redosledu. Potom iz formiranog binarnog stabla upisati podatke u zadatu izlaznu datoteku, u sledećem rasporedu polja strukture namirnica_st:

  • količina vitamina (koristiti "%3u" format specifikator)
  • naziv namirnice (koristiti "%-13s" format specifikator)
  • vrsta namirnice

i potom u istu izlaznu datoteku upisati informaciju o namirnici sa najviše vitamina C.

Primer poziva programa:

./analiza namirnice.txt izvestaj.txt

sa zadatim ulazom u datoteci namirnice.txt:

Ananas          9 voce
Bakalar        26 meso
BeliLuk        31 povrce
Brokoli        90 povrce
CrvenaPaprika 190 povrce
Grejpfrut      29 voce
Jagoda         60 voce
Kivi           89 voce
Krompir        20 povrce
Limun          40 voce
Paradajz       10 povrce
PilecaJetra    13 meso
Pomorandza     50 voce
Ribizla       200 voce
Sipurak       426 voce
Spanac         30 povrce
TelecaJetra    36 meso

i očekivanim izlazom u datoteci izvestaj.txt:

426 Sipurak       voce
200 Ribizla       voce
190 CrvenaPaprika povrce
 90 Brokoli       povrce
 89 Kivi          voce
 60 Jagoda        voce
 50 Pomorandza    voce
 40 Limun         voce
 36 TelecaJetra   meso
 31 BeliLuk       povrce
 30 Spanac        povrce
 29 Grejpfrut     voce
 26 Bakalar       meso
 20 Krompir       povrce
 13 PilecaJetra   meso
 10 Paradajz      povrce
  9 Ananas        voce

Namirnica sa najvise vitamina C je:
426 Sipurak       voce

Primer poziva programa kada su ulazni podaci već sortirani u rastućem redosledu:

./analiza sorted-asc.txt izvestaj-asc.txt

sa zadatim ulazom u datoteci sorted-asc.txt:

Limun          40 voce
Pomorandza     50 voce
Jagoda         60 voce
Kivi           89 voce
Brokoli        90 povrce

i očekivanim izlazom u datoteci izvestaj-asc.txt:

 90 Brokoli       povrce
 89 Kivi          voce
 60 Jagoda        voce
 50 Pomorandza    voce
 40 Limun         voce

Namirnica sa najvise vitamina C je:
 90 Brokoli       povrce

Primer poziva programa kada su ulazni podaci već sortirani u opadajućem redosledu:

./analiza sorted-desc.txt izvestaj-desc.txt

sa zadatim ulazom u datoteci sorted-desc.txt:

Bakalar        26 meso
Krompir        20 povrce
PilecaJetra    13 meso
Paradajz       10 povrce
Ananas          9 voce

i očekivanim izlazom u datoteci izvestaj-desc.txt:

 26 Bakalar       meso
 20 Krompir       povrce
 13 PilecaJetra   meso
 10 Paradajz      povrce
  9 Ananas        voce

Namirnica sa najvise vitamina C je:
 26 Bakalar       meso

Primer rešenja

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

#define MAX_NAZIV 13+1
#define MAX_VRSTA 10+1

typedef struct namirnica_st {
    char naziv[MAX_NAZIV];
    unsigned kolicina;
    char vrsta[MAX_VRSTA];

    struct namirnica_st *left;
    struct namirnica_st *right;
} NAMIRNICA;

void init_tree(NAMIRNICA **root) {
    *root = NULL;
}

void add_to_tree(NAMIRNICA *new, NAMIRNICA **root) {
    if(*root == NULL) { // tree is empty
        *root = new;
    } else if (new->kolicina >= (*root)->kolicina) {
        add_to_tree(new, &((*root)->left));
    } else {
        add_to_tree(new, &((*root)->right));
    }
}

NAMIRNICA *create_new_item(char naziv[], unsigned kolicina, char vrsta[]) {
    NAMIRNICA *new = (NAMIRNICA *)malloc(sizeof(NAMIRNICA));
    if (new == NULL) {
        printf("Not enough RAM!\n");
        exit(21);
    }

    strcpy(new->naziv, naziv);
    new->kolicina = kolicina;
    strcpy(new->vrsta, vrsta);

    new->left = NULL;
    new->right = NULL;

    return new;
}

void read_tree_from(FILE *in, NAMIRNICA **root) {
    char naziv[MAX_NAZIV];
    unsigned kolicina;
    char vrsta[MAX_VRSTA];

    while(fscanf(in, "%s %u %s", naziv, &kolicina, vrsta) != EOF) {
        NAMIRNICA *new = create_new_item(naziv, kolicina, vrsta);
        add_to_tree(new, root);
    }
}

void save_item_to(FILE *out, NAMIRNICA *x) {
    fprintf(
        out, "%3u %-13s %s\n",
        x->kolicina, x->naziv, x->vrsta
    );
}

void save_tree_to(FILE *out, NAMIRNICA *root) {
    if(root != NULL) {
        save_tree_to(out, root->left);
        save_item_to(out, root);
        save_tree_to(out, root->right);
    }
}

void destroy_tree(NAMIRNICA **root) {
    if(*root != NULL) {
        destroy_tree(&((*root)->left));
        destroy_tree(&((*root)->right));
        free(*root);
        *root = NULL;
    }
}

FILE *safe_fopen(char *filename, char *mode, int error_code) {
    FILE *fp = fopen(filename, mode);
    if (fp == NULL) {
        printf("Can't open '%s'!\n", filename);
        exit(error_code);
    }
    return fp;
}

NAMIRNICA *get_najbolja_namirnica(NAMIRNICA *root) {
    if (root == NULL) { // tree is empty
        return NULL;
    }

    // Stablo je uredjeno po kljucu "kolicina", u opadajucem redosledu.
    // Stoga se namirnica sa najvise vitamina C sigurno nalazi u krajnje levom
    // listu.

    if (root->left == NULL) {
        // ovaj "root" je krajnje levi list, posto nema levo dete
        return root;
    }

    // Trazi dalje, *sigurno* ima namirnica sa jos vise vitamina C
    return get_najbolja_namirnica(root->left);
}

int main(int arg_num, char *args[]) {
    if (arg_num != 3) {
        printf("USAGE: %s IN_FILENAME OUT_FILENAME\n", args[0]);
        exit(11);
    }

    char *in_filename = args[1];
    char *out_filename = args[2];

    FILE *in  = safe_fopen(in_filename,  "r", 1);
    FILE *out = safe_fopen(out_filename, "w", 2);

    NAMIRNICA *root;
    init_tree(&root);

    read_tree_from(in, &root);
    save_tree_to(out, root);

    NAMIRNICA *best = get_najbolja_namirnica(root);
    if (best != NULL) {
        fprintf(out, "\nNamirnica sa najvise vitamina C je:\n");
        save_item_to(out, best);
    }

    destroy_tree(&root);

    fclose(in);
    fclose(out);

    return 0;
}