ANSI C: Walking tree

[A. Fig Lee]

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

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

Ето понятно, в том то и суть что previous нет. Ето смущало.
Должен ли быть парент у всех не NULL - по смыслу видать ето и имели ввиду.

[SVK]

Должен ли быть парент у всех не NULL - по смыслу видать ето и имели ввиду.

Это зависит от того, как еще используется такая структура.

Конкретно для walkTree ссылка parent нужна только там, где нет ссылки next - во всех остальных случаях она игнорируется. Но для других алгоритмов промежуточные parent тоже могут требоваться. В общем случае, для такой структуры, правильнее заполнять все parents одного уровня.

[olg2002]

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

Это действительно так. Я сначала воспринял parent как избыточную ссылку, но если она есть, алгоритм обхода сильно упрощается и не требует памяти.

[SVK]

Это действительно так. Я сначала воспринял parent как избыточную ссылку, но если она есть, алгоритм обхода сильно упрощается и не требует памяти.

Да. Я это осознал в те времена, когда из нашей школы уже убрали компьютер "Урал-1", а другого еще не было. И программированию нас в то время учили на абстрактном "Языке символических обозначений"

А оценки за контрольные по программированию были такие:
Первый - очень слабо: оценка 3
Второй - еще хуже: оценка 2
Третий - вообще все перепутано: оценка 1
Четвертый - даже не понял условия: оценка 0
Пятый - явно списал с соседа - одни обрывки: оценка -1
Шестой - даже не начал решать: оценка -2

[A. Fig Lee]

Это действительно так. Я сначала воспринял parent как избыточную ссылку, но если она есть, алгоритм обхода сильно упрощается и не требует памяти.

Да. Я это осознал в те времена, когда из нашей школы уже убрали компьютер "Урал-1", а другого еще не было. И программированию нас в то время учили на абстрактном "Языке символических обозначений"

Да... А я вот не осознал, что ее устанавливать будут...

[olg2002]

У меня самый простой обход такой получился:

Code: Select all

Node *cur=root;
while ( cur ) {
    process( cur );
    if ( cur->child ) {
        cur = cur->child;
        continue;
    }
    while ( cur ) {
        if ( cur->next ) {
            cur = cur->next;
            break;
        }
        cur = cur->parent;
    }
}

[theukrainian]

Нее. По картинке, которую нарисовал Фигли, работать не будет, по-моему. Ведь первая часть цикла уходит всегда на child, и только если нету children вы начинаете смотреть на siblings.

К предыдущим сообщениям: тут parents не NULL - просто tree задается интересно. На самом деле, если это дерево немного перевернуть, то получится что в приведенной картинке, parent 6 это 2.

На самом деле, такой walk решается со стэком. Короче, как Странник сказал ... или я совсем ничего не понял в колбасных обрезках.

[SVK]

У меня самый простой обход такой получился:

Code: Select all

Node *cur=root;
while ( cur ) {
    process( cur );
    if ( cur->child ) {
        cur = cur->child;
        continue;
    }
    while ( cur ) {
        if ( cur->next ) {
            cur = cur->next;
            break;
        }
        cur = cur->parent;
    }
}

1-2-3-4-5-4-5-4-5-4-5-4-5-4-5-4-5-4-5-4-5-4-5-4-.....

Помимо этого:
- повторная обработка узла при движении вверх;
- не остановилась бы на root в случае, когда root задан как под-дерево в более глобальной структуре;
- еще разные мелочи.

Оценка по моим школьным воспоминаниям будет: -1

[SVK]

На самом деле, такой walk решается со стэком. Короче, как Странник сказал ... или я совсем ничего не понял в колбасных обрезках.

Свет клином на стеке не сошелся, однако...

Эта конкретная задача, как я понимаю, именно в том и заключается, чтобы обойтись без всяких дополнительных структур или памяти. В том числе без стека. Именно чтобы понять, умеет ли кандидат сам писать алгоритмы на элементарном уровне, а не только вызывать готовые методы и т.д. Иначе решение любой задачи на свете выглядит примерно одинаково:

result = findSolution( inputData) ;
return result;

[A. Fig Lee]

Да, стек скорее всего не имелся ввиду. В общем как обычно - разгадать что хотели сказать

[theukrainian]

дык, в том то и дело что они, наверное, хотели чтобы кандидат написал стек.

[SVK]

дык, в том то и дело что они, наверное, хотели чтобы кандидат написал стек.

...и это бы на 100% показало, что кандидидат не понимает ситуации. Наличие ссылки *parent - это и есть уже готовый стек прямо встроенный в имеющуюся структуру данных. Если кандидат не может его разглядеть, и строит вместо этого дублирующую структуру, то "таких не берут в космонавты". В перспективе он много дублирующего может понастроить в реальных системах, где это далеко не так очевидно, как в простейшей задаче.

[olg2002]

1-2-3-4-5-4-5-4-5-4-5-4-5-4-5-4-5-4-5-4-5-4-5-4-.....

Помимо этого:
- повторная обработка узла при движении вверх;
- не остановилась бы на root в случае, когда root задан как под-дерево в более глобальной структуре;
- еще разные мелочи.

Оценка по моим школьным воспоминаниям будет: -1

Надо было хоть проверить, как этот алгоритм работает на компьютере, прежде чем такое написать. А так получилось глупо и высокомерно. Хуже нет, когда с таким сталкиваешься на интервью. Единственное путнее замечание про обход поддерева (правится элементарно, но красоту портить не хочется). Оценку ставить не буду.

[SVK]

Надо было хоть проверить, как этот алгоритм работает на компьютере, прежде чем такое написать. А так получилось глупо и высокомерно. Хуже нет, когда с таким сталкиваешься на интервью. Единственное путнее замечание про обход поддерева (правится элементарно, но красоту портить не хочется). Оценку ставить не буду.

Посмотрел еще раз - все могу повторить то же самое. Главное - цикл бесконечный на 4-5-4-5-4-5-4-5-4-5-.... (ну, вижу я это без компьютера ), не считая также не вполне правильных промежуточных результатов. То есть, алгоритм не выдает конечного результата вообще. У нас в школе с этим было строго: нет результата - оценка -1...

[SVK]

правится элементарно, но красоту портить не хочется

По поводу красоты.

Самый красивый алгоритм вычисления факториала, к тому же приводимый в 95-99% учебников, - это рекурсивный вызов

Code: Select all

long fact(int n)
{
return (n > 1)? n * fact(n-1) : 1;
}

Но боюсь что на интервью такой вопрос могут задать скорее с целью отсеять тех, кто даст такой ответ.