Давыдов В.Г. - Программирование и основы алгоритмизации - 2003

уменьшения случайных ошибок, этот способ позволяет экономить память при передаче сложных объектов. Исключение составляют параметры, размер которых меньше размера указателя - их лучше передавать по значению.

Нельзя возвращать из функции ссылку на локальную пере­ менную, потому что она автоматически уничтожается при выходе из функции, которая является ее областью действия. Не рекомендуется также возвращать ссылку на объект, созданный внутри функции с помощью функции malloc{ ) или операции new, так как это приводит к трудно контролируемым утечкам динамической памяти.

Следует избегать использования в программе чисел в явном виде. Константы должны иметь осмысленные имена, заданные через const или епит (последнее предпочтительнее, так как память под перечисление не выделяется). Символическое имя делает программу более понятной. Кроме того, при необходимости изменить значение константы это можно сделать всего лишь в одном месте программы.

Для записи каждого фрагмента программы необходимо ис­ пользовать наиболее подходящие языковые средства. Любой цикл можно, в принципе, реализовать с помощью операторов if и goto, но это было бы нелепо, поскольку с помощью операторов цикла те же действия легче читаются, а компилятор генерирует более эффектив­ ный код. Ветвление на три или более направлений предпочтитель­ нее программировать с использованием оператора switch, а не с по­ мощью гнезда операторов if.

Следует избегать лишних проверок условий. Например, вме­ сто операторов

