Лабораторная работа № 1. Тема: Реализация контейнерного класса динамической структуры данных

Тема: Реализация контейнерного класса динамической структуры данных. Инкапсуляция. Перегрузка функций и операторов.

Цель работы: Изучить основы программирования на языке С++. Получить практические навыки составления программ на С++, описания классов, перегрузки операторов и функций.

Задание. Реализовать и протестировать контейнерный класс динамической структуры данных, содержащей строки. Класс должен иметь интерфейс АТД для добавления, удаления и поиска элементов, а также содержать следующие функции-члены:

а) перегруженные конструкторы:

̶ по умолчанию;

̶ копирования;

̶ с параметрами по умолчанию.

б) деструктор;

в) перегруженные операции:

̶ добавление элемента +;

̶ удаление элемента -;

̶ индексирование [];

̶ копирование =;

̶ отношение равенства ==;

̶ отношение порядка >;

̶ вывод значения контейнера в стандартный поток вывода <<;

г) объявление и реализация дружественной функции.

Контрольные вопросы:

̶ абстракция;

̶ АТД;

̶ инкапсуляция;

̶ методы доступа к членам класса;

̶ дружественные функции и классы;

̶ перегрузка функций;

̶ перегрузка унарных и бинарных операторов.

Структура и содержание отчета

Перечень обязательных элементов отчета.

1. Титульный лист.

2. Лист задания: тема, цель, номер варианта, задание.

3. Выполнение задания.

4. Листинг программы / программных модулей на С++ с комментариями.

5. Выводы.

Варианты заданий

Номер варианта выбирается по номеру по журналу.

Варианты заданий приведены в списке ниже.

1. Массив.

2. Стек.

3. Дек.

4. Очередь.

5. Приоритетная очередь.

6. Односвязный список.

7. Двусвязный список.

8. Хэш-таблица.

9. Множество.

10. Мультимножество.

11. Бинарное дерево.

12. Граф.

13. Словарь ассоциаций.

Методические указания к выполнению лабораторной работы

1 Понятие абстракции

Существенным понятием объектно-ориентированного программирования является абстракция. Ее смысл состоит в том, что абстракция позволяет смотреть на объект, не заставляя себя разобраться в той совокупности сложных частей, из которых состоит данный объект. Через абстракцию человек управляет сложностью [1-3].

Например, люди не представляют себе автомобиль как набор десятков тысяч индивидуальных частей (деталей). В их воображении автомобиль - хорошо определенный объект со своим собственным уникальным поведением. Эта абстракция позволяет людям использовать автомобиль, не задумываясь над сложностью деталей, из которых он состоит.

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

2 Понятие объекта

Объект – структурированная переменная, содержащая всю информацию о некотором физическом предмете или реализуемом в программе понятии, т.е. это некоторая сущность, имеющая четко выраженные границы [1-3].

Объект может быть реальным или абстрактным.

Каждый объект характеризуется тремя составляющими:

1. Состояние.

2. Поведение.

3. Индивидуальность.

Объект – набор свойств. Объект описывается некоторым набором свойств (статических) и набором значений, как правило динамических. Набор значений динамический, если он меняется. Например: Студент (имя, возраст, рост, вес).

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

14. Модификатор (операция, изменяющая свойства объекта).

15. Селектор (операция, позволяющая читать значение свойств объекта).

16. Итератор (операция, позволяющая получать последовательный доступ к свойствам объекта).

17. Конструктор (операция, создающая объект).

18. Деструктор (операция, разрушающая объект).

Индивидуальность – набор свойств объекта, который позволяет определить уникальный объект (экземпляр объекта), т.е. это то, что отличает один объект от другого. Существует также такое понятие как тождественность. Два объекта тождественны друг другу, если они имеют одинаковые имена или же одинаковый набор свойств их значений.

Отношения между объектами.

1. Воздействие: Один объект может выполнять операции над другим объектом. Например: В объекте " утюг " существует второй объект - датчик температуры, который может включать и выключать температуру, тем самым выполняет воздействие.

Если объекты находятся в отношении воздействия, они могут относиться к одной из трех категорий:

а) объекты, которые воздействуют сами и не поддаются воздействию со стороны других объектов.

б) объекты, которые только выполняют некоторые операции, они являются исполнителями.

в) объекты, выполняющие воздействие и сами подвергающиеся воздействию.

2. Включение: Объекты могут быть составной частью других объектов.

3 Понятие класса

Когда мы описывали технологию ООП, мы говорили, что, класс (базовое понятие этой технологии) объединяет в себе данные (структурированная переменная) и методы (функции) [1-3].

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

