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

Дерево - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Перенос битов http://www.cyberforum.ru/cpp-beginners/thread288608.html
Ввести число, перенести все еденичные биты в середину разрядной сетки.
C++ typedef struct .... Здравствуейте. Обьясните пожалуйсто новичку что означает этот код. typedef struct { long num_servers; long data_size; char* data; }SSQ_BATCH_REPLY,*PSSQ_BATCH_REPLY; http://www.cyberforum.ru/cpp-beginners/thread288590.html
C++ Программка С++ Proc
Описать функцию Power2(A, N) вещественного типа, находящую вели- чину AN(N-это степень A) (A — вещественный, N — целый параметр) по следующим форму- лам: A0(0-степень A) = 1; ...
Работа со словами в строке. C++
Здравствуйте. Помогите, пожалуйста, с решением. 1) Вводим предложение. Нужно вывести каждое слово с новой строки. Разделителями между словами могут быть: пробел, ‘ , /, , . и т.д. Цифры выводить не...
C++ Задание про слова http://www.cyberforum.ru/cpp-beginners/thread288554.html
Здравствуйте,я в си новичок.Не поможете мне решить задачу(написать код)? "Дано ошибочно написанное слово "рпроцессо". Путем перемещения его букв получить слово "процессор"
C++ прога, которая по нажатой клавише выводит ascii - код символа это клавиши или scan - код самой клавиши. написать программу, которая по нажатой клавише выводит ascii - код символа этой клавиши или scan - код самой клавиши. осуществите вывод в 8-й, 10-й и 16-й системах счисления. код с++. заранее... подробнее

Показать сообщение отдельно
fasked
Эксперт С++
4942 / 2522 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
05.05.2011, 00:50
kjahert, конкретно по примеру Вашей структуры нет, но есть более-менее похожий вариант. Получайте

teacher.h
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#ifndef KJAHERT_TEACHER_H
#define KJAHERT_TEACHER_H
 
#define TEACHER_NAME_LENGTH 30
#define TEACHER_DISC_LENGTH 10
#define TEACHER_POST_LENGTH 10
#define TEACHER_NUMBER_DISC  3
 
struct teacher {
    char name[TEACHER_NAME_LENGTH];
    char post[TEACHER_POST_LENGTH];
    char disc[TEACHER_NUMBER_DISC][TEACHER_DISC_LENGTH];
};
 
#endif /* KJAHERT_TEACHER_H */
tree.h
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#ifndef KJAHERT_TREE_H
#define KJAHERT_TREE_H
 
#include <stdio.h>
#include "teacher.h"
 
struct binary_tree_node;
 
struct binary_tree
{
    struct binary_tree_node *root;
};
 
struct binary_tree *binary_tree_new();
void binary_tree_delete(struct binary_tree *);
void binary_tree_clear(struct binary_tree *tree);
void binary_tree_remove(struct binary_tree *tree, const char *key); 
void binary_tree_insert(struct binary_tree *tree, struct teacher *item);
 
void binary_tree_print(FILE *stream, struct binary_tree *tree);
 
#endif /* KJAHERT_TREE_H */
tree.c
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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
 
#include "tree.h"
 
struct binary_tree_node {
    struct teacher item;
    struct binary_tree_node *left;
    struct binary_tree_node *right;
};
 
struct binary_tree_node *binary_tree_node_new(struct binary_tree_node *left,
                                              struct binary_tree_node *right)
{
    struct binary_tree_node *node = 
           (struct binary_tree_node *)calloc(1, sizeof(struct binary_tree_node));
 
    if (node) {
        node->left = left;
        node->right = right;
    }
    
    return node;
}
 
void binary_tree_insert(struct binary_tree *tree, struct teacher *item) {
    struct binary_tree_node *node = tree->root;
    struct binary_tree_node *parent = NULL;
    
    assert(tree);
    assert(item);
    
    while (node) {
        parent = node;
        if (strcmp(node->item.name, item->name) == -1)
            node = node->left;
        else
            node = node->right;
    }
    
    node = binary_tree_node_new(NULL, NULL);
    node->item = *item; // memcpy(&node->item, item, sizeof(*item)); //
    printf("%p NODE created\n", node);
    
    if (!parent) {
        tree->root = node;
    }
    else {
        if (strcmp(parent->item.name, item->name) == -1)
            parent->left = node;
        else
            parent->right = node;
    }
}
 
void binary_tree_remove(struct binary_tree *tree, const char *key) {
    struct binary_tree_node *node = tree->root;
    struct binary_tree_node *child = NULL;
    struct binary_tree_node *parent = NULL;
    struct binary_tree_node *removed = NULL;
    struct binary_tree_node *most_left = NULL;
    struct binary_tree_node *most_left_parent = NULL;
 
    assert(key);
    assert(tree);
 
    while (node && strcmp(node->item.name, key)) {
        parent = node;
        if (strcmp(node->item.name, key) == -1)
            node = node->left;
        else
            node = node->right;
    }
 
    if (node) {
        if (!node->left || !node->right) {
            removed = node;
            if (node->left)
                child = node->left;
            else if (node->right)
                child = node->right;
            
            if (!parent) {
                tree->root = child;
            }
            else {
                if (parent->left == node)
                    parent->left = child;
                else
                    parent->right = child;
            }
        }
        else {
            most_left = node->right;
            most_left_parent = node;
            
            while (most_left->left) {
                most_left_parent = most_left;
                most_left = most_left->left;
            }
            
            node->item = most_left->item;
            removed = most_left;
            
            if (most_left_parent->left == most_left)
                most_left_parent->left = NULL;
            else
                most_left_parent->right = NULL;
        }
 
        printf("%p NODE deleted\n", removed);
    } 
}
 
