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

Бинарное идеально-сбалансированное дерево - C++

Восстановить пароль Регистрация
 
demigod324
4 / 2 / 0
Регистрация: 17.03.2013
Сообщений: 102
01.06.2014, 23:07     Бинарное идеально-сбалансированное дерево #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
#include <iostream.h>
#include <conio.h>
#include <stdlib.h>
struct traine {                    //структура - дерево
    unsigned long time;            //время отправления в секундах
    unsigned short number;        //номер поезда
    char *station;                //имя станции
    traine *left,*right;};        //указатели на левую и правую ветку дерева
traine* add(traine *beg, unsigned short number, unsigned long time, char station[50])    //функция добавления элемента в дерево
{
    if (!beg) {                        //если дерево пустое
        traine *temp=new traine;
        temp->number=number;
        temp->time=time;
        temp->station = new char[];
        temp->station=station;
        temp->left=0;
        temp->right=0;
        return temp;
    }                //если дерево не пустое, начинается рекурсивный вход в него
    else if ((number)>(beg->number)) {    //бОльшие номера идут в правое поддерево
        beg->right=add(beg->right,number, time, station);
        return beg;
    }
    else {        //меньшие номера идут в левое поддерево
        beg->left=add(beg->left,number, time, station);
        return beg;}
}
void show_all(traine *temp){    //функция вывода всего дерева - рекурсивный обход слева направо
    unsigned long d,h,m,s,t;
    if (temp){
        show_all(temp->left);
        t=temp->time;s=t%60;t=(t-s)/60;m=t%60;t=(t-m)/60;h=t%24;d=(t-h)/24;//разложение времени на дни, часы, минуты и секунды
        cout << "Train number:" << temp->number << endl << "Start time(d/h/m/s):" << d << ":" << h << ":" << m << ":" << s << endl << "Station:" << temp->station << endl;
        show_all(temp->right);}
}
void show_number(traine *temp, unsigned short number){ //поиск элемента с нужным номером, с учётом отсортированности дерева
    unsigned long d,h,m,s,t;
    if (temp){
        if (temp->number<number) {show_number(temp->right,number);}
        else if (temp->number>number) {show_number(temp->left,number);}
        else{
        t=temp->time;s=t%60;t=(t-s)/60;m=t%60;t=(t-m)/60;h=t%24;d=(t-h)/24;
        cout << "Train number:" << temp->number << endl << "Start time(d/h/m/s):" << d << ":" << h << ":" << m << ":" << s << endl << "Station:" << temp->station << endl;
        return;}
    }
        cout << "There is no such records\n";}
void show_station(traine *temp, char st[50],bool &f){ //переменная f нужна для определения, был ли найден хотя бы 1 поезд, т.к. обход производится "втупую", т.к. дерево сортировано не по имени станции
    if (temp){
        if (st == (temp->station)) //если найден подходящий поезд
        {
            f=1;
            unsigned long d,h,m,s,t,f;
            t=temp->time;s=t%60;t=(t-s)/60;m=t%60;t=(t-m)/60;h=t%24;d=(t-h)/24;
            cout << "Train number:" << temp->number << endl << "Start time(d/h/m/s):" << d << ":" << h << ":" << m << ":" << s << f<<endl << "Station:" << temp->station << endl << endl;
        }
        show_station(temp->right,st,f); //просмотр правого поддерева
        show_station(temp->left,st,f);    //просмотр левого поддерева
    }
}
int main() {    //главная функция
    char k;        //временная переменная для чтения 1 символа для выбора пунктов меню
    bool f;        //переменная для использования с функцией поиска по имени станции
    char strtmp[80];    //временная переменная для чтения с клавиатуры
    traine *list=0;    //дерево, изначально являющееся пустым
    unsigned short d,h,m,s;    //переменные для разложения времени на дни, часы, минуты и секунды
    unsigned short number;    //временный номер
    char station[30];    //временная станция
    do{//главный цикл меню
    cout << "Enter your choice:\n[1] Add new record\n[2] View all records\n[3] View a specific train number\n[4] View all trains aimed to a specified station\n[0] Exit program\n";
    do{
    cin >> k;//ввод выбора (а далее всё понятно и так)
    if (k=='1'){
        do{
            cout << "Train number:\n";
            cin >> strtmp;
            number=atoi(strtmp);
        }while (!(number>0));
        do{
            cout << "Number of days:\n";
            cin >> strtmp;
            d=atoi(strtmp);
            cout << "Number of hours:\n";
            cin >> strtmp;
            h=atoi(strtmp);
            cout << "Number of minutes:\n";
            cin >> strtmp;
            m=atoi(strtmp);
            cout << "Number of seconds:\n";
            cin >> strtmp;
            s=atoi(strtmp);
        }while(d==0 && h==0 && m==0 && s==0);
        cout << "Station name:\n";
        cin >> station;
        list=add(list,number,s+m*60+h*3600+d*86400,station);
            
    }
    else if (k=='2'){
        if (list){
            show_all(list);}
        else {cout << "There is no trains\n";}}
    else if (k=='3'){
        cout << "Enter a train number:";
        do{
            cin >> strtmp;
            number=atoi(strtmp);
        }while (!(number>0));
        show_number(list,number);}
    else if (k=='4'){
        cout << "Enter a station name:";
        cin >>station;
        f=0;
        show_station(list,station,f);
        if (!f) {cout << "There is no trains\n";}
    }
    }while (!((k=='4')||(k=='3')||(k=='2')||(k=='1')||(k=='0')));
    }while (!(k=='0'));
    return 1;}
Но здесь данные были организованы в виде двоичного дерева. Помогите переделать на бинарное идеально-сбалансированное дерево.
И еще, вылезает ошибка:
C++
1
[C++ Error] Unit1.cpp(15): E2453 Size of the type 'char[]' is unknown or zero
Как её исправить?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.06.2014, 23:07     Бинарное идеально-сбалансированное дерево
Посмотрите здесь:

C++ Сбалансированное дерево (бинарное)
C++ Сбалансированное дерево
C++ Сформировать идеально сбалансированное бинарное дерево
Идеально сбалансированное дерево C++
Идеально сбалансированное дерево C++
C++ Идеально сбансированное дерево
Сбалансированное бинарное дерево. Структуры даннных C++
Идеально сбалансированное дерево C++

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

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

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