VB, MS Access, VC++, Delphi, Builder C++ принципы(технология), алгоритмы программирования

' Поместить источник в список возможных узлов.

candidates.Add SourceNode

SourceNode.NodeStatus = NOW_IN_LIST

' Продолжать, пока список возможных узлов не опустеет.

Do While candidates.Count > 0

Set node = candidates(1)

candidates.Remove 1

node.NodeStatus = WAS_IN_LIST

id1 = node.Id

' Проверить выходящие из узла связи.

For Each link In node.Links

If link.Node1 Is node Then

Set to_node = link.Node2

Else

Set to_node = link.Node1

End If

id2 = to_node.Id

' Проверить, что residual > 0, и этот узел

' никогда не был в списке.

If Residual(id1, id2) > 0 And _

to_node.NodeStatus = NOT_IN_LIST _

Then

' Добавить узел в список.

candidates.Add to_node

to_node.NodeStatus = NOW_IN_LIST

Set to_node.InLink = link

End If

Next link

' Остановиться, если помечен узел-сток.

If Not (SinkNode.InLink Is Nothing) Then _

Exit Do

Loop

' Остановиться, если расширяющий путь не найден.

If SinkNode.InLink Is Nothing Then Exit Do

' Найти наименьшую остаточную пропускную способность

' вдоль расширяющего пути.

min_residual = INFINITY

Set node = SinkNode

Do

If node Is SourceNode Then Exit Do

id2 = node.Id

Set link = node.InLink

If link.Node1 Is node Then

Set from_node = link.Node2

Else

Set from_node = link.Node1

End If

id1 = from_node.Id

If min_residual > Residual(id1, id2) Then _

min_residual = Residual(id1, id2)

Set node = from_node

Loop

' Обновить остаточные пропускные способности,

' используя расширяющий путь.

Set node = SinkNode

Do

If node Is SourceNode Then Exit Do

id2 = node.Id

Set link = node.InLink

If link.Node1 Is node Then

Set from_node = link.Node2

Else

Set from_node = link.Node1

End If

id1 = from_node.Id

Residual(id1, id2) = Residual(id1, id2) _

- min_residual

Residual(id2, id1) = Residual(id2, id1) _

+ min_residual

Set node = from_node

Loop

Loop ' Повторять, пока больше не останется расширяющих путей.

' Вычислить потоки в остаточной сети.

For Each link In Links

id1 = link.Node1.Id

id2 = link.Node2.Id

If link.Capacity > Residual(id1, id2) Then

link.Flow = link.Capacity - Residual(id1, id2)

Else

' Отрицательные значения соответствуют

' обратному направлению движения.

link.Flow = Residual(id2, id1) - link.Capacity

End If

Next link

' Найти полный поток.

TotalFlow = 0

For Each link In SourceNode.Links

TotalFlow = TotalFlow + Abs(link.Flow)

Next link

End Sub

=======348-350

Программа Flow использует метод поиска расширяющего пути для нахождения

максимального потока в сети. Она похожа на остальные программы в этой

главе. Если вы не добавляете или не удаляете узел или связь, вы можете

выбрать источник при помощи левой кнопки мыши, а затем выбрать сток при

помощи правой кнопки мыши. После выбора источника и стока программа

вычисляет и выводит на экран максимальный поток. На рис. 12.26 показано

окно программы, на котором изображены потоки в небольшой сети.

Приложения максимального потока

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

для многих сетей может быть важно знать максимальный поток, этот метод

часто используется для получения результатов, которые на первый взгляд

имеют отдаленное отношение к пропускной способности сети.

Непересекающиеся пути

Большие сети связи должны обладать избыточностью (redundancy). Для заданной

сети, например такой, как на рис. 12.27, может потребоваться найти число

непересекающихся путей из источника к стоку. При этом, если между двумя

узлами сети есть множество непересекающихся путей, все связи в которых

различны, то соединение между этими узлами останется, даже если несколько

связей в сети будут разорваны.

Можно определить число различных путей, используя метод вычисления

максимального потока. Создадим сеть с узлами и связями, соответствующими

узлам и связям в коммуникационной сети. Присвоим каждой связи единичную

пропускную способность.

@Рис. 12.26. Программа Flow

=====351

@Рис. 12.27. Сеть коммуникаций

Затем вычислим максимальный поток в сети. Максимальный поток будет равен

числу различных путей от источника к стоку. Так как каждая связь может

нести единичный поток, то ни один из путей, использованных при вычислении

максимального потока, не может иметь общей связи.

При более строгом определении избыточности можно потребовать, чтобы

различные пути не имели ни общих связей, ни общих узлов. Немного изменив

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

решения и этой задачи.

Разделим каждый узел за исключением источника и стока на два узла,

соединенных связью единичной пропускной способности. Соединим первый из

полученных узлов со всеми связями, входящими в исходный узел. Все связи,

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

разбиения узлу. На рис. 12.28 показана сеть с рис. 12.27, узлы на которой

разбиты таким образом. Теперь найдем максимальный поток для этой сети.

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

через узел, то он может использовать связь, которая соединяет два

получившихся после разбиения узла. Так как эта связь имеет единичную

пропускную способность, никакие два пути, полученные при вычислении

максимального потока, не могут пройти по этой связи между узлами, поэтому в

исходной сети никакие два пути не могут использовать один и тот же узел.

@Рис. 12.28. Коммуникационная сеть после преобразования

======352

@Рис. 12.29. Сеть распределения работы

Распределение работы

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

определенными навыками. Предположим также, что существует ряд заданий,

которые требуют привлечения сотрудника, обладающего заданным набором

навыков. Задача распределения работы (work assignment) состоит в том, чтобы

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

сотрудник, имеющий соответствующие навыки.

Чтобы свести эту задачу к вычислению максимального потока, создадим сеть с

двумя столбцами узлов. Каждый узел в левом столбце представляет одного

сотрудника. Каждый узел в правом столбце представляет одно задание.

Затем сравним навыки каждого сотрудника с навыками, необходимыми для

выполнения каждого из заданий. Создадим связь между каждым сотрудником и

каждым заданием, которое он способен выполнить, и присвоим всем связям

единичную пропускную способность.

Создадим узел-источник и соединим его с каждым из сотрудников связью

единичной пропускной способности. Затем создадим узел-сток и соединим с ним

каждое задание, снова при помощи связей с единичной пропускной

способностью. На рис. 12.29 показана соответствующая сеть для задачи

распределения работы с четырьмя сотрудниками и четырьмя заданиями.

Теперь найдем максимальный поток из источника в сток. Каждая единица потока

должна пройти через один узел сотрудника и один узел задания. Этот поток

представляет распределение работы для этого сотрудника.

@Рис. 12.30. Программа Work

=======353

Если сотрудники обладают соответствующими навыками для выполнения всех

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

невозможно выполнить все задания, то в процессе вычисления максимального

потока работа будет распределена так, чтобы было выполнено максимально

возможное число заданий.

Программа Work использует этот алгоритм для распределения работы между

сотрудниками. Введите фамилии сотрудников и их навыки в текстовом поле

слева, а задания, которые требуется выполнить и требующиеся для них навыки

в текстовом поле посередине. После того, как вы нажмете на кнопку Go

(Начать), программа распределит работу между сотрудниками, используя для

этого сеть максимального потока. На рис. 12.30 показано окно программы с

полученным распределением работы.

Резюме

Некоторые сетевые алгоритмы можно применить непосредственно к сетеподобным

объектам. Например, можно использовать алгоритм поиска кратчайшего маршрута

для нахождения наилучшего пути в уличной сети. Для определения наименьшей

стоимости построения сети связи или соединения городов железными дорогами

можно использовать минимальное остовное дерево.

Многие другие сетевые алгоритм находят менее очевидные применения.

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

разбиения на районы, составления плана работ методом кратчайшего пути, или

графика коллективной работы. Алгоритмы вычисления максимального потока

можно использовать для распределения работы. Эти менее очевидные применения

сетевых алгоритмов обычно оказываются более интересными и перспективными.

======354

Глава 13. Объектно-ориентированные методы

Использование функций и подпрограмм позволяет программисту разбить код

большой программы на части. Массивы и определенные пользователем типы

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

ними.

Классы, которые впервые появились в 4-й версии Visual Basic, позволяют

программисту по-новому сгруппировать данные и логику работы программы.

Класс позволяет объединить в одном объекте данные и методы работы с ними.

Этот новый подход к управлению сложностью программ позволяет взглянуть на

алгоритмы с другой точки зрения.

В этой главе рассматриваются вопросы объектно-ориентированного

программирования, возникающие при применении классов Visual Basic. В ней

описаны преимущества объектно-ориентированного программирования (ООП) и

показано, какую выгоду можно получить от их применения в программах на

языке Visual Basic. Затем в главе рассматривается набор полезных объектно-

ориентированных примеров, которые вы можете использовать для управления

сложностью ваших приложений.

Преимущества ООП

К традиционным преимуществам объектно-ориентированного программирования

относятся инкапсуляция или скрытие (encapsulation), полиморфизм

(polymorphism) и повторное использование (reuse). Реализация их в классах

Visual Basic несколько отличается от того, как они реализованы в других

объектно-ориентированных языках. В следующих разделах рассматриваются эти

преимущества ООП и то, как можно ими воспользоваться в программах на Visual

Basic.

Инкапсуляция

Объект, определенный при помощи класса, заключает в себе данные, которые он

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

его данными, не зная о том, как хранятся или изменяются значения данных.

Объект предоставляет открытые (public) процедуры, функции, и процедуры

изменения свойств, которые позволяют программе косвенно манипулировать или

просматривать данные. Так как при этом данные являются абстрактными с точки

зрения программы, это также называется абстракцией данных (data

abstraction).

Инкапсуляция позволяет программе использовать объекты как «черные ящики».

Программа может использовать открытые методы объекта для проверки и

изменения значений без необходимости разбираться в том, что происходит

внутри черного ящика.

=========355

Поскольку действия внутри объектов скрыты от основной программы, реализация

объекта может меняться без изменения основной программы. Изменения в

свойствах объекта происходят только в модуле класса.

Например, предположим, что имеется класс FileDownload, который скачивает

файлы из Internet. Программа сообщает классу FileDownload положение

объекта, а объект возвращает строку с содержимым файла. В этом случае

программе не требуется знать, каким образом объект производит загрузку

файла. Он может скачивать файл, используя модемное соединение или

соединение по выделенной линии, или даже извлекать файл из кэша на

локальном диске. Программа знает только, что объект возвращает строку после

того, как ему передается ссылка на файл.

Обеспечение инкапсуляции

Для обеспечения инкапсуляции класс должен предотвращать непосредственный

доступ к своим данным. Если переменная в классе объявлена как открытая, то

другие части программы смогут напрямую изменять и считывать данные из нее.

Если позднее представление данных изменится, то любые части программы,

которые непосредственно взаимодействуют с данными, также должны будут

измениться. При этом теряется преимущество инкапсуляции.

Чтобы обеспечить доступ к данным, класс должен использовать процедуры для

работы со свойствами. Например, следующие процедуры позволяют другим частям

программы просматривать и изменять значение DegreesF объекта Temperature.

Private m_DegreesF As Single ' Градусы Фаренгейта.

Public Property Get DegreesF() As Single

DegreesF = m_DegreesF

End Property

Public Property Let DegreesF(new_DegreesF As Single)

m_DegreesF = new_DegreesF

End Property

Различия между этими процедурами и определением m_DegreesF как открытой

переменной пока невелики. Тем не менее, использование этих процедур

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

решите измерять температуру в градусах Кельвина, а не Фаренгейта. При этом

можно изменить класс, не затрагивая остальных частей программы, в которых

используются процедуры свойства DegreesF. Можно также добавить код для

проверки ошибок, чтобы убедиться, что программа не попытается передать

объекту недопустимые значения.

Private m_DegreesK As Single ' Градусы Кельвина.

Public Property Get DegreesF() As Single

DegreesF = (m_DegreesK - 273.15) * 1.8

End Property

Public Property Let DegreesF(ByVal new_DegreesF As Single)

Dim new_value As Single

new_value = (new_DegreesF / 1.8) + 273.15

If new_value < 0 Then

' Сообщить об ошибке - недопустимое значении.

Error.Raise 380, "Temperature", _

"Температура должна быть неотрицательной."

Else

m_DegreesK = new_value

End If

End Property

======357

Программы, описанные в этом материале, безобразно нарушают принцип

инкапсуляции, используя в классах открытые переменные. Это не слишком

хороший стиль программирования, но так сделано по трем причинами.

Во-первых, непосредственное изменение значений данных выполняется быстрее,

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

в производительности из-за использования ссылок на объекты вместо

применения более сложного метода псевдоуказателей. Применения процедур

свойств еще сильнее замедлит их работу.

Во-вторых, многие программы демонстрируют методы работы со структурами

данных. Например, сетевые алгоритмы, описанные в 12 главе, непосредственно

используют данные объекта. Указатели, которые связывают узлы в сети друг с

другом, составляют неотъемлемую часть алгоритмов. Было бы бессмысленно

менять способ хранения этих указателей.

И, наконец, благодаря использованию открытых значений данных, код

становится проще. Это позволяет вам сконцентрироваться на алгоритмах, и

этому не мешают лишние процедуры работы со свойствами.

Полиморфизм

Второе преимущество объектно-ориентированного программирования — это

полиморфизм (polymorphism), что означает «имеющий множество форм». В Visual

Basic это означает, что один объект может иметь различный формы в

зависимости от ситуации. Например, следующий код представляет собой

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

Объект obj может быть формой, элементом управления, или объектом

определенного вами класса.

Private Sub ShowName(obj As Object)

MsgBox TypeName(obj)

End Sub

Полиморфизм позволяет создавать процедуры, которые могут работать буквально

со всеми типами объектов. Но за эту гибкость приходится платить. Если

