Повороты
Повороты необходимы, когда корень (родительский узел) R становится разбалансированным. Рассмотрим повороты вправо.
Одинарный поворот вправо
Происходит тогда, когда R и его левый потомок A начинают перевешивать влево после включения узла в позицию X.
В результате поворота узел A замещает корень R, который становится правым потомком узла A. Бывшее правое поддерево B узла A присоединяется к R в качестве левого поддерева. Это сохраняет упорядоченность, т.к. узлы в B больше узла A, но меньше узла R. Поворот уравновешивает как родителя R, так и его левого потомка A.
Пример
Двойной поворот вправо
Происходит тогда, когда корень R становится перевешивающим влево, а его левый потомок A – перевешивающим вправо. B – корень правого перевешивающего поддерева узла A. Возможны два случая.
1-й случай
2-й случай
В результате поворота узел B замещает корень R.
Пример
Самостоятельно: 1) пример на одинарный поворот влево, 2) пример на двойной поворот влево.
Классы и объектно-ориентированное программирование
Класс – пользовательский тип данных. Появился по причине недостатков программирования с использованием структур:
struct time{
int h, m, s;
} t;
Мало операций со структурами – только присваивание однотипных структур.
Структуры не могут быть выведены как единое целое: можно выводить только по одному элементу с соответствующим форматированием.
Инициализация структур не обязательно, поэтому возможно появление данных с неизвестными начальными значениями.
Если данные получат начальные значения, то они могут быть неверными, т.к. программист имеет прямой доступ к данным.
При изменении реализации структурного типа необходимо редактировать всю программу, т.к. в структурах отсутствует интерфейс, который должен гарантировать правильное использование типов данных и непротиворечивость данных.
Объявление класса
class time{
public:
time(); //функции-
void settime(int, int, int); //элементы
void printtime(); //класса
private:
` int h; //данные-
int m; //элементы
int s; //класса
};
Метки public:, private:, protected: - открытый, закрытый, защищенный – спецификаторы доступа к элементам класса. Могут появляться в объявлении класса любое число раз и в любом порядке. Рекомендуется – один раз и первым - public:. По умолчанию – в структуре - public:, в классе - private:.
Раздел public: - это интерфейсная часть класса. Здесь элементы доступны через имя объекта класса, ссылку на объект, указателя на объект, т.е. доступны вне класса.
В разделах private:, protected: элементы доступны только функциям-элементам класса и дружественным функциям класса, т.е. недоступны вне класса.
Функции-элементы и данные-элементы могут находиться в любых разделах класса. Рекомендуется размещать данные-элементы в закрытой части класса.
Определение класса (реализация класса)
#include <iostream.h>
class time{
…………….
};
//----------------------------------------------------------------------------------------------
//Определение конструктора класса time();
time::time() { h=m=s=0; }
Разные классы могут иметь функции-элементы с одинаковыми именами. Для идентификации функций-элементов данного класса используется операция (::) разрешения области действия или доступа к области действия (time::).
Конструктор класса time() – функция-элемент, вызываемая автоматически при создании объекта класса, присваивает начальные значения каждому данному-элементу, обеспечивает согласованное начальное состояние всех объектов класса.
//----------------------------------------------------------------------------------------------
//Определение функции-элемента void settime(int, int, int);
void time::settime(int hs, int ms, int ss)
{ h=(hs>=0&&hs<24)?hs:0;
m=(ms>=0&&ms<60)?ms:0;
s=(ss>=0&&ss<60)?ss:0;
}
Эта функция-элемент задает новые параметру объекту. Проверяет правильность значений данных. Обнуляет неверные значения.
//----------------------------------------------------------------------------------------------
//Определение функции-элемента void printtime();
void time::printtime()
{ cout<<(h<10?”0”:””)<<h<<”:”
<<(m<10?”0”:””)<<m<<”:”
<<(s<10?”0”:””)<<s; //пример: 05:12:09
}
Эта функция-элемент не имеет параметров. В этом нет необходимости, т.к. функции-элементы имеют прямой доступ к элементам класса.
//----------------------------------------------------------------------------------------------