Файл: Think likea programmer.pdf

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

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

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

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

Добавлен: 30.10.2023

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

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

произошел от строго процедурного языка С, код на C++ может быть написан с использованием как процедурной, так и объектно ориен- тированной парадигмы. Объектно ориентированное программиро- вание применяется сегодня настолько повсеместно, что не может быть исключено из обсуждения решения задач. Однако многие фун- даментальные подходы к решению задач могут быть реализованы в строго процедурной парадигме, что упрощает как написание, так и изменение кода. В-третьих, будучи низкоуровневым языком с высо- коуровневыми библиотеками, С++ позволяет мне обсудить оба уров- ня программирования. При необходимости лучшие программисты могут объединять низкоуровневые части с высокоуровневыми биб- лиотеками и компонентами для сокращения времени разработки.
Наконец, С++ — это отличный выбор, так как, научившись решать за- дачи на этом языке, вы сможете в принципе решать задачи на любом другом языке программирования. Изучение одного языка програм- мирования облегчает последующее изучение других. Это особенно характерно для языка C++, так как он довольно сложен и основан на двух парадигмах одновременно. Возможно, это может вас испугать.
Но преуспев в C++, в сможете не просто писать программы — вы по- настоящему станете программистом.

16 Глава 1
16
Эта книга посвящена решению задач, но что это значит на самом деле? Когда люди используют этот термин в разговоре, они зачастую име- ют в виду нечто очень отличное от того, о чем я говорю в этой книге.
Если из выхлопной трубы вашего старого автомобиля идет сизый дым, двигатель то и дело глохнет, а расход топлива вырос, то эта проблема, как задача, может быть ре- шена с применением знаний автомобиля, диагностикой и заменой деталей при помощи инструментов автомеханика. Впрочем, если вы расскажете о своей проблеме друзьям, то один из них может вам ответить: «Эй, ты должен заменить свою старую машину на что-то поновее, и проблема будет решена». Однако предложение вашего друга на самом деле не будет решением задачи: это будет лишь спосо- бом ее избежать.

1

Стратегии решения задач 17
Задачи подразумевают ограничения, незыблемые правила, ка- сающиеся задачи или способа ее решения. В случае со сломанной машиной одно из ограничений заключается в том, что вам нужно отремонтировать имеющийся автомобиль, а не купить новый. Огра- ничения также должны подразумевать общую стоимость ремонта, время на ремонт и невозможность приобретения инструмента для ремонта только этой поломки.
При решении проблемы в программе у вас также есть опреде- ленные ограничения. Среди общих ограничений язык программи- рования, платформа (будет ли программа работать на ПК, iPhone или ином устройстве?), производительность (для игровой програм- мы может требоваться обновление графики до 30 кадров в секунду, бизнес-приложение должно иметь ограничение по максимальному времени отклика на ввод пользователя) или объем требуемой памя- ти. Иногда ограничения также подразумевают код, на который вы можете ссылаться: возможно, программа не может включать опреде- ленный открытый код или, наоборот, должна использовать только открытый код.
Таким образом, термин решение задач для программистов я могу определить как написание оригинальной программы, выполняю- щей определенный набор заданий и соответствующей всем установ- ленным ограничениям.
Начинающие программисты зачастую так хотят выполнить пер- вую часть определения — написать программу, выполняющую опре- деленное задание — что забывают про выполнение второй части определения — соответствовать установленным ограничениям. Я на- зываю такую программу, выдающую правильный результат, но нару- шающую одно или несколько заявленных правил, «Кобаяси Мару ».
Если это название вам незнакомо, значит вы не смотрели культовый в узких кругах кинофильм «Звездный Путь 2: Ярость Хана». В этом фильме есть сюжетная линия про тест для начинающих офицеров
Академии Звездного флота. Кадетов помещают на мостик симулято- ра звездного корабля или поручают роль капитана, выполняющего миссию, в ходе которой они встречаются с невозможным выбором.
Гибель грозит людям на подбитом корабле «Кобаяси Мару», однако, чтобы добраться до них, вам нужно пойти на самоубийственное сра- жение с врагами. Цель этого упражнения — проверить смелость и отвагу кадета, когда он находится под огнем. В данном сражении по- бедить невозможно, и любой выбор ведет к провалу. Ближе к концу фильма мы обнаруживаем, что капитан Кирк модифицировал симу- лятор, сделав победу возможной. Кирк был хитер, но он не решил дилемму «Кобаяси Мару», а лишь избежал ее.
К счастью, задачи, с которыми вы столкнетесь как программист, разрешимы, но многие программисты все еще прибегают к подхо- ду Кирка. В некоторых случаях они делают это случайно. («О, черт!
Мое решение работает только в том случае, если элементов данных

1   2   3   4   5   6   7   8   9   ...   34
18 Глава 1
сто или меньше. Оно должен работать для неограниченного набора данных. Мне придется переосмыслить это решение».) В других слу- чаях ограничения изменяют преднамеренно, прибегая к этому как к уловке, чтобы успеть к сроку, установленному начальником или пре- подавателем. В других случаях программист просто не знает, как со- ответствовать всем ограничениям. В худших случаях, которые я ви- дел, студенты-программисты платили третьим лицам за написание программы. Независимо от мотивов, мы всегда должны проявлять максимум усердия во избежание «Кобаяси Мару».
Классические головоломки
По мере чтения книги вы заметите, что, несмотря на изменение частностей исходного кода от одной проблемной области к другой, некоторые схемы в моих подходах останутся неизменными. И это хорошо, потому что в конце концов позволит нам уверенно подхо- дить к решению любой задачи, вне зависимости от того, есть ли у вас большой опыт в той или иной проблемной области. Эксперты в решении задач могут быстро распознать аналогию, т. е. пригодное для использования сходство между решенной и нерешенной зада- чей. Если мы распознаем, что некое свойство задачи А аналогично некоему свойству задачи Б, при условии, что мы уже решили задачу
Б, у нас будет очень ценная наработка для решения задачи А.
В этом разделе мы обсудим классические задачи не из мира про- граммирования, из которых мы можем вынести уроки, применимые при решении задач по программированию.
Лисица, гусь и кукуруза
Первая классическая задача, которую мы обсудим, — это загадка про крестьянина, которому нужно пересечь реку. Возможно, вы уже встречались с этой задачей в той или иной форме.
: ?
Крестьянин с лисицей, гусем и мешком кукурузы должен пересечь реку. У крестьянина есть лодка, однако в ней есть место только для самого крестьянина и одного из пере- численных объектов. К сожалению, и лисица, и гусь голодны. Лисица не может быть оставлена наедине с гусем, так как она съест гуся. Точно так же гусь не может остаться наедине с мешком кукурузы, иначе он склюет кукурузу. Как крестьянину перевезти животных и кукурузу через реку?
Условие задачи проиллюстрировано на рис. 1.1. Если вы никогда ранее не встречались с этой задачей, сделайте небольшую паузу и по- тратьте несколько минут на попытки решить ее. Если же вы слыша- ли эту загадку ранее, попытайтесь вспомнить решение и нашли ли вы его самостоятельно.


Стратегии решения задач 19
Рис. 1.1. Лисица, гусь и мешок кукурузы. Лодка может перевезти только один объект за раз.
Лисицу нельзя оставить на одном берегу с гусем, точно так же, как и гуся нельзя оставлять
на одном берегу с мешком кукурузы
Очень немногие могут решить эту загадку, по крайней мере без подсказки. Я тоже не смог. Вот как обычно идет рассуждение: по- скольку крестьянин может брать в лодку только один из объектов за раз, ему потребуется несколько поездок, чтобы перевезти все на дальний берег. Если крестьянин возьмет в первую поездке лисицу, то гусь останется с мешком с кукурузы — и склюет кукурузу. Точно так же, если бы крестьянин взял мешок с кукурузой в первую поездку, а лисица осталась бы в компании с гусем, то лисица съела бы гуся. Та- ким образом, крестьянин должен взять гуся в первую поездку, в ре- зультате чего получится конфигурация, показанная на рис. 1.2.
Рис. 1.2. Необходимый первый шаг решения задачи с лисицей, гусем и мешком кукурузы.
Однако складывается ощущение, что все последующие шаги обречены на провал
Пока что все идет нормально. Но во вторую поездку крестьянин должен взять лисицу или кукурузу. Однако, что бы крестьянин ни взял, этот объект должен быть оставлен на дальнем берегу с гусем, на то время, пока крестьянин возвращается к ближнему берегу за остав- шимся объектом. Это означает, что лиса и гусь останутся наедине

20 Глава 1
или что гусь и кукуруза будут оставлены вместе. Поскольку ни одна из этих ситуаций не приемлема, проблема кажется неразрешимой.
Повторимся, если вы уже встречали эту задачу, то, возможно, вы помните ключевой элемент решения. Как было объяснено выше, крестьянин должен взять в первую поездку гуся. Давайте предло- жим, что во вторую поездку крестьянин берет с собой лисицу. Одна- ко вместо того, чтобы оставить гуся с лисицей, крестьянин отво зит
гуся обратно на ближний берег. Затем крестьянин перевозит через реку мешок кукурузы, оставляя на дальнем берегу лисицу с кукурузой, и возвращается туда в четвертую поездку с гусем. Полное решение за- дачи показано на рис. 1.3.
Рис. 1.3. Пошаговое решение головоломки с лисицей, гусем и кукурузой
Эта задача сложна потому, что большинство людей не рассматри- вает возможность перевезти один из элементов обратно с дальнего берега на ближний. Некоторые могут посчитать загадку нечестной и сказать что-то наподобие: «Вы не говорили, что я могу перевезти что-то обратно!» Это правда, впрочем, как правда и то, что ничего в

Стратегии решения задач 21
описании задачи не указывает на то, что перевозить объекты обрат- но запрещено.
Представьте, насколько проще было бы решить эту головоломку, если бы возможность перевезти один из объектов обратно на ближ- ний берег была бы указана явно: У крестьянина есть лодка, которую он
может использовать для перевозки объектов в обоих направлениях, но в
лодке есть место только для самого крестьянина и одного из трех объектов.
Теперь, когда эта подсказка видна невооруженным глазом, большее количество людей смогут решить задачу. Это позволяет проиллюстри- ровать важный принцип решения задач: если вам не известны все дей- ствия, которые вы можете предпринять, то, возможно, вы не сможете решить задачу. Мы можем называть эти действия операциями. Создав список всех возможных операций, мы сможем решить любую задачу, проверяя все возможные сочетания операций до тех пор, пока одно из этих сочетаний не решит задачу. В общем, переформулирование задачи более формальным языком позволяет нам открыть решения, которые ускользнули бы от нас в противном случае.
Давайте забудем, что мы уже знаем решение, и попытаемся более формально поставить условие данной конкретной задачи. В первую очередь, перечислим основные ограничения:
1. Крестьянин может взять в лодку только один объект за раз.
2. Лисицу нельзя оставить вместе с гусем.
3. Гуся нельзя оставить вместе с кукурузой.
Эта задача — хороший пример важности ограничений. Если мы уберем одно из вышеприведенных ограничений, то головоломка ста- новится простой. Убрав первое ограничение, мы сможем запросто перевезти все три объекта через реку за одну поездку. Даже если мы можем взять только два объекта, то мы можем взять лисицу и кукуру- зу и перевезти их через реку, а затем вернуться за гусем. Убрав второе ограничение (но оставив в силе все прочие), то, нам нужно лишь быть внимательными и сначала взять гуся, затем переправить лисицу и, на- конец, вернуться за кукурузой. Таким образом, если мы забудем или проигнорируем ограничения, то получим «Кобаяси Мару».
Теперь давайте перечислим все операции. Существует несколько способов формулировки операций этой головоломки. Мы могли бы составить список конкретных действий, которые, как нам кажется, мы можем предпринять.
1. Операция: Перевезти лисицу на дальний берег реки.
2. Операция: Перевезти гуся на дальний берег реки.
3. Операция: Перевезти кукурузу на дальний берег реки.
Помните, что цель формальной переустановки задачи — получение некоего аналитического вывода для решения. Если мы раньше не реша- ли эту задачу и не находили возможную «скрытую» операцию, такую как перевозка гуся обратно на ближний берег, мы не сможем найти эту опе-

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