ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 30.10.2023
Просмотров: 416
Скачиваний: 1
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
СОДЕРЖАНИЕ
Решение задач с помощью рекурсии 199
правилом для выбора между рекурсией и итерацией является следу- ющее: выбирайте рекурсию, когда эти аргументы не работают.
Рассмотрим нашу функцию, которая подсчитывает количество листьев в двоичном дереве. Как бы вы решили эту задачу без рекур- сии? Это возможно, но вам бы понадобился явный механизм для под- держания «тропы из хлебных крошек» для обозначения узлов, до- черние элементы которых в левом поддереве уже были посещены, а в правом — нет. К этим узлам пришлось бы вернуться в какой-то момент, чтобы иметь возможность посетить дочерние элементы в правом поддереве. Вы могли бы хранить эти узлы в такой динамиче- ской структуре, как стек. Для сравнения далее приведена реализация функции, которая использует класс stack из стандартной библиоте- ки шаблонов C++: int binaryTree::stackBasedCountLeaves() {
if (_root == NULL) return 0;
int leafCount = 0;
Xstack< YbinaryTreeNode *> nodes;
Znodes.push(_root);
while (
[!nodes.empty()) {
treePtr currentNode =
\nodes.top();
]nodes.pop();
if (currentNode->left == NULL && currentNode->right == NULL) leafCount++;
else {
if (currentNode->right != NULL) wnodes.push(currentNode->right);
if (currentNode->left != NULL) wnodes.push(currentNode->left);
}
}
return leafCount;
}
Этот код следует той же схеме, что и оригинал, однако, если вы никогда раньше не использовали класс stack, здесь будут умест- ны некоторые комментарии. Класс stack работает как системный стек, который мы обсуждали в главе 3; вы можете добавлять и уда- лять элементы только на вершине. Обратите внимание на то, что мы могли бы выполнить операцию подсчета листьев, используя лю- бую структуру данных, которая не имеет фиксированного размера.
Например, мы могли бы использовать вектор, однако использова- ние стека лучше всего отражает исходный код. Когда мы объявля- ем стек
X
, то указываем тип элементов, которые собираемся в нем хранить. В данном случае мы будем хранить указатели на структуру binaryTreeNode
Y
. В этом коде мы будем использовать четыре мето- да класса stack. Метод push
Z
помещает элемент (в данном случае указатель на узел) на вершину стека. Метод empty
[
говорит нам, остались ли в стеке какие-либо элементы. Метод top
\
предостав- ляет нам копию элемента на вершине стека, а метод pop
]
удаляет верхний элемент из стека.
Данный код решает задачу, помещая на стек указатель на пер- вый узел, а затем последовательно удаляя из стека указатель на узел,
200 Глава 6
проверяя, является ли он листом, увеличивая счетчик на 1, если это так, и помещая на стек указатели на дочерние узлы, если они суще- ствуют. Таким образом, стек отслеживает узлы, которые мы обнару- жили, но еще не обработали, так же, как цепочка рекурсивных вы- зовов в рекурсивной версии отслеживает узлы, которые мы должны повторно посетить. Сравнивая эту итеративную версию с рекурсив- ной, мы видим, что ни одно из стандартных возражений против ре- курсии не имеет в данном случае достаточной силы. Во-первых, этот код длиннее и сложнее, чем его рекурсивная версия, поэтому про- тив рекурсивной версии нельзя выдвинуть аргумент, связанный с концептуальной сложностью. Во-вторых, посмотрите, сколько вы- зовов функций совершает stackBasedCountLeaves — на каждое посе- щение внутреннего узла (то есть узла, который не является листом) эта функция совершает до пяти вызовов функций: по одному для ме- тодов empty, top и pop и один или два для метода push. Рекурсивная версия совершает только два рекурсивных вызова для каждого вну- треннего узла. (Обратите внимание на то, что мы можем избежать вызовов функцией объекта стека, включив в функцию логику стека.
Однако это еще больше увеличит сложность функции.) В-третьих, хотя эта итеративная версия не использует дополнительное про- странство системного стека, она явно использует приватный стек.
Справедливости ради следует сказать, что при этом расход простран- ства меньше, чем расход пространства системного стека при рекур- сивных вызовах, однако это по-прежнему расходование системной памяти, пропорциональное максимальной глубине двоичного дере- ва, которое мы обходим.
Поскольку в данной ситуации возражения против рекурсии смягчаются или сводятся к минимуму, рекурсия — хороший вы- бор для решения этой задачи. В общем случае, если задачу легко решить итеративно, то итерация должна быть вашим первым вы- бором. Рекурсию следует использовать, когда решение с помощью итерации представляется сложным. Часто это требует использова- ния описанного здесь механизма создания «тропы из хлебных кро- шек». Обход ветвящихся структур, таких как деревья и графы, по своей сути рекурсивен. Обработка линейных структур, таких как массивы и связные списки, обычно не требует рекурсии, однако су- ществуют исключения. Вы никогда не ошибетесь, если начнете ре- шать задачу с помощью итерации и посмотрите, как далеко вас это заведет. В качестве последних примеров рассмотрим следующие за- дачи со связными списками.
: D "
" "
Напишите функцию, которой передается указатель на головной элемент односвязного списка, где типом данных каждого узла является целое число, и которая отображает эти целые числа по одному на строке в порядке их следования в списке.
Решение задач с помощью рекурсии
1 ... 20 21 22 23 24 25 26 27 ... 34
201
: D "
"
Напишите функцию, которой передается указатель на головной элемент односвязного списка, где типом данных каждого узла является целое число, и которая отображает эти целые числа по одному на строке в порядке, обратном порядку их следования в списке.
Поскольку эти задачи являются зеркальными версиями друг друга, естественно предположить, что их решения также будут зер- кальными. Это действительно так в случае рекурсивных реализа- ций. Далее приведены рекурсивные функции для решения обеих этих задач с использованием приведенных ранее типов listNode и listPtr
: void displayListForwardsRecursion(listPtr head) {
if (head != NULL) {
X cout << head->data << "\n";
Y displayListForwardsRecursion(head->next);
}
}
void displayListBackwardsRecursion(listPtr head) {
if (head != NULL) {
Z displayListBackwardsRecursion(head->next);
[ cout << head->data << "\n";
}
}
Как видите, код в этих функциях одинаков, за исключением по- рядка следования двух утверждений внутри инструкции if. В этом все различие. В первом случае мы отображаем значение в первом узле
X
, прежде чем делать рекурсивный вызов для отображения остальной части списка
Y
. Во втором случае мы совершаем вызов для отображения остальной части списка,
Z
прежде чем отображать значение в первом узле
[
. Благодаря этому порядок отображения оказывается обратным.
Поскольку обе эти функции одинаково лаконичны, можно пред- положить, что рекурсия уместна для решения обеих этих задач, од- нако это не так. Чтобы убедиться в этом, давайте рассмотрим итера- тивные реализации обеих этих функций. void displayListForwardsIterative(listPtr head) {
X for (listPtr current = head; current != NULL; current = current->next) cout << current->data << "\n";
}
void displayListBackwardsIterative(listPtr head) {
Y stack
Z for (listPtr current = head; current != NULL; current = current->next) nodes.push(current);
[ while (!nodes.empty()) {
\ nodePtr current = nodes.top();
] nodes.pop();
^ cout << current->data << "\n";
}
}
202 Глава 6
Функция для отображения элементов списка в прямом порядке — это не что иное, как цикл прямого обхода
X
, вроде обсуждаемого нами в главе 4. Однако функция для отображения элементов списка в об- ратном порядке сложнее. Она страдает от той же необходимости в ис- пользовании «тропы из хлебных крошек», как и наши задачи с двоич- ным деревом. Отображение узлов связного списка в обратном порядке по определению требует возврата к предыдущим узлам. В случае с од- носвязным списком этого нельзя сделать, используя сам список, поэ- тому требуется вторая структура. В данном примере нам нужен другой стек. После объявления стека
Y
мы помещаем все узлы нашего связно- го списка в стек, используя цикл for
Z
. Поскольку это стек, в котором каждый элемент добавляется поверх предыдущих элементов, первый элемент в связном списке будет находиться внизу стека, а последний элемент связного списка — на его вершине. Мы вводим цикл while, ко- торый выполняется до тех пор, пока стек не опустеет
[
, последова- тельно захватываем указатель на верхний узел в стеке
\
, удаляем из стека этот указатель на узел
]
, а затем отображаем данные в узле, на который ссылаемся
^
. Поскольку данные на вершине стека являются последними данными в связном списке, в результате данные связного списка оказываются отображенными в обратном порядке.
Как и в случае с показанной ранее итеративной функцией двоично- го дерева, эту функцию можно было написать без использования стека
(путем создания второго списка в пределах функции, которая является обратной версией оригинала). Тем не менее нет никакого способа сде- лать вторую функцию такой же простой, как и первая, или избежать фактического обхода двух структур вместо одной. Сравнивая рекурсив- ную и итерационную реализации, нетрудно заметить, что итеративная
«прямая» функция настолько проста, что у использования рекурсии отсутствуют практические преимущества и при наличии нескольких практических недостатков. Напротив, рекурсивная «обратная» функ- ция проще, чем итеративная версия, и от нее следует ожидать пример- но такой же производительности, как от итеративной версии. Таким образом, «обратная» функция представляет собой разумное использо- вание рекурсии, в то время как «прямая» функция, хоть и является хо- рошим упражнением в рекурсивном программировании, не может счи- таться хорошим примером практического применения рекурсии.
Упражнения
Как всегда, вам настоятельно рекомендуется опробовать идеи, пред- ставленные в данной главе!
6.1.
Напишите функцию для вычисления суммы только положитель- ных чисел в целочисленном массиве. Сначала решите эту задачу, используя итерацию. Затем, используя технику, описанную в этой главе, преобразуйте вашу итеративную функцию в рекурсивную.
6.2.
Рассмотрите массив, представляющий двоичную строку, где значе- ние каждого элемента равно либо 0, либо 1. Напишите функцию
bool
, чтобы проверить двоичную строку на нечетность (устано- вить, содержит ли двоичная строка нечетное количество единич- ных битов). Подсказка: помните, что рекурсивная функция воз- вратит true (нечетность) или false (четность), а не количество единичных битов. Решите эту задачу, используя сначала итера- цию, а затем рекурсию.
6.3.
Напишите функцию, которой передается целочисленный массив и «целевое» число и которая возвращает количество случаев, ког- да это целевое число встречается в массиве. Решите эту задачу, ис- пользуя сначала итерацию, а затем рекурсию.
6.4.
Придумайте свою собственную задачу: найдите задачу на обра- ботку одномерного массива, которую вы уже решали или тривиа- льную, учитывая ваш текущий уровень мастерства, и решите ее с помощью рекурсии.
6.5.
Решите задачу 6.1 снова, используя связный список вместо массива.
6.6.
Решите задачу 6.2 снова, используя связный список вместо массива.
6.7.
Решите задачу 6.3 снова, используя связный список вместо массива.
6.8.
Придумайте свою собственную задачу: попробуйте найти задачу на обработку связных списков, которая трудно решается с помо- щью итерации, но может быть решена с использованием рекур- сии.
6.9.
Некоторые слова в программировании имеют более одного зна- чения. В главе 4 мы узнали о куче, из которой мы выделяем память с помощью оператора new. Термин куча также описывает двоич- ное дерево, в котором значение каждого узла выше любого значе- ния в левом или правом поддереве. Напишите рекурсивную функ- цию, чтобы определить, является ли двоичное дерево кучей.
6.10.
Двоичное дерево поиска — это двоичное дерево, в котором значение каждого узла больше любого значения в левом поддереве этого узла, но меньше любого значения в правом поддереве узла. На- пишите рекурсивную функцию, чтобы определить, является ли двоичное дерево двоичным деревом поиска.
6.11.
Напишите рекурсивную функцию, которой передается корне- вой указатель двоичного дерева поиска и новое значение, под- лежащее вставке, и которая создает новый узел с новым значе- нием, помещая его в нужное место для поддержания структуры двоичного дерева поиска. Подсказка: попробуйте сделать пара- метр корневого указателя опорным параметром.
6.12.
Придумайте свою собственную задачу: рассмотрите простые ста- тистические показатели для набора числовых значений, напри- мер среднее арифметическое, медиана, мода и т.д. Попробуйте написать рекурсивные функции для вычисления этих статисти- ческих показателей для двоичного дерева, состоящего из целых чисел. Некоторые из них легче написать, чем другие. Почему?
, чтобы проверить двоичную строку на нечетность (устано- вить, содержит ли двоичная строка нечетное количество единич- ных битов). Подсказка: помните, что рекурсивная функция воз- вратит true (нечетность) или false (четность), а не количество единичных битов. Решите эту задачу, используя сначала итера- цию, а затем рекурсию.
6.3.
Напишите функцию, которой передается целочисленный массив и «целевое» число и которая возвращает количество случаев, ког- да это целевое число встречается в массиве. Решите эту задачу, ис- пользуя сначала итерацию, а затем рекурсию.
6.4.
Придумайте свою собственную задачу: найдите задачу на обра- ботку одномерного массива, которую вы уже решали или тривиа- льную, учитывая ваш текущий уровень мастерства, и решите ее с помощью рекурсии.
6.5.
Решите задачу 6.1 снова, используя связный список вместо массива.
6.6.
Решите задачу 6.2 снова, используя связный список вместо массива.
6.7.
Решите задачу 6.3 снова, используя связный список вместо массива.
6.8.
Придумайте свою собственную задачу: попробуйте найти задачу на обработку связных списков, которая трудно решается с помо- щью итерации, но может быть решена с использованием рекур- сии.
6.9.
Некоторые слова в программировании имеют более одного зна- чения. В главе 4 мы узнали о куче, из которой мы выделяем память с помощью оператора new. Термин куча также описывает двоич- ное дерево, в котором значение каждого узла выше любого значе- ния в левом или правом поддереве. Напишите рекурсивную функ- цию, чтобы определить, является ли двоичное дерево кучей.
6.10.
Двоичное дерево поиска — это двоичное дерево, в котором значение каждого узла больше любого значения в левом поддереве этого узла, но меньше любого значения в правом поддереве узла. На- пишите рекурсивную функцию, чтобы определить, является ли двоичное дерево двоичным деревом поиска.
6.11.
Напишите рекурсивную функцию, которой передается корне- вой указатель двоичного дерева поиска и новое значение, под- лежащее вставке, и которая создает новый узел с новым значе- нием, помещая его в нужное место для поддержания структуры двоичного дерева поиска. Подсказка: попробуйте сделать пара- метр корневого указателя опорным параметром.
6.12.
Придумайте свою собственную задачу: рассмотрите простые ста- тистические показатели для набора числовых значений, напри- мер среднее арифметическое, медиана, мода и т.д. Попробуйте написать рекурсивные функции для вычисления этих статисти- ческих показателей для двоичного дерева, состоящего из целых чисел. Некоторые из них легче написать, чем другие. Почему?
204 Глава 7
Эта глава сильно отличается от пре- дыдущих. Ранее я подчеркивал важ- ность нахождения собственных реше- ний для задач. В конце концов, именно этому и посвящена данная книга — написанию ори- гинальных решений для задач в области програм- мирования.
Тем не менее даже в предыдущих главах мы говори- ли о том, что вы всегда учитесь на написанном ранее коде, и поэтому вам следует сохранять весь этот код на будущее. В этой главе мы сде- лаем еще один шаг вперед и поговорим о том, как использовать код и идеи других программистов для решения стоящих перед нами задач.
Если вы помните, с чего началась эта книга, то эта тема может показаться странным вкраплением. Вначале я говорил о том, какой ошибкой была бы попытка решения сложных задач путем модифи-
+ " ! =
7
Решение задач с помощью повторного использования кода 205
кации чужого кода. Мало того, что такой подход имеет мало шансов на успех, но даже когда он срабатывает, вы не приобретаете обуча- ющего опыта. И если это все, что вы умеете, вы никогда не стане- те настоящим программистом и мало чем сможете обогатить сферу разработки программного обеспечения. Тем не менее, когда задача создания программы является достаточно сложной, неразумно ожи- дать от программиста того, что он будет разрабатывать ее решение с нуля. Это неэффективное использование времени программиста, и оно необоснованно подразумевает, что программист является экс- пертом во всем. Кроме того, это скорее приведет к созданию про- граммы полной ошибок или сложной в плане сопровождения.
Хорошее и плохое повторное
использование кода
Нам следует различать хорошее повторное использование кода, по- зволяющее нам писать программы лучше и быстрее, и плохое по- вторное использование кода, позволяющее на какое-то время при- твориться программистом, но в конечном итоге приводящее к плохому развитию как кода, так и самого программиста. В табл. 7.1 приведены эти различия. В левом столбце перечислены свойства хо- рошего повторного использования кода, а в правом столбце — пло- хого. При рассмотрении вопроса о возможности повторного ис- пользования кода спросите себя, какие из свойств вы, скорее всего, продемонстрируете — из правого или левого столбца.
Табл. 7.1. Хорошее и плохое повторное использование кода
%!% C%"2%!…%
,“C% ƒ%"=…, % =
%.% C%"2%!…%
,“C% ƒ%"=…, % =
Следование схеме
Копирование чужой работы
Усиливает и расширяет ваши возможности
Фальсифицирует ваши возможности
Помогает вам научиться
Позволяет избежать обучения
Экономит время в краткосрочной и долгосрочной перспективе
Может сэкономить время в краткосрочной перспективе, но удлинить рабочий процесс в долгосрочной перспективе
Результат — рабочая программа
Может привести к созданию программы, которая в любом случае не работает
Важно отметить, что различие между хорошим и плохим повтор- ным использованием кода зависит не от самого кода или того, как вы его используете, а от вашего отношения к этому коду и концеп- циям, которые вы заимствуете. Однажды при написании курсовой работы по литературе я обнаружил, что часть знаний, полученных при прохождении курса, имела отношение к теме моей работы, по- этому я включил их в нее. Когда я показал черновик своей работы профессору, она сказала, что я должен был оформить эту инфор- мацию в качестве цитаты. В замешательстве я спросил своего про- фессора, в какой момент я могу просто использовать свои знания в работе, не указывая ссылку на источник. Она ответила, что я смогу
206 Глава 7
перестать ссылаться на других при использовании знаний, находя- щихся в моей голове, когда я стану таким экспертом, что другие нач- нут ссылаться на меня.
Выражаясь в терминах программирования, хорошее повторное использование кода имеет место, когда вы сами пишете код, основы- ваясь на чьем-то описании общей концепции, или когда вы использу- ете код, который могли бы написать сами. На протяжении всей этой главы мы будем говорить о том, как вы можете усвоить концепции создания кода, чтобы быть уверенными, что повторное использова- ние помогает вам стать более умелым, а не более ленивым програм- мистом.
Позвольте мне также обратить внимание на последнюю строку табл. 7.1. Попытки плохого повторного использования кода часто оказываются неудачными. Это неудивительно, потому что при этом программист использует код, который он или она фактически не по- нимает. В некоторых ситуациях заимствованный код поначалу рабо- тает, однако когда программист пытается изменить или расширить заимствованную кодовую базу, отсутствие глубокого понимания не позволяет подойти к задаче организованно. Поэтому программист начинает действовать наобум путем проб и ошибок, тем самым нару- шая первое и самое главное из наших общих правил решения задач, которое заключается в том, чтобы всегда иметь план.
Основы работы с компонентами
Теперь, когда мы знаем, к какому результату стремимся, давайте клас- сифицируем различные способы повторного использования кода.
В этой книге я буду использовать термин компонент для обозначе- ния того, что было создано одним программистом и что может быть повторно использовано другим для решения задачи программиро- вания. Компоненты могут существовать в любом месте континуума от абстрактного до конкретного, от идеи до полностью реализован- ного кода. Если мы подумаем о решении задачи программирования, как о проекте в стиле «сделай сам», то изученные нами методы для решения задач будут похожи на инструменты, а компоненты — на специальные части. Описанные далее компоненты представляют со- бой различные способы повторного использования результатов ра- боты других программистов.
Кодовый блок
Кодовый блок представляет собой не что иное, как блок кода, скопи- рованный из одного листинга программы в другой. На сленге это называется «копипастой». Это самая низкоуровневая форма исполь- зования компонентов и часто пример плохого повторного использо- вания кода со всеми вытекающими из этого проблемами. Конечно, если код, который вы копируете, ваш собственный, это не наносит
Решение задач с помощью повторного использования кода 207
реального вреда, правда, вы можете рассмотреть возможность упа- ковки существующего кода в виде библиотеки классов или другой структуры, чтобы его можно было повторно использовать более чи- стым и удобным образом.
Алгоритмы
Алгоритм — это программный рецепт; особый метод достижения цели, который выражается либо простым языком, либо наглядно, как в блок-схеме. Например, в главе 3 мы обсудили операцию сор-
тировки массивов и различные способы ее реализации. Одним из таких способов является алгоритм сортировки вставками, и я про- демонстрировал примерную реализацию этого алгоритма. Важно отметить, что данный код представлял собой одну из реализаций такой сортировки, однако она сама по себе является алгоритмом — способом сортировки массива, а не конкретным кодом. При сорти- ровке вставками берется каждое последующее неотсортированное значение в массиве, а отсортированные значения многократно сдвигаются на одну позицию, пока не освободится место, подходя- щее для значения, подлежащего вставке. Любой код, который ис- пользует этот метод сортировки массива, представляет собой со- ртировку вставками.
Алгоритмы — это высокоуровневая форма повторного использо- вания кода, и обычно они характеризуются хорошими свойствами этого процесса. Алгоритмы — это, по сути, просто идеи, и вам как программисту необходимо реализовать идеи, используя свои навы- ки программирования и глубокое понимание самого алгоритма. Ал- горитмы, которые вы обычно будете использовать, хорошо изучены и имеют предсказуемую производительность в различных ситуаци- ях. С алгоритмом в качестве схемы вы можете быть уверены в пра- вильности вашего кода и его эффективности.
Тем не менее у использования алгоритма в качестве основы для кода существуют некоторые недостатки. Когда вы используете ал- горитм, вы начинаете с концептуального уровня. Поэтому впереди вас ожидает длинный путь до готового кода для конкретного раздела программы. Алгоритм, безусловно, экономит время, поскольку этап решения задачи по сути завершен, однако в зависимости от алгорит- ма и его конкретного применения в вашей работе, реализация алго- ритма может оказаться нетривиальной задачей.
Шаблоны
В программировании шаблон (или шаблон проектирования) представ- ляет собой схему для конкретного метода программирования. Эта концепция напоминает алгоритм, но отличается от него. Алгорит- мы подобны рецептам для решения конкретных задач, а шаблоны — это общие методы, используемые в конкретных ситуациях в процес- се программирования. Задачи, которые решают шаблоны, обычно
208 Глава 7
входят в структуру самого кода. Например, в главе 6 мы обсудили проблему, представленную рекурсивной функцией в классе связных списков: рекурсивной функции был нужен «головной» указатель на первый узел в списке в качестве параметра, однако эти данные долж- ны были оставаться приватными. Решение заключалось в создании
обертки, функции, которая адаптировала бы один список параметров к другому. Техника, предполагающая использование обертки, пред- ставляет собой шаблон проектирования. Мы можем использовать этот шаблон для решения проблемы рекурсивной функции в клас- се, однако его можно использовать и другими способами. Например, предположим, что у нас есть класс linkedList, который позволяет вставлять или удалять элементы в любой точке списка, но нам нужен класс stack, то есть список, который позволяет вставлять и удалять элементы только на одном конце. Мы могли бы создать новый класс stack
, который предусматривал бы общедоступные методы для ти- пичных операций стека, таких как push и pop. Эти методы просто вы- зывали бы функции-члены на объекте linkedList, являющемся при- ватным членом данных нашего класса stack. Таким образом, мы бы повторно использовали функциональность класса связного списка, предоставляя при этом интерфейс класса stack.
Как и алгоритмы, шаблоны представляют собой высокоуровневую форму использования компонентов, а изучение шаблонов является отличным способом пополнения вашего профессионального инстру- ментария. Однако шаблоны разделяют некоторые из потенциальных проблем алгоритмов. Знать о существовании шаблона — это не то же самое, что уметь реализовывать его на определенном языке, который вы выбрали для решения задачи программирования, кроме того, ша- блоны часто бывает сложно реализовать правильно или с максималь- ной производительностью. Например, существует шаблон, известный как одиночка (singleton), представляющий собой класс, который позволя- ет создавать только один объект класса. Создать класс-одиночку легко, однако создать класс-одиночку, который не создает единственный до- пустимый экземпляр объекта до тех пор, пока он на самом деле не пона- добится, бывает на удивление сложно, а лучший способ решения этой задачи может отличаться в зависимости от языка.
1 ... 21 22 23 24 25 26 27 28 ... 34
Абстрактные типы данных
Абстрактный тип данных, как говорилось в главе 5, представляет со- бой тип, определяемый его операциями, а не тем, как эти операции выполняются. Хорошим примером является тип стек, который мы уже несколько раз использовали в этой книге. Абстрактные типы данных похожи на шаблоны в плане определения эффектов опера- ций, но они конкретно не определяют, как эти операции реализу- ются. Тем не менее, как и в случае с алгоритмами, для этих опера- ций существуют хорошо известные методы реализации. Например, стек может быть реализован с использованием любого количества таких основополагающих структур данных, как связный список или
Решение задач с помощью повторного использования кода 209
массив. Однако когда мы выбираем конкретную структуру данных, решения, связанные с ее реализацией, иногда оказываются уже при- нятыми. Предположим, мы реализовали стек с помощью связного списка и не можем обернуть существующий связный список, но нам требуется написать собственный код списка. Поскольку стек являет- ся структурой типа «последним пришел — первым ушел» (last-in-first- out), нам имеет смысл добавлять и удалять элементы только на од- ном конце связанного списка. Кроме того, имеет смысл добавлять и удалять элементы только в начале списка. Теоретически вы можете добавлять и удалять элементы в конце, однако это приведет к неэф- фективному обходу всего списка при каждой вставке или удалении.
Чтобы избежать этих обходов, потребуется двусвязный список с от- дельным указателем на последний узел в списке. Вставка и удаление элементов в начале списка делает возможной простейшую, наибо- лее эффективную реализацию, поэтому практически все реализации стеков на основе связных списков одинаковы.
Таким образом, хотя слово абстрактный в названии абстракт-
ный тип данных означает, что тип является концептуальным и не со- держит деталей, относящихся к реализации, на практике, если вы решите реализовать абстрактный тип данных в своем коде, вам не придется разрабатывать реализацию с нуля. Вместо этого в качестве руководства вам послужат существующие реализации данного типа.
Библиотеки
В программировании библиотека представляет собой набор свя- занных фрагментов кода. Как правило, библиотека включает код в скомпилированной форме вместе с необходимыми объявлениями исходного кода. Библиотеки могут включать автономные функции, классы, объявления типов или что-либо еще, что может использо- ваться в коде. В языке C++ наиболее очевидными примерами явля- ются стандартные библиотеки. Функция strcmp, которую мы исполь- зовали в предыдущих главах, была взята из старой библиотеки языка
C cstring, такие контейнерные классы, как vector, — из стандартной библиотеки шаблонов C ++ и даже макрос NULL, который мы исполь- зовали во всем коде на основе указателей, не является частью языка
C++, а определяется в заголовочном файле библиотеки, stdlib.h. По- скольку так много базовых функций содержится в библиотеках, их использование в современном программировании неизбежно.
Вообще, использование библиотеки является примером хорошего повторного использования кода. Код включен в библиотеку, посколь- ку он обеспечивает функциональность, которая обычно необходима в различных программах, — библиотечный код помогает программи- стам избежать необходимости «изобретать колесо». Тем не менее как разработчики программ при использовании библиотечного кода мы должны стремиться научиться на своем опыте, а не просто использо- вать обходной путь. Далее в этой главе мы рассмотрим пример.
210 Глава 7
Обратите внимание на то, что, хотя многие библиотеки явля- ются библиотеками общего назначения, другие разработаны как ин-
терфейсы прикладного программирования (API), предоставляющие про- граммисту, работающему с высокоуровневым языком, упрощенное или более последовательное представление об основополагающей платформе. Например, язык Java включает в себя API под названи- ем JDBC, который предоставляет классы, позволяющие программам взаимодействовать с реляционными базами данных стандартным способом. Другой пример — это DirectX, который предоставляет программистам игр Microsoft Windows обширную функциональ- ность для работы со звуком и графикой. В обоих случаях библиоте- ка обеспечивает связь между высокоуровневой программой и фунда- ментальным аппаратным и программным обеспечением — с движком базы данных в случае JDBC и графическим и звуковым оборудовани- ем в случае DirectX. Более того, в обоих случаях повторное исполь- зование кода не только допустимо, но и желательно для всех прак- тических целей. Программист базы данных, работающий с языком
Java, или графический программист, пишущий код C++ для Windows, будет использовать API, если не перечисленные выше API, то что-то еще, но программист не будет с нуля разрабатывать новое соедине- ние с платформой.
Изучение компонентов
Компоненты настолько полезны, что программисты используют их при любой возможности. Тем не менее, чтобы использовать компо- нент для решения задачи, программист должен знать о его существо- вании. В зависимости от того, насколько точно вы их определяете, доступные компоненты могут исчисляться сотнями или даже тыся- чами, а начинающий программист будет знать только о некоторых из них. Поэтому хороший программист всегда должен стараться обо- гащать свои знания о компонентах. Такое накопление знаний про- исходит двумя разными способами: программист может специально выделить время для изучения новых компонентов или поискать ком- понент для решения конкретной задачи. Мы будем называть первый подход исследовательским обучением, а второй — обучением по мере необ-
ходимости. Чтобы развиваться как программисту, вам нужно будет использовать оба подхода. После освоения синтаксиса выбранно- го вами языка программирования, изучение новых компонентов — один из основных способов самосовершенствования в качестве про- граммиста.
Исследовательское обучение
Давайте начнем с примера исследовательского обучения. Предполо- жим, нам нужно узнать больше о шаблонах проектирования. К сча- стью, существует общее соглашение относительно того, какие шаб- лоны проектирования являются наиболее полезными или часто
Решение задач с помощью повторного использования кода 211
используемыми, поэтому мы могли бы начать с любого количества ресурсов по этой теме и быть достаточно уверенными в том, что не упустим ничего важного. Мы бы выиграли от простого нахождения списка шаблонов проектирования и его изучения, однако мы бы до- стигли большего понимания, если бы реализовали некоторые из этих шаблонов.
Один шаблон, который мы можем найти в типичном списке, назы- вается стратегией или политикой. Это идея, позволяющая выбрать алго- ритм или часть алгоритма во время выполнения программы. В самой чистой форме, в форме стратегии, этот шаблон позволяет изменить способ функционирования метода или функции, не изменяя результат.
Например, метод класса, который сортирует данные или предполагает их сортировку, может допускать выбор метода сортировки (например, быстрая сортировка или сортировка вставками). Результат — отсорти- рованные данные — во всех случаях будет одним и тем же, однако пре- доставление клиенту возможности выбора метода сортировки может обеспечить некоторые преимущества в плане производительности. На- пример, клиент может избежать использования быстрой сортировки для данных с высокой степенью дублирования. В форме политики вы- бор клиента влияет на результат. Например, предположим, что класс представляет собой набор игральных карт. Политика сортировки мо- жет определить, считаются ли тузы самыми старшими картами (стар- ше короля) или самыми младшими (младше 2).
Применение полученных знаний на практике
Изучив предыдущий абзац, вы узнали, что представляет собой ша- блон стратегия/политика, но вы не сделали его своим инструмен- том. Это подобно разнице между просмотром инструментов в ма- газине и их фактической покупкой и использованием. Поэтому давайте возьмем этот шаблон проектирования с полки и попробу- ем его в деле. Самый быстрый способ опробовать новую технику — включить ее в уже написанный вами код. Давайте сформулируем за- дачу, которая может быть решена с использованием этого шаблона и построена на уже написанном нами коде.
:
В каждом классе школы назначается староста («первый ученик»), который отвечает за поддержание порядка в классе в отсутствие учителя. Первоначально это звание при- сваивалось ученику с наивысшим уровнем успеваемости, однако теперь некоторые преподаватели считают, что староста должен определяться по старшинству, то есть по наименьшему идентификационному номеру ученика, поскольку они назначаются последовательно. Другая часть преподавателей считает традицию избрания старосты смехотворной и намеревается протестовать против нее, просто выбрав ученика, имя которого идет первым по алфавиту в ведомости успеваемости класса. Наша задача — изменить класс коллекции учеников, добавив метод для извлечения из этой коллекции старосты, при этом учитывая критерии отбора различных групп учителей.
212 Глава 7
Как видите, решение этой задачи подразумевает использование шаблона в форме политики. Мы хотим, чтобы наш метод, возвраща- ющий имя старосты, возвращал имена разных учеников в зависи- мости от выбранного критерия. Чтобы реализовать это средствами языка C++, мы будем использовать указатели на функции. В главе 3 мы кратко рассмотрели эту концепцию в действии на примере функ- ции qsort, принимающей указатель на функцию, которая сравни- вает два элемента в массиве, подлежащем сортировке. Мы сделаем что-то подобное и здесь; мы используем набор функций сравнения, которые возьмут два наших объекта studentRecord и определят, явля- ется ли первый ученик «лучше» второго, исходя из их оценок, иден- тификационных номеров или имен.
Для начала мы должны определить тип для наших функций срав- нения: typedef bool
X(* rstStudentPolicy)(studentRecord r1, studentRecord r2);
Это объявление создает тип с именем rstStudentPolicy в каче- стве указателя на функцию, которая возвращает bool и принимает два параметра типа studentRecord. Круглые скобки вокруг * rstStudent-
Policy
X
необходимы, чтобы исключить интерпретацию объявления как функции, которая возвращает указатель на bool. После добавле- ния этого объявления мы можем создать три функции политики: bool higherGrade(studentRecord r1, studentRecord r2) {
return r1.grade() > r2.grade();
}
bool lowerStudentNumber(studentRecord r1, studentRecord r2) {
return r1.studentID() < r2.studentID();
}
bool nameComesFirst(studentRecord r1, studentRecord r2) {
return
Xstrcmp(r1.name().c_str()Y, r2.name().c_str()Y )Z< 0;
}
Первые две функции очень просты: higherGrade возвращает зна- чение true, когда первая запись содержит более высокую оценку, а lowerStudentNumber возвращает значение true, когда первая запись со- держит меньший идентификационный номер ученика. Третья функ- ция nameComesFirst по сути представляет собой то же самое, но требу- ет использования библиотечной функции strcmp
X
, которая ожидает две строки в «стиле С», то есть нуль-терминированные массивы сим- волов вместо объектов string. Поэтому мы должны вызывать метод c_
str()
Y
в строках name в обеих записях с данными об учениках. Функ- ция strcmp возвращает отрицательное число, когда первая строка следует по алфавиту перед второй, поэтому мы проверяем возвращен- ное значение, чтобы посмотреть, не превышает ли оно значение 0
Z
Теперь мы готовы изменить сам класс studentCollection: class studentCollection {
private:
struct studentNode {
studentRecord studentData;
Решение задач с помощью повторного использования кода 213
studentNode * next;
};
public:
studentCollection();
studentCollection();
studentCollection(const studentCollection ©);
studentCollection& operator=(const studentCollection &rhs);
void addRecord(studentRecord newStudent);
studentRecord recordWithNumber(int IDnum);
void removeRecord(int IDnum);
X void setFirstStudentPolicy( rstStudentPolicy f);
Y studentRecord rstStudent();
private:
Z rstStudentPolicy _currentPolicy;
typedef studentNode * studentList;
studentList _listHead;
void deleteList(studentList &listPtr);
studentList copiedList(const studentList copy);
};
Это объявление класса, которое мы видели в главе 5 с тремя но- выми членами: приватным членом данных, _currentPolicy
Z
, для хранения указателя на одну из наших функций-политик; методом setFirstStudentPolicy
Z
для изменения этой политики; и самим ме- тодом rstStudent
Y
, который возвращает имя старосты в соответ- ствии с текущей политикой. Код для метода setFirstStudentPolicy прост: void studentCollection::setFirstStudentPolicy( rstStudentPolicy f) {
_currentPolicy = f;
}
Нам также нужно изменить конструктор по умолчанию для ини- циализации текущей политики: studentCollection::studentCollection() {
_listHead = NULL;
_currentPolicy = NULL;
}
Теперь мы готовы создать метод rstStudent: studentRecord studentCollection:: rstStudent() {
X if (_listHead == NULL || _currentPolicy == NULL) {
studentRecord dummyRecord(-1, -1, "");
return dummyRecord;
}
studentNode * loopPtr = _listHead;
Y studentRecord rst = loopPtr->studentData;
Z loopPtr = loopPtr->next;
while (loopPtr != NULL) {
if (
[_currentPolicy(loopPtr->studentData, rst)) {
rst = loopPtr->studentData;
}
\loopPtr = loopPtr->next;
}
return rst;
}
214 Глава 7
Этот метод начинается с проверки специальных случаев. При отсутствии списка для проверки или политики
X
мы возвращаем фиктивную запись. В противном случае мы обходим список, чтобы обнаружить ученика, лучше всего соответствующего текущей поли- тике, используя базовые методы поиска, которые многократно при- меняли в этой книге. Мы присваиваем запись в начале списка пере- менной rst
Y
, запускаем нашу переменную цикла на второй записи в списке
Z
и начинаем обход. Внутри цикла обхода вызов текущей функции политики
[
сообщает нам, является ли рассматриваемый нами ученик «лучшим учеником» по сравнению с лучшим учеником, определенным нами до сих пор, исходя из текущего критерия. По- сле завершения цикла мы возвращаем имя старосты, то есть «перво- го ученика»
\
Анализ решения задачи выбора старосты
Решив задачу с помощью шаблона стратегии/политики, мы скорее распознаем ситуации, в которых применим этот метод, чем если бы мы просто о нем прочитали, но так и не опробовали. Мы также можем проанализировать нашу задачу, чтобы начать формировать собственное мнение о ценности метода, о том, когда его использо- вание может быть уместным, а когда ошибочным или по крайней мере принести больше неприятностей, чем пользы. Одна мысль, которая могла у вас возникнуть по поводу этого конкретного шаб- лона, заключается в том, что он ухудшает инкапсуляцию и сокры- тие информации. Например, если клиентский код предоставляет функции политики, он требует доступа к типам, которые обычно остаются внутренними для класса, в данном случае к типу studen- tRecord
. (Мы рассмотрим способ решения этой проблемы в упраж- нениях). Это означает, что в клиентском коде может произойти сбой, если мы когда-либо изменим этот тип, и мы должны сопоста- вить эту проблему с преимуществами шаблона, прежде чем приме- нять его в других проектах. В предыдущих главах мы уже говорили, что знание того, когда следует использовать тот или иной метод, а когда не следует, так же важно, как знание того, как его использо- вать. Изучение собственного кода позволяет вам ответить на этот крайне важный вопрос.
Для дальнейшей практики вы можете просмотреть свою библи- отеку готовых проектов, чтобы найти код, который можно перера- ботать с использованием этого метода. Помните о том, что большая часть «настоящего» программирования предполагает дополнение или изменение существующей базы кода, поэтому данная практика отлично подходит для подобных модификаций, а также развивает ваши навыки работы с конкретным компонентом. Более того, одним из преимуществ хорошего повторного использования кода является то, что мы учимся на этом, а данная практика позволяет получить от обучения максимальную пользу.
Решение задач с помощью повторного использования кода 215
Обучение по мере необходимости
Предыдущий раздел был посвящен тому, что можно было бы назвать
«блуждающим обучением». Хотя такие странствия ценны для про- граммистов, иногда нам приходится двигаться к определенной цели.
Если вы работаете над конкретной задачей, особенно если вам нуж- но успеть к какому-то сроку и вы считаете, что компонент может вам очень помочь, вам не нужно бесцельно блуждать по миру программи- рования в надежде наткнуться на то, что вам нужно. Вместо этого вы хотите как можно быстрее найти компонент или компоненты, непо- средственно применимые к вашей ситуации. Однако проблема вот в чем: как вы найдете то, что вам нужно, если вы точно не знаете, что ищете? Рассмотрим следующую задачу.
: D ' ' # $ 9
В проекте программы будет использоваться ваш класс studentCollection. Клиент- ский код нуждается в возможности обхода всех учеников в коллекции. Очевидно, что для обеспечения сокрытия информации клиентскому коду не может быть предоставлен прямой доступ к списку, однако эффективность обходов — непременное условие.
Поскольку ключевым словом в этом описании является эффек-
тивность, давайте уточним, что это значит в данном случае. Предпо- ложим, что отдельный объект нашего класса studentCollection со- держит 100 учеников. Если бы у нас был прямой доступ к связному списку, мы могли бы написать цикл для обхода этого списка, кото- рый бы обрабатывал список 100 раз. Это максимально эффективный обход списка. Любое решение, требующее, чтобы мы обрабатывали список более 100 раз для определения результата, будет считаться неэффективным.
Без требования эффективности мы можем попытаться решить эту задачу, добавив в наш класс простой метод recordAt, который бу- дет возвращать запись с данными об ученике в конкретной позиции в коллекции, присвоив первой записи номер 1: studentRecord studentCollection::recordAt(int position) {
studentNode * loopPtr = _listHead;
int i = 1;
X while (loopPtr != NULL && i < position) {
i++;
loopPtr = loopPtr->next;
}
if (loopPtr == NULL) {
Y studentRecord dummyRecord(-1, -1, "");
return dummyRecord;
} else {
Z return loopPtr->studentData;
}
}
В этом методе используем цикл
X
, чтобы обходить список до тех пор, пока мы не достигнем желаемой позиции или конца списка.
1 ... 22 23 24 25 26 27 28 29 ... 34
Решение задач с помощью повторного использования кода 209
массив. Однако когда мы выбираем конкретную структуру данных, решения, связанные с ее реализацией, иногда оказываются уже при- нятыми. Предположим, мы реализовали стек с помощью связного списка и не можем обернуть существующий связный список, но нам требуется написать собственный код списка. Поскольку стек являет- ся структурой типа «последним пришел — первым ушел» (last-in-first- out), нам имеет смысл добавлять и удалять элементы только на од- ном конце связанного списка. Кроме того, имеет смысл добавлять и удалять элементы только в начале списка. Теоретически вы можете добавлять и удалять элементы в конце, однако это приведет к неэф- фективному обходу всего списка при каждой вставке или удалении.
Чтобы избежать этих обходов, потребуется двусвязный список с от- дельным указателем на последний узел в списке. Вставка и удаление элементов в начале списка делает возможной простейшую, наибо- лее эффективную реализацию, поэтому практически все реализации стеков на основе связных списков одинаковы.
Таким образом, хотя слово абстрактный в названии абстракт-
ный тип данных означает, что тип является концептуальным и не со- держит деталей, относящихся к реализации, на практике, если вы решите реализовать абстрактный тип данных в своем коде, вам не придется разрабатывать реализацию с нуля. Вместо этого в качестве руководства вам послужат существующие реализации данного типа.
Библиотеки
В программировании библиотека представляет собой набор свя- занных фрагментов кода. Как правило, библиотека включает код в скомпилированной форме вместе с необходимыми объявлениями исходного кода. Библиотеки могут включать автономные функции, классы, объявления типов или что-либо еще, что может использо- ваться в коде. В языке C++ наиболее очевидными примерами явля- ются стандартные библиотеки. Функция strcmp, которую мы исполь- зовали в предыдущих главах, была взята из старой библиотеки языка
C cstring, такие контейнерные классы, как vector, — из стандартной библиотеки шаблонов C ++ и даже макрос NULL, который мы исполь- зовали во всем коде на основе указателей, не является частью языка
C++, а определяется в заголовочном файле библиотеки, stdlib.h. По- скольку так много базовых функций содержится в библиотеках, их использование в современном программировании неизбежно.
Вообще, использование библиотеки является примером хорошего повторного использования кода. Код включен в библиотеку, посколь- ку он обеспечивает функциональность, которая обычно необходима в различных программах, — библиотечный код помогает программи- стам избежать необходимости «изобретать колесо». Тем не менее как разработчики программ при использовании библиотечного кода мы должны стремиться научиться на своем опыте, а не просто использо- вать обходной путь. Далее в этой главе мы рассмотрим пример.
210 Глава 7
Обратите внимание на то, что, хотя многие библиотеки явля- ются библиотеками общего назначения, другие разработаны как ин-
терфейсы прикладного программирования (API), предоставляющие про- граммисту, работающему с высокоуровневым языком, упрощенное или более последовательное представление об основополагающей платформе. Например, язык Java включает в себя API под названи- ем JDBC, который предоставляет классы, позволяющие программам взаимодействовать с реляционными базами данных стандартным способом. Другой пример — это DirectX, который предоставляет программистам игр Microsoft Windows обширную функциональ- ность для работы со звуком и графикой. В обоих случаях библиоте- ка обеспечивает связь между высокоуровневой программой и фунда- ментальным аппаратным и программным обеспечением — с движком базы данных в случае JDBC и графическим и звуковым оборудовани- ем в случае DirectX. Более того, в обоих случаях повторное исполь- зование кода не только допустимо, но и желательно для всех прак- тических целей. Программист базы данных, работающий с языком
Java, или графический программист, пишущий код C++ для Windows, будет использовать API, если не перечисленные выше API, то что-то еще, но программист не будет с нуля разрабатывать новое соедине- ние с платформой.
Изучение компонентов
Компоненты настолько полезны, что программисты используют их при любой возможности. Тем не менее, чтобы использовать компо- нент для решения задачи, программист должен знать о его существо- вании. В зависимости от того, насколько точно вы их определяете, доступные компоненты могут исчисляться сотнями или даже тыся- чами, а начинающий программист будет знать только о некоторых из них. Поэтому хороший программист всегда должен стараться обо- гащать свои знания о компонентах. Такое накопление знаний про- исходит двумя разными способами: программист может специально выделить время для изучения новых компонентов или поискать ком- понент для решения конкретной задачи. Мы будем называть первый подход исследовательским обучением, а второй — обучением по мере необ-
ходимости. Чтобы развиваться как программисту, вам нужно будет использовать оба подхода. После освоения синтаксиса выбранно- го вами языка программирования, изучение новых компонентов — один из основных способов самосовершенствования в качестве про- граммиста.
Исследовательское обучение
Давайте начнем с примера исследовательского обучения. Предполо- жим, нам нужно узнать больше о шаблонах проектирования. К сча- стью, существует общее соглашение относительно того, какие шаб- лоны проектирования являются наиболее полезными или часто
Решение задач с помощью повторного использования кода 211
используемыми, поэтому мы могли бы начать с любого количества ресурсов по этой теме и быть достаточно уверенными в том, что не упустим ничего важного. Мы бы выиграли от простого нахождения списка шаблонов проектирования и его изучения, однако мы бы до- стигли большего понимания, если бы реализовали некоторые из этих шаблонов.
Один шаблон, который мы можем найти в типичном списке, назы- вается стратегией или политикой. Это идея, позволяющая выбрать алго- ритм или часть алгоритма во время выполнения программы. В самой чистой форме, в форме стратегии, этот шаблон позволяет изменить способ функционирования метода или функции, не изменяя результат.
Например, метод класса, который сортирует данные или предполагает их сортировку, может допускать выбор метода сортировки (например, быстрая сортировка или сортировка вставками). Результат — отсорти- рованные данные — во всех случаях будет одним и тем же, однако пре- доставление клиенту возможности выбора метода сортировки может обеспечить некоторые преимущества в плане производительности. На- пример, клиент может избежать использования быстрой сортировки для данных с высокой степенью дублирования. В форме политики вы- бор клиента влияет на результат. Например, предположим, что класс представляет собой набор игральных карт. Политика сортировки мо- жет определить, считаются ли тузы самыми старшими картами (стар- ше короля) или самыми младшими (младше 2).
Применение полученных знаний на практике
Изучив предыдущий абзац, вы узнали, что представляет собой ша- блон стратегия/политика, но вы не сделали его своим инструмен- том. Это подобно разнице между просмотром инструментов в ма- газине и их фактической покупкой и использованием. Поэтому давайте возьмем этот шаблон проектирования с полки и попробу- ем его в деле. Самый быстрый способ опробовать новую технику — включить ее в уже написанный вами код. Давайте сформулируем за- дачу, которая может быть решена с использованием этого шаблона и построена на уже написанном нами коде.
:
В каждом классе школы назначается староста («первый ученик»), который отвечает за поддержание порядка в классе в отсутствие учителя. Первоначально это звание при- сваивалось ученику с наивысшим уровнем успеваемости, однако теперь некоторые преподаватели считают, что староста должен определяться по старшинству, то есть по наименьшему идентификационному номеру ученика, поскольку они назначаются последовательно. Другая часть преподавателей считает традицию избрания старосты смехотворной и намеревается протестовать против нее, просто выбрав ученика, имя которого идет первым по алфавиту в ведомости успеваемости класса. Наша задача — изменить класс коллекции учеников, добавив метод для извлечения из этой коллекции старосты, при этом учитывая критерии отбора различных групп учителей.
212 Глава 7
Как видите, решение этой задачи подразумевает использование шаблона в форме политики. Мы хотим, чтобы наш метод, возвраща- ющий имя старосты, возвращал имена разных учеников в зависи- мости от выбранного критерия. Чтобы реализовать это средствами языка C++, мы будем использовать указатели на функции. В главе 3 мы кратко рассмотрели эту концепцию в действии на примере функ- ции qsort, принимающей указатель на функцию, которая сравни- вает два элемента в массиве, подлежащем сортировке. Мы сделаем что-то подобное и здесь; мы используем набор функций сравнения, которые возьмут два наших объекта studentRecord и определят, явля- ется ли первый ученик «лучше» второго, исходя из их оценок, иден- тификационных номеров или имен.
Для начала мы должны определить тип для наших функций срав- нения: typedef bool
X(* rstStudentPolicy)(studentRecord r1, studentRecord r2);
Это объявление создает тип с именем rstStudentPolicy в каче- стве указателя на функцию, которая возвращает bool и принимает два параметра типа studentRecord. Круглые скобки вокруг * rstStudent-
Policy
X
необходимы, чтобы исключить интерпретацию объявления как функции, которая возвращает указатель на bool. После добавле- ния этого объявления мы можем создать три функции политики: bool higherGrade(studentRecord r1, studentRecord r2) {
return r1.grade() > r2.grade();
}
bool lowerStudentNumber(studentRecord r1, studentRecord r2) {
return r1.studentID() < r2.studentID();
}
bool nameComesFirst(studentRecord r1, studentRecord r2) {
return
Xstrcmp(r1.name().c_str()Y, r2.name().c_str()Y )Z< 0;
}
Первые две функции очень просты: higherGrade возвращает зна- чение true, когда первая запись содержит более высокую оценку, а lowerStudentNumber возвращает значение true, когда первая запись со- держит меньший идентификационный номер ученика. Третья функ- ция nameComesFirst по сути представляет собой то же самое, но требу- ет использования библиотечной функции strcmp
X
, которая ожидает две строки в «стиле С», то есть нуль-терминированные массивы сим- волов вместо объектов string. Поэтому мы должны вызывать метод c_
str()
Y
в строках name в обеих записях с данными об учениках. Функ- ция strcmp возвращает отрицательное число, когда первая строка следует по алфавиту перед второй, поэтому мы проверяем возвращен- ное значение, чтобы посмотреть, не превышает ли оно значение 0
Z
Теперь мы готовы изменить сам класс studentCollection: class studentCollection {
private:
struct studentNode {
studentRecord studentData;
Решение задач с помощью повторного использования кода 213
studentNode * next;
};
public:
studentCollection();
studentCollection();
studentCollection(const studentCollection ©);
studentCollection& operator=(const studentCollection &rhs);
void addRecord(studentRecord newStudent);
studentRecord recordWithNumber(int IDnum);
void removeRecord(int IDnum);
X void setFirstStudentPolicy( rstStudentPolicy f);
Y studentRecord rstStudent();
private:
Z rstStudentPolicy _currentPolicy;
typedef studentNode * studentList;
studentList _listHead;
void deleteList(studentList &listPtr);
studentList copiedList(const studentList copy);
};
Это объявление класса, которое мы видели в главе 5 с тремя но- выми членами: приватным членом данных, _currentPolicy
Z
, для хранения указателя на одну из наших функций-политик; методом setFirstStudentPolicy
Z
для изменения этой политики; и самим ме- тодом rstStudent
Y
, который возвращает имя старосты в соответ- ствии с текущей политикой. Код для метода setFirstStudentPolicy прост: void studentCollection::setFirstStudentPolicy( rstStudentPolicy f) {
_currentPolicy = f;
}
Нам также нужно изменить конструктор по умолчанию для ини- циализации текущей политики: studentCollection::studentCollection() {
_listHead = NULL;
_currentPolicy = NULL;
}
Теперь мы готовы создать метод rstStudent: studentRecord studentCollection:: rstStudent() {
X if (_listHead == NULL || _currentPolicy == NULL) {
studentRecord dummyRecord(-1, -1, "");
return dummyRecord;
}
studentNode * loopPtr = _listHead;
Y studentRecord rst = loopPtr->studentData;
Z loopPtr = loopPtr->next;
while (loopPtr != NULL) {
if (
[_currentPolicy(loopPtr->studentData, rst)) {
rst = loopPtr->studentData;
}
\loopPtr = loopPtr->next;
}
return rst;
}
214 Глава 7
Этот метод начинается с проверки специальных случаев. При отсутствии списка для проверки или политики
X
мы возвращаем фиктивную запись. В противном случае мы обходим список, чтобы обнаружить ученика, лучше всего соответствующего текущей поли- тике, используя базовые методы поиска, которые многократно при- меняли в этой книге. Мы присваиваем запись в начале списка пере- менной rst
Y
, запускаем нашу переменную цикла на второй записи в списке
Z
и начинаем обход. Внутри цикла обхода вызов текущей функции политики
[
сообщает нам, является ли рассматриваемый нами ученик «лучшим учеником» по сравнению с лучшим учеником, определенным нами до сих пор, исходя из текущего критерия. По- сле завершения цикла мы возвращаем имя старосты, то есть «перво- го ученика»
\
Анализ решения задачи выбора старосты
Решив задачу с помощью шаблона стратегии/политики, мы скорее распознаем ситуации, в которых применим этот метод, чем если бы мы просто о нем прочитали, но так и не опробовали. Мы также можем проанализировать нашу задачу, чтобы начать формировать собственное мнение о ценности метода, о том, когда его использо- вание может быть уместным, а когда ошибочным или по крайней мере принести больше неприятностей, чем пользы. Одна мысль, которая могла у вас возникнуть по поводу этого конкретного шаб- лона, заключается в том, что он ухудшает инкапсуляцию и сокры- тие информации. Например, если клиентский код предоставляет функции политики, он требует доступа к типам, которые обычно остаются внутренними для класса, в данном случае к типу studen- tRecord
. (Мы рассмотрим способ решения этой проблемы в упраж- нениях). Это означает, что в клиентском коде может произойти сбой, если мы когда-либо изменим этот тип, и мы должны сопоста- вить эту проблему с преимуществами шаблона, прежде чем приме- нять его в других проектах. В предыдущих главах мы уже говорили, что знание того, когда следует использовать тот или иной метод, а когда не следует, так же важно, как знание того, как его использо- вать. Изучение собственного кода позволяет вам ответить на этот крайне важный вопрос.
Для дальнейшей практики вы можете просмотреть свою библи- отеку готовых проектов, чтобы найти код, который можно перера- ботать с использованием этого метода. Помните о том, что большая часть «настоящего» программирования предполагает дополнение или изменение существующей базы кода, поэтому данная практика отлично подходит для подобных модификаций, а также развивает ваши навыки работы с конкретным компонентом. Более того, одним из преимуществ хорошего повторного использования кода является то, что мы учимся на этом, а данная практика позволяет получить от обучения максимальную пользу.
Решение задач с помощью повторного использования кода 215
Обучение по мере необходимости
Предыдущий раздел был посвящен тому, что можно было бы назвать
«блуждающим обучением». Хотя такие странствия ценны для про- граммистов, иногда нам приходится двигаться к определенной цели.
Если вы работаете над конкретной задачей, особенно если вам нуж- но успеть к какому-то сроку и вы считаете, что компонент может вам очень помочь, вам не нужно бесцельно блуждать по миру программи- рования в надежде наткнуться на то, что вам нужно. Вместо этого вы хотите как можно быстрее найти компонент или компоненты, непо- средственно применимые к вашей ситуации. Однако проблема вот в чем: как вы найдете то, что вам нужно, если вы точно не знаете, что ищете? Рассмотрим следующую задачу.
: D ' ' # $ 9
В проекте программы будет использоваться ваш класс studentCollection. Клиент- ский код нуждается в возможности обхода всех учеников в коллекции. Очевидно, что для обеспечения сокрытия информации клиентскому коду не может быть предоставлен прямой доступ к списку, однако эффективность обходов — непременное условие.
Поскольку ключевым словом в этом описании является эффек-
тивность, давайте уточним, что это значит в данном случае. Предпо- ложим, что отдельный объект нашего класса studentCollection со- держит 100 учеников. Если бы у нас был прямой доступ к связному списку, мы могли бы написать цикл для обхода этого списка, кото- рый бы обрабатывал список 100 раз. Это максимально эффективный обход списка. Любое решение, требующее, чтобы мы обрабатывали список более 100 раз для определения результата, будет считаться неэффективным.
Без требования эффективности мы можем попытаться решить эту задачу, добавив в наш класс простой метод recordAt, который бу- дет возвращать запись с данными об ученике в конкретной позиции в коллекции, присвоив первой записи номер 1: studentRecord studentCollection::recordAt(int position) {
studentNode * loopPtr = _listHead;
int i = 1;
X while (loopPtr != NULL && i < position) {
i++;
loopPtr = loopPtr->next;
}
if (loopPtr == NULL) {
Y studentRecord dummyRecord(-1, -1, "");
return dummyRecord;
} else {
Z return loopPtr->studentData;
}
}
В этом методе используем цикл
X
, чтобы обходить список до тех пор, пока мы не достигнем желаемой позиции или конца списка.
1 ... 22 23 24 25 26 27 28 29 ... 34