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

Бинарные деревья - C++

Восстановить пароль Регистрация
 
xorrer
0 / 0 / 0
Регистрация: 25.02.2013
Сообщений: 23
12.12.2013, 20:25     Бинарные деревья #1
Здравствуйте! Я пытаюсь выполнить лабораторную, но вот не понимаю причин возникающих ошибок... Помогите, пожалуйста!)
Изначально задание звучит так:
Составить программу, которая содержит текущую информацию о книгах в библиотеке.
Сведения о книгах содержат:
УДК;
ФИО автора;
название;
год издания;
количество экземпляров данной книги в библиотеке.
Программа должна обеспечивать:
начальное формирование данных о всех книгах в библиотеке в виде двоичного дерева;
добавление данных о книгах, вновь поступающих в библиотеку;
удаление данных о списываемых книгах;
по запросу выдаются сведения о наличии книг в библиотеке, упорядоченные по годам издания

Я реализую его вот так:
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
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
#include "stdafx.h"
#include <iostream>
 
using namespace std;
 
struct bib {    //библиотека)
char udk[30];
char fio[50];
char title[250];
int year;
int kolvo;
int id;
bib* left;
bib* right;
};
 
 
 
void vvodbibl (bib *t) 
{
        cout << "Enter FIO of author" << endl;
        char fam[50];
        cin >> fam;
        strcpy (t->fio, fam);
        cout << "Enter UDK" << endl;
        char num[30];
        cin >> num;
        strcpy (t->udk, num);
        cout << "Enter the title" << endl;
        char tit[250];
        cin >> tit;
        strcpy (t->title, tit);
        cout << "Enter the quantity of such books" << endl;
        int q;
        cin >> q;
        t->kolvo = q;
        cout << "Enter the year of release" << endl;
        int y;
        cin >> y;
        t->year = y;
}
/*ФУНКЦИЯ ЗАПИСИ ЭЛЕМЕНТА В БИНАРНОЕ ДЕРЕВО*/
void push(int a, bib **t)
{
    if ((*t) == NULL) //Если дерева не существует
    {
        (*t) = new bib; //Выделяем память
        (*t)->id = a; //Кладем в выделенное место аргумент a
        vvodbibl (*t);
        (*t)->left = (*t)->right = NULL; //Очищаем память для следующего роста
        return; //Заложили семечко, выходим
    }
       //Дерево есть
    if (a == (*t)->id) {
        (*t)->kolvo = (*t)->kolvo + 1;
        (*t)->left = (*t)->right = NULL;
    }
    else {
        if (a > (*t)->id){ //Если аргумент а больше чем текущий элемент, кладем его 
          if ((*t)->right != NULL) {
                push(a,&(*t)->right); //При помощи рекурсии заталкиваем элемент на свободный участок
            }
            else {
                (*t)->right = new bib; //Выделяем память
                (*t)->right->id = a; //Кладем в выделенное место аргумент a
                vvodbibl (*t);
                (*t)->right->left = (*t)->right->right = NULL; //Очищаем память для следующего роста
            }
        }
        else {                 //Иначе кладем его влево
            if ((*t)->left != NULL) {
                push(a,&(*t)->left); //При помощи рекурсии заталкиваем элемент на свободный участок
            }
            else {
                (*t)->left = new bib; //Выделяем память
                (*t)->left->id = a; //Кладем в выделенное место аргумент a
                vvodbibl (*t);
                (*t)->left->left = (*t)->left->right = NULL; //Очищаем память для следующего роста
            }
                          
            
        }
    }
}
 
 
 
/*ФУНКЦИЯ ОТОБРАЖЕНИЯ ДЕРЕВА НА ЭКРАНЕ*/
/*void print1 (int u, bib *t) 
{
    if (t == NULL){ //Если дерево пустое, то отображать нечего, выходим
        return;
    }
    else //Иначе
    {
    print1(++u, t->left);//С помощью рекурсивного посещаем левое поддерево
    cout << endl;
    cout << "UDK   " << t->udk << endl; //И показываем элемент
    cout <<"FIO of the author   " << t->fio << endl;
    cout <<"The title of the book   " << t->title << endl;
    cout <<"The year of release   " << t->year << endl;
    cout <<"The quantity of such books   " << t->kolvo << endl;
    u--;
    }
    print1(u++, t->right); //С помощью рекурсии посещаем правое поддерево
}*/
 
 
 
