Построение класса параметризованного ограниченного массива.

#include <iostream.h>

#include <stdlib.h>

// параметризованный класс ограниченого массива

template <class Atype> class atype {

Atype *a;

int length;

public:

atype (int size);

~atype () { delete [] a; }

Atype &operator[] (int I);};

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

template <class Atype> atype<Atype>::atype(int size)

{ length = size;

a = new Atype[size]; // динамически выделение области хранения

if (!a) {cout << "Невозможно выделить массив";

exit (1);}

for (int i=0; i<size; i++) a[i] = 0;}

template <class Atype> Atype &atype<Atype>::operator [] (int i)

{if (i<0 || i>length-1){

cout << "\nЗначение с индексом ";

cout << i << " выходит за пределы диапазона. \n";

exit (1);}

return a[i];}

int main ()

{atype<int> intob(20); // массив целых чисел

atype<double> doubleob(10); // массив рациональных чисел

int i;

cout << "Массив целых: ";

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

{ intob[i] = i;

cout << intob[i] << " ";}

cout << endl;

cout << "Массив дробных чисел: ";

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

{doubleob[i] = (double)i * 3.14;

cout << doubleob[i] << " "; }

cout << endl;

intob[45] = 100; // генерация ошибки

return 0;}

 

Построение параметризованного класса очереди.

#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 add (Qtype x);

Qtype pop (); };

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

template <class Qtype> queue<Qtype>::queue(int size)

{ size++;

q = new Qtype[size];

if (!q) {cout << "Невозможно создать очередь.\n";

exit(1); }

length = size;

sloc = rloc = 0; }

// добавление элемента

template <class Qtype> void queue<Qtype>::add(Qtype i)

{ if (sloc+1==length) {

cout << "Очередь заполнена";

return; }

sloc++;

q[sloc] = i; }

// извлечение элемента

template <class Qtype> Qtype queue<Qtype>::pop()

{ if (rloc == sloc){ cout << "Очередь пуста.\n";

return 0; }

rloc++;

return q[rloc]; }

int main ()

{ queue<int> a(5), b(5);

a.add(100);

b.add(200);

a.add(300);

b.add(400);

cout << "Очередь int 1: ";

cout << a.pop() << " ";

cout << a.pop() << " \n";

cout << "Очередь int 2: ";

cout << b.pop() << " ";

cout << b.pop() << " ";

queue<double> c(5), d(5);

c.add(8.12); d.add(9.23); c.add(-2.2); d.add(0.986);

cout << "Очередь double 1: ";

cout << c.pop() << " ";

cout << c.pop() << " \n";

cout << "Очередь double 2: ";

cout << d.pop() << " ";

cout << d.pop() << " ";

return 0; }

 

 

void Drob::Vvod(void)

{ соut«"Числитель?"; cin»A.P; cout«"Знаменатель?"; cin»A.Q;}

int Drob::NOD(void)

{ int M,N;

M=abs(A.P); N=A.Q;

while(M!=N)

{ if(M>N)

if(M%N!=0) M=M%N; else M=N;

else if(N%M!=0) N=N%M; else N=M;}

return M;}

void Drob::Sokr(void)

{ int X;

X=NOD();

if(A.P!=0)

{ A.P=A.P/X; A.Q=A.Q/X;}

else A.Q=1;}

void Drob::Stepen(int N)

{ int i;

F.P=F.Q=1;

for(i=l;i<=N;i++)

{ F.P*=A.P; F.Q*=A.Q;}}

void Drob::Print(void)

{ cout«"\n"«A.P«"/"«A.Q«"\n"; }

void main(void)

{ Drob Y; //Объявление объекта

cout«"Вводите дробь! "<<"\n";

Y.VvodO;

Y.Sokr ();

cout«"дробь после сокращения:"<<"\n";

Y.Print();

Y.Stepen(2);

cout<<" дробь, возведенная в

квадрат:"<<"\п";

cout «F. P «" / " «F. Q «" \ n "; }

 

Збалансовані дерева. Включення в збалансоване дерево. Два випадки балансування.

Идеально сбалансированным называется дерево, у которого для каждой вершины выполняется требование: число вершин в левом и правом поддеревьях различается не более, чем на 1. Однако идеальную сбалансированность довольно трудно поддерживать. В некоторых случаях при добавлении/удалении может потребоваться значительная перестройка дерева, не гарантирующая логарифмической сложности. Поэтому Г.М.Адельсон-Вельский и Е.М.Ландис ввели менее строгое определение сбалансированности и доказали, что при таком определении можно написать программы добавления/удаления, имеющие логарифмическую сложность и сохраняющие дерево сбалансированным.

Дерево считается сбалансированным, если для каждой вершины выполняется требование: высота левого и правого поддеревьев различаются не более, чем на 1. Не всякое сбалансированное дерево идеально сбалансировано, но всякое идеально сбалансированное дерево сбалансировано.

Вращения.

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

Рассмотрим такие преобразования.

Предварительно договоримся, что в каждой вершине дерева помимо значения элемента будем хранить показатель сбалансированности в данной вершине. Показатель сбалансированности - разница между высотами правого и левого поддеревьев.

PTree = ^ATTree; TTree = record

Item: T; {элемент дерева}

Left, Right: PTree; {указатели на поддеревья} Balance: ShortInt; {показатель сбалансированности} end;

В сбалансированном дереве показатели сбалансированности всех вершин лежат в пределах от - 1 до 1. При операциях добавления/удаления могут появляться вершины с показателями сбалансированности -2 и 2.

А теперь перейдем к рассмотрению преобразований.

Малое левое вращение.

Пусть показатель сбалансированности вершины, в которой произошло нарушение баланса, равен -2, а показатель сбалансированности корня левого поддерева равен -1. Тогда восстановить сбалансированность такого поддерева можно следующим преобразованием, называемым малым левым вращением:

На приведенном рисунке прямоугольниками обозначены поддеревья. Рядом с поддеревьями указана их высота. Поддеревья помечены арабскими цифрами. Кружочками обозначены вершины. Цифра рядом с вершиной - показатель сбалансированности в данной вершине. Буква внутри кружка - условное обозначение вершины.

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

Малое правое вращение.

В случае, когда показатель сбалансированности вершины, в которой произошло нарушение баланса, равен 2, а показатель сбалансированности корня правого поддерева равен 1, восстановить сбалансированность в вершине можно с помощью преобразования, называемого малым правым вращением. Это вращение симметрично малому

показатели сбалансированности проходимых вершин и производится балансировка там, где это необходимо. Добавление элемента в дерево никогда не требует более одного поворота.