Форум PHP

Задача вот в чём:
Есть БД `cat` в ней есть параметры `id`, `name` и `subcat`. Первый - это идентииктаор, второй - название и третий - ID родительской категории (вложенность бесконечная)

Мне надо получить все возможные списки подкатегорий. То есть что-то вроде такого списка:

Техника Машина Кухня Техника -> Телефон Техника -> Ноутбук Машина -> Honda Кухня -> Стол Кухня -> Стул Кухня -> Посуда Техника -> Телефон -> Apple Техника -> Телефон -> Nokia Машина -> Honda -> Внедорожник -> ещё_какая-то_подкатегория

И как это всё вывести - я не знаю. Была бы ограниченная вложенность, что-нибудь придумал бы, а так - без понятия, всю ночь пытаюсь придумать решение и ничего в голову не приходит :(

Для решения вам бы надо было к посту приложить такой дамп еще:

CREATE TABLE `cat` (   `id` int(10) unsigned NOT NULL AUTO_INCREMENT,   `name` varchar(255) NOT NULL,   `subcat` int(10) unsigned NOT NULL,   PRIMARY KEY (`id`) ) ENGINE=MyISAM  DEFAULT CHARSET=utf8; INSERT INTO `cat` (`id`, `name`, `subcat`) VALUES (1, 'Техника', 0), (2, 'Машина', 0), (3, 'Кухня', 0), (4, 'Телефон', 1), (5, 'Ноутбук', 1), (6, 'Honda', 2), (7, 'Стол', 3), (8, 'Стул', 3), (9, 'Посуда', 3), (10, 'Apple', 4), (11, 'Nokia', 4), (12, 'Внедорожник', 6), (13, 'ещё_какая-то_подкатегория', 12);

Это конечно, если вы хотите решение.

Если подсказку, то можно и без этого.

Подсказка: Решать надо рекурсией.

Решение:

<?php header('Content-Type: text/plain; charset=utf8'); $db = new mysqli('localhost', 'root', '', 'test'); $db->query('SET NAMES utf8'); $res = $db->query('SELECT * FROM cat ORDER BY subcat'); $arr = array(); while($row = $res->fetch_assoc()){   $arr[$row['id']] = array('name' => $row['name'], 'subcat' => $row['subcat']);   recurs_out($arr, $row['name'], (int)$row['subcat']); } function recurs_out($arr, $name, $subcat){   if($subcat)     recurs_out($arr, $arr[$subcat]['name'], $arr[$subcat]['subcat']);   if($subcat) echo ' -> ';   else echo "\n";   echo $name; }

Результат:

Техника Машина Кухня Техника -> Телефон Техника -> Ноутбук Машина -> Honda Кухня -> Посуда Кухня -> Стул Кухня -> Стол Техника -> Телефон -> Apple Техника -> Телефон -> Nokia Машина -> Honda -> Внедорожник Машина -> Honda -> Внедорожник -> ещё_какая-то_подкатегория

каждый раз дергать всю БД, даже если надо получить всего одну ветку

Это не мои проблемы. Вопроса "как сделать лучше" не звучало.

Вообще-то решение даже на "как сделать хоть как-нибудь" тянет не очень,
поскольку ограничено определенным порядком занесенных в таблицу строк.
Попробуйте, к примеру, 13-ю строку занести вперед других - убедитесь.

И таки да, рекурсия здесь не нужна.
Нужен стек - в Вашем решении рекурсия только его и поставляет.

К автору топика два вопроса.
1. Что понимается под бесконечной вложенностью?
уровней больше нескольких десятков?
уровней больше, чем можно удержать в памяти процесса?
уровни могут быть закольцованы (1, курица, 2), (2, яйцо, 1) и такие кольца нужно ловить?

2.выбор названия subcat для поля с номером надкатегории - это как?

> Попробуйте, к примеру, 13-ю строку занести вперед других - убедитесь.
Работать будет так же, будет другой порядок вывода строк.
Возможно вы не заметили "ORDER BY subcat".
Т.е. при любом раскладе все родители к моменту вывода потомка в $arr уже будут присутствовать.
А чтобы регулировать порядок строк, нужно хотя бы добавить поле level.

В любом случае, по тому как поставлено условие, я предположил, что это какая-то учебная задача, а не реальный проект. Поэтому не стал заморачиваться на тему "так лучше не делать, лучше сделать так".

> в Вашем решении рекурсия только его и поставляет.
Предложите свое решение. Я уже даже за топикстартера дамп сделал =)

> Попробуйте, к примеру, 13-ю строку занести вперед других - убедитесь.
>Работать будет так же, будет другой порядок вывода строк.
>Возможно вы не заметили "ORDER BY subcat".

Вобщем-то, да.
Чисто практически маловероятно, что ключ родителя окажется численно больше ключа потомка.
Но согласитесь, это не тот аспект , на который стоит опираться.

>Предложите свое решение. Я уже даже за топикстартера дамп сделал =)
Если совсем грязно, то что-то такое:

<? .. начало можно Ваше взять...  for($list=array();  $row = $res->fetch_assoc(); )   $list[$row['id']] = array('name' => $row['name'], 'pid' => $row['subcat']); foreach($list as $item) {     for($p = $item['name']; $id = $item['pid']; $p = $item['name'].' -> '.$p)        $item = $list[$id];     echo $p."\n"; }

а если все же сделать честный стек, заодно и про кольца возможные подумать,
выйдет как-то так:

<? for($list=array();  $row = $res->fetch_assoc(); )   $list[$row['id']] = array('name' => $row['name'], 'pid' => $row['subcat']); foreach($list as $id => $item) {   for($s = array($id => $item['name']);        ($id = $item['pid']) && !isset($s[$id]) ;         $s[$id] = $item['name']) $item = $list[$id];   $s=array_reverse($s);   echo implode( ' -> ', $s) ."\n"; }

а тут либо одним запросом всю таблицу подбирать - либо по запросу на каждый выводимый узел.

Учитывая постановку - вывести все возможные пути - фиг знает, что хуже.