Virt N. Algoritmy struktury dannyh = programmy (ru)(T)(410s) (522393), страница 2
Текст из файла (страница 2)
Появилась масса теорий н направлений, авторы и апологеты которых обещают быстро доставить корабль программирования к земле обетованной. Уже были н языки высокого и очень высокого уровня, и структурное программирование, и доказательство правильности, н доказательное программирование, и масса всяческих технологий. Одни из авторов языка Ада в своем интервью, опубликованном в старом и уважаемом программистами журнале Со>ппшп>саВоп о1 1)>е АСМ (1984, № 4), договорился до того, что легкость написания программ, оказывается, н не была целью разработки этого нового языка программирования.
В этой ситуации все труднее становится учить программистов хорошо программировать. На словах все признают, что в основе программирования лежит творческий акт. У'учеников нугкно развивать способность творчески мыслить. И здесь огромна роль учителя, не столько рассказывающего о чем-то, сколько показывающего, как <>н делает то-то и то-то. Заметим, что в основе обучения и действий учителя лежит тот же творческий акт. Творчество не подвластно канонам, методикам и, тем более, технологиям. Представьте себе учебник по технологии физики или еще лучше по технологии математики, по технологии соответствующего мышления. Блестящие книги Пойи лишь подтверждают правило, что творчеству учат Учителя.
При обучении «творческнм специальностям» ученики не столько слуша>от, сколько смотрят, что и как делает учитель. Они наблюдают весь процесс его творчества Но что же делать, если нужно обучать не десятки или сотни людей, а многие тысячи? В этом случае надо полагаться на «школы», во главе которых стоят такие крупные Учителя. В школах процесс обучения н воспитания опять- таки основан на показе, но носит более сложный характер н захватывает значительно большее количество учеников. В программировании таких школ несколько.
Одна из зару бежных школ находится в Цюрихе, во главе ее стоит Н. Вирт. Именно отсюда пришел элегантный Паскаль, завоевавший Пред«слов«е редактора ««ревода почти весь мир, отсюда пришли Модула и Модула-2. Здесь появилась книга «Систематическое программирование. Введение> (Пер, с англ.— Мл Мир, 1977), и отсюда же появляется книга, перевод которой читатель держит в руках. В ней обобщен авторский опыт многолетнего обучения программированию. Искусство автора проявилось в том, что в своей книге он подчеркивает основополагающие принципы программирования, а ие конкретные особенности того или иного модного языка программирования. Благодаря атому его книге суждена долгая жизнь.
Здесь почти нет никаких рецептов, рекомендаций, методик. Это набор примеров программ, про которые автор говорит: «Смотрите, как и почему я это делаюр. Действительно, читатель, посмотрите. Если Вы только начинающий программист, то для Вас книга будет очень хорошим самоучителем. Если Вы достаточно опытны„то в ней Вы обнаружите многие тонкости, которые позволят Вам усовершенствовать Ваш стиль программирования. И наконец, если Вы первый раз окунаетесь в «море программирования» и не знаете, что такое ЭВМ, то лучше оставьте зту книгу на прилавке; пусть ее купят другие: ведь программистов так много, а хороших книг для них, к сожалению, так мало. Д.
Б. Подшивалов Посвящается Нани Г)РЕДИСЛОВИЕ В последние годы программирование для вычислительных машин стало не только средством, владение которым оказывается решавшим для успешной работы во многих прикладных областях, а также и предметом научного изучения. Из ремесла программирование превратилось в академическуго дисциплину. Первые крупные шаги в этом направлении были сделаны в работах Э. Дейкстры и К. Хоора. «Заметки по структурному программировании» Дейкстры *) определили новый взглнд на программирование как на предмет научного изучении и поле для интеллектуальной деятельности; этот подход получил название «революции» в программировании.
В статье «Лксиоматическая основа программирования для вычислительных машин» "") Хоор продемонстрировал, что программы поддаются точному анализу, основанному на математических рассуждениях. В этих работах убедительно показано, что можно избежать многих ошибок программирования, если программисты со знанием дела будут применять те методы и приемы, которые оии ранее использовали интуитивно и часто неосознанно.
Основное внимание в них уделено построению и анализу программ, или, более конкретно, структуре алгоритмов, представленных текстами программ. Причем совершенно ясно, что систематический и научный подход к построению программ важен в первую очередь в случае больших программ со сложными данными. Таким образом, методы программирования включают также и все варианты структурирования данных. Программьг представляют собой. в конечном счете конкретные формулировки абстрактных алгоритмов, основанные иа конкретных вредставлсннях и структурах данных. Важный вклад в упдрядочение широкого разнообразия терминов и концепций, относящихся к структурам данных, был сделан Хоором в статье «О структурной организации данных»""). Стало ясно, что решения о структурировании данных нельзя принимать без *) В книге: О.
Дал, Э. дейкстра, К. Хвор, Структурное программирование: Пер, с англ, — Мг Мнр, 1975. "*) В Сонин, АСМ, 12, № 19 (1969), 576 — 563, »'») В книге «Структурное программирование» см. сноску выше. Предисловие знания алгоритмов, применяемых к этим данным, и наоборот, структура и выбор алгоритмов существенным образом зависят от структуры данных. Говоря короче, строение программ и структуры данных неразрывно связаны.
Предлагаемая книга начинается главой о структуре данных по двум причинам. Во-первых, мы интуитивно чувствуем, что данные предшествуют алгоритмам: нужно имегь некоторые объекты, прежде чем выполнять действия с ними. Во-вторых 1и это более непосредственная прнчина), хотя здесь и предполагается, что читатель знаком с основными понятиями программирования, но по традиции курсы введе. ния в программирование явно уделяют больше внимания алгоритмам, оперирующим данными со сравнительно простой структурой. В связи с этим возникла необходимость в вводной главе о структуре данных.
На протяжении всей кни~и, и в частности в гл. 1, мы следуем теории и терминологии, которые были предложены Хоором*> и реализованы в языке программирования Паскаль*'>, Суть этой теории состоит в том, что данные представляют собой прежде всего абстракции реальных объектов и формулируются предпочтительно как абстрактные структуры, не обязательно реализованные в распространенных языках программирования. В процессе конструирования программы представление данных постепенно уточняется вслед за уточнением алгоритма, все более подчиняясь ограничениям, накладываемым конкретной системой программирования. Поэтому мы определим несколько основных строительных конструкций — структур для данных, называемых >))у>гдаментальными структурами.
Особенно важно, что эти конструкции довольно легко реализуются на современных вычислительных машинах, поскольку только в этом случае пх можно действительно рассматривать как элементы реального представления данных, т. е, как «молекулы», возиикагощие на окончательном этапе уточнения описаний данных, Это следующие структуры: запись, массив !фиксированного размера) и множество.
Неудивительно, что этн основные строительные блоки соответствуют математическим обозначениям, которые также являются фундаментальными. Краеугольным камнем этой теории структур данных служит различие между фундаментальными и усложненными структурами. Фундаментальные структуры — это как бы молекулы (в свою очередь состоящие из атомов); они являются компонентами, из которых состоят усложненные структуры. ') Сн. первую сноску на предыдунгеа странице. Г«) Ь>. ЦГ>г!Ь, Тье Ргопгвтгп!пв ).впкнане Равен!, Ас!в 1п1оппацсв, 1, Ио.
1 (!971), 35 — 63. Предисловие Переменные фундаментальной структуры могут менять только свое значение, сохраняя форму или множество значений, которые они могут принимать. Таким образом, размер занимаемой нми памяти остается постоянным, Напротив, усложненные структуры характеризуются изменением не только значения, но и формы во время выполнения программы. Поэтому для их реализации нужно применять более сложные приемы. Последовательный файл, или просто последовательность, в этой классификации является промежуточным.
Его длина, естественно, изменяется, но это изменение формы тривиально, Поскольку последовательный файл играет важную роль практически во всех вычислительных системах, мы рассмотрим его среди фундаментальных структур в гл. Е Во второй главе описываются различные алгоритмы соутировки. Математический анализ некоторых из них раскрывает преимущества и недостатки разных методов и помогает программисту понять важность анализа при выборе подходящего способа решений стоящей перед ним задачи.
Разграничение методов сортировки массивов и методов сортировки файлов (часто называемых внутренней и внешней сортировкой) демонстрирует решающее влияние представления данных на выбор алгоритмов и их сложность, Сортировке уделяется столько внимания, так как с ее помощью можно прекрасно иллюстрировать многие принципы программирования и ситуации, возникающие и в других задачах. Создается впечатление, что можно построить целый курс программирования, выбирая примеры только из задач сортировки.
Другая тема, которой часто пренебрегают в курсах введения в программирование, но которая важна для понимания большого числа алгоритмических решений, — это рекурсия. Поэтому третья глава посвящена рекурсивньсм алгоритмам. В ней показано, что рекурсия — это обобщение повторения (итерации) н поэтому является важным и мощным средством программирования. К сожалению, при обучении программированию рекурсивные методы нередко демонстрируют на примерах, в которых достаточно простой итерации. В гл. 3, напротив, приводятся несколько примеров задач, где рекурсия позволяет получить решение наиболее естественным образом, тогда как использование итерации сделало бы программы громоздкими и трудными для понимания.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