±f(	strstr(	a,b	) >	О )	{ . . .	}
else	±f(	strstr(	a,b	)	< 0 )	{ . . .	;
else	( . . . }

лучше записать

±nt			ls_equal		= strstr	( a,b ) ;
±f(	is_equal	>	0 )	{ . . .	}
else	±f( is_equal		<	0 )	{ . . .	}
else	{ . . .	}

Бессмысленно использовать проверку на неравенство нулю

(или, что еще хуже, на равенство true

или

false):

bool

is_busy;

±f(

is_busy

==

true

)

{

}

//

Лучше

±f(

is_busy

)

{

}

±f(

is_busy

==

false

)

{

}

//

Лучше

±f(

!is_busy

)

{

}

while

( a ==

0 )

{

}

//

Лучше

while

( !a )

{

}

210

Если одна из ветвей условного оператора короче, чем другая,

то более	короткую	ветвь	условного	оператора	лучше поместить
сверху,	иначе вся управляющая структура может не поместиться на
экране, что затруднит отладку.
В некоторых случаях тернарная операция лучше условного
оператора:
if( Z )	2.-J; else	i=k;	//	i = z ? j	: k;

При	использовании			циклов		надо стремиться			объединять
инициализацию^			проверку условия			повторения		и	приращение в
одном месте.		Сказанное означает, что лучше использовать цикл/or.
Необходимо			проверять		коды	возврата	для	выявления		оши­
бок и предусматривать				печать		сообщений	в тех		точках	про­
граммы, куда		управление		при	нормальной работе			программы		пе­
редаваться	не доллсно.			Например, в переключателе должен исполь­
зоваться вариант default				с обработкой ситуации по умолчанию, осо­

бенно, если в переключателе перечислены все возможные варианты.

Сообщение об ошибке дол:н€но быть информативным и под­ сказывать пользователю, как ее исправить. Например, при вводе не­ верного значения в сообщении должен быть указан допустимый

диапазон.
Операции выделения	и освобо^исдения динамической памяти
следует помещать в одну	и ту Jtce функцию. Утечки памяти, когда

ее выделили, а освободить забыли, создают большие проблемы в программах, продолжительность работы которых велика или не ог­ раничена (на серверах баз данных, в операционных системах и т.п.

программах).
После написания программу надо тщательно	отредакти­

ровать — убрать ненужные фрагменты, сгруппировать описания, оп­ тимизировать проверки условий и циклы, проверить, оптимальное ли разбиение на функции и т.п. Подходить к написанию программы надо так, чтобы ее в любой момент можно было передать другому программисту.

Комментарии имеют очень важное значение, поскольку

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

По использованию комментариев и использованию форма­ тирования текста мо:>§€но дать следующие рекомендации (они

иллюстрируются многочисленными примерами исходных текстов программ, приведенными в этой книге).

•Программа, если она используется, живет не один год, по-

211

требность в каких-то ее новых свойствах появляется сразу же после ввода программы в эксплуатацию и сопровождение программы за­ нимает гораздо больше времени, чем ее разработка. По этой причи­ не основная часть документации долэюна находиться в тексте про­ граммы. Хорошие комментарии написать почти так же сложно, как

ихорошую программу.

аКомментарии долэюны представлять собой правильные предложения без сокращений и со знаками препинания и не должны подтверждать очевидное. В данной книге иногда есть отступы от этого в учебных целях.

аЕсли комментарий к фрагменту программы занимает не­

сколько	строк, его лучиге разместить				до фрагмента,		чем справа от
него, и	выровнять по вертикали.			Абзацный		отступ	комментария
долэюен соответствовать			отступу		комментируемого		блока.
•	Для	разделения	функций	и	других	логически	законченных
фрагментов		пользуйтесь пустыми строками и комментариями вида:

//* ii^ic-kic*i(i<irk*i(iciri(:*iricici(*i(**i^ic-kic*icif9c*i(-k^ic**ic-kiricici<*-k-^iri(i(icici^*ic*if*

•Вложенные блоки долэюны иметь отступ в 3 - 4 символа

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

•Помечайте комментарием конец длинного составного опе­

ратора.

•	Не следует размещать в одной строке много		операторов.
и	В комментариях	после знаков препинания	используйте

пробелы.

Настоятельно рекомендуем внимательно рассмотреть приве­ денные в книге программные тексты, обратив внимание на оформ­ ление комментариев и форматирование текста. Это будет способст­ вовать формированию хорошего стиля программирования.

13.2. Проектирование и тестирование программы [5]

Вначале рассмотрим, как не следует проектировать и тестиро­ вать программы. Начинающие программисты, особенно студенты, часто, получив задание, сразу садятся за компьютер и начинают ко­ дировать те части алгоритма, которые им удается придумать сходу. Объектам программы даются первые попавшиеся имена и т.п. Когда компьютер "зависает" или получаются "загадочные" результаты, по-

212

еле некоторого перерыва написанные фрагменты стираются и все повторяется заново.

В процессе работы неоднократно изменяются структуры дан­ ных, разбиение на модули (функции) делается только тогда, когда просматривать текст программы становится неудобно и утомитель­ но. При этом комментарии к программе не пишутся, а ее текст не форматируется. Из-за многочисленных неудач периодически выска­ зываются сомнения в правильности работы компилятора, компьюте­ ра и операционной системы.

Когда программа впервые доходит до стадии выполнения (а это случается не скоро), в нее вводятся произвольные исходные данные, после чего экран компьютера и файл результатов становят­ ся объектами пристального удивленного изучения. "Работает" такая программа обычно только на одном наборе исходных данных, а вне­ сение в них даже небольших изменений приводит автора к потере веры в себя и портит его настроение.

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

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

Рассмотрим этапы создания программ, рассчитанные на дос­ таточно большие программные проекты, разрабатываемые коллек­

тивом программистов	[5]. Для неболыиих	программ каждый	из та­
ких этапов упрощается,	но содержание	и последовательность	эта­
пов не изменяются,
13.2.1. Этап 1: постановка задачи
Создание любой программы начинается с постановки			задачи,

213

Изначально задача ставится в терминах некоторой предметной об­ ласти и необходимо перевести ее в термины, более близкие к про­ граммированию. Поскольку программист редко досконально разби­ рается в предметной области, а заказчик - в программировании, то постановка задачи может стать весьма непростым итерационным процессом. Отметим, что здесь весьма полезным является использо­

вание	объектно-ориентированного	подхода, средства реализации
которого в языке C++ будут рассмотрены во второй части книги.
	Постановка задачи заканчивается		созданием технического за­
дания,	а затем и внешней спецификации		программы, которая вклю­
чает в себя.

аОписание исходных данных и результатов (виды, представление, точность, ограничения и т.п.).

•Описание задачи, реализуемой программой,

аСпособ обращения к программе.

•Описание возможных особых и аварийных ситуаций и оши­ бок пользователя.

На этом этапе программа рассматривается как "черный ящик", для которого определена выполняемая им функция, входные и выходные данные.

13.2.2. Этап 2: разработка внутренних структур данных

Большинство алгоритмов решения задач зависит от того, ка­ ким образом организованы данные. Из этого следует, что начинать проектирование программы надо не с алгоритмов, а с разработки структур входных, промежуточных и выходных данных. При этом принимаются во внимание такие факторы, как ограничения на раз­ мер данных, необходимая точность, взаимосвязь данных между со­ бой, требования к быстродействию программы и т.п. Структуры данных могут располагаться в статической или динамической памя­ ти. В последнем случае обеспечивается более экономное использо­ вание оперативной памяти.

13.2.3.Этап 3: проектирование структуры программы

ивзаимодействия модулей

На этом этапе применяется технология нисходящего	проек­
тирования, основная идея которой заключается в разбиении	задачи

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

214

низком уровне абстракции и т.д. Очень важной на этом этапе явля­ ется спецификация интерфейсов, т.е. способов взаимодействия подзадач.

Для каждой подзадачи создается внешняя спецификация, ана­ логичная указанной для этапа 1. Здесь же решаются вопросы раз­ биения программы на модули. Декомпозиция выполняется таким образом, чтобы минимизировать взаимодействие модулей. В резуль­ тате может оказаться так, что одна задача реализуется с помощью нескольких модулей и, наоборот, в одном модуле может решаться несколько задач. На более низкий уровень проектирования перехо­ дят только после окончания проектирования верхнего уровня. Алго­ ритм записывают в обобщенной форме — например, текстуальной, в виде обобщенных блок-схем или другими способами.

На этапе проектирования следует учитывать возможность бу­ дущих модификаций программы и стремиться проектировать про­ грамму таким образом, чтобы вносить изменения было возможно проще. Процесс проектирования является итерационным, поскольку в программе реального размера трудно продумать все детали с пер­ вого раза.

13.2.4. Этап 4: структурное программирование

Процесс программирования (кодирования) также организуется по принципу "сверху вниз": вначале кодируются модули самого верхнего уровня и составляются тестовые примеры для их отладки. При этом на месте еще не написанных модулей следующего уровня ставятся "заглушки" - временные программы. "Заглушка" в про­ стейшем случае просто выдает сообщение о том, что ей передано управление, а затем возвращает его в вызывающий модуль. В других случаях "заглушка" может выдавать значения, заданные заранее или вычисленные по упрощенному алгоритму. Таким образом, сначала создается логический скелет программы, который затем обрастает "плотью" кода. Такая технология программирования получила на­ звание нисходящей технологии программирования, В литературе [5] показано, что эта технология по сравнению с восходящей техно­ логией программирования имеет целый ряд преимуществ, что и обу­ словило ее широкое распространение.

Рекомендации по записи алгоритмов в терминологии языка C++ приведены в подразд. 13.1. Ввиду важности, напомним еще раз, что главные цели — читаемость и простота структуры программы в целом и любой из составляющих ее функций.

При	программировании		следует отделять	интерфейс
(функции,	модуля,	класса) от	его реализации и	ограничивать
доступ к ненулсной		информации.	Небрежное, даже в мелочах, про-

215

граммирование может привести к огромным затратам на поиск оши­ бок на этапе отладки.

Этапы проектирования и программирования совмещены во времени: в идеале сначала проектируется и кодируется верхний уро­ вень, затем следующий за ним и т.д. Такая стратегия хороша тем, что в процессе кодирования может возникнуть необходимость врести изменения, отражающиеся на модулях нижнего уровня.

13.2.5. Этап 5: нисходящее тестирование

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

Необходимо различать процессы тестирования и отладки про­ граммы. Тестирование представляет собой процесс, посредством которого проверяется правильность функционирования программы и соответствие всем проектным спецификациям. Таким образом, тестирование носит позитивный характер. Отладка - процесс ис­ правления ошибок в программе. При отладке, в частности, исправ­ ляют ошибки, обнаруженные при тестировании. Следует заметить, что процесс обнаружения ошибок подчиняется экспоненциальному закону, т.е. большинство ошибок обнаруживается на ранних стадиях тестирования и, чем меньше в программе осталось ошибок, тем дольше придется искать каждую из них.

Для исчерпывающего тестирования программы необходимо

проверить каждую из ветвей алгоритма. Общее число ветвей оп­ ределяется числом комбинаций всех альтернатив на последователь­ ных участках алгоритма. Это конечное число, но оно может быть очень большим. Поэтому при тестировании программа разбивается на фрагменты, после исчерпывающего тестирования которых они рассматриваются как элементарные узлы более длинных ветвей. Тесты, в числе прочих возможностей, должны содержать проверку граничных условий (например, переход по условию л:>10 должен проверяться для значений 9, 10 и 11). Отдельно проверяется реакция программы на оигибочные исходные данные.

Идея нисходящего тестирования предполагает, что к тестиро­ ванию программы приступают еще до того, как завершено ее проек­ тирование и кодирование. Это позволяет раньше опробовать основ­ ные межмодульные интерфейсы, а также убедиться в том, что про­ грамма в основном удовлетворяет требованиям пользователя. Толь­ ко после того, как логическое ядро испытано настолько, что появля­ ется уверенность в правильности реализации основных интерфей-

216

сов, приступают к кодированию следующего уровня программы. Естественно, что полное тестирование программы, пока она

представлена в виде скелета, невозможно, однако добавление каж­ дого следующего уровня позволяет постепенно расширять область тестирования.

Этап комплексной отладки на уровне системы при нисходя­ щем проектировании занимает меньше времени, чем при восходя­ щем, поскольку вероятность появления серьезных ошибок, затраги­ вающих большую часть системы, гораздо ниже. Кроме того, для ка­ ждого следующего, подключаемого к системе модуля уже создано его окружение и выходные данные отлаженных модулей можно ис­ пользовать как входные для тестирования других. Но это, конечно, не значит, что модуль можно подключать к системе совсем "сырым" - бывает удобным провести часть тестирования автономно, по­ скольку сгенерировать на входе системы все варианты, необходи­ мые для тестирования отдельного модуля, трудно.

В приложении П.4 рассмотрена более подробно методика от­ ладки программы применительно к возможностям двух популярных разновидностей интегрированных сред проектирования программ.

ЧАСТЬ 2. ПРИКЛАДНОЕ ПРОГРАММИРОВАНИЕ

В число классических задач прикладного программирования

принято включать следующие задачи, составляющие золотой багаж любого программиста:

•сортировка (сортировка массивов, сортировка файлов);

•транспортная задача (задача коммивояжера);

•поиск в таблице;

•обработка списков;

•работа с очередями;

•численный анализ (вычислительная математика).

Численный анализ изучается в отдельном курсе, а остальные задачи прикладного программирования рассматриваются ниже.

Перечисленные задачи прикладного программирования рас­ сматриваются для овладения основами науки программирования и профессиональным стилем программирования. Умение решать эти и им подобные сложные задачи составляет основу профессиональной квалификации программиста.

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

14. ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ [5]

Любая программа предназначена для обработки данных. По этой причине алгоритмы обработки данных существенно зависят от способа организации данных и выбор структур данных должен предшествовать созданию алгоритмов. Стандартными способами организации данных в языках Си/С++ являются основные и состав­ ные типы. Очень часто в программах используются массивы, струк­ туры и их сочетания — структуры или массивы структур, полями ко­ торых, в свою очередь, являются массивы и структуры.

Оперативную память под данные можно выделять статически

или динамически, причем в обоих случаях выделяется		непрерывный
участок памяти. Статическое	распределение памяти	для	данных
производится при компиляции.	В этом случае требуемый		объем

218

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

ративной памяти. Динамическое размещение	данных	в памяти	про­
исходит во время выполнения программы с помощью операции			new
(только для языка С-+"Ь) или функции malloc	(языки	Си/С++).	При

этом необходимый объем требуемой памяти должен быть известен лишь к моменту динамического распределения памяти, а не до нача­ ла выполнения программы.

Как уже было сказано, если до начала работы с данными не­ возможно определить, сколько памяти потребуется для их хранения,, то память выделяется по мере необходимости отдельными блоками, связанными друг с другом с помощью указателей. Такой способ ор­ ганизации получил название динамических структур данных, по­ скольку их размер изменяется во время выполнения программы. В

качестве таких структур в программах часто используются	линейные
списки (см. разд. 8), бинарные деревья и очереди, частным	случаем
которых являются стеки. Они отличаются способами связи	отдель­

ных элементов друг с другом и допустимыми операциями. Отметим, что динамическая структура данных может занимать несмежные блоки оперативной памяти.

Динамические	структуры данных	часто	применяют и для	бо­
лее эффективной	работы с данными,	размер	которых известен.	К

такого рода случаям можно отнести решение задач сортировки и поиска элементов. При сортировке упорядочивание динамических структур не требует перестановки элементов, а сводится к измене­ нию указателей на эти элементы. Это особенно эффективно, если сортируемые элементы большого размера. При решении задачи по­ иска элемента в тех случаях, когда важна скорость, данные лучше всего представлять в виде бинарного дерева.

Элемент любой динамической структуры данных представляет собой структуру {struct), содержащую, по крайней мере, два поля - для хранения данных и для указателя (см. разд. 8). В общем случае полей данных и указателей может быть несколько. Поля данных мо­ гут быть любого типа: стандартного (основного), составного или типа указатель.

14.1. Линейные списки

Самый простой способ связать множество элементов - сделать так, чтобы каждый элемент содержал ссылку на следующий. Такой список называется однонаправленным (односвязным). Исчерпываю­ щий пример такого рода рассмотрен в разд. 8. Если добавить в каж-

219