Предыдущая страница реферата | 35  36  37  38  39  40  41  42  43  44  45

Класс 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 главе, создают файлы данных в директории SrcCh9/. Все эти файлы имеют расширение “.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

Скачали данный реферат: Mar'ja, Дигна, Акинф, Evlent'ev, Садовский, Кондрат, Пярин.
Последние просмотренные рефераты на тему: реферат поведение, физика и техника, образ сочинение, какой ответ.





Предыдущая страница реферата | 35  36  37  38  39  40  41  42  43  44  45