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

Преобразование объекта в строку обеспечивает большую гибкость основной программы. При этом она может сохранять и считывать объекты, используя текстовые файлы, базу данных или область памяти. Она может переслать представленный таким образом объект по сети или сделать его доступным на 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

Стр: 19
 [RP1]Вариант – временная и ёмкостная сложность

Page: 31
 [RP2]Вариант – перегрузкой памяти.

Стр: 43
 [RP3]Вероятно, жаргонизм, может выбросить вообще?

Стр: 43
 [RP4]Вариант: «сборка мусора»

Стр: 44
 [RP5]Исправлена опечатка в книге – см. http://www.vb-helper.com/vbaupd.htm

Ñòð: 83
 [RV6]Может есть более удачный вариант термина?

Ñòð: 138
 [RV7]Вариант: многопоточные деревья.

Ñòð: 138
 [RV8]Варианты: TRIE-структуры, ТРАЙ-структуры

Ñòð: 138
 [RV9]Варианты: деревья квадрантов, Q-деревья.

Ñòð: 140
 [RV10]Вариант: тернарными

Ñòð: 141
 [RV11]Исправлена ошибка в исходном листинге - Left заменено на Right

Стр: 165
 [RP12]Варианты: деревья квадратов, Q-деревья

Стр: 190
 [RV13]Исправлена ошибка – в оригинале буквы элементов не соответствуют рисунку.

Стр: 212
 [RV14]Вариант: задача о ранце

Стр: 214
 [RV15]Исправлена смысловая ошибка в оригинале — вместо узла B в нем написано узел C.

Стр: 300
 [RV16]Варианты ‑ последовательностью проверок, последовательностью проб

Стр: 303
 [RV17]Ошибка в оригинале - на рисунке приведен скриншот другой программы, искомое значение не соответствует тексту.

Стр: 304
 [RV18]Ошибка в оригинале - на рисунке приведен скриншот другой программы.

Стр: 314
 [RV19]Возможно, имеется в виду хеш‑адресация.

Стр: 339
 [RV20]Вариант - «жадными» алгоритмами.

Стр: 352
 [RV21]Вариант: кратчайший маршрут между двумя точками

Стр: 361
 [RV22]Вариант: потоковой сетью (flow network)

Стр: 378
 [RP23]Не уверен в точности терминов.