итерация. помогите с выводом ветки.

[dorfey]

итерация. помогите с выводом ветки.

Возникла следующая проблема.
Имеем таблицу в БД MySQL следующего вида:
| id | name | parent |
| 1 | компы | 0 |
| 2 | на intel | 1 |

и т.д.

В таблице хранятся разделы сайта.
id - айдишник раздела
name - название раздела
parent - айдишник верхнего уровня.

хотелось бы вывести скажем так ветку разделов, до раздела в котором находится юзер.

Сейчас это у меня реализовано так:

# Достаем айдишник родительского раздела
$select = mysql_query("select * from TABLE where cid=\"$_GET[cat]\"");
$r = mysql_fetch_array($select);


# Тут поехали выбирать разделы
$a1 = mysql_query("select * from table where cid=\"$r[parent]\"");
$c1 = mysql_num_rows($a1);
if($c1 > 0)
{
$b1 = mysql_fetch_array($a1);
$a2 = mysql_query("select * from table where cid=\"$b1[parent]\"");
$c2 = mysql_num_rows($a2);
if($c2 > 0)
{
$b2 = mysql_fetch_array($a2);
$a3 = mysql_query("select * from table where cid=\"$b2[parent]\"");
$c3 = mysql_num_rows($a3);
if($c3 > 0)
{
$b3 = mysql_fetch_array($a3);
$a4 = mysql_query("select * from table where cid=\"$b3[parent]\"");
$c4 = mysql_num_rows($a4);
if($c4 > 0)
{
$b4 = mysql_fetch_array($a4);
$a5 = mysql_query("select * from table where cid=\"$b4[parent]\"");
$c5 = mysql_num_rows($a5);
if($c5 > 0)
{
$b5 = mysql_fetch_array($a5);
}
}
}
}
}

# принтуем названия разделов.
print("каталог > ");
if($b5 != NULL) { print("$b5[name] > "); }
if($b4 != NULL) { print("$b4[name] > "); }
if($b3 != NULL) { print("$b3[name] > "); }
if($b2 != NULL) { print("$b2[name] > "); }
if($b1 != NULL) { print("$b1[name] > "); }
print("$r[name]");

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

 

[SiMM]

Тебе нужна рекурсия - в поиск по форуму - обсуждалось неоднократно.

 

[dorfey]

Да как бы функция у меня уже есть, но толи сервак глючный толи руки кривые.
Функция выглядит так:

$select = mysql_query("select * from table where cid=\"$_GET[cat]\"");
$r = mysql_fetch_array($select);

$uid = $r["parent"];

function tree($uid)
{
GLOBAL $uid;
$a = mysql_query("SELECT * FROM cat_1_cat WHERE cid=\"$uid\"");
while($x = mysql_fetch_array($a))
{
print("$x[name] > ");
tree($x["parent"]);
}
}

Вызываем: tree(0);

Сервак выдает таймаут, скрипт выводит в огромном количестве раздел с id=0

-~{}~ 16.11.04 16:50:

во втором запросе таблица не cat_1_cat а table

 

[Profic]

dorfey
Итить, ты похоже ничему в ирке так и не научился?

Ну скажи накой черт тебе тут сдалась рекурсия?

function PathToCurNode ($id, $delim = ' > ') {
    $path = array ();
    do {
        $res = mysql_query ('SELECT parentid, name FROM table WHERE id=' . (int) $id) or die (mysql_error ());
        if (!mysql_num_rows ($res)) break;
        $row = mysql_fetch_array ($res)
        $path[] = $row['name'];
        $id = $row['parentid']
    } while (true);
    return implode ($delim, array_reverse ($path));
}

Вызывать ее так:

echo PathToCurNode ($curid);
// $curid - идентификатор ТЕКУЩЕГО узла, а не корневого

ЗЫ. Это код не специально для тебя, а как пример, чтобы потом можно было в поиск посылать

ЗЫЫ. Последняя модификащия уже не предполагает, что корневой узел должен быть с номером id = 0

 

[dorfey]

Profic
Ответ почему я выбрал рекурсию:
Взгляни на мой код и на свой, чей легче воспринимается???
Люди помогите доделать мою рекурсию, может кто знает почему возникает проблема с моим вариантом???

 

[Profic]

dorfey
Тебе еще рано для рекурсии. Ты ее не понимаешь. И не понимаешь где она реально нужна, а где нафиг не сдалась и даже вредна. Любой рекурсивный алгоритм, можно заменить на аналогичный, но итеративный. Вопрос только в производительности и понятности. Вот это как раз твой случай.
Кстати твоя задача называется "вывод строки навигации" или "вывод пути в дереве от корня до текущей ветки". Тут никакая рекурсия не нужна.
Мой код более прозрачный для понимания, чем твой, который к тому же содержит кучу ошибок.

