VPF::линейный обход хэша - Форум программистов

mastercz

Дата 16.9.2010, 08:04 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 112
Регистрация: 5.11.2008

Репутация: нет
Всего: нет

Добрый день!
Прочитав статью http://base.vingrad.ru/view/1942-Rekursivn...a-ih-lineynyimi я задался вопросом а возможен ли subj.
Т. е. Возможно ли реализовать функцию обхода сложного хэш-массива без рекурсии?

Jimy

Дата 16.9.2010, 08:59 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 177
Регистрация: 4.7.2010

Репутация: нет
Всего: 3

Можно.
Рекурсию не сложно заменить использованием стэка.

ming

Дата 16.9.2010, 11:27 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 97
Регистрация: 30.1.2009
Где: Новосибирск

Репутация: 2
Всего: 3

Я у себя использую такой велосипед smile

Код

sub traverse {
    my ($parent, $onEachSub) = @_;
    
    my (@stack, @parents, @keys);
    push @parents,    $parent;
    push @keys,        keys %$parent;

    my $level = 0;
    
    while(1) {
        my $current_key = shift @keys;
        $parent = $parents[-1];
        if (!$current_key) {
            my $arr_ref = pop @stack;
            if(!$arr_ref) { # stack is empty
                last;
            }
            @keys = @$arr_ref;
            $level--; 
            $parent = pop @parents;
            next;
        } 
        my $current = $parent->{$current_key};
        
        # call handler
        &$onEachSub($current_key,$current,$level) if defined $onEachSub;

        my @subnode_keys = $current ? keys %$current : ();
        if (@subnode_keys) {
            push @stack, [ @keys ];
            push @parents, $current;
            $parent = $current;
            $level++;
            @keys = @subnode_keys;
            next;
        }
    }
}

Хэш допустим такой :

Код

my $HASH= {
            'a' => 
                {
                    'a0' => {
                                'a0_1' => {
                                          'x'=>undef,
                                          'y'=>undef
                                            },
                            },
                    'a1' => undef,
                    'a2' => {
                                'a2_1' => undef,
                            },
                },
            'b' => 
                {
                    'b1' => undef,
                    'b2' => {
                            'b2_1' => {
                                       'M'=>undef,
                                       'N'=>undef
                                        }
                            },
                    'b3' => {
                            'b3_1' => undef
                            },
                }

};

Вызываю так

Код

traverse($HASH, 
    sub {
        # $current_key - ключ текущего элемента, 
        # $current - сам текущий элемент (анонимный субхэш), 
        # $level - уровень вложенности текущего элемента ("0" = верхний уровень)
        my ($current_key, $current, $level) = @_;
        print "     "x$level, "$current_key\n";    
    });

результат

Это сообщение отредактировал(а) ming - 16.9.2010, 11:33

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Perl: Общие вопросы \| Следующая тема »