определить обобщенный (generic) объект, как в этом примере, то Visual Basic

не сможет определить, какие типы действий сможет выполнять объект, до

запуска программы.

========357

Если Visual Basic заранее знает, с объектом какого типа он будет иметь

дело, он может выполнить предварительные действия для того, чтобы более

эффективно использовать объект. Если используется обобщенный (generic)

объект, то программа не может выполнить подготовки, и в результате этого

потеряет в производительности.

Программа Generic демонстрирует разницу в производительности между

объявлением объектов как принадлежащих к определенному типу или как

обобщенных объектов. Тест выполняется одинаково, за исключением того, что в

одном из случаев объект определяется, как имеющий тип Object, а не тип

SpecificClass. При этом установка значения данных объекта с использованием

обобщенного объекта выполняется в 200 раз медленнее.

Private Sub TestSpecific()

Const REPS = 1000000 ' Выполнить миллион повторений.

Dim obj As SpecificClass

Dim i As Long

Dim start_time As Single

Dim stop_time As Single

Set obj = New SpecificClass

start_time = Timer

For i = 1 To REPS

obj.Value = I

Next i

stop_time = Timer

SpecificLabel.Caption = _

Format$(1000 * (stop_time - start_time) / REPS, "0.0000")

End Sub

Зарезервированное слово Implements

В 5-й версии Visual Basic зарезервированное слово Implements (Реализует)

позволяет программе использовать полиморфизм без использования обобщенных

объектов. Например, программа может определить интерфейс Vehicle (Средство

передвижения), Если классы Car (Автомобиль) и Truck (Грузовик) оба

реализуют интерфейс Vehicle, то программа может использовать для выполнения

функций интерфейса Vehicle объекты любого из двух классов.

Создадим вначале класс интерфейса, в котором определим открытые переменные,

которые он будет поддерживать. В нем также должны быть определены прототипы

открытых процедур для всех методов, которые он будет поддерживать.

Например, следующий код демонстрирует, как класс Vehicle может определить

переменную Speed (Скорость) и метод Drive (Вести машину):

Public Speed Long

Public Sub Drive()

End Sub

=======358

Теперь создадим класс, который реализует интерфейс. После оператора Option

Explicit в секции Declares добавляется оператор Implements определяющий имя

класса интерфейса. Этот класс должен также определять все необходимые для

работы локальные переменные.

Класс Car реализует интерфейс Vehicle. Следующий код демонстрирует, как в

нем определяется интерфейс и закрытая (private) переменная m_Speed:

Option Explicit

Implements Vehicle

Private m_Speed As Long

Когда к классу добавляется оператор Implements, Visual Basic считывает

интерфейс, определенный указанным классом, а затем создает соответствующие

заглушки в коде класса. В этом примере Visual Basic добавит новую секцию

Vehicle в исходный код класса Car, и определит процедуры let и get свойства

Vehicle_Speed для представления переменной Speed, определенной в интерфейсе

Vehicle. В процедуре let Visual Basic использует переменную RHS, которая

является сокращением от Right Hand Side (С правой стороны), в которой

задается новое значение переменной.

Также определяется процедура Vehicle_Drive. Чтобы реализовать функции этих

процедур, нужно написать код для них. Следующий код демонстрирует, как

класс Car может определять процедуры Speed и Drive.

Private Property Let Vehicle_Speed(ByVal RHS As Long)

m_Speed = RHS

End Property

Private Property Get Vehicle_Speed() As Long

Vehicle_Speed = m_Speed

End Property

Private Sub Get Vehicle_Drive()

' Выполнить какие-то действия.

:

End Property

После того, как интерфейс определен и реализован в одном или нескольких

классах, программа может полиморфно использовать элементы в этих классах.

Например, допустим, что программа определила классы Car и Track, которые

оба реализуют интерфейс Vehicle. Следующий код демонстрирует, как программа

может проинициализировать значения переменной Speed для объекта Car и

объекта Truck.

Dim obj As Vehicle

Set obj = New Car

obj.Speed = 55

Set obj = New Truck

obj .Speed =45

==========359

Ссылка obj может указывать либо на объект Car, либо на объект Truck. Так

как в обоих этих объектах реализован интерфейс Vehicle, то программа может

оперировать свойством obj.Speed независимо от того, указывает ли ссылка obj

на Car или Truck.

Так как ссылка obj указывает на объект, который реализует интерфейс

Vehicle, то Visual Basic знает, что этот объект имеет процедуры, работающие

со свойством Speed. Это означает, что он может выполнять вызовы процедур

свойства Speed более эффективно, чем это было бы в случае, если бы obj была

ссылкой на обобщенный объект.

Программа Implem является доработанной версией программы описанной выше

программы Generic. Она сравнивает скорость установки значений с

использованием обобщенных объектов, определенных объектов и объектов,

которые реализуют интерфейс. В одном из тестов на компьютере с процессором

Pentium с тактовой частотой 166 МГц, программе потребовалось 0,0007 секунды

для установки значений при использовании определенного типа объекта. Для

установки значений при использовании объекта, реализующего интерфейс,

потребовалось 0,0028 секунды (в 4 раза больше). Для установки значений при

использовании обобщенного объекта потребовалось 0,0508 секунды (в 72 раза

больше). Использование интерфейса является не таким быстрым, как

использование ссылки на определенный объект, но намного быстрее, чем

использование обобщенных объектов.

Наследование и повторное использование

Процедуры и функции поддерживают повторное использование (reuse). Вместо

того, чтобы каждый раз писать код заново, можно поместить его в

подпрограмму, тогда вместо блока кода можно просто подставить вызов

подпрограммы.

Аналогично, определение процедуры в классе делает ее доступной во всей

программе. Программа может использовать эту процедуру, используя объект,

который является экземпляром класса.

В среде программистов, использующих объектно-ориентированный подход, под

повторным использованием обычно подразумевается нечто большее, а именно

наследование (inheritance). В объектно-ориентированных языках, таких как

C++ или Delphi, один класс может порождать (derive) другой. При этом второй

класс наследует (inherits) всю функциональность первого класса. После этого

можно добавлять, изменять или убирать какие-либо функции из класса-

наследника. Это также является формой повторного использования кода,

поскольку при этом программисту не нужно заново реализовать функции

родительского класса, для того, чтобы использовать их в классе-наследнике.

Хотя Visual Basic и не поддерживает наследование непосредственно, можно

добиться примерно тех же результатов, используя ограничение (containment)

или делегирование (delegation). При делегировании объект из одного класса

содержит экземпляр класса из другого объекта, и затем передает часть своих

обязанностей заключенному в нем объекту.

Например, предположим, что имеется класс Employee, который представляет

данные о сотрудниках, такие как фамилия, идентификационный номер в системе

социального страхования и зарплата. Предположим, что нам теперь нужен класс

Manager, который делает то же самое, что и класс Employee, но имеет еще

одно свойство secretary (секретарь).

Для использования делегирования, класс Manager должен включать в себя

закрытый объект типа Employee с именем m_Employee. Вместо прямого

вычисления значений, процедуры работы со свойствами фамилии, номера

социального страхования и зарплаты передают соответствующие вызовы объекту

m_Employee. Следующий код демонстрирует, как класс Manager может

оперировать процедурами свойства name (фамилия):

==========360

Private m_Employee As New Employee

Property Get Name() As String

Name = m_Employee.Name

End Property

Property Let Name (New_Name As String)

m_Employee.Name = New_Name

End Property

Класс Manager также может изменять результат, возвращаемый делегированной

функцией, или выдавать результат сама. Например, в следующем коде показано,

как класс Employee возвращает строку текста с данными о сотруднике.

Public Function TextValues() As String

Dim txt As String

txt = m_Name & vbCrLf

txt = txt & " " & m_SSN & vbCrLf

txt = txt & " " & Format$(m_Salary, "Currency") & vbCrLf

TextValues = txt

End Function

Класс Manager использует функцию TextValues объекта Employee, но добавляет

перед возвратом информацию о секретаре в строку результата.

Public Function TextValues() As String

Dim txt As String

txt = m_Employee.TextValues

txt = txt & " " & m_Secretary & vbCrLf

TextValues = txt

End Function

Программа Inherit демонстрирует классы Employee и Manager. Интерфейс

программы не представляет интереса, но ее код включает простые определения

классов Employee и Manager.

Парадигмы ООП

В первой главе мы дали определение алгоритма как «последовательности

инструкций для выполнения какого-либо задания». Несомненно, класс может

использовать алгоритмы в своих процедурах и функциях. Например, можно

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

описанных в предыдущих главах, используют классы для инкапсуляции сложных

алгоритмов.

=========361

Классы также позволяют использовать новый стиль программирования, при

котором несколько объектов могут работать совместно для выполнения задачи.

В этом случае может быть бессмысленным задание последовательности

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

модели поведения объектов, чем сведение задачи к последовательности шагов.

Для того чтобы отличать такое поведение от традиционных алгоритмов, мы

назовем их «парадигмами».

Следующие раздела описывают некоторые полезные объектно-ориентированные

парадигмы. Многие из них ведут начало из других объектно-ориентированных

языков, таких как C++ или Smalltalk, хотя они могут также использоваться в

Visual Basic.

Управляющие объекты

Управляющие объекты (command) также называются объектами действия (action

objects), функций (function objects) или функторами (functors). Управляющий

объект представляет какое-либо действие. Программа может использовать метод

Execute (Выполнить) для выполнения объектом этого действия. Программе не

нужно знать ничего об этом действии, она знает только, что объект имеет

метод Execute.

Управляющие объекты могут иметь множество интересных применений. Программа

может использовать управляющий объект для реализации:

. Настраиваемых элементов интерфейса;

. Макрокоманд;

. Ведения и восстановления записей;

. Функций «отмена» и «повтор».

Чтобы создать настраиваемый интерфейс, форма может содержать управляющий

массив кнопок. Во время выполнения программы форма может загрузить надписи

на кнопках и создать соответствующий набор управляющих объектов. Когда

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

лишь вызвать метод Execute соответствующего управляющего объекта. Детали

происходящего находятся внутри класса управляющего объекта, а не в

обработчике событий.

Программа Command1 использует управляющие объекты для создания

настраиваемого интерфейса для нескольких не связанных между собой функций.

При нажатии на кнопку программа вызывает метод Execute соответствующего

управляющего объекта.

Программа может использовать управляющие объекты для создания определенных

пользователем макрокоманд. Пользователь задает последовательность действий,

которые программа запоминает в коллекции в виде управляющих объектов. Когда

затем пользователь вызывает макрокоманду, программа вызывает методы Execute

объектов, которые находятся в коллекции.

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

Управляющий объект может при каждом своем вызове записывать информацию о

себе в лог-файл. Если программа аварийно завершит работы, она может затем

использовать записанную информацию для восстановления управляющих объектов

и выполнения их для повторения последовательности команд, которая

выполнялась до сбоя программы.

И, наконец, программа может использовать набор управляющих объектов для

реализации функций отмены (undo) и повтора (redo).

=========362

Программа использует переменную LastCmd для отслеживания последнего

управляющего объекта в коллекции. Если вы выбираете команду Undo (Отменить)

в меню Draw (Рисовать), то программа уменьшает значение переменной LastCmd

на единицу. Когда программа потом выводит рисунок, она вызывает только

объекты, стоящие до объекта с номером LastCmd.

Если вы выбираете команду Redo (Повторить) в меню Draw, то программа

увеличивает значение переменной LastCmd на единицу. Когда программа выводит

рисунок, она выводит на один объект больше, чем раньше, поэтому

отображается восстановленный рисунок.

При добавлении новой фигуры программа удаляет любые команды из коллекции,

которые лежат после позиции LastCmd,. затем добавляет новую команду

рисования в конце и запрещает команду Redo, так как нет команд, которые

можно было бы отменить. На рис. 13.1 показано окно программы Command2 после

добавления новой фигуры.

Контролирующий объект

Контролирующий объект (visitor object) проверяет все элементы в составном

объекте (aggregate object). Процедура, реализованная в составном классе,

обходит все объекты, передавая каждый из них контролирующему объекту в

качестве параметра.

Например, предположим, что составной объект хранит элементы в связном

списке. Следующий код показывает, как его метод Visit обходит список,

передавая каждый объект в качестве параметра методу Visit контролирующего

объекта ListVisitor:

Public Sub Visit(obj As ListVisitor)

Dim cell As ListCell

Set cell = TopCell

Do While Not (cell Is Nothing)

obj.Visit cell

Set cell = cell.NextCell

Loop

End Sub

@Рис. 13.1. Программа Command2

=========363

Следующий код демонстрирует, как класс ListVisitor может выводить на экран

значения элементов в окне Immediate (Срочно).

Public Sub Visit(cell As ListCell)

Debug.Print cell.Value

End Sub

Используя парадигму контролирующего объекта, составной класс определяет

порядок, в котором обходятся элементы. Составной класс может определять

несколько методов для обхода содержащих его элементов. Например, класс

дерева может обеспечивать методы VisitPreorder (Прямой обход),

VisitPostorder (Обратный обход), VisitInorder (Симметричный обход) и

VisitBreadthFirst (Обход в глубину) для обхода элементов в различном

порядке.

Итератор

Итератор обеспечивает другой метод обхода элементов в составном объекте.

Объект-итератор обращается к составному объекту для обхода его элементов, и

в этом случае итератор определяет порядок, в котором проверяются элементы.

С составным классом могут быть сопоставлены несколько классов итераторов

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

Чтобы выполнить обход элементов, итератор должен представлять порядок, в

котором элементы записаны, чтобы определить порядок их обхода. Если

составной класс представляет собой связный список, то объект-итератор

должен знать, что элементы находятся в связном списке, и должен уметь

перемещаться по списку. Так как итератору известны детали внутреннего

