Абстрактные типы данных

3-е издание, электронное

Москва
Лаборатория знаний
2020

С. М. Окулов

АБСТРАКТНЫЕ
ТИПЫ
ДАННЫХ

УДК 519.85(023)
ББК 22.18

О-52

С е р и я о с н о в а н а в 2008 г.
Окулов С. М.

О-52
Абстрактные
типы
данных
/
С. М. Окулов. —
3-е изд., электрон. — М. : Лаборатория знаний, 2020. —
253 с. — (Развитие интеллекта школьников). — Систем.
требования:
Adobe
Reader
XI
;
экран 10". — Загл.
с титул. экрана. — Текст : электронный.
ISBN 978-5-00101-891-9
Абстракция,
абстрагирование — одна
из
составляющих
мыслительного процесса творческой личности. Для развития
этого компонента мышления в процессе обучения информатике есть дополнительные возможности, так как знание
абстрактных типов данных, умение оперировать ими — необходимый элемент профессиональной культуры специалиста,
связанного с разработкой программных комплексов.
Для
школьников,
преподавателей
информатики
и
студентов младших курсов университетов. Книга может быть
использована при проведении факультативных занятий и при
углубленном изучении информатики.
УДК 519.85(023)
ББК 22.18

Деривативное издание
на
основе
печатного
аналога: Абстрактные
типы
данных
/
С. М. Окулов. — М.
:
БИНОМ.
Лаборатория знаний, 2009. — 250 с. : ил. — (Развитие интеллекта школьников). — ISBN 978-5-94774-869-7.

В
соответствии
со
ст. 1299
и
1301
ГК
РФ
при
устранении
ограничений, установленных техническими средствами защиты
авторских прав, правообладатель вправе требовать от нарушителя
возмещения убытков или выплаты компенсации

ISBN 978-5-00101-891-9
c○ Лаборатория знаний, 2015

2

Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

Глава 1. Матрицы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

1.1. Основные понятия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.2. Операции над матрицами . . . . . . . . . . . . . . . . . . . . . . . 18
1.3. Элементарные преобразования матриц . . . . . . . . . . . 27

Глава 2. Списки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

2.1. Основные понятия о ссылочном типе данных
(указателях) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

2.2. Линейный список. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.3. Реализация линейного списка с использованием
массивов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

2.4. Двусвязные списки . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

Глава 3. Стек . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

3.1. Основные понятия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.2. Реализация стека через линейный список. . . . . . . . . 59
3.3. Реализация стека с использованием массива . . . . . . 60
3.4. Постфиксная, префиксная и инфиксная формы
записи выражений. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

3.5. Стек и рекурсивные процедуры . . . . . . . . . . . . . . . . . . 73

Глава 4. Очередь. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

4.1. Определение и реализация очереди
с использованием списков . . . . . . . . . . . . . . . . . . . . . . 84

4.2. Реализация очереди с помощью массива . . . . . . . . . . 86

Глава 5. Деревья. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

5.1. Основные понятия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
5.2. Двоичные деревья поиска . . . . . . . . . . . . . . . . . . . . . . . 96
5.3. Способы описания деревьев . . . . . . . . . . . . . . . . . . . . 105
5.4. Оптимальные двоичные деревья поиска . . . . . . . . . 115

Оглавление

Глава 6. Множества . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125

6.1. Основные понятия . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
6.2. Стандартные способы реализации множества . . . . 127
6.3. Объединение непересекающихся множеств . . . . . . 129
6.4. Использование древовидных структур данных
в задаче объединения непересекающихся
множеств . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134

6.5. Словари и хеширование . . . . . . . . . . . . . . . . . . . . . . . 141

Глава 7. Очереди с приоритетами. . . . . . . . . . . . . . . . . . . . . . . 150

7.1. Двоичная куча и пирамидальная сортировка . . . . . 150
7.2. Очередь с приоритетом на базе двоичной кучи . . . . 161
7.3. Биномиальная куча . . . . . . . . . . . . . . . . . . . . . . . . . . . 165

Глава 8. Сбалансированные деревья. . . . . . . . . . . . . . . . . . . . 178

8.1. АВЛ-деревья . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
8.2.«2–3»-деревья . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
8.3. Б-деревья . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
8.4. Красно-черные деревья . . . . . . . . . . . . . . . . . . . . . . . . 225

4
Оглавление

Выдвинем утверждение о том, что информатика обладает исключительным, присущим только этому предмету
ресурсом по интеллектуальному развитию школьника.