void Find(bib *root, int d, bib *k, int h) {
    bib *pv = root, *prev;
    bool found = false;
    while (pv && !found) { 
        prev = pv;
        if (d == pv->id) {
            found = true;
            cout << "the book has just been found" << endl;
            cout << "UDK:  " << pv->udk[30] << endl;
            cout << "FIO:  " << pv->fio[50] << endl;
            cout << "TITLE:   " << pv->title[250] << endl;
            cout << "YEAR:   " << pv->year << endl;
            cout << "QUANTITY:   " << pv->kolvo << endl;
            
            strcpy (k[h].fio, pv->fio);
            strcpy (k[h].udk, pv->udk);
            strcpy (k[h].title, pv->title);
            k[h].year = pv->year;
            k[h].kolvo = pv->kolvo;
            
        } else if (d < pv->id) {
            pv = pv->left;
        } else {
            pv = pv->right;
        }
    }
    if (found == false) cout << "Not found" << endl;
}
 
 
 
// Обход дерева
void print_tree2(bib *p, int level) {
    if (p != 0) {
        print_tree2(p->right, level + 1);
        for (int i = 0; i < level; i++) cout << "\t";
        cout << p->id << endl;
        print_tree2(p->left, level + 1);
    }
}
 
 
int getTreeSize(bib *root){
                if (!root) return 0;
                return getTreeSize(root->left)+getTreeSize(root->right);
            }
 
 
 
bib *del(bib *tree)
{
    if (tree->id)           //  дерево состоит из одной вершины
    {
        delete tree; 
    }
    else 
        if( tree->left == NULL )        //  левое поддерево пусто
        {
            bib *r = tree->right;           //  сохраняем указатель на правое поддерево
            *tree = *r;                 //  копируем состояние узла находящегося справа
            r->left = 0;            //  удаляем узел
            r->right = 0;
            delete r;
        } 
    else                //  левое поддерево не пусто -> ищем узел являющийся самым правым в левом поддереве
    {
        bib *c = tree->left;//  самый правый узел
        bib *p = tree->left;//  родитель самого правого узла
        while (c->right)            //  двигаемся по правой ветви левого поддерева
        {
            p = c;
            c = c->right;
        }
        p->right = c->left;     //  левое поддерево самого правого узла становиться правым поддеревом родителя
        c->left = NULL;         //  рвем отношение
        tree->id = c->id;       //  переносим ключ
        delete c;// удаляем самый правый узел
        }
        return tree;
}
 
 
 
bib* find_for_del(bib *tree, int s)
{
    if (tree == NULL)     //    если достигли листа, то узла с данным ключем не существует
        return 0;
    if (tree->id < s)           //  если ключ текущего узла меньше искомого
    {
        tree->right = find_for_del(tree->right, s); //  идем по правой ветке
        return tree;
    }
    else
    {
        if (s < tree->id)         //    если ключ текущего узла больше искомого
        {
            tree->left = find_for_del(tree->left, s);    // идем по левой ветке
            return tree;
        }
    }
    return del(tree);         //    ключ текущего узла равен искомому - удаляем
}
    
 
int main()
{ 
    
    int s, n;
    bib* tree = NULL;
    int q;
 
    do {   
        cout << "Choose the action" << endl;
        cout << "1 - to create" << endl;
        cout << "2 - to add" << endl;
        cout << "3 - to delete" << endl;
        cout << "4 - to find" << endl;
        cin >> q;
        
        switch(q) 
        {
        case 1: 
            cout << "Enter the quantity of books" << endl;
            cin >> n;
            for (int i = 0; i < n; i++){
                cout << "Enter the id of this book" << endl;
                cin >> s;
                push (s, &tree);
            }
            cout << endl;
            cout << "books" << endl;
            cout << endl;
            //print1 (0, tree);
            print_tree2(tree, 0);
            break;
        
        case 2: 
            cout << "Enter the id of this book" << endl;
            cin >> s;
            push (s, &tree);
            cout << "Finally  " << endl;
            print_tree2(tree, 0);
            break;
        
        case 3: 
            cout << "The tree before deleting   " << endl;
            print_tree2(tree, 0);
            cout << "Enter the id for the book you want to delete" << endl;
            cin >> s;
            tree = find_for_del(tree, s);
            cout << "Finally  " << endl;
            //print_tree2(tree, 0);
            break;
 
        case 4: 
print_tree2(tree, 0);
            int z = 0;
            z = getTreeSize(tree);  //посчитать кол-во элементов, нужных для сортировки
            
            cout << "z" << z << endl;
            bib *p = new bib[z];
            
            cout << "Enter the id of the book" << endl;
            cin >> s;
            int h = 0;
            if (tree != 0) {
                Find (tree, s, p, h);
                h++;
            }
 
            for (int k = 0; k < (z - 1); k++)           
            {
                for (int w = k + 1; w < z; w++)      
                {
                    if (p[k].year > p[w].year)           
                    {
                        int t = p[k].year;
                        int kol = p[k].kolvo;
                        char fam[50];
                        strcpy (fam, p[k].fio);
                        char num[30];
                        strcpy (num, p[k].udk);
                        char tit[250];
                        strcpy (tit, p[k].title);
                        
                        p[k].year = p[w].year;
                        p[k].kolvo = p[w].kolvo;
                        //s[k].fio = s[w].fio;
                        strcpy (p[k].fio, p[w].fio);
                        //s[k].udk = s[w].udk;
                        strcpy (p[k].udk, p[w].udk);
                        //s[k].title = s[w].title;
                        strcpy (p[k].title, p[w].title);
                        
                        p[w].year = t;
                        p[w].kolvo = kol;
                        strcpy (p[k].fio, fam);
                        strcpy (p[k].udk, num);
                        strcpy (p[k].title, tit);
                    }
                }
            } 
            for (int j = 0; j < z; j++)
            {
                cout << "The author:    " << p[j].fio << endl;
                cout << "The UDK:     " << p[j].udk << endl;
                cout << "The title:     " << p[j].title << endl;
                cout << "The of the release:    " << p[j].year << endl;
                cout << "The quantity of such books in our library:   " << p[j].kolvo << endl;
                cout << endl;
            }
            break;
        }
    } while (q != 5);
    return 0;
}
Сначала я в виде ключа использовала год издания, но потом поняла, что он требуется для сортировки, а значит одинаковых лет может быть много... И простым увеличиванием количества книг данного года издания не обойдешься...
И решила сделать еще одно id-поле, т.е. ключевое. И тут возникают проблемы
С созданием дерева все в порядке - работает. С добавлением тоже нормально.
Зато в функции удаления есть какая-то ошибка - элемент удаляется, но если я хочу вывести после этого дерево на экран - программа прекращает работу (поэтому я функцию вывода закомментила). Если же ничего не выводим, то если я после удаления добавляю элемент, то он почему-то встает и на свое законное, нужное место, и на место только что удаленного... Ума не приложу, почему???
А вот вторая, наверно, более глобальная, проблема с поиском и сортировкой. просто не укладывается в голове, что же делать с деревом... Ну, поиск еще вроде понятно, но как с помощью него сортировать... по-моему, у меня какой-то балаган с 4 случаем
Помогите разобраться, пожалуйста)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.12.2013, 20:25     Бинарные деревья
Посмотрите здесь:

C++ бинарные деревья
Бинарные деревья C++
Бинарные деревья C++
Бинарные деревья C++
Бинарные деревья C++
C++ Бинарные деревья
бинарные деревья С++ C++
Бинарные деревья C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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