ANSI C: Walking tree

SVK · Post by **SVK** » 28 Apr 2004 04:03

Strannik223 wrote:А когда перешли вверх, то что, колбасим весь уровень с начала?
Это вечный цикл, или я что то проглядел?

Когда перешли вверх (goUp), то идем вправо, если можно. Если нельзя вправо, то идем дальше вверх - не далее чем начальный *top.

Не будет бесконечного цикла. :umnik1:

Strannik223 · Post by **Strannik223** » 28 Apr 2004 04:03

A. Fig Lee wrote:
olg2002 wrote:В данной задаче, если бы мы решали ее с помощью рекурсивной функции, у нас было бы два рекурсивных вызова в ее теле: один для child, другой для next. В этом основная трудность: кроме стека аргументов, нам нужен еще стек точек возврата. Очень хорошая задача на понимание рекурсии!

Так отож! С рекурсией-то проблем нет - ето был предыдущий вопрос.
Интересно кстати, как Странник представляет себе реализацию стека без хипа.
Мне кроме сложных манипулаций с varg идеи не лезут...

А что, надо еще и без хипа?

SVK · Post by **SVK** » 28 Apr 2004 04:05

A. Fig Lee wrote:Strannik, не так.
все что направо - ето некст тех елементов, которые слева.
Которые внизы - чайлды тех елементов, кто над ними.
То есть добавить -> между квадратами для некст и стрелка вниз для чайлдов (только вниз, не вправо, ни влево). ну лень рисовать было.

Например: 7 - это child от 6, или next от 3???

A. Fig Lee · Post by **A. Fig Lee** » 28 Apr 2004 04:07

Да, картинка плохая. Вот лучше. Красные стрелки - К нексту, зеленые - К чайлдам (от родителей).

SVK · Post by **SVK** » 28 Apr 2004 04:09

A. Fig Lee wrote:Да, картинка плохая. Вот лучше. Красные стрелки - К нексту, зеленые - К чайлдам (от родителей).

Я понял, что сбивало с толку - отсутствие стрелок parent. Без них нужна рекурсия, а с правильными parents - будет работать, как я написал :gen1:

A. Fig Lee · Post by **A. Fig Lee** » 28 Apr 2004 04:10

Strannik223 wrote:А что, надо еще и без хипа?

Дак а с хипом то - какая разница, можно просто realloc().
Вообще если хипом, задачу можно решить, но изврат какой-то получается..

Strannik223 · Post by **Strannik223** » 28 Apr 2004 04:10

SVK wrote:
Strannik223 wrote:А когда перешли вверх, то что, колбасим весь уровень с начала?
Это вечный цикл, или я что то проглядел?

Когда перешли вверх (goUp), то идем вправо, если можно. Если нельзя вправо, то идем дальше вверх - не далее чем начальный *top.

Не будет бесконечного цикла. :umnik1:

Да, теперь понял, должно работать.

A. Fig Lee · Post by **A. Fig Lee** » 28 Apr 2004 04:11

SVK wrote:
A. Fig Lee wrote:Да, картинка плохая. Вот лучше. Красные стрелки - К нексту, зеленые - К чайлдам (от родителей).

Я понял, что сбивало с толку - отсутствие стрелок parent. Без них нужна рекурсия, а с правильными parents - будет работать, как я написал

ne budet. Once you got right, you may no go back left.

после 4-го попадет на 8-й и никогда не выберется до 3->7

SVK · Post by **SVK** » 28 Apr 2004 04:13

A. Fig Lee wrote:
SVK wrote:
A. Fig Lee wrote:Да, картинка плохая. Вот лучше. Красные стрелки - К нексту, зеленые - К чайлдам (от родителей).

Я понял, что сбивало с толку - отсутствие стрелок parent. Без них нужна рекурсия, а с правильными parents - будет работать, как я написал

ne budet. Once you got right, you may no go back left.

Чем спорить на словах, я предлагаю дорисовать правильные parents и убедиться, что будет работать

Strannik223 · Post by **Strannik223** » 28 Apr 2004 04:15

A. Fig Lee wrote:
SVK wrote:
A. Fig Lee wrote:Да, картинка плохая. Вот лучше. Красные стрелки - К нексту, зеленые - К чайлдам (от родителей).

Я понял, что сбивало с толку - отсутствие стрелок parent. Без них нужна рекурсия, а с правильными parents - будет работать, как я написал :gen1:

ne budet. Once you got right, you may no go back left.

после 4-го попадет на 8-й и никогда не выберется до 3->7

Не понял, у 6,7,8 parent == NULL ?!!!

SVK · Post by **SVK** » 28 Apr 2004 04:20

Strannik223 wrote:Не понял, у 6,7,8 parent == NULL ?!!!

По-правильному,
parent для 2, 6 и 9 - есть 1
parent для 3 и 7 - есть 2
parent для 4, 8 и 10 - есть 3
parent для 5 - есть 4
parent для 11 и 13 - есть 10
parent для 12 - есть 11
(хотя конкретно тут parent для "промежуточных" next-ов роли не играет)

A. Fig Lee · Post by **A. Fig Lee** » 28 Apr 2004 04:24

Strannik223 wrote:
Не понял, у 6,7,8 parent == NULL ?!!!

Ето интересный вопрос. логически парент должен быть.... Ну если будет парент, тогда ето чайлд.. Хммм... Наверное, ето и имелось ввиду...
Хотя конечно могут быть и без парент. Живой пример - MIME аттачменты друг в дружку. Тогда не получится
Ок. Всем спасибо за внимание. :gen1:

A. Fig Lee · Post by **A. Fig Lee** » 28 Apr 2004 04:30

Вообще лучше было бы назвать right i left. было бы четко и понятно.
иначе путаница выходит.

SVK · Post by **SVK** » 28 Apr 2004 04:30

A. Fig Lee wrote:Ето интересный вопрос. логически парент должен быть.... Ну если будет парент, тогда ето чайлд.. Хммм... Наверное, ето и имелось ввиду...
Хотя конечно могут быть и без парент. Живой пример - MIME аттачменты друг в дружку. Тогда не получится
Ок. Всем спасибо за внимание.

Наличие ссылки parent - это здесь основа для нерекурсивных алгоритмов. Без этих дополнительных ссылок требуется рекурсия, либо всякие стеки-нестеки, и прочее фуфло.

SVK · Post by **SVK** » 28 Apr 2004 04:31

A. Fig Lee wrote:Вообще лучше было бы назвать right i left. было бы четко и понятно.
иначе путаница выходит.

Нет, в этом контексте как раз right-left будет сбивать с толку. Как задано в задаче - это наиболее вразумительные обозначения.