Рекурсивный массив

[solovin1986]

Есть база

id|parentid|posi|name
 1|———--0|--—0|Россия
 2|———--1|--—0|Центр
 3|———--2|—--0|Москва и область
 4|———--3|—--0|Москва
 5|———--3|--—1|Долгопрудный
 6|———--3|—--0|Дубна
 7|———--0|—--0|Украина

Есть код

function get_region_arr($parentid = 0) {
	global $db;
	$db->query("SELECT * FROM " . PREFIX . "_region WHERE parentid = '$parentid' ORDER BY parentid, posi ASC");
	while ( $row = $db->get_row() ) {
		$arr[$row['id']] = $row['name'];
	}
	return $arr;
}

print '<pre>'. print_r(get_region_arr(), true) . '</pre>';

Результат

Array
(
    [1] => Россия
    [7] => Украина
)

КАК СОЗДАТЬ РЕКУРСИВНЫЙ МАССИВ.

ПОМОГИТЕ ПЛУЖУ УЖЕ ВТОРОЙ ДЕНЬ

[Veseloff]

Что такое рекурсивный массив? Какой результат нужен?

[Searcher]

Рекурсия это процесс а не свойство. Не понятно что вы имеете ввиду под рекурсивным массивом... Что должно то быть на выходе вашей функции?

[solovin1986]

Если посмотреть на запись в базе а именно на parentid то видно что это толе ссылаются на id.

И получается что нужно сформировать древовидный массив.

[Veseloff]

Если посмотреть на запись в базе а именно на parentid то видно что это толе ссылаются на id.

И получается что нужно сформировать древовидный массив.

Ну вот уже другое дело. Поле id — auto_increment?

[solovin1986]

Если посмотреть на запись в базе а именно на parentid то видно что это толе ссылаются на id.

И получается что нужно сформировать древовидный массив.

Ну вот уже другое дело. Поле id — auto_increment?

Да

[Veseloff]

Тогда делаем запрос

SELECT * FROM `tablename` ORDER BY `parent` ASC, `id` ASC

Собираем все данные в массив по порядку. Создаём новый массив, в котором будем делать дерево. Далее циклом foreach проходимся по первому массиву и ссылками создаём дерево во втором массиве. Задача решается линейно, никак не рекурсией. Я такую задачу на собеседования даю

[solovin1986]

Тогда делаем запрос

SELECT * FROM `tablename` ORDER BY `parent` ASC, `id` ASC

Собираем все данные в массив по порядку. Создаём новый массив, в котором будем делать дерево. Далее циклом foreach проходимся по первому массиву и ссылками создаём дерево во втором массиве. Задача решается линейно, никак не рекурсией. Я такую задачу на собеседования даю

Если вы внимательно смотрели на таблицу есть рекурсия в 3 вложения. А если представить на минутку что веток будет более 10.

Edited June 23, 2011 by solovin1986

[solovin1986]

Так что такие вот дела

[Searcher]

Рекурсия - вызов функцией саму себя. У вас для дерева нужен многомерный массив. И индексами будет не id, а parentid

[solovin1986]

Кто то может показать как?

[Veseloff]

Я показывать не буду и другим не советую. Это очень интересное задание и, если топикстартер поймёт как это делается, то это добавит ему стопицот к скиллу программиста. Как это делается я уже достаточно подробно объяснил. Можно, конечно, сразу заполнять дерево, но в два массива будет нагляднее. Подчерку ещё раз, что заполнять надо ссылками.

[solovin1986]

Я показывать не буду и другим не советую. Это очень интересное задание и, если топикстартер поймёт как это делается, то это добавит ему стопицот к скиллу программиста. Как это делается я уже достаточно подробно объяснил. Можно, конечно, сразу заполнять дерево, но в два массива будет нагляднее. Подчерку ещё раз, что заполнять надо ссылками.

Я конечно прошу прощения но ваше сообщение наводит на одну мысль.

[Veseloff]

Я конечно прошу прощения но ваше сообщение наводит на одну мысль.

И на какую же, если не секрет?

[solovin1986]

Просто "влом" показать.

