Навигация
Главная
Поиск
Форум
FAQ's
Ссылки
Карта сайта
Чат программистов

Статьи
-Delphi
-C/C++
-Turbo Pascal
-Assembler
-Java/JS
-PHP
-Perl
-DHTML
-Prolog
-GPSS
-Сайтостроительство
-CMS: PHP Fusion
-Инвестирование

Файлы
-Для программистов
-Компонеты для Delphi
-Исходники на Delphi
-Исходники на C/C++
-Книги по Delphi
-Книги по С/С++
-Книги по JAVA/JS
-Книги по Basic/VB/.NET
-Книги по PHP/MySQL
-Книги по Assembler
-PHP Fusion MOD'ы
-by Kest
Professional Download System
Реклама
Услуги

Автоматическое добавление статей на сайты на Wordpress, Joomla, DLE
Заказать продвижение сайта
Программа для рисования блок-схем
Инженерный калькулятор онлайн
Таблица сложения онлайн
Популярные статьи
OpenGL и Delphi... 65535
Форум на вашем ... 65535
HACK F.A.Q 65535
Бип из системно... 65535
Гостевая книга ... 65535
Invision Power ... 65535
Содержание сайт... 65535
Вызов хранимых ... 65535
Программируемая... 65535
Эмулятор микроп... 65535
Подключение Mic... 65535
Создание потоко... 65535
Приложение «Про... 65535
Оператор выбора... 65535
Организация зап... 65184
Создание отчето... 61658
Модуль Forms 61565
ТЕХНОЛОГИИ ДОСТ... 58136
Пример работы с... 55741
Имитационное мо... 53466
Реклама
Сейчас на сайте
Гостей: 6
На сайте нет зарегистрированных пользователей

Пользователей: 13,069
новичок: momotw
Новости
Реклама
Выполняем курсовые и лабораторные по разным языкам программирования
Подробнее - курсовые и лабораторные на заказ
Delphi, Turbo Pascal, Assembler, C, C++, C#, Visual Basic, Java, GPSS, Prolog, 3D MAX, Компас 3D
Заказать программу для Windows Mobile, Symbian

Калькулятор на Delphi с переводом в другую систему исчисления + Блок схемы
Информационная система - транспортный парк на Turbo Pascal (База данных)...
Диплом RSA, ЭЦП, сертификаты, шифрование на C#

Реклама



Подписывайся на YouTube канал о программировании, что бы не пропустить новые видео!

ПОДПИСЫВАЙСЯ на канал о программировании
Работа с MySQL. Деревья
Оригинал статьи находится по адресу:
http://detail.phpclub.net/2002-06-03.htm

Необходимость вывода данных структурированных в форме деревьев возникает при написании собственного форума или каталога сайтов. Готовых каталогов и форумов в сети можно найти предостаточно, однако иногда чужое в готовом не годится, а переделывать написанное другим займёт гораздо больше времени, чем написать своё.

Структуру данных лучше взять общепринятую - в записи сообщения или рубрики форума содержится идентификатор родителя. Для организации вывода дерева напрашивается рекурсивная функция. Именно так сделано в Phorum'е [http://phorum.org]. Файл include/multi-threads.php содержит функцию thread, которая строит вызывается для каждого корневого сообщения и рекурсивно вызывает себя для ответов на них:
function thread ($seed = 0) {
...

if(@is_array($messages[$seed]["replies"])) {
$count = count($messages[$seed]["replies"]);
for($x = 1;$ x <= $count; $x++) {
$key = key($messages[$seed]["replies"]);
thread ($key);
next ($messages[$seed]["replies"]);
}
}
}

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

Для построения дерева достаточно знать последовательность вывода рубрик и их уровень в дереве. Добавим два поля с этими данными в таблицу: level (TINYINT(4). 127 уровней - хватит?) и sortorder (VARCHAR(128)).

Всё, что нам нужно для построения дерева - это идентификатор рубрики и её родителя. Допустим, мы имеем в каталоге несколько рубрик такого содержания:
---------
id parent
---------
3 0
5 0
7 0
10 3
11 7
12 5
13 3
16 10
21 16
26 11
30 3
47 7
60 10
73 13
75 47
---------

