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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 14, средняя оценка - 4.64
get_lost
0 / 0 / 0
Регистрация: 05.05.2010
Сообщений: 15
#1

Бинарное дерево поиска знаков зодиака - C++

25.12.2010, 17:30. Просмотров 1696. Ответов 14
Метки нет (Все метки)

Помогите с задачей .Нужно построить бинарное дерево поиска знаков зодиака используя структуры.При вводе определенной даты , нужно чтобы выводило соответствующий знак зодиака.

Вообщем когда строил бинарное дерево с числовыми значениями у меня не возникало трудностей найти и вывести элемент , т.к там всего 1 информационное поле т.е найти элемент было не сложно. А тут даже не знаю с какой стороны подойти

Добавлено через 19 минут
буду рад любой помощи )
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.12.2010, 17:30     Бинарное дерево поиска знаков зодиака
Посмотрите здесь:

C++ Бинарное (двоичное) дерево поиска
Вывести число вершин n-го уровня (Бинарное дерево поиска) C++
C++ Вставить новый элемент в бинарное дерево поиска
C++ Структура, по строкам построить бинарное дерево поиска
Бинарное дерево поиска C++
Бинарное дерево поиска (удаление, добавление элемента) C++
C++ Бинарное дерево поиска C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
get_lost
0 / 0 / 0
Регистрация: 05.05.2010
Сообщений: 15
05.01.2011, 10:46  [ТС]     Бинарное дерево поиска знаков зодиака #2
ну помогите же чем нибудь
Manjak
269 / 175 / 7
Регистрация: 12.03.2010
Сообщений: 494
05.01.2011, 11:14     Бинарное дерево поиска знаков зодиака #3
А тут те же числа, каждый знак зодиака - это период от дня Х до дня У, например, Овен 21 марта — 20 апреля
easybudda
Эксперт С++
9454 / 5467 / 926
Регистрация: 25.07.2009
Сообщений: 10,490
05.01.2011, 22:32     Бинарное дерево поиска знаков зодиака #4
во наговнокодил, но вроде работает...
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
#include <iostream>
#include <string>
#include <clocale>
#include <stdexcept>
 