Схема доказательства этого утверждения: 1) дадим
неформальное определение информатики как школьного
предмета; 2) выделим особенности учебной деятельности,
присущие только предмету «Информатика»; 3) установим
соответствие
между
деятельностью
в
информатике
и
интеллектуальным развитием — например, на базе основных
положений
теории
интеллектуального
развития
Ж. Пиаже1).

1.
Во-первых, в школьном курсе информатики должны
изучаться фундаментальные основы этого предмета2).
Во-вторых, между понятиями «информатика» и «computer science» мы практически ставим знак эквивалентности. Из этого вытекает, например, то, что в информатике не

Сыновьям: Алексею, Михаилу
и Сергею Окуловым —посвящаю

Предисловие

Когда человек познает самого себя,
сфинкс засмеется.
Надпись на постаменте сфинкса

1) Жан Пиаже (1896–1980) — психолог, чье влияние на развитие психологии
XX векабылоопределяющим.Вгенетической эпистемологии (какназывают
его теорию) отражено глубокое убеждение в том, что развитие интеллекта
проходитопределенныестадии иявляется результатом динамического взаимодействия ребенка и окружающей среды.
2) О фундаментальных основах информатики вы можете прочитать короткое
эссе в предыдущей книге серии «Развитие интеллекта школьников»: Окулов С. М., Лялин А. В. «Ханойские башни». М.: БИНОМ. Лаборатория знаний, 2008.

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

2.
Программирование — это многогранная деятельность.
Кратко охарактеризуем только один ее аспект. Программу
можно рассматривать как формализованную запись метода решения некой сложной проблемы. Программа попадает
и под понятие модели, ибо последняя — не что иное, как
имитация структуры или функционирования объекта (например, коммивояжера, которому требуется определенным
образом обойти заданную совокупность городов). Но главное даже не в этом, а в том, что программа есть динамичес
6
Предисловие

1) Обоснование этого положения дано в монографии: Окулов С. М. Информатика: развитие интеллекта школьника. М.: БИНОМ. Лаборатория знаний,
2005.
2) Самостоятельная деятельность не исключает учителя. Она понимается по
М. Мамардашвили: человек может что-то понять, узнать только сам, никому
не дано пребывать в состоянии чужой мысли и заставить другого мыслить.

кая модель со всеми вытекающими из этого положения
следствиями, принципиальным из которых является появление возможности исследовать эту модель. И именно в данной возможности состоит принципиальное отличие информатики от любого другого школьного предмета!
Что происходит при решении сложной проблемы (задачи), при разработке и исследовании динамической модели?
Сложная задача разбивается на взаимосвязанные подзадачи. Последние, в свою очередь, опять разделяются на свои
подзадачи и т. д. вплоть до самых низших уровней нашего
понимания задачи.
Что мы при этом получаем? Во-первых, сложная задача (проблема) описывается некой иерархической структурой; во-вторых, определяются принципы ее декомпозиции; в-третьих, так как каждый уровень — это определенный уровень абстрагирования, создается инструментарий
для описания абстракций. Иерархия — это ранжированная или упорядоченная система абстракций, расположение частей или элементов целого в порядке от высшего к
низшему. В результате деятельности программиста создается иерархическая структура из абстракций (A). Но ведь
«абстракция — это такие существенные характеристики
исследуемого объекта, которые отличают его от всех других видов объектов и, таким образом, четко определяют
особенности данного объекта с точки зрения дальнейшего
рассмотрения и анализа»1). Г. Буч (и не только он2)) разделяет абстракцию сущности объекта — когда объект
представляет собой модель существенных сторон предметной области, и абстракцию поведения — когда объект состоит из обобщенного множества операций, каждая из которых выполняет определенную функцию. Другими словами, сущность задачи (проблемы) и метода ее решения мы
описываем (очевидно, на каком-то языке, а это уже и есть
формализованная запись!) на уровне данных в программе,
а ее поведение — действиями над данными.
Но как осуществляется движение от проблемы (задачи)
к модели, к динамической модели? С помощью логических
приемов мышления, основными из которых являются ана
Предисловие
7

1) Буч Г. Объектно-ориентированное проектирование с примерами применения. М.: Конкорд, 1992.
2) Здесь можно сослаться на работы В. М. Глушкова, известного специалиста
ХХ в. по кибернетике, и на работы родоначальника школьной информатики
А. П. Ершова.

