VPF::Помогите составить дерево - Форум программистов

Igor_K

Дата 16.4.2008, 21:13 (ссылка)

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

Загрузка ...

Бывалый

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

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

Всем привет!

У меня возникли трудности с составлением дерева. Не могу сообразить, ума не хватает :(((
Есть массив:

Код


$arr = array
(
    array(1, 0, 'Элемент № 1'),
    array(2, 1, 'Элемент № 2'),
    array(3, 2, 'Элемент № 3'),
    array(4, 3, 'Элемент № 4'),
    array(5, 2, 'Элемент № 5'),
    array(6, 3, 'Элемент № 6'),
    array(7, 1, 'Элемент № 7'),
    array(8, 2, 'Элемент № 8'),
    array(9, 1, 'Элемент № 9'),
    array(10, 1, 'Элемент № 10')
);

где внутренние массивы имеют вид array(идентификатор, родитель, значение)

нужно его преобразовать в массив такого вида:

Код


$aarr = array
(
    'Элемент № 1',
    array
    (
        'Элемент № 2',
        array
        (
            'Элемент № 3',
            array
            (
                'Элемент № 4',
                'Элемент № 6'
            ),
            'Элемент № 5',
            'Элемент № 8'
        ),
        'Элемент № 7',
        'Элемент № 9',
        'Элемент № 10'
    )
);

то есть создать такое от дерево. Только ума не хватает, подскажите пожалуйста! smile

Советом, или ссылками.

GZep

Дата 16.4.2008, 21:53 (ссылка)

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

Загрузка ...

участник Винграда

Профиль
Группа: Завсегдатай
Сообщений: 1528
Регистрация: 7.7.2006
Где: Москва

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

Igor_K, тебе нужна функция, которая бы принимала 1й вариант и возвращала второй?

--------------------

Igor_K

Дата 16.4.2008, 22:05 (ссылка)

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

Загрузка ...

Бывалый

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

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

GZep, можно и функцию, можно и на словах обьяснить. smile

Я уже и так исяк, но не получается :(

almagnit

Дата 16.4.2008, 22:16 (ссылка)

(голосов:2)

Загрузка ...

Опытный

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

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

Если с операторами РНР у Вас все в порядке, тогда используте алгоритм:

1. Нужно узнать сколько нужно различных массивов для построения дерева, в Вашем случае нужно

четыре массива на это указывают их номера "0,1,2,3" в значениях массива arr.

2. Создаем массив с требуемым количеством элементов, либо нужное количество отдельных массивов

и присваиваем его n-ой ячейке, либо n-му массиву - элементы массива arr с соответствующими

значениями, т.е. в нулевую ячейку, либо в нулевой массив мы добавляем строку 'Элемент №1' и т.д.

3. Формируем массив aarr из полученного промежуточного массива или массивов

Fortop

Дата 16.4.2008, 22:46 (ссылка)

(голосов:2)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2200
Регистрация: 13.11.2007
Где: Донецк

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

Цитата(almagnit @ 16.4.2008, 22:16

)

ужно узнать сколько нужно различных массивов для построения дерева, в Вашем случае нужно
четыре массива на это указывают их номера "0,1,2,3" в значениях массива arr.

Вообще-то нужен всего 1 массив.

--------------------

Мир это Я.
Живее всех живых.

Igor_K

Дата 16.4.2008, 22:47 (ссылка)

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

Загрузка ...

Бывалый

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

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

almagnit, спасибо большое!!! smile

Цитата(almagnit @ 16.4.2008, 22:16

)

3. Формируем массив aarr из полученного промежуточного массива или массивов

Только от с этим не очень понял. Допустим получил 4 массива, как их соединить правильно? То есть поместить в нужную позицию.
Например, от, получил:

Код


$ar = array
(
    array
    (
        'Элемент № 1'
    ),
    array
    (
        'Элемент № 2',
        'Элемент № 7',
        'Элемент № 9',
        'Элемент № 10'
    ),
    array
    (
        'Элемент № 3',
        'Элемент № 5',
        'Элемент № 8'
    ),
    array
    (
        'Элемент № 4',
        'Элемент № 6'
    )
);

GZep

Дата 16.4.2008, 22:54 (ссылка)

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

Загрузка ...

участник Винграда

Профиль
Группа: Завсегдатай
Сообщений: 1528
Регистрация: 7.7.2006
Где: Москва

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

Igor_K, что-то мне подсказывает, что для решения вопроса нужно увидеть причину для такой сортировки массива. Может на конкретном примере? (вероятно, может получиться более простой способ решения реальной проблемы).

--------------------

skyboy

Дата 16.4.2008, 23:26 (ссылка)

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

Загрузка ...

неОпытный

Профиль
Группа: Модератор
Сообщений: 9820
Регистрация: 18.5.2006
Где: Днепропетровск

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

в каждом элементе объяви ещё один элемент массива - типа, children(к примеру).
тогда будет проще собрать дерево:

Код


$arr = array
(
    array(1, 0, 'Элемент № 1', array()),
    array(2, 1, 'Элемент № 2', array()),
    array(3, 2, 'Элемент № 3', array()),
    array(4, 3, 'Элемент № 4', array()),
    array(5, 2, 'Элемент № 5', array()),
    array(6, 3, 'Элемент № 6', array()),
    array(7, 1, 'Элемент № 7', array()),
    array(8, 2, 'Элемент № 8', array()),
    array(9, 1, 'Элемент № 9', array()),
    array(10, 1, 'Элемент № 10', array())
);
$root= null;
foreach($arr AS $key => $element) 
{
  if($element[1] == 0)
    $root= &$arr[$key];
  else
   $arr[$element[1] - 1][3][]= &$arr[$key];
}
print_r($root);

после сей операции у тебя получится не совсем то, что ты описал(из-за дополнительных элементов), но по полученной структуре пройтись вполне можно будет.
ещё я бы сделал ассоциативный массив(id, parent, name, chidren), а то обращение

Код


$root['children'][4]['children'][2]['name']

понятнее, чем

Код


$root[3][4][3][2][2]

вот пример вывода:

Код


Array
(
    [0] => 1
    [1] => 0
    [2] => Элемент № 1
    [3] => Array
        (
            [0] => Array
                (
                    [0] => 2
                    [1] => 1
                    [2] => Элемент № 2
                    [3] => Array
                        (
                            [0] => Array
                                (
                                    [0] => 3
                                    [1] => 2
                                    [2] => Элемент № 3
                                    [3] => Array
                                        (
                                            [0] => Array
                                                (
                                                    [0] => 4
                                                    [1] => 3
                                                    [2] => Элемент № 4
                                                    [3] => Array
                                                        (
                                                        )
                                                )
                                            [1] => Array
                                                (
                                                    [0] => 6
                                                    [1] => 3
                                                    [2] => Элемент № 6
                                                    [3] => Array
                                                        (
                                                        )
                                                )
                                        )
                                )
                            [1] => Array
                                (
                                    [0] => 5
                                    [1] => 2
                                    [2] => Элемент № 5
                                    [3] => Array
                                        (
                                        )
                                )
                            [2] => Array
                                (
                                    [0] => 8
                                    [1] => 2
                                    [2] => Элемент № 8
                                    [3] => Array
                                        (
                                        )

                                )
                        )
                )
            [1] => Array
                (
                    [0] => 7
                    [1] => 1
                    [2] => Элемент № 7
                    [3] => Array
                        (
                        )
                )

            [2] => Array
                (
                    [0] => 9
                    [1] => 1
                    [2] => Элемент № 9
                    [3] => Array
                        (
                        )
                )

            [3] => Array
                (
                    [0] => 10
                    [1] => 1
                    [2] => Элемент № 10
                    [3] => Array
                        (
                        )
                )
        )
)

SelenIT

Дата 17.4.2008, 00:29 (ссылка)

(голосов:4)

Загрузка ...

баг форума

Профиль
Группа: Завсегдатай
Сообщений: 3996
Регистрация: 17.10.2006
Где: Pale Blue Dot

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

Имхо, для исходной задачи так немного нагляднее:

Код


// сортируем исходный массив так,
// чтобы предки гарантированно шли впереди потомков
// (чтобы не потерять ни одной ветки)
function cmp($a,$b) {
    if ($a[1]!=$b[1]) return $a[1] - $b[1];
    else return $a[0] - $b[0];
}
usort($arr, "cmp");

// запоминаем ID-ы непустых ветвей (в ключах массива, для быстроты)
foreach ($arr as $elem) {
    $subtrees[$elem[1]] = 1;
}

// "вешаем" элементы на дерево
// если у элемента есть поддерево -
// создаем соотв. массив и вешаем ссылку на него сразу после самого эл-та
foreach($arr as $elem) {
    $tree[$elem[1]][] = $elem[2];
    if (isset($subtrees[$elem[0]])) {
        $tree[$elem[0]] = &$tree[$elem[1]][];
    }
}

// выводим полное дерево для корневого элемента
print_r($tree[0]);

Цитата(Igor_K @ 16.4.2008, 22:47

)

Допустим получил 4 массива, как их соединить правильно? То есть поместить в нужную позицию.

Лучше всего сделать этот массив ассоциативным:

Код


$ar = array
(
    0 => array
    (
        1 => 'Элемент № 1'
    ),
    1 => array
    (
        2 => 'Элемент № 2',
        7 => 'Элемент № 7',
        9 => 'Элемент № 9',
        10 => 'Элемент № 10'
    ),
    2 => array
    (
        3 => 'Элемент № 3',
        5 => 'Элемент № 5',
        8 => 'Элемент № 8'
    ),
    3 => array
    (
        4 => 'Элемент № 4',
        6 => 'Элемент № 6'
    )
);

Тогда из самого массива сразу станет ясно, что к чему привязывать smile

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

skyboy, в первом примере круто повезло, что айдишники идут по порядку, начиная с единицы;)

Это сообщение отредактировал(а) SelenIT - 17.4.2008, 00:31

--------------------

Осторожно! Данный юзер и его посты содержат ДГМО! Противопоказано лицам с предрасположенностью к зонеризму!

skyboy

Дата 17.4.2008, 00:49 (ссылка)

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

Загрузка ...

неОпытный

Профиль
Группа: Модератор
Сообщений: 9820
Регистрация: 18.5.2006
Где: Днепропетровск

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

Цитата(SelenIT @ 16.4.2008, 23:29

)

skyboy, в первом примере круто повезло, что айдишники идут по порядку, начиная с единицы;)

полный вариант: "круто повезло, что индекс в массиве совпадает со значением id - 1" ;)
етественно, лучше было бы, если бы индексом элемента в начальном массиве был бы сам id. тогда бы и единицу не прилось бы вычитать.
и если бы элементы юыли бы ассоциативным массивом, было бы удобнее и т.д..

SelenIT

Дата 17.4.2008, 00:54 (ссылка)

(голосов:1)

Загрузка ...

баг форума

Профиль
Группа: Завсегдатай
Сообщений: 3996
Регистрация: 17.10.2006
Где: Pale Blue Dot

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

Цитата(skyboy @ 17.4.2008, 00:49

)

полный вариант: "круто повезло, что индекс в массиве совпадает со значением id - 1" ;)