const int DAYS_IN_MONTH[] = { 0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
 
class Date {
    int mi_month;
    int mi_day;
public:
    Date() : mi_month(1), mi_day(1) {}
    Date(int m, int d) : mi_month(m), mi_day(d) {}
    int month() const { return mi_month; }
    int day() const { return mi_day; }
    void month(int m) { mi_month = m; }
    void day(int d) { mi_day = d; }
    bool correct() const {
        return ( mi_month > 0 && mi_month < 13 && mi_day > 0 && mi_day <= DAYS_IN_MONTH[mi_month] );
    }
    bool operator < (const Date & another) const {
        return ( mi_month < another.month() || ( mi_month == another.month() && mi_day < another.day() ) );
    }
    bool operator > (const Date & another) const {
        return ( mi_month > another.month() || ( mi_month == another.month() && mi_day > another.day() ) );
    }
    bool operator == (const Date & another) const {
        return ( mi_month == another.month() && mi_day == another.day() );
    }
    bool operator <= (const Date & another) const {
        return ( *this < another || *this == another );
    }
    bool operator >= (const Date & another) const {
        return ( *this > another || *this == another );
    }
    // до кучи :)
    bool operator != (const Date & another) const {
        return ( mi_day != another.day() || mi_month != another.month() );
    }
};
 
class Sign {
    std::string ms_name;
    Date md_start;
    Date md_end;
    Sign * mp_left;
    Sign * mp_right;
public:
    Sign(std::string n, Date s, Date e) : ms_name(n), md_start(s), md_end(e), mp_left(0), mp_right(0) {
        if ( md_start > md_end )
            md_end.month(13);
    }
    Sign(const Sign & another) : ms_name(another.ms_name), md_start(another.md_start), md_end(another.md_end),
        mp_left(0), mp_right(0) {}
    ~Sign(){
        if ( mp_left )
            delete mp_left;
        if ( mp_right )
            delete mp_right;
    }
    std::string name() const { return ms_name; }
    void name(std::string n) { ms_name = n; }
    Date startDate() const { return md_start; }
    Date endDate() const { return md_end; }
    Sign * left() const { return mp_left; }
    void left(Sign * ps) { mp_left = ps; }
    Sign * right() const { return mp_right; }
    void right(Sign * ps) { mp_right = ps; }
    bool operator < (const Sign & another) const {
        return ( md_end < another.md_start );
    }
    bool operator > (const Sign & another) const {
        return ( md_start > another.md_end );
    }
    bool operator == (const Sign & another) const {
        return ( md_start >= another.md_start && md_end <= another.md_end );
    }
};
 
class Tree {
    Sign * mp_root;
    void addSign(Sign * ptr, const Sign & val){
        if ( ! ptr )
            throw std::runtime_error("Null pointer!");
        
        if ( *ptr > val ){
            if ( ptr->left() ){
                addSign(ptr->left(), val);
            }
            else {
                ptr->left(new Sign(val));
            }
        }
        else if ( *ptr < val ){
            if ( ptr->right() ){
                addSign(ptr->right(), val);
            }
            else {
                ptr->right(new Sign(val));
            }
        }
        else
            throw std::runtime_error("Doubling signs!");
    }
    Sign * findSign(Sign * ps, const Sign & test){
        if ( ! ps )
            return 0;
        else if ( test == *ps )
            return ps;
        else if ( test < *ps )
            return findSign(ps->left(), test);
        else if ( test > *ps )
            return findSign(ps->right(), test);
        else {
            std::cerr << "Date comparsion failed!" << std::endl;
            return 0;
        }
    }
    Tree(const Tree & another);
public:
    Tree() : mp_root(0) {}
    ~Tree() {
        if ( mp_root )
            delete mp_root;
    }
    void add(Sign s){
        if ( ! mp_root )
            mp_root = new Sign(s);
        else
            addSign(mp_root, s);
    }
    std::string signName(Date d){
        Sign * ps = findSign(mp_root, Sign("", d, d));
        if ( ! ps ){
            d.month(13);
            ps = findSign(mp_root, Sign("", d, d));
        }
        return ( ps ) ? ps->name() : "Not found!";
    }
};
 
int main(){
    setlocale(LC_ALL, "Russian");
 
    Tree z;
    z.add(Sign("Дева", Date(8, 24), Date(9, 23)));
    z.add(Sign("Лев", Date(7, 23), Date(8, 23)));
    z.add(Sign("Весы", Date(9, 24), Date(10, 23)));
    z.add(Sign("Рак", Date(6, 22), Date(7, 22)));
    z.add(Sign("Скорпион", Date(10, 24), Date(11, 22)));
    z.add(Sign("Близнецы", Date(5, 22), Date(6, 21)));
    z.add(Sign("Стрелец", Date(11, 23), Date(12, 21)));
    z.add(Sign("Телец", Date(4, 21), Date(5, 21)));
    z.add(Sign("Козерог", Date(12, 22), Date(1, 20)));
    z.add(Sign("Овен", Date(3, 21), Date(4, 20)));
    z.add(Sign("Водолей", Date(1, 21), Date(2, 19)));
    z.add(Sign("Рыбы", Date(2, 20), Date(3, 20)));
 
    int month, day;
    std::cout << "Вводите дату в формате Месяц День. 0 0 - выход" << std::endl;
    while ( true ){
        std::cout << "Дата: ";
        std::cin >> month >> day;
        if ( month < 1 || day < 1 )
            break;
        Date d(month, day);
        if ( ! d.correct() ){
            std::cerr << "Ошибка! Попробуйте ещё раз." << std::endl;
            continue;
        }
        std::cout << "Знак: " << z.signName(d) << std::endl;
    }
 
    return 0;
}
Бинарное дерево поиска знаков зодиака
Байт
Эксперт C
15551 / 9893 / 1487
Регистрация: 24.12.2010
Сообщений: 18,500
05.01.2011, 23:25     Бинарное дерево поиска знаков зодиака #5
Все это чрезвычайно просто.
Берем долготу Солнца и делим ее на 30. Результат присваиваем переменной типа int или short или даже char. 0 - Овен, 1 - телец и т.д.
Правда, для этого надо уметь считать эфемериды, учитывать временную поправку относительно гринвича, неравномерность вращения Земли вокруг собственной оси, абберацию, искривление светового луча под воздействием гравитации и кое-то еще.
Day
1154 / 959 / 57
Регистрация: 29.10.2009
Сообщений: 1,385
05.01.2011, 23:30     Бинарное дерево поиска знаков зодиака #6
А лунные дни не нужны ли? Для этого еще надо знать широту местности.
Со всем этим прекрасно справляется программа Uranus.
Гугль в помощь!
get_lost
0 / 0 / 0
Регистрация: 05.05.2010
Сообщений: 15
13.01.2011, 14:11  [ТС]     Бинарное дерево поиска знаков зодиака #7
спасибо большое за помощь. Вы не могли бы со структурами переделать , а то классы не знаю , тем самым для меня этот код не понятен
get_lost
0 / 0 / 0
Регистрация: 05.05.2010
Сообщений: 15
14.01.2011, 17:45  [ТС]     Бинарное дерево поиска знаков зодиака #8
Цитата Сообщение от get_lost Посмотреть сообщение
спасибо большое за помощь. Вы не могли бы со структурами переделать , а то классы не знаю , тем самым для меня этот код не понятен
пожалуйста помогите
get_lost
0 / 0 / 0
Регистрация: 05.05.2010
Сообщений: 15
17.01.2011, 15:55  [ТС]     Бинарное дерево поиска знаков зодиака #9
или сделайте пожалуйста пояснение к коду .Век буду благодарен
easybudda
Эксперт С++
9454 / 5467 / 926
Регистрация: 25.07.2009
Сообщений: 10,490
17.01.2011, 18:35     Бинарное дерево поиска знаков зодиака #10
Цитата Сообщение от get_lost Посмотреть сообщение
сделайте пожалуйста пояснение к коду
Там много всего, напишите, с какого момента не понятно. В общем случае:
Класс Date символизирует дату в виде (месяц, день) и содержит кучу переопределённых операторов сравнения.
Класс Sign определяет знак зодиака, содержит название, дату начала, дату окончания и два указателя - один на знак, идущий перед данным, второй - на знак, идущий после данного.
Класс Tree - собственно дерево, узлами которого являются объекты класса Sign.
Ну а дальше всё просто - в основной программе создаётся дерево, запихиваются в него описания знаков (кстати, в таком виде, как у меня, дерево будет скорее упорядоченный массив напоминать, который от центра заполняется, лучше в него знаки вообще без всякой системы заряжать, ну или по-взрослому морочиться с балансировкой...). Запрашивается дата у пользователя и по ней отыскивается соответствующий узел в дереве.
Самая серьёзная засада со знаком "Козерог" была - он начинается в конце года, а заканчивается в начале следующего. Пришлось для него тринадцатый месяц сделать...
get_lost
0 / 0 / 0
Регистрация: 05.05.2010
Сообщений: 15
17.01.2011, 18:46  [ТС]     Бинарное дерево поиска знаков зодиака #11
easybudda,

спасибо за отклик.

не понятен вот этот блок:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 bool correct() const {
                return ( mi_month > 0 && mi_month < 13 && mi_day > 0 && mi_day <= DAYS_IN_MONTH[mi_month] );
        }
        bool operator < (const Date & another) const {
                return ( mi_month < another.month() || ( mi_month == another.month() && mi_day < another.day() ) );
        }
        bool operator > (const Date & another) const {
                return ( mi_month > another.month() || ( mi_month == another.month() && mi_day > another.day() ) );
        }
        bool operator == (const Date & another) const {
                return ( mi_month == another.month() && mi_day == another.day() );
        }
        bool operator <= (const Date & another) const {
                return ( *this < another || *this == another );
        }
        bool operator >= (const Date & another) const {
                return ( *this > another || *this == another );
        }
        // äî ГЄГіГ·ГЁ :)
        bool operator != (const Date & another) const {
                return ( mi_day != another.day() || mi_month != another.month() );
        }
};
easybudda
Эксперт С++
9454 / 5467 / 926
Регистрация: 25.07.2009
Сообщений: 10,490
17.01.2011, 18:51     Бинарное дерево поиска знаков зодиака #12
Цитата Сообщение от get_lost Посмотреть сообщение
bool correct()
проверяет введённую дату на корректность - номер месяца от 1 до 12, номер дня не меньше одного и не больше количества дней в соответствующем месяце. Имеет смысл использовать только для проверки того, что ввёл пользователь (помним про козерога...)
Всё остальное -
Цитата Сообщение от easybudda Посмотреть сообщение
и содержит кучу переопределённых операторов сравнения.
операторы сравнения двух дат. Собственно на сравнении дат основано сравнение знаков зодиака, а соответственно - размещение и поиск их в дереве...
get_lost
0 / 0 / 0
Регистрация: 05.05.2010
Сообщений: 15
18.01.2011, 17:21  [ТС]     Бинарное дерево поиска знаков зодиака #13
easybudda,

