Думай как программист: креативный подход к созданию кода. С++ версия [Антон Спрол] (pdf) читать постранично

ANTON SPRAUN

THINK
LIKE
A PROGRAMMER
AN INTRODUCTION TO CREATIVE PROBLEM SOLVING

АНТОН СПРОЛ

ДУМАЙ
КАК
ПРОГРАММИСТ
КРЕАТИВНЫЙ ПОДХОД К СОЗДАНИЮ КОДА

 004.4
 32.973.26-018
74

V. Anton Spraul
THINK LIKE A PROGRAMMER
Copyright 2012 by V. Anton Spraul. Title of English-language original: Think Like
a Programmer, ISBN 978-1-59327-424-5, published by No Starch Press. Russian-language
edition copyright 2018 by EKSMO Publishing House. All rights reserved.

74

,  .

 :
 
    .
C++   /   . —   :  , 2018. — 272 . —
( 
 !  " ).
#  $ %
 "
 , "  & $ , '  * !    
   . 
 "  "
 , $ &!   
  *
"    &.
    "    & ! ,  &   ! "
 
 !  !  & ! 
   . ;  , '
     C++   !       & %
  $ !.
004.4
32.973.26-018

Âñå ïðàâà çàùèùåíû. Êíèãà èëè ëþáàÿ åå ÷àñòü íå ìîæåò áûòü ñêîïèðîâàíà, âîñïðîèçâåäåíà â
ýëåêòðîííîé èëè ìåõàíè÷åñêîé ôîðìå, â âèäå ôîòîêîïèè, çàïèñè â ïàìÿòü ÝÂÌ, ðåïðîäóêöèè
èëè êàêèì-ëèáî èíûì ñïîñîáîì, à òàêæå èñïîëüçîâàíà â ëþáîé èíôîðìàöèîííîé ñèñòåìå áåç
ïîëó÷åíèÿ ðàçðåøåíèÿ îò èçäàòåëÿ. Êîïèðîâàíèå, âîñïðîèçâåäåíèå è èíîå èñïîëüçîâàíèå
êíèãè èëè åå ÷àñòè áåç ñîãëàñèÿ èçäàòåëÿ ÿâëÿåòñÿ íåçàêîííûì è âëå÷åò óãîëîâíóþ,
àäìèíèñòðàòèâíóþ è ãðàæäàíñêóþ îòâåòñòâåííîñòü.
Íàó÷íî-ïîïóëÿðíîå èçäàíèå
ÌÈÐÎÂÎÉ ÊÎÌÏÜÞÒÅÐÍÛÉ ÁÅÑÒÑÅËËÅÐ

Àíòîí Ñïðîë
ÄÓÌÀÉ ÊÀÊ ÏÐÎÃÐÀÌÌÈÑÒ
ÊÐÅÀÒÈÂÍÛÉ ÏÎÄÕÎÄ Ê ÑÎÇÄÀÍÈÞ ÊÎÄÀ
C++ ÂÅÐÑÈß
Äèðåêòîð ðåäàêöèè Å. Êàïü¸â. Îòâåòñòâåííûé ðåäàêòîð Å. Èñòîìèíà
Ìëàäøèé ðåäàêòîð Å. Ìèíèíà. Õóäîæåñòâåííûé ðåäàêòîð À. Ãóñåâ
ООО «Издательство «Эксмо»
123308, Москва, ул. Зорге, д. 1. Тел.: 8 (495) 411-68-86.
Home page: www.eksmo.ru E-mail: info@eksmo.ru
ндіруші: «ЭКСМО» А*Б Баспасы, 123308, М7скеу, Ресей, Зорге к;шесі, 1 right == NULL && root->left == NULL)
return root->data;
Z int leftMax = maxValue(root->left);
[ int rightMax = maxValue(root->right);
\ int maxNum = root->data;
if (leftMax > maxNum) maxNum = leftMax;
if (rightMax > maxNum) maxNum = rightMax;
return maxNum;
}

Обратите внимание на то, что минимальное дерево для этой задачи представляет собой единственный узел Y (хотя случай с пустым
деревом учитывается по соображениям безопасности X). Это связано с тем, что на вопрос, который мы задаем, можно дать осмысленный ответ с помощью минимум одного значения. Рассмотрим практическую проблему, когда базовым случаем является пустое дерево.
Какое значение мы могли бы вернуть? Если мы возвращаем ноль, мы
неявно требуем наличия в этом дереве нескольких положительных
значений; если все значения в дереве отрицательные, то ноль будет
ошибочно возвращен как наибольшее значение в дереве. Мы могли бы решить эту проблему, возвращая наименьшее (самое отрицательное) целое число, но в этом случае нам бы пришлось осторожно
адаптировать код для других числовых типов. Сделав базовым случаем единственный узел, мы полностью избегаем необходимости принятия этого решения.
Остальная часть кода проста. Мы используем рекурсию для нахождения максимальных значений в левом Z и правом поддере-

194

Глава 6

вьях [. Затем мы находим наибольшее из трех значений (значение
в корневом узле, наибольшее значение в левом поддереве, наибольшее значение в правом поддереве), используя вариант алгоритма
«Царь горы», который мы использовали на протяжении всей этой
книги \.

Функции-обертки
В предыдущих примерах в этой главе мы обсуждали только саму рекурсивную функцию. Однако в некоторых случаях эту рекурсивную
функцию требуется «настраивать» с помощью второй функции.
Чаще всего это происходит, когда мы пишем рекурсивные функции
внутри структур классов. Это может привести к несоответствию
между параметрами, необходимыми для рекурсивной функции, и параметрами, необходимыми для общедоступного метода класса. Поскольку классы обычно обеспечивают сокрытие информации, код
клиента класса может не иметь доступа к данным или типам, который требуется рекурсивной функции. Эта проблема и ее решение
показаны в следующем примере.
:

9
     
   "  

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

Давайте обрисуем схему того, как мог бы выглядеть этот класс,
прежде чем мы попытаемся реализовать решение этой задачи. Для
простоты мы будем включать только соответствующие части класса,
игнорируя конструкторы, деструктор и даже методы, которые позволили бы нам построить дерево, чтобы сосредоточиться на нашем
рекурсивном методе.
class binaryTree {
public:
X int leafCount();
private:
struct binaryTreeNode {
int data;
binaryTreeNode * left;
binaryTreeNode * right;
};
typedef binaryTreeNode * treePtr;
treePtr _root;
};

Обратите внимание на то, что наша функция для подсчета листьев не принимает параметров X. С точки зрения интерфейса это
корректно. Рассмотрим образец вызова для ранее построенного
объекта binaryTree bt:
Решение задач с помощью рекурсии

195

int numLeaves = bt.leafCount();

В