шпоры6 (1079660)

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

Текст из файла

1. Абстрактные классы и их применение

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

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

virtual тип имя_функции (список_параметров)=0;

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

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

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

1. Вставка и удаление вершин из двоичных деревьев поиска

Придерживаясь естественной для графового представления терминологии, мы будем называть связи между поддеревьями ветвями, а корень каждого поддерева - вершиной. По определению, корень дерева находится на уровне 0, а все вершины дерева, непосредственно связанные с вершиной уровня i, находятся на уровне i+1. Вершина x уровня i, непосредственно связанная с вершиной y уровня i+1, называется непосредственным предком (или родителем) вершины y. Такая вершина y соответственно называется непосредственным потомком (или сыном) вершины x. Вершина без непосредственных потомков называется листовой (или терминальной), нелистовые вершины называются внутренними. Под степенью внутренней вершины понимается число ее непосредственных потомков.

Для включения в дерево вершины с новым ключом x по общим правилам поиска ищется листовая вершина, в которой находился бы этот ключ, если бы он входил в дерево. Возможны две ситуации: (a) такая вершина не существует; (b) вершина существует и уже занята, т.е. содержит некоторый ключ y. В первой ситуации создается недостающая вершина, и в нее заносится значение ключа x. Во второй ситуации после включения ключа x эта вершина в любом случае становится внутренней, причем если x > y, то ключ x заносится в новую листовую вершину - правого сына y, а если x < y - то в левую. Четыре потенциально возможных случая проиллюстрированы на рисунке 4.9.

(a) (b) (c)

(d) (e)
Рис. 4.9.

При выполнении исключения ключа из дерева также прежде всего выполняется поиск ключа. Если ключ обнаруживается, то возможны следующие случаи: (a) ключ содержится в листовой вершине, у вершины-отца которой имеются два сына; (b) ключ содержится в листовой вершине, являющей единственным сыном своего отца; (c) ключ содержится во внутренней вершине, имеющей только левого или только правого сына; (d) ключ содержится во внутренней вершине, имеющей и левого, и правого сыновей. В случае (a) соответствующая листовая вершина ликвидируется, а у ее отца остается только один сын. В случае (b) листовая вершина ликвидируется, а ее отец становится новой листовой вершиной. В случае (c) внутренняя вершина ликвидируется, и ее место занимает единственный сын (он может быть внутренней или листовой вершиной. В случае (d) внутренняя вершина ликвидируется, и заменяется на листовую или внутреннюю вершину, достигаемую по самому правому пути от левого сына внутренней вершины. Эта вершина наследует левого и правого сыновей ликвидируемой вершины. Возможные варианты иллюстрируются на рисунке 4.10.

(a) (b) (c)

(d) (e) (f)
Рис. 4.10. Исключение ключа из двоичного дерева

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

Контейнеры

Библиотека STL имеет в своем арсенале элементы, называемые контейнерами. Контейнеры - это объекты, хранящие в себе другие объекты. В STL таких контейнеров десять:

vector - массив с произвольным доступом, чаще всего применяемый в тех случаях, когда надо последовательно добавлять данные в конец цепочки;

list - похож на вектор, но эффективен при добавлении и удалении данных в любое место цепочки;

deque - контейнер, удобный для вставки данных в начало или конец;

set - набор уникальных элементов, отсортированных в определенном порядке;

multiset - то же, что и set, но может содержать повторяющиеся копии;

map - обеспечивает доступ к значениям по ключам;

multimap - то же, что и map, но допускающий повторяющиеся ключи;

stack - данные добавляются в одном порядке, а вынимаются в обратном;

queue - данные добавляются и вынимаются в том же порядке;

priority queue - то же, что и queue, но может сортировать данные по приоритету.

Функциональные объекты

Функциональные объекты - это объекты, у которых задан перегруженный оператор вызова функции "operator ()()". Они очень важны для эффективного использования.

Функциональными объектами являются все арифметические операторы: сложения, вычитания, умножения, деления, взятия остатка и обращения знака. Имеются функциональные объекты для вычисления равенства, неравенства, операции "больше", операции "меньше"операции "больше или равно", операции "меньше или равно". Для логических операторов имеются свои функциональные объекты: логическое "и", логическое "или" и логическое "не".

1. Сравнение статического и динамического связывания классов

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

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

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

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

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

Пример позднего связывания:

#include <iostream>

class Mammal

{ public:

Mammal ( ) : itsAge (1){ }

~Mammal ( ) { }

virtual void Speak ( ) const {std::cout<<”Mammal speak!\n”;}

protected:

int itsAge; };

class Dog: public Mammal

{public:

void Speak ( ) const { std:: cout<<”Woof!\n”;}}

class Cat : public Mammal

{public:

void Speak ( ) const { std::cout<<”Meow!\n”;}}

int main

{ Mamml*array [3];

Mammal*ptr;

int choice, i;

for (i=0, i<3, i++)

{ std::cin>>choice;

switch (choice)

{ case 1: ptr =new Dog; break;

case 2: ptr =new Cat; break;

default: ptr =new Mammal; break;}

array [i]= ptr;}

for (i=0, i<3, i++) array [i]->Speak ( );

return 0;}

На момент компиляции неизвестно, какие именно объекты будут созданы, а следовательно, какие из методов Speak( ) использованы. Указатель ptr привязывается к своему объекту только в процессе выполнения. Это называется поздним связыванием, или связыванием в процессе выполнения( динамическим), в отличие от статического связывания, или связывания во время компиляции (раннего).

Статическое( ранее) связывание:

Например, базовый класс figure может описывать фигуру на экране без конкретизации ее вида, а производные классы (треугольник, эллипс и т.п.) однозначно определяют ее формы и размеры. Если в базовом классе ввести функцию для изображения фигуры на экране, то выполнение этой функции будет возможно только для объектов каждого из производных классов, определяющих конкретные изображения. Пусть в этом классе определена компонентная функция void show(). Так как внешний вид фигуры в базовом классе еще не определен, то в каждый из производных классов нужно включить свою функцию void show() для формирования изображения на экране. Доступ к функции show() производного класса возможен только с помощью явного указания области видимости:

имя_производного_класса::show()

или имя_объекта_производного_класса.show()

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

51.Структура стандартной библиотеки шаблонов.

Библиотека стандартных шаблонов (Standard template Library - STL) представляет шаблонные классы и функции общего назначения, которые реализуют многие популярные и часто используемые алгоритмы и структуры данных. Например она включает в себя поддержку векторов, списков, очередей и стеков, а также определяет различные функции, а также определяет различные функции, обеспечивающие к ним доступ. Поскольку STL состоит из шаблонных классов, алгоритмы и структуры данных могут быть применены к данным практически любого типа.

То есть библиотека STL – это набор шаблонных классов и функций общего назначения.

Ядро STL включает три основных элемента: контейнеры, алгоритмы, итераторы и функциональные объекты.

Они работают совместно один с другим, представляя тем самым готовые решения различных задач программирования.

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

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

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

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

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