Форум: "Основная";
Поиск по всему сайту: delphimaster.net;
Текущий архив: 2002.04.25;
Скачать: [xml.tar.bz2];




Вниз

Есть дерево. Но не бинарное. :) 


Sat7   (2002-04-12 11:59) [0]

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



Anatoly Podgoretsky   (2002-04-12 12:09) [1]

Используй двухсвязный список, поля prev, next можешь назвать right, left



Alx2   (2002-04-12 12:12) [2]

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



Виктор Щербаков   (2002-04-12 12:12) [3]

Может поможет:
http://algolist.manual.ru/ds/index.php



vovochka   (2002-04-12 12:17) [4]

TNode = record
Parent:TNode;
prev,next:TNode;
FirstChild,LastChild:TNode;

......

end;
У?



Бурундук   (2002-04-12 12:17) [5]

А почему всё-таки не бинарное? (firstchild, nextbrother)



Sat7   (2002-04-12 12:29) [6]

vovochka © (12.04.02 12:17)

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



vovochka   (2002-04-12 12:36) [7]

А где были тормоза?
HASH пробывал?



Sat7   (2002-04-12 12:45) [8]

vovochka © (12.04.02 12:36)

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



Игорь Шевченко   (2002-04-12 12:58) [9]

День добрый,

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

С уважением,



vovochka   (2002-04-12 13:28) [10]

2Sat7

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



Sat7   (2002-04-12 14:01) [11]

vovochka © (12.04.02 13:28)

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



vovochka   (2002-04-12 14:19) [12]

Ля, это просто список типа "радост первокурсника"! Обходишь все узлы по рекурсии и всё!

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

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;

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



Бурундук   (2002-04-12 14:21) [13]

Любое дерево можно преобразовать в бинарное.
Собственно, в таком виде, как это предлагает vovochka ©
оно уже бинарное
(От каждого узла дерева отходят две ветки - FirstChild и Next).




Форум: "Основная";
Поиск по всему сайту: delphimaster.net;
Текущий архив: 2002.04.25;
Скачать: [xml.tar.bz2];




Наверх





Память: 0.74 MB
Время: 0.029 c
3-80805           B_A_V                 2002-04-03 17:33  2002.04.25  
Использую в таблице тип money, datetime


4-81110           SerVS - S             2002-02-18 20:01  2002.04.25  
Подскажите плз как вырубить Ctrl+Alt+Del


3-80743           Shaman                2002-04-04 00:24  2002.04.25  
Вопрос к знатокам InterBase


7-81100           Alex622               2002-01-29 11:46  2002.04.25  
Две мыши


3-80803           trever                2002-04-05 10:22  2002.04.25  
Помогите советом, пожалуйста!