Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

Есть дерево. Но не бинарное. :) [Win95/98]

Sat7 © (2002-04-12 11:59:00)
Кто предложит оптимальную древовидную структуру для хранения (извиняюсь за каламбур) структуры директорий на винте и их поиска?
Задачка сводится к следующему: спроектировать класс, который хранит в себе структуру каталогов винта и функции их поиска. Единственное условие - поиск нужной директории в структуре должен идти рекурсивно. Я все-таки склоняюсь к связному списку, но здесь есть некоторые трудности. У бинарного дерева две ветки - правая и левая, по нему легко пройтись рекурсией. А обход дерева каталогов...
Подскажите, если кто-то имел с этим дело.

Бурундук (2002-04-12 14:21:00) [1]
Любое дерево можно преобразовать в бинарное.
Собственно, в таком виде, как это предлагает vovochka ©
оно уже бинарное
(От каждого узла дерева отходят две ветки - FirstChild и Next).

vovochka (2002-04-12 14:19:00) [2]
Ля, это просто список типа "радост первокурсника"! Обходишь все узлы по рекурсии и всё!

будет что-то типа:

function Calc(n:TNode):integer;
var
pc:TNode;
begin
result:=0;
pc:=n.FirstChild;
while pc<>nil do
begin
result:=result+pc.value;
if pc.FirstChild<>nil then result:=result+Calc(pc);
pc:=pc.next;
end;
//По моему всё должно работать.
end;

Так надо или мы друг друга непонимаем?

Sat7 (2002-04-12 14:01:00) [3]
vovochka © (12.04.02 13:28)

Давай более общий случай рассмотрим. Представь, что тебе нужно сначала заполнить дерево, а потом посчитать сумму в узлах дерева, обойти все эти узлы. Но не обычного дерева - "Радость первокурсника", а дерева, у которого из одного узла отходит не две ветки, а заранее неизвестно сколько. Получается, что у нас есть: деревце, в узлах которого находятся значения, общую сумму которых нужно посчитать, и, собственно, узлы, из которых отходит несколько веток. Сколько веток будет - до заполнения не знаешь. Как ты станешь делать заполнение и обход узлов (подсчет суммы)?

vovochka (2002-04-12 13:28:00) [4]
2Sat7

Чёто я тебя совсем непонимаю.
По-моему это один из самых лучших вариантов. Что-то типа однонаправленного графа.
Где будут тормоза: при создании, поиске или где?

Игорь Шевченко (2002-04-12 12:58:00) [5]
День добрый,

А TStringList не подходит, у которого в Objects для каждого каталога находится аналогичный TStringList с подкаталогами и так далее... ?

С уважением,

Sat7 (2002-04-12 12:45:00) [6]
vovochka © (12.04.02 12:36)

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

vovochka (2002-04-12 12:36:00) [7]
А где были тормоза?
HASH пробывал?

Sat7 (2002-04-12 12:29:00) [8]
vovochka © (12.04.02 12:17)

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

vovochka (2002-04-12 12:17:00) [9]
TNode = record
Parent:TNode;
prev,next:TNode;
FirstChild,LastChild:TNode;

......

end;
У?

Бурундук (2002-04-12 12:17:00) [10]
А почему всё-таки не бинарное? (firstchild, nextbrother)

Alx2 (2002-04-12 12:12:00) [11]
Связный список веток в глубину. мультидерево такое вот.

Виктор Щербаков (2002-04-12 12:12:00) [12]
Может поможет:
http://algolist.manual.ru/ds/index.php

Anatoly Podgoretsky (2002-04-12 12:09:00) [13]
Используй двухсвязный список, поля prev, next можешь назвать right, left

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »