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

N-дерево - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Ошибка LNK2019 в многофайловом проекте http://www.cyberforum.ru/cpp-beginners/thread1171891.html
Смысл: Мне нужно создать абстрактный класс контейнер, на его основе конкретные классы, далее создать абстрактный класс итератор и для каждого класса контейнера свой итератор. (для простоты оставил только один конкретный контейнер и итератор) При компиляции выходит ошибка Ошибка 1 error LNK2019: ссылка на неразрешенный внешний символ "public: __thiscall Vector::Iterv::Iterv(int *)"...
C++ Запись строковой переменной в файл String z ; z= Edit5->Text.c_str(); FILE * ptrFile = fopen("1.txt", "r"); if (ptrFile != NULL) { fputs(z.c_str(), ptrFile); // записать строку в файл fclose (ptrFile); } http://www.cyberforum.ru/cpp-beginners/thread1171889.html
Распечатать данные в массиве сведения, используя указанный образец C++
Бился-бился,не добился результата. Пожалуйста помогите. Задан массив, содержащий в себе сведения о сотрудниках учреждения такого образца: фамилия (пробел) имя (пробел) отчество, фамилия (пробел) имя (пробел) отчество ... Распечатать эти сведения, используя образец: имя (пробел) отчество (пробел) фамилия, имя (пробел) отчество (пробел) фамилия, ...
C++ Выбор оптимальной структуры данных
Здравствуйте! Задача состоит в следующем. Есть большой файл (~68 mb) с текстом. Нужно посчитать сколько раз встречается каждое слово в тексте и вывести эту информацию в формате "слово :: количество". Причем вывод должен быть отсортирован в алфавитном порядке. Я попробовал реализовать через двусвязный список, но файл обрабатывается довольно-таки долго: файла ~ 68,6 Мб t1 ::...
C++ Не пойму почему перменная d изменяет значения http://www.cyberforum.ru/cpp-beginners/thread1171872.html
// Kursovay_2.cpp: определяет точку входа для консольного приложения. //После выхода из функции graf_null изменяется перменная d #include "stdafx.h" #include <iostream> #include <conio.h> using namespace std; struct list{
C++ Написать программу, формирующую список, куда входят по одному разу элементы, присутствующие в обоих списках Ребят, прошу вашей помощи. Я плохо еще разбираюсь в односвязных списках. Мне просто программу с функциями нужно написать, которая формирует список Р. В этот список входят по одному разу элементы, которые одновременно входят в списки Р1 и Р2. Я уже очень долго пытаюсь понять эти списки. Вот пыталась написать что-то свое: // ConsoleApplication1.cpp: определяет точку входа для консольного... подробнее

Показать сообщение отдельно
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
11.05.2014, 17:08     N-дерево
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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <cstdio>
#include <cctype>
using namespace std;
 
int N; // определяет арность дерева
 
struct Node
{
    int v; // значение в узле дерева
    int n; // кол-во узлов в поддереве с корнем в данном узле
    Node **cld; // массив потомков
    Node() : v( 0 ), n( 1 ), cld( new Node * [ N ] ) { for ( int i = 0; i < N; ++i ) cld[ i ] = 0; }
};
 
Node *root = 0; // корень дерева
Node *msub = 0; // корень поддерева, которое надо найти по заданию
 
int parseTreeR( Node *&r, char *&s ) // парсит дерево из скобочной последовательности; возвращает кол-во узлов в поддереве
{
    int n = 0; // здесь накапливаем узлы поддерева
    int m; // не знаю как объяснить, чтобы не запутать
 
    if ( isdigit( *s ) )
    {
        r = new Node(); // создаем очередной узел дерева
        n = 1; // и запоминаем, что в поддереве с корнем в этом узле есть 1 узел
        do { r->v = r->v * 10 + *s++ - '0'; } while ( isdigit( *s ) ); // парсим значение в узле
        for ( int i = 0; i < N; ++i ) // рекурсивно парсим всех потомков
            if ( *s == '(' && ( m = parseTreeR( r->cld[ i ], ++s ) ) >= 0 && *s == ')' )
                { ++s; n += m; }
        return r->n = n;
    }
    else if ( *s == ')' ) return n; // особый случай: пустой узел ( типа такого: () )
    else return -1; // если криво ввели скобочную последовательность, то надо об этом сообщить "наверх"
}
 
bool parseTree( char *s ) // обертка над парсилкой дерева parseTreeR
{
    int m;
    if ( *s == '(' )
    {
        m = parseTreeR( root, ++s );
        if ( m == -1 ) return false;
        if ( *s == ')' && *++s == 0 ) return true;
        else return false;
    }
    return false;
}
 
void showTreeR( Node *r, int sh ) // распечатка дерева
{
    if ( !r ) return;
    for ( int j = 0; j < sh; ++j ) putchar( ' ' );
    printf( "%d\n", r->v );
    for ( int i = 0; i < N; ++i )
        showTreeR( r->cld[ i ], sh + 5 );
}
 
void showTree() // обертка над печаталкой дерева
{
    printf( "\nTree:\n\n" );
    showTreeR( root, 0 );
    printf( "\n" );
}
 
bool findMaxSubR( Node *r, int *a, int n ) // ф-ция поиска максимального поддерева с заданными свойствами
{
    if ( !r ) return true;
    
    bool flag = true;
 
    for ( int i = 0; i < N; ++i )
        flag &= findMaxSubR( r->cld[ i ], a, n );
    for ( int j = 0; j < n; ++j )
        if ( a[ j ] == r->v )
            flag = false;
    if ( flag )
        if ( !msub || msub->n < r->n )
            msub = r;
    return flag;
}
 
void findMaxSub( int *a, int n ) // обертка над findMaxSubR + распечатка результатов
{
    findMaxSubR( root, a, n );
    printf( "\nMaxSubTree:\n" );
    showTreeR( msub, 0 );
    printf( "\n" );
}
 
int main()
{
    N = 3; // задаем арность дерева
//  char s[] = "(1)";
//  char s[] = "(1(2(3)(4)))";
    char s[] = "(1(2(5(6)))(3(7(8)(2)))(4))"; // дерево в виде скобочной последовательности
 
    int a[] = { 1, 9, 4 }; // это "заданные вершины"
 
    if ( parseTree( s ) ) // если дерево удачно спарсилось из скобочной последовательности
    {
        showTree();
        findMaxSub( a, sizeof( a ) );
    }
    else
        printf( "Bad tree\n\n" );
 
    return 0;
}
задание дерева с помощью скобочной последовательности (N = 3):
() - пустое дерево
(5) - дерево с одним узлом со значением 5
(5()()()) - то же что и выше, но в более развернутой форме (указано, что есть 3 пустых потомка)
(5(7)) - дерево с корнем 5 и одним потомком со значением 7
(5()(7)()) - то же что и выше
(5(7)(4)) - дерево с корнем 5 и 2-мя его потомками 7 и 4
(5(7)()(4)) - то же что и выше
(5(7(4))) - дерево с корнем 5, его сыном 7 и внуком 4
(5(7(4)())) - то же что и выше
(5()(7(4))) - то же что и выше
(5()(7(4))()) - то же что и выше
думаю примерно понятно как задается дерево с помощью скобочной последовательности: дерево должно быть окружено парой скобок, внутри скобок вначале задается значение корня, а затем перечисляются все поддеревья этого дерева (естественно каждое в отдельных скобках) (их должно быть не больше N). по мне так очень удобно задавать деревья (после небольшой практики конечно )
обращаю внимание на то, что пустые пары скобок не обязательны, можно добавить а можно и опустить.
 
Текущее время: 19:14. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru