Модули и структуры данных А.А.Бурцев Москва 1998 Пособие посвящено вопросам построения новых структур данных при разработке программ. В первой части пособия подробно рассматриваются типовые структуры данных: стек, очередь, дек. списки, деревья, множества, таблицы. Анализируются разнообразные способы их реализации как на основе массива, так и с помощью указателей. Во второй части демонстрируются приемы решения задач на построение структур данных и реализацию эффективных операций над ними, а также предлагается перечень задач для самостоятельного решения. Учебное пособие предлагается студентам факультета кибернетики, осваивающим технологии разработки сложных многомодульных программ. ВВЕДЕНИЕ
Всякий алгоритм строится в расчете на определенного исполнителя, под которым понимается некое механическое или электронное устройство (компьютер или робот) со строго определенным набором возможных операций. Набор этих операций образует систему команд исполнителя. В построении исполнителя с заданной системой команд по сути и заключается всякая задача программирования [1]. Иногда ее упрощенно сводят к реализации одного или нескольких алгоритмов.
При разработке алгоритма всякой операции по обработке данных огромную роль играет форма организации этих данных [2,3]. Удачное представление данных позволит существенно упростить алгоритм, сделать его более эффективным. И наоборот, плохо продуманная организация данных затруднит реализацию алгоритма, сделает его громоздким, ухудшит его производительность.
Взаимосвязь качества алгоритма с формой организации данных можно образно представить в форме правила, аналогичного золотому правилу механики о соотношении силы и расстояния. Как известно, чтобы выиграть в силе, приходится уступить в расстоянии. При разработке программы это означает, что для получения более качественного алгоритма потребуется навести порядок в данных, придумать более "хитрую" форму для их организации. На усвоение этого правила и направлено все дальнейшее изложение.
Чтобы подчеркнуть, что данные подходящим образом организованы, что между их отдельными элементами установлены необходимые взаимосвязи и задан определенный порядок доступа к ним. говорят, что они образуют структуру данных [4,гл.З]. При характеристике конкретной структуры данных .определяют, как связаны между собой образующие ее элементы и какие операции предусмотрены для работы с ней.
Существенно, что структура данных при. этом рассматривается как некое единое целостное образование, и потому совершать какие-либо действия разрешается только с ней целиком и никоим образом с какими-то ее частями по отдельности. Можно образно представить, что данные как будто бы упрятываются в некую "бронированную" капсулу и доступ к ним становится возможен только через специальные "окошки", которые раскрываются лишь на время выполнения заранее предусмотренных операций. Такое свойство защищенности данных, при котором доступ к ним обеспечивается только посредством заданных над ними операций, называется инкапсуляцией (data encapsulation).
Для функционирования структуры данных необходимо реализовать исполнителя, способного осуществлять предусмотренные над ней операции. Такой исполнитель должен обеспечивать свойство инкапсуляции для данных, объединенных в структуру. Но обычными средствами языка программирования это сделать, увы. не удается, ибо становится неразрешимой проблема: где в программе объявлять данные, чтобы они были доступны всем подпрограммам, совершающим над ними требуемые операции, но недоступны нигде более в остальных местах программы.
Чтобы объединить набор подпрограмм, выполняющих совместные действия над общими данными, скрытыми от остальных частей программы, в языках программирования предусматривается специальная синтаксическая конструкция, называемая модулем [5,гл.5]. В данном пособии поясняется, как такие модули оформляются в программе на языке Турбо Паскаль [6.7] .
Основное содержание пособия посвящено знакомству с типовыми структурами данных, которые наиболее часто применяются при решении практических задач. Для каждой структуры рассматриваются различные формы ее представления и объясняются приемы реализации основных операций. При этом алгоритмы типичных операций оформляются в виде модуля на языке Турбо Паскаль.
Изложенный в пособии материал соответствует семестровому курсу, который автор на протяжении ряда лет преподавал студентам 2-го года обучения факультета Кибернетики ИАТЭ (по специальности "Прикладная математика"). Для его освоения необходимо и достаточно владеть навыками составления программ с использованием стандартных возможностей языка Паскаль.
Автор выражает глубокую благодарность своим коллегам, преподавателям программирования Виноградовой Е.А. и Крылову Е.В., чьи замечания и советы способствовали становлению и совершенствованию курса, положенного в основу этого пособия.

СОДЕРЖАНИЕ
Введение ....... ..................-3
ТИПОВЫЕ СТРУКТУРЫ ДАННЫХ И СПОСОБЫ ИХ ПОСТРОЕНИЯ ... 5
1. МОДУЛИ..........................-5
2. АБСТРАКТНЫЕ ТИПЫ ДАННЫХ ................. 9
3. СПИСКИ В СПЛОШНОМ ПРЕДСТАВЛЕНИИ ............. 14
3.1. Общая характеристика списков, их разновидности:
стек, очередь, дек . . ........•......... 14
3.2. Представление стека на основе массива ......... 16
3.3. Представление очереди на основе массива ........ 18
3.4. Представление дека в форме "кольцевого" массива .... 20
3.5. Список с произвольным доступом на основе массива ... 21
3.6. Список с массивом индексов .............. 23
4. СПИСКИ В ЦЕПНОМ ПРЕДСТАВЛЕНИИ .............. 25
4.1. Указатели и операции динамического распределения памяти 25
4.2. Однонаправленный линейный список ........... 26
4.3. Стек в форме простейшего линейного списка ....... 29
4.4. Очередь в виде линейного однонаправленного списка : . 30
4.5. Двунаправленный линейный список ........... 32
4.6. Дек в форме двунаправленного списка.......... 34
4.7. Кольцевые списки ................... 35
4.8. Иерархические списки ................. 38
4.9. Ассоциативные списки................. 39
5. ДЕРЕВЬЯ.........................41
5.1. Формы представления деревьев и алгоритмы обхода .... 41
5.2. Рекурсивное построение деревьев ............ 44
5.3. Двоичное дерево поиска ........... ..... 45
6. ТАБЛИЦЫ......................... 49
6.1. Линейный поиск................... . 49
6.2. Дихотомический поиск ................. 51
6.3. Поиск хешированием ................. 52
ЗАДАЧИ СО СТРУКТУРАМИ ДАННЫХ ....... .56
7. ЗАДАЧИ НА РЕАЛИЗАЦИЮ ЗАДАННЫХ СТРУКТУР ДАННЫХ ...... 56
7.1. Арифметический стек.................. 56
7.2. Строки........................ 58
7.2.1. Строка со счетчиком длины ............. . 59
7.2.2. Строка с признаком конца .............. 60
7.3. Текст........................ 61
7.3.1. Текст как список строк ............... 62
7.3.2. Текст со списком индексов строк............63
7.3.3. Текст со списком указателей строк .......... 64
7.3.4. Текст как линейный список строк ........... 65
7.3.5. Текст как линейный список указателей строк ..... 66
7.4. Списки студентов курса................ 68
7.5. Деревья родственников..........:...... 72
8. ЗАДАЧИ НА РАЗРАБОТКУ СТРУКТУР ДАННЫХ .......... 75
8.1. Полиномы . . . . •................... 75
8.2. Разреженные массивы (вектора и матрицы) ........ 76
8.3. Списки со свойствами множеств (списки-множества) ... 76
8.4. Последовательности .................. 77
8.5. Массивы во внешней памяти ("виртуальные" массивы) ... 77
Литература......................... 78