Алгоритмы и структуры данных

В.В. БЕЛОВ, В.И. ЧИСТЯКОВА

УЧЕБНИК

Москва
КУРС
ИНФРА-М
2020

АЛГОРИТМЫ 
И СТРУКТУРЫ
ДАННЫХ

Рекомендовано  
Научно-методическим советом ФГБОУ ВО «РГРТУ» 
в качестве учебника для студентов высших  
учебных заведений, обучающихся по направлению  
подготовки 2.09.03.04 «Программная инженерия» 
(квалификация — Бакалавр)

УДК 519.178(075.8)
ББК 22.176я73
 
Б43

© В.В. Белов,  
 
В.И. Чистякова, 2016, 2019
© КУРС, 2016, 2019

Белов В.В., Чистякова В.И.
Алгоритмы и структуры данных: Учебник / В.В. Белов, В.И. 
Чистякова. — Москва: КУРС: ИНФРА-М, 2020. — 240 с.

ISBN 978-5-906818-25-6 (КУРС)
ISBN 978-5-16-011704-1 (ИНФРА-М, print)
ISBN 978-5-16-104748-4 (ИНФРА-М, online)

Учебник создан в соответствии с Федеральным государственным образовательным стандартом высшего образования по направлению подготовки 
2.09.03.04 «Программная инженерия» (квалификация «бакалавр»).
Рассмотрены вопросы разработки и реализации структур, используемых 
при решении различных задач на ЭВМ — стеков, очередей, деков, односвязных и двухсвязных списков, деревьев, графов. Дано описание различных алгоритмов обработки данных на ЭВМ, включая алгоритмы поиска, хеширования 
и сортировки информации. Каждая из тем завершается заданием к лабораторной работе и примером ее выполнения. Алгоритмы реализованы на языке 
Delphi с использованием технологии объектно-ориентированного программирования. Приведены варианты заданий к курсовой работе с методическими 
указаниями по содержанию и оформлению пояснительной записки.
Учебник может быть полезен студентам всех направлений подготовки 
укрупненной группы 2.09.00.00 «Информатика и вычислительная техника» 
при изучении вопросов организации и использования структур данных в рамках дисциплин, связанных с рассмотрением информационно-вычислительных 
процессов.

УДК 519.178(075.8)
ББК 22.176я73

Б43

ФЗ 
№ 436-ФЗ
Издание не подлежит маркировке 
в соответствии с п. 1 ч. 4 ст. 11

Р е ц е н з е н т ы:
А.Н. Пылькин — д-р техн. наук, профессор, зав. кафедрой вычислительной 
и прикладной математики ФГБОУ ВПО «Рязанский государственный 
радиотехнический университет»;
В.Н. Агеев — д-р техн. наук, профессор кафедры автоматизации  
технологических процессов ФГБОУ ВПО «Московский государственный институт 
печати имени Ивана Федорова»

ISBN 978-5-906818-25-6 (КУРС)
ISBN 978-5-16-011704-1 (ИНФРА-М, print)
ISBN 978-5-16-104748-4 (ИНФРА-М, online)

ПРЕДИСЛОВИЕ

Настоящий учебник преследует следующие цели:
1) ознакомление студентов с базовыми структурами данных, к  которым относятся стеки, очереди, деки, списки, деревья, графы, 
и основными алгоритмами обработки этих структур — пополнение, 
удаление, модификация, прохождение, поиск, упорядочивание;
2) формирование навыка разработки алгоритмов и составления 
программ с использованием объектно-ориентированной методологии для решения задач, в которых активно используются изучаемые 
структуры данных.
Достижению поставленной цели способствует компактное и доходчивое, отточенное многолетней учебной практикой изложение 
теоретических основ дисциплины «Алгоритмы и структуры данных», 
а также методическое обеспечение лабораторного практикума и курсового проектирования.
Выполняя задания к лабораторным работам и курсовой работе, 
учащиеся не только закрепляют новые знания по организации и обработке структур данных, но и совершенствуют, а иногда и впервые 
приобретают навыки практического использования объектно-ориентированного программирования, профессиональной спецификации и оформления программ.
Темы курсовых работ основываются на использовании приемов 
организации и обработки структур данных для решения, различных 
специальных задач, таких как моделирование работы системы массового обслуживания, имитация работы условной вычислительной 
машины, планирование действий и топологическая сортировка, построения сетевого графика и определения характеристик его работ, 
разработка собственных типов данных, например, массивов с динамическим распределением памяти, построение деревьев оптимального поиска.
Настоятельно рекомендуется потребовать от учащихся, чтобы 
оформление пояснительной записки к курсовой работе соответствовало современным требованиям к организации и документированию 
программного обеспечения. В частности, пояснительная записка 
обязательно должна содержать функциональную спецификацию, 
описание структуры программы, анализ и оценку полученных результатов.
Предполагается, что учащиеся имеют минимальные навыки программирования в Turbo Pascal или Delphi. Дополнительные сведения 

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

