Результат работы программы
Введите первое множество :
a
b
c
d
e
Введите второе множество :
e
f
g
h
i
Первое множество: a b c d e
Количество его элементов: 5
Второе множество:e f g h i
Объединение множеств: a b c d e f g h i
Разность множеств: a b c d
Пересечение множеств: e
Первое множество после удаления элемента 'a' : b c d e
Проверка на принадлежность элемента 'f' второму множеству:
Элемент принадлежит множеству
Проверка на равенство двух данных множеств:
Множества не равны
производные КЛАССЫ
Доступ к полям и функциям базового класса
#include <iostream.h> //библиотека потокового ввода-вывода
void f()
{
cout << “\nВнешняя функция”
}
struct Base1 //первый класс
{
void f() { cout << “\nФункция из Base1”;}
};
struct Base2 //второй класс
{
void f() { cout << “\nФункция из Base2;”}
};
struct Deriv: Base1, Base2 //класс, производный от двух данных классов
{
void f() {::f();} // вызов внешней функции
}
int main()
{
Deriv obj; //создаём объект класса Deriv
f();
obj.Base1::f();
obj.Base2::f();
obj.f();
return 0;
}
В результате работы программы будут выведены следующие строки:
Внешняя функция
Функция из Base1
Функция из Base2
Внешняя функция
Таблица 4.1
| Доступ в базовом классе | Атрибут доступа перед базовым классом | Доступ в производном классе | |
| struct | class | ||
| public | отсутствует | public | private |
| protected | отсутствует | public | private |
| private | отсутствует | недоступны | недоступны |
| public | public | public | public |
| protected | public | protected | protected |
| private | public | недоступны | недоступны |
| public | protected | protected | protected |
| protected | protected | protected | protected |
| private | protected | недоступны | недоступны |
| public | private | private | private |
| protected | private | private | private |
| private | private | недоступны | недоступны |
В таблице отражено преобразование статуса доступа как для классов, определенных с помощью ключевого слова struct, так и для классов, заданных с помощью class. Например:
Class A: protected B { };
Struct A: B { };
Класс дерева поиска
Ниже приведён текст программы, реализующей класс дерева поиска:
#include <stdio.h> //стандартная библиотека ввода-вывода
#include <conio.h> //библиотека консольного ввода-вывода
struct NODE //структура узла дерева
{
int info; //информационное поле
NODE *left, *right; //указатели на левое и правое поддеревья
};
class LIST //базовый класс списка
{
protected:
NODE *root;
public:
LIST() { root = NULL;}
};
class TREE: LIST //класс дерева поиска, производный
//от класса списка
{
public:
void insert(int x); //добавление элемента
void show(); //обход в симметричном порядке
};
NODE* insert(NODE* root, int x)
{
if (!root) //если дерево пусто, то
{
root = new NODE; //создаём новое дерево
root -> info = x; //заполняем информационную часть
root -> left = root -> right = NULL;
}
else
{
//дерево не пусто
//если значение добавляемого элемента меньше чем
//значение информационной части корня, то его следует добавлять
//в левое поддерево
if (x < root -> info) root -> left = insert(root -> left, x);
//в противном случае его следует добавлять в правое поддерево
else root -> right = insert(root -> right, x);
}
return root;
};
void TREE :: insert(int x)
{
root = ::insert(root, x);
};
void display(NODE* p)
{
if(p)
{
display(p -> left); //переходим в левое поддерево
printf("\n%d", p -> info); //отображаем содержимое
//информационного поля
display(p -> right); //переходим в правое поддерево
}
};
void TREE :: show()
{
display(root);
};
int main()
{
TREE a; //создадим объект класса дерево
clrscr(); //очистим экран
//добавим в дерево произвольные элементы
a.insert(2);
a.insert(3);
a.insert(1);
a.insert(12);
a.insert(21);
a.insert(14);
a.insert(20);
a.insert(3);
printf ("Обход дерева в симметричном порядке:");
a.show(); //отобразим дерево на экране
getch(); //ожидание нажатия любой клавиши (пауза)
return 0;
}
Результаты работы программы
Обход дерева в симметричном порядке:
Параметризованный связный список
Рассмотрим метод построения параметризованного списка с двойными связями. Список организовывается с помощью двух классов, первый из которых listob определяет природу элементов списка, а второй, dlist, реализует механизм списка с двойными связями. Первый из этих классов определяется следующим образом:
template <class DataT>
class listob // класс элемента списка
{
public:
DataT info; // информационная часть
listob <DataT> *next; // указатель на следующий элемент
listob <DataT> *prior; // указатель на предшествующий элемент
listob() // конструктор
{
info = 0; next = prior = NULL;
};
listob (DataT c) // конструктор
{
info = c; next = prior = NULL;
};
listob <DataT> *getnext() { return next;}
listob <DataT> *getprior() { return prior;}
void getinfo (DataT& c) { c = info; }
void change (DataT c) { info = c;} // изменение элемента
friend ostream &operator << (ostream &stream, listob <DataT> o);
friend ostream &operator << (ostream &stream, listob <DataT> *o);
friend istream &operator >> (istream &stream, listob <DataT> &o);
};
// перегрузка операции << для объекта listob
template <class DataT>
ostream &operator << (ostream &stream, listob <DataT> o)
{
stream << o.info << endl; return stream;
}
template <class DataT>
ostream &operator << (ostream &stream, listob <DataT> *o)
{
stream << o -> info << endl; return stream;
}
// Перегрузка операции >>
template <class DataT>
istream &operator >> (istream &stream, listob <DataT> &o)
{
cout << “Введите информацию: ”;
stream << o.info; return stream;
}
Механизм построения связного списка реализуется классом, приведенным ниже. Этот класс является производным от класса listob и оперирует с объектами класса listob.
template <class DataT> // параметризованный класс объекта списка
class dlist: public listob<DataT>
// класс списка - производный от класса узла
{
listob<DataT> *start, *end;
// указатели на первый и последний элементы
public:
dlist(){start=end=NULL;} // конструктор
~dlist(); // деструктор
void store(DataT c); // запись в список
void remove(listob<DataT> *ob); // удаление элемента
void frwdlist(); // чтение в прямом направлении
void bkwdlist(); // чтение в обратном направлении
listob<DataT> *find(DataT c); // поиск
listob<DataT> *getstart(){return start;} // начало поиска
listob<DataT> *getend(){return end;} // указатель на конец списка
}
Разработаем подпрограммы, выполняющие эти операции и тестовую программу.
// dlist.cpp - parametrised class of the double connected list
#include <conio.h>
#include <iostream.h>
#include <stdlib.h>
template <class DataT> class listob;
template <class DataT>
ostream &operator << (operator &stream, listob<DataT> o)
{
stream<<o.info<<endl; // вывод объекта
return stream;
}
/* template <class DataT>
ostream &operator<<(ostream &stream, listob<DataT> *o)
{
stream<<o->info<<endl; // вывод объекта по указателю
return stream;
}*/
/* template <class DataT>
istream &operator>>(istream &stream, listob<DataT> &o)
{
cout<<"Input data: ";
stream>>o.info; // ввод объекта
return stream;
}
*/
template <class DataT> class listob // класс узла
{
public:
DataT info; // информационная часть
Listob<DataT> *next, // указатель на следующий элемент
*prior; // указатель на предшествующий элемент
listob()
{
info=0; next = NULL; prior=NULL; // конструктор
}
listob(DataT c)
{
info=c; next=NULL; prior=NULL; // конструктор
}
listob<DataT> *getnext(){return next;}
// чтение адреса следующего элемента
listob<DataT> *getprior(){return prior;}
//чтение адреса предшествующего элемента
void getinfo(DataT &c){c=info;} // чтение информации в аргумент
void change(DataT c){info=c;} // изменение информации
friend ostream &operator<<(ostream &stream, listob<DataT> o);
// дружественные функции
//friend ostream &operator<<(ostream &stream, listob<DataT> *o);
// ввода - вывода
//friend istream &operator>>(istream &stream, listob<DataT> &o);
};
template <class DataT> // параметризованный класс объекта списка
class dlist: public listob<DataT>
// класс списка - производный от класса узла
{
listob<DataT> *start, *end;
// указатели на первый и последний элементы
public:
dlist(){start=end=NULL;} // конструктор
~dlist(); // деструктор
void store(DataT c); // запись в список
void remove(listob<DataT> *ob); // удаление элемента
void frwdlist(); // чтение в прямом направлении
void bkwdlist(); // чтение в обратном направлении
listob<DataT> *find(DataT c); // поиск
listob<DataT> *getstart(){return start;} // начало поиска
listob<DataT> *getend(){return end;} // указатель на конец списка
}
template <class DataT> dlist<DataT>::~dlist
{
listob<DataT> *p, *p1; // деструктор
p=start;
while(p)
{
p1=p->next; delete p; p=p1; // освобождение памяти, занятой
} // элементами списка
}
template <class DataT> void dlist<DataT>::store(DataT c)
{
listob<DataT> *p;
p= new listob<DataT>; // запись нового элемента
if(!p){cout<<"Error of memory allocation\n"; exit(1);}
p->info=c;
if(start==NULL)
// если список пуст, то создается список, состоящий из одного элемента
{
end=start=p;
}
else // иначе изменяем значения указателей
{
p->prior=end; end->next=p; end=p;
}
}
template <class DataT>
void dlist<DataT>::remove(listob<DataT> *ob)
// удаление элемента списка
{
if(ob->prior) // если не первый элемент
{
ob->prior->next=ob->next;
if(ob->next) // если не последний элемент
ob->next->prior=ob->prior;
else // иначе удаляется последний
end=ob->prior; // обновление указателя на конец списка
}
else // удаляется первый элемент списка, если список не пуст
{
if(ob->next)
{
ob->next->prior = NULL;
start=ob->next;
}
else // иначе, т.е. если список пуст,
start=end=NULL; // установить начало и конец на 0
}
}
template <class DataT>
void dlist<DataT>::frwdlist()
// вывод элементов списка в прямом направлении
{
listob<DataT> *temp;
temp=start;
while(temp)
{
cout<<temp->info<< " ";
temp = temp -> getnext();
}
cout<<endl;
}
template <class DataT>
void dlist<DataT>::bkwdlist()
// вывод элементов списка в обратном направлении
{
listob<DataT> *temp;
temp=end;
while(temp)
{
cout<<temp->info<< " ";
temp = temp -> getprior();
}
cout<<endl;
}
template <class DataT>
listob<DataT> *dlist<DataT>::find(DataT c)
// поиск объекта, содержащего информацию, совпадающую с указанной
{
listob<DataT> *temp;
temp=start;
while(temp)
{
if(c==temp->info) return temp; // совпадение найдено
temp = temp->getnext();
}
return NULL; // совпадение не найдено
}
main()
{
dlist<double> list; // демонстрация списка элементов типа double
double i;
listob<double> *p;
clrscr();
list.store(1); // запись элементов 1, 2, 3
list.store(2);
list.store(3);
cout<<"\nDirect list";
list.frwdlist(); // вывод в прямом направлении
cout<<"\nreverse list";
list.bkwdlist(); // вывод в обратном направлении
cout<<endl;
cout<<"Hand viewing of the list"; // ручной просмотр списка
p=list.getstart();
while(p)
{
p->getinfo(i); cout<<i<<" ";
p=p->getnext(); // следующий элемент
}
cout<<endl<<endl;
cout<<" find of 2\n";
p=list.find(2); // поиск элемента 2
if(p)
{
p->getinfo(i);
cout<<"we have find" <<i<<endl; // найден элемент i
}
cout<<endl;
p->getinfo(i);
cout<<"delete"<<i<<"\n";
list.remove(p); // удаление элемента
cout<<"list after deleting";
list.frwdlist(); // список после удаления
cout<<endl;
cout<<"insert the new 4"; // запись элемента 4
list.store(4);
cout<<"\nlist after insert";
list.frwdlist(); // вывод в прямом направлении
cout<<endl;
p=list.find(1); // поиск элемента 1
if(!p)
{
cout<<"Error. No such element\n"; return 1; // если не найден, выйти
}
p->getinfo(i); // чтение в i
cout<<"Change"<<i<<"to 5\n"; // вывод значения i
p->change(5); // изменение 1 на 5
cout<<"list after the change";
list.frwdlist(); // вывод в прямом направлении
cout<<"Reverse list":
list.bkwdlist(); // вывод в обратном направлении
cout<<endl;
getch();
return 0;
}
Результаты работы программы
Список в прямом направлении: 1 2 3
Список в обратном направлении: 3 2 1
Ручной просмотр списка: 1 2 3
Поиск числа 2 в списке
Число 2 было найдено
Удаление числа 2 из списка
Список после удаления: 1 3
Запись нового элемента 4 в список
Список после вставки нового элемента: 1 3 4
Заменим 1 на 5
Список после замены: 5 3 4
Просмотр полученного списка в обратном порядке: 4 3 5
Множественное наследование
Пример. Пусть INTEGER – класс, объектами которого являются целые числа, POSITIVE – класс положительных целых чисел. Определим рациональную дробь как объект производного класса от этих двух классов. Пара, представляющая рациональную дробь, состоит из взаимно простых целых чисел.
#include <iostream.h> //библиотека потокового ввода-вывода
#include <process.h> //библиотека с прототипом функции exit
#include <conio.h> //библиотека консольного ввода-вывода
class INTEGER //класс целых чисел
{
public:
long NUM; //информационное поле
INTEGER (long Val): NUM(Val) {} //конструктор
};
class POSITIVE //класс положительных чисел
{
public:
unsigned long Den; // информационное поле
POSITIVE(unsigned long d) : Den(d) //конструктор
{
if(d==0) {cout << "Ошибка"; exit(1);}//ноль недопустим
}
};
class RATIONAL : public INTEGER, public POSITIVE
//класс дроби
{
//дружественная функция вывода дроби в некоторый поток
friend ostream &operator<<(ostream& stream, RATIONAL& o);
public:
RATIONAL(long v, unsigned long u=1): INTEGER(v), POSITIVE(u)
//конструктор
{
long w;
if (v==0) {u=1; return;}
if(v<0) {w = -v;}
else
{
w=v;
}
//поскольку числитель и знаменатель должны быть
//взаимно простыми числами то следует найти наибольший
//общий делитель для числителя и знаменателя
while (w!=u)
{
if(w>u) w=w-u;
if(u>w) u=u-w;
}
//и следует сократить дробь
NUM = NUM/w;
Den = Den/w;
}
};
ostream& operator<<(ostream& stream, RATIONAL& o)
{
stream<<o.NUM<<"/"<<o.Den;
return stream;
}
main()
{
RATIONAL r1(10, 20), r2(-15, 10);
clrscr();
cout<<"Первая дробь (числитель равен 10, знаменатель равен 20): ";
cout<<r1<<"\n";
cout<<"Вторая дробь (числитель равен -15,знаменатель равен 10): ";
cout<<r2<<"\n";
getch();
}