Stanica Peklo

Ďalšou pracovnou úlohou na pozícii riaditeľa vlakovej stanice bude spočítať koľko cestujúcich cestuje do každej stanice. Úloha to nie je jednoduchá, lebo databáza musí byť pekelne rýchla. Lineárne vyhľadávanie musíme obmedziť na minimum. V oddelení vývoja vymysleli geniálny zlepšovák - vyhľadávanie pri ktorom je jedno v akej veľkej stanici vyhľadávane, vždy bude trvať rovnaký čas. Vzniklo nové perpettum mobile?

Na účel vyhľadávania si vytvoríme asociatívne pole, ktoré stanici priradí počet cestujúcich ktorí do nej cestujú.

Ak ste to ešte neurobili, podrobne si zopakujte spojkové zoznamy a dynamické polia, budete ich potrebovať.

Úloha

Vytvorte databázu na uloženie informácií o počte cestujúcich do rôznych staníc. Databázu vytvorte pomocou hešovacej tabuľky so zreťazením. V databáze môže byť o každej stanici maximálne jeden záznam o počte cestujúcich ktorí do nej cestujú.

Podľa dokumentácie v hlavičkovom súbore implementujte všetky funkcie.

Po tom ako splníte automatické testy, pridajte tieto vlastnosti:

• Načítanie existujúcej databázy z textového súboru.
• Pridanie nového záznamu a zvýšenie kapacity do danej destinácie
• Vyhľadávanie informácií podľa zadanej destinácie

V úlohe budete implementovať sadu funkcií z hlavičkového súboru. Ak to urobíte správne, vznikne Vám asociatívne pole, do ktoré si ku ľubovoľnému kľúču budete vedieť priradiť nejakú hodnotu.

Bohato využijeme znalosti z predošlého cvičenia, prednášky aj minulého ročníka. Namiesto jedného spojkového zoznamu ich ale budeme mať viac. Odkaz na každý spojkový zoznam si uložíme do dynamicky alokovaného poľa smerníkov.

Najprv získajte šablónu zadania a oboznámte sa s funkciami ktoré máte vytvoriť. Dokumentáciu nájdete v súbore a_station.h. Odovzdávať na GIT budete súbor a_station.c. V súbore main.c nájdete nejaké pomocné funkcie.

1. Dynamické pole smerníkov

V tejto úlohe si implementujeme hešovaciu tabuľku so zreťazením. Aby bolo zreťazenie možné, jedna pozícia v tabuľke bude mať smerníkový typ. Viacero smerníkov nám tvorí pole smerníkov.

Na dynamické pole smerníkov si vytvoríme ďalší typ. Adresy spojkových zoznamov si poznačíme do poľa smerníkov tracks. Počet prvkov v poli smerníkov si uložíme do premennej track_count.

struct station {
    // Dynamicke pole smernikov na zaznamy
    struct car** tracks;
    // Velkost pola tracks
    int track_count;
};

V šablóne nájdete funkciu na dynamické vytvorenie poľa smerníkov:

struct station* create_station(){
   struct station* station = calloc(1,sizeof(struct station));
   station->tracks = calloc(STATION_SIZE, sizeof(struct car*));
   station->track_count = STATION_SIZE;
   return station;
}

Funkcia dynamicky alokuje celú štruktúru, do nej alokuje pole smerníkov a poznačí jeho veľkosť. Na koniec vráti adresu na štruktúru struct station. Pole smerníkov je na začiatku nulové.

Porozmýšľajte, ako uvoľniť takto alokovanú pamäť vo funkcii destroy_station. Každé volanie calloc alebo malloc musí mať svojho kamaráta free (inak sa program bude správať nepredvídateľne).

V práci Vám pomôže aj funkcia na výpis aktuálneho stavu vlakovej stanice, aby ste videli na ktorej trati je koľko vlakov. Pozrite si ju a zistite, ako prechádzať všetky prvky v hešovacej tabuľke. V jednom cykle prejdite všetky spojkové zoznamy a v druhom prejdite všetky prvky spojkového zoznamu. Pomôže Vám pri ladení programu ak budete vedieť kam sa Vaše dáta ukladajú.

void print_station(struct station* station){
        printf("station>>>\n");
        // Prejde vsetky trate
        for (int i = 0 ; i< station->track_count; i++){
                struct car* start = station->tracks[i];
                struct car* this = start;
                // Prejde vsetky vozne vo vlaku
                while(this != NULL){
                        printf("%s %d -> ",this->value,this->capacity);
                        this=this->next;
                }
                printf("NULL\n");
        }
        printf("<<<station\n");
}

