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

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

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

int sum();

protected:

int asdf;};

class qwer : public inf

{int p;

public:

void func();};

class qwer1 : public qwer

{int p1;

public:

void func1();};

Если базовый класс наследуется закрытым способом, защищенные члены этого базового класса становятся закрытыми (private) членами производного класса. То есть при повторном наследовании(наследовании первого производного класса вторым производным в качестве базового) второму производному классу защищенные члены становятся недоступны.

class inf

{int a;

double b;

public:

void num();

int sum();

protected:

int asdf;};

class qwer : private inf

{int p;

public:

void func();}; (конец)

45. Построение списков при помощи массивов

Для построения списка при помощи массива необходимо выделение массива очень большого размера, для того чтобы учесть возможность вставки элементов между имеющимися элементами списка. Исходя из предположения, что может возникнуть необходимость вставки максимум n элементов между уже существующими, нам необходимо выделить массив размера k+k*(n-1), где k-количество начальных элементов. В результате мы получаем большой статический массив, который прост в обработке (за счет замены работы с указателями как в стандартном случае при работе с индексами-целыми числами), но очень объемен.

1. Типы наследования классов (нач. – 19 вопр.)

Простое наследование

Класс, от которого произошло наследование, называется базовым или родительским (англ. base class). Классы, которые произошли от базового, называются потомками, наследниками или производными классами (англ. derived class).

В некоторых языках используются абстрактные классы. Абстрактный класс — это класс, содержащий хотя бы один абстрактный метод, он описан в программе, имеет поля, методы и не может использоваться для непосредственного создания объекта. Т.е. от Абстрактного класса можно только наследовать. Объекты создаются только на основе производных классов, наследованных от абстрактного. Например, абстрактным классом может быть базовый класс «сотрудник ВУЗа», от которого наследуются классы «аспирант», «профессор» и т.д. Т.к. производные классы имеют общие поля и функции (например, поле «год рождения»), то эти члены класса могут быть описаны в базовом классе. В программе создаются объекты на основе классов «аспирант», «профессор», но нет смысла создавать объект на основе класса «сотрудник вуза».

Множественное наследование

При множественном наследовании у класса может быть более одного предка. В этом случае класс наследует методы всех предков. Достоинства такого подхода в большей гибкости. Множественное наследование реализовано в C++. Из других языков, предоставляющих эту возможность, можно отметить Python. Множественное наследование поддерживается в языке UML.

