Входные данные (неотсортированный массив):
5 10 12 3 8 9 2 1
Выходные данные (отсортированный массив):
1 2 3 5 8 9 10 12
контейнерные КЛАССЫ
Шаблоны классов
Пример. Определим параметризованный контейнерный класс - массив. Этот массив защищен в том смысле, что при записи и чтении его элементов контролируется выход за границы массива. Такой массив называется ограниченным.
#include <conio.h>
#include <iostream.h> //библиотека потокового ввода-вывода
#include <stdlib.h> //стандартная библиотека
template <class Atype> class array
{
Atype *a; // элементы массива
int length; // число элементов
public:
array(int size); //конструктор
~array() {delete [] a;} //деструктор
Atype& operator[] (int i); //получение элемента массива
};
template <class Atype>
array <Atype>:: array (int size) // конструктор
{
int i; length = size;
a = new Atype[size]; // выделение памяти
if(!a) { cout << "\nнет памяти для массива";
exit(1);
}
for(i=0; i<size; i++) a[i] = 0; // запись нулей
}
template <class Atype>
Atype& array <Atype>:: operator[](int i)
{
if(i<0 || i > length-1)
{
cout << "\nзначение с индексом " << i;
cout << " выходит за пределы массива";
exit(1);
}
return a[i];
}
main()
{
array <int> ix(20); //массив целых чисел
array <double> dx(20); // массив чисел с плавающей точкой
int i;
clrscr();
for(i=0; i < 20; i++) ix[i] = i;
cout << "\nмассив целых чисел" << ":\n";
for(i=0; i < 20; i++) cout << ix[i] << " ";
for(i=0; i < 20; i++) dx[i] = (double) i;
cout << "\nмассив чисел с плавающей точкой: \n";
for(i=0; i < 20; i++) cout << dx[i] << " ";
ix[20] = 1; // генерирует ошибку
return 0;
}
Результат работы программы
массив целых чисел:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
массив чисел с плавающей точкой:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
значение с индексом 20 выходит за пределы массива
Например, определим параметризованный класс стека. В данном примере иллюстрируется преимущество использования нетипизированных параметров.
template <class T, int size> // здесь size нетипизированный параметр
class
{
T v[size];
int top;
public:
stack(): top(-1){}
~stack() {}
void Push(const T& x)
{
if(top < size-1) {v[++top] = x;}
}
T& Pop() {if (top > -1) return v[top--];}
};
main()
{
stack <int, 20> tiny;
stack <int, 1000> huge;
tiny.Push(-25);
}
Пусть определён класс стека:
template <class T>
class Stack
{
T *v;
int size, top;
public:
stack (int n); // n – размер стека
~stack();
void Push (const T&); // записать Т в стек
T& Pop(); // извлечь Т из стека
…
}
Переопределим его для T = char*:
class Stack <char *>
{
char ** v; // указатель на char*
int size, top;
public:
Stack(int n);
~stack();
void Push(const char*&);
char* Pop();
…
// далее следуют новые функции Push и Pop
};
Параметризованные очереди и стеки
пример программы, создающей параметризованную очередь, размеры которой ограничены и задаются конструктором.
// очередь элементов типа Qtype
#include <conio.h> //библиотека консольного ввода-вывода
#include <iostream.h> //библиотека потокового ввода-вывода
#include <stdlib.h> //стандартная библиотека
template <class Qtype> class queue
{
Qtype *q; // массив элементов очереди
int sloc, rloc; // последний записанный элемент
// и последний прочитанный
int length; // размер очереди
public:
queue(int size); // конструктор
~queue() { delete [] q;} //деструктор
void qstore(Qtype i); //запись в конец очереди
Qtype qretrieve(); // получение первого элемента очереди
};
// конструктор
template <class Qtype>
queue <Qtype>:: queue(int size)
{
size++; // размер на 1 больше
q = new Qtype[size]; //выделим память
if(!q) //если не удалось выделить память
{
cout << "\nнет памяти для очереди"; exit(1);
}
length = size; //длина очереди
sloc = rloc = 0; // начало и конец очереди
}
// запись в очередь
template <class Qtype>
void queue <Qtype>:: qstore(Qtype i)
{
if(sloc+1 == length) //если нельзя сместить указатель на конец
{
cout << "Очередь переполнена\n";
return;
}
sloc++; //смещаем указатель
q[sloc] = i; //записываем элемент
}
// чтение и удаление из очереди
template <class Qtype>
Qtype queue <Qtype>:: qretrieve()
{
if(rloc == sloc) //если указатель на конец равен указателю на начало
{
cout << "\nОчередь пуста ";
return 0;
}
rloc++; return q[rloc];
}
// пример использования очереди
main()
{
clrscr(); //очистка экрана
queue <int> a(10), b(10); //две очереди с целыми числами
queue <double> c(10); //одна очередь с числами с плавающей точкой
a.qstore(100);
a.qstore(200);
b.qstore(300);
b.qstore(400);
cout<<"Первый элемент очереди а "<<a.qretrieve()<<" \n";//выведет 100
cout<<"Второй элемент очереди а "<<a.qretrieve()<<" "; // выведет 200
cout << a.qretrieve() << " \n"; // "очередь пуста"
c.qstore(-1);
c.qstore(-2);
cout<<"Первый элемент очереди с "<<c.qretrieve()<<" "; //выведет -1
return 0;
}
Результат работы программы
Первый элемент очереди а 100
Второй элемент очереди а 200
Очередь пуста 0
Первый элемент очереди с –1
Приведём текст программы, имеющей те же самые результаты, что и в предыдущем примере, но использующей в своей работе циклическую очередь.
// очередь элементов типа Qtype
#include <conio.h> //библиотека консольного ввода-вывода
#include <iostream.h> //библиотека потокового ввода-вывода
#include <stdlib.h> //стандартная библиотека
template <class Qtype> class queue
{
Qtype *q; // массив элементов очереди
int sloc, rloc; // последний записанный элемент
// и последний прочитанный
int length; // размер очереди
public:
queue(int size); // конструктор
~queue() { delete [] q;} //деструктор
void qstore(Qtype i); //запись в конец очереди
Qtype qretrieve(); // получение первого элемента очереди
};
// конструктор
template <class Qtype>
queue <Qtype>:: queue(int size)
{
size++; // размер на 1 больше
q = new Qtype[size]; //выделим память
if(!q) //если не удалось выделить память
{
cout << "\nнет памяти для очереди"; exit(1);
}
length = size; //длина очереди
sloc = rloc = 0; // начало и конец очереди
}
// запись в очередь
template <class Qtype>
void queue <Qtype>::qstore(Qtype i) // добавление
{
if((sloc+1 == rloc) || (sloc+1 == length) &&!rloc)
{
cout << "\nОчередь переполнена"; return;
}
q[sloc] = i; sloc++;
if(sloc == length) sloc = 0; // циклический список
}
// чтение и удаление из очереди
template <class Qtype>
Qtype queue <Qtype>:: qretrieve()
{
if(rloc == length) rloc = 0;
if(rloc == sloc)
{
cout << "\nОчередь пуста"; return 0;
}
rloc++;
return q[rloc-1];
}
// пример использования очереди
main()
{
clrscr(); //очистка экрана
queue <int> a(10), b(10); //две очереди с целыми числами
queue <double> c(10); //одна очередь с числами с плавающей точкой
a.qstore(100);
a.qstore(200);
b.qstore(300);
b.qstore(400);
cout<<"Первый элемент очереди а "<<a.qretrieve()<<" \n";//выведет 100
cout<<"Второй элемент очереди а "<<a.qretrieve()<<" "; // выведет 200
cout << a.qretrieve() << " \n"; // "очередь пуста"
c.qstore(-1);
c.qstore(-2);
cout<<"Первый элемент очереди с "<<c.qretrieve()<<" "; //выведет -1
return 0;
}
Результат работы программы
Первый элемент очереди а 100
Второй элемент очереди а 200
Очередь пуста 0
Первый элемент очереди с –1
Приведенная ниже программа реализует параметризованный класс стека.
//программа, использующая стек
#include <conio.h> //библиотека консольного ввода-вывода
#include <iostream.h> //библиотека потокового ввода-вывода
#include <stdlib.h> //стандартная библиотека
template <class Stype>
class stack //класс стека
{
Stype *s; // массив, содержащий элементы стека
int tos; // число записанных элементов
int length; // размер стека
public:
stack(int size); // конструктор
~stack() {delete [] s;} // освобождение памяти
void push(Stype i); // запись элемента в стек
Stype pop(); // извлечение элемента из стека
};
// конструктор
template <class Stype>
stack <Stype>:: stack(int size)
{
s = new Stype[size]; // захват памяти
if(!s) // если s=0
{
cout << "\nНет памяти для стека";
exit(1);
}
length = size; tos = 0; // вершина стека
}
// запись объекта в стек
template <class Stype>
void stack <Stype>:: push(Stype i)
{
if(tos == length) //если длина стека - максимум
{
cout << "\nСтек переполнен";
return;
}
s[tos++] = i; //сохраняем элемент в стеке
}
// чтение и удаление объекта из стека
template <class Stype>
Stype stack <Stype>:: pop()
{
if(tos == 0)
{
cout << "\nСтек пуст"; return 0;
}
return s[--tos]; //получение элемента из стека
}
// примеры использования стека
main()
{
stack <int> a(10); // стек целых чисел
stack <double> b(10); // стек чисел с плавающей точкой
clrscr(); // очистка экрана
a.push(10); // запись в стек a
b.push(-1); // запись в стек b
a.push(20); // запись в стек a
cout <<"Последний элемент стека а "<< a.pop()<<"\n";// вывод числа 20
cout <<"Последний элемент стека b "<< b.pop(); // вывод числа -1
return 0;
}
Результат работы программы
Последний элемент стека а 20
Последний элемент стека b -1
Бинарные деревья
Для определения параметризованного класса бинарного дерева будет использоваться следующий шаблон:
template <class DataT>
class tree
{
DataT info; // информ. часть
tree *left, *right; // указатели на поддеревья
public:
tree <DataT> *root; //корень дерева
tree() { root = NULL;} //конструктор
//добавление элемента в дерево
void stree(tree <DataT>*,tree <DataT>*,DataT);
//удаление из дерева
tree <DataT> * dtree(tree <DataT>*r, DataT key);
void preorder(tree <DataT>*r); // обход прямой
void inorder(tree <DataT>*r); // симметричный обход
void postorder(tree <DataT>*r); // обратный обход
void print_tree(tree <DataT>*r, int l); // вывод дерева
//поиск в дереве
tree <DataT> * search_tree(tree <DataT>*r, DataT key);
};
Для включения новых элементов в дерево используется функция, описанная в теле класса как stree:
//параметризованная функция добавления элемента в дерево
template <class DataT>
void tree <DataT>::stree (tree <DataT> *r, tree <DataT> *previous, DataT info)
{
if (!r)
{
//если в качестве дерева для вставки передан NULL то
r = new tree <DataT>; //выделим память
if (!r)
{
cout<< "\nНедостаточно памяти"; exit(1);
}
//создаётся новое дараво
r -> left = r -> right = NULL;//левое и правое поддеревья пусты
r -> info = info;
if (!root) root = r; // корень
else //если корень первоначального дерева не пуст
{
//вставляем элемент на его место в дереве поиска
if (info<previous -> info) previous -> left = r;
else previous -> right = r;
}
return;
}
//если передано в качастве формального параметра не пустое дерево,
//то вставим элемент либо
if (info < r -> info)
stree (r -> left, r, info);//в левое поддерево
else
stree (r -> right, r, info);//либо в правое
}
Для прохождения дерева с выводом на экран значений его узлов можно использовать функцию обхода в симметричном порядке, описанную в теле класса как inorder:
//параметризованная функция обхода дерева в симметричном порядке
template <class DataT>
void tree <DataT>::inorder(tree <DataT> *r)
{
if(!r) return; //если дерево пусто
inorder (r -> left); //посетим левое поддерево
if(r -> info) cout << r -> info << " "; //вывод элемента
inorder (r -> right); //посетим правое поддерево
}
Эту функцию следует использовать, применяя в качестве аргумента указатель на корень созданного дерева. Значения элементов будут выведены в неубывающем порядке.
Приведем соответствующие функции для обхода дерева в прямом и обратном порядках, описанные в теле класса как preorder и postorder соответственно:
//параметризованная функция обхода дерева в прямом порядке
template <class DataT>
void tree <DataT>::preorder(tree <DataT>*r)
{
if(!r) return; //если дерево пусто
if(r -> info) cout << r -> info << " "; //вывод элемента
preorder (r -> left); //посетим левое поддерево
preorder (r -> right); //посетим правое поддерево
}
//параметризованная функция обхода дерева в обратном порядке
template <class DataT>
void tree <DataT>::postorder(tree <DataT>*r)
{
if(!r) return; //если дерево пусто
postorder (r -> left); //посетим левое поддерево
postorder (r -> right); //посетим правое поддерево
if (r -> info) cout << r -> info << " ";//вывод элемента
}
Для вывода дерева на экран, можно применить следующую подпрограмму, описанную в теле класса как print_tree:
//параметризированная функция печати дерева на экране
template <class DataT>
void tree <DataT>::print_tree(tree <DataT>*r, int l)
{
int i;
if(!r) return; //если дерево пусто
print_tree(r -> right, l+1); //распечатаем правое поддерево на
//l+1 уровне
for (i = 0; i < l; i++) cout << " ";//вывод необходимого
//количества пробелов
cout << r -> info << endl; //вывод информационной части
print_tree(r -> left, l+1); //распечатаем правое поддерево на
//l+1 уровне
}
Для полноты приведём подпрограммы поиска элемента (search_tree) и удаления (dtree) элемента бинарного дерева.
//параметризованная функция поиска поддерева с корнем, равным key
template <class DataT>
tree <DataT> *tree<DataT>::search_tree(tree <DataT>*r, DataT key)
{
if (!r) return r; // если дерево пусто
while (r -> info!= key) //цикл пока не найдено поддерево
{
if (key < r -> info) r = r -> left;//ищем слева
else r = r -> right; //ищем справа
if (r == NULL) break; //если не нашли
}
return r;
}
Если элемент не найден, то эта подпрограмма возвратит NULL.
Подпрограмма удаления элемента реализуется рекурсивно:
//параметризованная функция получения нового дерева из имеющегося
//путём удаления некоторого узла
template <class DataT>
tree <DataT>* tree <DataT>::dtree(tree <DataT> *r, DataT key)
{
tree <DataT> *p;
tree <DataT> *p2; // r - корень дерева
if (!r) return r; // если элемент не найден
if (r -> info == key) //элемент это корень-?
{
if (r -> left == r -> right) // если 1 элемент
{ //вернём пустое дерево
if (root==r) root = NULL;
return NULL; // пустое дерево
}
else if(r -> left == NULL) //если левое поддерево пусто
{
p = r -> right; // нет левого поддерева
if (root == r) root = p;
return p;
}
else if (r -> right == NULL) //если правое поддерево пусто
{
p = r -> left; // нет правого поддерева
if (r == root) root = p;
return p;
}
else //в противном случае
{
p2 = r -> right;//как минимум дерево из правого поддерева
p = r -> right; //правые поддеревья
while (p -> left) p = p -> left;
p -> left = r -> left;
if (r == root) root = p2;
return p2; //вернём новое дерево
}
}
//если не корень, двигаемся
if (r -> info < key) r -> right = dtree(r -> right, key); //вправо
else r -> left = dtree (r -> left, key); //и влево
//пока искомый элемент не станет корнем
return r;
}
Ниже приведём пример программы, использующей вышеописанные функции для работы с бинарным деревом, информационной частью элементов которого являются символы, вводимые пользователем с клавиатуры.
#include <iostream.h> //библиотека потокового ввода-вывода
#include <conio.h> //библиотека консольного ввода-вывода
#include <process.h> //необходимо для использования функции exit
template <class DataT>
class tree
{
DataT info; // информ. часть
tree *left, *right; // указатели на поддеревья
public:
tree <DataT> *root; //корень дерева
tree() { root = NULL;} //конструктор
//добавление элемента в дерево
void stree(tree <DataT>*,tree <DataT>*,DataT);
//удаление из дерева
tree <DataT> * dtree(tree <DataT>*r, DataT key);
void preorder(tree <DataT>*r); // обход прямой
void inorder(tree <DataT>*r); // симметричный обход
void postorder(tree <DataT>*r); // обратный обход
void print_tree(tree <DataT>*r, int l); // вывод дерева
//поиск в дереве
tree <DataT> * search_tree(tree <DataT>*r, DataT key);
};
//параметризованная функция добавления элемента в дерево
template <class DataT>
void tree <DataT>::stree (tree <DataT> *r, tree <DataT> *previous, DataT info)
{
if (!r)
{
//если в качестве дерева для вставки передан NULL то
r = new tree <DataT>; //выделим память
if (!r)
{
cout<< "\nНедостаточно памяти"; exit(1);
}
//создаётся новое дараво
r -> left = r -> right = NULL;//левое и правое поддеревья пусты
r -> info = info;
if (!root) root = r; // корень
else //если корень первоначального дерева не пуст
{
//вставляем элемент на его место в дереве поиска
if (info<previous -> info) previous -> left = r;
else previous -> right = r;
}
return;
}
//если передано в качестве формального параметра не пустое дерево,
//то вставим элемент либо
if (info < r -> info)
stree (r -> left, r, info);//в левое поддерево,
else
stree (r -> right, r, info);//либо в правое
}
//параметризованная функция обхода дерева в симметричном порядке
template <class DataT>
void tree <DataT>::inorder(tree <DataT> *r)
{
if(!r) return; //если дерево пусто
inorder (r -> left); //посетим левое поддерево
if(r -> info) cout << r -> info << " "; //вывод элемента
inorder (r -> right); //посетим правое поддерево
}
//параметризованная функция обхода дерева в прямом порядке
template <class DataT>
void tree <DataT>::preorder(tree <DataT>*r)
{
if(!r) return; //если дерево пусто
if(r -> info) cout << r -> info << " "; //вывод элемента
preorder (r -> left); //посетим левое поддерево
preorder (r -> right); //посетим правое поддерево
}
//параметризованная функция обхода дерева в обратном порядке
template <class DataT>
void tree <DataT>::postorder(tree <DataT>*r)
{
if(!r) return; //если дерево пусто
postorder (r -> left); //посетим левое поддерево
postorder (r -> right); //посетим правое поддерево
if (r -> info) cout << r -> info << " ";//вывод элемента
}
//параметризованная функция печати дерева на экране
template <class DataT>
void tree <DataT>::print_tree(tree <DataT>*r, int l)
{
int i;
if(!r) return; //если дерево пусто
print_tree(r -> right, l+1); //распечатаем правое поддерево на
//l+1 уровне
for (i = 0; i < l; i++) cout << " ";//вывод необходимого
//количества пробелов
cout << r -> info << endl; //вывод информационной части
print_tree(r -> left, l+1); //распечатаем правое поддерево на
//l+1 уровне
}
//параметризованная функция поиска поддерева с корнем, равным key
template <class DataT>
tree <DataT> *tree<DataT>::search_tree(tree <DataT>*r, DataT key)
{
if (!r) return r; // если дерево пусто
while (r -> info!= key) //цикл пока не найдено поддерево
{
if (key < r -> info) r = r -> left;//ищем слева
else r = r -> right; //ищем справа
if (r == NULL) break; //если не нашли
}
return r;
}
//параметризованная функция получения нового дерева из имеющегося
//путём удаления некоторого узла
template <class DataT>
tree <DataT>* tree <DataT>::dtree(tree <DataT> *r, DataT key)
{
tree <DataT> *p;
tree <DataT> *p2; // r - корень дерева
if (!r) return r; // если элемент не найден
if (r -> info == key) //элемент это корень-?
{
if (r -> left == r -> right) // если 1 элемент
{ //вернём пустое дерево
if (root==r) root = NULL;
return NULL; // пустое дерево
}
else if(r -> left == NULL) //если левое поддерево пусто
{
p = r -> right; // нет левого поддерева
if (root == r) root = p;
return p;
}
else if (r -> right == NULL) //если правое поддерево пусто
{
p = r -> left; // нет правого поддерева
if (r == root) root = p;
return p;
}
else //в противном случае
{
p2 = r -> right;//как минимум дерево из правого поддерева
p = r -> right; //правые поддеревья
while (p -> left) p = p -> left;
p -> left = r -> left;
if (r == root) root = p2;
return p2; //вернём новое дерево
}
}
//если не корень, двигаемся
if (r -> info < key) r -> right = dtree(r -> right, key); //вправо
else r -> left = dtree (r -> left, key); //и влево
//пока искомый элемент не станет корнем
return r;
}
int main(void)
{
char stemp[80]; //символьная строка
int i=0; //счётчик
tree <char> ch; //дерево
tree <char> *ch1; //указатель на дерево
ch1=new tree <char>; //выделим память для дерева
clrscr(); //очистим экран
cout << "Введите строку (она должна завершаться точкой):";
cin >> stemp;
do
{
//пока не встретилась точка, вставляем каждый элемент строки
//в дерево ch
if (stemp[i]!='.') ch.stree(ch.root, NULL, stemp[i]);
i++;
}
while (stemp[i]!= '.');
cout <<"Обход первоначального дерева в прямом порядке:\n";
ch.preorder(ch.root);
cout <<'\n';
cout <<"Обход первоначального дерева в обратном порядке:\n";
ch.postorder(ch.root);
cout <<'\n';
cout <<"Обход первоначального дерева в симметричном порядке:\n";
ch.inorder(ch.root);
ch1->root=ch.dtree(ch.root,stemp[0]); //получение нового дерева
cout <<'\n';
cout <<"Обход дерева в прямом порядке после удаления первого введённого элемента:\n";
ch1->preorder(ch1->root);
cout <<'\n';
cout <<"Печать окончательного вида дерева:\n";
ch.print_tree(ch.root,0);
return 0;
}
Результат работы программы
Введите строку (она должна завершаться точкой):123321453754.
Обход первоначального дерева в прямом порядке:
1 2 1 3 2 3 4 3 5 4 7 5
Обход первоначального дерева в обратном порядке:
1 2 3 4 5 7 5 4 3 3 2 1
Обход первоначального дерева в симметричном порядке:
1 1 2 2 3 3 3 4 4 5 5 7
Обход дерева в прямом порядке после удаления первого введённого элемента:
2 1 3 2 3 4 3 5 4 7 5
Печать окончательного вида дерева:
Определение класса множества
Класс множества определим следующим образом:
//параметризированный класс множества
template <class Stype>
class Set
{
Stype *SetPtr; // указатель на первый элемент
int MaxSize; // максимальное число элементов
int NumMembers; // количество элементов множества
void insert (Stype member); // добавление элемента
void remove (Stype member); // удаление элемента
int find(Stype member); // поиск элемента
int ismember (Stype member); // принадлежность элемента
public:
Set(); // конструкторы
Set(int size);
Set(const Set &ob); // конструктор копирования
~Set() { delete SetPtr; } // деструктор
Set <Stype> &operator = (Set <Stype> &ob); // присваивание
Set <Stype> operator + (Stype member); // добавление элемента
friend Set<Stype> operator + (Stype member, Set <Stype> ob);
Set <Stype> operator + (Set <Stype> &ob); // объединение
Set <Stype> operator - (Stype member); // удаление элемента
Set <Stype> operator - (Set <Stype> &ob); // разность
Set <Stype> operator & (Set <Stype> &ob); // пересечение
// опреации сравнения
int operator == (Set <Stype> &ob); // 1 если равно
int operator!= (Set <Stype> &); // 1 если не равно
int operator < (Set <Stype> &ob); // 1 если подмножество
friend int operator < (Stype member, Set <Stype> ob);
// 1 если элемент множества
operator int() {return NumMembers;} // преобразование в целое
// ввод - вывод
friend istream &operator >> (istream &stream, Set<Stype> &ob);
friend ostream &operator << (ostream &stream, Set<Stype> & ob);
};
Конструкторы. Первый конструктор без аргументов резервирует память для массива, состоящего из элементов, количество которых равно DEFSET. Значение DEFSET определяется с помощью внешней константы, например:
const int DEFSET = 100;
оно используется в конструкторе:
//параметризированный конструктор класса, вызываемый по умолчанию
template <class Stype>
Set <Stype>::Set()
{
SetPtr = new Stype [DEFSET]; //выделим память
if(!SetPtr){ cout << "Нет памяти\n";
exit(1);
}
NumMembers = 0; MaxSize = DEFSET;
}
Для построения множества заданного размера будем использовать конструктор:
//параметризированный конструктор с заданным числом элементов
template <class Stype>
Set <Stype>::Set(int size)
{
SetPtr = new Stype[size]; //выделим память
if(!SetPtr){ //не удалось
cout << "Нет памяти\n"; exit(1);
}
NumMembers = 0; MaxSize = size;
}
Поиск элемента. Приведём подпрограмму find поиска элемента и тест на принадлежность элемента множеству:
//закрытый член класса, обеспечивающий поиск элемента в множестве
template <class Stype>
int Set <Stype>::find(Stype member)
{
int i;
for (i = 0; i < NumMembers; i++) //поиск во всем множестве
if(SetPtr[i] == member) return i;
return -1; // если такого элемента нет
}
//закрытый член класса, дающий ответ на вопрос:
//принадлежит ли переданное ему значение множеству
template <class Stype>
int Set <Stype>::ismember(Stype member)
{
if (find(member)!= -1) return 1; //произведём поиск
else return 0; //не нашли
}
Функция find() возвращает индекс указанного элемента, если этот элемент принадлежит множеству. В противном случае она возвращает –1.
Добавление и удаление элементов. Приведём подпрограмму добавления (insert()) и удаления (remove()) элементов множества.
//закрытый член класса, обеспечивающий добавление элемента во множество
template <class Stype>
void Set<Stype>::insert(Stype member) // добавление
{
if(NumMembers == MaxSize) //проверим не переполнено ли множество
{
cout << "\nПереполнение множества"; exit(1);
}
if(!ismember(member)) // если нет такого элемента
{
SetPtr[NumMembers] = member; // добавить
NumMembers++; // элементов стало на один больше
}
}
Аргументом этой подпрограммы служит новый элемент множества. Для удаления будем использовать закрытую функцию remove():
//закрытый член класса, обеспечивающий удаление заданного
//элемента множества
template <class Stype>
void Set<Stype>::remove(Stype member)
{
int loc = find(member); //найдём элемент множества
if(loc!= -1) // если элемент найден
{
for(; loc < NumMembers -1; loc++)
SetPtr[loc] = SetPtr[loc+1]; //сдвигаем множество
NumMembers--; //элементов на один стало меньше
}
}
Если такой элемент множества существует, то он удаляется путем сдвига элементов массива на одну позицию влево.
// Конструктор копирования
template <class Stype>
Set<Stype>::Set(const Set<Stype> &ob)
{
int i;
MaxSize = ob.MaxSize;
SetPtr = new Stype[MaxSize]; //выделим память
if(!SetPtr) //если не удалось
{
cout << "\nНет памяти для копирования";
exit(1);
}
NumMembers = 0;
for(i=0; i < ob.NumMembers; i++)
insert(ob.SetPtr[i]); //производим копирование
}
//операция присваивания
template <class Stype>
Set<Stype> &Set<Stype>::operator = (Set<Stype> &ob)
{
int i;
// обработка случая s = s
if(SetPtr == ob.SetPtr) return *this;
// проверяем число элементов
if(ob.NumMembers > MaxSize)
{
delete SetPtr; //сначала удалим множество
SetPtr = new Stype[ob.NumMembers]; //затем выделим память
//под новое множество
if(!SetPtr) //если нет памяти
{
cout << "\nНет памяти для копирования"; exit(1);
}
MaxSize = ob.NumMembers;
}
NumMembers = 0; // удаляем старое множество
for (i = 0; i < ob.NumMembers; i++)
insert(ob.SetPtr[i]); //производим копирование всех элементов
return *this; //возврат указателя на текущий экземпляр
//класса
}
Добавление элемента и построение объединения. Перегрузим операцию сложения для двух случаев. В первом случае эта операция обрабатывает ситуацию «множество плюс элемент ».
//Операция добавления нового элемента в множество
template <class Stype>
Set<Stype> Set<Stype>::operator+(Stype member)
{
int i;
Set<Stype> temp(NumMembers+1);
// копирование элементов во временное множество
for(i = 0; i < NumMembers; i++)
temp.insert(SetPtr[i]);
temp.insert(member);
return temp; // возврат нового множества
}
Во втором случае эта операция обрабатывает ситуацию «элемент плюс множество ». Она определяется с помощью дружественной функции:
//Ещё одна сигнатура операции добавления
template <class Stype>
Set<Stype> operator+(Stype member, Set<Stype> ob)
{
int i;
Set<Stype> temp(ob.NumMembers + 1);
// копирование элементов во временное множество
for(i = 0; i < ob.NumMembers; i++)
temp.insert(ob.SetPtr[i]);
// вставка нового элемента
temp.insert(member);
return temp; // возврат нового множества
}
Перегрузим операцию `+` для объединения множеств:
//операция объединения двух множеств
template <class Stype>
Set<Stype> Set<Stype>::operator+(Set<Stype> &ob)
{
int i;
Set<Stype> temp(NumMembers+ob.NumMembers);
for(i = 0; i < NumMembers; i++)
temp.insert(SetPtr[i]); //во временное множество копируем
//сначала первое множество
for(i = 0; i < ob.NumMembers; i++)
temp.insert(ob.SetPtr[i]); //а затем второе
return temp; //возврат нового множества
}
Эта операция используется для выполнения операторов следующего типа:
set1 = set2 + set3;
где set1, set2, set3 – объекты класса set.
Удаление элемента и разность множеств. Для удаления элемента определим операцию `-`:
//операция удаления элемента из множества
template <class Stype>
Set<Stype> Set<Stype>::operator-(Stype member)
{
int i;
Set<Stype> temp = *this;
temp.remove(member); // удаление элемента
return temp; // возврат множества
}
Эта функция позволяет вычислять выражения set1 = set2 – item, где set1 и set2 - объекты класса set, а item – элемент из set2.
Перегрузим операцию вычитания для вычисления разности множеств:
//операция разности двух множеств
template <class Stype>
Set<Stype> Set<Stype>::operator-(Set<Stype> &ob)
{
int i;
Set<Stype> temp = *this;
// удаляем элементы из *this, принадлежащие ob
for(i = 0; i < NumMembers; i++)
if(ob.ismember(SetPtr[i]))
temp.remove(SetPtr[i]);
return temp; // возврат результата
}
Например, после выполнения оператора set1 = set2 – set3, множество set1 будет состоять из элементов set2, не принадлежащих set3.
Пересечение множеств. Для обозначения пересечения будем использовать знак конъюнкции:
//Операция пересечения множеств
template <class Stype>
Set<Stype> Set<Stype>::operator& (Set<Stype> &ob)
{
int i, j;
Set<Stype> temp(NumMembers);
for(i = 0; i < NumMembers; i++)
if(ob.ismember(SetPtr[i]))
temp.insert(SetPtr[i]); //вставляем в результат только
//те элементы, которые принадлежат и
//первому множеству,
//и второму
return temp; // возврат результата
}
После выполнения операции set1 = set2 & set3 множество set1 будет содержать элементы из set2, одновременно принадлежащие set3.
Сравнение множеств. Равенство и неравенство для класса Set реализованы перегрузкой операций ` ==` и ` !=`:
// 1 - если множества равны
template <class Stype>
int Set<Stype>::operator == (Set<Stype> &ob)
{
if(NumMembers!= ob.NumMembers) return 0;
// множества должны содержать одинаковое число элементов
return *this < ob; // если первое содержится во втором, то равны
}
// проверка на неравенство
template <class Stype>
int Set<Stype>::operator!=(Set<Stype> &ob)
{
return!(*this == ob);
}
// проверка на включение
template <class Stype>
int Set<Stype>::operator < (Set<Stype> &ob)
{
int i;
for(i = 0; i < NumMembers; i++)
if(!ob.ismember(SetPtr[i])) return 0;
// если SetPtr[i] не принадлежит ob
return 1;
}
Проверка принадлежности. Операцию `<` перегрузим для определения принадлежности элемента множеству:
// 1 - если принадлежит
template <class Stype>
int operator < (Stype member, Set<Stype> ob)
{
if (ob.ismember(member)) return 1; //если есть такой элемент
return 0;
}
Преобразование в целое. Преобразование объекта класса set в целое число возвращает число, равное количеству элементов, содержащихся в множестве на текущий момент. Если множество пусто, то возвращается нуль. Функция преобразования нужна для автоматического преобразования к другому, обычно встроенному, типу. Ее текст определен как inline -функция:
operatot int() {return NumMembers;}
Эта функция позволяет выполнять действия, подобные приведенным ниже:
if (set) cout << “Множество не пустое”;
cout << “set1 содержит” << (int) set1 << “\n элементов”
Перегрузка операторов ввода-вывода. Определим операции ввода и вывода с помощью `>>` и `<<`, как дружественные функции:
// ввод
template <class Stype>
istream& operator >>(istream& stream, Set <Stype> &ob)
{
Stype member;
stream >> member; // ввод элемента
ob = ob + member; // запись элемента в множество
return stream; // возврат результата
}
// вывод
template <class Stype>
ostream &operator << (ostream &stream, Set<Stype> &ob)
{
int i;
for(i = 0; i < ob.NumMembers; i++) //для всех элементов
stream << ob.SetPtr[i] << ' '; //вывод
stream << endl; //после вывода всех элементов
//перевод строки
return stream;
}
Приведём пример программы, использующей параметризованный класс множества:
#include <iostream.h> //библиотека потокового ввода-вывода
#include <conio.h> //библиотека консольного ввода-вывода
#include <process.h> //необходимо для функции exit
const int DEFSET = 100;
template <class Stype>
class Set
{
Stype *SetPtr; // указатель на первый элемент
int MaxSize; // максимальное число элементов
int NumMembers; // количество элементов множества
void insert (Stype member); // добавление элемента
void remove (Stype member); // удаление элемента
int find(Stype member); // поиск элемента
int ismember (Stype member); // принадлежность элемента
public:
Set(); // конструкторы
Set(int size);
Set(const Set &ob); // конструктор копирования
~Set() { delete SetPtr; } // деструктор
Set <Stype> &operator = (Set <Stype> &ob); // присваивание
Set <Stype> operator + (Stype member); // добавление элемента
friend Set<Stype> operator + (Stype member, Set <Stype> ob);
Set <Stype> operator + (Set <Stype> &ob); // объединение
Set <Stype> operator - (Stype member); // удаление элемента
Set <Stype> operator - (Set <Stype> &ob); // разность
Set <Stype> operator & (Set <Stype> &ob); // пересечение
// операции сравнения
int operator == (Set <Stype> &ob); // 1 если равно
int operator!= (Set <Stype> &); // 1 если не равно
int operator < (Set <Stype> &ob); // 1 если подмножество
friend int operator < (Stype member, Set <Stype> ob);
// 1 если элемент множества
operator int() {return NumMembers;} // преобразование в целое
// ввод - вывод
friend istream &operator >> (istream &stream, Set<Stype> &ob);
friend ostream &operator << (ostream &stream, Set<Stype> & ob);
};
//параметризованный конструктор класса, вызываемый по умолчанию
template <class Stype>
Set <Stype>::Set()
{
SetPtr = new Stype [DEFSET]; //выделим память
if(!SetPtr){ cout << "Нет памяти\n";
exit(1);
}
NumMembers = 0; MaxSize = DEFSET;
}
//параметризованный конструктор с заданным числом элементов
template <class Stype>
Set <Stype>::Set(int size)
{
SetPtr = new Stype[size]; //выделим память
if(!SetPtr){ //не удалось
cout << "Нет памяти\n"; exit(1);
}
NumMembers = 0; MaxSize = size;
}
//закрытый член класса, обеспечивающий поиск элемента в множестве
template <class Stype>
int Set <Stype>::find(Stype member)
{
int i;
for (i = 0; i < NumMembers; i++) //поиск во всем множестве
if(SetPtr[i] == member) return i;
return -1; // если такого элемента нет
}
//закрытый член класса, дающий ответ на вопрос:
//принадлежит ли переданное ему значение множеству
template <class Stype>
int Set <Stype>::ismember(Stype member)
{
if (find(member)!= -1) return 1; //произведём поиск
else return 0; //не нашли
}
//закрытый член класса обеспечивающий добавление элемента в множество
template <class Stype>
void Set<Stype>::insert(Stype member) // добавление
{
if(NumMembers == MaxSize) //проверим, не переполнено ли множество
{
cout << "\nПереполнение множества"; exit(1);
}
if(!ismember(member)) // если нет такого элемента
{
SetPtr[NumMembers] = member; // добавить
NumMembers++; // элементов стало на один больше
}
}
//закрытый член класса, обеспечивающий удаление заданного
//элемента множества
template <class Stype>
void Set<Stype>::remove(Stype member)
{
int loc = find(member); //найдём элемент множества
if(loc!= -1) // если элемент найден
{
for(; loc < NumMembers -1; loc++)
SetPtr[loc] = SetPtr[loc+1]; //сдвигаем множество
NumMembers--; //элементов на один стало меньше
}
}
// Конструктор копирования
template <class Stype>
Set<Stype>::Set(const Set<Stype> &ob)
{
int i;
MaxSize = ob.MaxSize;
SetPtr = new Stype[MaxSize]; //выделим память
if(!SetPtr) //если не удалось
{
cout << "\nНет памяти для копирования";
exit(1);
}
NumMembers = 0;
for(i=0; i < ob.NumMembers; i++)
insert(ob.SetPtr[i]); //производим копирование
}
//операция присваивания
template <class Stype>
Set<Stype> &Set<Stype>::operator = (Set<Stype