Пермский национальный исследовательский
Политехнический университет
Кафедра «Информационные технологии и автоматизированные системы»
Классы, стеки, наследование, полиморфизм
Выполнил(а): студент(ка) группы РИС-16-1б
Болилый В.С.
Проверил: доцент ИТАС
Полякова О.А.
Пермь, 2017
СОДЕРЖАНИЕ
Абстрактные типы данных 3
Инкапсуляция 4
Конструкторы и деструкторы 9
Перегрузка операций и дружественные функции 13
Наследование 17
Полиморфизм 21
Литература 27
Абстрактные типы данных
Абстракция данных — центральное понятие в разработке программ.
Абстракция определяет область и структуру данных вместе с набором операций, которые имеют доступ к данным.
Абстракция, называемая абстрактным типом данных (ADT), создает определяемый пользователем тип данных, чьи операции указывают, как клиент может манипулировать этими данными. ADT является независимым от реализации и позволяет программисту сосредоточиться на идеализированных моделях данных и операциях над ними.
ADT - формат
Для описания ADT используется формат, который включает заголовок с именем ADT, описание типа данных и список операций. Для каждой операции определяются входные значения, предоставляемые клиентом, предусловия, применяемые к данным до того, как операция может быть выполнена, и процесс, который выполняется операцией. После выполнения операции определяются выходные (значения, которые возвращаются клиенту, и постусловия, указывающие на любые изменения данных.
ADT ADT_Name
Данные
Описание структуры данных
Операции
Конструктор
Начальные значения: Данные, используемые для инициализации объекта
Процесс: Инициализация объекта
Операция1:
Вход: Данные от клиента
Предусловия: Необходимое состояние системы перед выполнением операций
Процесс: Действия, выполняемые с данными
Выход: Данные, возвращаемые клиенту
Постусловия: Состояние системы после выполнения операций
Операция2
* • •
Операцияn
* • •
Конец ADT
Инкапсуляция
Инкапсуляция (incapsulation) — это механизм, связывающий воедино код и данные, которыми он манипулирует, а также обеспечивающий их защиту от внешнего вмешательства и неправильного использования. В объектно-ориентированном языке код и данные можно погружать в “черный ящик”, который называется объектом (object). Иначе говоря, объект — это средство инкапсуляции.
Классы
Определения:
§ Класс является абстрактным типом данных, определяемым пользователем, и представляет собой модель реального объекта в виде данных и функций для работы с ними.
§ Данные класса называются полями, а функции класса — методами.
§ Поля и методы называются элементами класса.
Описание класса:
class <имя>{
[ private: ]
<описание скрытых элементов>
public:
<описание доступных элементов>
};
· Private и public - спецификаторы доступа, управляют видимостью элементов класса.
· Private - видимы только внутри класса. Используется по умолчанию.
· Public – вне класса, служит интерфейсом.
Действие любого спецификатора распространяется до следующего спецификатора или до конца класса.
Поля класса:
· Имеют любой тип, кроме того же класса.
· Модификаторы: const (инициализируются с помощью конструктора), static.
· Инициализация полей при описании не допускается.
Стек
Стек (stack) — это список элементов, организованных по принципу LIFO (last in — first out, последним пришёл — первым вышел). Элементы добавляются или удаляются из списка только в вершине (top) стека. Подносы в столовой или стопка коробок являются моделями стека.
Стек является одной из наиболее используемых и наиболее важных структур данных. Стеки применяются очень часто. Например, распознавание синтаксиса в компиляторе, как и оценка выражений, основано на стеке. На нижнем уровне стеки используются для передачи параметров функциям, выполнения вызова функции и возвращения из нее.
ADT – формат стека
ADT Stack
Данные
Список элементов с позицией top, указывающей на вершину стека.
Операции
Конструктор
Начальные значения: Нет
Процесс: Инициализация вершины стека.
StackEmpty
Вход: Нет
Предусловия: Нет
Процесс: Проверка, пустой ли стек.
Выход: Возвращать True, если стек пустой, иначе возвращать False.
Постусловия: Нет
Pop
Вход: Нет
Предусловия: Стек не пустой.
Процесс: Удаление элемента из вершины стека.
Выход: Возвращать элемент из вершины стека.
Постусловия: Элемент удаляется из вершины стека.
Push
Вход: Элемент для стека.
Предусловия: Нет
Процесс: Сохранение элемента в вершине стека.
Выход: Нет
Постусловия: Стек имеет новый элемент в вершине.
Peek
Вход: Нет
Предусловия: Стек не пустой.
Процесс: Нахождение значения элемента в вершине стека.
Выход: Возвращать значение элемента из вершины стека.
Постусловия: Стек неизменный.
ClearStack
Вход: Нет
Предусловия: Нет
Процесс: Удаление всех элементов из стека и переустановка вершины стека.
Выход: Нет
Постусловия: Стек переустановлен в начальные условия.
Конец ADT Stack
Листинг 1: Пример класса стек
// pragma once - препроцессорная директива, разработанная для контроля за тем, чтобы конкретный исходный файл при компиляции подключался строго один раз.
#pragma once
#include <iostream>
namespace stk{
//тип стека (псевдоним типа)
typedef int DType;
//Макс. Размер стека
const int STACK_SIZE=20;
class Stack{
DType stck[STACK_SIZE];
int top;
public:
//Инициализация
void init();
// операции модификации стека
void push(const DType &item);
DType pop();
void clear();
// доступ к стеку
// функция не может модифицировать вызывающий ее объект.
DType peek (void) const;
// методы проверки стека
bool isEmpty() const;
bool isFull() const; // реализация массива
};
}
Пример реализации:
#include "stack.h"
namespace stk{
void Stack::init()
{
top = -1;
}
void Stack::push(const DType &item)
{
if (top == STACK_SIZE-1){
std::cerr << "Стек полон.\n";
return;
}
stck[++top] = item;
}
DType Stack::pop()
{
if (top == -1){
std::cerr << "Стек пуст.\n";
return 0;
}
return stck[top--];
}
void Stack::clear(void)
{
top = -1;
}
DType Stack::peek() const
{
if (top == -1)
{
std::cerr << "Стэк пуст!\n";
exit(1);
}
return stck[top];
}
bool Stack::isEmpty() const
{
return top == -1;
}
bool Stack::isFull() const
{
return top == STACK_SIZE-1;
}
}
Пример использования:
#include <iostream>
#include "stack_v0.h"
using namespace std;
int main(int argc, char *argv[])
{
system("chcp 65001");
stk::Stack stck;
stck.init();
for (int i=0; i< 3; i++)
stck.push(i+1);
cout << stck.peek() << endl;
for (int i=0; i< 3; i++)
cout << stck.pop() << endl;
return 0;
}
Результат:
Способы использования класса:
stk::Stack *pstck = new stk::Stack;
pstck->init();
pstck->push(10);
cout << pstck->pop() << endl;
Ошибки:
stk::Stack stck;
stck.top //Ошибка компиляции
Указатель this
Каждый объект содержит свой экземпляр полей класса. Методы класса находятся в памяти в единственном экземпляре и используются всеми объектами совместно, поэтому необходимо обеспечить работу методов с полями именно того объекта, для которого они были вызваны. Это обеспечивается передачей в функцию скрытого параметра this, в котором хранится константный указатель на вызвавший функцию объект.
Пример:
| Явно | Не явно |
| void Stack::init() { this->top = 0; } | void Stack::init() { top = 0; } |
Классы могут быть глобальными и локальными.