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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 16, средняя оценка - 4.81
uto
6 / 6 / 0
Регистрация: 07.05.2009
Сообщений: 94
#1

Динамические структуры данных Вариант 18 Павловской - C++

19.05.2009, 05:37. Просмотров 1983. Ответов 17
Метки нет (Все метки)

И вот еще одна задачка из динамических массивов. Буду рад любой помощи!!!

На междугородной телефонной станции картотека абонентов, содержащая сведения о телефонах и их владельцах, организована как двоичное дерево.
Составить программу, которая:
- обеспечивает начальное форматирование картотеки в виде двоичного дерева;
- производит вывод всей картотеки;
- выводит номер телефона и время разговора;
- выводит извещение на оплату телефонного разговора;
Программа должна обеспечивать диалог с помощью меню и контроль ошибок при вводе.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.05.2009, 05:37     Динамические структуры данных Вариант 18 Павловской
Посмотрите здесь:

Лабораторная работа №4 (динамические структуры данных) C++
C++ Динамические информационные структуры данных. (Дек)
Указатели и динамические структуры данных C++
Указатели и динамические структуры данных C++
C++ Динамические структуры данных.Стек.
Динамические структуры данных. Дек C++
Динамические структуры данных на языке С/С++ C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
accept
4817 / 3237 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
19.05.2009, 10:35     Динамические структуры данных Вариант 18 Павловской #2
создание дерева для списка слов
Вложения
Тип файла: zip tree.tar.zip (1.3 Кб, 78 просмотров)
uto
6 / 6 / 0
Регистрация: 07.05.2009
Сообщений: 94
19.05.2009, 19:55  [ТС]     Динамические структуры данных Вариант 18 Павловской #3
Эммм, а что это, впервые вижу такое
Объясните, кому не сложно
accept
4817 / 3237 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
20.05.2009, 05:08     Динамические структуры данных Вариант 18 Павловской #4
обеспечивает начальное форматирование картотеки в виде двоичного дерева
двоичное дерево здесь ключевое слово, это такая структура для хранения данных (вообще это граф из математики, не из всей, конечно, а из дискретной - то есть раздел дискретной математики, графов вообще бесконечное множество, у них там разные свойства заданы, в компьютеры это пришло в очень усечённом виде, как и всё математическое)
в итоге, в компьютерах это выглядит так: есть узлы с данными в них и из каждого узла может выходить только два узла, выходы явлются ссылками на следующие узлы, лист - это узел, у которого выходы обнулены
вся эта структура называется бинарным деревом (потому что только два узла могут выходить из узла, графов бесконечное множество и виды у них разные бывают может вообще одна точка быть, может линия быть из точек, может быть дуга замкнута на точку - петля, ориентация ребёр ещё есть, может и не быть её)
короче, в дереве можно только спускаться и похоже оно на ядерную реакцию: из одного два, потом из двух четыре, из четырёх восемь
конечно, некоторые могут быть обнулены (то есть левая ветвь есть а правой нет и так для каждого узла может быть)

берётся слово, если оно меньше по алфавиту, то оно отправляется в левую ветвь (и там тоже повторяется проверка), если оно больше по алфавиту, то оно отправляется в правую ветвь (и там тоже повторяется проверка), а если оно равно - просто счётчик слова увеличивается (потому что значит такое слово уже в дереве есть)

построение начинается с корня (самого первого узла), слово записывается в корневой узел и потом следующее слово сравнивается с ним и формируется левый узел для нового слова или правый или не формируется ни один, а просто счётчик наращивается
таким образом дерево растёт (то есть поначалу даже корня нет, он тоже из текста как слово берётся)
uto
6 / 6 / 0
Регистрация: 07.05.2009
Сообщений: 94
20.05.2009, 11:15  [ТС]     Динамические структуры данных Вариант 18 Павловской #5
Так.... допустим... половину хоть и не понял, разберемся по ходу)))
Вот картотека, как я понял, примерно, такого плана

tel.txt
uto
6 / 6 / 0
Регистрация: 07.05.2009
Сообщений: 94
20.05.2009, 11:24  [ТС]     Динамические структуры данных Вариант 18 Павловской #6
Вот структура для файлика =)