Как правило, имеет место иерархия классов, а технология ООП иначе может быть названа как программирование "от класса к классу".

Как выше сказано, класс - базовое понятие этой технологии объединяет в себе данные и методы.

Класс можно также охарактеризовать так: Класс - описание множества объектов и выполняемых над ними действий.

Класс описывается (декларируется) следующим образом:

тип_класса имя_класса {поля, методы};

Class New_class {……описание членов класса………..};

Тип класса может быть задан одним из 3-х атрибутов: class, struct, union. Имя класса становится идентификатором нового типа данных. Поля определяются с помощью базовых типов, методы записываются как обычные функции.

Например: в данном случае класс имеет имя Book и поля: название, автор, цена:

Отношения между классами:

1. Разновидность (роза является разновидностью цветов).

2. Составная часть (Класс определяет часть другого класса).

3. Отношение ассоциативности (Розы и гвоздики являются украшением стола).

4. Наследование. Одно из базовых понятий ООП.

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

Если класс D наследует структуру и поведение класса В, то класс В называют базовым, а класс D - производным.

В иерархической структуре такое наследование изображается стрелкой, идущей от класса D к классу В ( D->В ). Причем не следует думать, что синонимы слов базовый, производный несут другую смысловую нагрузку, т.е. Базовый класс (base) так же можно назвать суперклассом (superclass), родителем (parent), предшественником.

Класс D называют: производным, подклассом, ребенком, потомком.

Существует такое понятие как метакласс. Метакласс - описывает множество классов;

Интерфейсная часть описания классов может быть трех типов.

Доступ к наследуемым компонентам.

Если доступ к собственным компонентам производных классов определяется обычным образом, то на доступ наследуемым компонентам влияет, во-первых, атрибут доступа, определенный в базовом классе, и во-вторых, модификатор доступа, указанный перед именем базового класса в конструкции определения производного класса. Этими модификаторами являются public и private.

Варианты наследования прав доступа приведены в таблице 1.1.

Таблица 1.1 – Варианты наследования прав доступа

Доступ в базовом классе	Модификатор доступа	Унаследованные права доступа
private	private	Не доступен
protected	private	private
public	private	private
private	public	Не доступен
protected	public	protected
public	public	public

Public - Общедоступная часть. В ней описываются свойства и методы, которые доступны везде, где доступен сам класс.

Protected - Защищенная часть класса. Она доступна только для объектов данного класса или для объектов порожденных классов.

Protected - Личная или обособленная часть . Доступна только для объектов данного класса.

Свойство protected аналогично свойству private, но доступ к такому компоненту возможен как через интерфейс базового класса, так и через интерфейс производного. По умолчанию для базового класса типа class в качестве модификатора доступа используется private, для класса struct - public.

Пример программы.

Класс Node задает тип данных, которым является элемент одностороннего списка; класс List является базовым, класс Stack -производным это обозначается так: (List<- Stack), а описывается так:

StructNode

{

Int elem;

Node *next,

Node (int el, Node *ptr)

{

elem=el;

next=ptr;

}

};

class List

{

protected:

Node *head;

public:

List() {head=0;}

List(int a) {head=new Node(a,0),}

Void Show(void);

~List();

};

class Stack: public List

{

public:

Stack (int el): List(el){};

void Push(int);

intPop();

};

Унаследованная переменная head может быть использована в теле функций Push и Pop, но в программе она доступна только через интерфейс классов - функции Push, Pop, Show.

Отметим следующий момент: если производный класс был унаследован из базового с модификатором public, то указатель на базовый класс можно использовать и как указатель на производный класс без какого-либо преобразования типов:

указатель_на_ базовый = указатель_на_производный;

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

Наследуя каждому родителю, производный класс может получить несколько копий одних и тех же полей, что приводит к неоднозначности обращения к этим полям. Добавление слова virtual в списке базовых классов (перед модификатором доступа) устраняет дублирование.

4 Понятие инкапсуляции

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

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

Инкапсуляция автоматически подразумевает защиту данных. Для этого в структуре class используется спецификатор раздела private, содержащий данные и методы, доступные только для самого класса.

Если данные и методы содержатся в разделе public, они доступны извне класса. Раздел protected содержит данные и методы, доступные из класса и любого его производного класса. Наличие последних позволяет говорить об иерархии классов, где есть классы - родители - шаблоны для создания классов - потомков. Объекты, полученные из описания класса, называют экземплярами этого класса.

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

Базовое понятие ООП - инкапсуляция. Подразумевает объединение вместе данных и методов по обработке этих данных внутри классов.

