Замечание Виртуальными не могут быть только конструкторы и статические функции. Подумайте почему.
Использование виртуальных функций позволяет реализовать механизм позднего связывания, когда требуемая реализация функции выбирается на этапе выполнения программы. Рассмотрим, как реализуется механизм позднего связывания.
Когда в базовом классе объявляется хотя бы одна виртуальная функция, для всех полиморфных классов (базового и всех его производных) создаётся единая таблица виртуальных функций.
Помимо создания таблицы виртуальных функций в базовом классе создается специальный скрытый указатель на данную таблицу. Этот указатель наследуется всеми производными классами. При вызове виртуальной функции компилятор обращает внимание не на тип объекта, а осуществляет поиск требуемой реализации функции по таблице виртуальных функций.
Вернемся к нашему примеру. Объявим функцию Show в базовом классе Point как виртуальную функцию: virtual void
Show(
string info)
{ cout <<
"Point "
<< info <<
": ("
<< x <<
", "
<< y <<
")"
<< endl;
}
Тогда при выполнении фрагмента программы, приведенного в начале п.4.3., мы получим правильный результат:
Point: (1, 1)
Point: (2, 2, 2)
Point: (3, 3, 3)
Point: (4, 4)
31
4.4.
Абстрактные классы и чисто виртуальные функции
Иногда полезно создать базовый класс, определяющий только своего рода "пустой бланк", который унаследуют все производные классы, причем каждый из них заполнит этот "бланк" собственной информацией. Такой класс определяет структуру функций, а их реализации будут предложены позже. Подобная ситуация может возникнуть в случае многоуровневого наследования, когда базовый класс просто не может предложить реализацию запланированных функций. Решить данную проблему можно с помощью абстрактных классов и чисто виртуальных функций.
Виртуальная функция, не имеющая тела, называется чистой виртуальной функцией и определяется следующим образом: virtual <тип функции>
<имя функции> (<список параметров>) = 0;
Класс, в котором есть хотя бы одна чистая виртуальная функция, называется абстрактным классом. Объекты абстрактного класса создавать запрещено. И при передаче параметра в функцию невозможно передать объект абстрактного класса по значению, т.к. нельзя создать его копию.
При наследовании абстрактность сохраняется. Если класс-наследник не реализует унаследованную чистую виртуальную функцию, то он тоже является абстрактным. Часто абстрактные классы являются вершиной иерархии классов.
В качестве примера рассмотрим следующую трехуровневую иерархию объектов:
Стрелки с окончанием в виде черного треугольника показывают направление наследования (от производного класса к базовому), а стрелки с белым ромбом на конце - агрегацию. В данном случае агрегация говорит о том, что поле класса Circle будет являться указателем на объект класса Point, т.к. центр окружности является точкой.
Рассмотрим реализацию данной иерархии объектов:
#include
#include
using namespace std; class
Object
//Абстрактный класс
{ public
:
32
virtual void
Show() = 0; virtual double
GetDistance() = 0;
}; class
Point
: public
Object
//Класс - точка на плоскости
{ protected
: int x; int y; public
:
Point(): x(0), y(0) {}
Point(
int x, int y): x(x), y(y) {} void
Show()
{ cout <<
"Point:"
; cout <<
" ("
<< x <<
", "
<< y <<
")"
<< endl;
} double
GetDistance()
{ return sqrt((
double
)(x*x+y*y));
} int
GetX()
{ return x;
} int
GetY()
{ return y;
}
}; class
PointSpace
: public
Point
//Класс - точка в пространстве
{
protected
: int z; public
:
PointSpace():
Point
(), z(0) {}
PointSpace(
int x, int y, int z):
Point
(x, y), z(z) {} void
Show()
{ cout <<
"Point "
<< info <<
":"
; cout <<
" ("
<< x <<
", "
<< y <<
", "
<< z <<
")"
<< endl;
}
33
double
GetDistance()
{ return sqrt((
double
)(x*x + y*y + z*z));
} int
GetZ()
{ return z;
}
}; class
Circle
: public
Object
//Класс - окружность на плоскости{ protected
:
Point
*a;
//проявление агрегации: поле класса Circle является//указателем на объект класса Point int radius; public
:
Circle(): radius(O)
{ a = new
Point
();
//неявная инициализация центра окружности}
Circle(
int х, int у, int radius): radius(radius)
{ a = new
Point
(x, у);
//явная инициализация центра окружности} void
Show()
{ cout <<
"Circle: "
; cout <<
"center ("
<< a->GetX() <<
", "
<< a->GetY() <<
"), "
; cout <<
"radius "
<< radius << endl;
} double
GetDistance()
{ return sqrt((
double
)(a->GetX()*a->GetX()+a->GetY()*a->GetY()));
}
Circle()
{ delete а;
//освобождаем память, связанную с указателем а}
}; int main()
{
Object
*objects [6];
//массив указателейobjects[0] = new
Point
(1, 1); objects[1] = new
PointSpace
(2, 2, 2); objects[2] = new
Circle
(0, 0, 3);
34
objects[3] = new
Circle
(4, 3. 10); objects[4] = new
PointSpace
(-1,2, -
1); objects[5] = new
Point
(0,2); for
(
int i = 0; i < 6; i++)
{ objects[i]->Show(); cout <<
"Distance: "
<< objects[i]->GetDistance() << endl;
} for
(
int i = 0; i < 6; i++)
{ delete objects[i];
} return
0;
}
Результат работы:
Point: (1,1)
Distance: 1.41421
Point: (2, 2, 2)
Distance: 3.4641
Circle: center (0, 0), radius 3
Distance: 0
Circle: center (4, 3), radius 10
Distance: 5
Point: (-1, 2, 1)
Distance: 2.44949
Point: (0, 2)
Distance: 2
4.5.
Практикум №2
Замечание. Перед выполнением задания продумайте и опишите полную структуру классов и их взаимосвязь.
Задание 1
1.
Создать абстрактный класс Figure с функциями вычисления площади и периметра, а также функцией, выводящей информацию о фигуре на экран.
2.
Создать производные классы: Rectangle (прямоугольник), Circle (круг), Triangle
(треугольник).
3.
Создать массив n фигур и вывести полную информацию о фигурах на экран.
Задание 2
1.
Создать абстрактный класс Function с функциями вычисления значения по формуле y=f(x) в заданной точке, а также функцией, выводящей информацию о виде функции на экран.
2.
Создать производные классы: Line (y=ax+b), Cube (y=ax
2
+bx+c), Hyperbola (у=а/х).
3.
Создать массив n функций и вывести полную информацию о значении данных функций в точке х.
35
Задание 3 1.
Создать абстрактный класс Edition с функциями, позволяющими вывести на экран информацию об издании, а также определить, является ли данное издание искомым.
2.
Создать производные классы: Book (название, фамилия автора, год издания, издательство), Article (название, фамилия автора, название журнала, его номер и год издания), OnlineResource (название, фамилия автора, ссылка, аннотация).
3.
Создать каталог (массив) из n изданий, вывести полную информацию из каталога, а также организовать поиск изданий по фамилии автора.
Задание 4 1.
Создать абстрактный класс Transport с функциями, позволяющими вывести на экран информацию о транспортном средстве, а также определить грузоподъемность транспортного средства.
2.
Создать производные классы: Саг (марка, номер, скорость, грузоподъемность),
Motorbike (марка, номер, скорость, грузоподъемность, наличие коляски, при этом если коляска отсутствует, то грузоподъемность равна 0), Truck (марка, номер, скорость, грузоподъемность, наличие прицепа, при этом если есть прицеп, то грузоподъемность увеличивается в два раза).
3.
Создать базу (массив) из n машин, вывести полную информацию из базы на экран, а также организовать поиск машин, удовлетворяющих требованиям грузоподъемности.
Задание 51.
Создать абстрактный класс Persona с функциями, позволяющими вывести на экран информацию о персоне, а также определить ее возраст (на момент текущей даты).
2.
Создать производные классы: Enrollee (фамилия, дата рождения, факультет), Student
(фамилия, дата рождения, факультет, курс), Teacher (фамилия, дата рождения, факультет, должность, стаж).
3.
Создать базу (массив) из n персон, вывести полную информацию из базы на экран, а также организовать поиск персон, чей возраст попадает в заданный диапазон.
Задание 6 1.
Создать абстрактный класс Goods с функциями, позволяющими вывести на экран информацию о товаре, а также определить, соответствует ли он сроку годности на текущую дату.
2.
Создать производные классы: Product (название, цена,
дата производства, срок годности), Party (название, цена, количество (шт), дата производства, срок годности),
Kit (название, цена, перечень продуктов).
3.
Создать базу (массив) из n товаров, вывести полную информацию из базы на экран, а также организовать поиск просроченного товара (на момент текущей даты).
36
Задание 71.
Создать абстрактный класс Goods с функциями, позволяющими вывести на экран информацию о товаре, а также определить, соответствует ли она искомому типу.
2.
Создать производные классы: Toy (название, цена, производитель, материал, возраст, на который рассчитана), Book (название, автор, цена, издательство, возраст, на который рассчитана), SportsEquipment (название, цена, производитель, возраст, на который рассчитан).
3.
Создать базу (массив) из n товаров, вывести полную информацию из базы на экран, а также организовать поиск товаров определенного типа.
Задание 8 1.
Создать абстрактный класс TelephoneDirectory с функциями, позволяющими вывести на экран информацию о записях в телефонном справочнике, а также определить соответствие записи критерию поиска.
2.
Создать производные классы: Persona (фамилия, адрес, номер телефона),
Organization (название, адрес, телефон, факс, контактное лицо), Friend (фамилия, адрес, номер телефона, дата рождения).
3.
Создать базу (массив) из n записей, вывести полную информацию из базы на экран, а также организовать поиск в базе по фамилии.
Задание 9 1.
Создать абстрактный класс Client с функциями, позволяющими вывести на экран информацию о клиентах банка, а также определить соответствие клиента критерию поиска.
2.
Создать производные классы: Depositor (фамилия, дата открытия вклада, размер вклада, процент по вкладу), Credited (фамилия, дата выдачи кредита, размер кредита, процент по кредиту, остаток долга), Organization (название, дата открытия счета, номер счета, сумма на счету).
3.
Создать базу (массив) из n клиентов, вывести полную информацию из базы на экран, а также организовать поиск клиентов, начавших сотрудничать с банком с заданной даты.
Задание 10 1.
Создать абстрактный класс Software с методами, позволяющими вывести на экран информацию о программном обеспечении, а также определить соответствие возможности использования (на момент текущей даты).
2.
Создать производные классы:
FreeSoftware
(название, производитель),
SharewareSoftware (название, производитель,
дата установки, срок бесплатного использования), ProprietarySoftware (название, производитель, цена, дата установки, срок использования).
3.
Создать базу (массив) из n видов программного обеспечения, вывести полную информацию из базы на экран, а также организовать поиск программного обеспечения, которое допустимо использовать на текущую дату.
37
Задание 11*Реализовать базу вакансий организаций, которая позволяет: добавлять и удалять информацию об организациях, добавлять и удалять информацию о вакансиях в организации; просматривать полную информацию о вакансиях или информацию о вакансиях в конкретной организации; осуществлять поиск вакансий по заданной специальности.
Задание 12* Реализовать каталог музыкальных компакт-дисков, который позволяет: добавлять и удалять диски; добавлять и удалять песни на диске; просматривать содержимое целого каталога и каждого диска в отдельности; осуществлять поиск всех песен заданного исполнителя по всему каталогу.
5.ОБЪЕКТНО-ОРИЕНТИРОВАНАЯ РЕАЛИЗАЦИЯ СПИСКОВ В данном разделе мы рассмотрим структуры данных и алгоритмы, которые являются фундаментом современного программирования.
Термины
тип данных, структура данных и
абстрактный тип данных звучат очень похоже, но имеют различный смысл.
В языках программирования
тип данных определяет:
•
внутреннее представление данных в памяти компьютера;
•
объем оперативной памяти, выделяемый для
размещения значения данного типа;
•
множество значений, которые могут принимать величины этого типа;
•
операции и стандартные функции, которые можно применять к величинам этого типа.
Например, в C++ целый тип long:
•
имеет знаковый формат представления данных в памяти ЭВМ;
•
в оперативной памяти занимает 4 байта;
•
множество его значений лежит в диапазоне от-2147483648 до 2147483647;
•
к величинам этого типа могут применяться унарные операции (++, --, -, !), бинарные арифметические операции (/,
%, *, +, -), операции отношения (<, <=, >, >=, = =, !=), логические операции (&&, ||), операции присваивания (=, /=,
%=, *=, +=, -=) и стандартные арифметические функции заголовочного файла math.h.
Абстрактный тип данных (АТД) — это математическая модель плюс различные операторы, определенные в рамках этой модели. Любой алгоритм может разрабатываться в терминах АТД. Но для реализации алгоритма на конкретном языке программирования необходимо найти способ представления АТД в терминах типов данных и операторов, поддерживаемых данным языком программирования. Для представления АТД используются
структуры данных, которые представляют собой набор переменных, возможно, различных типов данных, объединенных определенным образом.
Более подробно мы рассмотрим АТД список и его реализацию с помощью структуры, называемой связным списком.
38
5.1.Основные понятия В математике
список - это последовательность элементов а
1
а
2
,...,а n
(n >=0) одного типа. Количество элементов n называется длиной списка. Если n > 0, то a
1
называется первым элементом списка, а а n
- последним элементом списка. В случае n = 0 имеем пустой список, который не содержит элементов. Важное свойство списка заключается в том, что его элементы линейно упорядочены в соответствии с их позицией в списке. Так элемент а i
предшествует a i+1
для i = l, 2, ... n-1 и а i
следует за а i-1
для i = 2,...n.
Однозначно определенного множества операторов для этой модели не существует. В каждом конкретном случае операции со списком будут зависеть от решаемой задачи. Тем не менее, можно выделить некоторые базовые операции: добавление элемента в список, удаление элемента из списка, проход по списку
(например, для вывода элементов, для подсчета количества элементов с определенным свойством и т.д.).
Список может быть реализован в виде массива или с помощью указателей в виде связного списка.
Один из способов
создания связного списка - сделать так, чтобы каждый элемент списка содержал указатель на следующий элемент. Такую структуру называют однонаправленным или односвязным списком. Если каждый элемент списка содержит два указателя: один на следующий элемент в списке, второй - на предыдущий элемент, то такой список называется двунаправленным или двусвязным.
Далее подробно рассмотрим частные случаи списка (стек и очередь) и их односвязную реализацию, а также список общего вида в односвязной и двусвязной реализации.
5.2.Стек Стек - это частный случай списка, все операции с которым (добавление, просмотр и выборка) выполняются с одного конца, называемого вершиной стека (головой — head). Другие операции со стеком не определены. При выборке элемент исключается из стека. Говорят, что стек реализует принцип обслуживания LIFO (last in - fist out, последним пришел - первым вышел). Стек проще всего представить себе в виде пирамиды, на которую надевают кольца.
Достать первое кольцо можно только после того, как будут сняты все верхние кольца.
Стеки широко применяются в системном программном обеспечении, компиляторах, в различных рекурсивных алгоритмах, поэтому очень важно разобраться в принципах работы со стеками.
Рассмотрим организацию стека с помощью однонаправленного списка, изображенного на рис. 5.1.
39
Рис. 5.1. Стек
Базовый элемент стека содержит:
•
информационное поле inf, которое может быть любого типа, кроме файлового, и будет использоваться для хранения значений, например, чисел, символов, строк;
•
поле-указатель next, в котором хранится адрес следующего элемента в стеке, и которое будет использоваться для организации связи элементов стека.
Замечание В общем случае базовый элемент стека может содержать несколько информационных полей.
Предложенный базовый элемент стека может быть описан следующим образом: struct
Element
{ int inf;
//информационное поле целого типа
Element
*next;
//указатель на следующий элемент стека
Element(
int х,
Element
*p): inf(x), next(p){}
//конструктор элемента стека
};
Замечание Работа с типом данных "структура" на языке C++ подробно рассмотрена в пособии [9].
Как уже говорилось, доступ к элементам стека возможен только из одной точки - из вершины (головы) стека. Основные операции со стеком - это взять элемент из вершины и положить элемент в вершину. Можно еще добавить операцию просмотра верхнего элемента без его удаления из стека и проверку стека на пустоту. С учетом вышеизложенного представим теперь реализацию стека с помощью класса Stack:
class
Stack
{ struct
Element
{ int inf;
Element
*next;
Element(
int x,
Element
*p): inf(x), next(p) {}
};
Element
*head;
//указатель на вершину стека
public
:
Stack(): head(0) {}
//конструктор стека
bool
Empty()
//проверка стека на пустоту
{
return head == 0;
}
40
int
Pop()
//взять элемент из стека
{
if
(Empty())
//если стек пуст, то ничего не делать
{
return
0;
}
Element
*r = head;
//иначе запоминаем указатель на вершину стека
int i = r->inf;
//запоминаем информацию из верхнего элемента
head = r->next;
//передвигаем указатель стека на следующий
//от вершины элемент
delete r;
//освобождаем память, на которую указывает r
return i;
//возвращаем значение
} void
Push(
int data)
//добавить элемент в стек
{ head = new
Element
(data, head);
} int
Тор()
//просмотреть элемент на вершине стека
{
if
(Empty())
//если стек пуст, то возвращаем 0
{
return
0;
} else
//иначе возвращаем информацию из вершины стека
{
return head->inf;
}
}
};
Рассмотрим базовые операции со стеком на примерах.
1.
Добавление элемента в стек
void
Push(
int data)
{ head = new
Element
(data, head);
}
Теперь последовательно выполним следующие команды:
Stack t;
//1
t.Push(3);
//2
t.Push(8);
//3
Команда 1 создает экземпляр класса Stack с именем t, при этом вершина стека пуста (поле head равно NULL).
41
Команда 2 приводит к выполнению оператора head = new Element(3, head).
Данный оператор состоит из двух частей:
•
выделение памяти под новый элемент списка
(new), при этом в поле data нового элемента записывается значение 3, а в поле next записывается адрес области памяти, с которой связан указатель head;
•
переадресация указателя head на новый элемент.
Таким образом, после выполнения команды 2 стек содержит один элемент и выглядит следующим образом:
Рис. 5.2. Стек с одним элементом
Строка 3 приведет к выполнению оператора head = new Element(8,head), который также последовательно выполнит два действия:
Таким образом, после выполнения команды 3 стек содержит два элемента и выглядит следующим образом:
Рис. 5.3. Стек с двумя элементами
2. Извлечение элемента из стека
int
Рор()
{ if
(Empty())
//если стек пуст, то ничего не делать
{ return
0;
}
Element
*r = head;
//1
int i = r->inf;
//2
head = r->next;
//3
42
delete r;
//4return i;
//5}
Проиллюстрируем работу функции Pop на рисунках. Первоначально считаем, что структура стека соответствует рис. 5.3. Выполним операцию t.Pop(). Условие пустоты ложное (стек не пуст), поэтому последовательно выполняются следующие операторы:
Оператор 2: в переменную i записывается 8 - значение информационного поля элемента, на который указывает г.
Оператор 3: указатель head переадресуется на элемент, следующий за r в стеке, таким образом, элемент со значением 8 исключается из стека, а верхним элементом становится элемент со значением 3.
Оператор 4:
освобождает область оперативной памяти, связанную с указателем r.
Оператор 5: функция возвращает значение переменной i, т.е. значение 8.
В результате выполнения операции t.Pop() стек состоит из одного элемента и соответствует рисунку 5.2.
Повторное выполнение операции t.Pop() можно проиллюстрировать следующим образом.
Таким образом, стек окажется пустым.
Скачать 1.93 Mb.