устройства списка, это нарушает скрытие данных составного объекта.

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

составного класса, реализовал обход самостоятельно, можно сопоставить

составному классу класс итератора. Класс итератора должен содержать простые

процедуры MoveFirst (Переместиться в начало), MoveNext (Переместиться на

следующий элемент), EndOfList (Переместиться в конец списка) и CurrentItem

(Текущий элемент) для обеспечения косвенного доступа к списку. Новые классы

могут включать в себя экземпляр класса итератора и использовать его методы

для обхода элементов составного класса. На рис. 13.2 схематически показано,

как новый объект использует объект-итератор для связи со списком.

Программа IterTree, описанная ниже, использует итераторы для обхода полного

двоичного дерева. Класс Traverser (Обходчик) содержит ссылку на объект-

итератор. Они использует обеспечиваемые итератором процедуры MoveFirst,

MoveNext, CurrentCaption и EndOfTree для получения списка узлов в дереве.

@Рис. 13.2. Использование итератора для косвенной связи со списком

=========364

Итераторы нарушают скрытие соответствующих им составных объектов, в отличие

от новых классов, которые содержат итераторы. Для того, чтобы избавиться от

потенциальной путаницы, можно рассматривать итератор как надстройку над

составным объектом.

Контролирующие объекты и итераторы обеспечивают выполнение похожих функций,

используя различные подходы. Так как парадигма контролирующего объекта

оставляет детали составного объекта скрытыми внутри него, она обеспечивает

лучшую инкапсуляцию. Итераторы могут быть полезны, если порядок обхода

может часто изменяться или он должен переопределяться во время выполнения

программы. Например, составной объект может использовать методы

порождающего класса (который описан позднее) для создания объекта-итератора

в процессе выполнения программы. Содержащий итератор класс не должен знать,

как создается итератор, он всего лишь использует методы итератора для

доступа к элементам составного объекта.

Дружественный класс

Многие классы тесно работают с другими. Например, класс итератора тесно

взаимодействует с составным классом. Для выполнения работы, итератор должен

нарушать скрытие составного класса. При этом, хотя эти связанные классы

иногда должны нарушать скрытие данных друг друга, другие классы должны не

иметь такой возможности.

Дружественный класс (friend class) — это класс, имеющий специальное

разрешение нарушать скрытие данных для другого класса. Например, класс

итератора является дружественным классом для соответствующего составного

класса. Ему, в отличие от других классов, разрешено нарушать скрытие данных

для составного класса.

В 5-й версии Visual Basic появилось зарезервированное слово Friend для

разрешения ограниченного доступа к переменным и процедурам, определенным

внутри модуля. Элементы, определенные при помощи зарезервированного слова

Friend, доступны внутри проекта, но не в других проектах. Например,

предположим, что вы создали классы LinkedList (Связный список) и

ListIterator (Итератор списка) в проекте ActiveX сервера. Программа может

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

Порождающий метод класса LinkedList может создавать объекты типа

ListIterator для использования в программе.

Класс LinkedList может обеспечивать в программе средства для работы со

связными списками. Этот класс объявляет свои свойства и методы открытыми,

чтобы их можно было использовать в основной программе. Класс ListIterator

позволяет программе выполнять итерации над объектами, которыми управляет

класс LinkeList. Процедуры, используемые классом ListIterator для

оперирования объектами LinkedList, объявляются как дружественные в модуле

LinkedList. Если классы LinkedList и ListIterator создаются в одном и том

же проекте, то класс ListIterator может использовать эти дружественные

процедуры. Поскольку основная программа находится в другом проекте, она

этого сделать не может.

Этот очень эффективный, но довольно громоздкий метод. Она требует создания

двух проектов, и установки одного сервера ActiveX. Он также не работает в

более ранних версиях Visual Basic.

Наиболее простой альтернативой было бы соглашение о том, что только

дружественные классы могут нарушать скрытие данных друг друга. Если все

разработчики будут придерживаться этого правила, то проектом все еще можно

будет управлять. Тем не менее, искушение обратиться напрямую к данным

класса LinkedList может быть сильным, и всегда существует вероятность, что

кто-нибудь нарушит скрытие данных из-за лени или по неосторожности.

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

себя другому классу в качестве параметра. Передавая себя в качестве

параметра, дружественный класс тем самым показывает, что он является

таковым. Программа Fstacks использует этот метод для реализации стеков.

=======365

При использовании этого метода все еще можно нарушить скрытие данных

объекта. Программа может создать объект дружественного класса и

использовать его в качестве параметра, чтобы обмануть процедуры другого

объекта. Тем не менее, это достаточно громоздкий процесс, и маловероятно,

что разработчик сделает так случайно.

Интерфейс

В этой парадигме один из объектов выступает в качестве интерфейса

(interface) между двумя другими. Один объект может использовать свойства и

методы первого объекта для взаимодействия со вторым. Интерфейс иногда также

называется адаптером (adapter), упаковщиком (wrapper), или мостом (bridge).

На рис. 13.3 схематически изображена работа интерфейса.

Интерфейс позволяет двум объектам на его концах изменяться независимо.

Например, если свойства объекта слева на рис. 13.3 изменятся, интерфейс

должен быть изменен, а объект справа — нет.

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

разработчиками, которые отвечают за эти объекты. Разработчик, который

реализует левый объект, также занимается реализацией процедур интерфейса,

которые взаимодействуют с левым объектом.

Фасад

Фасад (Facade) аналогичен интерфейсу, но он обеспечивает простой интерфейс

для сложного объекта или группы объектов. Фасад также иногда называется

упаковщиком (wrapper). На рис. 13.4. показана схема работы фасада.

Разница между фасадом и интерфейсом в основном умозрительная. Основная

задача интерфейса — обеспечение косвенного взаимодействия между объектами,

чтобы они могли развиваться независимо. Основная задача фасада — облегчение

использования каких-то сложных вещей за счет скрытия деталей.

Порождающий объект

Порождающий объект (Factory) — это объект, который создает другие объекты.

Порождающий метод — это процедура или функция, которая создает объект.

Порождающие объекты наиболее полезны, если два класса должны тесно работать

вместе. Например, составной класс может содержать порождающий метод,

который создает итераторы для него. Порождающий метод может

инициализировать итератор таким образом, чтобы он был готов к работе с

экземпляром класса, который его создал.

@Рис. 13.3 Интерфейс

========366

@Рис. 13.4. Фасад

Программа IterTree создает полное двоичное дерево, записанное в массиве.

После нажатия на одну из кнопок, задающих направление обхода, программа

создает объект Traverser (Обходчик). Она также использует один из

порождающих методов дерева для создания соответствующего итератора. Объект

Traverser использует итератор для обхода дерева и вывода списка узлов в

правильном порядке. На рис. 13.5 приведено окно программы IterTree,

показывающее обратный обход дерева.

Единственный объект

Единственный объект (singleton object) — это объект, который существует в

приложении в единственном экземпляре. Например, в Visual Basic определен

класс Printer (Принтер). Он также определяет единственный объект с тем же