void binary_tree_clear(struct binary_tree *tree) {
    assert(tree);
    while (tree->root) {
        binary_tree_remove(tree, tree->root->item.name);
    }
}
 
struct binary_tree *binary_tree_new() {
    struct binary_tree *p = (struct binary_tree *)calloc(1, sizeof(struct binary_tree));
    printf("%p TREE created\n", p);
    
    return p;
}
 
void binary_tree_delete(struct binary_tree *tree) {
    if (tree) {
        binary_tree_clear(tree);
        
        printf("%p TREE deleted\n", tree);
        free(tree);
    }
}
 
void binary_tree_postorder_print(FILE *stream, struct binary_tree_node *node) {
    int i;
    if (node) {
        binary_tree_postorder_print(stream, node->left);
        binary_tree_postorder_print(stream, node->right);
        
        fprintf(stream, "%10s: %s\n%10s: %s\n%10s:\n", "name", node->item.name, "post", node->item.post, "disciplines");
        for (i = 0; *(node->item.disc[i]); ++i) {
            fprintf(stream, "%10s: %s\n", "", node->item.disc[i]);
        }
    }
}
 
void binary_tree_print(FILE *stream, struct binary_tree *tree) {
    assert(tree);
    binary_tree_postorder_print(stream, tree->root);
}
main.c
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
#include "tree.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
struct teacher *input_info(FILE *stream, struct teacher *t) {
    int i;
    
    printf ("INPUT info for %p\n", t);
    printf ("NAME: ");
    fgets(t->name, TEACHER_NAME_LENGTH, stream);
    t->name[strlen(t->name) - 1] = '\0';
    
    printf ("POST: ");
    fgets(t->post, TEACHER_POST_LENGTH, stream);
    t->post[strlen(t->post) - 1] = '\0';
    
    for (i = 0; i < TEACHER_NUMBER_DISC; ++i) {
        printf ("DISC: ");
        fgets(t->disc[i], TEACHER_DISC_LENGTH, stream);
        t->disc[i][strlen(t->disc[i]) - 1] = '\0';
    }
    
    return t;
}
 
int main()
{
    struct binary_tree *tree;
    struct teacher t;
    int i;
    
    if ((tree = binary_tree_new()) == NULL) {
        fprintf(stderr, "allocate memory error\n");
        exit(1);
    }
    
    for (i = 0; i < 3; ++i) {
        memset(&t, 1, sizeof(t));
        binary_tree_insert(tree, input_info(stdin, &t));
    }
    
    binary_tree_print(stdout, tree);
    
    binary_tree_delete(tree);
    return 0;
}
В файле main.c приводится пример работы с деревом. Создается 3 записи типа teacher. Количество дисциплин у каждого по три, можно сделать неограниченное, но это надо возиться, для примера пойдет и так (тем более смысл работы тут именно в дереве). Функции для дерева только необходимое: добавление элемента, удаление элемента по ключу и post-order обход дерева для вывода содержимого.

В коде программы много отладочной информации, в первую очередь для контроля памяти - чтобы утечек не было. Перед каждым вызов malloc/calloc и перед каждым вызовом free. По номерам указателей можно видеть, что утечек нет. Конечно отладочную информацию можно убрать.

В таком примере программа работает следующим образом:
Код
// старт программы
00542E70 TREE created

// ввод информации с клавиатуры
INPUT info for 0028FEF2
NAME: IVANOV
POST: DIRECTOR
DISC: 01
DISC: 02
DISC: 03
00540E78 NODE created
INPUT info for 0028FEF2
NAME: SIDOROV
POST: TEACHER
DISC: 02
DISC: 03
DISC: 05
00540ED0 NODE created
INPUT info for 0028FEF2
NAME: PETROV
POST: TEACHER
DISC: 01
DISC: 06
DISC: 07
00540F28 NODE created

// вывод информации начинается с этого момента

      name: PETROV
      post: TEACHER
disciplines:
          : 01
          : 06
          : 07
      name: SIDOROV
      post: TEACHER
disciplines:
          : 02
          : 03
          : 05
      name: IVANOV
      post: DIRECTOR
disciplines:
          : 01
          : 02
          : 03
00540E78 NODE deleted
00540ED0 NODE deleted
00540F28 NODE deleted
00542E70 TREE deleted
Комментарии я повставлял сам, чтобы Вам понятнее было, где какая часть работает.
Возникнут вопросы - задавайте их здесь.

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