[Veseloff]

Отнюдь. Просто сейчас качество программистов падает, а так быть не должно. Чтобы так не было, надо учиться. Давайте так — вы сделаете свой вариант, а потом я покажу как бы сделал я.

[solovin1986]

Отнюдь. Просто сейчас качество программистов падает, а так быть не должно. Чтобы так не было, надо учиться. Давайте так — вы сделаете свой вариант, а потом я покажу как бы сделал я.

Хотите выиграть во времени? )

[Veseloff]

Хотите выиграть во времени? )

Ахахах! Вы бы ещё сказали, что я время тяну, чтобы сделать сортировку пузырьком. Я практически такую же задачу даю на собеседовании, так что решение у меня точно есть. Вот, например, от одного из претендентов решение задачи на питоне — не самое лучшее, но рабочее

?

import MySQLdb
db = MySQLdb.Connect(host="localhost",user="username",passwd="password",db="TOAST")
cursor = db.cursor()

baseQuery = "SELECT * FROM comments WHERE PARENT = "


def getChildren(currentID):

    query = baseQuery + str(currentID) + ";"
    found = cursor.execute(query)

    if found == 0 : return None

    currentLevelComments = {}

    results = cursor.fetchall()
    for i in range(len(results)):

        currentComment = results[i]
        currentCommentID = currentComment[0]
        currentCommentParent = currentComment[1]
        currentCommentAuthor = currentComment[2]
        currentCommentText = currentComment[3]

        currentCommentDict = {}
        currentCommentDict["ID"] = currentCommentID
        currentCommentDict["Parent"] = currentCommentParent
        currentCommentDict["Author"] = currentCommentAuthor
        currentCommentDict["Text"] = currentCommentText

        children = getChildren(currentCommentID)

        if children != None:

            currentCommentDict["Children"] = children

        currentLevelComments[currentCommentID] = currentCommentDict

    return currentLevelComments

comments = getChildren(0)

[solovin1986]

Хотите выиграть во времени? )

Ахахах! Вы бы ещё сказали, что я время тяну, чтобы сделать сортировку пузырьком. Я практически такую же задачу даю на собеседовании, так что решение у меня точно есть. Вот, например, от одного из претендентов решение задачи на питоне — не самое лучшее, но рабочее

?

import MySQLdb
db = MySQLdb.Connect(host="localhost",user="username",passwd="password",db="TOAST")
cursor = db.cursor()

baseQuery = "SELECT * FROM comments WHERE PARENT = "


def getChildren(currentID):

    query = baseQuery + str(currentID) + ";"
    found = cursor.execute(query)

    if found == 0 : return None

    currentLevelComments = {}

    results = cursor.fetchall()
    for i in range(len(results)):

        currentComment = results[i]
        currentCommentID = currentComment[0]
        currentCommentParent = currentComment[1]
        currentCommentAuthor = currentComment[2]
        currentCommentText = currentComment[3]

        currentCommentDict = {}
        currentCommentDict["ID"] = currentCommentID
        currentCommentDict["Parent"] = currentCommentParent
        currentCommentDict["Author"] = currentCommentAuthor
        currentCommentDict["Text"] = currentCommentText

        children = getChildren(currentCommentID)

        if children != None:

            currentCommentDict["Children"] = children

        currentLevelComments[currentCommentID] = currentCommentDict

    return currentLevelComments

comments = getChildren(0)

Ладно всем спасибо что смотрели сделаю сам выложу. А то только нравоучения а помощи 0.

[Int]

Двумерного массива будет достаточно

a=1 - элемент a имеет связь весом 1 (в данном случае все веса будет равны 1) с элементом i.

Соответственно нужно делать и i[a]=1. Это если рёбра графа не направленные.

Реализация настолько очевидна, что даже приводить не буду.

У меня, кстати, есть незаконченная игрушка, в которой маршруты по карте строятся именно так. Плюс ещё один двумерный массив заранее рассчитанных маршрутов длиной 2, типа a=i, где маршрут проходит из a в b через i. Это немного сокращает время поиска кратчайшего пути на карте (плюс кэширование найденных маршрутов). Хочу со временем заняться этой игрушкой всерьёз и перенести расчёты клиенту в яваскрипт.

