🚀 go-pugleaf

Christof Laeremans <christof_laeremans@hotmail.com> wrote:
> Code
> ---------
> Stack::Stack(Stack &st)
> {
> _start = NULL;
> Element* temp = st._start;
> While(temp)
>  {
>     Element*e = new Element(temp -> getData());
>     e -> setNext(_start);
>     _start = e;
>     temp = temp -> getNext();
>  }
> }

> De vraag is nu, bestaat er geen "eenvoudigere" manier om een copy
> constructor te implementeren voor een LIFO lijst.

> Maar er is me nog iets opgevallen bij deze copy constructor ... Ik denk dat
> het er ene is voor een FIFO lijst (of vergis ik me) want als ik een kopie
> maak van het object dat de lijst bevat bv. A B C D dan komt er D C B A ....

Je laat de code voor Element::getNext() niet zien, maar als ze doet
wat de naam suggereert wordt de lijst intern inderdaad omgedraaid.
En dus is de code zowel fout voor een FIFO lijst als voor een LIFO
lijst. Want wat je der ook insteekt, het komt er omgekeerd weer
uit.

Tenslotte is er nog iets 'fout'. Een 'echte' copy constructor neemt
als parameter een const reference en geen reference. Maar laten we
dat even terzijde.

Dat gezegd zijnde kunnen we eens gaan denken over 'eenvoudigere' code.
In de hoop dat die eenvoud ook zal inhouden dat het juist zal zijn.
Hier is wat ik zou doen (buiten de STL gebruiken, natuurlijk, maar
ik veronderstel dat je docent je op pointers wil trainen)

Stack::Stack(Stack& st)
: _start(0)
{
	if (st._start)
		_start = st._start->copy();
}

Dat kan alvast niet fout zijn, maar nu hebben we het probleem wel
verschoven naar een 'copy' functie in Element. Maakt dat de zaak
eenvoudiger? Hoe zouden we die copy schrijven? (Ik veronderstel
even dat _next de variable is die naar het volgende element wijst)

Element* Element::copy()
{
	Element* r = new Element(getData());
	if (_next)
		r->_next = _next->copy();
	return r;
}

Waarom is deze oplossing nu eenvoudiger? We hebben onze 'moeilijke'
taak in twee eenvoudige opgesplitst. Zijnde : copieer het eerste
element van een gelinkte lijst en copieer de rest van een
gelinkte lijst. En aangezien het tweede deel van het probleem
eigenlijk ons oorspronkelijke probleem is, gebruiken we heel
natuurlijk recursie.

Een echt lastige docent zou nog als bijvraag kunnen opmerken.
Ja maar : als dit een general purpose stack class is, dan kunnen
die wel eens heel veel elementen bevatten. Wordt dat in de praktijk
dan geen probleem met betreffende stack overflow door het teveel
aanroepen van recursieve functies. Dan zou ik antwoorden.

Dit is een duidelijk geval van 'tail recursion'. De optimalisaties
daarvoor zijn goed gekend en dus in bijna alle moderne compilers
voorzien. En in het geval dat je daar niet op wil/kan rekenen,
is het triviaal om zelf de tail recursion optimisatie uit te
voeren.

(Maar een lastige docent moet ook bereid zijn om zelf op lastige
vragen te antwoorden, zoals waarom hij in dit geval het object
Element dat de data draagt 'vervuilt' met puur infrastructurele
zaken zoals de pointer van de gelinkte lijst. Het gevolg is dat
'Element' enkel in data structuren kan gebruikt worden die volgens
dat principe werken... Beter was om de logical van Stack volledig
binnen 'Stack' te houden en niet deels naar Element te exporteren.)

cu bart

-- 
http://www.irule.be/bvh/