
#include "pch.h"
#include 
#include 

using namespace std;

const int N = 20;
const int D = 20; // pocet pismen ve slove
const int K = 256; // pocet prihradek

struct Item
{
    char key [D+1]; // znak 0 na konci
    Item * next;
};

struct List
{
    Item * first;
    Item * last;
};

List inp; // vstup a vystup

List tab[K]; // pole prihradek


void init (List & a)
{
    a.first = nullptr;
    a.last = nullptr;
}

void add (List & a, Item * p)
{
    p->next = nullptr;
    if (a.first == nullptr)
        a.first = p;
    else
        a.last->next = p;
    a.last = p;
}

void link(List & a, List & b) // pridat b na konec a
{
    if (b.first != nullptr)
    {
        if (a.first == nullptr)
            a.first = b.first;
        else
            a.last->next = b.first;
        a.last = b.last;
    }
}

Item * create (int c)
{
    Item * p = new Item;
    // p->key = c
    for (int i = D - 1; i >= 0; i--)
    {
        p->key[i] = '0' + c % 10;
        c = c / 10;
    }
    p->key[D] = 0; // znak nula na konci
    return p;
}

void sort(int r) // tridime podle r-teho pismene
{
    for (int inx = 0; inx < K; inx++)
        init (tab[inx]);

    Item * p = inp.first;
    while (p != nullptr)
    {
        Item * t = p->next; // zapamatovat naslednika pred odpojenim
        int inx = p->key[r]; // cislo prihradky
        add (tab[inx], p);
        p = t;
    }

    init (inp);
    for (int inx = 0; inx < K; inx++)
    {
        link(inp, tab[inx]);
        /*
        Item * p = tab[inx].first;
        while (p != nullptr)
        {
            Item * t = p->next;
            add(inp, p);
            p = t;
        }
        */
    }

}

int main()
{
    init (inp);
    srand (time(NULL));
    for (int i = 0; i < N; i++)
        add (inp, create (rand() % 10000));

    for (int r = D-1; r >= 0; r--)
       sort(r);

    bool ok = true;
    Item * p = inp.first;
    while (p != nullptr)
    {
        cout << p->key;
        Item * t = p->next;
        if (t != nullptr && strcmp (t->key , p->key) < 0) 
           { ok = false; cout << " CHYBA"; }
        cout << endl;
        p = t;
    }
    if (ok)
       cout << "O.K." << endl; 
}