Pole struktur v C - výpis prvků podle kritérií
Zdravím. Prosím někoho zasvěceného, kdo má čas, aby mi poradil s následujícím.
Účelem programu je číst znaky ze standardního vstupu a po ukončení vytisknout na standardní výstup podle četnosti. Znaky se stejnou četností musí být seřazeny podle ord. hodnoty a pokud četnost přeteče (má se pracovat s datovým typem unsigned char), vytisknou se místo četnosti tři písmena. Mám vytvořené pole struktur o 255 prvcích (pro každý znak jeden), do kterého ukládám četnost znaků (proměnná sum) a také stav, zda četnost přetekla (proměnná full typu bool). Např. přečtu znak 'a', tak do pole struktur s indexem 97 přičtu 1 k proměnné sum a pokud je četnost maximální, nastavím proměnnou full na true (stav této proměnné testuji ještě před inkrementací). Tolik k načítání. A teď je potřeba prvky seřadit podle četnosti. Řešil jsem to pomocí selection sort. Ještě bylo nutné přidat do struktury další proměnnou ord, která představovala ordinální hodnotu znaku (pořadí se měnilo, tak už pro určení ord. hodnoty nestačil pouhý index v poli, jestli mi rozumíte). Znaky se tedy seřadily podle četnosti od nejvyšší a drůhým průchodem (tentokrát bubble sort) se řadily jen znaky se stejnou četností podle ord. hodnoty. Nakonec program vypsal strukturu na stdout. To vše funguje správně. Asi se ptáte, co mám teda za problém. Jde o to, že k seřazování struktury (prej) vůbec nemusí dojít a přesto lze znaky vypisovat podle zadání. Prosím o lehké nakopnutí, jak to udělat. Jako příklad stačí i obyčejné pole řekněme o 10 číslech {9,4,6,2,7,1,8,3,15,32}. Jak z něj vypsat čísla seřazená od nejvyššího bez použití nějaké řadící metody? Děkuji.
Jedině na kvantovém počítači...
Vypisovat ve správném pořadí čísla z pole nejde, bez toho, aniž bys je předtím seřadil. Což nejde v O(n). Umí to jenom Radix sort a to ještě jenom v některých případech.
V zadání projektu je tohle:
Co tím teda mají na mysli?
Tím chtějí říct, že data stačí seřadit až ve chvíli, kdy je potřebuješ mít seřazené. Není nutné je řadit průběžně.
Leda tak...
Mám tedy správný postup, když data nejdřív přečtu, poté je seřadím a nakonec vytisknu? Nebo ve které fázi bych je měl řadit?
Jistě. Osobně by mě ani nenapadlo to řadit průběžně, pokud by to z principu úlohy nebylo nutné.
Dobře, pak tedy není co řešit. Díky.
to je blbost:
Takže jestli nemam mít seřazené data a zároven je mam tisknout v nějakém pořadí -> O(n*n) složitost, no fakt magoři, to určitě zadal nějak učitel.
Jasně že učitel
Ale uvítal bych nějakou radu, jak na to.
To fakt netuším. Kdo to psal?
Vracím se ještě k tomuto tématu. Od cvičícího jsem v diskuzi na toto téma dostal tento vzkaz:
Z čehož plyne, že seřadit pole ještě před výpisem na obrazovku není správně. Zkuste mi prosím poradit, jak z neseřazeného pole vybírat prvky od nejvyššího po nejnižší a hned tisknout. Napadá mě projíždět strukturou, hledat max. číslo a jak ho vypíšu, označím, že už je vypsané a hledám znovu max. číslo ze zbytku.