Наследование объектов. Полиморфизм

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

Например, и класс Flea (Блоха), и класс Tyranosaur (Тираннозавр) могут иметь метод bite (Кусать). Полиморфизм означает, что можно вызывать метод Bite, не зная, является ли объект объектом Flea или объектом Tyranosaur, хотя впоследствии, конечно, мы об этом узнаем.

Большинство систем объектно-ориентированного программирования предоставляют полиморфизм через наследование (inheritance). То есть, оба гипотетических класса – и Flea и Tyranosaur могли бы наследовать из класса Animal (Животное). Каждый класс переопределял бы метод Bite класса Animal, чтобы обеспечить свои собственные характеристики.

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

Visual Basic не использует наследования для предоставления полиморфизма. Он обеспечивает его с помощью нескольких интерфейсов ActiveX. В объектной модели компонентов, которая формирует инфраструктуру спецификации ActiveX, несколько интерфейсов позволяют развивать систему программных компонентов без коренного изменения существующего кода.

Интерфейс – это набор связанных методов и свойств. Большая часть спецификации ActiveX имеет отношение к реализации стандартных интерфейсов для получения системного сервиса или для предоставления функциональных возможностей другим программам.

В Visual Basic можно было бы создать интерфейс Animal и реализовать его в собственных класса Flea и Tyranosaur. Затем можно было бы вызывать метод Bite объекта любого типа, не зная конкретно, какому объекту он принадлежит.

Полиморфизм важен для эффективности выполнения. Рассмотрим следующую функцию:

Public sub GetFood(ByVal Critter as Object, ByVal Food as Object)

Dim dblDistance As Double

‘ Код вычисления расстояния до пищи (пропущен).

Critter.Move dblDistance ‘Позднее связывание

Critter.bite Food ‘Позднее связывание

End Sub

Методы Move и Bite для объекта Critter (Живое существо) являются методами позднего связывания. Позднее связывание происходит, если Visual Basic во время компиляции не может определить, какого типа объект будет содержаться в переменной. В данном примере параметр Critter объявлен как Object, поэтому во время выполнения он может содержать объект любого типа.

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

В противоположность вышесказанному, интерфейсы допускают раннее связывание. Если visual Basic во время компиляции «знает», какой интерфейс вызывается. Он может проверить библиотеку типов, чтобы посмотреть поддерживает ли этот интерфейс данный метод. Затем он может скомпилировать код непосредственным переходом на этот метод, используя виртуальную таблицу функций. Это во много раз быстрее, чем позднее связывание.

4. Остов, построение кратчайшего остова в графе. Сведение кратчайшего остова к кратчайшей гамильтоновой цепи.

Описание алгоритма построения SST ( задача построения кратчайшего остовного дерева (Shortest Skeleton Tree - SST). )

В процессе работы алгоритма сформируем следующие множества и параметры:

- множество вершин, входящих в SST;

- множество дуг, входящих в SST;

- множество вершин, доступных для расширения остового дерева;

- длина SST.

Сначала полагаем: , , , ,

Шаг 1. Если , вывести и и идти в конец, иначе идти к шагу 2.

Шаг 2. Отыскиваем

,

и получаем в результате и , на которых достигается минимум. ().

Шаг 3. Формируем множества и париметр (длину, вес) остова:

,

,

,

и идти к шагу 1.