Да, именно это я имел в виду smile

--------------------

Осторожно! Данный юзер и его посты содержат ДГМО! Противопоказано лицам с предрасположенностью к зонеризму!

skyboy

Дата 17.4.2008, 01:18 (ссылка)

(голосов:4)

Загрузка ...

неОпытный

Профиль
Группа: Модератор
Сообщений: 9820
Регистрация: 18.5.2006
Где: Днепропетровск

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

чтоб не париться, можно положить, что исходный массив может быть только таким и модификацию производить собственными силами:

Код


$arr=... // заполнение массива
$result= array();
foreach($arr AS $value) // преобразование массива
{
  $result[$value[0]]= array('id'=> $value[0],'parent'=> $value[1], 'name'=> $value[2], 'children'=> array());
}
$root= null;
foreach($result AS $key => $element) 
{
  if($element['parent'] == 0)
    $root= &$result[$key];
  else
   $result[$element['parent']]['children'][$element['id']]= &$result[$key];
}
print_r($root);

все же, как мне кажется, сортировка в решении будет лишней. у нас и так для ассоциативного массива хеш строится...
P.S. Да, мой код похож на код SelenIT'a, но, чесное слово, не плагиатил, а доработал smile

SelenIT

Дата 17.4.2008, 01:34 (ссылка)

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

Загрузка ...

баг форума

Профиль
Группа: Завсегдатай
Сообщений: 3996
Регистрация: 17.10.2006
Где: Pale Blue Dot

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

Цитата(skyboy @ 17.4.2008, 01:18

)

как мне кажется, сортировка в решении будет лишней. у нас и так для ассоциативного массива хеш строится...

Да, вариант с хешем однозначно лучше smile

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

--------------------

Осторожно! Данный юзер и его посты содержат ДГМО! Противопоказано лицам с предрасположенностью к зонеризму!

Igor_K

Дата 17.4.2008, 16:17 (ссылка)

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

Загрузка ...

Бывалый

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

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

Спасибо большое!!!!! smile

Щяс буду пробовать ваши варианты. smile

Igor_K

Дата 17.4.2008, 17:23 (ссылка)

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

Загрузка ...

Бывалый

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

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

Цитата(SelenIT @ 17.4.2008, 00:29

)

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

Да, из базы данных. а как ее получить в таком виде?

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