ПК 2102. ПК(2102). П. Г. Колинько пользовательские контейнеры

• Название: П. Г. Колинько пользовательские контейнеры
• Анкор: ПК 2102
• Дата: 28.11.2021
• Размер: 0.78 Mb.
• Имя файла: ПК(2102).docx
• Тип: Учебно-методическое пособие; #284768
• страница: 1 из 12

^{МИНОБРНАУКИ РОССИИ}

___________________________________________________

Санкт-Петербургский государственный электротехнический
университет «ЛЭТИ» им. В. И. Ульянова (Ленина)

—————————————­­­­­­­­­­———————

П. Г. КОЛИНЬКО

ПОЛЬЗОВАТЕЛЬСКИЕ КОНТЕЙНЕРЫ

Учебно-методическое пособие
Санкт-Петербург
Издательство СПбГЭТУ «ЛЭТИ»
2020

УДК 004.424:004.422.63(07)

ББК З 973.2–018я7

К 60

Колинько П. Г.

К60 Пользовательские контейнеры: учебно-метод. пособие. СПб.: СПбГЭТУ «ЛЭТИ», 2020. 67 с.

ISBN 978-5-7629-

Описывается цикл зачетных самостоятельных работ на ПЭВМ. Содержатся материалы для курсовой работы.

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

УДК 004.424:004.422.63(07)

ББК З 973.2–018я7

Рецензент: канд. техн. наук, доцент СПбГУПТД Н. А. Мальгунова.

Утверждено
редакционно-издательским советом университета
в качестве учебно-методического пособия
© П. Г. Колинько, 2012–2020(0221)

ISBN 978-5-7629- © СПбГЭТУ «ЛЭТИ», 2020

ВВЕДЕНИЕ

Цель методических указаний — поддержка второй части двухсеместрового курса «Алгоритмы и структуры данных». Пособие содержит три тематических главы. Первые две посвящены завершению знакомства с воз­мож­но­стя­ми объектного программирования. На простом примере изучаются способы объединения нескольких классов в одном проекте — наследование и включение, а также механизм поддержки обработки особых ситуаций. Третья глава посвящена комбинированным структурам данных. В ней рассматриваются способы размещения множеств в памяти ЭВМ, оптимизированные под различные задачи работы с ними. Изучаются алгоритмы эффективного выполнения двуместных операций над множествами в этих структурах данных, а также применение их для поддержки произвольных последовательностей. Проводится эксперимент по созданию пользовательского контейнера, поддерживающего операции как с множеством, так и с последовательностью с помощью алгоритмов из стандартной библиотеки шаблонов.

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

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

Каждая из четырёх зачётных работ рассчитана на четыре учебных недели. Отчеты по работам должны содержать: название темы; текст индивидуального задания; тесты для проверки программ; результаты их работы; выводы, обязательно содержащие заключение о временной сложности реализованных алгоритмов; список использованных источников; перечень приложений. Обязательное приложение: исходный текст отлаженной программы на машинном носителе.

Все примеры, имеющиеся в пособии, проверены в оболочке Visual C++ 2017. Для обучения могут быть использованы любые программные оболочки типа Linux с поддержкой компилятора g++ с опцией С++17. Visual C++ 2017 и 2019 в варианте Community доступен для скачивания на сайте Microsoft. Актуальную информацию о стандартах С++11/14/17, необходимую для работы, и другую справочную информацию о языке и STL можно получить на сайте ru.cppreference.com. Нововведения подробно изложены в [11, c. 1049–1151] и кратко — в [16, с. 164–168]. Изучить программирование на С++ в новом стандарте можно также по [3] и [6]. С основами библиотеки STL можно ознакомиться по [2], [4] и [10]. Типовые ошибки в программах на С++ обсуждаются в  [7] и [12].

1. РАБОТА С ИЕРАРХИЕЙ ОБЪЕКТОВ:
НАСЛЕДОВАНИЕ И ПОЛИМОРФИЗМ

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

Любое понятие существует не изолированно, а во взаимосвязи с другими понятиями, и мощность данного понятия во многом определяется наличием таких связей. Если класс служит для представления понятий, встает вопрос: как представить взаимосвязь понятий? Понятие производного класса и поддерживающие его языковые средства служат для представления иерархических связей, иными словами, для выражения общности между классами. Например, понятия окружности и треугольника связаны между собой, так как оба они представляют еще понятие фигуры, т. е. содержат более общее понятие. Чтобы представлять в программе окружности и треугольники и при этом не упускать из вида, что они являются фигурами, надо явно определять классы «окружность» и «треугольник» так, чтобы было видно, что у них есть общий класс — фигура. Эта простая идея, по сути, является основой того, что обычно называется объектно-ориентированным программированием.

Подробнее см. [3, с. 200–210], [15, с. 149–180].

Рассмотрим учебную программу, использующую некоторые из этих идей, прототип которой взят из [15]. Программа предназначена для вывода на экран картинок, составленных из набора заготовок — «фигур».

В программе объявлен абстрактный класс «фигура» (shape). Все конкретные фигуры — линия, прямоугольник и т. п. — являются производными от этого класса. Класс «фигура» определяет действия, необходимые для всех фигур. Он также создает из всех объявляемых фигур общий список, который может быть обработан функцией рисования при выдаче фигур на экран. В классе «фигура» объявлен набор функций-членов, которые должны поддерживать все фигуры, чтобы из них можно было создавать картинки. Это функции для рисования, перемещения и изменения размеров фигуры, а также функции, возвращающие координаты всех крайних точек фигуры, по которым их можно будет стыковать. Функции — чисто виртуальные, они должны быть обязательно определены затем отдельно в каждой фигуре. Имеются также два дополнительных класса, уточняющие свойства фигур. Некоторые фигуры можно поворачивать. Для таких фигур имеется базовый класс rotatable, производный от shape. Для других фигур возможна операция отражения относительно горизонтальной или вертикальной оси. Эти фигуры можно строить на базе класса reflectable. Если для фигуры нужно и то и другое, то она должна быть производной от обоих классов.

Класс «фигура» является ядром библиотеки фигур snape.h. Имеется также библиотека поддержки работы с экраном screen.h, в которой определены размеры экрана, введено понятие точки и перечислены утилиты работы с экраном, конкретизированные затем в shape.h. Для простоты и универсальности работа с экраном реализована как формирование и построчный вывод матрицы символов.

Предполагается, что файлы screen.h и shape.h — покупные, а разработчик создает только третий файл — с самой прикладной программой.