Red vožnje

Autor zadatka: Rade Radišić <radisic.rade@uns.ac.rs>

Napisati program koji na osnovu spiska polazaka sa autobuske stanice formira red vožnje. Iz ulazne datoteke učitati u binarno stablo pretrage sledeće podatke:

• odredište (jedna reč, do 20 karaktera)

• vreme_polaska (jedna reč, u formatu sat, dva karaktera, tačka, minut, dva karaktera)

• prevoznik (jedna reč, do 30 karaktera)

• cena_karte (realan broj)

Stablo se formira na osnovu vrednosti polja vreme_polaska.

Program prima ime ulazne, izlazne datoteke, odredište i vreme kao argumente komandne linije. U izlaznu datoteku potrebno je ispisati podatke iz ulazne datoteke, sortirane po vremenima polaska u rastućem redosledu. Prilikom ispisa u izlaznu datoteku, koristiti format "%9s %5s %-15s %7.2lf\n".

Na standardni izlaz ispisati najjeftiniji polazak za zadato mesto do naznačenog vremena polaska (uključujući i vreme polaska). Ukoliko postoji, ispisati:

Polazak pre <zadato-vreme> casova za mesto <zadato-mesto> sa najjeftinijom kartom je:

zajedno sa informacijama o polasku. Prilikom formatiranja jedino zaokružiti cenu karte na dve decimale. Ukoliko ne postoji, ispisati poruku sledeće sadržine:

Ne postoji polazak za mesto <zadato-mesto> pre <zadato-vreme> casova.

zadato-mesto i zadato-vreme predstavljaju vrednosti argumenata komandne linije.

Uraditi validaciju argumenta komandne linije koji predstavlja zadato vreme na sledeći način:

• Iskontrolisati dužinu stringa tako da u njega stane format, po dve cifre za čas i za minut, sa tačkom između (proveriti i njeno postojanje)

• Izdvojiti iz stringa čas i minut, pretvoriti u celobrojne vrednosti i iskontrolisati da li se nalaze u validnom opsegu

  • Čas je vrednost između 0 i 23

  • Minut je vrednost između 0 i 59

Radi jednostavnosti, pretpostaviti da se na mestima rezervisanim za časove i minute mogu naći samo cifre.

U slučaju sledećih grešaka prilikom rada programa, izaći sa odgovarajućim kodom greške:

• Nedovoljan ili suvišan broj argumenata, kod greške 1 (EXIT_FAILURE)

• Neuspešna validacija zadatog vremena, kod greške 2

• Neuspešno otvaranje ulazne datoteke, kod greške 3

• Neuspešno otvaranje izlazne datoteke, kod greške 4

• Nije moguće dinamički zauzeti memoriju, kod greške 5

Program realizovati tako da sve funkcije koje imaju veze isključivo sa stablom (inicijalizacija, dodavanje, brisanje...) budu odvojene u jedan par datoteka koje predstavljaju zaglavlje i implementaciju.

Primer ulazne datoteke polasci.txt:

Beograd   08.55 Lasta            801.50
Beograd   10.00 Jugoprevoz       821.50
Beograd   11.35 Severtrans       821.50
Beograd   12.20 SaobracajZabalj  671.50
Becej     09.50 BecejPrevoz      632.50
Becej     12.10 BecejPrevoz      632.50
Becej     13.15 BecejPrevoz      632.50
Becej     13.45 Lasta            572.50
Subotica  08.25 Lasta            971.50
Subotica  10.35 NisEkspres      1211.50
Subotica  12.25 SaobracajZabalj  971.50
Subotica  13.50 NisEkspres      1381.50
Zrenjanin 08.58 BanatTrans       471.50
Zrenjanin 09.30 AsTours          461.50
Zrenjanin 10.30 StupVrsac        521.50
Zrenjanin 11.50 BanatTrans       471.50

Za primer poziva programa:

./a.out polasci.txt red-voznje.txt Zrenjanin 13.00

Očekivani ispis na standardnom izlazu je:

Polazak pre 13.00 casova za mesto Zrenjanin sa najjeftinijom kartom je: Zrenjanin 09.30 AsTours 461.50

Dok je za poziv sledeći poziv programa:

./a.out polasci.txt red-voznje.txt Zrenjanin 08.00

Očekivani ispis na standardnom izlazu:

Ne postoji polazak za mesto Zrenjanin pre 08.00 casova.

U oba slučaja, sadržaj izlazne datoteke red-voznje.txt je sledeći:

 Subotica 08.25 Lasta            971.50
  Beograd 08.55 Lasta            801.50
Zrenjanin 08.58 BanatTrans       471.50
Zrenjanin 09.30 AsTours          461.50
    Becej 09.50 BecejPrevoz      632.50
  Beograd 10.00 Jugoprevoz       821.50
Zrenjanin 10.30 StupVrsac        521.50
 Subotica 10.35 NisEkspres      1211.50
  Beograd 11.35 Severtrans       821.50
