Модераторы: Daevaorn
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Запись и чтение двоичного дерева в файл 
:(
    Опции темы
Бармалей
Дата 5.9.2003, 11:32 (ссылка)    |    (голосов: 0) Загрузка ... Загрузка ... Быстрая цитата Цитата


Unregistered











Совственно вопрос изложен в теме как енто провернуть Заранее благодарен
  Вверх
Baa
Дата 5.9.2003, 11:40 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Экс. модератор
Сообщений: 2639
Регистрация: 12.4.2002
Где: Москва

Репутация: 8
Всего: 12



А в чем проблема?


--------------------
"Duty is everything; the greatest of joys, the deepest of sorrows" Aribeth de Tylmarande
PM ICQ   Вверх
mr.DUDA
Дата 5.9.2003, 11:40 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


3D-маньяк
****


Профиль
Группа: Экс. модератор
Сообщений: 8244
Регистрация: 27.7.2003
Где: город-герой Минск

Репутация: 25
Всего: 232



Если дерево - STL'овский map, то берем итератор из "iter = begin()", и пока он не станет равным "end()" шагаем по дереву "iter++"; пару "ключ=>значение" получаем по "*iter" и сохраняем в файл. Дополнительно сохраняем перед началом дерева количество элементов.

Если надо потом загрузить, то грузим кол-во элементов и в цикле добавляем по "insert" каждую загружаемую пару "ключ=>значение".




--------------------
user posted image
PM MAIL WWW   Вверх
Бармалей
Дата 5.9.2003, 14:10 (ссылка)    |    (голосов: 0) Загрузка ... Загрузка ... Быстрая цитата Цитата


Unregistered











Baa
Проблема в том что я незнаю как правильно записать дерево чтобы его потом правильно же считатьmr.DUDA
Не STL фсе ручками сделаноо
  Вверх
Baa
Дата 5.9.2003, 14:20 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Экс. модератор
Сообщений: 2639
Регистрация: 12.4.2002
Где: Москва

Репутация: 8
Всего: 12



Дык если это ключ и значение, то самое простое - это INI файл.


--------------------
"Duty is everything; the greatest of joys, the deepest of sorrows" Aribeth de Tylmarande
PM ICQ   Вверх
RAN
Дата 5.9.2003, 21:20 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Экс. модератор
Сообщений: 709
Регистрация: 14.3.2003
Где: Щёлково Моск.обл.

Репутация: 5
Всего: 6



Цитата
Не STL фсе ручками сделаноо
Ну, так надо и писать тогда можешь как угодно. Это будет твоим форматам. Если хочешь выпендриться - используй XML. В этом формате сегодня почти любые профессиональные программы свои данные могут экспортировать. Тем более это как раз дерево чистой воды. Правда не двоичными будут данные.

P.S. Господа, в STL нет деревьев.
Модератор: По-моему, это вопрос не совсем по C++

PM MAIL ICQ   Вверх
mr.DUDA
Дата 5.9.2003, 22:08 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


3D-маньяк
****


Профиль
Группа: Экс. модератор
Сообщений: 8244
Регистрация: 27.7.2003
Где: город-герой Минск

Репутация: 25
Всего: 232



Цитата
P.S. Господа, в STL нет деревьев

Хехехе, как раз таки и облом.

Map и set хранят свои данные в виде сбалансированного двоичного дерева !!! Так что можно было б сделать в STL сие задание. А если и не в STL, то так:
Цитата

1) дерево внутри файла состоит из элементов след. типов:
     1а)  узел - объект, не содержащий других узлов и ветвей
     1б)  развилка - список узлов или развилок
     1в)  признак конца списка
2) для каждого из элементов сопоставляется свой признак (тэг), сохраняемый в файле перед каждым элементом дерева:
     2а)  для узла - байт, равный 1
     2б)  для развилки - байт 2
     2в)  для конца списка - байт 0
3) для сохранения дерева просто-напросто рекурсивно вызывается функция:
     3а)  если объект является узлом, перед ним записывается тэг 1, потом
            содержимое именно этого объекта (без дочерних)
     3б)  если объект содержит список дочерних объектов, т.е. является развилкой,
            то в файл записывается тэг 2, потом содержимое объекта и список
     3в)  список объектов записывается в файл (итеративно вызываются п.п. 3а и 3б)
     3г)  признаком конца списка является тэг 0 (записываемый в файл после
            последнего элемента списка/развилки)
