// lexsort.cpp
 
 
#include "stdafx.h"
#include <string>
#include <iostream>
using namespace std;
 
const char low = 'a';
const char high = 'z';
const int k = high - low + 1; // pocet prihradek
 
const int z = 3; // delka retezce
 
class item{ public: char slovo[z];
                    item*next;
                    item():next(nullptr){for (int i=0;i<z;i++) slovo[i]=low;};
};
 
class list{ public:item*first;
                   item*last;
                   list();
                   void add(item* p);
                   void clear();
                   void join(list & p);
};
 
list::list(){
first=nullptr;
last=nullptr;
}
 
void list::add(item* p){
    if (first==nullptr){first = p;}
    else last->next = p;
    last = p;
    p->next = nullptr;
}
 
void list::clear(){
    first =nullptr;
    last = nullptr;
}
 
void list::join(list & p)
{
    if (p.first != nullptr)
    {
        if (first == nullptr)
        {
            first = p.first;
            last = p.last;
        }
        else
        {
            last->next = p.first;
            last = p.last;
        }
    }
}
 
list vstup;
list box[k];
 
void sort(int i) {
    for(int j = 0; j <k ; j++) 
        box[j].clear();
 
    item *p = vstup.first;
    while(p != nullptr) {
        int j = p->slovo[i] - low;
        item *q = p->next;
        box[j].add(p);
        p=q;
    }
 
    vstup.clear ();
    for (int j = 0; j <k ; j++) { vstup.join(box[j]); }
}
 
void sort () {
    for (int j = z-1; j >= 0 ; j--) 
        sort (j);
}
 
void insert (string s)
{
    item * p = new item ();
 
    int len = s.length ();
    for (int j = 0; j < z; j ++)
    {
        char c = low;
        if (j  < len) c = s[j];
        p->slovo [j] = c;
    }
 
    vstup.add (p);
}
 
void print ()
{
    item * p = vstup.first;
    while (p != nullptr)
    {
        for (int j = 0; j < z; j ++)
            cout << p->slovo[j];
        cout << endl;
        p = p->next;
    }
}
 
int _tmain(int argc, _TCHAR* argv[])
{
    insert ("abc");
    insert ("aba");
    insert ("zax");
    sort ();
    print ();
    system ("pause");
    return 0;
}