C++
1
2
3
4
5
6
7
struct telbook
{
   char name[20];      // Имя абонента
   char phone[11];     // Номер абонента
   char time[10];       // Время разговоров по телефону
   char duty[15];       // Задолжность
};
uto
6 / 6 / 0
Регистрация: 07.05.2009
Сообщений: 94
20.05.2009, 11:37  [ТС]     Динамические структуры данных Вариант 18 Павловской #7
Цитата Сообщение от uto Посмотреть сообщение
Так.... допустим... половину хоть и не понял, разберемся по ходу)))
Вот картотека, как я понял, примерно, такого плана

Вложение 4207
Исправил файлик на tel.txt для структуры описанной ниже
uto
6 / 6 / 0
Регистрация: 07.05.2009
Сообщений: 94
20.05.2009, 17:54  [ТС]     Динамические структуры данных Вариант 18 Павловской #8
C++
1
2
3
4
5
6
7
struct telbook
{
   char name[20];       // Имя абонента
   int phone;           // Номер абонента
   int time;            // Время разговоров по телефону в мин.
   char duty[8];        // Задолжность в руб.
};
Добавлено через 6 часов 14 минут 29 секунд
Ребята, знаю, что вы можете сделать и бесплатно, помочь с лабами в трудную минуту, но ПОМОГИТЕ решить СРОЧНО, а то меня отчислить хотят... =(
Дам 100р. (так мало, студент все-таки =/ ), кто поможет...
Знаю, что Kazak шарит, НО прошу всех. Кто напишет, тому вознагрождение! =)
Простите, что так мало(((
accept
4817 / 3237 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
21.05.2009, 04:36     Динамические структуры данных Вариант 18 Павловской #9
структура не содержит указателей на левый и правый узлы

C
1
2
3
4
5
typedef struct tnode {
    char *word;
    int count;
    struct tnode *left, *right; /* вот узлы дерева, сюда будут подключаться ветки */
} Tnode, *Tnodep;
в узле может хранится большое число данных (то есть не только одно слово)

Программа должна обеспечивать диалог с помощью меню и контроль ошибок при вводе.
этот пункт - шелуха, делается в последнюю очередь

тебе надо хотя бы составить дерево без всяких файлов, просто в оперативной памяти, чтобы с ним можно было работать, а потом уж и писать его в базу можно будет или выводить с него инфу и писать интерфейс для его заполнения и управления им
uto
6 / 6 / 0
Регистрация: 07.05.2009
Сообщений: 94
22.05.2009, 19:32  [ТС]     Динамические структуры данных Вариант 18 Павловской #10
Цитата Сообщение от accept Посмотреть сообщение
структура не содержит указателей на левый и правый узлы
Что это значит?
Цитата Сообщение от accept Посмотреть сообщение
в узле может хранится большое число данных (то есть не только одно слово)
эээ, вопрос выше)))))
Цитата Сообщение от accept Посмотреть сообщение
тебе надо хотя бы составить дерево без всяких файлов, просто в оперативной памяти, чтобы с ним можно было работать
А разве это не то дерево?
Цитата Сообщение от accept Посмотреть сообщение
создание дерева для списка слов
tree.tar.zip (1.3 Кб, 6 просмотров
Цитата Сообщение от accept Посмотреть сообщение
а потом уж и писать его в базу можно будет
SQL???? Не разу с ней не работал
accept
4817 / 3237 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
23.05.2009, 07:40     Динамические структуры данных Вариант 18 Павловской #11
Цитата Сообщение от uto
SQL???? Не разу с ней не работал
база данных - это где данные могут храниться
туда можно сохранить данные, а потом прочитать данные, вот это и есть база
телефонный справочник - это база данных телефонных номеров, хотя это книга и она без sql

Цитата Сообщение от uto
А разве это не то дерево?
не, это не дерево, дерево это граф или структура для хранения данных, даже когда они не записаны ни на одном языке программирования, из них можно составить дерево и это будет готовое дерево, останется только записать это дерево на каком-нибудь языке программирования
то есть struct и структура данных - разные вещи
struct - понятие из языка программирования С
структура данных - понятие из теории программирования

Цитата Сообщение от uto
Что это значит?
дерево - это понятие из теории программирования
и для всех языков теория программирования одна, и вот в некоторых языках дерево не реализуешь, но оно есть и никуда не девается
в C есть возможность реализовать дерево, создать узлы а потом связать их, или создавая узлы привязывать их к дереву

Цитата Сообщение от uto
А разве это не то дерево?
это узел дерева, причём форма (все узлы разные данные хранят, но в одной форме)
uto
6 / 6 / 0
Регистрация: 07.05.2009
Сообщений: 94
23.05.2009, 08:19  [ТС]     Динамические структуры данных Вариант 18 Павловской #12
Т.е. мне надо реализовать рабочее дерево с помощью графа? И как это сделать?
accept
4817 / 3237 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
23.05.2009, 08:50     Динамические структуры данных Вариант 18 Павловской #13
нужна функция добавления узла в дерево, ну, там по имени абонента определять куда его, в правую ветвь или в левую передавать (там снова проверяться оно будет)
языка не знаешь совсем ?
uto
6 / 6 / 0
Регистрация: 07.05.2009
Сообщений: 94
23.05.2009, 09:00  [ТС]     Динамические структуры данных Вариант 18 Павловской #14
Я базу изучил, а вот с деревом впервые столкнулся
Потому нужна срочная помощь, если до вторника все лабы не сдам, отчислят
Не хочу в армию :'(
accept
4817 / 3237 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
23.05.2009, 09:23     Динамические структуры данных Вариант 18 Павловской #15
C
1
2
3
4
5
6
7
8
typedef struct telbook
{
    char name[20];       // Имя абонента
    int phone;           // Номер абонента
    int time;            // Время разговоров по телефону в мин.
    char duty[8];        // Задолжность в руб.
    struct telbook *left, *right;
} Book, *Bookptr;
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>
 
int main(void)
{
    Book root = {
        "first",
        2222,
        10,
        "10rub",
        NULL,
        NULL
    };
 
    printf("%s\n", root.name);
 
    return 0;
}
это первый узел дерева и его заполнение, нужно функцию которая будет всё это делать автоматически и ещё определять добавить ли новый узел
Monte-Cristo
2786 / 1372 / 30
Регистрация: 07.03.2009
Сообщений: 4,446
23.05.2009, 09:39     Динамические структуры данных Вариант 18 Павловской #16
ну вот наброски моего друга по бинарному дереву. разберайся
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
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
#include <iostream>
using namespace std;
 
/* структура бинарного дерева */
struct Tree
{
    int data; // данные
 
    Tree* parent; // родительский элемент
    Tree* left;  // левое поддерево
    Tree* right; // правое поддерево
};
 
/* вставка элемента */
void TreeInsert(Tree** root, int data)
{
    Tree* parent = NULL; // указатель на предыдущий родительский элемент
    Tree* current = *root; // вспомогательный указатель для перемещения по дереву
 
    /* создаём новый элемент, инициализурем его данными */
    Tree* newelement = new Tree;
    newelement->data = data;
    newelement->left = NULL;
    newelement->right = NULL;
 
    /* в цикле доходим до листьев */
    while (current)
    {
        parent = current;
        if (data < current->data)
            current = current->left;
        else
            current = current->right;
    }
 
    newelement->parent = parent; // устанавлием указатель на родительский элемент
    /* устанавлием указетели в родительском элементе */
    if (!parent) // дерево пустое
        *root = newelement;
    else if (data < parent->data)
        parent->left = newelement;
    else
        parent->right = newelement;
}
 
/* Возвращает минимальный элемент в дереве  */
Tree* TreeMinimum(Tree* root)
{
    while (root->left != NULL)
        root = root->left;
    return root;
}
/*  */
Tree* TreeSuccessor(Tree* root)
{
    if (root->right != NULL)
        return TreeMinimum(root->right);
    Tree* current = root->parent;
    while (current != NULL && root == current->right)
    {
        root = current;
        current = current->parent;
    }
    return current;
}
 
/* удаление элемента */
Tree* TreeRemove(Tree** root, Tree* element)
{
    Tree* current = NULL;
    Tree* temp = NULL;
 
    if (element->left == NULL || element->right == NULL)
        current = element;
    else
        current = TreeSuccessor(element);
 
    if (current->left != NULL)
        temp = current->left;
    else
        temp = current->right;
 
    if (temp != NULL)
        temp->parent = current->parent;
 
    if (current->parent == NULL)
        *root = temp;
    else if (current == current->parent->left)
        current->parent->left = temp;
    else
        current->parent->right = temp;
 
    if (current != element)
        element->data = current->data;
 
    return current;
 
}
 
/* симметричный обход дерева, печать элементов */
void TreePrint(Tree* root)
{
    if (root != NULL)
    {
        TreePrint(root->left);
        cout << root->data << endl;
        TreePrint(root->right);
    }
}
 
/* поиск элемента в дереве */
Tree* TreeSearch(Tree* root, int key)
{
    if (root == NULL || root->data == key)
        return root;
 
    if (key < root->data)
            TreeSearch(root->left, key);
    else
            TreeSearch(root->right, key);
}
 
/* рекурсивное удаление дерева  */
void TreeDelete(Tree* root)
{
    /*  пока есть левые потомки - рекурсивно перемещаемся в левое поддерево */
    if (root->left)
            TreeDelete(root->left);
    /*  пока есть правые потомки - рекурсивно перемещаемся в правое поддерево */
    if (root->right)
            TreeDelete(root->right);
    /* мы в листе - удаляем его */
    delete root;
}
 
int main()
{
    int data; // данные для ввода
 
    /* создаем корень */
    Tree* root = NULL;
 
    /* вводим элементы до ввода некорректного элемента */
    while (true)
    {
        cout << "Enter next element: \n";
        cin >> data;
        if (cin.good()) // проверяем успешность ввода
        {
            cin.ignore(10, '\n'); // очищаем буфер
            TreeInsert(&root, data); // добавляем элемент в дерево
        }
        else
        {
            cin.clear(); // очищаем флаги потока cin
            cin.ignore(10, '\n'); // очищаем буфер
            cout << "Data should be an integer, stop!\n";
            break;
        }
    }
 
    /* Рекурсивный обход с печатью элементов */
    cout << "Your tree: \n";
    TreePrint(root);
 
    /* поиск элемента */
    int key;
 
    cout << "Enter a key to find: ";
    while (true)
    {
        cin >> key;
        if (cin.good())
        {
            cin.ignore(10, '\n');
            break;
        }
 
        cin.clear();
        cin.ignore(10, '\n');
        cout << "Key should be an integer!\n";
    }
 
    Tree* found = TreeSearch(root, key);
    if (found == NULL)
        cout << "There is no such element!\n";
    else
        cout << "Here is your element: " << found->data << endl;
    cout << "Trying to delete the found element...\n";
    TreeRemove(&root, found);
    cout << "Printing your tree again: \n";
    TreePrint(root);
 
    cout << "Exiting...\n";
    /* Освобождение памяти */
    TreeDelete(root);
    return 0;
}
uto
6 / 6 / 0
Регистрация: 07.05.2009
Сообщений: 94
23.05.2009, 09:43  [ТС]     Динамические структуры данных Вариант 18 Павловской #17
Monte-Cristo, спасибо конечно, но вопрос.. Это дерево подойдет к моей задаче и не надо ничего исправлять?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.05.2009, 11:58     Динамические структуры данных Вариант 18 Павловской
Еще ссылки по теме:

C++ [C++] Динамические структуры данных
Динамические структуры данных о квартирах C++
Задача на динамические структуры данных C++
Динамические структуры данных на языке С/С++ C++

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

Или воспользуйтесь поиском по форуму:
accept
4817 / 3237 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
23.05.2009, 11:58     Динамические структуры данных Вариант 18 Павловской #18
здесь создание книги, без удаления

Код
[guest@station src]$ ./phones
a 1
b 22-22
c 333-333-333
d 4444-4444-4444-4444
[guest@station src]$
Вложения
Тип файла: zip phones.tar.zip (1.2 Кб, 31 просмотров)
Yandex
Объявления
23.05.2009, 11:58     Динамические структуры данных Вариант 18 Павловской
Ответ Создать тему
Опции темы

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