4) для загрузки дерева:
     4а)  загружается из файла тэг
     4б)  если тэг 1, то загружается объект (узел дерева)
     4в)  если тэг 2, то в последнем загруженном узле создается список дочерних
            элементов (т.е. развилка)
     4г)  если тэг 0, то список заканчивается

Надеюсь, понятно объяснил wink.gif ?

ЗЫ, данная тема хоть и не относится чисто к C++, зато наиболее красиво дерево реализуется именно в C++.

ЗЫ(2), можно найти инфу на http://www.codeguru.com/algorithms/index.shtml, и возможно ещё на http://www.codeproject.com.

Это сообщение отредактировал(а) mr.DUDA - 5.9.2003, 23:05


--------------------
user posted image
PM MAIL WWW   Вверх
RAN
Дата 6.9.2003, 19:56 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Экс. модератор
Сообщений: 709
Регистрация: 14.3.2003
Где: Щёлково Моск.обл.

Репутация: 5
Всего: 6



Цитата
Map и set хранят свои данные в виде сбалансированного двоичного дерева

Кто-нибудь это понял smile.gif ? mr.DUDA, ты нас не путай, ты нам на пальцах объясни. Вот, к примеру, как такое дерево в STL записать:
Было две кошки Маруся и Муся, у них родились котатя, у тех, когда они выросли, тоже родились котята и т.д.
Код
<cats>
<cat>Маруся
         <cat>Пушок</cat>
         <cat>Мурка
                  <cat>Тишка</cat>
         </cat>
         <cat>Маркиз</cat>
</cat>
<cat>Муся
         <cat>Матрёна</cat>
</cat>
</cats>


PM MAIL ICQ   Вверх
mr.DUDA
Дата 6.9.2003, 23:05 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


3D-маньяк
****


Профиль
Группа: Экс. модератор
Сообщений: 8244
Регистрация: 27.7.2003
Где: город-герой Минск

Репутация: 25
Всего: 232



Код
#define   TAG_NODE  char(1)
#define   TAG_LIST    char(2)
#define   TAG_END    char(0)

class  CNode
{
 public:
       list<CNode*> m_Children;

       virtual void SaveInternalData(fstream &file) = 0;
       virtual void LoadInternalData(fstream &file) = 0;

       void SaveToFile(fstream &file)
       {
               SaveInternalData(file);
               for(int i=0; i<m_Children.size();; i++)
               {
                       file<<TAG_NODE;
                       m_pChildren[i]->SaveToFile(file);
               }
               file<<TAG_END;
       }