названием. Этот объект представляет принтер, выбранный в системе по

умолчанию. Так как в каждый момент времени может быть выбран только один

принтер, то имеет смысл определить объект Printer как единственный объект.

Один из способов создания единственного объекта заключается в использовании

процедуры, работающей со свойствами в модуле BAS. Эта процедура возвращает

ссылку на объект, определенный внутри модуля как закрытый. Для других

частей программы эта процедура выглядит как просто еще один объект.

@Рис. 13.5. Программа IterTree, демонстрирующая обратный обход

=======367

Программа WinList использует этот подход для создания единственного объекта

класса WinListerClass. Объект класса WinListerClass представляет окна в

системе. Так как операционная система одна, то нужен только один объект

класса WinListerClass. Модуль WinList.BAS использует следующий код для

создания единственного объекта с названием WindowLister.

Private m_WindowLister As New WindowListerClass

Property Get WindowLister() As WindowListerClass

Set WindowLister = m_WindowLister

End Property

Единственный объект WindowLister доступен во всем проекте. Следующий код

демонстрирует, как основная программа использует свойство WindowList этого

объекта для вывода на экран списка окон.

WindowListText.Text = WindowLister.WindowList

Преобразование в последовательную форму

Многие приложения сохраняют объекты и восстанавливают их позднее. Например,

приложение может сохранять копию своих объектов в текстовом файле. При

следующем запуске программы, она считывает это файл и загружает объекты.

Объект может содержать процедуры, которые считывают и записывают его в

файл. Общий подход может заключаться в том, чтобы создать процедуры,

которые сохраняют и восстанавливают данные объекта, используя строку.

Поскольку запись данных объекта в одной строке преобразует объект в

последовательность символов, этот процесс иногда называется преобразованием

в последовательную форму (serialization).

Преобразование объекта в строку обеспечивает большую гибкость основной

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

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

представленный таким образом объект по сети или сделать его доступным на

Web-странице. Программа или элемент ActiveX на другом конце может

использовать преобразование объекта в строку для воссоздания объекта.

Программа также может дополнительно обработать строку, например,

зашифровать ее после преобразования объекта в строку и расшифровать перед

обратным преобразованием.

Один из подходов к преобразованию объекта в последовательную форму

заключается в том, чтобы объект записал все свои данные в строку заданного

формата. Например, предположим, что класс Rectangle (Прямоугольник) имеет

свойства X1, Y1, X2 и Y2. Следующий код демонстрирует, как класс может

определять процедуры свойства Serialization:

Property Get Serialization() As String

Serialization = _

Format$(X1) & ";" & Format$(Y1) & ";" & _

Format$(X2) & ";" & Format$(Y2) & ";"

End Property

Property Let Serialization(txt As String)

Dim pos1 As Integer

Dim pos2 As Integer

pos1 = InStr(txt, ";")

X1 = CSng(Left$(txt, pos1 - 1))

pos2 = InStr(pos1 + 1, txt, ";")

Y1 = CSng(Mid$(txt, pos1 + 1, pos2 – pos1 - 1))

pos1 = InStr(pos2 + 1, txt, ";")

X2 = CSng(Mid$(txt, pos2 + 1, pos1 - pos2 - 1))

pos2 = InStr(pos1 + 1, txt, ";")

Y2 = CSng(Mid$(txt, pos1 + 1, pos2 – pos1 - 1))

End Property

Этот метод довольно простой, но не очень гибкий. По мере развития

программы, изменения в структуре объектов могут заставить вас

перетранслировать все сохраненные ранее преобразованные в последовательную

форму объекты. Если они находятся в файлах или базах данных, для загрузки

старых данных и записи их в новом формате может потребоваться написание

программ-конверторов.

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

элементов данных объекта их имена. Когда объект считывает данные,

преобразованные в последовательную форму, он использует имена элементов для

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

определение элемента будут добавлены какие-либо элементы, или удалены из

него, то не придется преобразовывать старые данные. Если новый объект

загрузит старые данные, то он просто проигнорирует не поддерживаемые более

значения.

Определяя значения данных по умолчанию, иногда можно уменьшить размер

преобразованных в последовательную форму объектов. Процедура get свойства

Serialization сохраняет только значения, которые отличаются от значений по

умолчанию. Перед тем, как процедура let свойства начнет выполнение

преобразования в последовательную форму, она инициализирует все элементы

объекта значениями по умолчанию. Значения, не равные значениям по

умолчанию, обновляются по мере обработки данных процедурой.

Программа Shapes использует этот подход для сохранения и загрузки с диска

рисунков, содержащих эллипсы, линии, и прямоугольники. Объект ShapePicture

представляет весь рисунок целиком. Он содержит коллекцию управляющих

объектов, которые представляют различные фигуры.

Следующий код демонстрирует процедуры свойства Serialization объекта

ShapePicture. Объект ShapePicture сохраняет имя типа для каждого из типов

объектов, а затем в скобках — представление объекта в последовательной

форме.

Property Get Serialization() As String

Dim txt As String

Dim i As Integer

For i = 1 To LastCmd

txt = txt & _

TypeName(CmdObjects(i)) & "(" & _

CmdObjects(i).Serialization & ")"

Next I

Serialization = txt

End Property

==========369

Процедура let свойства Serialization использует подпрограмму

GetSerialization для чтения имени объекта и списка данных в скобках.

Например, если объект ShapePicture содержит команду рисования

прямоугольника, то его представление в последовательной форме будет

включать строку “RectangleCMD”, за которой будут следовать данные,

представленные в последовательной форме.

Процедура использует подпрограмму CommandFactory для создания объекта

соответствующего типа, а затем заставляет новый объект преобразовать себя

из последовательной формы представления.

Property Let Serialization(txt As String) Dim pos As Integer Dim token_name

As String Dim token_value As String Dim and As Object

' Start a new picture.

NewPicture

' Read values until there are no more.

GetSerialization txt, pos, token_name, token_value Do While token_name <>

""

' Make the object and make it unserialize itself.

Set and = ConiniandFactory(token_name)

If Not (and Is Nothing) Then _

and.Serialization = token_value

GetSerialization txt, pos, token_name, tokerL-value Loop

LastCmd = CmdObjects.Count End Property

Парадигма Модель/Вид/Контроллер.

Парадигма Модель/Вид/Контроллер (МВК) (Model/View/Controller) позволяет

программе управлять сложными соотношениями между объектами, которые

сохраняют данные, объектами, которые отображают их на экране, и объектами,

которые оперируют данными. Например, приложение работы с финансами может

выводить данные о расходах в виде таблицы, секторной диаграммы, или

графика. Если пользователь изменяет значение в таблице, приложение должно

автоматически обновить изображение на экране. Может также понадобиться

записать измененные данные на диск.

Для сложных систем управление взаимодействием между объектами, которые

хранят, отображают и оперируют данными, может быть достаточно запутанным.

Парадигма Модель/Вид/Контроллер разбивает взаимодействия, так что можно

работать с ними по отдельности, при этом используются три типа объектов:

