double arrow

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


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

Неотсортированные BCD числа:

+00000000001234

+00000000000924

-00000000000092

+00000000000000

-00000000000001

+00000000000010

+00000000000012

+00000000000001

-00000000000002

+00000000012345

Отсортированные BCD числа:

-00000000000092

-00000000000002

-00000000000001

+00000000000000

+00000000000001

+00000000000010

+00000000000012

+00000000000924

+00000000001234

+00000000012345

Пример. Рассмотрим параметризованную подпрограмму (функцию) сортировки методом выбора. Сначала находим наименьший элемент массива и переставляем его с первым элементом. Затем из оставшихся элементов находим наименьший и переставляем его со вторым элементом и т.д. Для того чтобы не переставлять элемент сам с собой в том случае, когда он уже является наименьшим среди элементов подмассива, определим переменную exchange, которая будет равна 0, если перестановки не нужны. Получим следующую подпрограмму:

template <class Type>

void select(Type *x, int count)

{

int i, j, k, exchange;

Type t;

for(i=0; i<count-1; i++)

{

exchange=0;

k=i; t=x[i];

for(j=i+1; j<count; j++)

{

if(x[j]<t)

{

k=j; t=x[j]; exchange=1;

}

}

if(exchange)

{

x[k]=x[i]; x[i]=t;

}

}

}

Вызов подпрограммы осуществляется слудующим образом :

int nums[] = {1, 3, 8, -1, 12, -1, 15};

Select(nums, 7);

Пример. Рассмотрим параметризованную функцию быстрой сортировки Хоара. Алгоритм быстрой сортировки опирается на идею разбиения массива на две части с последующим рекурсивным применением подпрограммы сортировки к каждой из этих частей. Перед разбиением выбирается некоторый элемент массива, значение которого называется компарандом.

Все элементы, значения которых меньше компаранда, переносятся в левую часть массива, а элементы, имеющие большее значение – в правую часть. Затем этот же процесс повторяется для каждой из частей. И так до тех пор, пока массив не будет отсортирован. Ниже приведён текст программы.

#include <iostream.h> //библиотека потокового ввода-вывода

#include <conio.h> //библиотека консольного ввода-вывода

//параметризованная функция быстрой сортировки Хоара

template <class Type>

void qs(Type *a, int left, int right)

{

int i, j; //левая и правая границы массива

Type x, y;

i = left; j = right;

x = a[(left+right)/2]; //определим "центр" массива

do

{

//произведём поиск элементов для перестановки

while(a[i]<x && i<right) i++;

while(x<a[j] && j>left) j--;

if(i<=j)

{

//выполняем перестановку

y=a[i]; a[i]=a[j]; a[j]=y;

i++; j--;

}

}

while(i<=j);

if(left<j) qs(a, left, j); //рекурсивный вызов для левой части

if(i<right) qs(a, i, right);//рекурсивный вызов для правой части

}

//основная программа

void main()

{

int i;

int nums[]={5, 10, 12, 3, 8, 9, 2, 1}; //массив чисел для сортировки

clrscr();

cout<<"Входные данные (неотсортированный массив):\n";

for(i=0; i<8; i++) cout << nums[i] << " ";

qs(nums, 0, 7); //вызов подпрограммы сортировки

cout<<"\nВыходные данные (отсортированный массив):\n";

for(i=0; i<8; i++) cout << nums[i] << " ";//вывод результатов на экран




}

Входные данные (неотсортированный массив):

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> &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; //возврат нового множества

}

//операция удаления элемента из множества

template <class Stype>

Set<Stype> Set<Stype>::operator-(Stype member)

{

int i;

Set<Stype> temp = *this;

temp.remove(member); // удаление элемента

return temp; // возврат множества

}

//операция разности двух множеств

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; // возврат результата

}

//Операция пересечения множеств

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; // возврат результата

}

// 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;

}

// ввод

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;

}

void main (void)

{

Set <char> a(5);

Set <char> b(5);

Set <char> d(5);

Set <char> temp(5);

clrscr();

cout << "Введите первое множество :\n";

cin >> a;

cin >> a;

cin >> a;

cin >> a;

cin >> a;

cout << "Введите второе множество :\n";

cin >> b;

cin >> b;

cin >> b;

cin >> b;

cin >> b;

cout << "Первое множество:"<<a;

cout << "Количество его элементов: "<<int(a)<<"\n";

cout << "Второе множество:"<<b;

cout << "Объединение множеств: "<<a+b;

cout << "Разность множеств: "<<a-b;

temp=a;

d=a&b;

cout << "Пересечение множеств: "<<d;

temp=temp-'a';

cout << "Первое множество после удаления элемента 'a' : "<<temp;

cout << "Проверка на принадлежность элемента 'f' второму множеству:\n";

if (b<'f')

{

cout <<"Элемент принадлежит множеству\n";

}

else

{

cout <<"Элемент не принадлежит множеству\n";

}

cout << "Проверка на равенство двух данных множеств:\n";

temp=temp+'a';

if (b==temp)

{

cout <<"Множества равны\n";

}

else

{

cout <<"Множества не равны\n";

}

return;

}

Заказать ✍️ написание учебной работы
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой

Сейчас читают про:
Поможем в написании
> Курсовые, контрольные, дипломные и другие работы со скидкой до 25%
3 569 лучших специалисов, готовы оказать помощь 24/7