Файл: Think likea programmer.pdf

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

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

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

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

Добавлен: 30.10.2023

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

Скачиваний: 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


30 Глава 1
Это довольно просто, но вы должны сделать все так, чтобы не включилась сигнализация, которая работает следующим образом.
На каждом Кратцце есть несколько кристаллических силовых гемм
Квиникрис, каждая из которых имеет форму звезды. Каждый рецеп- тор оснащен четырьмя датчиками, которые загораются в случае, если количество Квиникрис в колонне над рецептором четное. Си- рена включается, если количество загоревшихся датчиков равно од- ному. Обратите внимание, что оба рецептора оснащены отдельной сигнализацией, то есть у вас не может возникнуть ситуации, когда только один датчик горит для левого или для правого рецептора. Хо- рошая новость в том, что каждая сигнализация оснащена супрессо- ром, не позволяющим сигнализации сработать, если нажата кнопка.
Если бы вы могли нажать оба супрессора одновременно, то задача была бы легкой, но вы не можете, так как у вас лишь короткие чело- веческие руки, а не длинные щупальца, как у Кварраси.
Принимая во внимание вышеописанное, как вы передвине- те Кратцц для открытия двери, не активируя при этом одну из сигнали заций?
Начальная конфигурация приведена на рис. 1.13. В этой конфи- гурации все три Кратцца находятся в правом рецепторе. Для поясне- ния на рис. 1.14 показан пример неудачного решения: перенос само- го верхнего Кратцца в левый рецептор приводит к срабатыванию правого рецептора. Вам может показаться, что мы могли бы избе- жать срабатывания сигнализации, воспользовавшись супрессором, но помните, что мы только что переместили правый Кратцц в левый рецептор и, следовательно, находимся в трех метрах от супрессора правого рецептора.
Рис. 1.13. Начальная конфигурация для задачи замок Кварраси. Вы должны перенести три
бруска Кратцца, находящихся в данный момент в правом рецепторе, в левый, не активи-
ровав при этом сигнализацию. Датчик срабатывает, когда четное число звездообразных
Квиникрис находится в колонне над этим датчиком, при этом сигнализация срабатывает,
когда загорается один из подключенных датчиков. Супрессоры могут предотвратить сра-
батывание сигнализации, но только для того рецептора, рядом с которым вы находитесь

Стратегии решения задач 31
Рис. 1.14. Замок Кварраси в режиме сработавшей сигнализации. Вы только что передви-
нули Кратцц в левый рецептор, то есть правый рецептор для вас вне досягаемости. Второй
датчик правой сигнализации загорелся, так как в колонне над ним находится четное количе-
ство Квиникрис, сигнализация срабатывает, когда загорается один из датчиков
Прежде чем продолжать чтение, возьмите небольшую паузу, что- бы изучить задачу и попытаться найти решение. В зависимости от вашей собственной точки зрения, эта задача может оказаться не та- кой сложной, какой кажется на первый взгляд. Серьезно, подумайте над ее решением прежде, чем продолжать чтение!
Вы подумали над задачей? Смогли ли вы найти решение? Суще- ствует два пути ответа на этот вопрос. Первый путь — это путь проб и ошибок: методически пробовать передвигать различные Кратццы и возвращаться на предыдущие шаги при достижении состояния сра- батывания сигнализации до тех пор, пока не найдете работающую последовательность движений.
Второй путь — понять, что данная головоломка — лишь уловка.
Если вы не поняли, в чем уловка, то объясню: перед нами лишь зада- ча с лисицей, гусем и кукурузой в изысканной маскировке. Несмотря на то, что правила для срабатывания сигнализации описаны лишь в общем, существует только определенное количество сочетаний для каждого замка. Имея лишь три Кратцца, все, что нужно знать, — это то, какие комбинации Кратццев в рецепторе считаются допустимы- ми. Если мы обозначим три Кратцца как верхний, средний и нижний, то получим следующие комбинации, вызывающие срабатывание сиг- нализации, это «верхний и средний» и «средний и нижний». Если мы переименуем верхний в лисицу, средний в гуся, а нижний — в кукурузу, то комбинации, вызывающие трудности в этой задаче аналогичны комбинациям во второй: «лисица и гусь» и «гусь и кукуруза».
Таким образом, эта задача решается так же, как и задача с ли- сицей, гусем и кукурузой. Нам нужно передвинуть средний Кратцц
(гусь) в левый рецептор, после этого передвинуть влево верхний
Кратцц (лисица), удерживая при этом нажатой кнопку супрессора.

32 Глава 1
Далее мы начнем передвижение среднего Кратцца (гусь) обратно в правый рецептор. Затем мы перенесем нижний Кратцц (кукуруза) влево и, наконец, снова перенесем средний Кратцц (гусь) влево, от- крыв замок.
Вынесенные уроки
Главный урок здесь — это важность умения распознать аналогии.
В данном примере продемонстрировано, что проблема замка Квар- раси аналогична задаче с лисицей, гусем и кукурузой. Если мы смо- жем как можно раньше распознать аналогию, то сможем и избежать значительной части работы, просто взяв решение первой задачи, вместо создания нового. Большинство случаев сходства в решении задач не будут столь же прямыми, но по мере применения вы будете замечать это чаще и чаще.
Если вам было сложно увидеть связь между этой задачей и зада- чей с лисицей, гусем и кукурузой, это лишь потому, что я специаль- но включил настолько большое количество пространных деталей, насколько это было возможно. История, включенная в постановку задачи Кварраси, не имеет отношения к ее решению, точно также все наименования инопланетных технологий нужны для увеличения чувства нахождения в незнакомой обстановке. Более того, механизм с четным/нечетным количеством брусков делает задачу на первый взгляд более сложной, чем она есть. Если вы посмотрите на положе- ние Квиникрис, то вы увидите, что верхний Кратцц противополо- жен нижнему, поэтому они не могут взаимодействовать в сигнальной системе. Однако средний Кратцц взаимодействует с оставшимися двумя Кратццами.
Повторимся, если вы не разглядели аналогию, не переживайте.
Вы начнете распознавать их эффективнее, если будете знать об их существовании.
Общие подходы к решению задач
Приведенные выше примеры демонстрируют множество важных подходов, применяемых при решении задач. В оставшейся части книги вы будете изучать конкретные проблемы программирования и искать способы их решения, но для начала нужно составить общий список подходов и методов. Как вы убедитесь позднее, в некоторых областях существуют специфические подходы, но правила ниже мо- гут применяться практически в любой ситуации. Если вы сделаете их неотъемлемой частью вашего подхода к решению задач, ни одна проблема не поставит вас в тупик.
Планируйте решения
Это, вероятно, самое важное правило. У вас всегда должен быть план. Не стоит заниматься бессмысленной деятельностью.

Стратегии решения задач 33
К этому моменту вы, должно быть, поняли, что всегда можно со- ставить план. Правда в том, что если вы не решили задачу мыслен- но, то у вас не может быть плана по реализации решения в виде про- граммного кода. Это придет позже. Однако даже в самом начале у вас должен быть план, как вы будете искать решение.
Честно говоря, по ходу решения той или иной задачи план мо- жет потребоваться изменить или вообще отказаться от него в поль- зу нового плана. Тогда почему же это правило так важно? Генерал
Дуайт Эйзенхауэр известен своей фразой: «Я всегда убеждался, что планы бесполезны, но без планирования не обойтись». Он имел в виду, что сражения настолько хаотичны, что невозможно предска- зать все, что может произойти, или иметь вариант для любой ситуа- ции. В этом смысле планы бесполезны на поле сражения (известная фраза прусского полководца Гельмута фон Мольтке гласит: «Ни один план не выживает после первого контакта с врагом»). Но никакая армия не может одержать победу без планирования и организации.
Благодаря планированию генерал узнает возможности армии, как взаимодействуют различные армейские подразделения и так далее.
Точно так же у вас всегда должен быть план решения задачи. Он может и не выжить после первого контакта с врагом, вы можете от- казаться от него, как только начнете писать код в редакторе, но план у вас быть должен.
Без плана вы просто хватаетесь за соломинку в надежде пре- успеть, но ваши шансы на удачу близки к шансам обезьянки напи- сать пьесу Шекспира, беспорядочно нажимая клавиши на клавиа- туре. Счастливые случайности редки, а если такая случайность все же происходит, то ей все равно потребуется план. Многие слыша- ли историю о том, как был открыт пенициллин: исследователь по имени Александр Флеминг забыл прикрыть на ночь чашку Петри, используемую для культивирования бактерий, а на утро обнаружил, что плесень замедлила рост бактерий в чашке. Однако Флеминг не сидел в праздном ожидании счастливой случайности, он ставил экс- перименты, делал это тщательным и контролируемым образом и поэтому смог распознать важность того, что увидел в чашке Петри.
Должен заметить: если бы я обнаружил плесень на чем-то, что оста- вил неприкрытым на ночь, это явно не привело бы к важному науч- ному открытию.
Планирование также позволяет вам устанавливать промежуточ- ные цели и достигать их. Без плана у вас лишь одна цель: решить задачу. И до того, как вы решите эту задачу, вы не будете чувство- вать, что достигли чего-то. Возможно, как вы уже убедились на сво- ем опыте, программы редко делают что-то полезное, пока не будут близки к завершению процесса создания. Таким образом, работа на достижение только основной цели неизбежно ведет к разочарова- нию, и вы не получите удовлетворения до тех пор, пока не дойдете до конца. Однако если вместо этого вы создадите план, в котором

34 Глава 1
установите несколько последовательных меньших целей, даже если некоторые из них кажутся напрямую не связанными с основной це- лью, вы все равно будете измеримо продвигаться к решению задачи и чувствовать, что потратили время не зря. По окончании каждой рабочей сессии вы сможете проверить элементы плана и обрести уверенность, что сможете решить задачу, а не получить еще больше разочарований.
Переформулируйте задачи
Как показал пример задачи с лисицей, гусем и кукурузой, переформу- лирование условий может привести к ценным результатам. В неко- торых случаях задача, которая выглядит сложной, может оказаться очень простой при иной постановке или при использовании других определений. Переформулирование задачи похоже на то, как вы об- ходите гору, перед тем как взойти на нее. Прежде чем начать подъ- ем, почему бы не рассмотреть склон со всех сторон в поиске самого легкого пути к вершине?
Переформулирование иногда показывает, что цель — это совсем не то, что мы изначально предполагали. Однажды я прочитал исто- рию про бабушку, которая следила за внучкой, занимаясь при этом вя- занием. Чтобы успеть довязать, бабушка посадила внучку в перенос- ной манеж, но ребенку не нравилось сидеть в манеже, и девочка все время плакала. Бабушка перепробовала все возможные игрушки, что- бы сделать времяпрепровождение в манеже веселым, пока не поняла, что посадить ребенка в манеж было ошибкой изначально. Цель состо- яла в том, чтобы бабушка могла вязать в тишине. Решение: дать ре- бенку спокойно играть на ковре, пока бабушка вяжет, сидя в манеже.
Переформулирование задачи — это мощный прием, но многие про- граммисты не пользуются им, так как он не подразумевает непосред- ственно написание кода или хотя бы разработку решения. Это еще одна причина, почему просто необходимо иметь план. Без плана ваша единственная цель — получить работающий код, а переформулирова- ние задачи отводит вас дальше от написания кода. Имея план, вы мо- жете сделать «формальную переустановку задачи» первым пунк том.
Даже если переформулирование не приводит к очевидному ноу- хау, оно все равно может быть полезным. Например, если ваш босс или преподаватель поставил вам задачу, вы можете показать пере- фразированную версию человеку, который вам ее поставил, чтобы убедиться в правильном понимании проблемы. Кроме того, пере- формулирование задачи может быть необходимым предваритель- ным шагом при использовании других общих техник, таких как уменьшение и разделение задачи.
В более широком смысле переформулирование может транс- формировать все проблемные участки. Так, техника, которую я ис- пользую для рекурсивных решений и которой поделюсь в одной из глав, представляет собой метод переформулирования рекурсивных

Стратегии решения задач
1   2   3   4   5   6   7   8   9   ...   34

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