модели, виды, и контроллеры.

Модели

Модель (Model) представляет данные, обеспечивая методы, которые другие

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

работы с финансовыми данными, модель содержит данные о расходах. Она

обеспечивает процедуры для просмотра и изменения значений расходов и ввода

новых значений. Она также может обеспечивать функции для вычисления

суммарных величин, таких как полные издержки, расходы по подразделениям,

средние расходы за месяц, и так далее

Модель включает в себя набор видов, которые отображают данные. При

изменении данных, модель сообщает об этом видам, которые изменяют

изображение на экране соответствующим образом.

Виды

Вид (View) отображает представленные в модели данные. Так как виды обычно

выводят данные для просмотра пользователем, иногда удобнее создавать их,

используя форму, а не класс.

Когда программа создает вид, она должна добавить его к набору видов модели.

Контроллеры

Контроллер (Controller) изменяет данные в модели. Контроллер должен всегда

обращаться к данным модели через ее открытые методы. Эти методы могут затем

сообщать об изменении видам. Если контроллер изменял бы данные модели

непосредственно, то модель не смогла бы сообщить об этом видам.

Виды/Контроллеры

Многие объекты одновременно отображают и изменяют данные. Например,

текстовое поле позволяет пользователю вводить и просматривать данные.

Форма, содержащая текстовое поле, является одновременно и видом, и

контроллером. Переключатели, поля выбора опций, полосы прокрутки, и многие

другие элементы пользовательского интерфейса позволяют одновременно

просматривать и оперировать данными.

Видами/контроллерами проще всего управлять, если попытаться максимально

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

не должен сам обновлять изображение на экране. Он может сделать это

позднее, когда модель сообщит ему как виду о произошедшем изменении.

Эти методы достаточно громоздки для реализации стандартных объектов

пользовательского интерфейса, таких как текстовые поля. Когда пользователь

вводит значение в текстовом поле, оно немедленно обновляется, и выполнятся

его обработчик события Change. Этот обработчик событий может модель об

изменении. Модель затем сообщает виду/контроллеру (выступающему теперь как

вид) о произошедшем изменении. Если при этом объект обновит текстовое поле,

то произойдет еще одно событие Change, о котором снова будет сообщено

модели и программа войдет в бесконечный цикл.

Чтобы предотвратить эту проблему, методы, изменяющие данные в модели,

должны иметь необязательный параметр, указывающий на контроллер, который

вызвал эти изменения. Если виду/контроллеру требуется сообщить об

изменении, которое он вызывает, он должен передать значение Nothing

процедуре, вносящей изменения. Если этого не требуется, то в качестве

параметра объект должен передавать себя.

=========371

@Рис. 13.6. Программа ExpMVC

Программа ExpMVC, показанная на рис. 13.6, использует парадигму

Модель/Вид/Контроллер для вывода данных о расходах. На рисунке показаны три

вида различных типов. Вид/контроллер TableView отображает данные в таблице,

при этом можно изменять названия статей расходов и их значения в

соответствующих полях.

Вид/контроллер GraphView отображает данные при помощи гистограммы, при этом

можно изменять значения расходов, двигая столбики при помощи мыши вправо.

Вид PieView отображает секторную диаграмму. Это просто вид, поэтому его

нельзя использовать для изменения данных.

Резюме

Классы позволяют программистам на Visual Basic рассматривать старые задачи

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

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

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

задача правильно разбита на части, то каждый из классов по отдельности

может быть очень простым, хотя все вместе они могут выполнять очень сложную

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

классы так, чтобы каждый из них оказался максимально простым.

==============372

Требования к аппаратному обеспечению

Для запуска и изменения примеров приложений вам понадобится компьютер,

который удовлетворяет требованиям Visual Basic к аппаратному обеспечению.

Алгоритм выполняются с различной скоростью на компьютерах разных

конфигураций. Компьютер с процессором Pentium Pro и 64 Мбайт памяти будет

быстрее компьютера с 386 процессором и 4 Мбайт памяти. Вы быстро узнаете

ограничения вашего оборудования.

Выполнение программ примеров

Один из наиболее полезных способов выполнения программ примеров — запускать

их при помощи встроенных средств отладки Visual Basic. Используя точки

останова, просмотр значений переменных и другие свойства отладчика, вы

можете наблюдать алгоритмы в действии. Это может быть особенно полезно для

понимания наиболее сложных алгоритмов, таких как алгоритмы работы со

сбалансированными деревьями и сетевые алгоритмы, представленные в 7 и 12

главах соответственно.

Некоторые и программ примеров создают файлы данных или временные файлы. Эти

программы помещают такие файлы в соответствующие директории. Например,

некоторые из программ сортировки, представленные в 9 главе, создают файлы

данных в директории Src\Ch9/. Все эти файлы имеют расширение “.DAT”,

поэтому вы можете найти и удалить их в случае необходимости.

Программы примеров предназначены только для демонстрационных целей, чтобы

помочь вам понять определенные концепции алгоритмов, и в них не почти не

реализована обработка ошибок или проверка данных. Если вы введете

неправильное решение, программа может аварийно завершить работу. Если вы не

знаете, какие данные допустимы, воспользуйтесь для получения инструкций

меню Help (Помощь) программы.

========374

A

addressing

indirect, 49

open, 314

adjacency matrix, 86

aggregate object, 382

ancestor, 139

array

irregular, 89

sparse, 92

triangular, 86

augmenting path, 363

B

B+Tree, 12

balanced profit, 222

base case, 101

best case, 27

binary hunt and search, 294

binary search, 286

branch, 139

branch-and-bound technique, 204

bubblesort, 254

bucketsort, 275

C

cells, 47

child, 139

circular referencing problem, 58

collision resolution policy, 299

command, 380

complexity theory, 17

controller, 391

countingsort, 273

critical path, 359

cycle, 331

D

data abstraction, 372

decision tree, 203

delegation, 378

descendant, 139

E

edge, 331

encapsulation, 371

exhaustive search, 204, 282

expected case, 27

F

facade, 386

factorial, 100

factory, 386

fake pointer, 32, 65

fat node, 12, 140

Fibonacci numbers, 105

firehouse problem, 239

First-In-First-Out, 72

forward star, 12, 90, 143

friend class, 384

functors, 380

G

game tree, 204

garbage collection, 43

garbage value, 43

generic, 374

graph, 138, 331

greatest common divisor, 103

greedy algorithms, 339

H

Hamiltonian path, 237

hashing, 298

heap, 266

heapsort, 265

heuristic, 204

Hilbert curves, 108

hill-climbing, 219

I

implements, 375

incremental improvements, 225

inheritance, 378

insertionsort, 251

interface, 385

interpolation search, 288

interpolative hunt and search, 295

K

knapsack problem, 212

L

label correcting, 342

label setting, 342

Last-In-First-Out list, 69

least-cost, 220

linear probing, 314

link, 331

list

circular, 56

doubly linked, 58

linked, 36

threaded, 61

unordered, 36, 43

M

mergesort, 263