2. Vytvorte si hešovaciu funkciu

Na výpočet indexu kde do poľa uložíme spojkového zoznamu použijeme hešovaciu funkciu.

Databáza bude tvorená viacerými záznamami, ktoré vyzerajú podobne ako spojkový zoznam:

struct car {
   int capacity;
   char value[SIZE];
   struct car* next;
};

Hešovacia funkcia nám hovorí na ktorej koľaji nájdeme vozeň do niektorej cieľovej stanice. V hešovacej tabuľke je najdôležitejšia hešovacia funkcia - pomôže nám určiť, s ktorou časťou poľa práve pracujeme. Možným riešením je použiť hešovaciu tabuľku so zreťazením. Namiesto jedného spojkového zoznamu použijeme viacero spojkových zoznamov, ktoré uložíme do poľa.

Jeden spojkový zoznam si môžeme predstaviť ako vlak, hešovaciu tabuľku si vieme predstaviť ako celú stanicu, kde sa naraz nachádza viac vlakov, každý na svojej koľaji. Do jednej stanice je smerovaný práve jeden vozeň (cieľové stanice sa nemôžu opakovať). Podobne ako na stanici, musíme povedať, na ktorej trati sa vlak bude nachádzať. To nám povie hešovacia funkcia, ktorá názvu cieľovej stanice priradí nejaké celé číslo. Dôležíté je, aby výsledné číslo bolo čo najviac "nepredvídateľné", ale stále rovnaké pre rovnaký reťazec.

3. Vytvorte funkciu na pridanie záznamu

Algoritmus na pridanie nového záznamu do databázy bude vyzerať takto:

1. Pomocou funkcie select_track vyberte s ktorým spojkovým zoznamom budeme pracovať.
2. Ak je spojkový zoznam prázdny, vytvoríme nový prvok a zapíšeme ho na vybrané miesto.
3. Ak spojkový zoznam nie je prázdny, prechádzame všetky jeho prvky. Ak nájdeme "vozeň" s rovnakou cieľovou stanicou, pripočítame jeho kapacitu a skončíme.

Miesto v poli smerníkov vyberieme pomocou hešovacej funkcie:

int track = select_track(station,target);
struct car* start = station->tracks[track];

Pri pridávaní musíte zabezpečiť, aby v databáze bol maximálne jeden záznam o danej cieľovej stanici. Keď vieme v na ktorom mieste sa záznam nachádza, so záznamom robíme rovnako ako so spojkovým zoznamom.

4. Správne uvoľnite pamäť

Ubezpečte sa, že funkcia destroy_station uvoľní aj pamäť všetkých záznamov, ktoré ste vytvorili vo funkcii add_target_capacity

5. Vytvorte funkciu na vyhľadanie

Ak na základe hash funkcie vieme do ktorého vlaku vlaku vozeň patrí, je jednoduché ho vyhľadať.

1. Vypočítajte heš z reťazca názvu stanice pomocou funkcie select_track.
2. Určite číslo "koľaje", do ktorého ide záznam. Funkcia select_track vráti ľubovoľne veľké celé číslo. Toto číslo konvertujeme do intervalu 0 až station->size -1 pomocou operátora %.
3. Vyhľadajte "vozeň" s daným názvom v určenom vlaku. Prejdite všetky prvky spojkového zoznamu.

6. Vytvorte funkcie na spočítanie

všetkých záznamov a dostupnej kapacity.

Ako príklad môžte použiť funkciu print_station.

7. Dokončite program do používateľsky príjemnej podoby

Do aplikácie doplňte tieto vlastnosti:

• Načítanie existujúcej databázy z textového súboru.
• Pridanie nového záznamu a zvýšenie kapacity do danej destinácie
• Vyhľadávanie informácií podľa zadanej destinácie

Odovzdanie a hodnotenie

• odovzdanie cez GIT
• hodnotenie systémom Traktor. V tomto zadaní budete hodnotení pomocou jednotkových testov funkcií ktoré máte vytvoriť. Budete odovzdávať obsah súboru a_station.c podľa predpisov a dokumentácie v súbore a_station.h.
• Používateľskú funkčnosť Vášho programu a znalosť zdrojových kódov predstavíte v rámci osobnej obhajoby.

Previous Post Next Post