Здравствуйте, Vlads, Вы писали:
V>Народ подскажите как лучше построить дерево, которое бы представляло дерево файлов и директорий. Соответственно эту структуру необходимо сохранять и сравнивать с другим деревом — в результате необходимо описать отличия двух деревьев (перемещен файл, удален и т.д.). Может кто решал похожую задачу?
Ну, собственно, дерево — оно и в африке дерево...
В твоей задаче оно будет с неизвестным заранее числом вершин, поэтому тут просто
придется динамически выделять память под каждый его элемент...Т.е. в зависимости от результата
работы функции FindNext(...) добавляешь либо в список файлов, либо в список папок....
Это можно реализовать как рекурсивно, так и нет...Имхо, стоит итеративно(очередь закольцевать можно),
впрочем, не об этом речь..
Например, вот так это всё будет записано с помощью std::list....
class File
// а может класс и не нужен - там сам решишь....
{ ... };
class Folder
{
private:
// тут храним файлы и папки, которые находятся в текущей папке,
// все в виде указателей, естсно....
std::list < Folder* > LFolder;
std::list < File* > LFile;
// не забываем про предка....
Folder* prev;
// остальная информация о папке, как-то: имя, дата создания,
// атрибуты и т.п...
public:
// добавление тривиально - list.push_[back, front]...
void AddFolder(Folder* F);
void AddFile(Folder* F);
};
class Tree
{
public:
Folder* root;
// мб еще что-нибудь из данных + методы...
};
Хранение дерева этого не представляет какой-либо сверхсложной задачи....
Практически, результат может совпадать с обходом вглубь, разве что надо
при каждом рекурсивном вызове печатать текущую директорию и, соответственно,
предусмотреть выражение(спецстрока/кодовый символ) для перехода на следующий
уровень вложенности и выражение для закрытия очередного уровня вложенности....
Сравнение уже интереснее...Если время не сильно критично — то просто упорно просматриваем
каждую папку в одном дереве и ищем её в другом(на одном уровне вложенности)...Причем стоит
помечать рассмотренные папки, чтобы в конце остались в каждом дереве лишь те, которых нет в
другом...
По этому формируем разность на этом уровне вложенности.
Например, такого вида:
left:
C:\Windows
C:\Test,
что означает отсутствие во втором(правом) дереве и при
сутствие в первом(левом) этих папок...
right:
C:\Winnt
C:\T,
что означает то же самое с точностью до наоборот...
А далее повторяем сие для каждой подпапки, причем остались для рассмотрения
папки, присутствующие и там, и там...
Здравствуйте, Vlads, Вы писали:
V>Народ подскажите как лучше построить дерево, которое бы представляло дерево файлов и директорий. Соответственно эту структуру необходимо сохранять и сравнивать с другим деревом — в результате необходимо описать отличия двух деревьев (перемещен файл, удален и т.д.). Может кто решал похожую задачу?
Сиотри в сторону Б-Деревьев, они специально для файловых структур созданы. Вообще тебе к 2-3-4-деревьям.
... << RSDN@Home 1.1.3 stable >>
Народ подскажите как лучше построить дерево, которое бы представляло дерево файлов и директорий. Соответственно эту структуру необходимо сохранять и сравнивать с другим деревом — в результате необходимо описать отличия двух деревьев (перемещен файл, удален и т.д.). Может кто решал похожую задачу?
Здравствуйте, Vlads, Вы писали:
V>Народ подскажите как лучше построить дерево, которое бы представляло дерево файлов и директорий. Соответственно эту структуру необходимо сохранять и сравнивать с другим деревом — в результате необходимо описать отличия двух деревьев (перемещен файл, удален и т.д.). Может кто решал похожую задачу?
Так это ж edit distance, только для деревьев
Несколько алгоритмов описано, например,
здесь.
... << RSDN@Home 1.1.4 beta 5 rev. 395>>