Najvhodnejšia dátová štruktúra na vyriešenie úlohy

Na vstupe sa nachádza postupnosť mien osôb. Meno osoby je reťazec znakov, neexistujú dve rôzne osoby s rovnakým menom. V postupnosti sú zachytení prichádzajúce aj odchádzajúce osoby z miestnosti. Pri spracovaní mena ľahko určíme, či ide o príchod alebo odchod podľa toho, či sa osoba s daným menom momentálne v miestnosti nachádza (odchod) alebo nie (príchod).

Napíšte program v jazyku C/C++, ktorý na vstupe dostane postupnosť mien osôb a na výstup vypíše pre každý príchod osoby do miestnosti jej meno, počet predchádzajúcich pobytov v miestnosti a jej umiestnenie v abecednom usporiadaní momentálne zadržiavaných osôb. Snažte sa vytvoriť najefektívnejšie možné riešenie, bodovanie závisí aj od počtu dátových vzoriek, ktoré váš program bude schopný vyriešiť.

Príklad vstupu:

Kód: Vybrať všetko

boris cyril boris adam boris

Príklad výstupu:

Kód: Vybrať všetko

boris 0 1
cyril 0 2
adam 0 1
boris 1 2

-----------------------------------------------------------------
Nechcem, aby mi to tu niekto riešil.
Chcem len nejaké návrhy, ako by sa to dalo riešiť. resp. aký vhodný dátový typ zvoliť...

môj návrh je použiť množinu

ďakujem za všetky pripomienky na mieste

piton

Velmi nerozumiem tomu zadaniu, ale typ vstupu bude asi dvojrozmerne pole char (v C), pripadne dynamicky alokovane...

piton napísal:Velmi nerozumiem tomu zadaniu, ale typ vstupu bude asi dvojrozmerne pole char (v C), pripadne dynamicky alokovane...

mal by to byt bud, strom, mnozina alebo daco take zlozitejsie... a mimochodom dvojrozmerne pole mi nepride ako dobry napad... toboz uz nie pole charov... to musia byt nejake struktury

juho · Príspevok od používateľa **juho** » 22 okt 2008, 6:51

tak asi binarny zoznam cize strom a jasne ze cez struct-ury . cize ked sa ma vypisat meno pri prichode prvy udaj je pocet predchadzajucich prichodov a druhy je vzostupne umiestnenie v abecede, tak to len prebehnes a bud pridas jeden zaznam alebo zmenis.

mas pravdu, super, to by mohlo byt elegantne riesenie...
diky

a este ako spravit toto

Kód: Vybrať všetko

umiestnenie v abecednom usporiadaní

juho · Príspevok od používateľa **juho** » 22 okt 2008, 12:31

sak pojdes postupne po vetve od zaciatku a zistis kolky prvok je to v poradi..pricom ten prvok si zaradil uz predtym podla abecedy tak ze si kontroloval napr. zaciatocne pismena.

juho napísal:sak pojdes postupne po vetve od zaciatku a zistis kolky prvok je to v poradi..pricom ten prvok si zaradil uz predtym podla abecedy tak ze si kontroloval napr. zaciatocne pismena.

lenze ked pojdem napr. hned z korena do laveho podstromu, tak ja neviem kolko je mien v pravom podstrome... teda viem ich spocitat ale neviem to priamo

gwixt

preco by si ich chcel spocitavat?

V zadani je ze pri kazdom prichode sa ma vypisat pocet predchadzajucich navstev (to nie je problem) a poradie v abecednom zozname (toto je problem).

Ten zoznam sa sklada len z osob, ktore su v miestnosti.

gwixt

aky problem? ved ten linearny zoznam .. alebo bin. strom budes mat vzdy abecedne usporiadany ... o to sa postaras pri vkladani novej osoby .... tak vo co go?

gwixt napísal:aky problem? ved ten linearny zoznam .. alebo bin. strom budes mat vzdy abecedne usporiadany ... o to sa postaras pri vkladani novej osoby .... tak vo co go?

nakoniec nam v skole povedali, ze sa to ma riesit heshovacou tabulkov

gwixt · Príspevok od používateľa **gwixt** » 28 okt 2008, 9:47

heh ... presne to som si aj myslel ... ked napisu pouzite najefektivnejsie riesenie, vzdy je to hashovacia tabulka

aj ked som mal z toho skusku ... takmer kazdy pouzil nejaky strom a ono to mala byt hash tabulka

... aj ked je tazsie ju spravit, vo vysledku je najefektivnejsia