Структура дерева, подобие которой мы хотим получить такова:
o- 3
|
+-o- 10
| |
| +-o- 16
| | |
| | +-o- 21
| |
| +-o- 60
|
+-o- 13
| |
| +-o- 73
|
+-o- 30

o- 5
|
+-o- 12

o- 7
|
+-o- 11
| |
| +-o- 26
|
+-o- 47
|
+-o- 75

Правда, данный алгоритм позволит нарисовать дерево, но без веток виде линий, как сделано на этом рисунке. Структура дерева будет нарисована при помощи отступов слева.

Вернёмся ещё раз к таблице id-parent. Это рубрики, уже отсортированные по некоторому признаку, по которому мы хотим сортировать элементы одинакового уровня. Например, по убыванию числа сайтов. Кроме id и родительской рубрики мы знаем и номер каждой из них в данном списке. Выровняем эти номера до нужной длины, добавив слева нули. После этого для каждой рубрики сделаем текстовую строку с номерами всех её родителей от самого корня:
------------------------------
id sort parent sortorder level
------------------------------
3 1 0 01 0
5 2 0 02 0
7 3 0 03 0
10 4 3 0104 1
11 5 7 0305 1
12 6 5 0206 1
13 7 3 0107 1
16 8 10 010408 2
21 9 16 01040809 3
26 10 11 030510 2
30 11 3 0111 1
47 12 7 0312 1
60 13 10 010413 2
73 14 13 010714 2
75 15 47 031215 2
------------------------------

При сортировке по полю sortorder мы получим именно то, что нам нужно:
------------------------------
id sort parent sortorder level
------------------------------
3 1 0 01 0
10 4 3 0104 1
16 8 10 010408 2
21 9 16 01040809 3
60 13 10 010413 2
13 7 3 0107 1
73 14 13 010714 2
30 11 3 0111 1
5 2 0 02 0
12 6 5 0206 1
7 3 0 03 0
11 5 7 0305 1
26 10 11 030510 2
47 12 7 0312 1
75 15 47 031215 2
------------------------------

Отступ слева делается, учитывая поле level.

Важно так же отметить, что нам не нужно ничего сортировать в самом скрипте. Для формирования полей sortorder и level нужно заблокировать таблицу от записи (чтобы не произошло изменения структуры веток), выбрать из базы идентификатор рубрики и её родителя, отсортировав по нужному признаку, и записать их в простой двухмерный массив. Затем обработать массив последовательно от первого до последнего уровня и записать поля sortorder и level в таблицу.

Для формирования sortorder не нужно рекурсии (хотя можно, и, вероятно, она работать будет даже быстрее). Достаточно пройтись по массиву одним и тем же циклом. В нём, если рубрика не обработана, для неё формируется поле sortorder из поля sort и родительского sortorder. Если родительская рубрика ещё не обработана, поднимается флаг $unprocessed_rows_exist и цикл запускается ещё раз.
mysql_query("LOCK TABLES dir WRITE");

$result = mysql_query("SELECT id, IFNULL(parent,0) as parent \
FROM dir ORDER BY sites DESC, title");

while ($row = mysql_fetch_array($result)) {
$count++;
$data["parent"][$row["id"]] = $row["parent"];
$data["sort"][$row["id"]] = $count;
}

reset($data);