Zrenjanin 11.50 BanatTrans       471.50
    Becej 12.10 BecejPrevoz      632.50
  Beograd 12.20 SaobracajZabalj  671.50
 Subotica 12.25 SaobracajZabalj  971.50
    Becej 13.15 BecejPrevoz      632.50
    Becej 13.45 Lasta            572.50
 Subotica 13.50 NisEkspres      1381.50

Primer rešenja

resenje.cstablo.hstablo.cMakefile

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

POLAZAK *najjeftiniji_pre_vremena(POLAZAK *, char *, char *);
FILE *safe_fopen(char *, char *, int);
void ucitaj_polaske(FILE *, POLAZAK **);
void ispisi_polaske(FILE *, POLAZAK *);

int validacija_vremena(char *);

int main(int argc, char **argv) {
    POLAZAK *koren;

    if(argc != 5) {
        printf("Primer poziva programa: %s polasci.txt red-voznje.txt Zrenjanin 13.00\n", argv[0]);
        exit(1);
    }

    if(!validacija_vremena(argv[4])) {
        printf("Pogresan format vremena, primer dobrog formata: 13.00\n");
        exit(2);
    }

    inicijalizacija(&koren);

    FILE *ulazna = safe_fopen(argv[1], "r", 3);
    ucitaj_polaske(ulazna, &koren);
    fclose(ulazna);

    FILE *izlazna = safe_fopen(argv[2], "w", 4);
    ispisi_polaske(izlazna, koren);
    fclose(izlazna);

    POLAZAK *najjeftiniji = najjeftiniji_pre_vremena(koren, argv[3], argv[4]);
    if(najjeftiniji) {
        printf("Polazak pre %s casova za mesto %s sa najjeftinijom kartom je: %s %s %s %.2lf\n",
                argv[4], argv[3], najjeftiniji->odrediste, najjeftiniji->vreme_polaska, 
                najjeftiniji->prevoznik, najjeftiniji->cena_karte);
    } else {
        printf("Ne postoji polazak za mesto %s pre %s casova.\n", argv[3], argv[4]);
    }

    return 0;
}

POLAZAK *najjeftiniji_pre_vremena(POLAZAK *koren, char *odrediste, char *vreme) {
    POLAZAK *najjeftiniji = NULL;

    if(koren != NULL) {
        if(strcmp(koren->odrediste, odrediste) == 0 &&
           strcmp(koren->vreme_polaska, vreme) <= 0) {
            najjeftiniji = koren; 
        }

        POLAZAK *najjeftiniji_levi = najjeftiniji_pre_vremena(koren->levi, odrediste, vreme);
        if(najjeftiniji == NULL ||
           (najjeftiniji_levi != NULL && najjeftiniji_levi->cena_karte < najjeftiniji->cena_karte)) {
            najjeftiniji = najjeftiniji_levi;
        }

        POLAZAK *najjeftiniji_desni = najjeftiniji_pre_vremena(koren->desni, odrediste, vreme);
        if(najjeftiniji == NULL ||
           (najjeftiniji_desni != NULL && najjeftiniji_desni->cena_karte < najjeftiniji->cena_karte)) {
            najjeftiniji = najjeftiniji_desni;
        }
    }

    return najjeftiniji;
}

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

    if(fp == NULL) {
        printf("Greska prilikom otvaranja %s datoteke!\n", ime);
        exit(kod_greske);
    }

    return fp;
}

void ucitaj_polaske(FILE *pulazna, POLAZAK **pkoren) {
    char tmp_odrediste[MAX_ODREDISTE];
    char tmp_vreme_polaska[MAX_VREME_POLASKA];
    char tmp_prevoznik[MAX_PREVOZNIK];
    double tmp_cena_karte;

    while(fscanf(pulazna, "%s %s %s %lf",
                 tmp_odrediste,
                 tmp_vreme_polaska,
                 tmp_prevoznik,
                 &tmp_cena_karte) != EOF) {
        POLAZAK *novi = napravi_cvor(
            tmp_odrediste,
            tmp_vreme_polaska,
            tmp_prevoznik,
            tmp_cena_karte);
        dodaj_u_stablo(pkoren, novi);
    }

}

void ispisi_polaske(FILE *izlazna, POLAZAK *koren) {
    if(koren != NULL) {
        ispisi_polaske(izlazna, koren->levi);
        fprintf(izlazna, "%9s %5s %-15s %7.2lf\n",
                koren->odrediste,
                koren->vreme_polaska,
                koren->prevoznik,
                koren->cena_karte);
        ispisi_polaske(izlazna, koren->desni);
    }
}

int validacija_vremena(char *vreme) {
    int sat, minut;

    if(strlen(vreme) != 5 || vreme[2] != '.') return 0;

    sat = (vreme[0] - '0') * 10;
    sat += vreme[1] - '0';

    if(sat >= 24) return 0;

    minut = (vreme[3] - '0') * 10;
    minut += vreme[4] - '0';

    if(minut >= 60) return 0;

    return 1;
}