Основы алгоритмизации и программирования

-¬¡ ©¡¡
«¬ª°¡--¤ª©œ§¸©ª¡
ª¬œ£ªžœ©¤¡
-ÁÌÄÛ
ÊÍÉʾ¼É¼
¾

¿ÊÀÏ
В.Д. Колдаев
ОСНОВЫ 
АЛГОРИТМИЗАЦИИ 
И ПРОГРАММИРОВАНИЯ
УЧЕБНОЕ ПОСОБИЕ
Под редакцией профессора Л.Г. Гагариной
Допущено Министерством образования и науки Российской Федерации
в качестве учебного пособия для студентов учреждений среднего
профессионального образования, обучающихся по группе
специальностей 09.00.00 «Информатика и вычислительная техника»
Москва 
ИД «ФОРУМ» — ИНФРА-М
2021

УДК  004(075.32) 
ББК 32.973-018я723 
 
К60
Р е ц е н з е н т ы:
В.В. Уздовский, доктор физико-математических наук, профессор 
Московского государственного института электронной техники (технического университета), кафедра общей физики; 
О.И. Лисов, доктор технических наук, профессор Московского государственного института электронной техники (технического университета), кафедра информатики и программного обеспечения вычислительных систем
Колдаев В.Д.
К60  
Основы алгоритмизации и программирования : учебное пособие / В.Д. Колдаев ; под ред. проф. Л.Г. Гагариной. — Москва : 
ИД « 
ФОРУМ» : ИНФРА-М, 2021. — 414 с. — (Среднее профессиональное образование).
ISBN 978-5-8199-0733-7 (ИД «ФОРУМ») 
ISBN 978-5-16-013541-0 (ИНФРА-М, print) 
ISBN 978-5-16-103967-0 (ИНФРА-М, online)
Рассмотрен широкий круг алгоритмов обработки линейных и нелинейных структур данных. Приведены основные понятия алгоритмизации, 
свойств алгоритмов, общие принципы построения алгоритмов, основные 
алгоритмические конструкции. Рассмотрены эволюция языков программирования, технология работы и фрагменты программ, а также основные принципы объектно-ориентированного программирования.
Для студентов, обучающихся по направлению и специальностям программного обеспечения вычислительной техники и автоматизированных 
систем, прикладной математики и обработки информации. Пособие будет 
полезно широкому кругу специалистов по компьютерному моделированию.
УДК 004(075.32) 
ББК 32.973-018я723 
ISBN 978-5-8199-0733-7 (ИД «ФОРУМ») 
ISBN 978-5-16-013541-0 (ИНФРА-М, print) 
ISBN 978-5-16-103967-0 (ИНФРА-М, online)
© Колдаев В.Д., 2015
© ИД «ФОРУМ», 2015

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

 познакомить со всем разнообразием имеющихся структур
данных, показать, как эти структуры реализованы в языках
программирования;

Введение

 познакомить с операциями,
которые выполняются над
структурами данных;

 показать особенности структурного подхода к разработке
алгоритмов, продемонстрировать порядок разработки алгоритмов.
Тщательно подобранный материал, вошедший в пособие,
включает в себя основные, фундаментальные классы алгоритмов, которые в том или ином виде наиболее часто встречаются в
практике программирования.
Ценность его в том, что оно предназначено не столько для
обучения технике программирования, сколько для обучения,
если это возможно, «искусству» программирования. Настоящее
пособие предлагает массу рецептов усовершенствования программ и, что самое главное, учит самостоятельно находить эти
рецепты.
Рассмотрены структуры данных, их представление и алгоритмы обработки, без знания которых невозможно современное
компьютерное программирование. Приведены различные алгоритмы для работы с очередями, стеками, списками, деревьями,
таблицами и графами. Алгоритмы большинства операций над
структурами данных доведены до программной реализации в
виде функций на языках Си и Turbo Pascal.
В конце каждой главы содержится большое количество контрольных вопросов и задач для самостоятельного решения.
Пособие предназначено для студентов, обучающихся по направлению и специальностям «Вычислительные машины, системы, комплексы и сети», «Автоматизированные системы обработки информации и управления», «Программное обеспечение вычислительной техники и автоматизированных систем».
Выражаю благодарность Людмиле Михайловне Поддубной
и Борису Матвеевичу Полосухину за помощь в подготовке данного учебного пособия.

Глава 1
ОСНОВЫ АЛГОРИТМИЗАЦИИ
1.1. Структурная организация данных
Обработка на персональных электронных вычислительных
машинах (ПЭВМ) данных реального мира требует, чтобы их
структура была определена и точно представлена в ПЭВМ.
Структура данных определяет семантику данных, а также способы организации и управления данными. Информация, представленная в виде последовательности символов и предназначенная
для обработки на ПЭВМ, называется данными. При использовании компьютера для хранения и обработки данных необходимо
хорошо знать тип и структуру данных, а также найти способ
наиболее естественного их представления. Структуры данных и
алгоритмы служат теми материалами, из которых строятся программы.
Без понимания структур данных и алгоритмов невозможно
создать серьезный программный продукт — «они служат базовыми элементами любой машинной программы. В организации
структур данных и процедур их обработки заложена возможность проверки правильности работы программы» [4].
1.1.1. Основные понятия структур данных
В основе работы компьютера лежит умение оперировать
только с одним видом данных — с отдельными битами, или двоичными цифрами. Работает же с этими данными компьютер
только в соответствии с неизменным набором алгоритмов, которые определяются системой команд процессора. Задачи, которые решаются с помощью компьютера, редко выражаются на
языке битов. Как правило, данные имеют форму чисел, литер,

