Nepokoje v nasich vazniciach narastaju do neusosnych medzi. A to nielen preto, ze su preplnene, ale aj preto, ze recidivistom su vzdy pridelene nove cisla a nie tie ich, na kt. si uz zvykli. Vo vazniciach, kde sa vsetci oslovuju cislami, je tento fakt velmi nevytany. Vsetko vyriesil novy projekt Alcatraz II. Ak pride do tejto vaznice dalsi vazen, dozorcovia zadaju do pocitaca jeho meno a priezvisko a program vypise NOVY, ak tu este predtym vazneny nebol, alebo RECIDIVISTA, ak neprisiel po prvy raz. Program tiez vypise cislo vazna. Novemu vaznovi moze program priradit lubovolne cislo, ktore avsak nema iny vazen, no recidivistovi musi priradit cislo z jeho predchadzajuceho pobytu. Mozno predpokladat ze cisla su priradovane iba uvedenym programom. ULOHA: Vytvorte horeuvedeny program tak, aby fungoval co najrychlejsie a pre co najvacsie mnozstva vaznov. Program bude uvedeny do prevadzky zaroven s otvorenim vaznice, takze vaznica je na zaciatku prazdna. Kedze Alcatraz II nikdy neprestane fungovat, mal by aj vas program fungovat v nekonecnej slucke. Mena vaznov su zlozene z velkych pismen abecedy a z medzier. Priklad vstupu a vystupu: ? LEX LUTHOR NOVY 3560 ? JAMES BOND NOVY 007 ? LEX LUTHOR RECIDIVISTA 3560 ? LOIS LANE NOVY 806070 ? JAMES BOND RECIDIVISTA 007 Lexikograficky strom pre rychle vyhladavanie. Ovladanie je ESC pre exit a ? klavesa pre vyhladavanie. Program si vie aj zapamatat novopecenych recidivistov, ktorych si hned poznamena do stromu, tabulky aj do suboru cez append. Subor je obycajny textovy. Da sa premazat, ale nechal som dva prve riadky pre hlavicku Alcatraz II. Preto by mali byt vzdy 2 riadky zhora (program automaticky preskakuje 2 riadky). Program pouziva binarny strom, a sice dva. Jeden sluzi pre evidovanie vaznov, ten je lexikograficky s vetvami nazvov 'a'..'z' a velke pismena sa osetruju hned na zaciatku ansilowercase-om. Druhy je strom cisielkovy, je naprosto rovnaky, len s mensim poctom vetiev. Podstatna je len platna cesta. STROM Vaznov (napriklad): Strom Cisiel vaznov (napriklad): * * / * * * * * * / * * * *[a] = -1 *[c] = 7 * [0] = nil?* * [7]=nil?* (neexistuje)* (1 index v tab)* * * * * *** Spolu 26 vetiev v kazdom uzle tu je vetiev 10 Tabulka cisiel vaznov: [0] 313 [7] 007 ... Pri vkladani do cisloveho stromu sa len vytvaraju nove vetvy s nil podvetvami. Je to pre rychle vyhladavanie. Pri vkladani do pismenkoveho stromu sa vytvaraju nove vetvy takisto, ale kazda novovytvorena vetva sa nastavi na -1 pre cislo indexu. Okrem poslednej vetvy, kde uz sa vklada priamo cislo. Toto cislo indexu je velmi dolezite, lebo "Karol Koubek" je recidivista. Dozorca chce zistit, ci novoprijaty Karol Koube je uz v databaze. V beznom pripade ak by sme neskumali korektnost pomocou -1, by sme presli vetvami az po ..ek a zistime ze cesta je platna, vazen teda existuje. To je chyba. Pre istotu som aj do cisloveho stromu dal -1 validator. Keby sa cesta skoncila predcasne a cislo by nemalo existovat. Napriklad pri generovani noveho cisla pre noveho recidivistu, stary je zapisany ako 666, vytvori sa nahodou 666. Toto sa uz nestane. Nesmu byt dvaja rovnaki recidivisti a dve rovnake cisla. Dolezite je este spomenut ze pre tabulku skutocnych cisiel vaznov, pouzivam hlavny index velkost_pola_recidivistov, ktory sluzi jednak ako posledna aktualna velkost, a zaroven ako hodnota, ktora sa uklada do stromu vaznov. Pohyb v pismenkovom strome prebieha tak, ze sa retazec rozdeli na znaky, a zistuje sa len to, ci existuje vetva oznacena ako znak[z]. Pohyb v cisielkovom strome je rovnaky, pouziva vetvy oznacene ako 'a'..'z'. Mal som aj lepsie riesenie: z ciselka berieme poslednu cifierku najpr, teda z 1567 si zoberieme 7 pomocou 1567 mod 10. Potom cisielko este zmensime div 10. Vysledok zapiseme a nastavime novu vetvu. Ale nesplnalo to kriteria pre 007. Sofistikovane je prevedene zlucenie stromu cisielok a stromu vaznov. A to tak, ze vo vetve vaznov sa okrem mena eviduje cislo, ale nie konkretne instantne cislo, ale len poradove cislo indexu na lokalnej tabulke vaznov. Potom konkretne cislo vazna dostaneme, ked pouzieme toto "cislo" v indexe tabulky, a tym ho spravne rozlustime. Pole je array of string, a je dynamicke, pre rozny pocet vaznov a pre setrenie pamate. Jediny sposob ktory mi napadol pre okamzite zistenie ci novy vazen sa nekryje s inym vaznom (ciselne). Z cisielkoveho stromu je jedno ci cislo berieme v strome od predu alebo od zadu. Podstatne je len to, aby sme vzdy zvolili rovnaky postup. V zadani som si vsimol aj cislo 007. Rozhodol som sa teda, pre zjednodusenie vetvy urcit ako typ char. Ostatne veci su uz prijemne, zlozitost programu je O^n, priamo umerna poctu pismeniek a cisielok.