minimal spanning tree, 338

minimax, 206

model, 391

Model/View/Controller, 390

Monte Carlo search, 223

N

network, 331

capacitated, 361

capacity, 361

connected, 332

directed, 331

flow, 361

residual, 362

node, 139, 331

degree, 139

internal, 139

sibling, 139

O

octtree, 172

optimum

global, 230

local, 230

P

page file, 30

parent, 139

partition problem, 236

path, 331

pointers, 32

point-to-point shortest path, 352

polymorphism, 371, 374

primary clustering, 317

priority queue, 268

probe sequence, 300

pruning, 212

pseudo-random probing)., 324

Q

quadratic probing, 322

quadtree, 138, 165

queue, 72

circular, 75

multi-headed, 83

priority, 80

quicksort, 258

R

random search, 223

recursion

direct, 99

indirect, 25, 99

multiple, 24

tail recursion, 121

recursive procedure, 23

redundancy, 368

reference counter, 33

rehashing, 327

relatively prime, 103

residual capacity, 362

reuse, 371, 378

S

satisfiability problem, 235

secondary clustering, 324

selectionsort, 248

sentinel, 52

serialization, 388

shortest path, 342

Sierpinski curves, 112

simulated annealing, 231

singleton object, 387

sink, 361

source, 361

spanning tree, 336

stack, 69

subtree, 139

T

tail recursion removal, 121

thrashing, 31

thread, 61

traveling salesman problem, 238

traversal

breadth-first, 149

depth-first, 149

inorder, 148

postorder, 148

preorder, 148

tree, 138

AVL tree, 174

B+tree, 192

binary, 140

bottom-up B-trees, 192

B-tree, 187

complete, 147

depth, 140

left rotation, 177

left-right rotation, 178

right rotation, 176

right-left rotation, 178

symmetrically threaded, 160

ternary, 140

threaded, 138

top-down B-tree, 192

traversing, 148

tries, 138

turn penalties, 354

U

unsorting, 250

V

view, 391

virtual memory, 30

visitor object, 382

W

work assignment, 369

worst case, 27

А

Абстракция данных, 372

Адресация

косвенная, 49

открытая, 314

Алгоритм

поглощающий, 339

Г

Гамильтонов путь, 237

Граф, 138, 331

Д

Делегирование, 378

Деревья, 138

АВЛ-деревья, 174

Б+деревья, 12, 192, 193

Б-деревья, 187

ветвь, 139

внутренний узел, 139

восьмеричные, 172

вращения, 176

двоичные, 140

дочерний узел, 139

игры, 204

квадродеревья, 165

корень, 139

лист, 139

нисходящие Б-деревья, 192

обратный обход, 148

обход, 148

обход в глубину, 149

обход в ширину, 149

поддерево, 139

полные, 147

порядок, 139

потомок, 139

предок, 139

представление нумерацией связей, 12, 143

прямой обход, 148

решений, 203

родитель, 139

с полными узлами, 12

с симметричными ссылками, 160

симметричный обход, 148

троичные, 140

узел, 139

упорядоченные, 153

Дружественный класс, 384

З

Задача

коммивояжера, 238

о выполнимости, 235

о пожарных депо, 239

о разбиении, 236

поиска Гамильтонова пути, 237

распределения работы, 369

формирования портфеля, 212

Значение

"мусорное", 43

И

Инкапсуляция, 372

К

Ключи

объединение, 244

сжатие, 244

Коллекция, 37

Кратчайший маршрут

двухточечный, 352

дерево кратчайшего маршрута, 341

для всех пар, 352, 353

коррекция меток, 342, 348

со штрафами за повороты, 352, 354

установка меток, 342, 344

Кривые

Гильберта, 108

Серпинского, 112

М

Массив

нерегулярный, 89

представление в виде прямой звезды, 90

разреженный, 92

треугольный, 86

Матрица смежности, 86

Метод

ветвей и границ, 204, 212

восхождения на холм, 219

минимаксный, 206

Монте-Карло, 223

наименьшей стоимости, 220

отжига, 231

полного перебора, 204

последовательных приближений, 225

сбалансированной прибыли, 222

случайного поиска, 223

эвристический, 204

Модель/Вид/Контроллер, 390

Н

Наибольший общий делитель, 103

Наследование, 378

О

Объект

вид, 391

единственный, 387

интерфейс, 385

итератор, 383

контролирующий, 382

контроллер, 391

модель, 391

порождающий, 386

преобразование в последовательную форму, 388

составной, 382

управляющий, 380

фасад, 386

Ограничение, 378

Оптимум

глобальный, 230

локальный, 230

Очередь, 72

многопоточная, 83

приоритетная, 80, 268

циклическая, 75

П

Память

виртуальная, 30

пробуксовка, 31

чистка, 43

Пирамида, 265

Повторное использование, 378

Поиск

двоичный, 286

интерполяционный, 288

методом полного перебора, 282

следящий, 294

Полиморфизм, 374

Потоки, 61

Проблема циклических ссылок, 58

Процедура

очистки памяти, 45

рекурсивная, 23

Псевдоуказатели, 32, 65

Р

Разрешение конфликтов, 299

Рекурсия

восходящая, 175

косвенная, 25, 99

многократная, 24

прямая, 99

условие остановки, 101

хвостовая, 121

С

Сеть, 331

избыточность, 368

источник, 361

кратчайший маршрут, 341

критический путь, 359

нагруженная, 361

наименьшее остовное дерево, 338

ориентированная, 331

остаточная, 362

остаточная пропускная способность, 362

остовное дерево, 336

поток, 361

пропускная способность, 361

простой путь, 332

путь, 331

расширяющий путь, 363

ребро, 331

связная, 332

связь, 331

сток, 361

узел, 331

цена связи, 331

цикл, 331

Сигнальная метка, 52

Системный стек, 26

Случай

наилучший, 27

наихудший, 27

ожидаемый, 27

Сортировка

блочная, 275

быстрая, 258

вставкой, 251

выбором, 248

пирамидальная, 265

подсчетом, 273

пузырьковая, 254

рандомизация, 250

слиянием, 263

Список

двусвязный, 58

многопоточный, 61

неупорядоченный, 36, 43

первый вошел-первый вышел, 72

первый вошел-последний вышел, 69

связный, 36

циклический, 56

Стек, 69

Странный аттрактор, 170

Счетчик ссылок, 33

Т

Теория

сложности алгоритмов, 17

хаоса, 170

Тестовая последовательность

вторичная кластеризация, 324

квадратичная проверка, 321

линейная проверка, 314

первичная кластеризация, 317

псевдослучайная проверка, 324

У

Указатели, 32, 36

Ф

Файл подкачки, 30

Факториал, 100

Х

Хеширование, 298

блоки, 303

открытая адресация, 314

разрешение конфликтов, 299

рехеширование, 327

связывание, 300

тестовая последовательность, 300

хеш-таблица, 298

Ч

Числа

взаимно простые, 103

Фибоначчи, 105

Я

Ячейка, 47

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15