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

Splay-tree (написать программу, которая будет искать в файле сущности (целые числа) и заносить их в дерево) - C++

Восстановить пароль Регистрация
 
Sato
0 / 0 / 0
Регистрация: 10.12.2012
Сообщений: 18
25.05.2013, 21:24     Splay-tree (написать программу, которая будет искать в файле сущности (целые числа) и заносить их в дерево) #1
Приветствую. Потребовалось написать программу, которая будет искать в файле сущности (целые числа) и заносить их в дерево, с последующим выводом всех найденных значений на экран.
В процессе реализации возникло несколько вопросов:
а) Для подобной цели было выбрано Splay-дерево. Является ли адекватным его выбор? Особенно с учётом, что есть большая вероятность, что на выходе будет сильно разветвлённое дерево (в программе встречается множество разных значений, но каждое из них встречается лишь несколько раз).
И если всё-таки использовать Splay, не могли бы вы помочь с реализацией функции вставки\просмотра дерева? Алгоритмически всё кажется понятным, да и Splay я вроде с горем пополам реализовал, а с этими функциями совсем беда.
б) Попытался использовать string, чтобы посимвольно выискивать числа в тексте и заносить их в string-переменную, дабы в последствии направлять его в дерево.
Кликните здесь для просмотра всего текста
c:\program files (x86)\microsoft visual studio 10.0\vc\include\xstring(772): может быть "std::basic_string<_Elem,_Traits,_Ax> &std::basic_string<_Elem,_Traits,_Ax>::operator =(_Elem)"
1> with
1> [
1> _Elem=char,
1> _Traits=std::char_traits<char>,
1> _Ax=std::allocator<char>
1> ]
1> c:\program files (x86)\microsoft visual studio 10.0\vc\include\xstring(767): или "std::basic_string<_Elem,_Traits,_Ax> &std::basic_string<_Elem,_Traits,_Ax>::operator =(const _Elem *)"
1> with
1> [
1> _Elem=char,
1> _Traits=std::char_traits<char>,
1> _Ax=std::allocator<char>
1> ]
1> при попытке сопоставить список аргументов "(std::string, int)"

Именно такую ошибку выдаёт компилятор, хотя
C++
1
#include <string>
присутствует. В чём может быть проблема? Быть может есть альтернативные варианты?

Пока-что вроде всё. Хотя более чем уверен, что в процессе вопросы ещё возникнут ибо программа явно опережает мои познания в языке.
Заранее благодарю за ответы.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.05.2013, 21:24     Splay-tree (написать программу, которая будет искать в файле сущности (целые числа) и заносить их в дерево)
Посмотрите здесь:

Написать программу которая будет разделять число C++
Написать программу которая в текстовом файле будет искать слова с наибольшим количеством заданны букв C++
C++ Заданы целые числа a1, a2,…, an. Написать программу, которая находит сумму четных чисел среди чисел a1, a2,…, an
C++ Написать программу, которая выводит в консоль только четные целые числа из диапазона от 1 до 20
написать программу, которая будет переворачивать введенное предложение C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
gazlan
2855 / 1803 / 271
Регистрация: 27.08.2010
Сообщений: 4,883
Записей в блоге: 1
25.05.2013, 23:22     Splay-tree (написать программу, которая будет искать в файле сущности (целые числа) и заносить их в дерево) #2
Цитата Сообщение от Sato Посмотреть сообщение
было выбрано Splay-дерево. Является ли адекватным его выбор?
Каковы критерии выбора? Зачем вообще нужно дерево? Каков размер (уникальной) выборки?

Если выборка из дерева производится однократно, то Splay Tree, как минимум, бесполезно. Если размер выборки можно оценить заранее, хэш-таблица может оказаться лучшим (O(1)) вариантом. AVL Tree будет самым быстрым деревом поиска, а B/B+ Tree - самым компактным. А может быть вас и Priority Queue устроит? Что вы собираетесь делать с найденными числами?

Короче говоря, обозначьте цели и приоритеты, код пишется в последнюю очередь, когда уже ясно все остальное.
Sato
0 / 0 / 0
Регистрация: 10.12.2012
Сообщений: 18
26.05.2013, 01:23  [ТС]     Splay-tree (написать программу, которая будет искать в файле сущности (целые числа) и заносить их в дерево) #3
Будет производиться поиск целых чисел в текстовом файле. В задании прямо этого не сказано, но раз нет никаких ограничений внутри множества целых, то скорее всего каждое из чисел будет встречаться малое число раз (если вообще не по одному), зато количество разных значений будет зашкаливать. Планирую для теста конечной программы просто запустить лкг генератор на запись в текстовик, а потом пройтись по нему этим поиском.
Дерево требуется, потому что его нужно реализовать по заданию.
gazlan
2855 / 1803 / 271
Регистрация: 27.08.2010
Сообщений: 4,883
Записей в блоге: 1
26.05.2013, 01:48     Splay-tree (написать программу, которая будет искать в файле сущности (целые числа) и заносить их в дерево) #4
Ну, раз это учебная задача, используйте простейший вариант - бинарное дерево поиска. Для теста можете взять готовую таблицу простых чисел.
Sato
0 / 0 / 0
Регистрация: 10.12.2012
Сообщений: 18
26.05.2013, 12:54  [ТС]     Splay-tree (написать программу, которая будет искать в файле сущности (целые числа) и заносить их в дерево) #5
В том и проблема, что по заданию надо выбрать наиболее подходящее дерево. Бинарным тут вряд ли отстреляешься.
gazlan
2855 / 1803 / 271
Регистрация: 27.08.2010
Сообщений: 4,883
Записей в блоге: 1
26.05.2013, 13:09     Splay-tree (написать программу, которая будет искать в файле сущности (целые числа) и заносить их в дерево) #6
Ну, тогда AVL - сбалансированное, быстрый поиск, полно готовых реализаций. Хотя для однократной выборки это, опять же, избыточно.
Sato
0 / 0 / 0
Регистрация: 10.12.2012
Сообщений: 18
26.05.2013, 17:39  [ТС]     Splay-tree (написать программу, которая будет искать в файле сущности (целые числа) и заносить их в дерево) #7
Кликните здесь для просмотра всего текста
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
struct node // структура для представления узлов дерева
{
    int key;
    unsigned char height;
    node* left;
    node* right;
    node(int k) { key = k; left = right = 0; height = 1; }
};
 
