Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Perl: разработка для Web > создание древовидной структуры

Автор: Vinnety 11.4.2004, 21:56

Подскажите, пожайлуста!
Как создать древовидную структуру ???
Ну напримет в БД, хранится таблица :
id title parentcode
1 sect1 -1
2 sect2 -1
3 sect11 1
4 sect12 1
5 sect21 2
6 sect22 2
7 sect221 6
8 sect222 6

где id - код раздела, title - название раздела, parentcode - код родительского раздела ( -1 означает код корневого раздела) .

Подскажите как на Перле написать прогу, которая бы выводила на экран структуру ввиде дерева. Например :
sect1
sect11
sect12
sect2
sect21
sect22
sect221
sect222

Или укажите методику, как это лучше и проще сделать !

Автор: Secandr 11.4.2004, 22:17

на форуме был пример обхода дерева, по кругу, заполнения двух доп. столбцов маркерами и потом всё строится великолепно.

можно сделать следующим образом:
заводим массив parent,level и хеш map.

делаем селект, сортируя по parentcode
читаем построчно.
+ Если parentcode=-1 то parent[id]='0';leve[id]=0;map[parent[id].'_'.id]=title;
+ Если parentcode<>1 то parent[id]=parent[parentcode].'_'.parentcode;level[id]=level[parentcode]+1;map[parent[id].'_'.id]=title;
идём к следующей записи.

В итоге получаем %map вида:
0_1=sect1
0_1_3=sect11
0_1_4=sect12

0_2=sect2
0_2_5=sect21
0_2_6=sect22
0_2_6_7=sect221
0_2_6_8=sect222

А отсортировать и распечатать это не сложно.

Автор: Vinnety 12.4.2004, 15:02

Извините, но я не пойму зачем нужен массив @level ???
И как можно будет отсортировать такой хеш %map ???
%map = sort keys %map #<--- так будет не правильно !

Автор: Secandr 12.4.2004, 20:49

level нужен чтоб потом нужной ширины картинку вставить

- просто удобно.

а насчёт неправильно, у меня дома манулов нет

Сейчас ответ найду.
Добавлено @ 20:55
Попробуй @result = sort { $a cmp $b } @somelist;

я попробую завтра на работе, дома перла нет

Автор: Vinnety 13.4.2004, 10:23

К примеру, если
в массив @mas будет содержать:
$mas[0]="0_1";
$mas[1]="0_2";
$mas[2]="0_1_9_99999";
$mas[3]="0_1_2";
$mas[4]="0_2_2";
$mas[5]="0_2_1";
$mas[6]="0_1_1_1";
$mas[7]="0_1_1_2";
$mas[8]="0_1_32323232";
$mas[9]="0_1_9";
$mas[10]="0_1_9_1";

то сортировка @result = sort { $a cmp $b } @mas; будет неправильноЙ :
0_1
0_1_1_1
0_1_1_2
0_1_2
0_1_32323232 # уже на этом месте неправильно !!! :-(
0_1_9
0_1_9_1
0_1_9_99999
0_2
0_2_1
0_2_2

Что делать ?

Автор: GoodBoy 13.4.2004, 12:03

@result = sort { $a cmp $b } @mas;
замени на:
@result = sort { $a <=> $b } @mas;
Perl допускает использование знака "_" в записи числа.

Автор: Secandr 13.4.2004, 12:57

Цитата

0_1_32323232 # уже на этом месте неправильно !!! :-(

А чем это не правильно?

Автор: Secandr 13.4.2004, 13:49

Ещё предложение - можно делать ключи не 0_1_10_999_17, а 00000001001009990017

тогда уж точно проблем с сортировкой не будет

Автор: GoodBoy 13.4.2004, 13:56

Код

0_1_32323232 # уже на этом месте неправильно !!! :-(
0_1_9

по логике вещей 32323232 заведомо больше, чем 9... :-)))

Цитата

Ещё предложение - можно делать ключи не 0_1_10_999_17, а 00000001001009990017

тогда уж точно проблем с сортировкой не будет

Это только в том случае, если заранее будет известна максимальная длина ключа... Либо придется ориетнтироваться на максимальную возможную длинну, что не есть хорошо...

Автор: Secandr 13.4.2004, 14:05

GoodBoy Выборка делается из mysql, а там размер поля ограничен, можно ещё брать текущее максимальное значение.

Автор: Secandr 13.4.2004, 14:16

можно ещё по другому сделать:
при чтении строки пробегать по массиву ища родительский элемент и ставить после его, корневые добавлять в конец.

Автор: Secandr 13.4.2004, 14:31

Вот что я на пхп писал в одном из топиков:

Код

while (is_array($all)){
 unset($next);
 foreach($all as $one){
   $tmp=split('-',$one)
   $parent=$tmp[0];//предок
   $this=$tmp[1];//текущее значение

   if (strrpos($mystring, ",$parent,")>0){//предок уже записан

      eregi_replace(",$parent,",",$parent,$this,",$map);//добавим потомка в строку за предком
      $level[$this]=$level[$parent]+1;//Уровень потомка на 1 выше уровня предка

    }else{//предок ещё не внесён, отложим обработку до внесения предка 
      $next[]=$one;
    }
 }
 $all=$next;// будем проверять отложеные
}

смысл такой:

Код

имеем массив @A, где $A['id']='PREDOK';
имеем строку $LINK=',-1,';
пока @A содержит хотябы один элимент делаем следующее{
  Для каждого элемента массива @A делаем следующее{
    Если в строке $LINK содержится подстрока ",предок," , то заменяем эту подстроку на ",предок,текущий id,"
    иначе добавляем элемент в массив @B
  }
@A=@B
}
Вот вам и сортировка!

Автор: GoodBoy 14.4.2004, 11:17

Тебя спасет рекурсия!!! :-))))))))))

Код

my @elems = (массив ссылок на хэши);
my @result = ();

&create_tree(-1, \@elems, \@result);

sub create_tree {
    my ($pid, $elems, $res) = @_;

    foreach my $elem (sort {$a->{parentcode} <=> $b->{parentcode}} @{$elems}) {
        if ($elem->{parentcode} == $pid) {
            push(@{$res}, $elem);
            &create_tree($elem->{id}, $elems, $res);
        }
    }
}

Имеем в @result отсортированный как тебя надо массив ссылок на хэши. :-)))

$a->{parentcode} <=> $b->{parentcode} замени на $a->{title} cmp $b->{title} если тебе нужно, чтобы в ветвях отсортированного дерева была еще и алфавитная сортировка разделов.

Автор: Secandr 14.4.2004, 20:49

GoodBoy Рекурсия - не лучший выход. Жрёт больше ресурсов.

Автор: Vinnety 15.4.2004, 00:58

Спасибо!!! попробую и через рекурсию !!!!

Автор: GoodBoy 15.4.2004, 13:34

Secandr я не думаю, что в данном случае это важно... Т. к. дерево врядли будет содержать большое кол-во элементов.

Автор: Secandr 15.4.2004, 18:50

GoodBoy Согласен - просто потологически не переношу рекурсию, ещё с 386

Хотя здесь она эффективнее - быстро код пишется и работает с приемлемой скоростью.

Автор: GoodBoy 16.4.2004, 10:57

Цитата

потологически не переношу рекурсию, ещё с 386

А ты абстрагируйся!!!!!!!!!! :-)))))))))))))))

Автор: Guest 21.4.2004, 17:56

Поячитай статейку в http://www.codenet.ru "Множественная модель деревьев"