шпоры5 (1079657), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

virtual void who() {cout<<”1”<<endl;}};

class first_d:public base

{public:

void who() {cout<<”2”<<endl;}};

class second_d:public base

{public:

void who() {cout<<”3”<<endl;}};

int main()

{base base_obj;

base *p;

first_d first_obj;

second_d second_obj;

p=&base_obj;

p->who();

p=& first_obj;

p->who();

p=& second_obj;

p->who();

return 0;}

При выполнении эта программа генерирует такие результаты.

1 2 3

Виртуальную функцию можно вызвать и не через указатель, используя оператор точка, например.

first_obj.who();

Если виртуальная функция переопределяется в производном классе, ее называют переопределенной.

Атрибут virtual передается по наследству.

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

Р указатель на обьект класса ,через него вызывают поле(данные) обьекта класса.

49. Двоичные деревья поиска.

Для организации поиска в основной памяти особое значение имеют упорядоченные двоичные (бинарные) деревья (рис 4.3). В каждом таком дереве естественно определяются левое и правое поддеревья. Двоичное дерево называется идеально сбалансированным, если число вершин в его левом и правом поддеревьях отличается не более, чем на 1 (легко видеть, что при соблюдении этого условия длины пути до любой листовой вершины дерева отличаются не больше, чем на 1). Примеры идеально сбалансированных деревьев показаны на рисунке 4.5. Двоичные деревья обычно представляются как динамические структуры с базовым типом записи T, в число полей которого входят два указателя на переменные типа T.

При использовании в целях поиска элементов данных по значению уникального ключа применяются двоичные деревья поиска, обладающие тем свойством, что для любой вершины дерева значение ее ключа больше значения ключа любой вершины ее левого поддерева и больше значения ключа любой вершины правого поддерева (рисунок 4.7). Для поиска заданного ключа в дереве поиска достаточно пройти по одному пути от корня до (возможно, листовой) вершины (рисунок 4.7). Высота идеально сбалансированного двоичного дерева с n вершинами составляет не более, чем log n (логарифм двоичный), поэтому при применении таких деревьев в качестве деревьев поиска (рисунок 4.8) потребуется не более log n сравнений.

Рис. 4.7. Путь поиска ключа по знач. “23” Рис. 4.8. Идеально сбаланс двоичное дерево

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

Характеристики

Список файлов лабораторной работы