Да, кстати ты все таки определись, что тебе нужно. А то все же не совсем понятно.
1) Вывести путь до корня от текущей ветки
2) Вывести полностью дерево
3) Вывести путь до корня от текущей ветки и показать ее в развернутом виде
4) Что-то еще?
Приведи лучше пример, наглядный, чтобы было понятно.

 

[dorfey]

Короче мой сайт www.XXX.ru зайди например в XXX и пощелкай по разделам, увидишь про че я говорю. А из твоего списка вариантов я выбираю п.1 ( Вывести путь до корня от текущей ветки)

-~{}~ 16.11.04 18:20:

ИProfic
Подсказал бы какие ошибки нашел!!!

 

[Profic]

dorfey
Ы. Все-таки я был прав.
Ну коли хочешь рекурсию - держи

function PathToCurNode ($id, $delim = ' > ') {
    $res = mysql_query ('SELECT parentid,name FROM table WHERE id=' . (int) $id) or die (mysql_error ());
    if (!mysql_num_rows ()) return false;
    $row = mysql_fetch_array ($res);
    if (PathToCurNode ($row['parent'])) echo $delim;
    echo $row['name'];
    return true;
}

А теперь скажи - что, это намного понятнее, чем итеративный алгоритм?

ЗЫ. Вызывать так же как итеративный

 

[dorfey]

Profic

Тут я быстрее сорентировался.

Наконец получилось. Огромное спасибо.
Осталось два маленьких вопросика.
1.

<?
$res = mysql_query ('SELECT parentid,name FROM table WHERE id=' . (int) $id)
?>

не совсем понял что такое . (int) ???

2. Если я правельно понял, то при использовании рекурсивного алгоритма я буду терять скорость работы скрипта??? Если я прав то насколько это будет заметно.

 

[SiMM]

1. Преобразование в целое
2. Возьми да сравни два алгоритма [m]microtime[/m]. Только сравнивать желательно на больших объёмах данных и исключив возможность кэширования. Хотя в данном случае экономия если и будет, то имхо, на спичках.
PS: в следующий раз задавай вопросы так, чтобы они были понятны даже тем, кто не общался с тобой в ирке на тему заданного вопроса.

 

[dorfey]

SiMM
Спасибо за подсказку (п.1)

Протестить на больших объемах данных очень проблематично, максимум на сайте крутится порядка 80 разделов, которые при этом имеют не более 3-4 вложений от корневого раздела. Такое количесво записей в таблице просто смешно использовать для тестинга.

По поводу обсуждения вопросов, которые рание обсуждались в ирке. Если посмотришь весь пост, то видно что он грамотно построен. Были заданы популярные вопросы и даны очень грамотные ответы (огромный респект Profic'у).

-~{}~ 17.11.04 10:06:

Profic
Ты был прав, итеративный алгоритм гораздо проще. С утра как то проще было с этим разобраться, поэтому признаю что был не прав. Рекурсия действительно мне не нужна. Только теперь появился вопрос. В каких случаях надо применять рекурсию а когда итерацию??? Ведь на моем примере оба варианта дают одинаковый результат.

 

[SiMM]

dorfey, если ты не понял - я про твой первый пост - всё там описанное можно было изложить гораздо короче и понятней - достаточно было сказать про вывод навигатора.

 

[dorfey]

SiMM
Да вроде как знаниями ты тоже особо не блеснул, ответив избитой фразой:
в поиск по форуму - обсуждалось неоднократно.
При этом ты отправил меня искать рекурсию, а я о ней даже не спрашивал.
А спросить про навигатор я действительно не догадался, моя ошибка, признаю.

 

[Profic]

dorfey
Рекурсия нужна там, где данные и/или алгоритм сами по себе имеют рекурсионное описание, и их реализация в итеративной форме будет корявой и тормозной. Вот например если вы тебе нужно было вывести всё дерево целиком - то тут как раз рекурсия к месту. Вывести тоже самое итеративно можно, но это будет один большой глюк
Но твоя задача - идеально решается с помощью итеративного алгоритма. (К тому же хотел сделать как в первом варианте, с возвратом строки, но сам запутался (!) и решил сделать просто с выводом).
Однако не следует увидев рекурсионное описание данных/алгоритма кидаться писать его соответсвенно. Очень часто рекурсионный алгоритм сводится к итерации с вводом нескольких дополнительных переменных Например, факториал очень легко и просто ищется с помощью итерации. Так же как и числа Фибоначи.
В общем написать про это можно много и я советую тебе почитать книжку Вирта "Алгоритмы и структуры данных". Там про много чего написано, в том числе и про итерацию/рекурсию