       void LoadFromFile(fstream &file)
       {
               LoadInternalData(file);
               char  tag;
               file>>tag;
               if(tag == TAG_LIST)
               {
                       sequence_delete(m_Children);
                       m_Children.empty();
                       file>>tag;
                       white(tag !=TAG_END)
                       {
                               CNode *NewNode = new CNode;
                               NewNode->LoadFromFile(file);
                               m_Children.insert(NewNode);
                       {
               }
       }
};

class CCat: public CNode
{
public:
       string   m_strName;
       void  SaveInternalData(fstream &file)   {file<<m_strName;}
       void  LoadInternalData(fstream &file)   {file>>m_strName;}

       CCat(string  name)  {m_strName = name;}
       CNode  *AddNode(string name)
       {
               CCat  *NewNode = new CCat(name);                
               m_Children.insert(NewNode);
               return  NewNode;
       }
};

void main()
{
       CCat  cats("");
       CCat  *marusja = cats.AddNode("Маруся");
       CCat  *pushok = marusja->AddNode("Пушок");
       CCat  *murka = pushok->AddNode("Мурка");
       murka->AddNode("Тишка");
       marusja->AddNode("Маркиз");
       CCat  *musja = cats.AddNode("Муся");
       musja->AddNode("Матрёна");

       // ... открыли файл "fstream fileS" для записи
       cats.SaveToFile(fileS);

       // ... открыли файл "fstream fileL" для чтения
       cats.LoadFromFile(fileL);
}

Нужны ещё комментарии или примеры wink.gif ?

Надеюсь, после этого принцип станет понятен...
Извините, что не сохранял в XML, просто было бы ещё замудрёнее. Так хоть идею понять можно.

Это сообщение отредактировал(а) mr.DUDA - 6.9.2003, 23:17


--------------------
user posted image
PM MAIL WWW   Вверх
RAN
Дата 7.9.2003, 04:27 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Экс. модератор
Сообщений: 709
Регистрация: 14.3.2003
Где: Щёлково Моск.обл.

Репутация: 5
Всего: 6



mr.DUDA, только один вопрос: где использование
Цитата
сбалансированного двоичного дерева
? Ты создал контенер с контейнером внутри. Такой способ хранения данных мы обсуждали недавно в теме про многомерные массивы.

И ещё. Я, конечно, не лезу в стили программирования, но мне не понятно зачем использовать указатели в контейнерах. Почему ты пишешь list<CNode*>? Почему не просто list<CNode>? Ведь тебе потом приходиться это всё удалять. Если учесть, что STL ещё раз выделяет память под CNode* ...
И ещё, я так понял, ты этот код не проверял. m_Children.insert(NewNode); работать не будет, ты наверное хотел написать m_Children.insert(m_Children.end(), NewNode);.

Я, короче, по другому это видел. Вот тему организовал. Давай, заходи. Будем думу думать smile.gif .

А между прочим человеку, ты единственный по теме ответил. Попытался предложить схему записи/чтения дерева. Но ему надо было двоичные данные хранить, а не строки. Как там быть? Теги твои могут оказаться данными (совпасть). А если записывать кол-во элементов, то будут необоснованные ограничения на кол-во записей.
PM MAIL ICQ   Вверх
mr.DUDA
Дата 7.9.2003, 10:07 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


3D-маньяк
****


Профиль
Группа: Экс. модератор
Сообщений: 8244
Регистрация: 27.7.2003
Где: город-герой Минск

Репутация: 25
Всего: 232



Цитата
где использование сбалансированного двоичного дерева

Нигде. Потому что:
Цитата
Не STL фсе ручками сделаноо

вот.

Насчёт
Цитата
Если учесть, что STL ещё раз выделяет память под CNode* ...

отчечу тем, что при использовании "list<CNode>" STL будет при добавлении ещё раз выделять память под весь объект CNode в конструкторе копирования. Что быстрее - выделить 4 байта под указатель, или N байт под весь объект smile.gif ?

Код набивал прямо в форуме, без проверки. Извиняйте. Показывал принцип работы, а не готовый сорц. Этим можно объяснить и "странноватый" контейнер CCat, который я привёл как пример узла дерева.

И последнее,
Цитата
Теги твои могут оказаться данными (совпасть).

Объект, читающий свои данные из файла, точно "знает", что будет прочитано в следующем байте: тэг начала списка, или внутренние данные объекта. Это, по ходу, определяется логикой работы схемы загрузки/сохранения, которую можно проектировать как угодно, лишь бы объект при загрузке соблюдал правильную очередность распределения данных из файла по своим полям (правильную - это такую же как при сохранении).

Это сообщение отредактировал(а) mr.DUDA - 7.9.2003, 10:08


--------------------
user posted image
PM MAIL WWW   Вверх
RAN
Дата 7.9.2003, 10:59 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Экс. модератор
Сообщений: 709
Регистрация: 14.3.2003
Где: Щёлково Моск.обл.

Репутация: 5
Всего: 6



Цитата
при использовании "list<CNode>" STL будет при добавлении ещё раз выделять память под весь объект CNode в конструкторе копирования.

Не используй STL.

Цитата
Объект, читающий свои данные из файла, точно "знает", что будет прочитано в следующем байте: тэг начала списка, или внутренние данные объекта
Да, я посмотрел. Согласен. Это наверное самое разумное.
PM MAIL ICQ   Вверх
  
Ответ в темуСоздание новой темы Создание опроса
Правила форума "С++:Общие вопросы"
Earnest Daevaorn

Добро пожаловать!

  • Черновик стандарта C++ (за октябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика(4.4мб).
  • Черновик стандарта C (за сентябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика (3.4мб).
  • Прежде чем задать вопрос, прочтите это и/или это!
  • Здесь хранится весь мировой запас ссылок на документы, связанные с C++ :)
  • Не брезгуйте пользоваться тегами [code=cpp][/code].
  • Пожалуйста, не просите написать за вас программы в этом разделе - для этого существует "Центр Помощи".
  • C++ FAQ

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Earnest Daevaorn

 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | C/C++: Общие вопросы | Следующая тема »


 




[ Время генерации скрипта: 0.0911 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.