Множественное наследование — потенциальный источник ошибок, которые могут возникнуть из-за наличия одинаковых имен методов в предках. В языках, которые позиционируются как наследники C++ (Java, C# и др.), от множественного наследования было решено отказаться в пользу интерфейсов. Практически всегда можно обойтись без использования данного механизма. Однако, если такая необходимость все-таки возникла, то, для разрешения конфликтов использования наследованных методов с одинаковыми именами, возможно, например, применить операцию расширения видимости - "::" - для вызова конкретного метода конкретного родителя.

Большинство современных объектно-ориентированных языков программирования (C#, Java, Delphi и др.) поддерживает возможность одновременно наследоваться от класса-предка и реализовать методы нескольких интерфейсов одним классом. Этот механизм позволяет во многом заменить множественное наследование — методы интерфейсов необходимо переопределять явно, что исключает ошибки при наследовании функциональности одинаковых методов различных классов-предков.

Наследование в языке C++

«Наследование» в C++:

class A{ //базовый класс};

class B : public A{ //public наследование}

class C : protected A{ //protected наследование}

class Z : private A{ //private наследование}

В C++ существует три типа наследования: public, protected, private. Спецификаторы доступа членов базового класса меняются в потомках следующим образом:

-----при public-наследовании все спецификаторы остаются без изменения.

-----при protected-наследовании все спецификаторы остаются без изменения, кроме спецификатора public, который меняется на спецификатор protected (то есть public-члены базового класса в потомках становятся protected).

-----при private-наследовании все спецификаторы меняются на private.

Одним из основных преимуществ public-наследования является то, что указатель на классы—наследники может быть неявно преобразован в указатель на базовый класс, то есть для примера выше, можно написать

A* a = new B;

47. Древовидные структуры данных. Двоичные деревья.

Деревья- это математические абстракции, которые играют главную роль при разработке и анализе алгоритмов, так как

-деревья используются для описания динамических свойств алгоритмов

-играют важную роль во всевозможных прикладных проявлениях.

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

Рассмотрим бинарные(двоичные) деревья, поскольку если бинарное дерево отсортировано, оно позволит быстро осуществить поиск, вставку и удаление элементов.

Двоичное дерево - это дерево, у которого каждый узел имеет не более двух наследников. Пример бинарного дерева приведен на рис. 1. Предполагая, что k содержит значение, хранимое в данном узле, мы можем сказать, что бинарное дерево обладает следующим свойством: у всех узлов, расположенных слева от данного узла, значение соответствующего поля меньше, чем k, у всех узлов, расположенных справа от него, - больше. Вершину дерева называют его корнем, узлы, у которых отсутствуют оба наследника, называются листьями. Корень дерева содержит 20, а листья - 4, 16, 37 и 43. Высота дерева - это длина наидлиннейшего из путей от корня к листьям. В нашем примере высота дерева равна 2.

Чтобы найти в дереве какое-то значение, мы стартуем из корня и движемся вниз. Например, для поиска числа 16, мы замечаем, что 16 < 20, и потому идем влево. При втором сравнении видим, что 16 > 7, и потому мы движемся вправо. Третья попытка успешна - мы находим элемент с ключом, равным 16.

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

Рис. 2: Несбалансированное бинарное дерево

Двоичное дерево называется сбалансированным, если число вершин в его левом и правом поддеревьях отличается не более, чем на 1.

1. Раннее и позднее связывание классов

При обсуждении объектно-ориентированных языков обычно используются два термина: раннее связывание(early binding) и позднее связывание(late binding). В C++ эти термины связывают с событиями, которые происходят во время компиляции и в период выполнения программы соответственно.

При раннем связывании вызов функции подготавливается во время компиляции, а при позднем- во время выполнения программы.

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

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

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

1. Алгоритмы обхода вершин двоичных деревьев.

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

template<class T>

void walkTree(TNode<T>* p) {

if(p) {

walkTree(p->pleft);

cout << p->value << ' ';

walkTree(p->pright);}}

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

Например, нерекурсивная функция для обхода дерева может выглядеть так:

template<class T>

void walkNotRec(TNode<T>* tree) {

if (tree) {

TNode<T> temp;

TNode<T>* ptemp = &temp;

TNode<T>* p = ptemp, *c = tree, *w;

while (c != ptemp) {

cout << c->value;

w = c->pleft;

c->pleft = c->pright;

if(c == p)

c->pright = 0;

else

c->pright = p;

p = c;

if (w) c = w;} }}

Обход дерева – систематическая обработка всех узлов. Рассмотрим процесс для двоичных деревьев. Существуют две связи, и, следовательно, три основных порядка возможного посещения узлов:

1)Прямой обход (сверху вниз), при котором мы посещаем узел, а затем левое и правое поддеревья,

2) Поперечный обход (слева направо), при котором мы посещаем левое поддерево, затем узел, а затем правое поддерево,

3) Обратный обход (снизу вверх), при котором мы посещаем левое и правое поддеревья, а затем узел.

Можно также рассмотреть нерекурсивные реализации, в которых используется явный стек. Для простоты мы начнем с рассмотрения абстрактного стека, содержащего элементы дерева, инициализированного деревом, которое требуется обойти. Затем мы войдем в цикл, в котором выталкивается и обрабатывается верхняя запись стека, и который продолжается, пока стек не опустеет. Если вытолкнутая запись является элементом, мы посещаем его, если деревом, мы выполняем последовательность операций выталкивания, которая зависит от требуемого порядка:

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

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

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

1. Виртуальные методы классов

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

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

Чтобы объявить функцию виртуальной, достаточно предварить ее объявление ключевым словом virtual. При переопределении виртуальной функции в производном классе ключевое слово virtual повторять не нужно.

Класс, который включает виртуальную функцию, называется полиморфным классом. Этот термин также применяется к классу, который наследует базовый класс, содержащий виртуальную функцию.

#include <iostream>

using namespace std;

class base

{public:

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

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