УДК 681.3.06

Хохлов Д.Г. Программирование на языке высокого уровня. Часть 2. Методы программирования: Учебник. - Казань: Мастер Лайн, 2009. - 270 с.

ISBN 5-93139-200-9

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

Описываются базовые методы и приемы построения алгоритмов, основные понятия и элементы технологии модульного и объектно-ориентированного программирования. Приведены многочисленные примеры алгоритмов и программ на языке С/C++, в том числе программа простого компилятора для упрощенного языка С.

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

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

Учебник основан на многолетнем опыте автора по преподаванию программирования на кафедре автоматизированных систем обработки информации и управления Казанского государственного технического университета (КГТУ-КАИ).

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

Табл. 12, Ил. 69, Библиогр. 86 назв.

ISBN 5-93139-200-9

© Дмитрий Григорьевич Хохлов, 2009

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

Академик А.П. Ершов

Предисловие

Учебник охватывает весь предусмотренный государственным образовательным стандартом материал по дисциплине «Программирование на языке высокого уровня» для студентов вузов, обучающихся по направлению вычислительной техники и инфор­матики и специальностям «Автоматизирован­ные системы обработки информации и управления», «Вычислительные машины, комплексы, системы и сети», «Информационные системы в технике и технологиях» и другим.

Основу учебника составляет расширенный конспект лекций курса программирова­ния на языках высокого уровня, около тридцати лет под разными названиями читаемого автором на кафедре АСОИУ - автоматизирован­ных систем обработки информации и управления Казанского госу­дарственного технического университета (КГТУ – КАИ).

Данная книга является непосредственным продолжением учебника [67] и во многом опирается на его содержание и терминологию, но может использоваться и независимо от него для углубленного изучения программирования.

В первой части учебника [67] рассматриваются основные понятия и базовые методы программирования, иллюстрируемые на примере языка С/C++.

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

В разделе 1 кратко описываются базовые понятия и методы хранения сложных структур данных.

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

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

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

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

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

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

В разделе 9 приведен пример многомодульного проекта - разработки простого компилятора для упрощенного языка С.ов, 2005арактеристическими вектором.оявления лексемы, водящей в множество лексем возобновления анализа т

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

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

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

Нельзя не сказать, что большое влияние на содержание учебника оказал десятилетний опыт автора в подготовке студентов и школьников к олимпиадам по программированию, в том числе участие в чемпионате мира среди студенческих команд. Этим вопросам посвящено большое число источников и в приводимом списке литературы [34, 79 – 86, 32, 49 - 52, 10, 12, 13 и др.].

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

Автор пользуется случаем выразить благодарность многим людям, без участия которых эта книга не могла бы появиться на свет, своим учителям и коллегам: Ф. З. Рохлину, В. И. Медведеву, Л. И. Ожиганову, О. М. Рякину, Х. Ф. Кулееву, А. Р. Бикмурзиной, З. Х. Захаровой и другим, а также, конечно, своим студентам, для которых она и написана. Особая признательность - Ю. М. Баяковскому, программы и консультации которого способствовали первому приобщению автора к профессиональному программированию.