ВВЕДЕНИЕ

ТЕРМИНОЛОГИЯ

Основной сферой применения ЭВМ являются обработка больших 
массивов информации, организация их хранения, поиск в них нужных сведений. От правильной организации данных существенно зависит эффективность работы с этими данными. Данные могут быть 
организованы многими различными способами; логическая или математическая модель организации данных называется структурой 
данных [1]. 
Структура данных характеризуется ее логическим (абстрактным) 
и физическим (конкретным) представлениями, а также совокупностью операций над структурой [2]. 
Структуры данных, реализованные в конкретном языке программирования, называются типами данных этого языка.
Логическая структура — совокупность элементов данных, между 
которыми существуют некоторые отношения. Элементами данных 
могут быть: данное скалярного типа (например, целое число, вещественное число, логическое значение и т.п.), множество данных одного типа, множество данных разных типов или другая логическая 
структура данных, — структуры могут включать в себя другие структуры.
Отношения между элементами данных могут быть различными. 
Например, в массиве элементы данных имеют один и тот же тип и 
строго упорядочены.
Физическая структура — это способ представления логической 
структуры данных в машинной памяти.
В общем случае между логической и физической структурами существует различие, степень которого зависит и от самой структуры, 
и от той физической среды, в которой она должна быть отражена. 
Например, логическая структура «двумерный массив» физически 
реализуется в виде линейной последовательности элементов, номер 
(адрес) которых определяется парой индексов массива. В то же время, логический и физический аспекты структуры «список», реализованной в виде цепочки динамических переменных, практически 
не различимы в том смысле, что изложить их отдельно друг от друга 
невозможно.
Могут существовать различные структуры хранения одной и той 
же логической структуры данных, созданные с целью более эффективного выполнения тех или иных операций над структурой данных. 

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

КЛАССИФИКАЦИЯ СТРУКТУР ДАННЫХ 

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

Данные динамической структуры — это данные, внутреннее строение которых формируется по какому-либо закону, но количество 
элементов, их взаиморасположение и взаимосвязи могут динамически изменяться во время выполнения программы. К данным динамической структуры относятся файлы, несвязанные и связанные 
динамические данные.
Заметим, что в программировании термины «статические» и «динамические» по отношению к данным перегружены, — употребляются в двух смыслах: 1) по признаку изменчивости, — как указано 
выше; 2) по месту физического размещения — в сегментах данных 
или в свободно распределяемой памяти (Heap в DOS и Free storage 
в Windows).

ТИПОВЫЕ ОПЕРАЦИИ НАД СТРУКТУРАМИ ДАННЫХ

1. Операция «создать» создает соответствующую структуру данных. 
Например, процедура New может использоваться для создания структур данных в динамически распределяемой памяти компьютера.
2. Операция «уничтожить» приводит к уничтожению созданной 
структуры данных. Например, процедура Dispose может использоваться для удаления созданных ранее структур данных.
В современных системах программирования реализация этой 
операции целесообразна, но практическое ее использование осуществляется редко по причине интенсивного использования возможностей сборщика мусора (Garbage collector).
3. Операция «выбрать» осуществляет доступ к данным структуры 
для чтения (Read only). 
Выполнение этой операции осуществляется с помощью средств 
(подпрограмм или методов), называемых итераторами или нумераторами.
4. Операция «изменить» осуществляет доступ к данным структуры 
для записи (Read-Write) и приводит к изменению данных в структуре.

