Объектно-ориентированное программирование (стр. 8 )

if((Object. s[i]-48)==1)

return 1;

for(i=0;i<length;i++)

if((s[i]-48)<(Object. s[i+Object. length-length]-48))

return 1;

else if((s[i]-48)>(Object. s[i+Object. length-length]-48))

return 0;

//если строки равны, возвращаем 1

return 1;

}

//когда длины строк равны, просто побитово сравниваем обе строки

//до нарушения равновесия

for(i=0;i<length;i++)

if((s[i]-48)<(Object. s[i]-48))

return 1;

else if((s[i]-48)>(Object. s[i]-48))

return 0;

//если строки равны, возвращаем 1

return 1;

}

int BinStr::operator==(BinStr &Object)

{

int i;

//если длина левой строки больше правой

if(length>Object. length)

{

//проверяем, есть ли в старших битах левой

//строки, которых нет в правой, единицы

//если есть, то возвращаем 0

for(i=0;i<length-Object. length;i++)

if((s[i]-48)==1)

return 0;

//если единиц не оказалось, то побитово сравниваем

//обе строки: оставшуюся часть правой строки со всей левой,

//до нарушения равновесия

for(i=0;i<Object. length;i++)

if((s[i+(length-Object. length)]-48)!=(Object. s[i]-48))

return 0;

//если строки равны, возвращаем 1

return 1;

}

//далее следует все аналогично для оставшихся двух случаев,

//когда правая строка длиннее левой и когда длины строк равны

else if(length<Object. length)

{

for(i=0;i<Object. length-length;i++)

if((Object. s[i]-48)==1)

return 0;

for(i=0;i<length;i++)

if((s[i]-48)!=(Object. s[i+Object. length-length]-48))

return 0;

//если строки равны, возвращаем 1

return 1;

}

//когда длины строк равны, просто побитово сравниваем обе строки

//до нарушения равновесия

for(i=0;i<length;i++)

if((s[i]-48)!=(Object. s[i]-48))

return 0;

//если строки равны, возвращаем 1

return 1;

}

BinStr& BinStr::operator=(BinStr &Object)

{

length=strlen(Object. s);

s=new char[(length)+1];

strcpy (s, Object. s);

return *this;

}

ostream &operator<<(ostream &fo, BinStr &fp)

{

fo<<fp. s;

return fo;

}

template <class Type>

void shell(Type *x, int n1)

{ int i, j,k, gap;

Type t;

int a[5]={9,5,3,2,1};

for(k=0; k<5; k++)

{ gap=a[k];

for(i=gap; i<n1; i++)

{ t=x[i];

for(j=i-gap; t<x[j]&&j>=0; j=j-gap)

x[j+gap]=x[j];

x[j+gap]=t;

}

}

}

void main()

{

int i;

int mas1[n];

float mas2[n];

randomize();

for (i=0;i<n;i++)

{

mas1[i]=random(n);

mas2[i]=random(n)*0.01;

}

clrscr();

cout<<" Сортировка методом Шелла\n"<<endl;

//сортировка целых чисел

shell(mas1, n);

cout<<"Отсортированный массив целых чисел:\n"<<endl;

for (i=0;i<n;i++)

cout<<mas1[i]<<" ";

//сортировка чисел с плавающей точкой

shell(mas2, n);

cout<<endl<<"\nОтсортированный массив чисел с плавающей точкой:\n"<<endl;

for (i=0;i<n;i++)

cout<<mas2[i]<<" ";

BinStr mas3[n]={"1001","1000","1100","1010","1100","1011","0011","1111",

"","0110","1110","011001","1111","0011","0110",

"1011","0101","0011","0010","1111"};

//сортировка битовых строк

shell(mas3, n);

cout<<endl<<endl<<"Отсортированный массив битовых строк:"<<endl;

for (i=0;i<n;i++)

cout<<mas3[i]<<" ";

}

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

Сортировка методом Шелла

Отсортированный массив целых чисел:

111620

53 54

79 8

08896

Отсортированный массив чисел с плавающей точкой:

02 01 013 017 0.

19 023 027 029

35 037 03 048 0.

5 054 056 03 07

074 077 08 086 0

9 094 097 0.98

Отсортированный массив битовых строк:

010 111 1

00 111 011001

Пример 2

Задание

·  Написать параметризованную подпрограмму сортировки указанным методом. Отладить ее на целых числах и числах с плавающей точкой.

·  Определить класс объектов массива, предназначенного для сортировки. Перегрузить для него операцию присваивания и операции сравнения <, <=, ==, >=, >.

·  Написать программу, сортирующую массив объектов построенного класса с помощью написанной параметризованной подпрограммы.

Метод сортировки - метод вставок, класс – строка символов.

Программа

#include <iostream. h>

#include <string. h>

#include <conio. h>

#include <stdlib. h>

// Класс - строка символов

class SymStr

{

private:

char *s; // Строка

int length; // Длина строки

public:

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

SymStr()

{

s=new char[1];

*s='\0';

length=0;

}

SymStr(char *str)

{

length = strlen(str);

s = new char[length + 1];

strcpy (s, str);

}

SymStr(const SymStr &str)

{

length = str. length;

s = new char[length + 1];

strcpy (s, str. s);

}

// Деструктор

~SymStr() { delete s; }

// Перегрузка оператора >

int operator> (SymStr &);

// Перегрузка оператора >=

int operator>=(SymStr &);

// Перегрузка оператора <

int operator< (SymStr &);

// Перегрузка оператора <=

int operator<=(SymStr &);

// Перегрузка оператора ==

int operator==(SymStr &);

// Перегрузка оператора =

SymStr &operator=(SymStr &Object);

// Перегрузка оператора << для вывода строки

friend ostream &operator<<(ostream &, SymStr &);

};

