Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Господа, будьте снисходительны, не бросайтесь сразу штрафовать за, как вам кажется, глупые вопросы - beginners на то и beginners.
| | | |
Хорошо, более наглядный пример такой организации дерева в файле 19.09.03 14:17 Число просмотров: 1310
Автор: amirul <Serge> Статус: The Elderman
Отредактировано 19.09.03 14:18 Количество правок: 1
|
Экспортированный файл реестра (хотя не совсем такой же, потому как там нет длины для быстрого пропуска ветки)
Хотя можно добавить возможность прохода по дереву и к приведенному whiletrue метода, если использовать в качестве ID ноды использовать смещение в файле, а для каждой ноды, имеющей детей сохранять офсеты всех детей (или офсет на список детей - кому как нравится), тогда и восстанавливать дерево будет легче. Насколько я помню, реестр физически хранится именно так (да и файловые системы тоже примерно так).
ЗЫ: Вот сейчас подумал, второй вариант мне нравится больше - легче добавлять удалять детей без перетаскивания больших кусков файла.
|
|
<beginners>
|
как сохраняют дерево на диске ? 19.09.03 11:24
Автор: tdes <jin> Статус: Member
|
Предположим у меня есть (в памяти ) дерево ( в примитивном случае бинарное), полученное в результате работы некого алгоритма. Я хочу сохранить это дерево в файл, чтоб следующий раз не строить его, а просто загрузить в память с диска. Вопрос, как это сделать, при условии что “глубина” дерева не известна ?
10x
|
|
А что, XML плохо подходит? 19.09.03 15:09
Автор: Ktirf <Æ Rusakov> Статус: Elderman
|
|
|
| |
можно подробнее про связь с XML ? 19.09.03 19:54
Автор: tdes <jin> Статус: Member
|
|
|
| | |
Даже не знаю. 19.09.03 20:06
Автор: Ktirf <Æ Rusakov> Статус: Elderman
Отредактировано 19.09.03 20:08 Количество правок: 1
|
Что тут подробнее-то :) Алгоритм сохранения - как whiletrue описал. Конкретную форму выбираешь сам, можно, например, такой:
<node id="456">
<node id="789">
<![CDATA[здесь идут данные ребенка]]>
</node>
<![CDATA[здесь идут данные]]>
</node>
---
Когда нужно восстановить дерево, берешь первый попавшийся под руку XML-парсер, навешиваешь на него свои обработчики (их у тебя будет ровно два, если я не ошибаюсь) и разбираешь этот XML.
|
| | | |
но если учесть что в ХМЛ 19.09.03 20:15
Автор: tdes <jin> Статус: Member
|
не могут быть вложены однотипные ноды, то есть некоторые проблемы.
и, imho, лучше уже использовать SQL, так как не надо будет заботится о порядке сохранения нодов
|
| | | | |
Почему это в XML не могут быть сохранены однотипные ноды??? 19.09.03 20:39
Автор: Ktirf <Æ Rusakov> Статус: Elderman
Отредактировано 19.09.03 20:41 Количество правок: 1
|
<root>
<node id="1">
<![CDATA[Вот один]]>
</node>
<node id="2">
<![CDATA[Вот второй]]>
<node id="3">
<![CDATA[Или я чего-то не понимаю?]]>
</node>
</node>
</root>
---
А нужный порядок сохранения нетрудно обеспечить обходом вглубь.
|
| | | | | |
да, погорячился я )) 20.09.03 10:29
Автор: tdes <jin> Статус: Member
|
|
|
|
как сохраняют дерево на диске ? 19.09.03 11:28
Автор: whiletrue <Роман> Статус: Elderman
|
> Предположим у меня есть (в памяти ) дерево ( в примитивном
> случае бинарное), полученное в результате работы некого
> алгоритма. Я хочу сохранить это дерево в файл, чтоб
> следующий раз не строить его, а просто загрузить в память с
> диска. Вопрос, как это сделать, при условии что “глубина”
> дерева не известна ?
> 10x
Пробегаешь рекурсией по дереву и сохраняешь следущее:
ID | Сами данные | ID_Родителя
При восстановлении:
Пробегаешь по этому списку. Смотришь на ID_Родителя - туда и пихаешь.
|
| |
И еще 19.09.03 13:06
Автор: amirul <Serge> Статус: The Elderman
|
> Пробегаешь рекурсией по дереву и сохраняешь следущее:
> ID | Сами данные | ID_Родителя
>
> При восстановлении:
> Пробегаешь по этому списку. Смотришь на ID_Родителя - туда
> и пихаешь.
Для удобства навигации чаще всего его организовывают в виде chunk-ов, в которых содержится вся ветка (вместе со всеми потомками) и длина.
Можешь посмотреть документацию по мультимедийным форматам RIFF и IFF. Причем последний используется для хранения чуть ли не любых документов (рисунки, музыка, 3d-сцены, документы текстового процессора и т.п.) на платформе Amiga. А RIFF в свою очередь в видне используется для wav и avi файлов.
Так вот в простейшем случае разбитый на chunk-и файл выглядит так:
{chunk_id_1, chunk_len_1, { {chunk_id_2, chunk_len_2, {data2}} {chunk_id_3, chunk_len_3, {data3}} } data1}
Длина данных в листьях может быть нулевой, если важно само его наличие. Причем длина показывает длину ВСЕГО чанка вместе с потомками. Поле ID используется например для различия между разными нодами (например, ветвится ли дальше или является листом).
Для того, чтобы понять, как ЭТО сохранить на диск (самое интересное это как сохранить длины) рекомендую посмотреть интерфейс для работы с RIFF-файлами (mmioXxx - функции). Но вкратце это выглядит как работа с файловой системой: зашел в каталог (chunk), создал подкаталог, вошел в него, создал еще чего то... И т.д. А длина записываются при выходе из каталога (chunk-а).
Такая организация дает преимущество в том, что возможно свободное хождение по дереву и поиск нужной ветки без считывания всего дерева в память.
|
| | |
Тяжеловаты они (форматы эти), имхо... 19.09.03 13:53
Автор: HandleX <Александр М.> Статус: The Elderman
|
|
|
| | | |
Хорошо, более наглядный пример такой организации дерева в файле 19.09.03 14:17
Автор: amirul <Serge> Статус: The Elderman
Отредактировано 19.09.03 14:18 Количество правок: 1
|
Экспортированный файл реестра (хотя не совсем такой же, потому как там нет длины для быстрого пропуска ветки)
Хотя можно добавить возможность прохода по дереву и к приведенному whiletrue метода, если использовать в качестве ID ноды использовать смещение в файле, а для каждой ноды, имеющей детей сохранять офсеты всех детей (или офсет на список детей - кому как нравится), тогда и восстанавливать дерево будет легче. Насколько я помню, реестр физически хранится именно так (да и файловые системы тоже примерно так).
ЗЫ: Вот сейчас подумал, второй вариант мне нравится больше - легче добавлять удалять детей без перетаскивания больших кусков файла.
|
| |
угу, логично, наверное надо бросать пить ))) 19.09.03 11:40
Автор: tdes <jin> Статус: Member
|
|
|
|
|
подробно о проекте
Анализ криптографических сетевых...
