Virt N. Algoritmy struktury dannyh = programmy (ru)(T)(410s) (522393), страница 3

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

Текст из файла (страница 3)

Идеальным приложением рекурсии служит класс алгоритмов с возвратом, но наиболее очевидно ее использование в алгоритмах, работающих с данными, структура которых определена ре. курсивно. Подобные случаи рассматриваются в двух последних главах; третья глава дает для них соответствующую подготовку. 10 Предисловие В гл. 4 рассматриваюгся динамические структуры данных, т. е. такие структуры, которые изменяются во время выполнения программьк Показано, что рекурсивные структуры данных являются важным подклассом обычно используемых динамических структур.

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

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

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

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

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

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

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

Программисты, знакомые с другими языками высокого уровня, смогут легко разобраться в программах на Паскале, так как его выражения поясняются в тексте. Но это не значит, что некоторая подготовка была бы излишней. Идеальную подготовку дает книга «Систематическое программирование» *>, так как она тоже основана на Паскале. *) Х. мт!>1Ь (Епя!«меод С1ийь !ч. Зл Ргепцсе-На!1, 1МС., 1973). 1Имсетси перевод; Вирт Н. Систематическое программирование. Введе. иие. — Ми Мир, !977,) Предисловие Но она не может служить учебником языка Паскаль — для этого существуют более подходящие книги *).

Настоящая книга представляет собой сжатое и переработанное изложение нескольких курсов программирования, прочитанных в Федеральном технологическом институте (ЕТН) в Цюрихе. Многими идеями и взглядами, изложенными в этой книге, я обязан беседам со своими сотрудниками в ЕТН. В частности, мне хотелось бы выразить благодарность м-ру Г.

Сандмейеру за внимательное прочтение рукописи и мисс Хейди Тейлер за внимание и терпение при перепечатке текста. Я хотел бы также отметить большое влияние, оказанное встречами рабочих групп 2.! и 2.3 1Р)Р и особенно многочисленными беседами, которые я вел при этом с Э, Дэйкстрой н К. Хоором. Наконец, что не менее важно, ЕТН щедро предоставлял вычислительные машины, без которых была бы невозможна подготовка этой книги. и. Вирт ) К. зепзеп апд 1Ч.

%1г)Ь, РАЗСА).— 1)зег Манна! апд йерог1 Пес1пге )Чо1ез 1п Согпрн1ег зс)енсе, Чо1. 18 (Вегнп, )Чете Уог)г; Брмпяег-Чег1ан, 1974). (Имеется перевод: г)енсен К, Вирт Н., Паскаль. Руководства для пользователя и описание языка. — Мл Финансы и статистика, !982.) Наш высокочтимый г, Л. Эйлер делает нач в назидание следующее заявление. Он откровенно признает. И!. что, являясь королем математиков, он все же вечно будет ираснеть за вызов здравому смыслу и повседневному опыту, брошенный выводом ивето формулы, согласно которой тело под действием силы притяжения к центру сферы внезапно изменит направление движения к центру; 1т'. что он сделает все возможное, чтобы больше ие изменять разуму, доверяясь ошибочной формуле.

Он иа коленях молит правления за то, что кэх-то, имея в виду парадоксальный результат, он заявил: кВычислениям следует доверять больше, чем чувствам, лаже если кажется, что это противоречит действительностнтч 'т'. что впредь он никогда больше яе станет делзть вычисления на шестидесяти страницах лля получения результата, который по здравом размышления можно вывести в десяти строках; и если он когда-нибудь вновь соберется, засучив рукава, считать три дни н три ночи подряд, то он прежде потратит четверть часа на раздумья о том, какие методы вычисления для этого наиболее подходящн Вольтер, Паифлет доктора Акикия, яоябрь 17Ы е. ФУНДАМЕНТАЛЬНЫЕ СТРУКТУРЫ ДАННЫХ 1л. Ввядеимв Современная цифровая вычислительная машина первоначально предназначалась для облегчения и ускорения сложных и длительных вычислений.

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

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

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

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

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

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

Из приведенного примера видно, что при решении вопроса о представлении данных обычно имеется несколько уровней детализации. Пусть, например, нужно изобразить положение объекта в пространстве. На первом этапе берется пара вещественных чисел, например декартовы илн полярные координаты. На втором этапе они представляются как числа с плавающей запятой: каждому вещественному числу х ставится в соответствие пара целых чисел, обозначающих мантиссу," н порядок е (например, х =1 2'). На третьем этапе, когда учитывается, что данные должны располагаться в памяти ЭВМ, мы получаем двоичное позиционное представление целых чисел, и на последнем этапе двоичные числа могут представляться направлением магнитного поля в магнитном запоминающем устройстве. Ясно, что первый этап определяется в основном самой задачей, а последний тесно связан с используемым вычислительным устройством.

Характеристики

Список файлов учебной работы