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

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

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

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

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

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

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

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

Исходное бинарное дерево превратить в бинарное дерево поиска, при этом сохранив его структуру - C++
Помогите, не могу понять!( Нужно исходное бинарное дерево превратить в бинарное дерево поиска, при этом сохранив его структуру. вот...

Бинарное дерево поиска - C++
Вот задали лабораторною работу. Сделал бинарное дерево поиска. Выдает ошибку "Что послан сигнал от операционной системы на завершение...

Бинарное дерево поиска - C++
Дали такую задачу: Дан набор попарно не равных целых чисел, по ним строится бинарное дерево поиска. Нужно осуществить обход дерева и...

Бинарное дерево поиска - C++
В текстовом файле содержится произвольный текст. Построить на его основе бинарное дерево поиска, каждый узел которого содержит слово....

Бинарное дерево поиска C++ - C++
+Доброго времени суток! У меня есть задание:создать картотеку,в ней указать тип магазина,номер магазина,ключ,и адрес магазина.Такое...

Бинарное дерево поиска - C++
Помогите пожалуйста.. Нужна программа "бинарные деревья поиска".. и если можно объяснение.. спасибо заранее...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
get_lost
0 / 0 / 0
Регистрация: 05.05.2010
Сообщений: 15
05.01.2011, 10:46  [ТС] #2
ну помогите же чем нибудь
0
Manjak
269 / 175 / 7
Регистрация: 12.03.2010
Сообщений: 494
05.01.2011, 11:14 #3
А тут те же числа, каждый знак зодиака - это период от дня Х до дня У, например, Овен 21 марта — 20 апреля
1
easybudda
Модератор
Эксперт CЭксперт С++
9632 / 5580 / 948
Регистрация: 25.07.2009
Сообщений: 10,714
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;
}
Бинарное дерево поиска знаков зодиака
1
Байт
Эксперт C
16062 / 10331 / 1540
Регистрация: 24.12.2010
Сообщений: 19,471
05.01.2011, 23:25 #5
Все это чрезвычайно просто.
Берем долготу Солнца и делим ее на 30. Результат присваиваем переменной типа int или short или даже char. 0 - Овен, 1 - телец и т.д.
Правда, для этого надо уметь считать эфемериды, учитывать временную поправку относительно гринвича, неравномерность вращения Земли вокруг собственной оси, абберацию, искривление светового луча под воздействием гравитации и кое-то еще.
2
Day
1158 / 963 / 57
Регистрация: 29.10.2009
Сообщений: 1,385
05.01.2011, 23:30 #6
А лунные дни не нужны ли? Для этого еще надо знать широту местности.
Со всем этим прекрасно справляется программа Uranus.
Гугль в помощь!
2
get_lost
0 / 0 / 0
Регистрация: 05.05.2010
Сообщений: 15
13.01.2011, 14:11  [ТС] #7
спасибо большое за помощь. Вы не могли бы со структурами переделать , а то классы не знаю , тем самым для меня этот код не понятен
0
get_lost
0 / 0 / 0
Регистрация: 05.05.2010
Сообщений: 15
14.01.2011, 17:45  [ТС] #8
Цитата Сообщение от get_lost Посмотреть сообщение
спасибо большое за помощь. Вы не могли бы со структурами переделать , а то классы не знаю , тем самым для меня этот код не понятен
пожалуйста помогите
0
get_lost
0 / 0 / 0
Регистрация: 05.05.2010
Сообщений: 15
17.01.2011, 15:55  [ТС] #9
или сделайте пожалуйста пояснение к коду .Век буду благодарен
0
easybudda
Модератор
Эксперт CЭксперт С++
9632 / 5580 / 948
Регистрация: 25.07.2009
Сообщений: 10,714
17.01.2011, 18:35 #10
Цитата Сообщение от get_lost Посмотреть сообщение
сделайте пожалуйста пояснение к коду
Там много всего, напишите, с какого момента не понятно. В общем случае:
Класс Date символизирует дату в виде (месяц, день) и содержит кучу переопределённых операторов сравнения.
Класс Sign определяет знак зодиака, содержит название, дату начала, дату окончания и два указателя - один на знак, идущий перед данным, второй - на знак, идущий после данного.
Класс Tree - собственно дерево, узлами которого являются объекты класса Sign.
Ну а дальше всё просто - в основной программе создаётся дерево, запихиваются в него описания знаков (кстати, в таком виде, как у меня, дерево будет скорее упорядоченный массив напоминать, который от центра заполняется, лучше в него знаки вообще без всякой системы заряжать, ну или по-взрослому морочиться с балансировкой...). Запрашивается дата у пользователя и по ней отыскивается соответствующий узел в дереве.
Самая серьёзная засада со знаком "Козерог" была - он начинается в конце года, а заканчивается в начале следующего. Пришлось для него тринадцатый месяц сделать...
1
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() );
        }
};
0
easybudda
Модератор
Эксперт CЭксперт С++
9632 / 5580 / 948
Регистрация: 25.07.2009
Сообщений: 10,714
17.01.2011, 18:51 #12
Цитата Сообщение от get_lost Посмотреть сообщение
bool correct()
проверяет введённую дату на корректность - номер месяца от 1 до 12, номер дня не меньше одного и не больше количества дней в соответствующем месяце. Имеет смысл использовать только для проверки того, что ввёл пользователь (помним про козерога...)
Всё остальное -
Цитата Сообщение от easybudda Посмотреть сообщение
и содержит кучу переопределённых операторов сравнения.
операторы сравнения двух дат. Собственно на сравнении дат основано сравнение знаков зодиака, а соответственно - размещение и поиск их в дереве...
1
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!";
        }
};
0
easybudda
Модератор
Эксперт CЭксперт С++
9632 / 5580 / 948
Регистрация: 25.07.2009
Сообщений: 10,714
18.01.2011, 17:30 #14
get_lost,
1. Конструктор по умолчанию, который инициализирует указатель mp_root нулём и больше ничего не делает. И деструктор, который в случае, если корневой узел не пустой, его (узел) удаляет, а он (узел) в силу своих конструктивных особенностей за одно и все прикреплённые удаляет (ну должен бы по задумке)...
2. Если дерево пустое - просто создаётся новый корневой узел. Если не пустое - вызывается функция addSign(), которая сама разбирается, с какого бока новый узел прилепить.
3. Функция ищет попадание заданного числа в диапазон чисел какого-нибудь из знаков. Если сразу ничего не нашлось, присваивает месяцу искомой даты значение 13 и пробует ещё раз (помним про козерогов). Если снова ничего не нашлось, возвращает строку с ошибкой, если нашлось (с первой или второй попытки) - возвращается название знака.
1
get_lost
0 / 0 / 0
Регистрация: 05.05.2010
Сообщений: 15
18.01.2011, 17:46  [ТС] #15
easybudda,


огромное спасибо , сел учить классы
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.01.2011, 17:46
Привет! Вот еще темы с ответами:

Бинарное дерево поиска - C++
Давайте рассмотрим некоторый пример Допустим есть числа от 0 до 99 которые добавляются в бинарное дерево Элементы в бинарное дерево...

Бинарное дерево поиска - C++
Решил написать бинарное дерево поиска, но что-то пошло не так, дерево не выводиться не понимаю почему. Вот весь код: #include...

Бинарное дерево поиска - C++
#include &lt;iostream&gt; using namespace std; struct node { int key; node *left; node *right; node *p;

Бинарное дерево поиска - C++
Всем привет! Не могу понять одну вещь. Есть вот такой код для заполнения бинарного дерева: #include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; ...


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

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

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