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

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

  1#include <stdio.h>
  2#include <string.h>
  3#include <stdlib.h>
  4
  5#define MAX_ODREDISTE 21
  6#define MAX_PREVOZNIK 31
  7#define MAX_VREME_POLASKA 6
  8
  9typedef struct polazak_st {
 10    char odrediste[MAX_ODREDISTE];
 11    char vreme_polaska[MAX_VREME_POLASKA];
 12    char prevoznik[MAX_PREVOZNIK];
 13    double cena_karte;
 14    struct polazak_st *levi;
 15    struct polazak_st *desni;
 16} POLAZAK;
 17
 18void inicijalizacija(POLAZAK **);
 19POLAZAK *napravi_cvor(char *, char *, char *, double);
 20void dodaj_u_stablo(POLAZAK **, POLAZAK *);
 21POLAZAK *najjeftiniji_pre_vremena(POLAZAK *, char *, char *);
 22void obrisi_stablo(POLAZAK **);
 23
 24FILE *safe_fopen(char *, char *, int);
 25void ucitaj_polaske(FILE *, POLAZAK **);
 26void ispisi_polaske(FILE *, POLAZAK *);
 27
 28int validacija_vremena(char *);
 29
 30int main(int argc, char **argv) {
 31    POLAZAK *koren;
 32
 33    if(argc != 5) {
 34        printf("Primer poziva programa: %s polasci.txt red-voznje.txt Zrenjanin 13.00\n", argv[0]);
 35        exit(1);
 36    }
 37
 38    if(!validacija_vremena(argv[4])) {
 39        printf("Pogresan format vremena, primer dobrog formata: 13.00\n");
 40        exit(2);
 41    }
 42
 43    inicijalizacija(&koren);
 44
 45    FILE *ulazna = safe_fopen(argv[1], "r", 3);
 46    ucitaj_polaske(ulazna, &koren);
 47    fclose(ulazna);
 48
 49    FILE *izlazna = safe_fopen(argv[2], "w", 4);
 50    ispisi_polaske(izlazna, koren);
 51    fclose(izlazna);
 52
 53    POLAZAK *najjeftiniji = najjeftiniji_pre_vremena(koren, argv[3], argv[4]);
 54    if(najjeftiniji) {
 55        printf("Polazak pre %s casova za mesto %s sa najjeftinijom kartom je: %s %s %s %.2lf\n",
 56                argv[4], argv[3], najjeftiniji->odrediste, najjeftiniji->vreme_polaska, 
 57                najjeftiniji->prevoznik, najjeftiniji->cena_karte);
 58    } else {
 59        printf("Ne postoji polazak za mesto %s pre %s casova.\n", argv[3], argv[4]);
 60    }
 61
 62    return 0;
 63}
 64
 65void inicijalizacija(POLAZAK **pkoren) {
 66    *pkoren = NULL;
 67}
 68
 69POLAZAK *napravi_cvor(char *odrediste, char *vreme_polaska, char *prevoznik, double cena_karte) {
 70    POLAZAK *novi = (POLAZAK *)malloc(sizeof(POLAZAK));
 71
 72    if(novi == NULL) {
 73        printf("Greska prilikom zauzimanja memorije!\n");
 74        exit(5);
 75    }
 76
 77    strcpy(novi->odrediste, odrediste);
 78    strcpy(novi->vreme_polaska, vreme_polaska);
 79    strcpy(novi->prevoznik, prevoznik);
 80    novi->cena_karte = cena_karte;
 81    novi->levi = NULL;
 82    novi->desni = NULL;
 83
 84    return novi;
 85}
 86
 87void dodaj_u_stablo(POLAZAK **pkoren, POLAZAK *novi) {
 88    if(*pkoren == NULL) {
 89        *pkoren = novi;
 90    } else {
 91        if(strcmp(novi->vreme_polaska, (*pkoren)->vreme_polaska) < 0) {
 92            dodaj_u_stablo(&(*pkoren)->levi, novi);
 93        } else {
 94            dodaj_u_stablo(&(*pkoren)->desni, novi);
 95        }
 96    }
 97}
 98
 99POLAZAK *najjeftiniji_pre_vremena(POLAZAK *koren, char *odrediste, char *vreme) {
100    POLAZAK *najjeftiniji = NULL;
101
102    if(koren != NULL) {
103        if(strcmp(koren->odrediste, odrediste) == 0 &&
104           strcmp(koren->vreme_polaska, vreme) <= 0) {
105            najjeftiniji = koren; 
106        }
107
108        POLAZAK *najjeftiniji_levi = najjeftiniji_pre_vremena(koren->levi, odrediste, vreme);
109        if(najjeftiniji == NULL ||
110           (najjeftiniji_levi != NULL && najjeftiniji_levi->cena_karte < najjeftiniji->cena_karte)) {
111            najjeftiniji = najjeftiniji_levi;
112        }
113
114        POLAZAK *najjeftiniji_desni = najjeftiniji_pre_vremena(koren->desni, odrediste, vreme);
115        if(najjeftiniji == NULL ||
116           (najjeftiniji_desni != NULL && najjeftiniji_desni->cena_karte < najjeftiniji->cena_karte)) {
117            najjeftiniji = najjeftiniji_desni;
118        }
119    }
120
121    return najjeftiniji;
122}
123
124void obrisi_stablo(POLAZAK **pkoren) {
125    if(*pkoren != NULL) {
126        obrisi_stablo(&(*pkoren)->levi);
127        obrisi_stablo(&(*pkoren)->desni);
128        free(*pkoren);
129        *pkoren = NULL;
130    }
131}
132
133FILE *safe_fopen(char *ime, char *rezim, int kod_greske) {
134    FILE *fp = fopen(ime, rezim);
135
136    if(fp == NULL) {
137        printf("Greska prilikom otvaranja %s datoteke!\n", ime);
138        exit(kod_greske);
139    }
140
141    return fp;
142}
143
144void ucitaj_polaske(FILE *pulazna, POLAZAK **pkoren) {
145    char tmp_odrediste[MAX_ODREDISTE];
146    char tmp_vreme_polaska[MAX_VREME_POLASKA];
147    char tmp_prevoznik[MAX_PREVOZNIK];
148    double tmp_cena_karte;
149
150    while(fscanf(pulazna, "%s %s %s %lf",
151                 tmp_odrediste,
152                 tmp_vreme_polaska,
153                 tmp_prevoznik,
154                 &tmp_cena_karte) != EOF) {
155        POLAZAK *novi = napravi_cvor(
156            tmp_odrediste,
157            tmp_vreme_polaska,
158            tmp_prevoznik,
159            tmp_cena_karte);
160        dodaj_u_stablo(pkoren, novi);
161    }
162
163}
164
165void ispisi_polaske(FILE *izlazna, POLAZAK *koren) {
166    if(koren != NULL) {
167        ispisi_polaske(izlazna, koren->levi);
168        fprintf(izlazna, "%9s %5s %-15s %7.2lf\n",
169                koren->odrediste,
170                koren->vreme_polaska,
171                koren->prevoznik,
172                koren->cena_karte);
173        ispisi_polaske(izlazna, koren->desni);
174    }
175}
176
177int validacija_vremena(char *vreme) {
178    int sat, minut;
179
180    if(strlen(vreme) != 5 || vreme[2] != '.') return 0;
181
182    sat = (vreme[0] - '0') * 10;
183    sat += vreme[1] - '0';
184
185    if(sat >= 24) return 0;
186
187    minut = (vreme[3] - '0') * 10;
188    minut += vreme[4] - '0';
189
190    if(minut >= 60) return 0;
191
192    return 1;
193}