// Перегрузка оператора >

int SymStr::operator> (SymStr &Object)

{

if(strcmp(s, Object. s) > 0) return 1;

return 0;

}

// Перегрузка оператора >=

int SymStr::operator>=(SymStr &Object)

{

if(strcmp(s, Object. s) >= 0) return 1;

return 0;

}

// Перегрузка оператора <

int SymStr::operator< (SymStr &Object)

{

if(strcmp(s, Object. s) < 0) return 1;

return 0;

}

// Перегрузка оператора <=

int SymStr::operator<=(SymStr &Object)

{

if(strcmp(s, Object. s) <= 0) return 1;

return 0;

}

// Перегрузка оператора ==

int SymStr::operator==(SymStr &Object)

{

if(strcmp(s, Object. s) == 0) return 1;

return 0;

}

// Перегрузка оператора =

SymStr& SymStr::operator=(SymStr &Object)

{

length = strlen(Object. s);

s = new char[length + 1];

strcpy(s, Object. s);

return *this;

}

// Перегрузка оператора << для вывода строки

ostream &operator<<(ostream &fo, SymStr &fp)

{

fo << fp. s;

return fo;

}

// Cортировка вставками

template <class Type>

void insert (Type *x, int n)

{

int i, j;

Type t;

for (i = 1; i < n; i++)

{

t = x[i];

for (j = i - 1; j >= 0 && t < x[j]; j--)

x[j + 1] = x[j]; // Сдвиг на одну позицию

x[j + 1] = t;

}

}

void main()

{

int i;

int mas1[30]; // Определяем целочисленный массив

float mas2[30]; // Определяем массив чисел с плавающей точкой

randomize(); // Инициализация генератора случайных чисел

// Заполняем массивы случайными числами

for (i = 0; i < 30; i++)

{

mas1[i] = random(30);

mas2[i] = random(30) * 0.01;

}

clrscr(); // Очищаем экран

cout << "\t\t\tСортировка методом вставок\n\n";

// Сортировка целых чисел

insert(mas1, 30);

cout << "Результат сортировки целых чисел:\n";

for (i = 0; i < 30; i++)

cout << mas1[i] << " ";

// Cортировка чисел с плавающей точкой

insert(mas2, 30);

cout << "\n\nРезультат сортировки чисел с плавающей точкой:\n";

for (i = 0; i < 30; i++)

cout << mas2[i] << " ";

SymStr mas3[5] = {"diman", "max", "vasyan", "sanya", "leha"};

// Cортировка символьных строк

insert(mas3, 5);

cout << "\n\nРезультат сортировки битовых строк:\n";

for (i = 0; i < 5; i++)

cout << mas3[i] << " ";

getch();

}

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

Сортировка методом вставок

Результат сортировки целых чисел:

1627

Результат сортировки чисел с плавающей точкой:

0 005 008 02 015 018 0 027 0.29

Результат сортировки битовых строк:

diman leha max sanya vasyan

РАСЧЕТНО-ГРАФИЧЕСКОЕ ЗАДАНИЕ 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 << "Элементы данного дерева: \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.1.  Локальные и глобальные переменные………………………………………….4

1.2.  Подпрограммы и их аргументы…………………………………………………4

1.3.  Определение данных……………………………………………………………..5

1.4.  Операторы динамического распределения памяти…………………………….8

1.5.  Перегрузка функций и операций………………………………………………..9

2.  КЛАССЫ И ОБЪЕКТЫ…………………………………………………………….13

2.1.  Класс как обобщение структуры………………………………………………13

2.2.  Определение первичного класса……………………………………………….16

2.3.  Перегрузка операций для класса………………………………………………18

2.4.  Конструкторы…………………………………………………………………...21

2.5.  Список инициализации…………………………………………………………23

2.6.  Деструктор………………………………………………………………………24

2.7.  Дружественные классы…………………………………………………………27

2.8.  Статические элементы класса………………………………………………….29

2.9.  Шаблоны функций……………………………………………………………...31

3.  КОНТЕЙНЕРНЫЕ КЛАССЫ……………………………………………………..38

3.1.  Шаблоны классов……………………………………………………………….38

3.2.  Параметризованные очереди и стеки………………………………………….41

3.3.  Бинарные деревья……………………………………………………………….45

3.4.  Определение класса множества………………………………………………..51

4.  ПРОИЗВОДНЫЕ КЛАССЫ………………………………………………………..63

4.1.  Определение производного класса…………………………………………….63

4.2.  Доступ к полям и функциям базового класса…………………………………64

4.3.  Класс дерева поиска…………………………………………………………….66

4.4.  Параметризованный связный список………………………………………….68

4.5.  Множественное наследование…………………………………………………73

4.6.  Виртуальные классы……………………………………………………………76

5.  ВИРТУАЛЬНЫЕ ФУНКЦИИ……………………………………………………..81

5.1.  Переопределение составной функции………………………………………...81

5.2.  Организация списка объектов различного типа………………………………83

5.3.  Техническая реализация виртуальных функций……………………………...86

5.4.  Виртуальные деструкторы……………………………………………………..87

5.5.  Абстрактные классы……………………………………………………………88

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

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

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

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

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

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

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

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

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

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

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

Редактор

ЛР № 000 от 21.09.93

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

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

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

Редакционно-издательский отдел ГОУВПО «Комсомольский-

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

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

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

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

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