Форум программистов, компьютерный форум CyberForum.ru

Подскажите как написать такое дерево (или БД) - C++

Восстановить пароль Регистрация
 
eocron
Кактус
 Аватар для eocron
66 / 66 / 6
Регистрация: 23.05.2012
Сообщений: 343
25.07.2013, 18:02     Подскажите как написать такое дерево (или БД) #1
Задача состоит в том, чтобы построить структуру данных по заданному рекурсивному расписанию каталогов. Причем:Все узлы отсортированны по порядковому номеру, в каждом узле должно быть имя, индекс родителя, сортированный вектор из индексов детей.

Вот пример:
C++
1
2
3
4
5
6
7
8
9
10
11
.
./download_client.sh
./random1000_queries_sport.txt
./times.txt
./site
./site/site_kz_domains_random1000_2011-07-26.txt
./site/site_ru_domains_random1000_2011-07-26.txt
./site/site_by_domains_random1000_2011-07-26.txt
./site/kz
./site/kz/random1000
./site/kz/random1000/site_by_domains_random1000_2011sd-07-26.txt
А вот мой намоляканный код на обработку этого:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
      struct Node
      {
             string name;
             int high;
             int parent;
             map<int, Node *> kids;
      };
      
      map<int,Node> tree;
 
___________________________
 
                  string str;
                  string name;
 
                  for(int i=0;cin.good();i++)
                  {
                        cin>>str;
                        name = GetTail(str);
                        
                        tree[i].name                   = name;
                        tree[i].parent                 = ????????????????????????????
                        tree[i].high                   = tree[tree[i].parent].high + 1;
                        
                        tree[parent].kids[i]           = &tree[i]; //ну тут позор, да. Сделал для прикола
                  }
                  system("pause");
Загвоздка в том, что я не пойму каким образом получить индекс родителя. Точнее как это сделать оптимальнее всего, хранить весь путь а потом искать по нему? Или бить на части и искать по частям? Или мап сделать от имени (но тогда пострадает поиск по индексу, что вообще очень печально)?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Olivеr
 Аватар для Olivеr
411 / 407 / 13
Регистрация: 06.10.2011
Сообщений: 830
25.07.2013, 21:35     Подскажите как написать такое дерево (или БД) #2
Насколько я понял вам нужно построить дерево каталогов и файлов? Объясните подробнее...

Вот родил такой код:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <string>
#include <iomanip>
#include <stack>
#include <algorithm>
#include <cstdint>
 
struct Node
{
    Node(const std::string &_name) :
            name(_name),
            next() {}
 
    std::string name;
    std::vector<Node*> next;
 
    ~Node()
    {
        for (auto node : next) {
            delete node;
        }
    }
};
 
auto split(const std::string &str, char delim)
{
    std::vector<std::string> v;
    std::istringstream iss(str);
    std::string token;
    while (std::getline(iss, token, delim))
        v.push_back( std::move(token) );
    return v;
}
 
int main()
{
    setlocale(LC_CTYPE, "");
 
    std::ifstream file("file.txt");
    if (!file.good()) return 1;
 
    auto tree = new Node("");
 
    std::string str;
 
    while ( getline(file, str) ) {
        auto tokens = split(str, '/');
        auto node = tree;
 
        for (auto &s : tokens) {
            auto it = std::find_if( std::begin(node->next), std::end(node->next),
                            [&s](Node *n) { return n->name == s; } );
 
            if (it == end(node->next)) {
                node->next.push_back( new Node(s));
                node = node->next.back();
            } else {
                node = *it;
            }
        }
    }
 
    file.close();
 
    std::stack<std::pair<Node*, int32_t>> q;
    q.push( {tree, -1} );
 
    while ( !q.empty() ) {
        auto p = q.top();
        q.pop();
        std::cout << std::setw(p.second + p.first->name.size() + 1) << p.first->name << std::endl;
        for (auto node : p.first->next)
            q.push( {node, p.second + p.first->name.size()} );
    }
 
    delete tree;
    return 0;
}
если вбить в файл ваши данные, то получим (см. скриншот)
Миниатюры
Подскажите как написать такое дерево (или БД)  
eocron
Кактус
 Аватар для eocron
66 / 66 / 6
Регистрация: 23.05.2012
Сообщений: 343
25.07.2013, 22:20  [ТС]     Подскажите как написать такое дерево (или БД) #3
На самом деле я и сам могу построить дерево, но мне нужно не просто дерево, а быстрое дерево. В любом случае я уже написал такой код, который удовлетворяет моим нуждам) . Все равно спасибо )

Задача заключалась в быстрейшем доступе к элементу дерева по:полному имени, индексу или высоте.
gazlan
2861 / 1809 / 272
Регистрация: 27.08.2010
Сообщений: 4,897
Записей в блоге: 1
26.07.2013, 00:50     Подскажите как написать такое дерево (или БД) #4
R-tree
Yandex
Объявления
26.07.2013, 00:50     Подскажите как написать такое дерево (или БД)
Ответ Создать тему
Опции темы

Текущее время: 20:41. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru