В гл. 4 рассматриваются динамические структуры данных, т. е. такие структуры, которые изменяются во время выполнения программы. Показано, что рекурсивные структуры данных являются важным подклассом обычно используемых динамических структур. Хотя в таких случаях возможно и естественно рекурсивное определение^ его обычно на практике не применяют. Вместо этого программист получает доступ к механизму реализации путем использования явных ссылок, или указателей. Данная книга следует этому принципу, отражающему современное положение вещей; гл. 4 посвящена программированию со ссылками, а также спискам, деревьям и примерам, требующим еще более сложных совокупностей данных. В ней рассматривается процесс, который часто (и не совсем верно) называют обработкой списков . Довольно много места отведено организации деревьев, и в частности деревьев поиска. Глава заканчивается рассмотрением метода рассеянных таблиц, или хеширования , который часто предпочитают деревьям поиска. Это дает возможность сравнить два принципиально различных метода решения часто встречающейся задачи.

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

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

*) N. Wirth (Englewood Cliffs. N. J.-. Prentice-Hall. INC., 1973). [Имеется перевод: Вирт Н. Систематическое программирование. Введе ние. -м.: Мир, 1977.]

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

Разумеется, здесь возникает задача найти такую форму представления, которая может быть реализована на ЭВ.М и одновременно является достаточно машинно-независимой, чтобы здесь использоваться. Для этого не подходят ни широко употребительные языки, ни абстрактная нотация. Нужный компромисс обеспечивает язык Паскаль, который разработан специально для этой цели, поэтому и используется в данной книге. Программисты, знакомые с другими языками высокого уровня, смогут легко разобраться в программах на Паскале, так как его выражения поясняются в тексте. Но это не значит, что некоторая подготовка была бы излишней. Идеальную подготовку дает книга Систематическое программирование *>, так как она тоже основана на Паскале.

Но она не может служить учебником языка Паскаль-для этого существуют более подходящие книги *).

Настоящая книга представляет собой сжатое и переработанное изложение нескольких курсов программирования, прочитанных в Федеральном технологическом институте. (ЕТН) в Цюрихе. Многими идеями и взглядами, изложенными в этой Книге, я обязан беседам сО своими сотрудниками в ЕТН. В частности, мне хотелось бы выразить благодарность м-ру Г. Сандмейеру за внимательное прочтение рукописи и мисс Хейди Тейлер за внимание и терпение при перепечатке текста. Я хотел бы также отметить большое влияние, оказанное встречами рабочих групп 2.1 и 2.3 IFIP и особенно многочисленными беседами, которые я вел при этом с Э.Дэйк-строй и К. Хоором. Наконец, что не менее важно, ЕТН щедро предоставлял вычислительные машины, без которых была бы невозможна подготовка этой книги.

Н. Вирт

*) К. Jensen and N. Wirth, PASCAL -User Manual and Report Lecture Notes in Computer Science, Vol. 18 (Berlin, New York; Springer-Verlag, 1974). [Имеется перевод: Йеисен К., Вирт Н., Паскаль. Руководство для пользователя и описание языка. - М.: Финансы и статистика, 1982.]