$unprocessed_rows_exist = true;
while($unprocessed_rows_exist) {
$unprocessed_rows_exist = false;
while (list($i, $v) = each($data["parent"])) {
if(($data["parent"][$i] == 0 || !isset($data["sort"][$data["parent"][$i]])) &&
!isset($data["sortorder"][$i])) {
$data["sortorder"][$i] = str_pad($data["sort"][$i], $max,
"0", STR_PAD_LEFT);
$data["level"][$i] = 0;
}
elseif(!isset($data["sortorder"][$i]) &&
isset($data["sortorder"][$data["parent"][$i]])) {
$data["sortorder"][$i] = $data["sortorder"][$data["parent"][$i]].
str_pad($data["sort"][$i], $max, "0", STR_PAD_LEFT);
$data["level"][$i] = $data["level"][$data["parent"][$i]] + 1;
}
elseif(!isset($data["sortorder"][$i]) &&
isset($data["sort"][$data["parent"][$i]])) {
$unprocessed_rows_exist = true;
}
}

reset($data);

Отмечу, что данный алгоритм не зацикливается при наличии строк с битым полем parent и не пропускает их, а делает корневыми. Рекурсивный алгоритм их просто пропустит.

После выполнения этого цикла мы имеем массивы "id => level" и "id => sortorder". Отправляем в базу всего один запрос, пользуясь внутренними функциями MySQL ELT и FIND_IN_SET:
mysql_query("UPDATE dir SET sortorder=ELT(FIND_IN_SET(id,'".
implode(",", array_keys($data["sortorder"])).
"'),". implode(",", $data["sortorder"]).
"), level=ELT(FIND_IN_SET(id,'".
implode(",", array_keys($data["level"])).
"'),". implode(",", $data["level"]).
") WHERE id IN (".
implode(",", array_keys($data["sortorder"])).
")");

Конечно же, в отличие от дерева рубрик каталога, в большом форуме много сообщений. Передёргивать их всех при добавлении одного нового нет смысла.

В форумах чаще всего используется сортировка по дате написания сообщения. Поэтому поле sortorder можно смело делать из своего и родительского timestamp'а, выровненного функцией str_pad [http://www.php.net/manual/en/function.str-pad.php] до 11-значной длины.
Опубликовал Kest November 02 2008 17:27:08 · 0 Комментариев · 7154 Прочтений · Для печати

• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •


Комментарии
Нет комментариев.
Добавить комментарий
Имя:



smiley smiley smiley smiley smiley smiley smiley smiley smiley
Запретить смайлики в комментариях

Введите проверочный код:* =
Рейтинги
Рейтинг доступен только для пользователей.

Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.

Нет данных для оценки.
Гость
Имя

Пароль



Вы не зарегистрированны?
Нажмите здесь для регистрации.

Забыли пароль?
Запросите новый здесь.
Поделиться ссылкой
Фолловь меня в Твиттере! • Смотрите канал о путешествияхКак приготовить мидии в тайланде?
Загрузки
Новые загрузки
iChat v.7.0 Final...
iComm v.6.1 - выв...
Visual Studio 200...
CodeGear RAD Stud...
Шаблон для новост...

Случайные загрузки
Averaging [Исходн...
Borland Delphi 8 ...
ScrollCredit
Программирование ...
База Allsubmitter...
Работа с матрицами
Error mod
Запрет гостям ск...
Delphi. Разработк...
Ics
TrayComp
THttpScan v4.1
DragMe [Исходник ...
Измерение тактово...
Развивающийся фла...
Игра PackMan
LaserTank [Исходн...
GPSS World Studen...
Динамические за...
AboutSystem

Топ загрузок
Приложение Клие... 100397
Delphi 7 Enterp... 83968
Converter AMR<-... 20052
GPSS World Stud... 11465
Borland C++Buil... 11291
Borland Delphi ... 8236
Turbo Pascal fo... 6993
Visual Studio 2... 4974
Калькулятор [Ис... 4489
FreeSMS v1.3.1 3517
Случайные статьи
Здесь в первом слу...
Звуковая карта
Рекурсивное вычисл...
Математические выводы
Импортирование инф...
Управление трафико...
Метод обобщённого ...
Где мы находимся?
Триггеры проверки
Виртуализация внеш...
tld и engineering,...
4. Как изменить ср...
Функция MAXAVAIL. ...
Режим Ночной портр...
Создание поставщик...
Сообщения протокол...
Универсальный шлюз...
Глава 13. Страт...
Шаблоны и дружеств...
Анализ посещаемост...
Упражнение 2: прое...
Управление надстро...
Виджеты на основе ...
"=" expected
Моделирование аэро...
Статистика



Друзья сайта
Программы, игры


Полезно
В какую объединенную сеть входит классовая сеть? Суммирование маршрутов Занимают ли таблицы память маршрутизатора?