Глава 1. Основы алгоритмизации
текстов, символов и более сложных структур типа последовательностей, списков и деревьев. Еще разнообразнее алгоритмы,
применяемые для решения различных задач; фактически алгоритмов не меньше, чем вычислительных задач.
Структура данных относится по существу к пространственным понятиям: ее можно свести к схеме организации информации в памяти компьютера. Алгоритм же является соответствующим процедурным элементом в структуре программы — он служит рецептом расчета. Первые алгоритмы были придуманы для
решения численных задач типа умножения чисел, нахождения
наибольшего общего делителя, вычисления тригонометрических
функций и др. Сегодня в равной степени важны и нечисленные
алгоритмы; они разработаны для таких задач, как, например,
поиск в тексте заданного слова, планирование событий, сортировка данных в указанном порядке и т. п. Нечисленные алгоритмы оперируют с данными, которые не обязательно являются
числами.
Структуры данных, применяемые в алгоритмах, могут быть
чрезвычайно сложными. В результате выбор правильного представления данных часто служит ключом к удачному программированию и может в большей степени сказываться на производительности программы, чем детали используемого алгоритма.
Вряд ли когда-нибудь появится общая теория выбора структур
данных. Самое лучшее, что можно сделать, — разобраться во
всех базовых «кирпичиках» и собранных из них структурах.
Способность приложить эти знания к конструированию больших систем — это прежде всего дело инженерного мастерства и
практики.
Независимо от содержания и сложности любые данные в памяти ЭВМ представляются последовательностью двоичных разрядов, или битов, а их значениями являются соответствующие
двоичные числа. Данные, рассматриваемые в виде последовательности битов, имеют очень простую организацию или, другими словами, слабо структурированы. Для человека описывать и
исследовать сложные данные в терминах последовательностей
битов весьма неудобно. Более крупные и содержательные, нежели бит, «строительные блоки» для организации произвольных
данных получаются на основе понятия «структуры данных».
Под структурой данных в общем случае понимают множество
элементов данных и множество связей между ними. Такое определение охватывает все возможные подходы к структуризации

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

Глава 1. Основы алгоритмизации
1.1.2. Классификация структур данных по признаку
изменчивости
Весьма важный признак структуры данных — ее изменчивость, т. е. изменение числа элементов и (или) связей между элементами структуры. В определении изменчивости структуры не
отражен факт изменения значений элементов данных, поскольку
в этом случае все структуры данных имели бы свойство изменчивости. По признаку изменчивости различают статические, полустатические, динамические структуры. Классификация структур
данных (СД) по признаку изменчивости приведена на рис. 1.1.
Базовые структуры данных, статические, полустатические и динамические характерны для оперативной памяти и часто называются оперативными структурами. Файловые структуры соответствуют структурам данных для внешней памяти.
Вектор (одномерный массив) — структура данных с фиксированным числом элементов одного и того же типа.
Массив — последовательность элементов одного типа, называемого базовым.
Множество — такая структура, которая представляет собой
набор неповторяющихся данных одного и того же типа.
Запись — конечное упорядоченное множество полей, характеризующихся различным типом данных.
Рис. 1.1. Классификация структур данных

1.1. Структурная организация данных
9
Таблица — последовательность записей, которые имеют одну
и ту же организацию.
Списком называется упорядоченное множество, состоящее из
переменного числа элементов, к которым применимы операции
включения, исключения. Список, отражающий отношения соседства между элементами, называется линейным.
1.1.2.1. Связные списки
Связный список — структура данных, элементами которой
являются записи, связанные друг с другом с помощью указателей, хранящихся в самих элементах (рис. 1.2).
Рис. 1.2. Классификация связных списков
В зависимости от характера взаимного расположения элементов в памяти структуры данных можно разделить на структуры с последовательным распределением элементов в памяти (векторы, строки, массивы, стеки, очереди) и структуры с произвольным связным распределением элементов в памяти (односвязные,
двухсвязные списки) (рис. 1.3).
В языках программирования понятие «структуры данных»
тесно связано с понятием «типы данных». Любые данные, т. е.
константы, переменные, значения функций или выражения, характеризуются своими типами. Информация по каждому типу
однозначно определяет:
1) структуру хранения данных указанного типа, т. е. выделение памяти и представление данных в ней, с одной стороны, и
интерпретирование двоичного представления, с другой;
2) множество допустимых значений, которые может иметь
тот или иной объект описываемого типа;

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