Структуры данных и алгоритмы, страница 10

Читатель может проследить применение приведенныхрекомендаций при разработке программ в этой книге, а также может проверить ихдейственность в собственной практике программирования.1.2.3.Планируйте этапы, разработки программы. Мы описывали в разделе 1.1 этапыразработки программы: сначала черновой набросок алгоритма в неформальномстиле, затем псевдопрограмма, далее — последовательная формализация псевдопрограммы, т.е.

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

Один из неэффективных подходов к процессу программирования заключается в том, что каждый новый проект рассматривается "с нуля", без учета уже существующих про-1.6. ПРАКТИКА ПРОГРАММИРОВАНИЯ37грамм. Обычно среди программ, реализованных на момент начала проекта, можно найти такие, которые если решают не всю исходную задачу, то хотя бы еечасть.

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

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

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

В качестве примера рассмотрим программу spell, написанную Джонсоном (S.C. Johnson) с использованием команд UNIX . На вход этой программы поступает файл /1, состоящий из текста на английском языке, на выходе получаем всеслова из / lt не совпадающие со словами из небольшого словаря2.

Эта программа воспринимает имена и правильно написанные слова, которых нет в словаре, как орфографические ошибки. Но обычно выходной список ошибок достаточно короткий, поэтому его можно быстро пробежать глазами и определить, какие слова в нем не являются ошибками.Первый фильтр, используемый программой spell, — это команда translate, которая имеет соответствующие параметры и заменяет прописные буквы на строчные,пробелы — на начало новых строк, а остальные символы оставляет без изменений.На выходе этой команды мы получаем файл f2, состоящий из тех же сле^в, что ифайл /1, но каждое слово расположено в отдельной строке. Далее выполняется команда sort, упорядочивающая строки входного файла в алфавитном порядке.

Результатом выполнения этой команды является файл f3, содержащий отсортированныйсписок (возможно, с повторениями) слов из файла /2- Затем команда unique удаляет1UNIX — торговая марка Bell Laboratories.Мы могли бы использовать полный словарь, но многие орфографические ошибки совпадают со словами, которые почти никогда не применяются.238ГЛАВА 1. ПОСТРОЕНИЕ И АНАЛИЗ АЛГОРИТМОВ•Xповторяющиеся строки в своем входном файле f3, создавая выходной файл f4, содержащий слова из исходного файла (без прописных букв и повторений), упорядоченныев алфавитном порядке.

Наконец, к файлу /4 применяется команда diff, имеющая параметр, который указывает на файл /5. содержащий в алфавитном порядке слова изсловаря, расположенные по одному в строке. Результатом этой команды будет списокслов из файла /4» которые не совпадают со словами из файла /5. т.е. те слова из исходного списка, которых нет в словаре. Программа spell состоит из следующей последовательности команд:spell:translate [A-Z] -» [a-z], пробел —» новая строкаsortuniquediff словарьКомандный уровень программирования требует дисциплины от команды программистов. Они должны писать программы как фильтры везде, где это возможно, исоздавать программы-инструменты вместо узкоспециализированных программ всегда, когда для этого есть условия.

Существенным вознаграждением за это будет значительное повышение вашего коэффициента отношения результата к затраченнымусилиям. П1.7. Расширение языка PascalБольшинство программ в этой книге написаны на языке Pascal. Чтобы сделатьлистинги программ более читабельными, мы иногда будем применять три конструкции, которые вы не найдете в стандартном Pascal, но которые легко трансформируются в операторы языка Pascal. Одна из таких конструкций — нечисловые метки.Если в программе необходимо использовать несколько меток, то нечисловые меткизначительно облегчат понимание программы.

Например, оператор goto выход, очевидно, более понятен, чем goto 561. Для преобразования программы с нечисловымиметками в "чистую" программу Pascal, надо заменить все нечисловые метки различными числами и затем объявить их метками (label) в начале программы. Этот процесс можно полностью автоматизировать.Другой нестандартной конструкцией является оператор возврата return, которыйпозволяет писать более понятные программы без использования операторов goto.Оператор возврата будем использовать в следующей форме: ге1игп(выражение), гдескобка (выражение) необязательна. Преобразовать процедуру с операторами возвратав стандартную программу Pascal очень просто. Сначала надо объявить новую метку,скажем 999, и затем поместить ее на последний оператор end процедуры.

Например,оператор return(x) в некой функции zap заменяется следующим блоком:beginzap: = x;goto 999endОператор return, не имеющий аргументов, просто заменяется на оператор goto 999.Пример 1.12. В листинге 1.6 представлена программа, вычисляющая факториал,в которой использованы операторы возврата. В листинге 1.7 показана та же программа после замены операторов return стандартными операторами Pascal.

DЛистинг 1.6. Программа вычисления факториала с операторами возвратаfunction fact ( n: integer ) : integer;beginif n <= 1 then: ,'1.7. РАСШИРЕНИЕ ЯЗЫКА PASCAL.:••'•'.•-"••'•.i.'.-i.- • • , . .39return(1)elsereturnfn * fact(n - 1))end; { fact }Листинг 1.7. Программа вычисления факториала на языке Pascal•; ; - /:.,:"„.

",:,..,. ,,.., •• •::<:•:ГГfunction fact ( n: integer ): integer;label999;beginif n <= 1 thenbeginfact:= 1;goto 999endelsebeginfact:= n * fact(n - 1);goto 999endqqqУУ? .,end; { fact }Третье расширение языка Pascal, которое мы будем применять, заключается в постоянном использовании выражений, описывающих типы, в качестве имен типов. Например, выражения, подобные Т celltype, мы считаем допустимыми в качестве имен типов,но недопустимыми для типов параметров процедур или значений, возвращаемых функциями. Технически Pascal требует, чтобы мы использовали имена для типов данных, например prtocell (указатель на ячейку). В этой книге мы будем допускать такие описывающие выражения в качестве имен типов, надеясь, что читатель сможет придумать имядля типа данных и механически заменить описывающее тип выражение именем типа.1Другими словами, мы будем использовать операторы, подобныеfunction zap( A: array[1..10] of integer ) : t celltypeподразумевая под этим следующий оператор (здесь arrayofinteger обозначает "массивцелых чисел"):function zap( A: arrayofinteger ): prtocell,Наконец, замечание о применяемых нами соглашениях в отношении листинговпрограмм.