Тестирование и использование приложения
1.Запустите приложение на выполнение, нажав быстрые кнопки Сохранить все и Запуск.
2.Выполните тестирование по рис.8.5. Разница между заданным и фактическим количеством узлов в дереве объясняется тем, что узлы для последующих равных чисел не создаются.
3.Выполните тестирование по рис.8.6. Здесь вначале используется автоматический режим формирования дерева, а затем – ручной.
4.Создать дерево, а затем – копию этого дерева. Деревья вывести в окно.
5.Создать два дерева, а затем одно дерево присвоить другому. Правильность действий подтвердить выводом в окно.
6.Реализовать вертикальный вывод дерева в окно.
7.Реализовать сохранение дерева в файле.
8.Написать обработчики соответствующих событий по п.4…п.7 и дополнить интерфейс.
9.Полученные результаты продемонстрировать преподавателю.
Рис.8.5 – формирование дерева в автоматическом режиме
Рис.8.6 - формирование дерева в автоматическом и ручном режимах
Контрольные вопросы
1.Расскажите о назначении и содержании класса TreeNode.
2.Как выделяется и инициализируется память для узла дерева?
3.Укажите в коде использование функций Left() и Right(). Почему они объявлены константными?
4.Как выполняются конструктор и деструктор класса TreeNode?
5.Расскажите о назначении и содержании класса BinSTree.
6.С какой целью класс BinSTree объявлен другом класса TreeNode?
7.Как выполняются конструктор и деструктор класса BinSTree?
|
|
|
8.Как осуществляется поиск узла по ключу?
9.Как выполняется функция Find?
10.Как добавляется узел в дерево?
11.Как создать дерево в автоматическом режиме?
12.Как создать дерево в ручном режиме?
13.Как выводится дерево в окно?
14.Поясните назначение и выполнение функции FindNode.
15.Почему нужен указатель на родителя удаляемого узла?
16.Как находят заменяющий узел, когда удаляемый узел имеет оба поддерева?
17.Как происходит замена удаляемого узла, если заменяющий узел не является его сыном?
18.При выполнении какого условия заменяют корень?
19.Расскажите о назначении и выполнении функций Delete, DeleteTree, ClearTree, CopyTree, Depth, CountLeaf.
20.Как сохранить дерево в файле?
21.Как вывести дерево из файла?
22.Как выполняется перегруженная операция присваивания?
23.Как создать новое дерево – копию другого дерева?
24.Как присвоить одно дерево другому?
25.Как реализовать вертикальный вывод дерева?
Задания
1.Последовательность чисел представить в виде упорядоченного бинарного дерева. Вывести дерево и все его ветви на экран.
2.Массив из целых чисел представить в виде идеально сбалансированного бинарного дерева. Вывести дерево и слой с заданным ключом на экран.
3.Последовательность чисел представить в виде упорядоченного бинарного дерева. Вывести на экран дерево и все ветви слоя с заданным ключом.
|
|
|
4.Массив из чисел представить в виде идеально сбалансированного бинарного дерева. Вывести на экран дерево и ту половину дерева, где находится заданный ключ - с вершины, а другую половину - с корня.
5.Последовательность букв представить в виде идеально сбалансированного бинарного дерева. Вывести на экран дерево и все слои дерева, начиная с вершины, а затем - с корня.
6.Массив из букв представить в виде упорядоченного бинарного дерева. Вывести на экран дерево и номер того слоя, где находится заданная буква.
7.Массив из чисел представить в виде упорядоченного бинарного дерева. Вывести на экран дерево и все его ветви, исходящие из слоя с заданным ключом.
8.Последовательность чисел представить в виде упорядоченного бинарного дерева. Вывести на экран дерево и слой с минимальным ключом.
9.Последовательность чисел представить в виде упорядоченного бинарного дерева. Вывести на экран дерево и ветви, сумма ключей в которых превышает заданное число.
10.Последовательность букв представить в виде идеально сбалансированного дерева. Вывести на экран дерево и ветви с гласными буквами.
|
|
|
11.Массив строк представить в виде упорядоченного бинарного дерева. Вывести дерево и слои со строками одинаковой длины на экран.
12.Массив строк представить в виде идеально сбалансированного дерева. Вывести дерево, слой и ветвь со строкой максимальной длины на экран.
13.Два бинарных дерева зеркально подобны, если либо оба они пусты, либо оба непусты, и при этом левое поддерево одного из них подобно правому поддереву другого и наоборот. Определить, являются ли два дерева зеркально подобными.
14. Два бинарных дерева подобны, если либо оба они пусты, либо оба непусты, и при этом их левые и правые поддеревья подобны. Определить, являются ли два дерева подобными.
15. Составить программу, которая читает произвольный C-файл и печатает в алфавитном порядке каждую группу имен переменных, совпадающих в первых N символах, но различающихся где-либо дальше. При решении задачи использовать дерево с узлами вида: struct NODE{char* word; int k; NODE* left; NODE* right;};. (Слова внутри символьных строк и комментариев не рассматривать.)
16. Формулу вида <формула>::=<цифра>|(<формула><знак><формула>) <знак>::= + | - | * <цифра>::=0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 можно представить в виде бинарного дерева по следующим правилам: а)формула из одной цифры представляется деревом из одной вершины с этой цифрой; б)формула вида f1# f2 представляется деревом, в котором корень - это знак # соответствующей операции, а левое и правое поддеревья - это представления формул f1,f2 в виде бинарных деревьев. Например, формуле 5*(3+8) соответствует дерево
|
|
|
*
/ \
5 +
/ \
3 8
Требуется: а)построить дерево по формуле указанного выше вида; б)вычислить как целое число значение дерева-формулы; в)по заданному дереву распечатать соответствующую формулу.
17. Составить программу, формирующую “перекрестные списки”, т.е. печатающую список слов, которые встречаются в анализируемом файле, а для каждого слова - список номеров строк, в которых это слово встречается. При решении задачи рекомендуется использовать следующие структуры данных: struct LIST //список номеров строк для данного слова
{ int num; struct LIST* p; }
struct NODE //узел дерева с информацией об очередном слове
{ char* word; struct LIST*lines; struct NODE*left; struct NODE*right;}.
18. Распечатать слова текста, отсортированные в порядке убывания частоты их встречаемости (рядом с каждым словом выводить значение счетчика частоты его вхождений в текст). При решении задачи использовать дерево следующей структуры:
struct NODE
{char* word; int k; struct NODE* left; struct NODE* right;}.
19. В упорядоченном бинарном дереве удалить узел с указанным ключом.
20. В упорядоченном бинарном дереве удалить все листья.
21. Вывести упорядоченное бинарное дерево послойно, начиная с корня, сначала исходное, а затем – после удаления указанного слоя.
22. Составить программу, которая содержит текущую информацию о книгах в библиотеке. Сведения о книгах содержат: номер УДК, фамилию и инициалы автора, название, год издания, количество экземпляров данной книги в библиотеке. Программа должна обеспечивать: а)начальное формирование данных о всех книгах в библиотеке в виде бинарного дерева; б)добавление данных о книгах, вновь поступающих в библиотеку; в)удаление данных о списываемых книгах; г)по запросу выдаются сведения о наличии книг в библиотеке, упорядоченные по годам издания.
23. Составить программу, которая содержит текущую информацию о заявках на авиабилеты. Каждая заявка содержит: пункт назначения, номер рейса, фамилию и инициалы пассажира, желаемую дату вылета. Программа должна обеспечивать: а)хранение всех заявок в виде бинарного дерева; б)добавление и удаление заявок; в) по заданному номеру рейса и дате вылета вывод заявок с их последующим удалением; г)вывод всех заявок.
24. Англо-русский словарь построен как бинарное дерево. Каждая компонента содержит английское слово, соответствующее ему русское слово и счетчик количества обращений к данной компоненте. Первоначально дерево формируется согласно английскому алфавиту. В процессе эксплуатации словаря при каждом обращении к компоненте в счетчик обращений добавляется единица. Составить программу, которая: 1)обеспечивает начальный ввод словаря с конкретными значениями счетчиков обращений; 2)формирует новое представление словаря в виде бинарного дерева по следующему алгоритму: а)в старом словаре находится компонента с наибольшим значением счетчика обращений, б)найденная компонента заносится в новый словарь и удаляется из старого, в)переход к п. ‘а)’ до исчерпания исходного словаря; 3)производит вывод исходного и нового словарей. Программа должна обеспечивать диалог с помощью меню и контроль ошибок при вводе.
25. На междугородной телефонной станции картотека абонентов, содержащая сведения о телефонах и их владельцах, организована как бинарное дерево. Составить программу, которая: 1)обеспечивает начальное формирование картотеки в виде бинарного дерева; 2)производит вывод всей картотеки; 3)вводит номер телефона и время разговора; 4)выводит извещение на оплату телефонного разговора. Программа должна обеспечивать диалог с помощью меню и контроль ошибок при вводе.
26. Автоматизированная информационная система на железнодорожном вокзале содержит сведения об отправлении поездов дальнего следования. Для каждого поезда указывается: номер поезда, станция назначения, время отправления. Данные в информационной системе организованы в виде бинарного дерева. Составить программу, которая: 1)обеспечивает первоначальный ввод данных в информационную систему и формирование бинарного дерева; 2)производит вывод всего дерева; 3)вводит номер поезда и выводит все данные об этом поезде; 4)вводит название станции назначения и выводит данные обо всех поездах, следующих до этой станции. Программа должна обеспечивать диалог с помощью меню и контроль ошибок при вводе.
27. Бинарное упорядоченное дерево стереть слой за слоем, начиная с максимально дальней вершины.
28. В идеально сбалансированном бинарном дереве удалить узел с заданным ключом.
29. По исходному бинарному дереву построить подобное дерево.
30. По исходному бинарному дереву построить зеркально подобное дерево.
ЛАБОРАТОРНАЯ РАБОТА 9
ИЕРАРХИЯ: ТОЧКА, КРУГ, ЦИЛИНДР
Введение
Наследование и полиморфизм являются наиболее важными особенностями объектно-ориентированного программирования и позволяют эффективно преодолевать сложности программного обеспечения. Полиморфизм позволяет создавать программы, обрабатыващие широкий круг как существующих, так и еще даже не описанных родственных классов.
Наследование
Наследование – это способ повторного использования программного обеспечения, при котором новые классы создаются из уже существующих классов путем использования их атрибутов и функций. При создании нового класса можно указать, что он является наследником данных-элементов и функций-элементов ранее определенного базового класса. Новый класс называют производным классом. Он также может быть базовым для будущих производных классов. При простом наследовании класс порождается одним базовым классом.
Базовый класс может наследоваться как public (открытый), protected (защищенный) или private(закрытый). Защищенное и закрытое наследования встречаются редко. В случае public открытые элементы базового класса становятся открытыми элементами производного класса, а защищенные элементы базового класса становятся защищенными элементами производного класса. Закрытые элементы базового класса никогда не бывают доступны для производного класса. Элементы базового класса, которые не должны быть доступны производному классу через наследование, объявляются в базовом классе закрытыми.
Базовый класс может быть прямым или косвенным базовым классом производного класса. Прямой базовый класс явно перечисляется в заголовке при объявлении производного класса, а косвенный – наследуется через два или более уровней иерархии.
Производный класс обычно добавляет свои собственные данные-элементы и функции-элементы, так что производный класс в общем случае больше своего базового класса. Производный класс более специфичен по своему назначению, более узок, чем его базовый класс, и представляет меньшую группу объектов. При простом наследовании предполагается, что производный класс будет выполнять примерно те же функции, что и базовый класс.
Каждый объект производного класса при открытом наследовании является также объектом соответствующего базового класса, но не наоборот.
Одной из проблем наследования является то, что производный класс может наследовать открытые функции-элементы, когда в этом нет необходимости или когда это недопустимо. В таких случаях эти элементы соответствующим образом переопределяют в производном классе. Если имена функций-элементов в классах совпадают, то при переопределении в производном классе функции-элемента базового класса принято вызвать версию базового класса и после этого выполнять некоторые дополнительные операции. При этом ссылка на функцию-элемент базового класса должна использовать операцию разрешения области действия. Следует отметить, что при переопределении нет необходимости получать такую же сигнатуру, как у функции-элемента базового класса.
Наследование формирует древовидные иерархические структуры. Класс может существовать сам по себе, но когда класс входит в иерархию, он становится либо базовым классом, который снабжает атрибутами и функциями другие классы, либо производным классом, который наследует эти атрибуты и функции.
Виртуальные функции и полиморфизм
Виртуальные функции и полиморфное программирование позволяют автоматически выполнять логику, аналогичную логике оператора switch.
Виртуальная функция объявляется с помощью ключевого слова virtual, предшествующего прототипу функции в базовом классе, например, virtual float getX()const;. Функция может быть чистой виртуальной, тогда virtual float getX()const=0;. Несмотря на то, что некоторые функции могут быть неявно виртуальными, поскольку они были объявлены такими на более высоком уровне иерархии, рекомендуется явно объявлять функции виртуальными на каждом уровне иерархии, чтобы обеспечить ясность программы.
Производные классы могут иметь собственные реализации виртуальных функций базового класса, но если они их не имеют, то используются реализации, описанные в базовом классе.
Если виртуальная функция вызывается обращением к объекту по имени и при этом используется операция доступа точка, то эта ссылка обрабатывается во время компиляции (это называется статическим связыванием) и в качестве вызываемой определяется функция класса данного объекта (или наследуемая этим классом).
Использование виртуальных функций делает целесообразным определять в иерархии абстрактный базовый класс, который содержит хотя бы одну чистую вуртуальную функцию. В отличие от конкретных классов, абстрактные классы не могут порождать объекты. Однако указатель на абстрактный базовый класс может быть объявлен. Если класс является производным от класса с чистой виртуальной функцией и если эта чистая виртуальная функция не определена в производном классе, то функция остается чистой виртуальной и в производном классе. Тогда производный класс также является абстрактным классом.
Переопределенная в производном классе виртуальная функция должна иметь тот же самый тип возвращаемого значения и ту же сигнатуру, что и виртуальная функция базового класса.
С помощью виртуальных функций реализуется полиморфизм – это возможность для объектов разных классов, связанных с помощью наследования, реагировать различным образом при обращении к одной и той же функции-элементу.
Если запрос виртуальной функции для объекта иерархии осуществляется с помощью указателя базового класса (или ссылки, но в случае абстрактного базового класса - только с помощью указателя), то будет выбрана правильная переопределенная функция в соответствующем производном классе, связанном с данным объектом. Следовательно, благодаря использованию виртуальных функций и полиморфизму, один и тот же вызов функции-элемента может привести к различным действиям в зависимости от типа объекта, принимающего этот вызов. Очевидно, указатели на абстрактные базовые классы наиболее удобны для полиморфного оперирования объектами производных конкретных классов.
Когда вызов виртуальной функции осуществляется по указателю, вызываемая виртуальная функция будет установлена для вызванного объекта во время выполнения программы, т.е. при помощи динамического (позднего) связывания.
Динамическое связывание требует, чтобы во время выполнения программы вызов виртуальной функции-элемента был бы направлен варианту виртуальной функции соответствующего класса. Для этого служит таблица виртуальных методов, которая реализуется в виде массива, содержащего указатели на функции. У каждого класса, который содержит виртуальные функции, имеется таблица виртуальных методов. Для каждой виртуальной функции в классе таблица имеет элемент, содержащий указатель на вариант виртуальной функции, используемый в объектах данного класса. Виртуальная функция, используемая в некотором классе, может быть определена в этом классе или прямо или косвенно наследоваться из базового класса, стоящего выше в иерархии. В производных классах может быть переопределена или не переопределена виртуальная функция-элемент базового класса. Поэтому производный класс может использовать вариант виртуальной функции-элемента базового класса и это будет отражено а таблице виртуальных методов.
Каждый объект класса, содержащего виртуальные функции, имеет указатель на таблицу виртуальных методов этого класса, недоступный для программиста. Во время выполнения программы вызовы виртуальных функций осуществляются через разыменование соответствующего указателя в таблице виртуальных методов.
В класс с виртуальными функциями рекомендуется включать виртуальный деструктор. Это приведет к тому, что все деструкторы производных классов станут виртуальными, даже если они имеют имена, отличные от имени деструктора базового класса. В этом случае, если объект в иерархии уничтожен явным использованием операции delete, примененной к указателю базового класса на объект производного класса, то будет вызван деструктор соответствующего класса.
Конструкторы не могут быть виртуальными.
В данной лабораторной работе изучается пример иерархии – точка, круг, цилиндр, с прямым открытым наследованием. Для демонстрации возможностей полиморфизма в лабораторной работе рассмотрено два варианта иерархии. Виртуальные функции находятся во втором варианте. В первом варианте для отображения объектов использовано приведение типов указателей базовых классов к указателям производных классов, во втором – полиморфизм, реализованный при помощи виртуальных функций-элементов.
Проектирование приложения.
Дата добавления: 2018-05-13; просмотров: 825; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!