http://ru.wikipedia.org/wiki/%D0%93%D1%80%D0%B0%D1%84_%28%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0%29

[Иван Шумов]

Сто лет не писал, но не могу не вмешаться) "чтобы понять рекурсию - надо понять рекурсию" (с) И это, увы, правда. Самый правильный способ, я считаю - взять листок бумаги и массив с условно бесконечной вложенностью id-parent. И начать расписывать получение элемента из предыдущего. На каком-то шаге просто осенит)

[Int]

Осенит, что рекурсия тут вообще не нужна если использовать массив, как я предложил. Всё зависит от того, какую структуру в итоге нужно получить.Если нужно сохранить возможность пройти по дереву вверх, то мой вариант усложняет эту ситуацию, поскольку придётся осуществлять перебор всех маршрутов, так как в них не указано, какой является маршрутом к родителю. Но можно и указать, изменяя веса рёбер. Например, рёбра весом 2 - это рёбра до родителей. Тогда к началу дерева можно пройти по рёбрам, равным 2.

[solovin1986]

Сейчас доделаю маленький нюанс и покажу экспертам

[s0rr0w]

Пример рекурсивного массива

$a = array();
$a[] = $a;

Edited June 24, 2011 by s0rr0w

[solovin1986]

КОД

function get_region_arr() {
	global $db;
	$db->query("SELECT * FROM " . PREFIX . "_region ORDER BY parentid, posi ASC");
	while ( $row = $db->get_row() ) {
		$arr[$row['parentid']][] = $row;
	}
	return $arr;
}

function  get_region_tree($arr,$parentid){
    foreach($arr[$parentid] as $value){
		$tmp[$value['id']] = get_region_tree($arr, $value['id']);
        $tmp[$value['id']]['name'] = $value['name'];
    }
  return $tmp;
}
print '<pre>' . print_r(get_region_tree(get_region_arr(), 0), true) . '</pre>';

РЕЗУЛЬТАТ

Array
(
    [1] => Array
        (
            [2] => Array
                (
                    [3] => Array
                        (
                            [4] => Array
                                (
                                    [name] => Москва
                                )

                            [6] => Array
                                (
                                    [name] => Дубна 
                                )

                            [5] => Array
                                (
                                    [name] => Долгопрудный
                                )

                            [name] => Москва и область 
                        )

                    [name] => Центр
                )

            [name] => Россия
        )

    [7] => Array
        (
            [name] => Украина
        )

)

Правда есть один нюанс который глаз мусолит, то что ключ [name] не вначале. Не могу его правильно его туда зарядить.

А так работает. Пользуйтесь на здоровье.

[Int]

$names=array(0=>'Корневой элемент',1=>'Россия',2=>'Центр',3=>'Москва и область',4=>'Москва',5=>'Долгопрудный',6=>'Дубна',7=>'Украина');

$a=array();
$a[0][1]=1;
$a[0][7]=1;
$a[1][0]=2;
$a[7][0]=2;

$a[1][2]=1;
$a[2][1]=2;

$a[2][3]=1;
$a[3][2]=2;

$a[4][3]=1;
$a[5][3]=1;
$a[6][3]=1;
$a[3][4]=2;
$a[3][5]=2;
$a[3][6]=2;

Array
(
    [0] => Array
        (
            [1] => 1
            [7] => 1
        )

    [1] => Array
        (
            [0] => 2
            [2] => 1
        )

    [7] => Array
        (
            [0] => 2
        )

    [2] => Array
        (
            [1] => 2
            [3] => 1
        )

    [3] => Array
        (
            [2] => 2
            [4] => 2
            [5] => 2
            [6] => 2
        )

    [4] => Array
        (
            [3] => 1
        )

    [5] => Array
        (
            [3] => 1
        )

    [6] => Array
        (
            [3] => 1
        )

function GetParent($array,$ElemNum)
{
	foreach ($array[$ElemNum] as $neighbour=>$val) if ($val == 2) return $neighbour;
}