Тема 1
СТЕКИ, ОЧЕРЕДИ, ДЕКИ

1.1. СТЕК

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

Включение
→
E
D
C
B
A
Исключение ←
↑

Вершина

Рис. 1.1. Логическая структура стека

Здесь A, B, ... — элементы стека, каждый из которых может содержать одно или несколько полей. Стек функционирует по принципу 
LIFO (Last In — First Out — «последним пришел — первым исключается»). Известный пример стека — винтовочный патронный магазин. 
Число элементов стека не ограничено. Стек, в котором нет ни одного элемента, называется пустым.
Стековые структуры широко применяются в трансляторах при 
реализации вложенных подпрограмм, многоуровневых прерываний, 
рекурсивных процедур, для преобразования выражений из одной 
формы записи в другую.

1.2. ОПЕРАЦИИ НАД СТЕКОМ

Над стеком S могут быть выполнены следующие операции:
1) включение нового элемента со значением v в стек — Push(S, v);
2) исключение и возвращение значения верхнего элемента стека — Pop(S);
3) выработка признака «стек пуст» — Empty(S) (возвращает значение «истина», если стек пуст, и «ложь» — в противном случае);
4) считывание значения верхнего элемента без его исключения — 
TopValue(S);
5) возвращение числа элементов стека — Size(S);
6) очистка стека — Clear(S).
Первые три операции над стеками являются основными.

1.3. РЕАЛИЗАЦИЯ СТЕКА

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

Head
Value
Next
Value
Next
Value
Next

nil

Рис. 1.2. Реализация стека с помощью динамических переменных

Каждый элемент стека состоит из двух частей: содержательной и 
ссылки на ранее включенный элемент. Переменная Head ссылочного типа указывает на верхний элемент стека (содержит адрес этого 
элемента). За первым включенным элементом стека (последним от 
Head) нет следующего элемента, поэтому в поле ссылки этого элемента записывается значение nil.
Описание класса tStack с элементами вещественного типа может 
быть выполнено следующим образом:

type
 tValue = Real;   // тип значения элемента стека – вещественный
 pItem = ^tItem;      // тип указателя на элемент стека

tItem = record      // тип элемента стека
  Value : tValue;     // содержательная часть элемента стека
  Next : pItem;      // указатель на следующий элемент стека
 end; // tItem
 tStack = class      // класс–стек
 protected
  fHead : pItem;     // поле – указатель на вершину стека
  fSize : Word;      // поле – число элементов стека
 public
  property Size: Word read fSize; // число элементов стека
  procedure Push(v: tValue); // включение элемента со значением v
  function Pop: tValue;    // исключение верхнего элемента стека
  function Empty: Boolean;  // возвращение true, если стек пуст
  function TopValue: tValue; // возвращение значения верхнего элем.
  procedure Clear; virtual;     // очистка стека
  constructor Create;        // конструктор – создание стека
  destructor Destroy; override;  // деструктор – удаление стека
 end; // tStack

Свойство Size доступно только для чтения. Конструктор Create 
выполняет операции fHead:=nil и fSize:=0. Деструктор Destroy вызывает метод Clear для удаления элементов стека из памяти. Метод 
Push включает элемент в вершину стека и увеличивает число элементов стека на единицу. Метод Pop исключает элемент из вершины 
стека и уменьшает на единицу размер стека.

1.4. РЕАЛИЗАЦИЯ ОСНОВНЫХ ОПЕРАЦИЙ 
НАД СТЕКОМ

Включение элемента со значением v в стек приведено на рис. 1.3. 
Одинарными линиями показаны связи в исходном состоянии стека, 
пунктирными — связи, устанавливаемые в процессе выполнения 
операции. Сначала организуется вспомогательная динамическая переменная с указателем NewItem типа pItem. В поле значения этой 
переменной записывается значение нового элемента стека, в поле 
ссылки — адрес верхнего элемента стека, на который указывала ранее переменная fHead. Затем указатель fHead получает значение адреса вновь созданного элемента стека.

fHead

17
8
nil

Newltem
v

Рис. 1.3. Включение элемента со значением v в стек