Книга: Основы объектно-ориентированного программирования

Изменения и постоянство

Изменения и постоянство

Разработка ПО, как уже упоминалось, во многом связана с повторяемостью. Для понимания технической трудности повторного использования, следует понять природу повторяемости.

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

В таком же положении находится и разработчик ПО, создавая новые варианты, развивающие одни и те же основные темы.

Возьмем пример, упоминавшийся в начале этой лекции: табличный поиск. Несомненно, алгоритм табличного поиска в общем виде всегда выглядит одинаково: начать с некоторой позиции в таблице t, затем приступить к последовательному просмотру таблицы, всякий раз проверяя, является ли искомым элемент в текущей позиции и, если это не так, то переходить к следующей позиции. Процесс завершается, если найден нужный элемент, либо проверка всех элементов оказалась безуспешной. Такая общая схема применима к многим возможным случаям представления данных и алгоритмам для табличного поиска, в том числе в массивах (отсортированных или не отсортированных), связных списках (отсортированных или не отсортированных), последовательных файлах, двоичных деревьях, Б-деревьях и различных хеш-таблицах.

Нетрудно превратить это неформальное описание в частично детализированную подпрограмму:

has (t: TABLE, x: ELEMENT): BOOLEAN is
-- Присутствует ли x в t?
local
pos: POSITION
do
from
pos := INITIAL_POSITION (x, t)
until
EXHAUSTED (pos, t) or else FOUND (pos, x, t)
loop
pos := NEXT (pos, x, t)
end
Result := not EXHAUSTED (pos, t)
end

Некоторые пояснения к принятой здесь нотации: from ... until ... loop ... end описывает цикл, с начальным условием в предложении from, ни разу или повторно выполняющий действия предложения loop, и завершающийся при выполнении условия предложения until. Переменная Result содержит значение, возвращаемое функцией has. Если вы незнакомы с оператором or else (Оператор or else объясняется в лекции 13), то считайте, что здесь содержится просто логическое or.

Хотя приведенный выше текст описывает общую схему работы алгоритма, он не является непосредственно выполняемым, поскольку содержит некоторые не вполне определенные фрагменты (написанные заглавными буквами). Они соответствуют аспектам задачи табличного поиска, зависящим от выбранной реализации: тип элементов таблицы (ELEMENT), с какой позиции начинать поиск (INITIAL_POSITION), как переходить от текущей позиции к следующей (NEXT), как проверить наличие искомого элемента на некоторой позиции (FOUND), как определить, что все интересующие нас позиции уже проверены (EXHAUSTED).

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

Оглавление книги