лиз, всегда сочетающийся с абстрагированием1), и синтез!
Но описывают ли они полностью этот процесс движения к
результату? Вряд ли! Говорят, что этими дефинициями отражается рациональная сторона мышления — поэтому далее вводится понятие метода. Метод (в самом широком
смысле слова) — это «путь к чему-либо», способ достижения определенной цели, совокупность приемов или операций практического или теоретического освоения действительности. Р. Декарт писал в своем философском учении: «Под методом же я разумею достоверные и легкие
правила, строго соблюдая которые, человек никогда не
примет ничего ложного за истинное» и сможет добывать
новое знание — все, что он способен познать, — «без излишней траты умственных сил»2). Р. Декарт считал, что
для реализации правил его рационалистического метода
необходима интуиция, с помощью которой усматриваются первые начала (принципы), а затем с помощью дедукции получаются следствия из этих начал. Но нужна не
только интуиция, но и инсайт, и воображение, — другими
словами, все свойства (или качества) интеллекта, не укладывающиеся в его рациональную составляющую (B).
В чем отличие хорошей программы от плохой? Чем отличается добротно сделанная динамическая модель (даже
миниатюрная) от «поделки»? В хорошей программе нет
никаких излишеств ни на уровне абстракций сущности, ни
на уровне абстракций поведения. Хорошая программа
стремится
(состоит)
к
возникновению
и
организации
структур с простыми и четкими формами, к простым и
устойчивым состояниям. То есть она функционирует «без
излишней траты умственных сил»! И опять-таки выделим
главное: в результате исследования (экспериментальной
деятельности
с
программой)
достигается
соответствие
между динамической моделью и объектом, для которого
она строится (C).

8
Предисловие

1) Имеются в виду все типы абстракции: абстракция отождествления, или обобщающая абстракция; абстракция аналитическая, или изолирующая;
абстракция идеализирующая, или идеализация; абстракция актуальной
бесконечности (отвлечение от принципиальной невозможности зафиксировать каждый элемент бесконечного множества, т. е. когда бесконечные множества рассматриваются как конечные); абстракция потенциальной осуществимости (предполагается, что может быть осуществлено любое, но конечное число операций в процессе деятельности).
2) Декарт Р. Избранные произведения. М.: Госполитиздат, 1950.

3.
По Ж. Пиаже, интеллект, подобно всем биологическим
функциям, является продуктом эволюционной адаптации,
поэтому для его понимания следует изучать умственную деятельность от момента рождения, наблюдая за его развитием и изменением в процессе взросления.
Два основных принципа интеллектуального роста ребенка: организация (A) и адаптация (B). Адаптация (приспособление к условиям окружения) состоит из ассимиляции и аккомодации. Организация — это структуризация
интеллекта. Наиболее простой уровень такой структуризации — схема, являющаяся мысленной репрезентацией некоторого действия (физического или мысленного), выполняемого над объектом. Для новорожденного сосание, хватание, смотрение — это схемы, т. е. его способы познания
окружающего мира и воздействия на этот мир. С развитием
интеллект ребенка структурируется, или организуется, со
все возрастающей сложностью и степенью интеграции. Кроме того, как схемы действий, так и вновь образуемые структуры все более интериоризуются, т. е. начинают совершаться в его голове как быстрые, короткозамкнутые мысленные
последовательности.
Еще один фундаментальный аспект теории Ж. Пиаже — знание есть действие: «Познание начинается с действия, а всякое действие повторяется или обобщается (генерализуется) через применение к новым объектам, порождая
тем самым некоторую «схему»... Основная связь, лежащая
в основе всякого знания, состоит не в простой «ассоциации»
между объектами (поскольку это понятие отрицает активность субъекта), а в «ассимиляции» объектов по определенным схемам, которые присущи субъекту. Этот процесс является продолжением различных форм биологической ассимиляции,
среди
которых
когнитивная
ассимиляция
представляет лишь частный случай и выступает как процесс функциональной интеграции. В свою очередь, когда
объекты ассимилированы схемами действий, возникает необходимость приспособления («аккомодации» — (C) ) к особенностям этих объектов, это приспособление (аккомодация) является результатом внешних воздействий, т. е. результатом
опыта»1).
Знания
об
объекте
определяют
в

Предисловие
9

1) Пиаже Ж. Психогенез знаний и его эпистемологическое значение // Семиотика: Антология / Сост. Ю. С. Степанов. М.: Академ-Проект, Екатеринбург:
Деловая книга, 2001.

