Структуры и алгоритмы обработки данных

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

ОБРАБОТКИ  ДАННЫХ

УЧЕБНОЕ  ПОСОБИЕ

Москва
РИОР

ИНФРА-М

В.Д. КОЛДАЕВ

Рекомендовано Научно-методическим советом

Национального исследовательского университета

Московского института электронной техники
в качестве учебного пособия для студентов,

обучающихся по специальностям 

«Программное обеспечение вычислительной 

техники и автоматизированных систем», 

«Вычислительные машины, комплексы, системы и сети»,

«Прикладная информатика в экономике»

УДК 004.42(075.8)
ББК 32.81я73
          К60

Р е ц е н з е н т ы : 
канд. техн. наук, начальник отдела ООО «Кедах Электроникс» С.А. Костина;
канд. пед. наук, директор Зеленоградского отделения Московского социально-гуманитарного института С.Н. Литвинова

Колдаев В.Д. 

К60 
 
Структуры и алгоритмы обработки данных : учебное пособие / 

В.Д. Колдаев. — Москва : РИОР : ИНФРА-М, 2021. — 296 с. — (Высшее образование: Бакалавриат). — DOI: https://doi.org/10.12737/2833

ISBN 978-5-369-01264-2 (РИОР)
ISBN 978-5-16-009012-2 (ИНФРА-М, print)
ISBN 978-5-16-101275-8 (ИНФРА-М, online)
Рассмотрен широкий круг алгоритмов обработки линейных и нели
нейных структур данных. Приведены основные понятия алгоритмизации, 
свойств алгоритмов, общие принципы построения алгоритмов, основные 
алгоритмические конструкции. Рассмотрена технология работы и оценка 
функции сложности различных алгоритмов для работы с очередями, стеками, списками, деревьями, таблицами и графами.

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

УДК 004.42(075.8)
ББК 32.81я73

ISBN 978-5-369-01264-2 (РИОР)
ISBN 978-5-16-009012-2 (ИНФРА-М, print)
ISBN 978-5-16-101275-8 (ИНФРА-М, online)

Подписано в печать 10.07.2016.

Формат 60×90/16. Гарнитура Newton. 
Бумага офсетная. Печать офсетная.

Усл. печ. л. 18,5. Уч.-изд. л. 19,16.

Тираж 500 экз.
Цена свободная.

ТК 226500-620874-030314

ООО «Издательский Центр РИОР»

127282, Москва, ул. Полярная, д. 31В. 

info@riorp.ru      www.riorpub.com

ООО «Научно-издательский центр ИНФРА-М»

127282, Москва, ул. Полярная, д. 31В, стр. 1.
Тел.: (495) 280-15-96. Факс: (495) 280-36-29.

E-mail: books@infra-m.ru     

http://www.infra-m.ru

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

© Колдаев В.Д.

ПРЕДИСЛОВИЕ

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

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

ЧАСТЬ 1. ОСНОВЫ АЛГОРИТМИЗАЦИИ

Глава 1. СТРУКТУРНАЯ ОРГАНИЗАЦИЯ ДАННЫХ

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

1.1. Основные понятия структур данных

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

Рис. 1.1. Уровни представления структуры данных

Очень часто, говоря о той или иной СД, имеют в виду ее логическое представление, так как физическое представление обычно скрыто от программиста. Поскольку физическая СД реализуется в машинной памяти, имеющей ограниченный объем, при изучении такой СД 
должна учитываться проблема распределения и управления памятью.
СД, применяемые в алгоритмах, могут быть чрезвычайно сложными. В результате выбор правильного представления данных часто 
служит ключом к удачному программированию и может в большей 
степени влиять на производительность программы, чем детали используемого алгоритма.
Под структурой данных в общем случае понимают множество 
элементов данных и множество связей между ними. Структуру данных S можно определить как S = (D, R), где D — множество элементов данных; R — множество отношений между элементами данных. 
Все связи одного элемента данных с другими образуют элемент отношений, ассоциированный с соответствующим элементом данных. 
Элемент отношений можно представить в виде конечного множества пар, каждая из которых отражает одно из отношений ассоциированного элемента данных с каким-нибудь другим их элементом и 
указатель этого элемента. Пару, содержащую элемент данных и ассоциированный с ним элемент отношений, будем называть элементом структуры. При этом связи, или отношения, элемента данных 
с другими их элементами одновременно являются связями с соответствующими элементами структуры.
Приведенное определение охватывает все возможные подходы к 
структуризации данных, но в каждой конкретной задаче использу

        




        


 

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

1.2. Классификация структур данных 
по признаку изменчивости

СД и алгоритмы служат теми материалами, из которых строятся программы. Более того, сам компьютер состоит из СД и алгоритмов. 

