Файл: Think likea programmer.pdf

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 30.10.2023

Просмотров: 419

Скачиваний: 1

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

СОДЕРЖАНИЕ

158 Глава 5связным списком, это исходный головной указатель, имеющий зна- чение NULL. Здесь это определенно вызовет проблему, поскольку мы не проверяем это и код вызовет сбой, если мы попытаемся разыме- новать указатель loopPtr после входа в цикл. Кроме того, мы должны рассмотреть возможность, что идентификатор, переданный клиент- ским кодом, вообще не соответствует никаким записям в коллекции. В этом случае, даже если _listHead не NULL, loopPtr в конце концов станет NULL, когда мы достигнем конца списка. Таким образом, основная идея состоит в том, что мы должны остановить цикл, если значение loopPtr становится NULL. Это не сложно, но что мы вернем в такой ситуации? Очевидно, мы не можем вернуть loopPtr->studentData, поскольку loopPtr будет NULL. Вме- сто этого мы можем создать и вернуть фиктивную запись student-Record с очевидно некорректными значениями. studentRecord studentCollection::recordWithNumber(int idNum) {studentNode * loopPtr = _listHead;while (XloopPtr != NULL && loopPtr->studentData.studentID() != idNum) {loopPtr = loopPtr->next;}if (YloopPtr == NULL) {Z studentRecord dummyRecord( –1, –1, "");return dummyRecord;} else {return loopPtr->studentData;}}В этой версии метода, если цикл закончен, а указатель цикла со- держит значение NULL Y, мы создаем фиктивную запись с пустой строкой вместо фамилии студента и значениями –1 для его оценки и идентификатора Z и возвращаем эту запись. Возвращаясь к циклу, мы проверяем, равен ли NULL указатель loopPtr, что может произойти, если список пуст либо мы безуспешно полностью его просмотрели. Обратим внимание, что выражение условия цикла X — составное вы- ражение с условием loopPtr != NULL, идущим первым. Именно так и должно быть. Язык C++ использует для оценки составных логических выражений механизм, известный как сокращенные вычисления . Проще говоря, правая часть составного логического выражения не рассма- тривается, если значение всего выражения уже известно. Поскольку && означает логическое и, то если левая часть выражения && оказыва- ется ложной, все выражение также оказывается ложью, независимо от значения правой части. Для повышения эффективности, C++ ис- пользует этот факт, опуская расчет правой части выражения && , если левая часть оказывается ложной (для || или логического или правая часть по той же причине не рассчитывается, когда левая часть истин- на). Следовательно, когда loopPtr равен NULL, выражение loopPtr != NULL ложно, и правая часть выражения && не рассчитывается. Без со- кращенных вычислений правая часть рассчитывалась бы и указатель на NULL разыменовывался бы, вызывая сбой программы. Решение задач с классами 159Эта реализация позволяет избежать потенциальной поломки, ха- рактерной для первой версии, однако она оказывает слишком много доверия клиентскому коду. То есть функция, вызывающая этот метод, должна проверить вернувшуюся обратно запись studentRecord и до выполнения дальнейших операций убедиться, что она не фиктивная. Если вы похожи на меня, то вам должно быть немного не по себе . .%4B/Есть еще один способ. C++, как и многие другие языки программирования, пред-лагает механизм, известный как исключения, позволяющий методу или глобальной функции недвусмысленно сообщить об ошибке туда, откуда она была вызвана. Это сделано для ситуации, которая сложилась в этом методе, когда нет хорошего отве-та на вопрос, что возвращать, если ввод был некорректным. Исключения сложнее, чем мы можем позволить себе рассматривать сейчас, и, к сожалению, реализация исключений в C++ не решает проблему доверия, описанную в предыдущем абзаце.Перегруппировка спискаМетод removeRecord похож на recordWithNumber в той, что мы должны пройти список для нахождения узла, который необходимо удалить. Однако есть задачи сверх этого. Удаление узла из списка требует вни- мательности, поскольку остальные узлы должны остаться связным списком. Проще всего зашить сделанную нами дырочку соединени- ем узла, который шел перед удаленным, с тем, который шел следом за ним. Нам не нужно набрасывать функцию, потому что у нас уже есть прототип функции в объявлении класса, поэтому перей дем к тестам.studentCollection s;studentRecord stu3(84, 1152, "Sue");studentRecord stu2(75, 4875, "Ed");studentRecord stu1(98, 2938, "Todd");s.addRecord(stu3);s.addRecord(stu2);s.addRecord(stu1);X s.removeRecord(4875) Мы создали объект s класса studentCollection, а также три объ- екта класса studentRecord, каждый из которых был добавлен в кол- лекцию. Обратите внимание, что мы могли бы использовать одну и ту же запись, меняя значения между вызовами addRecord, но не стали этого делать для упрощения тестового кода. Последняя строка в те- сте вызывает метод removeRecord X, который в данном случае удалит вторую запись, то есть запись для студента по имени «Ed». Используя тот же стиль схем указателей, что и в главе 4, проиллюстрируем на рис. 5.1 состояние памяти «до» и «после» этого вызова.На рис. 5.1 (а) мы видим связный список, созданный нашим тесто- вым кодом. Обратите внимание, что, поскольку мы используем класс, наши соглашения о схемах слегка искажены. В левой части рисунка 160 Глава 5изображен стек/куча, в котором находятся _listHead, являющийся приватным полем внутри объекта s класса studentCollection, и idNum, являющийся параметром метода removeRecord. В правой части рисун- ка изображен сам список в куче. Помните, что addRecord размещает новую запись в начало списка, поэтому записи расположены в обрат- ном порядке по сравнению с тем, как они добавлялись в тестовом коде. Идентификатор среднего узла, «Ed» совпадает с параметром 4875, поэтому он должен быть удален из списка. Рис. 5.1 (б) показыва- ет результат вызова метода. Первый узел списка, «Todd», теперь ука- зывает на узел, который ранее был в списке третьим, то есть на «Sue». Узел «Ed» больше не связан с большим списком и удален. Рис. 5.1. Ситуация «до» и «после» вызова метода removeRecord в тестовом примере Теперь, зная, какого результата мы хотим добиться, начнем пи- сать код. Поскольку мы знаем, что нам надо найти узел с соответ- ствующим идентификатором, мы могли бы начать с цикла while из метода recordWithNumber. По окончанию это цикла указатель будет указывать на узел, который надо удалить. К сожалению, нам надо кое-что еще, чтобы закончить удаление. Посмотрите на рис. 5.1. Что- бы закрыть дыру и восстановить связный список, мы должны изме- нить поле next узла «Todd». Если все, что у нас есть, это указатель на узел «Ed», способа указать на «Todd» не существует, потому что каждый узел в связном списке указывает на своего последователя, а не предшественника. (Из-за подобной ситуации некоторые связные списки связывают в обоих направлениях, такие списки называются Решение задач с классами 161двойные связные списки , но нужда в них возникает редко.) Таким об- разом, в дополнение к указателю на удаляемый узел (который назы- вается loopPtr, если мы применим код предыдущей функции), нам необходим указатель на предыдущий узел: давайте назовем такой указатель trailing. Рис. 5.2 демонстрирует эту концепции примени- мо к нашему примеру.Рис. 5.2. Указатели, необходимые для удаления узла с номером idNumC указателями loopPtr ссылающимся на удаляемый узел и trail- ing, ссылающимся на предыдущий узел, мы можем удалить желае- мый узел и сохранить список.void studentCollection::removeRecord(int idNum) {studentNode * loopPtr = _listHead;X studentNode * trailing = NULL;while (loopPtr != NULL && loopPtr->studentData.studentID() != idNum) {Ytrailing = loopPtr;loopPtr = loopPtr->next;}Z if (loopPtr == NULL) return;[ trailing->next = loopPtr->next;\ delete loopPtr;}Первая часть этой функции похожа на метод recordWithNumber, с тем исключением, что мы объявили указатель trailing X и внутри цикла присвоили ему старое значение loopPtr Y до перехода loopPtr к следующему узлу. Таким образом, указатель trailing всегда нахо- дится на один узел позади loopPtr. Благодаря нашей работе с пре- дыдущей функцией мы уже знаем про специальный случай. Поэтому, когда цикл закончится, мы проверяем, не равен ли loopPtr значе- нию NULL. Если равен, это означает, что мы не нашли узел с заданным идентификатором и немедленно возвращаемся Z. Я называю выра- жение return в середине функции «смываться». Некоторые програм- мисты возражают против этого, потому что функцию с несколькими точками выхода тяжело читать. Однако альтернативный вариант в этом случае еще один уровень вложения для инструкции if, которое идет следом, так что я лучше смоюсь. Определив, что удаляемый узел существует, пора удалить его. На диаграмме видео, что необходимо установить, чтобы поле next узла 162 Глава 5trailing указывало на узел, на который в настоящий момент указы- вает поле next узла loopPtr [. Затем мы можем безопасно удалить узел, на который указывает loopPtr \Этот код работает для нашего тестового примера, но, как всег- да, необходимо проверить его на возможных специальных случаях . Мы уже разобрались с возможностью, что номер idNum отсутствует в записях нашей коллекции, но нет ли еще какой-нибудь проблемы? Посмотрим на пример. Изменится ли что-нибудь, если мы попробу- ем удалить первый или третий узел вместо среднего? Тестирование показывает отсутствие проблем при удалении третьего (последнего) узла. Однако удаление первого узла и в самом деле вызывает труд- ности из-за того, что в этом случае отсутствует предыдущий узел, на который должен указывать trailing. Для этого мы должны мани- пулировать указателем _listHead. Рис. 5.3 иллюстрирует ситуацию, сложившуюся по окончании цикла while. Рис. 5.3. Положение до удаления первого узла в спискеВ этой ситуации нам нужно перенаправить _listHead на бывший второй узел в списке, то есть на узел «Ed». Давайте перепишем наш метод, чтобы решить данную проблему. void studentCollection::removeRecord(int idNum) {studentNode * loopPtr = _listHead;studentNode * trailing = NULL;while (loopPtr != NULL && loopPtr->studentData.studentID() != idNum) {trailing = loopPtr;loopPtr = loopPtr->next;}if (loopPtr == NULL) return;X if (trailing == NULL) {Y _listHead = _listHead–>next;} else {trailing->next = loopPtr->next;}delete loopPtr;}Как видите, как проверка условия X, так и код, решающий про- блему Y, просты, поскольку мы тщательно проанализировали ситуа- цию, прежде чем писать его. Решение задач с классами 163Деструктор Реализовав эти три метода, мы можем подумать, что класс stu- dentCollection готов. Однако это не так. Первое, чего не хватает нашему классу, это деструктор. Это специальный метод, вызывае- мый, когда объект выходит из области видимости (когда функция, объявившая этот объект, закончила работу). Если в классе отсут- ствуют динамические данные, обычно деструктор не нужен. Одна- ко если такие данные присутствуют, без деструктора не обойтись. Помните, для того, чтобы не допустить утечек памяти, мы долж- ны применить ключевое слово delete для всех объектов, которым была выделена память с помощью ключевого слова new. Если объ- ект нашего класса studentCollection содержит три узла, необхо- димо освободить память, которую занимает каждый из них. К сча- стью, это несложно. Нам необходимо пройти по нашему связному списку, удаляя узлы. Однако вместо того, чтобы делать это непо- средственно, давайте напишем служебный метод, удаляющий все узлы в studentList. В приватной секции нашего класса добавим объявление:void deleteList(studentList &listPtr);Код для этого метода будет выглядеть так:void studentCollection::deleteList(studentList &listPtr) {while (listPtr != NULL) {X studentNode * temp = listPtr;Y listPtr = listPtr->next;Z delete temp;}}Во время обхода указатель на текущий узел копируется во вре- менную переменную X, передвигается к следующему узлу Y, а за- тем удаляется узел, на который указывает временная переменная ZС помощью этого кода мы можем написать деструктор очень просто. Прежде всего, добавим деструктор в публичную секцию объявления нашего класса:studentCollection();Обратите внимание, что, как и у конструктора, имя деструктора совпадает с названием класса и в нем отсутствует возвращаемый тип. Тильда перед именем позволяет отличить деструктор от конструкто- ра. Реализация будет выглядеть так:studentCollection::studentCollection() {deleteList(_listHead);}Код в этом методе прост, однако очень важно протестировать де- структор. Хотя плохо написанный деструктор и может вызвать сбой вашей программы, большинство проблем с деструктором вызывают 164 Глава 5не ошибку программы, но утечки памяти или, что хуже, необъясни- мое поведение программы. Следовательно, важно протестировать деструктор с помощью отладчика среды разработки, так чтобы вы могли видеть, действительно ли деструктор вызывает delete для каждого узла.Глубокое копирование Осталась еще одна серьезная проблема. В главе 4 мы кратко обсу- дили концепцию перекрестных связей , когда две переменных типа указатель имеют одно и то же значение. Даже если это разные пе- ременные, они указывают на одну и ту же структуру данных; следо- вательно, изменение структуры одной переменной изменяет обе. Эта проблема часто всплывает в классах, включающих динамиче- ски распределенную память. Чтобы увидеть, почему это проблема, рассмотрим следующий элементарный код на C++:int x = 10;int y = 15;x = y;X x = 5;Предположим, я спросил бы вас, какое влияние последнее выра- жение X оказывает на переменную y. Вы, вероятно, удивились бы не оговорился ли я. Последнее выражение не оказывает совсем никако- го эффекта на y, только на x. А теперь посмотрите на это:studentCollection s1;studentCollection s2;studentRecord r1(85, 99837, "John");s2.addRecord(r1);studentRecord r2(77, 4765, "Elsie");s2.addRecord(r2);X s1 = s2;Y s2.removeRecord(99837) Предположим, я спрошу вас, какое влияние окажет последнее вы- ражение Y на s1. К сожалению, влияние действительно будет. Хотя s1 и s2 — два разных объекта, они отныне не полностью отдельные объекты. По умолчанию, когда один объект приравнен к другому, как мы сейчас приравняли объекты s1 и s2 X, язык C++ производит то, что известно как поверхностное копирование . При поверхностном ко- пировании каждое поле класса одного объекта присваивается друго- му. Так если, _listHead — наше единственное поле класса, публично, s2 = s1 будет аналогично s1._listHead = s2._listHead. Получае- тся, что поле _listHead обоих объектов указывает на одно и то же место в памяти: узел для «Elsie», который указывает на другой узел, а именно на узел «John». Поэтому после удаления узла «John», он уда- ляется из двух списков, поскольку на самом деле существует только один список. Рис. 5.4 иллюстрирует положение, сложившееся к кон- цу данного кода. Решение задач с классами 165Рис. 5.4. Результаты поверхностного копирования при перекрестных связях; удаление узла «John» из одного списка удаляет из обоих Однако все может быть еще хуже. Что, если последняя строка кода удалит первую запись — узел «Elsie»? В этом случае указатель _listHead объекта s2 станет указывать на узел «John», а узел «Elsie» будет удален. Однако указатель _listHead объекта s1 по-прежнему будет указывать на удаленный узел «Elsie», то есть возникнет опасная висячая ссылка , как показано на рис. 5.5.Рис. 5.5. Удаление из s2 приводит к висящей ссылке в s1Для решения этой проблемы применяют глубокое копирование, то есть не только копирование указателя на структуру, но копирова- ние всей структуры. В нашем случае это означает копирование всех узлов списка. Тем самым происходит истинное копирование. Как и ранее, давайте начнем с приватных служебных методов, то есть в нашем случае с метода, копирующего studentList. Объявление в приватной секции класса выглядит примерно так:studentList copiedList(const studentList original);Как и ранее, я выбрал существительное для названия метода, возвра щающего значение. Реализация метода выглядит так:X studentCollection::studentList studentCollection::copiedList(const studentList original) {Y if (original == NULL) {return NULL;}studentList newList = new studentNode;Z newList->studentData = original->studentData;[ studentNode * oldLoopPtr = original->next;\ studentNode * newLoopPtr = newList;while (oldLoopPtr != NULL) { 166 Глава 5] newLoopPtr->next = new studentNode;newLoopPtr = newLoopPtr->next;newLoopPtr->studentData = oldLoopPtr->studentData;oldLoopPtr = oldLoopPtr->next;}^ newLoopPtr->next = NULL;_ return newList;}В этом методе происходит много всего, поэтому давайте будем раз- бираться постепенно. Прежде всего, обратим внимание, что, опреде- ляя тип возвращаемого значения, мы должны указать в префиксе имя класса X. В противном случае компилятор не поймет, о каком типе мы говорим. (Внутри метода это необязательно, поскольку компилятор уже знает, частью какого класса является метод – немного запутанно!) Мы проверяем, не пуст ли входящий список. Если он пуст, смываем- ся Y. Теперь, зная, что у нас есть список для копирования, копируем данные первого узла до начала цикла Z, поскольку для этого узла нам необходимо изменить указатель на начало нового списка.Затем мы устанавливаем два указателя для прохода по списку. Ука- затель oldLoopPtr [ проходит через пришедший список; он всегда бу- дет указывать на узел, который мы собираемся копировать. Указатель newLoopPtr\ проходит через новый, скопированный, список и всегда указывает на последний созданный узел, то есть узел, до которого мы будем добавлять следующий узел. Как и в методе removeRecord нам ну- жен здесь хвостовой указатель. В цикле ] мы создаем новый узел, пе- редвигаем newLoopPtr, чтобы он указывал на него, копируем данные из старого узла в новый и передвигаем указатель oldLoopPtr. После цикла мы завершаем новый список, присваивая значение NULL полю next по- следнего узла ^ и возвращаем (return) указатель на новый список _Как же этот служебный метод решает обозначенную выше пробле- му? Сам по себе никак. Но, добавив этот код, мы можем перегрузить оператор присваивания. Перегрузка операторов — особенность языка C++, позволяющая изменять действия, производимые встроенными операторами над определенными типами данных. В нашем случае мы хотим перегрузить оператор присваивания (=) так, чтобы вместо уста- новленного по умолчанию поверхностного копирования, он вызывал наш метод copiedList для выполнения глубокого копирования. В пуб- личной секции класса добавим следующее:XstudentCollection& Yoperator=(Zconst studentCollection & [rhs);Перегружаемый оператор определяется названием метода с ис- пользованием ключевого слова operator, за которым идет оператор, который мы хотим перегрузить Y. Имя выбранное мной для параме- тра (rhs [) обычный выбор для перегрузки операторов, поскольку это сокращение от словосочетания «правая сторона» (right-hand side). Это помогает программистам упрощать себе жизнь. Так, в присвое- нии, о котором идет речь s2 = s1, объект s1 будет правой стороной оператора присваивания, а s2 — левой стороной . На правую часть мы Решение задач с классами1   ...   16   17   18   19   20   21   22   23   ...   34

167ссылаемся через параметр, а на левую — непосредственно через поле класса, так же как и при любом другом методе класса. Итак, наша зада- ча состоит в создании списка, на который будет указывать _listHead и который будет являться копией списка, на который указывает _lis- tHead объекта rhs. Таким образом, при вызове s2 = s1 будет создан объект s2 как истинная копия объекта s1. Тип параметра — это постоянная ссылка на наш класс Z. Тип воз- вращаемого значения — это всегда ссылка на класс X. Скоро вы увиди- те, почему параметр — это ссылка. Вас, возможно, удивляет, почему метод возвращает все подряд, начиная с того, что мы изменяем поле класса непосредственно в методе. Это происходит из-за того, что язык C++ позволяет присвоение по цепочке, например s3 = s2 = s1, в котором возвращаемое значение первого присвоения становится па- раметром следующего.Теперь, когда синтаксис понятен, код оператора присваивания становится вполне очевидным:studentCollection& studentCollection::operator=(const studentCollection &rhs) {X if (this != &rhs) {Y deleteList(_listHead);Z _listHead = copiedList(rhs._listHead);}[ return * this;}Чтобы избежать утечки памяти, мы сначала должны удалить все узлы из левостороннего списка Y. (Именно для этой цели мы отдель- но написали вспомогательный метод deleteList, а не включили его код непосредственно в деструктор.) Удалив предыдущий левосторон- ний список, мы копируем правосторонний список, используя наш другой вспомогательный метод Z. Однако до выполнения этих шагов мы проверяем, что объект с правовой стороны отличается от объекта с левой (то есть, это не что-то подобное s1 = s2) проверяя, отлича- ются ли указатели X. Если указатели одинаковые, нет необходимости что-то делать, при этом это не вопрос эффективности. Если мы вы- полним глубокое копирование для одинаковых указателей, когда мы будем удалять узлы в левостороннем списке, мы также будем удалять узлы и в правостороннем. Наконец, мы возвращаем указатель на лево- сторонний объект [; это случится независимо от того, действительно ли скопировали мы что-нибудь или нет, потому что, хотя выражение, подобное s3 = s2 = s1, выглядит странным, мы хотим, чтобы оно рабо тало, если кто-нибудь попытается его выполнить.Сделав служебный метод для копирования списка, мы должны создать и копирующий конструктор . Это конструктор, принимающий другой объект того же класса как объект. Копирующий конструктор вызывается явно, когда нам надо создать дубликат существующего списка studentCollection, но может вызываться и неявно, если объ- ект этого класса передается как параметр по значению в функцию. Из-за этого вы должны предусмотреть передачу объекта по ссылке 168 Глава 5с ключевым словом const вместо передачи по значению, за исклю- чением тех случаев, когда функция, получающая объект, должна из- менить его копию. В противном случае ваш код будет делать много ненужной работы. Например, рассмотрим коллекцию из 10 000 за- писей о студентах. Коллекция может быть передана по ссылке одним указателем. В противном случае копирующий конструктор будет вы- зываться каждый раз во время длительного прохода по коллекции и распределять память 10 000 раз. Затем для этих копий в конце рабо- ты функции будет вызван деструктор с очередным долгим проходом по коллекции высвобождением памяти 10 000 раз. Вот поэтому пра- восторонний параметр перегрузки оператора присваивания исполь- зует параметр по ссылке с ключевым словом const. Для добавления копирующего конструктора в наш класс, доба- вим прежде его объявление в публичной секции объявления нашего класса.studentCollection(const studentCollection &original);Как и во всех конструкторах, здесь нет типа возвращаемого зна- чения. И, как и в случае перегрузки оператора присваивания, пере- даваемый параметр — это ссылка на наш класс с ключевым словом const. Поскольку мы уже создали служебный метод, реализация бу- дет простой. studentCollection::studentCollection(const studentCollection &original) {_listHead = copiedList(original._listHead);}Теперь мы можем выполнить подобное объявление:studentCollection s2(s1);Это объявление создает s2 и копирует туда все узлы s1. Общий обзор классов с динамической памятьюМы сделали многое в этом классе, завершив методы, указанные в ус- ловиях задачи, а теперь давайте взглянем, что у нас получилось. Вот так выглядит объявление нашего класса.class studentCollection {private:struct studentNode {studentRecord studentData;studentNode * next;};public:studentCollection();studentCollection();studentCollection(const studentCollection &original);studentCollection& operator=(const studentCollection &rhs);void addRecord(studentRecord newStudent);studentRecord recordWithNumber(int idNum);void removeRecord(int idNum); Решение задач с классами 169private:typedef studentNode * studentList;studentList _listHead;void deleteList(studentList &listPtr);studentList copiedList(const studentList original);};Данный урок состоит в том, что при создании классов с динами- ческой памятью необходимо добавлять новые части. В дополнении к сущностям базового фреймворка класса — приватным данным, конструктору и методам отправления данных в объект и получе- ния их оттуда — мы должны добавить методы, работающие с выде- лением и высвобождением динамической памяти. Как минимум мы должны добавить конструктор и деструктор копирования, а также перегрузить оператор присваивания, если есть вероятность, что он кому-нибудь понадобится. Создание этих дополнительных мето- дов часто облегчается созданием служебных методов копирования или удаления динамических структур данных. Кажется, что это большая работа. И это действительно мо- жет быть так. Но важно понимать, что со всем, что вы добавите в класс, вам так или иначе придется разбираться. Другими словами, даже если у нас нет класса для коллекции записей о студентах, ос- нованной на связном списке, мы все равно должны удалять узлы в списке после прохода по ним. Нам все равно придется думать о перекрестных связях, все равно придется проходить сквозь спи- сок и копировать узел за узлом, если нам нужна истинная копия исходного списка и так далее. Размещение всего в класс требует немного больше начальной подготовки, но как только все зара- ботает, клиентский код может не задумываться обо всех деталях, связанных с распределением памяти. Кроме того, инкапсуляции и сокрытие существенно облегчают работу со структурами дина- мических данных.Ошибки, которых следует избегатьМы поговорили о том, как создать хороший класс в языке C++, да- вайте теперь обсудим несколько подводных камней, которые следу- ет избегать.Фальшивый класс Как я уже говорил в начале этой главы, я считаю C++ отличным язы- ком для изучения объектно ориентированного программирования, поскольку это гибридный язык, включающий как процедурную, так и объектно ориентированную парадигму. В этом случае создание класса всегда является выбором программиста. В языках, подобных Java, никогда не стоит вопрос: «Надо ли мне делать класс?» Вместо него возникает вопрос: «Как мне поместить это все в класс?» Тре- бование поместить все в класс приводит к появлению того, что я 170 Глава 5называю фальшивым классом, то есть классом без последовательного проектирования, который корректен синтаксически, но не имеет смысла. Слово класс, как его используют программисты, соответ- ствует смыслу английского слова, означающего группу вещей с об- щими атрибутами, и хороший класс языка C++ соответствует этому определению.Фальшивый класс может быть создан по нескольким причинам. Например, программист хочет использовать глобальные перемен- ные, но не по обоснованным причинам (такие причины редки, но все-таки существуют), а из-за лени — чтобы избегать передачи пара- метров от функции к функции. При этом если программист пони- мает, что широкое использование глобальных переменных это при- знак плохого стиля, он или она полагает, что нашел лазейку. Все или большинство функций программы сваливают в класс, и теперь пере- менные, которые были бы глобальными, становятся полями этого класса. Функция main такой программы создает объект этого фаль- шивого класса и вызывает какой-то «главный» метод в классе. Тех- нически программа не использует глобальные переменные, но фаль- шивый класс означает, что этой программе присущи все недостатки программы с глобальными переменными.Другой тип фальшивых классов возникает из-за того, что про- граммист полагает, что объектно ориентированное программиро- вание всегда «лучше», и применяет его в тех ситуациях, где оно не подходит. В этих случаях программист часто создает класс, который инкапсулирует специфический функционал, имеющий смысл толь- ко в контексте исходной программы, для которой он написан. Есть два способа проверить, пишете ли вы фальшивый класс или нет. За- дайте себе вопрос: «Могу я назвать класс кратко и понятно?» Если имя будет выглядеть как PayrollReportManagerAndPrintSpooler, по- видимому, у вас проблемы. Другой тест выглядит так: «если мне при- дется писать другую программу с похожим функционалом, можно ли этот класс использовать еще раз с небольшими изменениями? Или его придется кардинальным образом переписывать?»Даже в языке C++ появление фальшивых классов неизбежно, на- пример, когда нам надо инкапсулировать данные для использования в классах-коллекциях. Однако такие классы обычно маленькие и эле- ментарные. Когда мы избегаем создания фальшивых классов, наш код становится лучше.Однозадачники Если вам доводилось смотреть телевизионное шоу Good Eats, вы зна- ете, что ведущий Элтон Браун тратит массу времени, рассуждая, как оборудовать кухню с максимальной эффективностью. Часто он вос- стает против кухонных приспособлений, которые называет одноза-дачниками, подразумевая инструменты, хорошо решающие одну зада- чу, но не приспособленные более ни для чего. Разрабатывая классы, Решение задач с классами 171мы должны стремиться сделать их настолько общими, насколько это возможно, последовательно включая все функции необходимые для нашей программы.Один из способов сделать это состоит в использовании шаблон- ных классов . Это продвинутый способ с немного загадочным син- таксисом, однако он позволяет нам создавать классы, где у одного или более полей тип определяется в момент создания объекта клас- са. Шаблонные классы позволяют нам «выделить» основной функ- ционал. Например, наш класс studentCollection содержит много кода одинакового для любого класса, инкапсулирующего связный список. Вместо этого мы можем сделать шаблонный класс для об- щего связного списка, такого, чтобы тип данных внутри узлов спи- ска определялся в момент создания объекта шаблонного класса, а не программировался как studentRecord. Тогда полем нашего клас- са studentCollection будет объект шаблонного класса связного спи- ска, а не указатель на начало списка, и наш класс больше не сможет непосредственно управлять связным списком.Мы не будем рассматривать шаблонные классы в этой книге, од- нако, развивая ваши навыки проектировщика классов, вы должны всегда стремиться делать классы «многозадачниками». Когда вы об- наруживаете, что текущую задачу можно решить, используя класс, написанный тогда, когда вы даже не подозревали о ее существова- нии, вы испытываете чувство глубокого удовлетворения. УпражненияВы знаете, что я хочу вам сказать, не так ли? Вперед, попытаетесь сами!5.1.Давайте попробуем реализовать класс, используя базовый фреймворк. Рассмотрим класс, хранящий данные по автомоби- лям. У нас есть три элемента данных: название производителя, название модели (оба строковые) и год выпуска – целочислен- ное. Создайте класс с методами get/set для каждого поля клас- са. Убедитесь, что вы приняли верные решения о деталях, на- пример имени переменных. Необязательно пользоваться моей конвенцией наименования, важнее грамотно подходить к при- нятию решений и быть в них последовательными.5.2. Добавьте в наш автомобильный класс из предыдущего упражне- ния служебный метод, возвращающий полное описание авто- мобиля в формате строки, например, «1957 Chevrolet Impala». Добавьте второй служебный метод, возвращающий возраст ав- томобиля в годах.5.3. Возьмите функции для строк переменной длины из главы 4 (ap- pend, concatenate и characterAt) и используйте их для создания класса для строк переменной длины. Убедитесь, что вы реализо- вали все необходимые конструкторы, деструктор, а также пере- грузили оператор присваивания. 5.4. Для класса строк переменной длины из предыдущего упражне- ния замените метод characterAt перегруженным оператором []. Например, если myString является объектом нашего класса, тог- да выражение myString[1] должно возвращать то же значение, что и myString.characterAt(1).5.5. Для класса строк переменной длины из предыдущих упражне- ний добавьте метод remove, принимающий начальную позицию и количество символов и удаляющий это количество символов из середины строки. Например, myString.remove(5,3) удалит три символа, начиная с пятой позиции. Убедитесь, что ваш метод ра- ботает, когда значение любого из параметров некор ректно.5.6. Подумайте, можно ли ваш класс строк переменной длины улуч- шить. Например, нет ли общего функционала, который можно выделить в приватный служебный метод?5.7. Возьмите функции записей о студентах из главы 4 (addRecord и averageRecord) и используйте их для создания класса, представ- ляющего коллекцию записей о студентах, как ранее. Убедитесь, что реализовали все необходимые конструкторы, деструктор, а также перегрузили оператор присваивания.5.8. Классу коллекции записей о студентах из предыдущего упражне- ния добавьте метод RecordsWithinRange, принимающий нижнее и верхнее значение оценки как параметры и возвращающий но- вую коллекцию, состоящую из записей в этом диапазоне (исход- ная коллекция не меняется). Например, myCollection.Record- sWithinRange(75, 80)вернет коллекцию всех записей с оценками в диапазоне от 75 до 80 включительно. 173Эта глава посвящена рекурсии, при которой функция прямо или кос- венно вызывает саму себя. Рекур- сивное программирование выглядит так, будто оно должно быть простым. Действи- тельно, хорошее рекурсивное решение часто имеет простой, почти элегантный вид. Тем не менее очень часто путь к этому решению весьма непрост. Это связано с тем, что рекурсия требует от нас мыслить не так, как в случае с другими ти- пами программирования. Когда мы обрабатываем данные с помощью циклов, мы думаем о последовательной обработке, однако при обра- ботке данных с использованием рекурсии, наш обычный процесс по- следовательного мышления не помогает. У многих хороших, но еще не оперившихся программистов возникают проблемы с рекурсией, поскольку они не могут найти способ применения уже освоенных ими + " ! = 6 174 Глава 6навыков решения задач к задачам с рекурсией. В этой главе мы обсу- дим систематический подход к решению таких задач. Ответ заключа- ется в том, что мы будем называть Большой Рекурсивной Идеей, далее по тексту — БРИ. Эта идея настолько проста, что напоминает трюк, но она работает. Обзор основ рекурсии Синтаксис рекурсии не очень сложен. Трудность возникает, когда вы пытаетесь использовать рекурсию для решения задач. Рекурсия име- ет место всегда, когда функция сама себя вызывает, поэтому синтак- сис рекурсии представляет собой просто синтаксис вызова функции. Наиболее распространенной формой является прямая рекурсия, ког- да вызов функции происходит в теле этой же функции. Например:int factorial(int n) {X if (n == 1) return 1;else return n * Yfactorial(n — 1);}Эта функция, которая является общей, но неэффективной демон- страцией рекурсии, вычисляет факториал числа n. Например, если n равно 5, то факториал — это произведение всех чисел от 5 до 1, или 120. Обратите внимание на то, что в некоторых случаях рекурсии не проис- ходит. В этой функции, если параметр равен 1, мы просто возвращаем значение напрямую без какой-либо рекурсии X, это так называемый ба-зовый случай. В противном случае мы делаем рекурсивный вызов YДругой формой рекурсии является косвенная рекурсия — напри- мер, когда функция A вызывает функцию B, которая далее вызывает функцию A. Косвенная рекурсия редко используется в качестве ме- тода решения задач, поэтому мы не будем здесь ее обсуждать. Головная и хвостовая рекурсия Прежде чем обсуждать БРИ, нам нужно понять разницу между голов- ной и хвостовой рекурсией. В случае головной рекурсии рекурсивный вызов, когда он происходит, предваряет другие процессы обработки в функции (считайте, что он происходит вверху или в голове функции). В случае хвостовой рекурсии все наоборот — обработка происходит пе- ред рекурсивным вызовом. Выбор между двумя рекурсивными стиля- ми может показаться произвольным, однако в этом выборе заключа- ется все различие. Чтобы проиллюстрировать это различие, давайте рассмотрим две задачи. : Пассажиры Райской тропической железной дороги (РТЖД) с нетерпением ждут того мо- мента, когда смогут увидеть из окон поезда многочисленных красочных птиц. По этой причине руководство железной дороги очень заинтересовано в состоянии здоровья Решение задач с помощью рекурсии 175местной популяции попугаев и решает подсчитать количество попугаев, находящихся в пределах видимости с каждой железнодорожной платформы вдоль главной линии. На каждую платформу направлен сотрудник РТЖД (см. рис. 6.1), который, безусловно, спо- собен подсчитать количество попугаев. К сожалению, работа усложняется из-за прими- тивной телефонной системы. С каждой платформы можно позвонить только на соседние платформы. Как передать общее число попугаев на терминал главной линии? Рис. 6.1. Сотрудники пяти станций могут общаться только со своими непосредственными соседями Предположим, что Арт насчитал на главном терминале 7 попугаев, Белинда — 5 попугаев, Кори — 3 попугая, Дебби — 10 попугаев, и 2 попу- гая насчитал Эван на последней станции. Таким образом, общее число попугаев составляет 27. Вопрос в том, как сотрудники собираются ра- ботать вместе, чтобы сообщить об этом Арту? Любое решение этой за- дачи потребует последовательной передачи сообщения от основного терминала до конца линии и обратно. Сотрудник на каждой платформе должен будет подсчитать количество попугаев, а затем сообщить о сво- их наблюдениях. Тем не менее существуют два разных подхода к реа- лизации этой цепочки сообщений, которые соответствуют головной и хвостовой рекурсии в программировании. 1   ...   17   18   19   20   21   22   23   24   ...   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-PolicyX необходимы, чтобы исключить интерпретацию объявления как функции, которая возвращает указатель на 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; Решение задач с помощью повторного использования кода 213studentNode * next;};public:studentCollection();studentCollection();studentCollection(const studentCollection &copy);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, для хранения указателя на одну из наших функций-политик; методом setFirstStudentPolicyZ для изменения этой политики; и самим ме- тодом 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


Решение задач с помощью рекурсии 179
нии сгенерировал данный клиент. Менеджер делегирует изучение остальных пяти файлов вице-менеджеру. Он обработает один файл и передаст остальные четыре заместителю менеджера. Этот про- цесс будет продолжаться до тех пор, пока мы не дойдем до шестого сотрудника, стажера, которому передадут один файл, и он должен будет просто обработать его, не имея возможности для дальнейше- го делегирования.
На рис. 6.4 показаны линии связи и разделения труда. Однако, как и в предыдущем примере, существует два различных подхода к реализации цепи сообщений.
Рис. 6.4. Нумерация шагов при использовании Подхода 1 (а) и Подхода 2 (б) для определе-
ния клиента, принесшего наибольшую прибыль
Подход 1
При использовании этого подхода, делегируя оставшиеся файлы, сотрудник также передает самое высокое значение прибыли, наблю- даемое до сих пор. Это значит, что сотрудник должен подсчитать общую прибыль в одном файле и сравнить полученное значение с предыдущим наибольшим значением прибыли, прежде чем делеги- ровать обработку оставшихся файлов другому сотруднику. Вот при- мер того, как это может происходить на практике.
1. МЕНЕДЖЕР подсчитывает прибыль от клиента №0001, которая составляет 172 000 долларов США.
2. МЕНЕДЖЕР ВИЦЕ-МЕНЕДЖЕРУ: «Самое высокое значение прибыли, которое мы наблюдали до сих пор, составляет 172 000

180 Глава 6
долларов США, клиент №0001. Изучите эти пять файлов и опре- делите максимальное значение прибыли».
3. ВИЦЕ-МЕНЕДЖЕР подсчитывает прибыль, полученную от кли- ента №0002, которая составляет 68 000 долларов США. Наиболь- шим из наблюдаемых до сих пор значений прибыли по-прежнему является 172 000 долларов США, клиент №0001.
4. ВИЦЕ-МЕНЕДЖЕР ЗАМЕСТИТЕЛЮ МЕНЕДЖЕРА: «Самое вы- сокое значение прибыли, которое мы наблюдали до сих пор, со- ставляет 172 000 долларов США, клиент №0001. Изучите эти че- тыре файла и определите максимальное значение прибыли».
5. ЗАМЕСТИТЕЛЬ МЕНЕДЖЕРА подсчитывает прибыль, полу- ченную от клиента №0003, которая составляет 193 000 долларов
США. Наибольшим из наблюдаемых до сих пор значений прибы- ли теперь является 193 000 долларов США, клиент №0003.
6. ЗАМЕСТИТЕЛЬ МЕНЕДЖЕРА ПОМОЩНИКУ МЕНЕДЖЕРА:
«Самое высокое значение прибыли, которое мы наблюдали до сих пор, составляет 193 000 долларов США, клиент №0003. Изучи- те эти три файла и определите максимальное значение прибыли».
7. ПОМОЩНИК МЕНЕДЖЕРА подсчитывает прибыль, полу- ченную от клиента №0004, которая составляет 13 000 долларов
США. Наибольшим из наблюдаемых до сих пор значений прибы- ли по-прежнему является 193 000 долларов США, клиент №0001.
8. ПОМОЩНИК МЕНЕДЖЕРА МЛАДШЕМУ МЕНЕДЖЕРУ: «Са- мое высокое значение прибыли, которое мы наблюдали до сих пор, составляет 193 000 долларов США, клиент №0003. Изучите эти два файла и определите максимальное значение прибыли».
9. МЛАДШИЙ МЕНЕДЖЕР подсчитывает прибыль, полученную от клиента №0005, которая составляет 256 000 долларов США.
Наибольшим из наблюдаемых до сих пор значений прибыли те- перь является 256 000 долларов США, клиент №0005.
10. МЛАДШИЙ МЕНЕДЖЕР СТАЖЕРУ: «Самое высокое значение прибыли, которое мы наблюдали до сих пор, составляет 256 000 долларов США, клиент №0005. Изучите последний файл и опре- делите максимальное значение прибыли».
11. СТАЖЕР подсчитывает прибыль, полученную от клиента
№0006, которая составляет 99 000 долларов США. Наибольшим из наблюдаемых до сих пор значений прибыли по-прежнему яв- ляется 256 000 долларов США, клиент №0005.
12. СТАЖЕР МЛАДШЕМУ МЕНЕДЖЕРУ: «Наибольшее значение прибыли составляет 256 000 долларов США, клиент №0005».
13. МЛАДШИЙ МЕНЕДЖЕР ПОМОЩНИКУ МЕНЕДЖЕРА: «Наи- большее значение прибыли составляет 256 000 долларов США, клиент №0005».
14. ПОМОЩНИК МЕНЕДЖЕРА ЗАМЕСТИТЕЛЮ МЕНЕДЖЕРА:

Решение задач с помощью рекурсии 181
«Наибольшее значение прибыли составляет 256 000 долларов
США, клиент №0005».
15. ЗАМЕСТИТЕЛЬ МЕНЕДЖЕРА ВИЦЕ-МЕНЕДЖЕРУ: «Наи- большее значение прибыли составляет 256 000 долларов США, клиент №0005».
16. ВИЦЕ-МЕНЕДЖЕР МЕНЕДЖЕРУ: «Наибольшее значение при- были составляет 256 000 долларов США, клиент №0005».
В этом подходе, показанном на рис. 6.4 (а), используется хвостовая рекурсия. Каждый сотрудник обрабатывает один файл клиента и срав- нивает вычисленное значение прибыли, полученной от этого клиента, с самым высоким значением, которое было обнаружено до сих пор. За- тем этот сотрудник передает результат сравнения подчиненному. Рекур- сия — делегирование задач — происходит после других операций обра- ботки. Процесс работы каждого сотрудника включает следующие шаги:
1. подсчет значения прибыли в одном файле клиента;
2. сравнение этого значения с самым высоким значением при- были, наблюдаемым начальством в других файлах клиентов;
3. передача оставшихся файлов клиентов подчиненному вместе с наибольшим значением прибыли, наблюдаемым до сих пор;
4. когда подчиненный сообщит самое высокое значение прибы- ли из всех файлов клиентов, требуется передать это значение началь нику.
Подход 2
При использовании этого подхода сотрудник сначала откладыва- ет один файл, а затем передает оставшиеся файлы подчиненному.
В данном случае перед подчиненным не ставится задача подсчета наибольшего значения прибыли из всех файлов, а только из тех, ко- торые были ему переданы. Как и в первой задаче, это упрощает за- просы. При использовании тех же данных, что и в первом подходе, цепочка сообщений выглядит следующим образом:
1. МЕНЕДЖЕР ВИЦЕ-МЕНЕДЖЕРУ: «Изучите эти пять файлов и сообщите мне максимальное значение прибыли».
2. ВИЦЕ-МЕНЕДЖЕР ЗАМЕСТИТЕЛЮ МЕНЕДЖЕРА: «Изучите эти четыре файла и сообщите мне максимальное значение при- были».
3. ЗАМЕСТИТЕЛЬ МЕНЕДЖЕРА ПОМОЩНИКУ МЕНЕДЖЕРА:
«Изучите эти три файла и сообщите мне максимальное значение прибыли».
4. ПОМОЩНИК МЕНЕДЖЕРА МЛАДШЕМУ МЕНЕДЖЕРУ: «Изучи- те эти два файла и сообщите мне максимальное значение прибыли».
5. МЛАДШИЙ МЕНЕДЖЕР СТАЖЕРУ: «Изучите этот файл и сооб- щите мне максимальное значение прибыли».

182 Глава 6 6. СТАЖЕР подсчитывает прибыль, полученную от клиента
№0006, которая составляет 99 000 долларов США. Это един- ственный файл, который видел СТАЖЕР, поэтому данное значе- ние прибыли является наибольшим.
7. СТАЖЕР МЛАДШЕМУ МЕНЕДЖЕРУ: «Наибольшее значение прибыли в моем файле составляет 99 000 долларов США, клиент
№0006».
8. МЛАДШИЙ МЕНЕДЖЕР подсчитывает прибыль, полученную от клиента №0005, которая составляет 256 000 долларов США.
Наибольшим из известных данному сотруднику значений явля- ется 256 000 долларов США, клиент №0005.
9. МЛАДШИЙ МЕНЕДЖЕР ПОМОЩНИКУ МЕНЕДЖЕРА: «Наи- большее значение прибыли в моих файлах составляет 256 000 долларов США, клиент №0005».
10. ПОМОЩНИК МЕНЕДЖЕРА подсчитывает прибыль, полу- ченную от клиента №0004, которая составляет 13 000 долларов
США. Наибольшим из известных данному сотруднику значений является 256 000 долларов США, клиент №0005.
11. ПОМОЩНИК МЕНЕДЖЕРА ЗАМЕСТИТЕЛЮ МЕНЕДЖЕРА:
«Наибольшее значение прибыли в моих файлах составляет 256 000 долларов США, клиент №0005».
12. ЗАМЕСТИТЕЛЬ МЕНЕДЖЕРА подсчитывает прибыль, полу- ченную от клиента №0003, которая составляет 193 000 долларов
США. Наибольшим из известных данному сотруднику значений является 256 000 долларов США, клиент №0005.
13. ЗАМЕСТИТЕЛЬ МЕНЕДЖЕРА ВИЦЕ-МЕНЕДЖЕРУ: «Наиболь- шее значение прибыли в моих файлах составляет 256 000 долла- ров США, клиент №0005».
14. ВИЦЕ-МЕНЕДЖЕР подсчитывает прибыль, полученную от кли- ента №0002, которая составляет 68 000 долларов США. Наиболь- шим из известных данному сотруднику значений является 256 000 долларов США, клиент №0005.
15. ВИЦЕ-МЕНЕДЖЕР МЕНЕДЖЕРУ: «Наибольшее значение при- были составляет 256 000 долларов США, клиент №0005».
16. МЕНЕДЖЕР подсчитывает прибыль от клиента №0001, которая составляет 172 000 долларов США. Наибольшим из известных данному сотруднику значений является 256 000 долларов США, клиент №0005.
В этом подходе, показанном на рис. 6.4 (б), используется головная рекурсия. Каждый сотрудник по-прежнему должен подсчитать значе- ние прибыли в одном файле клиента, однако это действие откладыва- ется до тех пор, пока подчиненный не определит самое высокое зна- чение в остальных файлах. Процесс работы каждого из сотрудников включает следующие этапы:

Решение задач с помощью рекурсии 183
1. передача подчиненному сотруднику всех файлов клиентов, кро- ме одного;
2. получение от подчиненного сотрудника наибольшего значения прибыли среди этих файлов;
3. определение значения прибыли в одном файле клиента;
4. передача начальнику большего из этих значений прибыли.
Как и в задаче с подсчетом количества попугаев, головная рекур- сия позволяет каждому сотруднику передать подчиненному мини- мальный объем информации.
Большая рекурсивная идея
Теперь мы подошли к Большой Рекурсивной Идее. На самом деле, если вы прочитали все этапы решения приведенных выше задач, вы уже видели БРИ в действии.
Как это? В обеих задачах используется некая форма рекурсивно- го решения. Каждый человек в коммуникационной цепочке выпол- няет одни и те же действия со все уменьшающимся подмножеством исходных данных. Однако важно отметить, что эти задачи вообще не
предусматривают никакой рекурсии.
В первой задаче каждый сотрудник железной дороги запрашивает данные у сотрудника следующей станции вниз по линии, и, выполняя этот запрос, следующий сотрудник повторяет те же шаги, что и преды- дущий. Однако ничто в формулировке запроса не требует от сотрудни- ка выполнения этих конкретных шагов. Например, когда Арт позвонил
Белинде, используя подход 2, он попросил ее подсчитать общее количе- ство попугаев от ее станции до конца линии. Он не требовал примене- ния какого-то определенного метода для вычисления этого значения.
Если бы он подумал об этом, то мог бы понять, что Белинде придется произвести те же действия, что и ему, однако ему не нужно это учиты- вать. Для решения своей задачи Арту было достаточно того, чтобы Бе- линда сообщила правильный ответ на заданный им вопрос.
Точно так же, во второй проблеме каждый сотрудник старался де- легировать подчиненному максимально возможное количество работы.
Например, помощник менеджера может хорошо знать младшего менед- жера и ожидать, что младший менеджер передаст стажеру все файлы, кроме одного. Однако у помощника менеджера нет причин задумывать- ся о том, обработает ли младший менеджер все оставшиеся файлы или передаст некоторые из них своему подчиненному. Помощник менед- жера заботится только о том, чтобы младший менеджер сообщил ему правильный ответ. Поскольку помощник менеджера не собирается по- вторять действия младшего менеджера, помощник менеджера просто предполагает, что результат, полученный от младшего менеджера явля- ется правильным, и использует эти данные для решения общей задачи, которую помощник менеджера получил от заместителя менеджера.

184 Глава 6
В обеих задачах, когда сотрудники обращаются к другим сотрудни- кам за информацией, они думают о том, что, а не о том, как. Вопрос задан; ответ получен. Таким образом, Большая Рекурсивная Идея сво- дится к следующему: если вы следуете определенным правилам в про- цессе кодирования, вы можете сделать вид, что рекурсии не происходит.
Вы даже можете использовать дешевый трюк (описан ниже), чтобы перейти от итеративной реализации к рекурсивной реализации, явно не рассматривая то, как рекурсия на самом деле решает проблему. Со временем вы выработаете интуитивное понимание того, как работа- ют рекурсивные решения, однако, пока этого не произошло, вы може- те реализовать рекурсию и быть уверенными в своем коде.
Давайте применим эту концепцию на практике с помощью при- мера кода.
: # " " # D "
& "
Напишите рекурсивную функцию, которой в качестве параметров передан массив целых чисел и размер массива. Эта функция должна возвратить сумму целых чисел в массиве.
Вашей первой мыслью, вероятно, было то, что эту проблему лег- ко можно решить итеративно. Действительно, давайте начнем с ите- ративного решения этой проблемы: int iterativeArraySum(int integers[], int size) {
int sum = 0;
for (int i = 0; i < size; i++) {
sum += integers[i];
}
return sum;
}
Вы видели код, очень похожий на этот, в главе 3, поэтому эта функция должна быть простой для понимания. Следующим шагом будет написание кода, который находится посередине между итера- ционным решением и конечным требуемым рекурсивным решени- ем. Мы оставим итеративную функцию и добавим вторую функцию, которую будем называть диспетчером. Он передаст большую часть ра- боты ранее написанной итеративной функции и использует эту ин- формацию для решения общей задачи. Чтобы написать функцию- диспетчер, мы должны следовать двум правилам.
1. Диспетчер должен быть в состоянии полностью справиться с са- мым тривиальным случаем, не вызывая итеративную функцию.
2. При вызове итеративной функции диспетчер должен передать меньшую версию задачи.
Применяя первое правило к этой задаче, мы должны решить, что собой представляет самый тривиальный случай. Если значение size равно 0, то функции концептуально передается массив «null» с суммой

Решение задач с помощью рекурсии
1   ...   18   19   20   21   22   23   24   25   ...   34
185
элементов равной 0. Можно поспорить, что самый тривиальный случай должен иметь место, когда значение size равно 1. В этом случае в логи- ческом массиве будет только одно число, мы можем вернуть это число в качестве суммы. Любая из этих интерпретаций будет работать, одна- ко выбор в пользу первого варианта позволяет функции обрабатывать специальный случай. Обратите внимание на то, что в исходной итера- тивной функции не произойдет сбой при значении size равном нулю, поэтому поддержание этой гибкости является предпочтительным.
Чтобы применить второе правило к этой задаче, мы должны найти способ передачи меньшей версии задачи от диспетчера ите- ративной функции. Нет простого способа передачи меньшего мас- сива, однако мы можем легко передать меньшее значение size. Если диспетчеру передано значение size равное 10, то от функции требу- ется вычислить сумму 10 значений в этом массиве. Если диспетчер передает итеративной функции значение size равное 9, то он запра- шивает сумму первых 9 значений в массиве. Затем диспетчер может добавить значение одного оставшегося элемента массива (10-го) для вычисления суммы всех 10 значений. Обратите внимание на то, что уменьшение размера на 1 при вызове итеративной функции макси- мизирует работу итеративной функции и тем самым минимизиру- ет работу диспетчера. Этот подход всегда является предпочтитель- ным — как менеджеры DelegateCorp, функция-диспетчер старается избежать как можно большего количества работы.
Объединив эти идеи, мы получаем следующую функцию-диспет- чер для этой задачи: int arraySumDelegate(int integers[], int size) {
X if (size == 0) return 0;
Y int lastNumber = integers[size — 1];
int allButLastSum =
ZiterativeArraySum(integers, size — 1);
[ return lastNumber + allButLastSum;
}
Первое утверждение обеспечивает соблюдение первого прави- ла диспетчеров: оно проверяет тривиальный случай и полностью его обрабатывает, в данном примере, возвращая 0
X
. В противном случае управление переходит к оставшемуся коду, который обеспе- чивает соблюдение второго правила. Последнее число в массиве хранится в локальной переменной lastNumber
Y
, а затем сумма всех остальных значений в массиве вычисляется посредством вызова итеративной функции
Z
. Этот результат сохраняется в другой ло- кальной переменной allButLastSum, и, наконец, функция возвраща- ет сумму значений двух локальных переменных
[
Если мы создали функцию-диспетчер правильно, мы уже создали рекурсивное решение. Это Большая Рекурсивная Идея в действии. Пре- вращение этого итеративного решения в рекурсивное требует лишь од- ного простого шага: нужно сделать так, чтобы функция-делегат вызыва- ла саму себя там, где она ранее вызывала итеративную функцию. Затем мы можем полностью удалить итерационную функцию.

Смотрите также файлы