Расчетно-графическое задание 3
Производные классы
Задание. Используя производные классы, определить класс параметризованного списка одного из следующих типов. Применить его для построения списка объектов указанного типа данных.
Определим следующие классы списков: S1. Упорядоченный список. S2. Циклический односвязный список. S3. Циклический двухсвязный список. S4. Дек. S5. Очередь. S6. Дерево поиска.
Определим следующие типы данных: T1. Число по модулю n. T2. Текстовая строка. T3. Рациональное число. T4. Битовая строка. T5. Комплексное число.
Комбинируя классы списков и типы данных, получаем варианты заданий:
Примеры выполнения РГЗ 3
Пример 1
Задание. Используя производные классы, определить класс параметризованного бинарного дерева поиска. Применить его для построения дерева, состоящего из рациональных дробей.
Программа
#include <string.h> #include <alloc.h> #include <conio.h> #include <iostream.h>
// Класс рациональной дроби class fraction { int m, n; // Числитель и знаменатель дроби public: // Конструктор fraction(int m1, int n1 = 1):m(m1), n(n1) { if (n == 0) n = 1; if (n < 0) {m = -m;n = -n;} }
// Перегрузка оператора <= int operator<=(fraction g) { if (m * g.n - g.m * n <= 0) return 1; else return 0; }
// Перегрузка оператора < int operator<(fraction g) { if (m * g.n - g.m * n < 0) return 1; else return 0; }
// Перегрузка оператора == int operator==(fraction g) { if (m * g.n - g.m * n == 0) return 1; else return 0; }
// Перегрузка оператора << friend ostream &operator<<(ostream &o, fraction &f); // Перегрузка оператора >> friend istream &operator>>(istream &i, fraction &f); };
// Перегрузка оператора << ostream &operator<<(ostream &o, fraction &f) { o << f.m << "/" << f.n; return o; }
// Перегрузка оператора >> istream &operator>>(istream &i, fraction &f) { i >> f.m >> f.n; if (f.n < 0) { f.m = -f.m; f.n = -f.n; }
return i; }
// Узел бинарного дерева template <class T> struct NODE { T info; // Содержимое узла
// Указатели на левое и правое поддерево struct NODE <T> *left, *right; };
// Корень бинарного дерева template <class T> struct LIST { NODE <T> *root; // Указатель на корень // Консруктор LIST() { root = NULL; } };
// Класс бинарного дерева template <class T> class TREE:public LIST <T> { public: // Добавление элемента в дерево void insert(T x) { root = ::insert(root, x); }
// Удаление элемента из дерева void remove(T x) { root=::remove(root, x); }
// Поиск элемента в дереве int find(T x) { if (::find(root, x)) return 1; else return 0; }
// Вывод дерева на экран void show() { ::show(root); } };
// Добавление элемента в бинарное дерево template <class T> NODE <T> *insert(NODE <T> *root, T x) { // Если узел пустой if (root == 0) { root = (NODE <T> *)malloc(sizeof(NODE <T>)); root->info = x ; root->left = root->right = 0 ; } // Если не пустой else if (x <= root->info) root->left = insert ( root->left, x ); else root->right = insert ( root-> right, x );
return root; }
// Удаление элемента из бинарного дерева template <class T> NODE <T> *remove(NODE <T> *root, T x) { NODE <T>* b; if (root == 0) return 0; if (x == root->info) { if (root->left == 0) { b = root->right; delete root; return b; }
b = root->left; while (b->right) b = b->right; b->right = root->right; return root->left; }
if (x <= root->info) root->left = remove(root->left, x); else root->right = remove(root->right, x); return root; }
// Поиск элемента в бинарном дереве template <class T> NODE <T> *find(NODE <T> *t, T x) { if(t) { if(x == t->info) return t; else if (x < t->info) return find(t->left, x); else return find(t->right, x); } else return 0; }
// Вывод дерева на экран template <class T> void show( NODE <T> *p ) { if (p) { show (p->left); cout << " " << p->info; show (p->right); } }
void main() { int num; fraction n(0, 1); // Дробь для ввода TREE <fraction> tree; // Создаём дерево
// Интерфейс работы с деревом do { clrscr(); cout << "Элементы данного дерева: "; tree.show(); cout << " Выберете действие <1> Добавить элемент в дерево <2> Удалить элемент из списка <3> Вывести элементы дерева <4> Поиск элемента дерева по значению <5> Закончить ";
num = getch(); switch (num) { case '1': cout << "Введите значение узла "; cin >> n; tree.insert(n); break; case '2': cout << "Введите значение узла "; cin >> n; tree.remove(n); break; case '3': tree.show(); cout << " Нажмите любую клавишу для продолжения..."; getch(); break; case '4': cout << "Введите значение узла "; cin >> n; if (tree.find(n)) cout << "В этом дереве есть число " << n << endl; else cout << "В этом дереве нет числа " << n << endl; cout << " Нажмите любую клавишу для продолжения..."; getch(); } } while (num != '5');
}
Результаты работы программы
Элементы данного дерева: -5/2 -6/3 -3/5 -2/5 2/7 2/5 3/5 3/4
Выберете действие <1> Добавить элемент в дерево <2> Удалить элемент из списка <3> Вывести элементы дерева <4> Поиск элемента дерева по значению <5> Закончить Введите значение узла -2 1 В этом дереве есть число -2/1
Нажмите любую клавишу для продолжения... |
| Оглавление| |