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

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

Войти
Регистрация
Восстановить пароль
 
Julia9311
3 / 3 / 0
Регистрация: 05.11.2011
Сообщений: 190
#1

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

11.06.2012, 17:32. Просмотров 367. Ответов 0
Метки нет (Все метки)

Эта программа, которая содержит текущую информацию о заявках на авиабилеты. Каждая заявка включает:
• пункт назначения;
• номер рейса;
• фамилию и инициалы пассажира;
• желаемую дату вылета.
Программа обеспечивает:
• хранение всех заявок в виде списка;
• добавление и удаление заявок;
• по заданному номеру рейса и дате вылета вывод заявок с их последующим удалением;
• вывод всех заявок.


C++ (Qt)
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
#include <iostream>
#include <locale>
#include <ctime>
#include <string>
using namespace std;
 
struct Aviabileti
 
{
 char punkt_naznachenia[51];
 int nomer_reysa;
 char  fio[51];
 char jelayemaia_data[21];
};
 
int main()
{
int flag=1, i=0, reg, kol=7;
Aviabileti mas[61]; 
 
while (f==1)
 
{
    cout<<"1.Vvod dannix ";
    cout<<"2.Poisk po reysu i date vileta ";
    cout<<"3.Vivod zayavok ";
    cout<<"4.Udaleniye zayavok ";
 
    //добавление данных в массив
    if(reg==1)
{
        for(i=0;i<kol;i++)
        cout<<"Vvedite punkt naznacheniya ";
        cin>>(mas[i].punkt_naznachenia);
        cout<<"Vvedite nomer reysa ";
        cin>>mas[i].nomer_reysa);
        cout<<"Vvedite fio passagira ";
        cin>>(mas[i].fio);
        cout<<"Vvedite datu vileta ";
        cin>>(mas[i].jelayemaia_data);
 
        
        }
 
    if(reg==3)
 
    {
//сортировка значений
int j, min, p1,pp, pp2, temp;
for(i=0;i<kol;i++)
{
min=mas[i].nomer_reysa;
p1=i;
for(j=i;j<kol;j++)
if(mas[j].nomer_reysa<min)
{
min=mas[j].nomer_reysa;
p1=j;
}
temp=mas[i].nomer_reysa;
mas[i].nomer_reysa=mas[p1].nomer_reysa;
mas[p1].nomr_reysa=temp;
strcpy(temp, mas[i].punkt_naznachenia);
strcpy(mas[i].punkt, mas[p1].punkt);
strcpy(mas[p1].punkt_naznachenia,temp);
strcpy(temp, mas[i].tip_samoleta);
strcpy(mas[i].tip_samoleta, mas[p1].tip_samoleta);
strcpy(mas[p1].tip_samoleta, temp);
}
 
for(i=0;i<kol;i++)
        {
        cout<<"Zapis "<<i;
        cout<<"Punkt naznacheniya "<<mas[i].punkt_naznachenia;
        cout<<"Nomer reysa "<<mas[i].nomer_reysa;
        cout<<"Fio passagira "<<mas[i].fio;
        cout<<"Jelaemaya data "<<mas[i].jelayemaia_data;
        }
        }
 
//поиск по рейсу и дате вылета
        if(reg==2)
        {
            cout<<"Vvedite nomer reysa dlya poiska ";
            cin>>pp;
            cout<<"Vvedite datu vileta dlya poiska ";
            cin>>pp2;
            cout<<"Rezultat poiska ";
            fl=0;
        for(int i=0;i<kol;i++)
        {
            if(strcmp(pp2,mas[i].jelayemaia_data, mas[i].nomer_reysa)==0);
            {
        cout<<"Zapis "<<i;
        cout<<"Punkt naznacheniya "<< mas[i].punkt_naznachenia;
        cout<<"Nomer reysa "<<mas[i].nomer_reysa;
        cout<<"Fio passagira "<<mas[i].fio;
        cout<<"Jelayemaia data "<<mas[i].jelayemaia_data;
        
        
            }
        }
 
        if(fl==0)
        cout<<"Biletov s takim punktom naznacheniya net ";
 
        }

двоичное дерево

C++ (Qt)
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
#include <iostream>
#include <conio.h>
#include<time.h>
using namespace std;
 
struct Node
{
    int d;         //Данные элемента
    Node *left;    //Ссылка на левое поддерево
    Node *right;   //Ссылка на правое поддерево
};
Node *first(int d);                    //Формирование первого элемента
Node *search_insert(Node *root, int d); //Поиск с включением
void print_tree(Node *root, int l);     //Обход дерева
 
//-------------------------------------------
void main()
{
    srand(time(0));
    setlocale(0,"Rus");
    int n;             //количество элементов в дереве
    cout << "Введите n: ";
    cin >> n;
    int *b = new int[n];
    cout << "Сгенерированная последовательность: " << endl << endl;
    for(int i = 0; i < n; i ++)
    {
        b[i] = 1 + rand()%100;
        cout << b[i] << " ";
    }
    cout << "\nДерево: " << endl << endl;
    Node *root = first(b[0]);    //Формируем корень дерева
    //Ищем место куда вставить и вставляем новые элементы
    for(int i = 1; i < n; i ++)
    {
        search_insert(root,b[i]);
    }
    print_tree(root,0);            //вывод дерева на экран
    
    int k;               //значения, которые больше заданного к будут удалены
    cout<<"Введите k: "; 
    cin>>k;
    for(int i=0;i<n;i++)
    {
        if(b[i] > k)
        {
            b[i]=-1;
        }
    }
    int o;
    int x=0;
for(int i = 0; i < n; i ++)
    {
        if(b[i]!=-1)
        {
            o=i;
            break;
        }
        else x++;
    }
    if(x==n)
    {
        cout<<"Дерево пустое";
        getch();
        exit(1);
    }
    cout << "\nНовое дерево: " << endl << endl;
    Node *root1 = first(b[o]);
    for(int i = 1; i < n; i ++)
    {
        if(b[i]!=-1)
        {
            search_insert(root1,b[i]);
        }
    }
    print_tree(root1,0);
    delete b;
    getch();
}
 
//--------------------------------------------
//Формирование первого элемента
Node *first(int d)
{
    Node *pv = new Node;      //Создаём элемент
    pv -> d = d;              //Присваиваем значение элементу поля
    pv -> left = 0;           //Ссылка на левое поддерево равна NULL
    pv -> right = 0;          //Ссылка на правое поддерево равна NULL
    return pv;               //Возвращаем адрес элемента
}
 
//---------------------------------------------
 
 
 
//Поиск с включением
Node *search_insert(Node *root,int d)
{
    Node *pv = root, *prev;
    bool found = false;    //Переменная отвечающая за то что нашли ли элемент или нет
    /*Ниже приведён алгоритм поиска, если нашли такой же элемент то мы его не вставляем в дерево выходим из функции возвратив адрес совпавшего элемента*/
    while(pv&&!found)
    {
        prev = pv;                       //получаем адрес элемента от которого будем пускать корни
        if(d == pv -> d)found = true;        //совпадение выходим из цикла
        else if(d < pv -> d)pv = pv -> left;   //Всовываемя в левое поддерево
        else pv = pv -> right;             //Всовываемя в правое поддерево 
//Выход из цикла осуществляется, тогда когда нашли свободный адрес : ссылку у дерева : для вставки нового узла */
    }
//---------------------------
/*Если совпало значение элемента со значением элемента который хотим вставить то выходим из функции возвращая адрес элемента
с которым совпало */
    if(found)return pv;               
    //Создание нового узла
    Node *pnew = new Node;
    pnew -> d = d;
    pnew -> left = 0;
    pnew -> right = 0;
    if(d < prev -> d)
    //Присоединение к левому поддереву предка
    prev -> left = pnew;
    else 
    //присоединяем к правому поддереву предка
    prev -> right = pnew;
    return pnew;
}
//---------------------------------------
//Обход дерева
void print_tree(Node *p,int level)
{
    if(p)
    {
        print_tree(p -> left, level + 1);           //Перемещение по левым поддеревьям
        for(int i = 0; i < level; i ++)cout<<"   ";
        cout << p -> d << '\n';                      //вывод значений дерева
        print_tree(p -> right, level + 1);          //Перемещение по правым поддеревьям        
     }
}

нужно как-то соединить эти две программы так, чтобы вместо хранения всех заявок в виде списка было хранение всех заявок в виде двоичного дерева. Но у самой не получается сделать! Помогите, пожалуйста!
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.06.2012, 17:32
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Из списка в двоичное дерево (C++):

Двоичное дерево - C++
Помогите найти ошибку, в консоль вообще ничего не выводится: #include&lt;iostream&gt; #include&lt;string&gt; #include&lt;fstream&gt; using...

Двоичное дерево - C++
Здравствуйте! Помоги задачу решить! Сразу говорю: это не от лени, нам просто мало объясняют! Хотя бы направление дайте, подсказку...Прогу...

Двоичное дерево - C++
Помогите пожалуйста построить двоичное дерево и найти в нём длину пути(количество ветвей от корня) до минимального элемента

Двоичное дерево Хаффмана - C++
Дана некоторая последовательность данных...(то есть набор каких то значений)...этот набор представляет из себя набор конечных потомков...

указатели. двоичное дерево - C++
Всем добрый день. Объясните мне, пожалуйста, несколько вещей. 1.Вот, например. root-&gt;left что делает он: -&gt; Я вроде читал, но не...

Двоичное дерево поиска - C++
Даны 2 вершины дерева .Для каждой из данных вершины вывести ее уровень или информацию что такой вершины нет Подскажите как...

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

Реализовать числовое двоичное дерево - C++
Создайте программой числовое двоичное дерево. Опишите функцию, которая находит сумму элементов непустого дерева.:wall:

Сбалансированное двоичное дерево поиска - C++
ЗДРАВСТВУЙТЕ! Есть код. При компилировании выдаёт ошибку. Помогите исправить пожалуйста. avl.h #include &lt;iostream&gt; #include...

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

Не рекурсивно разрушить двоичное дерево - C++
Доброго времени суток, натолкните пожалуйста на мысль, как не рекурсивно освободить память вот такой вот структуры. Дерево создавал...


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

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

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