конечном счете те действия, которые вы над ним можете совершить.
Согласно Ж. Пиаже, в развитии интеллекта человека
можно условно выделить четыре главных периода развития: сенсомоторная стадия (от рождения до 2 лет), дооперациональная стадия (от 2 до 7 лет); стадия конкретных
операций (от 7 до 11 лет) и стадия формальных операций
(от 11 лет и подростковый период). Последний период имеет
наибольшее отношение к рассматриваемой нами проблеме.
На предыдущей стадии ребенок ограничен координацией
конкретных объектов в действительной ситуации. Он все
еще не может координировать вероятностные события в гипотетической или более абстрактной формализованной ситуации, не может решать задачи без привязки к непосредственно воспринимаемой реальности. Главным же результатом
освоения
такой
координации
является
то,
что
подросток может вызвать в уме системы операций, не присущие конкретной наблюдаемой ситуации, он способен координировать мысленные системы в системы более высокого порядка (иерархия абстракций). Наступает период
умственной зрелости. Именно об этом периоде (стадии) формирования интеллекта идет речь: о периоде формирования
и становления гипотетического, абстрактного мышления.
Рассмотрим особенности стадии формальных операций.
Это — период формирования того, что называют теоретическим мышлением. Его логическими формами (способами
отражения действительности посредством взаимосвязанных абстракций) являются понятия, суждения и умозаключения. Они отражают как бы результат логических действий ума при решении проблемы. Проблема — ситуация, в
которой возникают задачи, связанные с интеллектуальной
деятельностью; говоря философским языком, — форма
теоретического знания. Ее содержанием является то, что
еще не познано человеком, но что нужно познать (знание о
незнании; вопрос, возникший в ходе познания и требующий ответа). Проблемная ситуация, согласно М. Вертгеймеру1), не является чем-то замкнутым в себе, поэтому
она ведет нас к решению, к структурному завершению. Точ
10
Предисловие

1) Макс Вертгеймер (1880–1943) — немецкий и американский психолог, один
из основателей и главных теоретиков гештальт-психологии. «Гештальт» —
это немецкий термин, не имеющий точного английского и русского аналога,
но вошедший в научный язык. Этот термин используется для обозначения
целого,полной структуры,множества, природа которогоне обнаруживается
с
помощью
простого
анализа
отдельных
частей,
его
составляющих.

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

А теперь, согласно ранее приведенной схеме доказательства утверждения, установим соответствие (которое
было намечено в предыдущем тексте буквами A, B и C)1).
Мы конструируем программу как иерархию абстракций,
порождаем некую схему — возможно ли это без структуризации интеллекта (А)? Ответ однозначен! Причем интеллект постоянно как бы тренируется в порождении схем.
Мы используем методы, а, по Ж. Пиаже, это не что иное,
как адаптация созданной схемы (иерархии абстракций) к
исследуемому объекту (В). У нашей динамической модели
нет согласования с объектом исследования? Начинается
творческий процесс поиска причин несоответствия. При
этом происходит или аккомодация, или новый виток генерации иерархии абстракций (С).

Предисловие
11

Афоризм, порожденный этой идеей: «Целое (т. е. гештальт) отличается от
суммы его частей».
1) Вероятно, существует весьма ограниченное количество законов, управляющих мирозданием и, в частности, процессом познания человеком окружающегомира и себя.Люди говорят освоем,на своемязыке, на языке своей предметной области. Но говорят ли они о разном?

Структура данных — это не что иное, как способ взаимосвязи элементов данных. Другими словами, из элементов данных конструируется некое целое, с некоторыми
свойствами, и это целое есть структура данных. Дальнейший шаг — в единое целое связываются как структуры
данных, так и выполняемые над ними операции. Это новое
целое
носит
в
информатике
название
«абстрактные
типы данных» (abstract data type), т. е. является множеством абстрактных объектов, представляющих неким образом организованные элементы данных, и определенного на
этом множестве набора операций, которые могут быть выполнены над его элементами. Зачем нужна эта цепь абстрагирования? Она позволяет более рационально мыслить при
решении проблем с использованием компьютера и в итоге
получать результат «с наименьшей затратой умственных
сил», — ибо уже не конкретное данное (число, символ
и т. д.), а абстрактные типы данных становятся элементарными
«кирпичиками»
конструирования
программного
продукта1). И эта книга — о таких элементарных кирпичиках!
Следует отметить, что данный основополагающий раздел информатики не представлен должным образом в рекомендациях по преподаванию информатики, разработанных

Введение

Инструменты, которые мы
применяем, оказывают глубокое
(и тонкое) влияние на наши способы
мышления и, следовательно, на нашу
способность мыслить.
Э. Дейкстра

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