Преподаватель Герасимов Александр Сергеевич
Элементы объектно-ориентированного программирования на Паскале
Задание 1. Реализовать полиморфную функцию бинарного поиска, привести пример её использования для поиска в массиве экземпляра объекта "студент", инкапсулирующего номер группы и фамилию; сдать на листах не позднее 09.10.2007.
Элементы программирования на C++
Рекомендуется книга автора языка C++ Б. Страуструпа Язык программирования C++, 3-е изд.
Можно пользоваться одной из систем разработки на C++:
Дистрибутив системы Microsoft Visual Studio 2005.NET, установленной в компьютерных классах факультета, можно получить там же. Из папки \\ilab\MSDNAA\pub\Devel\Visual Studio\2005.NET нужны файлы cd1.iso, cd2.iso, msdn1.iso, msdn2.iso, msdn3.iso (эти файлы - образы компакт-дисков, CD images). Для установки Visual Studio следует подключить (mount) первый их этих файлов (а затем, в ответ на предложения программы установки, и последующие файлы) с помощью программы-эмулятора CD дисковода, например, Daemon Tools.
Вместо вышеуказанной системы можно установить очень похожую бесплатную систему Microsoft Visual C++ 2005 Express Edition с сайта производителя.
Если требуется менее объёмная система, то можно воспользоваться тоже бесплатной системой, например, Borland C++ Compiler version 5.5 (загружать всего 8.5M) или DJGPP.
Как создать и запустить простую программу на C++ в Visual Studio 2005.
Задание 2. Реализовать функцию бинарного поиска в массиве из целых чисел; показать в компьютерном классе не позднее 16.10.2007.
Простой пример наследования и полиморфизма (рекомендуется модифицировать программу, например, убрав слова virtual, убрав вызов delete или изменив область видимости объекта, и посмотреть на результаты).
Полиморфная функция линейного поиска (полиморфизм времени выполнения) - аналог реализации на Паскале.
Шаблон функции линейного поиска (полиморфизм времени компиляции) и пример перегрузки оператора.
Задание 3. Реализовать полиморфную функцию бинарного поиска, полиморфизм которой основан на наследовании, и привести пример её использования; реализовать шаблон функции бинарного поиска и привести пример его использования; сдать на листах не позднее 06.11.2007.
Задание 4. Реализовать шаблон класса, представляющего АВЛ-дерево, и не позднее 20.11.2007 сдать на листах определение шаблона класса, достаточное для работы нерекурсивного метода добавления в АВЛ-дерево (и, конечно, уметь объяснять написанное). Рекомендуемые источники: конспект наших занятий, книга Н. Вирта Алгоритмы и структуры данных.
К занятию 20.11.2007 вспомнить образцы (паттерны) проектирования (адаптер, интерпретатор, посетитель и, по желанию, другие), например, с помощью книги: Э. Гамма и др. Приёмы объектно-ориентированного проектирования. Паттерны проектирования.
Обработка дерева выражения (образец проектирования интерпретатор): классы, представляющие дерево выражения, реализация их методов, шаблон класса, представляющего отображение, пример построения и использования дерева выражения.
Один из способов откомпилировать эту программу, состоящую из нескольких файлов: сохранить все файлы программы в одной директории и запустить cl /EHsc main_interpr.cpp expr_interpr.cpp (остальные детали см. в "Как создать и запустить простую программу на C++ в Visual Studio 2005 с использованием инструментов командной строки").
Задание 5. Не позднее 04.12.2007 сдать на листах программу, строящую по дереву выражения (содержащего бинарные операторы '+', '-', '*', '/') строку, которая представляет соответствующее этому дереву выражение без лишних скобок (скобки опускаются согласно обычному приоритету и ассоциативности операторов). Также, разумеется, следует уметь объяснять написанное и демонстрировать работу программы на компьютере.
Обработка дерева выражения (образец проектирования посетитель): абстрактный класс, задающий посетителя, и классы, представляющие дерево выражения, реализация их методов, пример обработки дерева выражения с помощью конкретного посетителя.
Задание 6. Сдать не позднее 18.12.2007. Это задание аналогично заданию 5, только требуется использовать образец проектирования посетитель и для тестирования расстановки скобок требуется создавать дерево выражения по входной строке, представляющей выражение, причём можно считать, что во входной строке любой идентификатор и любое число состоит из одного символа, а каждый бинарный оператор со своими операндами заключён в скобки. Как обычно, следует уметь объяснять написанное и демонстрировать работу программы на компьютере.