// begin code
#include <iostream>
using namespace std;
struct Tekst
{
char * value;
int length;
Tekst (char *s, int lengte)
{
length = lengte;
value = new char[lengte];
strcpy(value,s);
}
};
typedef struct LijstElement *Lijst;
const Lijst LegeLijst = NULL;
struct LijstElement
{
Tekst kop;
Lijst staart;
LijstElement (Tekst k, Lijst s = LegeLijst): kop(k), staart(s) { };
};
class Stapel
{
public:
Lijst inhoud;
Stapel () { inhoud = LegeLijst; langste = 0; Lijst z = inhoud; };
int langste;
Lijst z;
void erop (Lijst e, int lengte);
Lijst eraf ();
bool isLeeg ();
void toon () ;
int bepaalLengtLangsteWoord();
} ;
// Plaatst een woord op de stapel.
void Stapel :: erop (Lijst e, int lengte)
{
e->staart = inhoud;
inhoud = e;
if(lengte>langste)
langste = lengte;
}
// Haalt een woord van de stapel af.
Lijst Stapel :: eraf()
{
Lijst tmp = z;
z = z->staart;
return tmp;
}
// Zegt dat de stapel leeg is.
bool Stapel :: isLeeg()
{
return (inhoud==LegeLijst);
}
// Toont de inhoud van de stapel.
void Stapel :: toon()
{
for(;inhoud!=LegeLijst;inhoud=inhoud->staart)
cout << inhoud->kop.value << (inhoud->staart==LegeLijst ? "." : ",\n");
}
// vul de megeven rij van tekens 'tekst' met willekeurige inhoud
// de willekeurige karakters zitten in de range [min..max] (inclusief)
// de lengte van de willekeurige string wordt eveneens random bepaald en opgeleverd
int willekeurigeTekst(char min, char max, char tekst [], int max_lengte)
{
const int lengte = rand () % max_lengte + 1;
for (int i = 0; i < lengte; i++)
tekst[i] = min + rand() % (max - min + 1);
tekst[lengte] = '\0';
return lengte;
}
// genereer een stapel van een bepaalde grootte met willekeurige teksten
// de willekeurige karakters zitten in de range [min..max] (inclusief)
// de lengte van de langste tekst wordt opgeleverd
int willekeurigeStapel (int lengte, char min, char max, Stapel & stapel)
{
const int MaxLengte = 10;
char tekst [MaxLengte+1];
int grootste = 0;
for ( ; lengte > 0; lengte--)
{ const int lengte = willekeurigeTekst(min, max, tekst, MaxLengte);
stapel.erop (new LijstElement(Tekst (tekst,lengte)),lengte);
if (lengte > grootste)
grootste = lengte;
}
return grootste;
}
// Stapelt de sub-stapels weer op, maar dan in volgorde.
void radixHerstapel(Stapel s, Stapel letters[])
{
for(int x = 25; x > -1; x--)
for(;letters[x].inhoud!=LegeLijst;letters[x].inhoud=letters[x].inhoud->staart)
s.erop(letters[x].eraf(),letters[x].inhoud->kop.length);
}
// Verdeelt de tekst in (sub-)stapels, van elke letter 1, en 1 waar alle woorden die korter zijn in gezet worden.
void radixVerdeel(Stapel s, Stapel letters[], int x)
{
for(;s.z!=LegeLijst;s.z=s.z->staart)
if(s.inhoud->kop.length>=x)
letters[s.z->kop.value[x]-97].erop(s.eraf(),s.inhoud->kop.length);
else
letters[0].erop(s.eraf(),s.inhoud->kop.length);
}
// Sorteert de stapel.
void radixSort(Stapel s)
{
Stapel letters[26];
for(int x = s.langste-1; x >= 0; x--)
{
radixVerdeel(s,letters,x);
radixHerstapel(s,letters);
}
}
// Het programma wordt hier aangestuurd.
int main()
{
Stapel s;
const int grootste = willekeurigeStapel(250,'a','z',s);
radixSort(s);
s.toon();
return 0;
}
// end code
--
Caliguala