5. Zásobník

5.2  Problém - Priehradkové triedenie

  Utrieďte N - prvkovú postupnosť K - ciferných prirodzených čísel. Využite metódu tzv. priehradkového triedenia, pri ktorom sa pre každú z číslic 0, 1, 2, ..., 9 zavedie jedna priehradka a vlastné triedenie prebieha takto:

V prvom prechode čísla zo vstupnej postupnosti zaraďujeme do priehradok podľa ich poslednej číslice. Potom čísla spojíme z priehradok do novej postupnosti. V ďalšom prechode čísla z tejto novej postupnosti zaraďujeme do priehradok podľa ich predposlednej číslice, potom čísla z priehradok vyberieme a spojíme do ďalšej novej postupnosti atď. Takto postupujeme až po rád K. Na konci tak získame usporiadanú postupnosť čísel.

Riešenie

Pri riešení využijeme dynamickú údajovú štruktúru zásobník. Použijeme jeden hlavný zásobník, do ktorého načítame vstupnú postupnosť čísel a desať pomocných zásobníkov predstavujúcich jednotlivé priehradky.

Pôjde o zásobníky s prvkami typu TPrvok:

typedef struct prvok {
   char cifry[K]; 
   struct prvok *dalsi;
} TPrvok;
Deklarujeme pointer na vrch hlavného zásobníka:

TPrvok *vrch;

Deklarujeme pole pointerov na pomocné zásobníky (priehradky):

TPrvok *priehradka[10];

Nech napríklad N = 7 a K = 2.
Vstupná číselná postupnosť: 43 27 31 15 37 80 03

vstup(&vrch);
for (i=0; i<10; i++) priehradka[i] = NULL;

Situácia po uložení vstupnej postupnosti do hlavného zásobníka a vytvorení prázdnych priehradok je na obrázku:

1. prechod:
Z hlavného zásobníka presunieme prvky do priehradok podľa cifry na mieste jednotiek.



Vyprázdnime priehradky presunutím prvkov z pomocných zásobníkov späť do hlavného (v cykle postupne od priehradky č. 0 po č. 9):



2. prechod:
Z hlavného zásobníka presunieme prvky do priehradok podľa cifry na mieste desiatok.



Vyprázdnime priehradky presunutím prvkov z pomocných zásobníkov späť do hlavného (v cykle postupne od priehradky č. 0 po č. 9):



Teraz už stačí len vypísať prvky z hlavného zásobníka na obrazovku.

Usporiadaná postupnosť: 80 43 37 31 27 15 03

  Pri načítavaní vstupnej postupnosti každé číslo "rozbijeme" na cifry! Navyše ak má číslo menej ako K cifier, doplníme potrebný počet núl zľava. Výsledná číselná postupnosť je usporiadaná zostupne.

[Program]