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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
eocron
Кактус
66 / 66 / 6
Регистрация: 23.05.2012
Сообщений: 343
#1

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

25.07.2013, 18:02. Просмотров 379. Ответов 3
Метки нет (Все метки)

Задача состоит в том, чтобы построить структуру данных по заданному рекурсивному расписанию каталогов. Причем:Все узлы отсортированны по порядковому номеру, в каждом узле должно быть имя, индекс родителя, сортированный вектор из индексов детей.

Вот пример:
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");
Загвоздка в том, что я не пойму каким образом получить индекс родителя. Точнее как это сделать оптимальнее всего, хранить весь путь а потом искать по нему? Или бить на части и искать по частям? Или мап сделать от имени (но тогда пострадает поиск по индексу, что вообще очень печально)?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.07.2013, 18:02     Подскажите как написать такое дерево (или БД)
Посмотрите здесь:

Дан текст. файл, сост. из одной или нескольких строк.подскажите,как написать программу - C++
Дан текст. файл, сост. из одной или нескольких строк. Каждая строка файла содержит числа, разделенные пробелами. Из каждой строки файла...

Что такое матричный знакогенератор и как его написать - C++
необходимо написать Матричный знакогенератор.Что это такое? на языке С++

Конструктор дерева (не бинарного). Или как вообще правильно строить дерево? - C++
Хочу разобраться с деревьями, да что только не читал, не пересматривал - не могу разобраться. Для примера - хочу построить дерево такого...

Как написать такое явное преобразование из double в unsigned long int - C++
как написать такое явное преобразование из double в unsigned long int??? спасибо всем кто поможет...

Используя очередь или стек, описать процедуру или функцию, определяющую число вхождений элемента Е в дерево Т - C++
Народ помогите пожалуйста! Проблема в том, что не понимаю суть задания. Прошу не код, а объяснения принципа реализации. С чего начать? как...

Подскажите как написать - C++
Алгоритм решения индивидуальной задачи разделить на две функции: - функцию, которая организует вычисления по формуле, определенной в ...

Подскажите. Бинарное дерево - C++
подскажите пожалуйста, как сделать так чтобы при совпадении вершин(той которая уже в дереве с той, которую пытаемся добавить) обе...

Подскажите как написать программу - C++
не могу разобраться с логарифмом и корнем, помогите написать g=x*Ln(\frac{2x}{b})cos{}^{2}a a=0.3, b=0.05 Редактор формул внизу...

подскажите, как написать уравнение - C++
подскажите, как написать уравнение

Как написать праграмму подскажите на с++ - C++
В массиве хранятся сведения о количестве осадков,выпавших за каждый день августа.Определить среднее количество осадков,выпавших в дни,когда...

Подскажите, как правильно написать - C++
Здравствуйте! Подскажите, пожалуйста, как написать такой код правильно: class Example { public: Example(int...

лаба по Си++ подскажите как написать=) - C++
Характеристикой столбца целочисленной матрицы назовем сумму модулей его отрицательных нечетных элементов. Переставляя столбцы заданной...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Olivеr
412 / 408 / 13
Регистрация: 06.10.2011
Сообщений: 831
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
Кактус
66 / 66 / 6
Регистрация: 23.05.2012
Сообщений: 343
25.07.2013, 22:20  [ТС]     Подскажите как написать такое дерево (или БД) #3
На самом деле я и сам могу построить дерево, но мне нужно не просто дерево, а быстрое дерево. В любом случае я уже написал такой код, который удовлетворяет моим нуждам) . Все равно спасибо )

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru