Правила программирования на С и С++. Главы 1-6
Страница 13. Разлагайте сложные проблемы на задачи меньшего размера


 

8. Разлагайте сложные проблемы на задачи меньшего размера.

На самом деле это также правило и литературного стиля. Если концепцию слишком сложно объяснить за один раз, то разбейте ее на меньшие части и объясняйте каждую по очереди. То же назначение у глав в книге и параграфов в главе.

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

tree t; // дерево

node = postorder_first( t ); // исходный узел

while( node ) // есть еще узлы?

node = postorder_successor( t ); // следующий узел-родитель 

 

 
« Предыдущая статья