Dnia Sat, 26 May 2012 22:51:06 +0200, Borneq napisal:

> Użytkownik "Edek Pienkowski" <e...@g...com> napisał w
> wiadomości news:jprf9r$1eu$1@inews.gazeta.pl...
>> W starych czasach stosy paliły się tak długo jak to było potrzebne. Ale
>> w czasach dzisiejszych powiedziałbym, że to kwestia iteracji a nie
>> rekurencji.
>> Tylko kwestia sprawdzenia czy lepiej najpierw wszerz czy najpierw wgłąb.
>
> Zamiana na iterację to nie taka prosta sprawa, po wskaźniku nie wiadomo że
> będzie długa lista, a może być drzewo lub cykle.

mamy: lista (lub set) obiektów sprawdzanych llll (nie: sprawdzonych,
sprawdzanych).

Bierzemy pierwszy pointer zawarty w dowolnym obiekcie llll,
jeżeli ostatni to mark i usunąć z listy.

No i ten pointee jak ma więcej niż jeden pointer (i nie mark) to dodajemy
do llll i sprawdzamy pointer. I tak w kółko.

Lista może trochę urosnąć to fakt, ale mniej jest pointerów
niż dowolnej treści obiektów w tym pointerów. W zasadzie to prawie
jest pushdown automaton czyli prawie ze stosem, ale mamy set pointerów
a nie stos wywołań, czyli na pewno lepiej. Lista czy tablica
to nie problem, to jeden obiekt w llll albo jeden link do przodu w liście.
Gorsze są drzewa, ale tu jest log n jeżeli są zbalansowane. Dlatego nie
jest do końca dla mnie oczywiste że wgłąb, wredne niezbalansowane drzewa mogą
powodować długą listę.

Edek