С Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Переписать код програмы с QBasic в C++ http://www.cyberforum.ru/cpp-beginners/thread1195978.html
' Объявим константы: CONST pi = 3.141592653589793# CONST Gradus = pi / 180, RAD = 180 / pi ' Углы обзора CONST OBZORh = 40 * Gradus, OBZORv = 33 * Gradus ' Разрешение экрана ...
C++ Запуск проекта Доброго времени суток) Какие библиотеки directx нужно подгрузить для запуска проекта? http://www.cyberforum.ru/cpp-beginners/thread1195975.html
C++ Сумма ряда, не совпадает с проверкой
Вычисление суммы ряда (цикл) и проверка (т.е. вычисление арктангенса ) не совпадают. Помогите найти ошибку, пожалуйста. // 3.cpp: определяет точку входа для консольного приложения. // ...
C++ Нужно перевести задачу с делфи на с++
Помогите перевести задачу с делфи на с++. Срочно нужно. unit Unit1; interface uses Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls; type TForm1 =...
C++ Чтение данных из файла http://www.cyberforum.ru/cpp-beginners/thread1195964.html
Мне нужно прочитать с фаила и сделать запросы... Но как это сделать? помогите, пожалуйста... #include "stdafx.h" #include <iostream> #include <fstream> #include <iomanip> #include "conio.h"...
C++ Передача enum в качестве аргумента метода класса Есть класс //class order; class ticket{ enum type_of_place { coupe, general, berth, wagon_lit }_type_of_place; char* dispatch_station; char* arrival_station; char* departure_date; char*... подробнее

Показать сообщение отдельно
demigod324
4 / 2 / 0
Регистрация: 17.03.2013
Сообщений: 104

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

01.06.2014, 23:07. Просмотров 283. Ответов 0
Метки (Все метки)

Есть такое условие для задачи.
Автоматизированная информационная система на железнодорожном вокзале содержит сведения об отправлении
поездов дальнего следования. Для каждого поезда указывается:
- номер поезда;
- станция назначения;
- время отправления.
Данные в системе организовать в виде бинарного идеально-сбалансированного дерева.
Написать программу, которая:
- обеспечивает первоначальный ввод данных и формирование дерева;
- производит вывод всего дерева;
- осуществляет поиск поезда по номеру с использованием симметричного обхода дерева.

Нашел в такую программу:
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
Как её исправить?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.