unsigned char height(node* p)
{
    return p?p->height:0;
}
 
int bfactor(node* p)
{
    return height(p->right)-height(p->left);
}
 
void fixheight(node* p)
{
    unsigned char hl = height(p->left);
    unsigned char hr = height(p->right);
    p->height = (hl>hr?hl:hr)+1;
}
 
node* rotateright(node* p) // правый поворот вокруг p
{
    node* q = p->left;
    p->left = q->right;
    q->right = p;
    fixheight(p);
    fixheight(q);
    return q;
}
 
node* rotateleft(node* q) // левый поворот вокруг q
{
    node* p = q->right;
    q->right = p->left;
    p->left = q;
    fixheight(q);
    fixheight(p);
    return p;
}
 
node* balance(node* p) // балансировка узла p
{
    fixheight(p);
    if( bfactor(p)==2 )
    {
        if( bfactor(p->right) < 0 )
            p->right = rotateright(p->right);
        return rotateleft(p);
    }
    if( bfactor(p)==-2 )
    {
        if( bfactor(p->left) > 0  )
            p->left = rotateleft(p->left);
        return rotateright(p);
    }
    return p; // балансировка не нужна
}
 
node* insert(node* p, int k) // вставка ключа k в дерево с корнем p
{
    if( !p ) return new node(k);
    if( k<p->key )
        p->left = insert(p->left,k);
    else
        p->right = insert(p->right,k);
    return balance(p);
}


На просторах Хабра была найдена вот такая реализация АВЛ дерева, но с ней возникли те же проблемы, что и со Splay-ем. В частности, совершенно не понимаю добавления элемента\вывода элементов на экран. В своё время с горем пополам разобрался с линейный списком, но там всё было куда более прозаичным. Опять же, вроде алгоритмически понятно что сделано в примере и как к этому подключиться, но на практике сталкиваюсь с тем, что понятия не имею, как собственные значения направить в дерево.
gazlan
2855 / 1803 / 271
Регистрация: 27.08.2010
Сообщений: 4,883
Записей в блоге: 1
26.05.2013, 18:43     Splay-tree (написать программу, которая будет искать в файле сущности (целые числа) и заносить их в дерево) #8
Цитата Сообщение от Sato Посмотреть сообщение
не понимаю добавления элемента\вывода
Это вообще не зависит от типа дерева. У вас будут две операции вида Insert(Node* pNode) и Find(Node* pKey). Ну, еще полный обход.

Для вставки создаете новый пустой узел, присваиваете значению ключу и вызываете Insert(). Он делает все остальное. Для поиска все то же самое, только вызываете Find(). То что (и если) нашли - выводите на экран.

C++
1
2
3
4
5
NODE* pNewNode = new NODE;
 
pNewNode->Key = Key;
 
Tree.Insert(pNewNode);
C++
1
2
3
4
5
6
7
8
9
10
NODE* pFind = new NODE;
 
pFind->Key = Key;
 
NODE* pFound = Find(pFind);
 
if (pFound)
{
   // Do smth
}
Sato
0 / 0 / 0
Регистрация: 10.12.2012
Сообщений: 18
26.05.2013, 20:01  [ТС]     Splay-tree (написать программу, которая будет искать в файле сущности (целые числа) и заносить их в дерево) #9
А можно поподробнее с функцией Find? Просто меня поиск отдельных элементов как таковых не интересует - вывод будет производиться лишь один раз, на экран выводятся сразу все элементы (число - сколько их найдено в файле).
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.05.2013, 20:26     Splay-tree (написать программу, которая будет искать в файле сущности (целые числа) и заносить их в дерево)
Еще ссылки по теме:

Написать программу, которая буде искать и открывать файл. C++
C++ Написать программу которая будет искать разные слова из текста
C++ Реализовать программу, которая сохраняет три целые числа в текстовом файле и затем читает сохраненные данные

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

Или воспользуйтесь поиском по форуму:
gazlan
2855 / 1803 / 271
Регистрация: 27.08.2010
Сообщений: 4,883
Записей в блоге: 1
26.05.2013, 20:26     Splay-tree (написать программу, которая будет искать в файле сущности (целые числа) и заносить их в дерево) #10
Цитата Сообщение от Sato Посмотреть сообщение
вывод будет производиться лишь один раз
Тогда и Find() не нужен. Сделайте рекурсивный обход в глубину. Depth-first search
Yandex
Объявления
26.05.2013, 20:26     Splay-tree (написать программу, которая будет искать в файле сущности (целые числа) и заносить их в дерево)
Ответ Создать тему
Опции темы

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