Объектно-ориентированное программирование - Учебное пособие (А.А. Хусаинов)

Расчетно-графическое задание 3

 

Производные классы

 

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

 

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

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 << "Элементы данного дерева: ";

   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

 

 Нажмите любую клавишу для продолжения...