Лабораторная 7 Производные классы

Задание. Используя производные классы, определить класс параметризованного списка одного из следующих типов. Применить его для построения списка объектов указанного типа данных.

Определим следующие классы списков:

S1. Упорядоченный список.

S2. Циклический односвязный список.

S3. Циклический двухсвязный список.

S4. Дек.

S5. Очередь.

S6. Дерево поиска.

Определим следующие типы данных:

T1. Число по модулю n.

T2. Текстовая строка.

T3. Рациональное число.

T4. Битовая строка.

T5. Комплексное число.

Комбинируя классы списков и типы данных, получаем варианты заданий:

	S1	S2	S3	S4	S5	S6
T1	1	6	11	16	21	26
T2	2	7	12	17	22	27
T3	3	8	13	18	23	28
T4	4	9	14	19	24	29
T5	5	10	15	20	25	30

Примеры выполнения ргз 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 << "Элементы данного дерева: \n";

tree.show();

cout << "\n\nВыберете действие\n\

<1> Добавить элемент в дерево\n\

<2> Удалить элемент из списка\n\

<3> Вывести элементы дерева\n\

<4> Поиск элемента дерева по значению\n\

<5> Закончить\n";

num = getch();

switch (num)

{

case '1':

cout << "Введите значение узла \n";

cin >> n;

tree.insert(n);

break;

case '2':

cout << "Введите значение узла \n";

cin >> n;

tree.remove(n);

break;

case '3':

tree.show();

cout << "\n Нажмите любую клавишу для продолжения...";

getch();

break;

case '4':

cout << "Введите значение узла \n";

cin >> n;

if (tree.find(n))

cout << "В этом дереве есть число " << n << endl;

else

cout << "В этом дереве нет числа " << n << endl;

cout << "\n Нажмите любую клавишу для продолжения...";

getch();

}

} while (num != '5');

}