Отличие методов от подпрограмм состоит в том, что метод описывается внутри класса, может наследоваться, может быть виртуальным, а также синтаксис.

5 Понятие конструктора

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

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

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

Например:

class date

{

date(int, int, int);

};

Когда класс имеет конструктор, все объекты этого класса будут инициализироваться. Если для конструктора нужны параметры, они должны передаваться:

date today = date(23,6,1983);

date xmas(25,12,0); // сокращенная форма (xmas - рождество)

date my_birthday; // недопустимо, опущена инициализация

Часто необходимо обеспечить несколько способов инициализации объекта класса. Это можно сделать, задав несколько конструкторов.

Конструктор без параметров (по умолчанию). Один из способов сократить число родственных функций - использовать параметры по умолчанию.

Основные свойства и правила использования конструкторов:

̶ конструктор имеет то же имя, что и класс, в котором он объявляется;

̶ конструктор не возвращает значения даже типа void;

̶ конструктор не наследуется в производных классах. Если необходимо, то конструктор производного класса может вызвать конструкторы для его базовых классов;

̶ конструктор может иметь аргументы, заданные по умолчанию;

̶ конструктор - это функция, но он не может быть виртуальным, его нельзя объявить виртуальным;

̶ невозможно получить в программе адрес конструктора (указатель на конструктор);

̶ если конструктор не задан в программе, то он будет автоматически сгенерирован компилятором для построения соответствующих объектов;

̶ все конструкторы сгенерированные компилятором, имеют атрибут public;

̶ конструктор по умолчанию для класса Х - это конструктор, который может быть вызван без аргументов;

̶ конструктор вызывается автоматически только при описании объекта;

̶ объект, содержащий конструктор, нельзя включить в виде компонента в объединение (union);

̶ конструктор класса Х не может иметь аргумент типа Х;

̶ конструктор, заданный в виде Х::X(const X &), называется конструктором для копирования (copy constructor) класса Х.

6 Понятие деструктора

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

имя_класса

У деструктора не может быть параметров (даже типа void), и деструктор не имеет возможности возвращать какой-либо результат, даже типа void. Статус доступа деструктора по умолчанию public (т.е. деструктор доступен во всей области действия определения класса). В несложных классах деструктор обычно определяется по умолчанию.

Деструкторы не наследуются, поэтому даже при отсутствии в производном классе деструктора он не передается из базового, а формируется компилятором как умалчиваемый со статусом доступа public. Этот деструктор вызывает деструкторы базовых классов.

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

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

Основные свойства и правила использования деструкторов:

̶ деструктор имеет то же имя, что и класс, в котором он объявляется, с префиксом ~(тильдой);

̶ деструктор не возвращает значения даже типа void;

̶ деструктор не наследуется в производных классах;

̶ производный класс может вызвать деструкторы для его базовых классов;

̶ деструктор не имеет параметров (аргументов);

̶ класс может иметь только один деструктор;

̶ деструктор - это функция, и он может быть виртуальным, его можно объявить виртуальным;

̶ невозможно получить в программе адрес деструктора (указатель на деструктор);

̶ если деструктор не задан в программе, то он будет автоматически сгенерирован компилятором для уничтожения соответствующих объектов;

̶ все деструкторы, сгенерированные компилятором, имеют атрибут public;

̶ деструктор вызывается автоматически при разрушении объекта;

̶ когда вызывается библиотечная функция exit, вызываются деструкторы только для глобальных объектов;

̶ когда вызывается библиотечная функция abort, никакие деструкторы не вызываются.

7 Дружественные функции и классы

При определении класса следует стараться часть данных скрывать от пользователей, описывая их в разделе private, что позволяет обезопасить данные от вмешательства со стороны других функций. Для обеспечения скрытия информации мы должны использовать private. Но есть правило! Можно только увеличить скрытие данных, но ведь возможна ситуация, когда необходимо иметь доступ к скрытым членам класса. Для этого необходимый класс нужно объявить как дружественный классу из которого мы хотим получить доступ.

8 Перегрузка операторов и функций

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

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

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

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

Перегрузка операций производится с помощью специальной функции operator согласно следующей форме:

тип operator знак_операции (типы аргументов) {...}.

Перегруженная операция может быть определена как компонент класса; в этом случае она имеет один параметр или вообще не имеет параметров. У дружественной перегруженной операции может быть один или два параметра. Поэтому бинарные операции следует перегружать как дружественные.

Перегружаться могут практически все операции (исключение - оператор принадлежности ::, операторы ..* ?: sizeofn символ #).