«Программное обеспечение вычислительной техники и автоматизированных систем»

Вид материалаУчебное пособие

Содержание


Результаты работы программы
Учебное пособие
Подобный материал:
1   2   3   4   5   6   7   8   9


Примеры выполнения РГЗ 3


Пример 1


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

Программа


#include

#include

#include

#include


// Класс рациональной дроби

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

struct NODE

{

T info; // Содержимое узла


// Указатели на левое и правое поддерево

struct NODE *left, *right;

};


// Корень бинарного дерева

template

struct LIST

{

NODE *root; // Указатель на корень

// Консруктор

LIST() { root = NULL; }

};


// Класс бинарного дерева

template

class TREE:public LIST

{

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

NODE *insert(NODE *root, T x)

{

// Если узел пустой

if (root == 0)

{

root = (NODE *)malloc(sizeof(NODE ));

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

NODE *remove(NODE *root, T x)

{

NODE * 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

NODE *find(NODE *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

void show( NODE *p )

{

if (p)

{

show (p->left);

cout << " " << p->info;

show (p->right);

}

}


void main()

{

int num;

fraction n(0, 1); // Дробь для ввода

TREE 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');


}

^
Результаты работы программы


Элементы данного дерева:

-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


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

ЛИТЕРАТУРА

  1. Белецкий Я. Турбо Си++: Новая разработка. – М.: Машиностроение, 1994. – 400 с.
  2. Вайнер Р., Пинстон Л. С++ изнутри. – Киев: «ДиаСофт», 1993. – 304 с.
  3. Дьюхарст С., Старк К. Программирование на С++. – Киев: «ДиаСофт», 1993. – 272 с.
  4. Лукас П. С++ под рукой. – Киев: «ДиаСофт», 1993. – 176 с.
  5. Намиот Д.Е. Язык программирования TURBO C++: Учеб. пособие / Под ред. В.А. Сухомлинова. – М.: МГУ, 1991. – 121 с.
  6. Рассохин Д. От Си к Си++. – М.: Издательство «ЭДЕЛЬ», 1993. – 128 с.
  7. Подбельский В.В. Язык Си++. – М.: Финансы и статистика, 2002. – 560 с.
  8. Страуструп Б. Язык программирования Си++. – Киев: «ДиаСофт», 1993. Ч. 1. – 264 с. Ч. 2. – 296 с.
  9. Тан К.Ш. Символьный С++: Введение в компьютерную алгебру с использованием объектно-ориентированного программирования / К.Ш. Тан, В.-Х. Стиб В.-Х, Й. Харди. – М.: Мир, 2001. – 622 с.
  10. Топп У., Форд У. Структуры данных в С++. – М.: ЗАО «Издательство БИНОМ», 1999. – 816 с.
  11. Шамис В. Borland C++ Builder 5: учебный курс. – СПб.: Питер, 2002. – 688 с.
  12. Шилдт Г. Теория и практика С++. – СПб.: BHV – Санкт-Петербург, 1996. – 416 с.

ОГЛАВЛЕНИЕ



ВВЕДЕНИЕ…………………………………………………………………………………..3
  1. ДОПОЛНИТЕЛЬНЫЕ ВОЗМОЖНОСТИ Си++………………………………....4
    1. Локальные и глобальные переменные………………………………………….4
    2. Подпрограммы и их аргументы…………………………………………………4
    3. Определение данных……………………………………………………………..5
    4. Операторы динамического распределения памяти…………………………….8
    5. Перегрузка функций и операций………………………………………………..9
  2. КЛАССЫ И ОБЪЕКТЫ…………………………………………………………….13
    1. Класс как обобщение структуры………………………………………………13
    2. Определение первичного класса……………………………………………….16
    3. Перегрузка операций для класса………………………………………………18
    4. Конструкторы…………………………………………………………………...21
    5. Список инициализации…………………………………………………………23
    6. Деструктор………………………………………………………………………24
    7. Дружественные классы…………………………………………………………27
    8. Статические элементы класса………………………………………………….29
    9. Шаблоны функций……………………………………………………………...31
  3. КОНТЕЙНЕРНЫЕ КЛАССЫ……………………………………………………..38
    1. Шаблоны классов……………………………………………………………….38
    2. Параметризованные очереди и стеки………………………………………….41
    3. Бинарные деревья……………………………………………………………….45
    4. Определение класса множества………………………………………………..51
  4. ПРОИЗВОДНЫЕ КЛАССЫ………………………………………………………..63
    1. Определение производного класса…………………………………………….63
    2. Доступ к полям и функциям базового класса…………………………………64
    3. Класс дерева поиска…………………………………………………………….66
    4. Параметризованный связный список………………………………………….68
    5. Множественное наследование…………………………………………………73
    6. Виртуальные классы……………………………………………………………76
  5. ВИРТУАЛЬНЫЕ ФУНКЦИИ……………………………………………………..81
    1. Переопределение составной функции………………………………………...81
    2. Организация списка объектов различного типа………………………………83
    3. Техническая реализация виртуальных функций……………………………...86
    4. Виртуальные деструкторы……………………………………………………..87
    5. Абстрактные классы……………………………………………………………88

ЗАКЛЮЧЕНИЕ…………………………………………………………………………….98

РАСЧЕТНО-ГРАФИЧЕСКОЕ ЗАДАНИЕ 1……………………………………………99

РАСЧЕТНО-ГРАФИЧЕСКОЕ ЗАДАНИЕ 2…………………………………………..112

РАСЧЕТНО-ГРАФИЧЕСКОЕ ЗАДАНИЕ 3…………………………………………..121

ЭКЗАМЕНАЦИОННЫЕ ВОПРОСЫ И ЗАДАЧИ…………………………………...126

ЛИТЕРАТУРА…………………………………………………………………………….133



Учебное издание


Ахмет Аксанович Хусаинов

Наталья Николаевна Михайлова


ОБЪЕКТНО-ОРИЕНТИРОВАННОЕ ПРОГРАММИРОВАНИЕ


^

Учебное пособие




Редактор Е.В. Трифонова


ЛР № 020825 от 21.09.93


Подписано в печать 13.08.2003.

Формат 60 х 84 1/16. Бумага писчая. Печать офсетная.

Усл. печ. л. 15,46. Уч.-изд. л. 7,15. Тираж

Редакционно-издательский отдел ГОУВПО «Комсомольский-
на-Амуре государственный технический университет»

681013, Комсомольск-на-Амуре, пр. Ленина, 27.


Полиграфическая лаборатория ГОУВПО «Комсомольский-

на-Амуре государственный технический университет»

681013, Комсомольск-на-Амуре, пр. Ленина, 27.