Встроенные СД представлены теми регистрами и словами памяти, где 
хранятся двоичные величины. Заложенные в конструкцию аппаратуры алгоритмы — это воплощенные в электронных логических цепях 
жесткие правила, по которым занесенные в память данные интерпретируются как команды, подлежащие исполнению. В основе работы 
компьютера лежит возможность оперировать только с одним видом 
данных — с отдельными битами, или двоичными цифрами. Работает 
же с этими данными компьютер только в соответствии с неизменным 
набором алгоритмов, которые определяются системой команд центрального процессора. Задачи, которые решают с помощью компьютера, редко выражаются на языке битов. Как правило, данные имеют 
форму чисел, литер, текстов, символов и более сложных структур типа 
последовательностей, списков и деревьев. Еще разнообразнее алгоритмы, применяемые для решения различных задач — фактически 
алгоритмов не меньше, чем вычислительных задач.
Структура данных — это программная единица, позволяющая 
хранить и обрабатывать множество однотипных и/или логически 
связанных данных в вычислительной технике. Для добавления, поиска, изменения и удаления данных СД предоставляет некоторый 
набор функций, составляющих ее интерфейс. СД часто является реализацией какого-либо абстрактного типа данных. При разработке 
программного обеспечения важную роль играет проектирование 
хранилища данных и представление всех данных в виде множества 
связанных СД. Хорошо запроектированное хранилище данных оптимизирует использование ресурсов (таких как время выполнения 
операций, используемый объем оперативной памяти, число обращений к дисковым накопителям), потребных для выполнения наиболее 
критичных операций.
СД формируются с помощью типов данных, ссылок и операций 
над ними в выбранном языке программирования. При разработке 
программного обеспечения сложность реализации и качество работы программ существенно зависят от правильного выбора СД. Это 
понимание положило начало формальным методам разработки и 
языкам программирования, в которых именно СД, а не алгоритмы 
составили основу архитектуры программного средства. Большая 
часть таких языков обладает определенным типом модульности, позволяющим структурам данных безопасно переиспользоваться в различных приложениях. Объектно ориентированные языки, такие как 
Java, C# и C++, являются примерами такого подхода. Многие классические СД представлены в стандартных библиотеках языков программирования или непосредственно встроены в эти языки. Например, структура данных хеш-таблица встроена в языки программирования Lua, Perl, Python, Ruby, Tcl и др. Широко используется 
стандартная библиотека шаблонов STL языка C++.

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




()
 

 


 

 -   

    
 

 
    ()  

    


 

    


 

    

 

 

        

 

 

 

 


 

 

 

 

 

 



 

 
 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рис. 1.2. Классификация структур данных

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

янное число элементов, которые называют полями. Совокупность 
записей одинаковой структуры называется файлом. (Файлом называют также набор данных во внешней памяти, например на магнитном диске.) Для того чтобы иметь возможность извлекать из файла 
отдельные записи, каждой записи присваивают уникальное имя или 
номер, которое служит ее идентификатором и располагается в отдельном поле. Этот идентификатор называют ключом.
Множество — это такая структура, которая представляет собой 
набор неповторяющихся данных одного и того же типа (множество 
есть совокупность различных элементов, мыслимая как единое целое).
Таблица — это способ передачи содержания, заключающийся в организации СД, в которой отдельные элементы помещены в ячейки, каждой 
из которых сопоставлена пара значений — номер строки и номер колонки (столбца). Таким образом, устанавливается смысловая связь между 
элементами, принадлежащими одному столбцу или одной строке.
Списком называют упорядоченное множество, состоящее из переменного числа элементов, к которым применимы операции включения, исключения (письменный перечень, число, состав; документ, 
содержащий перечень каких-либо сведений). Список, отражающий 
отношения соседства между элементами, называют линейным.

1.3. Линейные и нелинейные структуры данных

При создании тех или иных изделий и механизмов, так же как и при 
проведении многих научных экспериментов, весь процесс от возникновения идеи до ее реализации можно грубо разбить на следующие этапы. Сначала каким-то способом разрабатывают общий проект и готовят технологическую документацию. Затем строят опытный образец или его макет. И, наконец, проводят испытание. По его 
результатам в опытный образец вносят изменения и снова проводят 
испытание. Цикл образец — испытание — образец повторяют до тех 
пор, пока опытный образец не станет действующим, удовлетворяя 
всем заложенным в проект требованиям. Проведение каждого испытания и внесение очередных изменений в опытный образец почти 
всегда требует много денег и много времени. Поэтому одна из общих 
задач состоит в том, чтобы на пути превращения опытного образца 
в действующий сократить до минимума как число испытаний, так и 
их стоимость и время проведения.
Структуры данных — это отношения, заданные на множествах данных. Пусть Х — множество данных, Y — множество значений данных:



X
Y  и при этом: 






( )
:
,
i
i
i
x
x
x
X x
Y
.

Если на множестве (x) задано отношение S(x)  (x), то будем 
называть это отношение структурой данных, а (x) — областью оп