большое вам спасибо за помощь .Вы не могли бы прокомменитровать еще и это :

C++
1
2
3
4
 Tree() : mp_root(0) {}
        ~Tree() {
                if ( mp_root )
                        delete mp_root;
как я понял это деструктор узла дерева , перед повторным поиском ?
}
C++
1
2
3
4
5
6
void add(Sign s){
                if ( ! mp_root )
                        mp_root = new Sign(s);
                else
                        addSign(mp_root, s);
        }

s
C++
1
2
3
4
5
6
7
8
9
td::string signName(Date d){
                Sign * ps = findSign(mp_root, Sign("", d, d));
                if ( ! ps ){
                        d.month(13);
                        ps = findSign(mp_root, Sign("", d, d));
                }
                return ( ps ) ? ps->name() : "Not found!";
        }
};
easybudda
Эксперт С++
9454 / 5467 / 926
Регистрация: 25.07.2009
Сообщений: 10,490
18.01.2011, 17:30     Бинарное дерево поиска знаков зодиака #14
get_lost,
1. Конструктор по умолчанию, который инициализирует указатель mp_root нулём и больше ничего не делает. И деструктор, который в случае, если корневой узел не пустой, его (узел) удаляет, а он (узел) в силу своих конструктивных особенностей за одно и все прикреплённые удаляет (ну должен бы по задумке)...
2. Если дерево пустое - просто создаётся новый корневой узел. Если не пустое - вызывается функция addSign(), которая сама разбирается, с какого бока новый узел прилепить.
3. Функция ищет попадание заданного числа в диапазон чисел какого-нибудь из знаков. Если сразу ничего не нашлось, присваивает месяцу искомой даты значение 13 и пробует ещё раз (помним про козерогов). Если снова ничего не нашлось, возвращает строку с ошибкой, если нашлось (с первой или второй попытки) - возвращается название знака.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.01.2011, 17:46     Бинарное дерево поиска знаков зодиака
Еще ссылки по теме:

Бинарное дерево поиска (определить максимальную глубину) C++
C++ Бинарное дерево поиска
Бинарное дерево поиска.Вывести слова с тремя гласными C++
C++ Бинарное дерево поиска
Бинарное дерево поиска C++

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

Или воспользуйтесь поиском по форуму:
get_lost
0 / 0 / 0
Регистрация: 05.05.2010
Сообщений: 15
18.01.2011, 17:46  [ТС]     Бинарное дерево поиска знаков зодиака #15
easybudda,


огромное спасибо , сел учить классы
Yandex
Объявления
18.01.2011, 17:46     Бинарное дерево поиска знаков зодиака
Ответ Создать тему
Опции темы

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