Текст
Механико-математический факультет Кафедра вычислительной математики
В.Д. Валединский, Ю.Н. Пронкин
Вычислительные системы
и программирование
II
Механико-математический факультет Кафедра вычислительной математики
В.Д. Валединский, Ю.Н. Пронкин
Вычислительные системы
и программирование II
ББК 32.973
В 25
УДК 681.3
В. Д. Валединский, Ю. Н. Пронкин. Вычислительные системы и программирование II. — М.: Изд-во ЦПИ при механикоматематическом ф-те МГУ, 2000, - 128 с.
Настоящее пособие содержит переботанные и дополненные материалы курса лекций, читавшихся авторами на протяжении нескольких лет на механико-математическом факультете МГУ для студентов 2 курса. Рассматриваются подходы к реализации базовых структур данных (стек, дек, множество, список, дерево И др.).
Для студентов и аспирантов, изучающих программирование и применяющих его в практической работе, а также преподавателей, проводящих практические занятия.
Рецензент: академик РАН Н.С. Бахвалов
© В.Д. Валединский, Ю.Н. Пронкин, 2000 г.
Оглавление
Глава II. Вазовые алгоритмы и структуры 5
1 Введение...................................... 5
2 Замечания о стиле программирования........... 7
3 Объект как способ организации данных......... 10
4 Стек, дек, очередь........................... 17
4.1 Стек................................... 17
4.2 Дек.................................... 28
4.3 Очередь................................ 33
4.4 Упражнения............................. 35
5 Последовательность........................... 37
5.1 Однопроходные алгоритмы................ 37
5.2 Упражнения............................. 48
6 Списки....................................... 48
6.1 Ссылочный подход....................... 48
6.2 Одно- и двунаправленные списки......... 51
6.3 Упражнения............................. 64
7 Деревья...................................... 64
7.1 Определения и обходы................... 64
7.2 Деревья поиска......................... 72
7.3 Сбалансированные деревья поиска........ 79
7.4 В-деревья.............................. 97
7.5 Упражнения.............................103
8 Множества....................................104
8.1 Битовая реализация множества...........106
Оглавление
8.2 Хеширование..........................108
8.3 Упражнения...........................116
9 Контейнеры ................................117
9.1 Контейнер для элементов фиксированного размера.................................119
9.2 Контейнер для хранения текстовых строк . . 120
9.3 Идеи реализации функций типа malloc и free 122
Глава II
Базовые алгоритмы и структуры
1 Введение
Данная глава посвящена логическим схемам представления данных. Здесь разбираются такие базовые понятия как стек, дек, очередь, список, дерево, множество. Подобные структуры в том или ином виде используются во множестве существующих программ обработки данных.
Создание любой программы обычно предполагает принятие решений по двум основным пунктам: выбор способа представления и взаимосвязей данных, необходимых для решения поставленной задачи, и выбор алгоритмов обработки или преобразования этих данных. Безусловно, обе эти проблемы тесно взаимосвязаны. Выбор конкретного алгоритма существенно влияет на способ представления данных, а способ представления данных накладывает ограничения на класс возможных алгоритмов решения. Искусство программирования как раз и состоит в удачном сочетании решений по двум этим пунктам для достижения главной цели — созданию эффективной и надежной
программы.
Логическая проработка алгоритма и способов представления данных играет важную роль, но программа всегда разрабатывается и реализуется в конкретной вычислительной среде с использованием конкретной аппаратуры, компиляторов и операционных систем. Очень часто на разрабатываемую программу накладываются жесткие требования по ее быстродействию, объему используемой памяти, количеству обращений к внешним устройствам и т.п. При этом возникает другая проблема — как разумно согласовать два аспекта практической реализации программы, а именно, с одной стороны — повышение эффективности или удобства в работе за счет учета особенностей аппаратуры и операционной системы, и с другой стороны — сохранение надежности и универсальности за счет использования только стандартных средств. Способом увязки этих противоречий может служить грамотная разработка структуры самой программы с тем, чтобы выделить в исходной постановке задачи части, реализация которых требует учета аппаратных или системных особенностей, и части, которые могут быть реализованы с помощью системнонезависимых средств.
Поскольку обучение программированию невозможно без демонстрации примеров программного кода, при написании этой книги возник вопрос о языке, который будет использоваться для записи алгоритмов. Для этой цели были выбраны языки С и C++. В действительности, алгоритмы управления данными можно было бы описать и с помощью других алгоритмических языков, или даже некотором псевдокоде. Однако здесь, выбирая способ изложения, мы преследовали также и сопутствующие цели: продемонстрировать технику и стиль составления программ, дать примеры, которые можно было бы использовать на практике с минимальными модификациями. Кроме того, языки С и C++ стали в настоящее время общепризнанным средством реализации программ, приближенных к системному уровню работы вычислительной машины.
Таким образом, от читателя требуется знание основ программирования на этих языках и, в частности, принципов работы с указателями и структурами. Хотя в тексте и даются некоторые пояснения, касающиеся примеров программых реализаций, они не могут заменить специальной литературы (см., например, [1, 2,3]).
2 Замечания о стиле программирования
Мы приступаем к изучению форм и способов представления данных, имеющих более сложную организацию, чем просто числа или текстовые символы. Материал этой главы содержит большое количество примеров программного кода. Поэтому сделаем несколько замечаний по поводу формы записи этих примеров.
Стиль программирования — тема, обсуждаемая практически в каждой книге, посвященной разработке программного обеспечения (см., например [6]). Существуют разнообразные мнения о том как формировать имена переменных и процедур, сколькими пробелами выделять вложенные конструкции, каков должен быть максимальный размер отдельной процедуры, что и как комментировать и т.д. Тексты профессионально написанных программ имеют огромное учебное значение, которое трудно переоценить. Рассматривая и изучая такие программы, начинающий программист может составить собственное представление об удобстве того или иного стиля и принять тот, который ему больше по душе, или выработать собственный. Естественно, используемый язык программирования накладывает существенный отпечаток на стиль написания программ. Но не смотря на существующие отличия стилей, в них много общих черт, которые служат двум основным целям — улучшению “читаемости” и упрощению возможных последующих модификаций программ. В этой главе мы тоже будем по возможности придерживаться единого стиля, который в общих чертах описывается следующим пунктами.
• Переменные, функции, макроопределения, типы и пр., несущие в себе определенный смысл, происходящий от решаемой задачи, должны именоваться так, чтобы их названия отражали этот смысл. Как правило, это достигается включением в имя ключевых слов или их естественных сокращений. Подобная практика позволяет исключить излишние комментарии, поскольку имена переменных или функций уже сами по себе много говорят о их назначении.
• Имена, используемые для локальных или временных целей, обычно формируются из одной буквы или буквы с цифрой. Типичный пример — счетчики циклов или текущие индексы массивов, обозначаемые обычно именами ij,k,.. .Для некоторых имен подобного типа могут использоваться общепринятые сокращения: ent — для счетчиков различных количественных величин (counter), tmp — для временных значений (temporary), pos — для обозначения позиций в списках, массивах и пр. (position), err — для кодов ошибок (error), ptr — для указателей (pointer), sre — источники данных (source), dst — приемники данных (destination), и т.п.
• Для обозначения того, что именованные объекты (обычно функции) относятся к некоторой единой группе, в их именах ставится общий префикс, отделяемый от индивидуального названия символом подчеркивания.
• Блоки операторов, вложенные в циклы, условные конструкции и т.п., выделяются пробелами в начале строки. Часто рекомендуют ставить по 8 пробелов на каждый следующий уровень вложенности, но из-за ограниченности ширины страниц в этой книге мы будем ставить по 3 пробела.
• Константные выражения, несущие смысловую нагрузку (коды ошибок, информационные сообщения, пути или имена стандартных файлов и т.п.), определяются с помошью инструкции #define.
• Скобки, ограничивающие блоки операторов ({ и }), ставятся строго одна под другой. Скобки, ограничивающие блоки
описания полей структур ставятся по-другому (см. тексты примеров программ). В случае коротких блоков можно ставить открывающую и закрывающую скобки в одной строке.
• Функции, результат работы которых зависит от состояния различных объектов, как правило, возвращают значение О в случае успешного завершения своей работы и некоторый код ошибки — в случае отказа. Обычно каждому коду ошибки сопоставляется некоторое символическое имя, которое позволяет легко понять его смысл при чтении текста программы. Функции, возвращающие указатель на какие-либо данные, возвращают 0 при невозможности определить требуемый адрес.
• Программа должна быть тщательно прокомментирована. Однако, комментарии не должны быть назойливыми и разъяснять очевидный код. Но там, где смысл параметров, возвращаемых значений, особенностей алгоритмов не совсем прозрачен, должно даваться объяснение. Как правило, основные разъяснения и описание используемых соглашений, назначения переменных и других объектов программы даются в начале файлов или перед заголовками функций, а последующий текст программы должен быть составлен так, чтобы он был понятен сам по себе.
• Программная реализация практически любой задачи должна быть четко структурирована. Функции, отвечающие за логически независимые части алгорима, следует вынести в отдельный файл и снабдить заголовочным файлом с описанием необходимых типов данных и прототипов функций. Естественно, что количество таких файлов зависит от сложности задачи, но в любом случае реализация всей программы в одном единственном файле — признак неудачного стиля.
• Размер текста отдельной функции по возможности должен занимать не более 30-50 строк, чтобы ее можно было
охватить “одним взглядом”. Конечно, из этого правила могут быть исключения, но, как правило, слишком длинные тексты функций свидетельстуют о недостаточной предварительной проработке алгоритма. Пересмотрев алгоритм или способ его реализации, такие функции часто можно разбить на несколько более коротких.
Естественно, описанные правила не являются догмой и не охватывают всех особенностей стиля. Они приведены здесь лишь в качестве примера для того, чтобы, во-первых, облегчить понимание приводимых ниже примеров и, во-вторых, дать представление о том, как правильно читать чужие и составлять собственные программы. Следование стилевым соглашениям может существенно сократить время решения поставленной задачи и значительно повысить надежность работы программы, не говоря уж об эстетическом удоволетворении, получаемом от процесса написания программы и ее демонстрации другим.
3 Объект как способ организации данных
В самом общем виде можно сказать, что целью работы любой компьютерной программы является преобразование некоторого входного набора данных в некоторый выходной набор-результат. Такой подход к определению назначения программы не несет в себе особого глубокого смысла, но порождает некоторые идеи по поводу того, как должна быть организована сама программа. По-видимому, при реализации программы правильным будет такой способ организации данных, который отражает взаимосвязи между данными, присущие исходной постановке решаемой задачи. Подобные взаимосвязи могут иметь различную форму. Например, данные могут быть представлены в виде чисел, текстовых строк, логических значений. Как правило,
исходная задача предполагает объединение данных в некоторые агрегаты, которые могут содержать в качестве составных частей другие, более простые элементы данных (например, массивы, записи, структуры и т.п.). Данные могут быть связаны между собой отношениями подчиненности (зависимые, независимые, производные данные), на доступ или использование данных могут быть наложены разного рода ограничения или условия и т.п. Таким образом, одним из наиболее важных этапов реализации программы для решения конкретной задачи являются проектирование способа представления данных и разработка алгоритмов их обработки.
Рассматривая проблему обработки данных на абстрактном уровне, удобно ввести понятие объекта как некоторого агрегата, обеспечивающего работу с той или иной частью данных задачи. Что мы вкладываем в понятие объекта?
Во-первых — это способ организации данных (деление данных на элементы, определение взаимосвязей между отдельными элементами данных, задание дисциплины доступа к данным).
Во-вторых — это правила модификации данных (алгоритмы), обеспечивающие обработку или преобразование данных.
В третьих — это правила взаимодействия данного объекта с другими объектами (интерфейс).
При таком подходе объекты становятся основой решения прикладной задачи, а программа описывает необходимые объекты в терминах конкретного алгоритмического языка и реализует их взаимодействие с помощью тех или иных функций. Естественно, что любому объекту присущи определенные, характерные именно для этого объекта свойства. Объект может быть создан и может быть уничтожен, он хранит в себе и управляет некоторыми данными, он определяет набор допустимых операций над собой и над управляемыми им данными, он может использовать в своих целях другие объекты или может являться частью другого, более “сложного” объекта. Эти специфические свойства находят свое отражение в понятии тип объекта.
Читатель, знакомый с языком C++, сразу обнаружит, что наше понятие объекта практически тождественно понятию class. Действительно, базовые конструкции языка C++ представляют собой чрезвычайно удобное средство для создания объектов, управляющих данными. Тем не менее, в данной книге мы будем опираться не только на C++, но и на язык С, а также и просто описание алгоритмов на неформализованном “псевдокоде”. Заметим, что решение любой прикладной задачи всегда включает две стороны — осознание того что нужно сделать и того как это можно сделать. Обе эти стороны тесно взамосвязаны и сильно влияют друг на друга, но все-таки надо стремиться к тому, чтобы с учетом всех дополнительных соображений об эффективности реализации и трудоемкости разработки воплощать решение в программу в терминах наиболее подходящего для этого алгоритмического языка, а не решать задачу на языке С (или C++, Java, Fortran и т.п.), заранее накладывая на себя синтаксические и семантические ограничения выбранного языка.
В рамках данной учебной книги мы попытаемся представить различные способы реализации объектов — и как классов языка C++, й как функций языка С с тем, чтобы читатель мог лучше прочувствовать “кухню” программирования, увидеть проблемы, возникающие при взаимодействии данных и в дальнейшем более осознано принимать решения об использовании тех или иных языковых средств.
При решении задачи и реализации связанных с ней данных нам могут потребоваться некоторые дополнительные объекты: для хранения результатов промежуточных вычислений, для хранения информации о текущем состоянии программных объектов, для обеспечения интерфейса с другими объектами и т.д. Таким образом, с каждым объектом можно связать понятие его внутреннего представления.
Основа внутреннего представления • это конкретные формы размещения данных в памяти компьютера, способы интерпрета
J
ции и алгоритмы обработки. В этом смысле базовым уровнем является память компьютера, которую мы в простейшем случае можем рассматривать как одномерный массив байтов. Таким образом, проблема управления данными, расположенными в памяти, тесно переплетается в понятием адреса размещения данных (адресом объекта). Механизм работы с указателями, имеющийся в языках С и C++ является мощным аппаратом для работы с данными на уровне внутреннего представления. Однако использование указателей (как, впрочем, и классов) не должно становиться самоцелью. Поэтому в каждом конкретном случае программист должен принимать свое решение о способе внутреннего представления объекта.
Дисциплина работы с данными, реализованная в объектах конкретного типа, определяет правила использования этих объектов. На этом уровне внутренне представление уже становится несущественным — объект выступает как единое целое. Здесь мы приходим к понятию внешнего представления илй внешнего интерфейса объекта, посредством которого программист может использовать объект в своих целях. Внешнее представление фактически является своего рода “руководством пользователя”, в котором четко зафиксированы способы использования объекта (описаны прототипы функций) и результаты выполнения операций (возвращаемые значения, коды ошибок и т.п.).
Заметим, что правильно реализованный объект должен по возможности обеспечивать защиту своих внутренних данных от случайной порчи в результате некорректного использования. Способ достижения такой защиты может быть различным и сильно зависит от особенностей используемого алгоритмического языка. Для языка С этого можно добиться с помощью ограничения области видимости переменных и функций, размещая их в отдельных файлах, используя класс памяти static и т.п., для языка C++ решением будет грамотное использование атрибутов public, private, protected и т.д.
Итак, в каждый момент времени объекту соответствуют:
• на внешнем уровне — конкретное значение и (или) набор реализуемых операций (функций, методов);
• на внутреннем уровне — способ представления данных в памяти, конкретные алгоритмы обработки данных.
Простейшим примером объекта является переменная. Например, следующая запись на языке С
double a,b,c;
определяет в программе три объекта типа double, которые позволяют хранить числовые значения из некоторого подмножества вещественных чисел и осуществлять с ними арифметические операции. В данном тривиальном примере внутреннее представление характеризуется количеством байт, отводимых для хранения числа, а также способом интерпретации отдельных битов, содержащихся в этих байтах (какие биты относятся к порядку или мантиссе, как определить знак числа и т.д.). Внешнее представление определяет набор допустимых операций с этими объектами (например, мы можем выполнять арифметические операции с объектами типа double, но не имеем права индексировать ими элемент массива).
Традиционные языки программирования имеют некоторый набор встроенных базовых типов объектов. Для языка С такими базовыми типами являются целый (char, int, а также их модификации short, long, signed, unsigned) и вещественный (float, double). Конкретный язык программирования может также предоставить средства для конструирования более сложных объектов, таких как массивы, структуры, объединения, классы и пр. Помимо чисто языковых средств, многие системы программирования предоставляют пользователю достаточно богатые библиотеки с разнообразными заготовками для построения различных объектов. Поэтому в каждом конкретном случае следует решить, что проще — реализовать требуемый объект “с нуля” самому или собрать его из готовых блоков. При этом, однако, следует иметь в виду, что подобные готовые блоки могут
не совсем подходить к специфике решаемой задачи или быть недостаточно эффективными в конкретном случае. Возможно также, что для изучения и освоения имеющихся библиотечных заготовок потребуется значительное время, а готовая программа станет привязанной к определенной системе программирования и окажется непереносимой на другие компиляторы и операционные системы.
Предполагая у читателя знакомство с основами программирования на языке С, мы будем рассматривать в этой главе объекты, назначение которых — хранить наборы данных, добавлять или удалять данные, а также обеспечивать доступ к этим данным в соответствии с той или иной дисциплиной. Обеспечение ука-занных требований предполагает определенное структурирование данных, поэтому в дальнейшем мы будем называть такие объекты структурами данных.
Учитывая вышесказанное, мы можем разделить операции с объектом и данными на несколько категорий:
• создание и уничтожение объекта в целом;
• доступ к значениям хранящихся элементов данных;
• добавление и удаление данных;
• опрос состояния объекта.
Смысл этих категорий достаточно прозрачен, пояснения требует, разве что, последняя. Дело в том, что при добавлении или удалении элементов, а также при других действиях с объектом, он может прийти в такое состояние, при котором выполнение некоторых операций окажется некорректным, невозможным или даже опасным. Для контроля за подобными ситуациями надо располагать способом обнаружения таких состояний, что и находит свое выражение в операциях опроса состояния объекта.
Развитие методов программирования и анализ практических задач привели к выделению нескольких базовых дисциплин хранения и доступа к наборам данных, которые получили названия стек, дек, очередь, последовательность, список, дерево,
множество. Далее мы рассмотрим их подробно, а пока заметим, что существующие алгоритмические языки сами по себе, как правило, не имеют подобных встроенных типов объектов. С другой стороны, многие конкретные системы программирования имеют инструментальные библиотеки разработки, в которых обычно содержатся реализации подобных структур. Примеры, рассматриваемые в этой книге, помогут принять правильное решение о том, что удобнее сделать в конкретном случае — составить свою программу или воспользоваться готовой библиотечной функцией.
В этой главе мы будем рассматривать структуры данных, объединяющих в себе некоторый набор элементов одного и того же типа. Для простоты изложения будем считать, что каждый элемент данных занимает один и тот же объем памяти и допускает применение операции присваивания в смысле языка С, хотя все основные идеи можно перенести на элементы, не подходящие под эти ограничения, если немного усложнить примеры программ. (В частности, для сложных составных объектов присваивание всегда можно заменить вызовом функции копирования, а в языке C++ — переопределить оператор присваивания для объектов требуемого класса.)
Для повышения универсальности примеров мы будем обозначать этот абстрактный тип данных символом Туре. При тестировании или использовании примеров программ, приводимых далее, необходимо лишь добавить в текст явное определение этого типа. Например, для структуры данных, элементами которой являются целые числа, достаточно записать
typedef int Type;
Если же требуется работать с текстовыми строками (указателями на строки), то указанный тип можно определить как
typedef char* Type;
Для структуры, представляющей собой учетную запись о конкретном человеке в некоторой таблице (имя, возраст, рост, вес), это определение может выглядеть, например, так
typedef struct {
char name[20] ; int age;
double height, weight;
} Type;
Поскольку конкретный тип элемента данных не является существенным для изложения дисциплины работы с рассматриваемыми структурами, мы не будем заострять внимание на его определении в последующих примерах, предполагая, что читатель может при необходимости переопределить этот тип по собственному усмотрению.
4 Стек, дек, очередь
4.1 Стек
В программировании (да и в реальной жизни) мы часто сталкивается со способом организации данных, при котором накопление и обработка их значений разделены по времени и при этом элемент, появившийся последним, обрабатывается в первую очередь. Такой способ “обслуживания” используется, например, в автоматическом оружии, где патрон, заряженный в обойму последним, выстреливает первым. Эта дисциплина доступа часто обозначается аббревиатурой LIFO (от слов Last In — First Out) и находит свое воплощение в понятии стека. Естественно, примеры стекового доступа к данным не ограничиваются автоматом Калашникова. Дисциплина LIFO обычно используется в вычислительных системах при организации последовательных вызовов подпрограмм для сохранения данных, необходимых для продолжения работы функции, вызвавшей в ходе своего выполнения другую процедуру. Использование стеков при выполнении программ процессором было подробно рассмотрено в главе I. Можно привести и другие примеры, когда дисциплина LIFO является весьма удобной для организации обработки
данных. Итак, стек — это некоторая динамическая структура, позволяющая хранить, добавлять и изымать элементы данных по дисциплине LIFO. Абстрактный стек можно представить как “трубу”, закрытую с одного конца, где элементы данных закладываются или изымаются из этой “трубы” через другой открытый конец.
Элемент, к которому в данный момент можно получить доступ (т.е. последний добавленный элемент) называется вершиной стека. Естественно, что при практической реализации стека его “труба” не может быть бесконечно длинной, т.е. мы должны предусмотреть возможные ограничения на максимальное количество элементов, которые может вместить в себя данный стек.
“дно” “веошина” добавление
Рис. 4.1. Схема стека.
С точки зрения программирования построение стека должно заключаться в выделении некоторого участка памяти для хранения элементов данных (создание той самой “трубы”) и составлении набора функций, реализующих допустимые (в смысле дисциплины LIFO) операции по добавлению и удалению данных, а также доступу к этим данным. Набор этих функций мы будем называть системой предписаний (или команд) объекта “стек”. Фактически, система предписаний некоторого объекта однозначно определяет способы работы с этим объектом и является воплощением понятия “типа объекта” на внешнем уровне. Система предписаний должна быть полна в том смысле, что она, во-первых, позволяет полностью реализовать требуемую дисциплину работы с данными, и, во-вторых, дает возможность контролировать состояния объекта с тем, чтобы не допустить возникновения некорректных ситуаций при работе с ним.
Примерами некорректных ситуаций для стека могут служить попытка добавить новый элемент данных, когда стек уже заполнен “до предела”, или попытка извлечь элемент из стека, когда в нем нет ни одного элемента.
Попытавшись сформулировать систему команд объекта стек, мы можем прийти, например, к такому набору предписаний.
• Создать стек.
• Уничтожить стек.
• Добавить элемент в стек.
• Удалить вершину стека.
• Взять элемент из стека.
• Прочитать вершину стека.
• Изменить вершину стека.
• Есть место в стеке?
• Стек пуст?
Эта система предписаний полна в описанном выше смысле. Более того, она даже избыточна, поскольку некоторые предписания элементарно реализуются через другие (например, “взять элемент из стека” сводится к последовательному выполнению предписаний “прочитать вершину стека” и “удалить вершину стека”). Тем не менее мы оставим ее в таком виде, так как различные предписания могут оказаться более удобными в тех или иных ситуациях.
Для практической реализации эту систему предписаний следует уточнить. Действительно, в ней много неясностей, поскольку не разъясняется в чем конкретно должен заключаться результат каждой операции, какие параметры требуются для выполнения операций. Поэтому подойдем к построению системы предписаний более формально, а именно опишем прототипы функций, которые будут реализовывать каждое из предписаний, а заодно добавим несколько дополнительных операций, которые могут оказаться Удобными для работы. Этот шаг создает мост между внешним и внутренним представлением стека, поэтому здесь нам придется
определиться с используемым языком программирования. Взяв за основу язык С, мы составим предварительные описания функций объекта “стек”. В практическом программировании подобные описания обычно выделяются в отдельный файл для обеспечения интерфейса с другими программными модулями. В данном случае мы назовем этот файл stack. h. Для определенности будем считать, что тип Туре определяется в этом же файле как int. Итак, мы можем составить такие описания:
/♦
* Файл stack.h
♦ С-реализация стека элементов типа Туре
♦/
«ifndef STACK.H.INCLUDED «define STACK.H.INCLUDED
typedef int Type;
int St«Init (int maxsize); /♦ создать стек ♦/
void St_Term (void); /♦ уничтожить стек ♦/
int St «Push (Type value); /♦ добавить элемент в стек ♦/
int St-Pop (Type *dst); /♦ взять элемент из стека ♦/
int St.Del (void); /♦ удалить вершину стека */
int St-GetTop (Type *dst); /♦ прочитать вершину стека ♦/
int St-SetTop (Type value); /♦ изменить вершину стека ♦/
int St-Size (void); /♦ текущий размер стека ♦/
int #endif /♦ St.Room (void); /♦ есть место в стеке? ♦/
* конец файла stack.h
♦/
Комментарии к реализации.
Теперь можно пояснить смысл каждой функции.
St«Init. Создается стек для хранения не более maxsize элементов типа Туре. Функция возвращает maxsize, если стек создан, и —1, если создать не удалось.
St «Term. Уничтожается стек, созданный ранее функцией St.Init.
St Push. Элемент, определяемый параметром value, добавляется в стек. Возвращаемое значение — количество элементов в стеке после добавления или -1, если добавить не удалось.
St_Pop. Значение элемента на вершине стека копируется в объект, определяемый указателем dst, вершина стека удаляется, функция возвращает количество элементов в стеке после удаления или -1, если стек был пуст (в этом случае присваивания не происходит).
St-Del. Вершина стека удаляется. Возвращаемое значение — как в функции St.Pop.
St-GetTop. Функция работает точно так же, как и St-Pop, но вершина стека при этом не удаляется.
St-SetTop. Значение существующей вершины стека заменяется на значение value. Возвращаемое значение — количество элементов в стеке или ~ 1, если стек был пуст (в этом случае присваивания не происходит).
St.Size. Функция возвращает количество элементов в стеке.
St-Room. Функция возвращает число незанятых “мест” в стеке.
Перейдем теперь к реализации этих функций. Выделим блок памяти, достаточный для размещения всех элементов стека, и будем хранить указатель на вершину, который будет сдвигаться по мере добавления или удаления элементов. Здесь нам придется принять решение о том в какую сторону будет “расти” стек — от меньших адресов к большим или наоборот. Принципиальной разницы в этих двух вариантах нет. Поэтому примем, что стек “растет” от бблыпих адресов к меньшим. Итак, указатель top будет установлен на элемент, являющийся в данный момент вершиной стека. Нам также будет удобно хранить текущее количество элементов в стеке, для чего мы выделим переменную size.
/♦
* Файл stack.с
♦ С-реализация стека элементов типа Туре
♦ /
/* прототипы функций и типы данных ♦/ tindude <stdlib.h> tinclude "stack.h"
/♦ внутренние объекты стека ♦/
static Type *mem; /♦ начало области эл-тов стека ♦/
static Type *top; /♦ указатель на вершину стека ♦/
static int size; /* текущее количество элементов ♦/
/* реализация функций ♦/ int St.Init (int maxsize)
{ size = 0;
if ( top=mem=malloc(sizeof(Type)♦maxsize) ) top+=maxsize;
return (mem) ? maxsize : -1;
}
void St.Term (void)
{ if ( mem ) free (mem);
size = 0;
}
int St„Push (Type value)
{ return (top!=mem) ? ♦(—top)=value, ++size : -1; }
int St.Pop (Type *dst)
{ return (size) ? *dst=*(top++), —size : -1; }
int St„Del ()
{ return (size) ? ++top, --size : -1; }
int St.GetTop (Type *dst)
{ return (size) ? *dst=*top, size : -1; }
int St.SetTop (Type value)
{ return (size) ? *top=value, size : -1; }
int St.Size (void) { return size; }
int St„Room (void) { return top-mem; }
/*
* конец файда stack.c
♦/
Комментарии к реализации. Переменные mem, top, size
являются внутренними для объекта “стек”, но глобальными для всех его функций. В идеальном варианте они должны быть доступны только в этих функциях, поскольку в противном случае некорректное действие в какой-либо внешней программе может полностью разрушить стек. Для обеспечения защиты этих переменных используется класс памяти static в предположении, что данный текст помещен в отдельный файл.
Лаконичность записи — неотъемлемое достоинство языка С. Поэтому при реализации функций St.Push и St_Pop мы постарались “выжать” все возможное из специфических особенностей синтаксиса языка. Напомним, то конструкция
<условие> ? <выражение_1> : <выражение_2>
называется условным выражением и принимает значение первого выражения, если “условие” отлично от нуля, и второго выражения в противном случае. Операция объединяет отдельные выражения в составное выражение, значением которого является значение последнего выражения. Конечно, погоня за лаконичностью не должна становиться самоцелью, очень часто она вступает в противоречие с наглядностью алгоритма и ясностью программы. Однако в данном конкретном случае мы сознательно не стали использовать традиционную конструкцию if - else, поскольку идея алгоритма в этих элементарных функциях чрезвычайно проста, а указанный способ дает более эффективный код.
В данной реализации мы сознательно отказались от возвращения каких бы то ни было указателей на рабочие области стека. Возвращение указателя в качестве результата работы функции является потенциально опасной операцией, поскольку последующая запись по этому указателю ошибочного количества байт может разрушить и другие данные программы. Поэтому доступ к вершине стека реализован в виде двух функций — чтения и записи. Такой способ гарантирует, что при изменении значения вершины стека не будут случайно испорчены значения соседних элементов стека.
Конечно, представленные здесь варианты программ не являются единственно возможными. Они служат, скорее, для иллюстрации одного из подходов к построению объекта. При решении конкретных задач может оказаться, что данный способ реализации стека не является оптимальным или даже вообще неприемлем. Приведенный выше вариант предполагает, что в программе будет использоваться только один экземпляр стека, хотя часто возникает необходимость иметь несколько независимых стеков. Решение этой проблемы путем создания копий функций для каждого стека (например, Stl.InitO, St2_Init() и т.д.) выглядит довольно неуклюжим. Более правильным было бы решение о разделении областей данных для хранения элементов каждого стека и введении во все функции дополнительного параметра, идентифицирующего область данных конкретного стека, с которым в данный момент нужно работать. Для нашей реализации область данных, описывающая конкретный стек, содержит три значения — mem, top, size. Поэтому мы можем объединить их в одну структуру, с которой свяжем тип Stack.d (от слов stack data), и предложить реализацию следующего вида.
typedef struct { Туре ♦mem, *top; int size; } Stack.d;
Stack.d ♦ St.Init (int maxsize)
{ Stack.d ♦stj_($fod^^*^
if ( !(st=malloc(sizeof(Stack.d))) ) return 0;
st->size = 0; СЪре*)
if ( st->top=st->mem=4ialloc(sizeof(Type)♦maxsize) ) st->top += maxsize;
else {free(st);return 0;} return st;
} void St.Term (Stack.d *st) { if ( st->mem )
{ free (st->mem); _
if ( st ){free (st); Srt-iMLJ
int St.Push (Stack.d *st, Type value)
{ return (st->top!=st->mem) ?
♦(—st->top)=st->value, ++st->size : -1;
}
Остальные функции реализуются по аналогии.
Комментарии к реализации. В данном случае функция инициализации стека St_Init возвращает указатель на область данных создаваемого при этом нового стека. Далее этот указатель служит параметром, идентифицирующим конкретный стек для остальных функций. При отказе в создании стека (например, по нехватке памяти) эта функция возвращает нулевой указатель.
Функция завершения работы St.Term освобождает память, захваченную стеком. Это делается в два этапа. Сначала освобождается область, занятая элементами стека, а потом — область служебных переменных, определяющих состояние стека.
Следует заметить, что реализация, построенная таким образом, тоже является не совсем удачной. Внешние программы получают полный доступ к внутренним данным объекта стек через указатель, возвращаемый функцией St.Init. Случайное изменение этих данных в результате ошибки в программе может разрушить весь стек. Более правильным решением было бы создать массив указателей на подобные структуры типа Stacked, который являлся бы внутренним глобальным объектом набора функций стека (т.е. был бы объявлен как static в файле stack.c). Функция инициализации должна возвращать номер свободного индекса в этом массиве, и этот индекс далее должен использоваться как дескриптор нужного стека. Поскольку область данных для стеков теперь уже становится недоступной извне, то мы получаем необходимую защиту реализации. Однако теперь мы должны заранее определить какое максимальное количество стеков нам может понадобиться во время работы.
Нам становится тесно в рамках языка С, когда мы пытаемся аккуратно реализовать несколько однотипных объектов, которые владеют разными данными, но имеют общие алгоритмы обработки этих данных. Удобные средства для решения этой
проблемы предоставляет язык C++. Заметим, что использование C++ позволяет также полностью абстрагироваться от конкретного типа элементов данных. Это обеспечивается средствами шаблонов (template). Изложение концепций языка C++ не входит в цели данной книги (для этого можно порекомендовать книги [2, 3]), поэтому здесь мы будем приводить реализации на C++ лишь как примеры использования средств обектно-ориентированного программирования для построения структур данных, иллюстрируя возможности избирательного сокрытия данных.
Итак, построим реализацию стека.
И
И Ъвкл stack.h
И Параметризованная C++ реализация стека
//
#ifndef STACK.H.INCLUDED
tdefine STACK.H.INCLUDED
tdefine DEFAULT-SIZE 10
teoqplate <class Type> class Stack { private:
Type ♦mem, ♦top; int size;
public:
11 Конструктор и деструктор Stack ( int maxsize = DEFAULT-SIZE ) { mem = new Type [maxsize];
top = mem + maxsize; size = 0;
"Stack () { delete [] mem; }
// Методы работы co стеком int Push (Type value)
{ return (top!=mem) ? ♦(—top)=value, ++size : -1; } int Pop (Type & dst)
{ if (size) ? dst=*(top++), —size : -1; } int Del () { if (size) ? ++top, —size : -1; }
int SetTop (Type value)
{ return (size) ? *top=value, size : -1; }
int GetTop (Type *dst)
{ return (size) ? ♦dst=*top, size : -1; } int Size () { return size; }
int Room () { return top-mem; }
};
#endif
//
// конец файла stack.h
//
Коментарии к реализации. Алгоритмическая сторона этой реализации полностью повторяет С-реализацию. Главное отличие состоит в использовании средств создания объектов и защиты данных, присущих языку C++. Возможность избирательного сокрытия данных — одна из главных черт языка C++. Поэтому здесь совершенно естественно объявить переменные mem, top, size как private, ограничив тем самым доступ к этим переменным извне и разрешив его только членам класса стек.
При построении конструктора мы воспользовались возможностью задания параметров по умолчанию. Таким образом в нашем случае объявления
Stack<int> а(20);
Stack<double> Ъ;
создадут стек а на 20 целых чисел и стек b на 10 вещественных чисел.
Заметим, что при выделении памяти для хранения элементов в конструкторе (оператор new) возникает определенная проблема, связанная с контролем успешности этой операции. В обычной С-реализации мы можем проверить значение, возвращаемое функцией St.Init, но конструктор объекта в C++ не возвращает значения. Наиболее простой способ решения этой проблемы — добавить в члены класса Stack еще одну функцию, возвращающую 1 при успешном выделении памяти и 0 — в противном случае:
int Success () { return (mem) ? 1 : 0; }
Правда, при этом возникает другая проблема. При отказе в выделении памяти в С-реализации мы могли попытаться еще раз вызывать функцию St_Init с меньшим значением maxsize или освободить захваченную, но ненужную пока память и повторить попытку. В языке C++ стек окажется созданным, но будет неработоспособным. Таким образом, мы можем обнаружить отказ, но не можем сразу же исправить ситуацию (по крайней мере, для предлагаемой выше реализации), поскольку созданный стек будет уничтожен только при выходе из области его видимости. Корректное разрешение этой проблемы требует использования механизма исключений языка C++ (exception и try-блоки) (см. {2,3]).
Заметим, что достоинство или недостаток той или иной реализации — понятия относительные. Например, реализация на языке C++, наиболее лаконичная и элегантная из приведенных здесь, может оказаться неприемлемой с точки зрения переносимости программы (представьте себе, что программа должна разрабатываться и выполняться на компьютере, где по каким-то причинам нет компилятора C++, или данная версия языка не поддерживает параметризацию template). Поэтому еще раз напомним, что приведенные примеры иллюстрируют возможные подхода, а какому из них следовать —- зависит от конкретной ситуации и личного опыта.
4.2 Дек
Название дек (deque) происходит от аббревиатуры английских слов Double Ended QUEue, что означает “очередь с двумя концами”. Тем не менее, мы обсудим понятие дека раньше понятия очереди. Как и стек, дек можно представить в виде “трубы”, только открытой с обоих концов. При этом добавление, удаление и доступ к элементам может осуществляться как с одного конца (начало дека), так и с другого конца (конец дека).
добавление “начало” “конец” ^добавление
удаление^ "^удаление
Рис. 4.2. Схема дека.
Другую интерпретацию дисциплины доступа к элементам дека можно получить, если представить себе, что два стека “склеили” по закрытым концам, а затем убрали возникшую между ними перегородку. Таким образом, система предписаний объекта дек получается из системы предписаний стека простым Сдвоением команд^ имеющих дело с добавлением или удалением элементов.
• Создать дек.
• Уничтожить дек.
• Добавить элемент в начало / конец дека.
• Взять элемент из начала / конца дека.
• Удалить элемент из начала / конца дека.
• Прочитать начало / конец дека.
• Изменить начало / конец дека.
• Есть место в деке?
• Дек пуст?
По аналогии с функциями, реализующими стек, можно описать прототипы функций дека. Приведем их здесь без дополнительных комментариев.
/♦
* Файл deque.h
* С-реализация дека элементов типа Туре
♦/
«ifndef DEQUE_H_INCLUDED
«define DEQUE_H_INCLUDED /♦ типы данных ♦/
typedef ..... Type; /♦ тип элементов ♦/
/♦ прототипы функции ♦/
int Dq^Init (int maxsize); /♦ Создать дек ♦/
void Dq.Term (void); /♦ Уничтожить дек ♦/
int Dq_PushHead (Type value); /♦ Добавить в начало ♦/
int DqJhishTail (Type value); /♦ Добавить в конец ♦/
int Dq_PopHead (Type *dst); /♦ Взять из начала ♦/
int Dq_PopTail (Type *dst); /♦ Взять из конца ♦/
int Dq_DelHead (void); /♦ Удалить начало ♦/
int Dq_DelTail (void); /♦ Удалить конец ♦/
int Dq.Getfiead (Type *dst); /♦ Прочитать начало ♦/
int Dq_GetTail (Type *dst); /♦ Прочитать конец ♦/
int Dq.SetHead (Type value); /♦ Изменить начало ♦/
int Dq_SetTail (Type value); /♦ Изменить конец ♦/
int Dq.Size (void); /♦ Количество элементов ♦/
int Dq.Room (void); /♦ Свободное место ♦/
#endif
/♦
♦ конец файла deque.h
♦/
Однако, разумную реализацию дека нельзя получить непосредственно на основе реализации стека. Действительно, если мы выделим некоторый блок памяти для хранения элементов дека и будем размещать элементы по аналогии с их размещением в стеке (т.е. рядом друг с другом), то в какой-то момент времени состояние дека вполне может принять следующий вид:
“начало”
“конец”
Рис. 4.3. Дек с заполненным началом и свободным концом.
В данной ситуации становится непонятным, как выполнить операцию добавления нового элемента в начало дека. С одной стороны, “законное” место нового элемента выходит за границы зарезервированного блока памяти, и мы не имеем права его добавлять, с другой стороны, у нас имеется достаточно места для размещения элементов со стороны конца дека, которое в данной ситуации можно было бы использовать. Очевидно,
что решение “подвинуть” все элементы дека вправо на одну позицию, чтобы освободить место для добавляемого элемента, является совершенно неприемлемым, так как вызывает пересылку большого количества данных из одного места памяти в другое (столько, сколько элементов хранится в данный момент в деке). Правильным решением здесь будет организация кольцевого буфера.
Разместим новый элемент в позицию maxsize-1. В результате мы нарушим “непрерывность” размещения элементов, поэтому будем описывать их взаимную связь в терминах “следующий” и “предыдущий”. Итак, предыдущей для позиции 0 будет позиция maxsize-1, а следующей для позиции maxsize-1 будет позиция 0. В остальных случаях данная позиция отличается от следующей или предыдущей на единицу. Таким образом, при добавлении в начало дека элемент размещается в предыдущей позиции относительно начала, а при добавлении в конец — в следующей относительно конца. Вычисление следующей и предыдущей позиции можно выполнять, например, такими функциями:
int Next (int k) { return (k<maxsize-l) ? k+1 : 0; } int Prev (int k) { return (k>0) ? k-1 : maxsize-1; }
Однако в реализации, приведенной ниже, мы будем вычислять не номер позиции, а непосредственно указатель на место размещения нового элемента. Как и для стека, будем хранить указатели на начальный и конечный элементы дека (head и tail), а также указатели на начало и конец области памяти, выделенной для размещения элементов (mem и endmem).
Рис. 4.4. Указатели внутреннего представления дека.
Заметим, что пустому и полностью заполненному деку соответствует одно и то же взаимное положение указателей на начало
и конец дека: в обоих случаях tail указывает на предыдущую позицию по отношению к head. Следовательно, мы не сможем различить эти два состояния, имея в своем распоряжении только два указателя. Для решения этой проблемы будем также хранить количество элементов в деке (size). В качестве примера приведем фрагменты реализации дека, основывающуюся на сделанных выше замечаниях. Как й для стека, функции, добавляющие или удаляющие элементы, возвращают количество элементов в деке, если операция выполнилась успешно, и —1 в противном случае.
/♦
* Файл deque.с
* С-реализация дека элементов типа Туре
♦/
/♦ прототипы функций и типы данных ♦/
# include <stdlib.h> /♦ malloc и free ♦/
tinclude “deque.h“
/♦ внутренние объекты дека ♦/
Type *mem; /♦ качало выделенной памяти ♦/
Type ♦endmem; /♦ конец выделенной памяти ♦/
Type ♦head, ♦tail; /♦ начало и конец дека ♦/
int size; /♦ кол-во элементов ♦/
/* реализация функций ♦/ Type ♦Next (Type *pos)
{ return (pos==endmem) ? mem : pos+1; }
Type ♦Prev (Type *pos)
{ return (pos==mem) ? endmem : pos-1; }
int \Dq_Init (int maxsize)
{ mem -malloc( sizeof(Type)♦maxsize );
if ( !mem ) return 0;
endmem = mem + maxsize-1; head = mem; tail = endmem; size = 0;
return maxsize;
int Dq.PushHead (Type value)
{ if ( Dq.RoomO )
{ head = Prev(head); ♦head = value; return ++size; }
else return -1;
int Dq.PopHead (Type *dst)
{ if ( DqJSizeQ )
{ *dst = *head; head = Next(head); return —size; } else return -1;
int Dq.PushTail (Type value)
{ if ( Dq.RoomO )
{ tail « Next(tail); ♦tail=value; return ++size; } else return -1;
int Dq.PopTail (Type *dst)
{ if ( Dq.SizeO )
{ *dst = «tail; tail = Prev(tail); return —size; } else return -1;
}
int Dq.Room (void)
{ return (endmem-mem)+1-size; }
/♦
♦ конец файла deque.с
♦/
Остальные функции реализуются аналогично достаточно очевидным образом, и мы их здесь приводить не будем.
4.3 Очередь
Очередь можно рассматривать как частный случай дека, если выбросить предписания “добавить в начало”, “взять из конца” и ограничиться возможностью доступа только к начальному элементу. В такой трактовке очередь вполне соответствует ее обыденному смыслу, когда поступивший (добавленный в конец) элемент продвигается к ее началу по мере изъятия из начала очереди стоящих перед ним элементов. Эта дисциплина хранения и обслуживания данных часто описываётся термином FIFO, который происходит от слов first in — first out (первым пришел — первым уйдешь).
‘начало”
‘конец” добавление
удаление
Рис. 4.5. Схема очереди.
Реализация очереди тождественна реализации дека (если выкинуть соответствующие функции), поэтому для разнообразия приведем здесь пример на языке C-h-h и несколько изменим названия функций.
И
И Файл queue.h
И Параметризованная C++ реализация очереди
//
«ifndef QUEUE-H-INCLUDED
«define QUEUE-H-INCLUDED
«define DEFAULT-SIZE 10
template <class TYPE> class Queue
{ private:
Type ♦mem, ♦endmem; // границы выделенной памяти Type *head, ♦tail; // начало и конец очереди int size; // количество элементов
Type ♦ Next (TYPE ^pos) // очередная позиция
{ return (pos==endmem) ? mem : pos+1; } public:
// Конструктор
Queue ( int maxsize = DEFAULT-SIZE )
{ head = mem = new Type [maxsize] ; tail = endmem = mem + maxsize - 1; size = 0;
}
11 Деструктор
"Queue () < delete [] mem; }
// Методы работы с очередью int Put (Type value) // добавить элемент { return RoomO ?
♦(tail=Next(tail)) = value, ++size : -1; } int Take (Type ftvalue) // взять элемент { return SizeO ?
value = ♦head, head = Next(head), —size : -1;
} int Del О // удалить элемент
{ return SizeO ?
head = Next(head), —size : -1; } int Set (Type value) // изменить начало
{ return SizeO ? ♦head = value, size : -1; } int Get (Type &value) // прочитать начало
{ return SizeO ? value = ♦head, size : -i; } int Size 0 { return size; } // кол-во элементов
int Room 0 { return (endmem-mem)+1 -size; }
#endif
//
// конец файла queue.h
//
4.4 Упражнения
4.1. Составьте полные реализации стека, дека, очереди. Придумайте тестирующие программы для этих реализаций, которые бы выводили на экран в наглядной форме состояние этих структур и проверяли работу всех функций. Попробуйте вызвать функции реализации в некорректной ситуации (например, удалить элемент из пустой структуры, добавить в полностью заполненную). К каким последствиям это может привести в вашей реализации? Как должны быть составлены функции, чтобы снизить риск потерь от некорректного обращения к ним? Как может повлиять защита от некорректного вызова на быстродействие реализации в целом?
4.2. Составьте совместную реализацию двух стеков на базе одного блока памяти (один стек растет от начала “вверх”, другой
— от конца “вниз”).
4.3. Составьте реализацию нескольких независимых однотипных стеков на базе одного набора функций. Для задания того, сколько всего стеков может быть создано, следует предусмотреть функцию
int St.InitTotal (int n);
где параметр п определяет максимальное число стеков. Остальные функции реализуют те же операции, что и ранее, но имеют дополнительные параметр — номер конкретного стека. Например,
int St.Init (int k, int maxsize);
int St_Push (int k, Type value);
и т.д. Реализация должна обнаруживать попытку обращения к неинициализированному или несуществующему стеку.
4.4. Реализуйте стек, дек, очередь на языке C++ с использованием параметризованных типов (template). Составьте тестирующие программы, которые одновременно создают несколько указанных структур данных для элементов различных типов.
4.5. Реализуйте стек элементов типа char*. На основе этой реализации составьте программу, которая выводит строки текстового файла в порядке, обратном их появлению в файле. (Каждая строка размещается в памяти с помощью функции malloc, можно считать, что количество строк в файле не превосходит заданной величины.)
4.6. Пусть в памяти записан некоторый текст, каждая строка этого текста завершается символом перевода строки (’\п’). Известен начальный адрес размещения текста (указатель) и общее количество символов (включая концы строк). Реализуйте процедуры добавления и удаления строк в конце текста по стековому принципу. Максимальный размер текста не должен превосходить заданного количества символов.
4.7. Реализуйте стек записей заданной фиксированной длины на базе файла. При добавлении записи в стек эта запись
дописывается к концу файла. При чтении — считывается последняя запись файла. При удалении из стека-файла записи нужно корректировать размер файла (например, с помощью функции truncate).
4.8. Постройте реализацию стека строк на основе объединения идей упражнений 4.6-4.7. При небольшом количестве строк все они размещаются в буфере оперативной памяти. При увеличении размера стека в памяти часть буфера в виде отдельных записей переписывается в файловый стек. При освобождении стека в памяти эти записи последовательно считываются из файла обратно в память.
4.9. Классической задачей, использующей понятие стека, является задача о “Ханойской башне” — требуется переместить кольца “детской пирамидки” с одного стержня на другой в том же порядке, имея еще один стержень для откладывания колец, причем не разрешается класть большее кольцо сверху на меньшее. Программное решение этой задачи легко получается на базе реализации трех стеков и рекурсивного алгоритма перемещения элементов. Составьте программу решения этой задачи с визуализацией процесса перемещения элементов пирамидок.
5 Последовательность
5.1 Однопроходные алгоритмы
Последовательность — это еще один способ организации данных, смысл которого состоит в том, что в каждый момент времени мы имеем доступ к некоторому “очередному” элементу данных и, обработав его, можем перейти к обработке “следующего”. При этом обработанный элемент не удаляется из набора данных, но мы уже не можем вернуться к нему просто так. Единственный способ повторно получить доступ к уже обработанным элементам — это встать в самое начало последовательности и начать
ее просмотр заново. Типичным примером такой дисциплины доступа является чтение данных из последовательного файла, где каждая операция чтения возвращает значение очередной файловой записи. Дисциплину доступа к данным, хранящимся в последовательности, можно формализовать следующим образом:
• Открыть последовательность.
• Прочитать очередной элемент.
• Пропустить очередной элемент.
• Встать в начало последовательности.
• Достигли конца последовательности?
В приведенных выше предписаниях отсутствуют команды формирования самой последовательности (т.е. неявно предполагается, что в ней уже существуют какие-то данные). Поэтому для полноты картины можно дополнительно включить операцию добавления нового элемента в последовательность (дописывания в конец):
• Добавить элемент в конец последовательности.
Дисциплина работы с абстрактной последовательностью очень напоминает правила работы с очередью с одним единственным исключением — обработанные элементы, вообще говоря, не удаляются, а остаются в памяти (или на диске). В этом смысле организация доступа к данным по последовательному принципу не вызывает проблем.
В реальном программировании дисциплина последовательного доступа к данным создает проблемы совсем с другой стороны, и главная из них — наличие памяти для размещения элементов. Рассмотрим такой пример. Пусть имеется датчик, снимающий показания о характеристиках некоторого процесса или системы. Это может быть технологический процесс, натурный физический эксперимент, периодический контроль состояния разнообразных устройств и т.п. Данные от датчика поступают на вход программы, которая должна их анализировать и принимать решения о последующем управлении системой или процессом.
Очевидно, что обрабатываемые элементы данных организованы в последовательность. Они поступают последовательно один за другим, но мы заранее не можем предсказать сколько всего их будет. В принципе, возможно начать просмотр последовательности заново, но для этого придется запустить исследуемый процесс с начала, что может оказаться неэффективным по времени. Сохранение всей последовательности в памяти для последующей обработки также нецелесообразно из-за непредсказуемых расходов памяти. Встречаются ситуации, когда невозможно повторить просмотр последовательности с самого начала из-за уникальности самой последовательности (данные от физического эксперимента), либо из-за необходимости принимать решения сразу при обнаружении специфического поведения последовательности (например, данные о состоянии реакторов атомной электростанции).
Следовательно, анализ последовательности должен быть организован так, чтобы требуемые характеристики прочитанной части элементов вычислялись программой сразу и при этом не требовалось хранить в памяти всю последовательнось целиком, сохраняя лишь минимальное количество дополнительных промежуточных значений. Алгоритмы, удовлетворяющие таким требованиям, называют однопроходными.
Фактически в большинстве задач, связанных с обработкой последовательностей, нам нужно вычислять некоторую функцию, определенную на последовательностях данных. Сформулированные выше требования на однопроходность алгоритма приводят к понятию индуктивной функции. Математически строгое определение индуктивных функций и других связанных с ними понятий, а также доказательство ряда необходимых фактов приведено в книге [4]. Однопроходные алгоритмы, вычисляющие индуктивные функции, являются в некотором смысле оптимальными, поскольку они обрабатывают каждый поступающий на вход элемент данных “только один раз”. Количество промежуточных данных, с которыми оперирует алгоритм, также характеризует
его качество. В связи с этим упомянем теорему о существовании минимального (по памяти) индуктивного алгоритма, вычисляющего заданную характеристику последовательности (подробнее см. [4]). Заметим, что оптимальность однопроходных алгоритмов оправдывает их применение не только для последовательностей, а и для других способов организации наборов данных, когда элементы логически выстроены в линейную цепочку (например, для массивов).
Не углубляясь в теоретические построения, мы разберем ряд примеров, иллюстрирующих технику построения однопроходных алгоритмов. Уточним постановку задачи. Пусть есть некоторая последовательность элементов {ап}, мы уже просмотрели к ее элементов, и теперь в нашем распоряжении имеется очередной элемент a*.+i и некоторое количество промежуточных значений, на основании которых мы должны вычислять значение требуемой функции. Наша цель состоит в определении некоторой системы рекуррентных соотношений, позволяющих пересчитывать необходимые значения на основе “старых” значений и нового поступившего элемента последовательности. Будем считать, что получение очередного элемента данных реализуется функцией GetNextElementO, которая возвращает значение требуемого типа, а проверка достижения конца последовательности выполняется функцией EndSequence(), возвращающей 0, если последовательность еще не окончилась.
Пример 1. Среднее арифметическое вещественной числовой последовательности. Очевидно, что среднее арифметическое нельзя вычислить только на основе значений элементов последовательности, поскольку нам обязательно нужно знать их общее количество. С другой стороны, сумму и количество элементов можно вычислять шаг за шагом по очевидным рекуррентным формулам п = п 4- 1 и sn+i = sn 4- an+i, и это все, что нужно для определения среднего арифметического. Заметим также, что хотя среднее арифметическое не определено для пустой последовательности, мы в программной реализации можем взять их начальные значения равными нулю, так как применение
рекуррентных формул для первого элемента последовательности уже даст правильный результат. Итак, мы приходим к следующему фрагменту программы:
int п=0; /♦ текущее количество элементов */
double ss0; /* текущая сумма элементов */
double mean=0; /♦ среднее арифметическое ♦/
double а; /♦ текущий элемент */
while ( !EndSequence() ) { а = GetNextElement();
n++; s += а;
if ( n ) mean = s/n;
Пример 2. Количество локальных максимумов. Назовем элемент числовой последовательности локальным максимумом, если он больше предыдущего и не меньше последующего элементов. Простейшее решение — сохранять значения двух последних просмотренных элементов с тем, чтобы, прочитав новый элемент, выполнять требуемую операцию сравнения. Заметим также, что для последовательности, содержащей менее трех элементов, требуемая характеристика не определена. Поэтому в реализации следовало бы предусмотреть реакцию на такие “вырожденные” последовательности, но для упрощения текста программы мы будем считать, что для подобных последовательностей число локальных максимумов равно нулю. Наш вариант решения приводит к такому фрагменту программы.
int cnt=O; /♦ счетчик максимумов ♦/
double al,a2; /♦ предпоследний и последний эл-ты */
double аЗ; /♦ текущий элемент */
if ( !EndSequence() ) al = GetNextElement(); if ( !EndSequence() ) a2 = GetNextElement();
while ( !EndSequence() )
{ a3 = GetNextElement();
if ( al<a2 && a2>sa3 ) ++cnt;
al = a2; a2 = a3;
}
Этот пример не очень хорош, так как для возрастающего участка последовательности он требует две операции сравнения и две пересылки данных на каждый новый элемент. Для чисел это не влечет особого снижения эффективности, но для объемистых элементов данных может потребовать значительного времени. Попробуем немного пересмотреть алгоритм, чтобы снизить затраты времени. Очевидно, что если последний прочитанные элемент последовательности больше предыдущего прочитанного элемента, то нам достаточно его сравнить только с новым элементом, а если нет, то локального максимума в этом месте вообще быть не может. Введем переменную grow, которая будет равна 1, если на последних двух элементах последовательность возрастает, и — 0 в противном случае. Тогда требуемую задачу решает следующий фрагмент программы:
int cnts0; /♦ счетчик максимумов ♦/
double а2; /* последний элемент */
double аЗ; /* текущий элемент */
int grow; /* признак возрастания */
if ( !EndSequenceО ) а2 ® GetNextO; if ( !EndSequenceО ) аЗ = GetNextO; grow = (аЗ>а2) ? 1 : 0;
а2 = аЗ;
while ( !EndSequence() )
{ аЗ = GetNextElement();
if ( grow )
{ if ( a2>=a3 ) { ++cnt; grow = 0; } } else
{ if ( a2<a3 ) grow = 1; }
a2 = a3;
В этом варианте каждый раз выполняется не более одного сравнения элементов последовательности, одна проверка числового (логического) значения переменной grow и одна пересылка данных на каждый прочитанный элемент последовательности.
Пример 3. Вычисление значения многочлена. Индуктивные алгоритмы могут оказаться полезными не только для “длинных”
последовательностей. Это иллюстрирует следующий пример. Пусть последовательность ao,ai,fl2 • • • представляет собой коэффициенты некоторого многочлена а^хп 4- aixn~l 4- .... Наша задача — реализовать вычисление значения этого многочлена в заданной точке х с минимальным числом арифметических операций. Оказывается, эту задачу решает хорошо известный алгорим — схема Горнера. При расчете по этому алгоритму нам не важно конкретное количество элементов в последовательности коэффициентов, в каждый момент времени мы имеем значение многочлена, определяемого просмотренными к этому моменту коэффициентами. В математических обозначениях схему Горнера можно описать формулой
Рп(х) = (... ((а0 • х 4- ап-1) * я + «п-2) • х 4-...) • х 4- ап.
Алгоритмический эквивалент этой формулы выглядит так.
double х, р, а;
Р = 0;
while ( !EndSequence() ) { а = GetNextElementО;
р » р*х+а;
}
Можно показать, что этот алгоритм является минимальным по сложности и наименее чувствительным к погрешностям округления при вычислении многочленов общего вида (без учета какой либо дополнительной информации о коэффициентах и других свойствах этого многочлена). Поэтому этот алгоритм естественно применять для вычисления многочленов и в том случае, когда их коэффициенты заданы не последовательностью, а массивом:
double Polynom (double х, double *а, double n)
double p=0;
while (п—) р = р*х + *а++;
return р;
}
Пример 4. Обнаружение заданного “слова” в последовательности символов. Задача обнаружения заданного набора символов в текстовой строке является одной из классических задач программирования. Известно множество алгоритмов решения этой, задачи (см. [5]). Но здесь мы обсудим задачу обнаружения образца именно в последовательности. То есть в той ситуации, когда мы не имеем возможности накапливать поступающие символы в отдельной строке для последующего ее анализа или возвращаться назад в исходной строке, а должны сразу отреагировать на поступивший символ, если он завершает появившееся в последовательности искомое “слово”.
Понятно, что не следует запоминать последние прочитанные элементы последовательности в количестве, сравнимом с длиной слова-образца. Такое решение привело бы к операциям посимвольного сравнения двух целых строк и сдвиге всех символов в строке каждый раз при появлении очередного элемента последовательности. Мы рассмотрим другой алгоритм, идейно близкий к понятию конечного автомата.
Идея, лежащая в основе алгоритма, довольно проста — будем считать сколько символов от начала слова-образца совпало с элементами последовательности. Если в какой-то момент этот счетчик станет равным длине образца, то мы фиксируем наличие слова в последовательности, если же очередной символ последовательности не подходит к очередному символу образца, то сбрасываем этот счетчик в нуль. Пусть образец записан в массиве pattern, длина образца — п. Заметим, что значение счетчика совпадений после проверки очередного символа равно индексу символа образца, который мы должны проверять в следующий момент. Поэтому для сохранения этого значения нам достаточно одной переменной, которую мы назовем ind. Попробуем реализовать этот алгоритм для решения задачи о подсчете
количества вхождений заданного образца в последовательность
символов.
char sym; /♦ очередной символ последовательности ♦/
int ind=0; /* текущий индекс в образце */
int cnt=0; /♦ счетчик количества найденных образцов */
int next=l; /♦ признак необходимости чтения элемента ♦/
while ( !EndSequence() )
{ if (next) sym = GetNextElement();
if ( pattern[ind] == sym ) { ++ind; next = 1; }
else { next = (ind) ? 0:1; ind = 0; } if ( ind == n )
{ /♦ образец найден ♦/
++cnt;
ind = 0; next = 1;
}
Комментарий к алгоритму. Необходимость введения переменной next вызвана следующим обстоятельством. При обнаружении несовпадения очередного символа из последовательности с образцом после нескольких предшествующих совпадений мы должны сравнить этот символ с начальным символом образца, что выполняется по той же схеме, но только без чтения нового символа из последовательности. Таким образом, признак необходимости чтения next устанавливается в единицу, если нет совпадения с начальным символом образца или есть совпадение с очередным символом.
Алгоритм выглядит довольно просто, но к сожалению, он не всегда будет работать правильно. Действительно, достаточно рассмотреть его работу на примере последовательности “aaabb” и образцов “abb” и “aab”. Отметим текущие символы в последовательности и образце круглыми скобками. Тогда процесс просмотра будет происходить следующим образом.
Поиск "abb" значение после сравнения
(a)aabbb (a)bb ind ® 1
a(a)abbb a(b)b ind = 0
a(a)abbb (а)ЪЪ ind = 1
aa(a)bbb а(Ъ)Ь ind = 0
аа(а)ЪЪЪ (а)ЪЬ ind = 1
ааа(Ъ)ЪЪ а(Ъ)Ъ ind = 2
аааЪ(Ъ)Ъ аЪ(Ъ) ind = 3 образец найден
аааЪЪ(Ъ) (а)ЪЪ ind = 0
Поиск "aab“ значение после i сравнения
(a)aabbb (a)ab ind = 1
a(a)abbb a(a)b ind = 2
aa(a)bbb aa(b) ind = 0 образец пропущен
aa(a)bbb (a)ab ind = 1
aaa(b)bb a(a)b ind = 0
aaa(b)bb (a)ab ind = 0
aaab(b)b (a)ab ind = 0
aaabb(b) (a)ab ind = 0
Причина неудачи состоит в том, что образец содержит группу символов, которая повторяется два раза в его начале (в нашем случае — это пара символов “а”). При несовпадении очередных символов алгоритм не учитывает возможность того, что начало вхождения образца может находиться среди уже просмотренных элементов последовательности, и “примеряет” несовпавший символ к началу образца. Для устранения этой ошибки нужно заставить “примерять” этот символ к нужной позиции образца. В нашем случае таблица сравнений должна была бы выглядеть так:
Поиск "i
'aabM
(a)aabbb (a)ab ind = 1
a(a)abbb a(a)b ind = 2
aa(a)bbb aa(b) ind = 1
aa(a)bbb a(a)b ind = 2
aaa(b)bb aa(b) ind = 3
Добиться такого результата можно, если провести предварительный анализ образца на наличие повторяющихся подпоследовательностей в его начале и запомнить какое значение следует
присвоить переменной ind при обнаружении несовпадения очередного символа. Итак, пусть массив newind определяет какой символ образца должен стать текущим, если на данном символе обнаружено несовпадение, т.е. индекс нового текущего символа определяется присваиванием ind = newind[ind]. Нетрудно проверить, что в нашем случае этот массив будет иметь вид newind={0,0>i}.
Теперь можно выписать исправленный вариант алгоритма поиска образца в последовательности в предположении, что массив newind уже определен.
int sym; /♦ очередной символ последовательности ♦/
int ind=0; /♦ текущий индекс в образце ♦/
int cnt=0; /♦ счетчик количества найденных образцов ♦/ while ( !EndSequence() )
{
sym = GetNextElement О ;
while(( ind )&&( pattern[ind] != sym ))
{ ind « newind[ind]; }
if ( pattern[ind] == sym ) ++ind;
if ( ind == n ) { ++cnt;
ind = 0;
Возникает вопрос о том как по заданному образцу построить массив newind и насколько эта предварительная работа может снизить эффективность алгоритма в целом. Понятно, что эта работа должна быть сделана один раз для каждого искомого образца. Поэтому в задачах, где в последовательности ищутся заранее определенные известные образцы, которые можно предварительно обработать, этот алгоритм будет весьма эффективен. С другой стороны, если в последовательности требуется отыскивать разнообразные и заранее неизвестные образцы, то работа по предварительному их анализу и построению соответствующих массивов newind может составить значительную часть от всего времени выполнения алгоритма.
5.2 Упражнения
5.1. Пусть в файле задана числовая последовательность неизвестной длины. Реализуйте однопроходные алгоритмы для вычисления следующих характеристик последовательности.
• минимальный элемент последовательности;
• первый элемент, равный заданному числу х\
• последний элемент, равный заданному числу х;
• количество элементов, равных заданному числу х;
• количество максимальных элементов последовательности;
• длина наибольшего постоянного участка последовательности;
• удовлетворяют ли элементы последовательности Xi заданному рекуррентному соотношению axi + bxi+i + cxi+2 = d;
• количество элементов, лежащих на возрастающих участках последовательности.
5.2. На основе схемы Горнера постройте однопроходный алгоритм вычисления значения производной в заданной точке от многочлена, определяемого последовательностью его коэффициентов в порядке убывания степеней.
5.3. Постройте “вручную” массивы newind соответствующие образцам “abab”, “ababcabcd”, “abcdabce”, “abcdabcab” для задачи обнаружения строки в последовательности символов.
5.4. Предложите и реализуйте автономный алгоритм поиска образца в последовательности символов, который по заданной строке-образцу сам строит массив newind.
6 Списки
6.1 Ссылочный подход
Реализации структур данных, с которыми мы имели дело в предыдущем разделе, часто называют непрерывными, поскольку
элементы, добавляемые в структуру, размещаются в памяти рядом друг с другом. Вообще говоря, такое свойство реализаций обусловлено правилами работы с этими структурами, так как сами системы предписаний разрешают добавление и удаление элементов только “по краям” указанных структур. Если мы захотим добавлять или удалять элементы данных не только “по краям”, оставаясь в рамках непрерывного способа их размещения, то неминуемо столкнемся с необходимостью выполнения массовых операций по раздвиганию массива элементов, чтобы получить новое место при добавлении, или сдвиганию, чтобы уничтожить образовавшуюся “дыру” при удалении элемента. Собственного говоря, подобная ситуация уже возникала при pear лизации дека и очереди. Там мы ее обошли с помощью замыкания линейного массива в кольцо с помощью понятий “следующий” и “предыдущий”, которые реализовывались с помощью функций Next О и Prev(), вычисляющих номер соответствующей позиции или непосредственно указатель на требуемый элемент.
Попробуем обобщить эту идею для реализации структуры данных, обладающей следующими свойствами:
1. элементы данных образуют линейную цепочку, т.е. для каждого элемента существует “следующий” и “предыдущий” (естественно, кроме концевых элементов, для которых существует только один такой соседний элемент);
2. в каждый момент времени в этой линейной цепочке определена некоторая текущая позиция и нам разрешен доступ к элементу в этой текущей позиции (или к его непосредственным “соседям”).
3. положение текущей позиции можно изменять и тем самым получать доступ к значению любого элемента данной структуры не извлекая из нее элементов;
4. добавление и удаление элементов может происходить в окрестности текущей позиции, причем эти операции не должны приводить к массовым пересылкам данных в памяти;
Структуры данных, обладающие указанными свойствами обычно называют списками. Наглядным примером списочной организации данных может служить работа с текстом в большинстве текстовых редакторов. Редактирование текста можно выполнять в окрестности текущей позиции, которая определяется положением курсора. Можно удалить текущую строку или вставить новую строку непосредственно перед текущей. Можно перемещаться по строкам по направлению к началу или концу текста. Таким образом, весь текст можно рассматривать как список строк. Точно так же каждую отдельную строку можно рассматривать как список символов, по которому можно перемещать текущую позицию редактирования к началу или концу строки и добавлять или удалять символы в окрестности текущей позиции.
Обсудим теперь идеи реализации подобных структур. Для того, чтобы обеспечить выполнение условия 4, нам придется отказаться от непрерывности размещения элементов. Новый добавляемый элемент списка будет размещаться в памяти там, где в данный момент для него найдется место. Таким образом, добавление нового элемента никак не повлияет на размещение уже существующих данных.
Как же в этом случае гарантировать условие 1, ведь теперь позицию следующего или предыдущего элемента уже нельзя “вычислить”? Ответ прост — раз нельзя вычислить, придется запомнить. Итак, наряду с содержательными данными каждого элемента нам придется хранить информацию о местоположении следующего и предыдущего элементов. Теперь достаточно легко обеспечить выполнение условия 2. Для этого достаточно хранить указатель на элемент списка, к которому в данный момент разрешен доступ. Будем называть указателем списка переменную (или переменные), хранящие указатель на доступный в данный момент элемент (или два соседних элемента) списка. Изменяя значение этого указателя (“передвигая” указатель списка), мы можем добраться до любой позиции в списке, т.е. обеспечить выполнение
условия 3. Описанные соображения — это только идеи. При конкретной реализации возникает множество вопросов: каким образом хранить ссылки на соседние элементы, как отличать “внутренние” элементы списка от “крайних” (первого и последнего), каким образом мы сможем передвинуть указатель текущего элемента в любую позицию списка, как следует выполнять операции добавления или удаления элементов и т.п. Решения всех этих вопросов можно выполнить по-разному, что естественным образом приведет к различным реализациям списка. Поскольку невозможно описать все типы списочных структур, которые могут потребоваться в конкретных задачах, мы рассмотрим здесь только два примера, обращая внимание скорее на возникающие проблемы, чем на необходимость буквально следовать предлагаемым алгоритмическим решениям.
6.2 Одно- и двунаправленные списки
Сначала мы рассмотрим реализацию двунаправленного списка, в котором каждый элемент (кроме первого и последнего) ссылается на два соседних с ним элемента. Примем следующие соглашения по поводу задания структуры этого списка:
• каждый элемент списка представляет собой составной объект, хранящий в себе содержательную информацию данного элемента и два указателя — на следующий и предыдущий элементы;
• в каждый момент времени разрешен доступ только к двум соседним элементам списка (будем называть их элемент до указателя и элемент за указателем), пару указателей на позиции этих двух элементов будем называть указателем текущей позиции;
• удалять можно только те элементы, на которые показывает указатель текущей позиции (т.е. элементы до или за указателем), при этом соответствующая ссылка указателя списка
перемещается на предыдущий (соответственно, следующий) элемент;
• новые элементы добавляются в окрестности указателя текущей позиции, т.е. добавленный элемент может стать либо элементом до указателя, либо элементом за указателем.
В этих соглашениях не отражен только один пункт — как работать с концевыми элементами списка, т.е. как отличать их от внутренних, как устанавливать указатель текущей позиции в начало или конец списка и т.д. Обычно применяется одно из двух решений: первое — указатель на предыдущий для первого элемента и указатель на следующий для последнего элемента полагаются равными нулю, второе — вводится дополнительный служебный элемент списка, который замыкает весь список в кольцо. Мы разберем второй способ. Итак, вводится дополнительный элемент, который мы обозначим base. Этот элемент является предыдущим для первого и одновременно последующим для последнего элементов списка. Зная адрес размещения элемента base, мы всегда можем узнать находится ли текущая позиция указателя списка в начале или в конце.
Принятые нами решения по поводу системы ссылок можно условно изобразить в виде следующей схемы:
Рис. 6.1. Схема закольцованного двунаправленного списка.
Теперь, как и для предыдущих стуктур, попытаемся разработать систему предписаний двунаправленного списка:
• Создать список;
• Уничтожить список;
• Добавить элемент до (или за) указателем;
• Удалить элемент до (или за) указателем;
• Прочитать элемент до (или за) указателем;
• Изменить элемент до (или за) указателем;
• Передвинуть указатель вперед (или назад);
• Встать в начало (конец) списка;
• Список пуст ?
• Указатель в конце (или начале) ?
Теперь можно приступить к реализации. При использовании языка С список будет представлять собой набор функций, работающих с общим набором данных — элементами списка. Каждый элемент списка в этом случае можно представить в виде структруры, содержащей информационное поле value и два указателя на соседние элементы: next, prev. Как обычно, для защиты внутренних объектов реализации определения этих функций следует выделить в отдельный файл, а внешний интерфейс описать в заголовочном файле с именем list2.h.
/♦
♦ Файл list2.h
* С-реализация двунаправленного списка элементов типа Туре ♦/
«ifndef LIST2.H.INCLUDED
«define LIST2.H_INCLUDED /♦ типы данных ♦/ typedef struct L2 { /♦ тип - элемент списка ♦/
Type value; /♦ значение элемента списка ♦/
struct L2 *next, *prev; /♦ ссылки на соседние эл-ты ♦/
} L2_Item;
/♦ прототипы функций */
int L2_Init (void); /♦ создать список ♦/
void L2_Term (void); /♦ уничтожить список ♦/
int L2_InsBefore (Type value); /♦ вставить до указателя ♦/
int L2_InsAfter (Type value); /* вставить за указателем*/
int L2_DelBefore (void); /♦ удалить до указателя ♦/
int L2.DelAfter (void); /♦ удалить за указателем ♦/
int L2_TakeBefore(Type *dst); /♦ взять до указателя ♦/
int L2.TakeAfter (Type *dst); /♦ взять за указателем ♦/
int L2_GetBefore (Type *dst); /♦ прочитать до указателя ♦/
int L2_GetAfter (Type *dst); /♦ прочитать за указателем*/
int L2_SetBefore (Type value); /♦ изменить до указателя ♦/
int L2_SetAfter (Type value); /♦ изменить за указателем*/
int L2_StepForward (void); /♦ передвинуть вперед ♦/
int L2_StepBackward (void); /♦ передвинуть назад ♦/
void L2_GotoBeg (void); /♦ встать в начало ♦/
void L2_GotoEnd (void); /♦ встать в конец ♦/
int L2_AtBeg (void); /♦ указатель в начале ? ♦/
int L2_AtEnd (void); /♦ указатель в конце ? ♦/
int L2_IsEmpty (void); /♦ список пуст ? ♦/
tendif
/♦ конец файла list2.h ♦/
Комментарий к реализации.
Функции L2_GetBefore и L2_GetAfter копируют значение соответствующего элемента списка по указателю dst.
Функции L2_TakeBefore и L2_TakeAfter также копируют значение соответствующего элемента списка по указателю dst, после чего данный элемент списка удаляется.
Функции L2_SetBefore и L2_SetAfter записывают значение value в соответствующий элемент списка, текущая позиция остается без изменения.
Функции L2_StepForward и L2_StepBackward перемещают текущую позицию в списке на один элемент в указанном направлении.
Функция L2_IsEmpty возвращает 1 для пустого и 0 для непустого списков.
Все остальные функции, возвращающие int, возвращают О в случае успеха, и —1 в случае невозможности выполнить указанную операцию. Например, при добавлении элемента может не оказаться свободной памяти для создания нового элемента списка; при указателе, установленном в начало списка, не существует элемента до указателя и, следовательно, его нельзя удалить; нельзя сделать шаг вперед, находясь в конце списка, и т.п.
Отметим, что в системе предписаний отсутствует функция “есть место в списке?”, которая проверяла бы возможность добавления нового элемента. Дело в том, что при выделении памяти с помощью функций типа malloc мы не можем ответить на этот вопрос, пока не попытаемся реально захватить место для элемента. Таким образом, нам гораздо проще сначала попытаться выполнить требуемую операцию добавления, а потом проверить ее успешность, анализируя значение, возвращаемое соответствующей функцией.
Приступая к реализации функций, мы должны принять еще одно решение по поводу того, где и как брать память для размещения элементов. Возможны два различных способа. Первый — выделять память под каждый элемент по мере необходимости системными средствами (например, функцией malloc). Второй — заранее зарезервировать большой блок памяти, а потом уже самостоятельно размещать в нем элементы. В последнем случае нам придется самим заботиться о том, как отыскивать свободное место в этом блоке, но сам процесс выделения места для элемента при решении конкретной задачи может оказаться эффективнее (по времени и памяти), чем в первом случае. Задача управления размещением объектов в памяти будет рассмотрена в разделе, посвященном контейнерам, а пока мы можем считать, что выделением памяти под элемент и ее последующим освобождением в примерах на языке С занимаются отдельные функции с именами GetPlace и FreePlace, а в примерах на языке С-Н-оператор
new. В приведенном ниже тексте эти функции будут просто вызывать malloc и free.
Функции, работающие с элементами до указателя текущей позиции симметричны функциям, работающим с элементами за указателем. Поэтому мы приведем здесь только часть реализации, предполагая, что остальные функции легко могут быть построены по аналогии.
/* ф Файл list2.с * С-реализация двунаправленного списка элементов типа Туре
♦/
/♦ прототипы функций ♦/
«include <stdlib.h> /♦ malloc и free ♦/
«include ”list2.h" /♦ функции списка ♦/
void ♦ GetPlace (void); /♦ захватить элемент ♦/
void FreePlace(void *pos); /♦ освободить элемент ♦/
/♦ внутренние глобальные объекты */
static L2_Item ♦before, «after; /♦ указатель списка ♦/
static L2_Item base; /♦ базовый элемент ♦/
/♦ определения функций */
void ♦ GetPlace (void)
{return malloc(sizeof(L2_Item)); }
void FreePlace (void *pos) { free (pos); У
int L2.Init (void) /♦ создать список ♦/
{ /♦ создается пустой список ♦/ before = after = Abase;
base.next = base.prev = Abase;
return 0;
void L2_Term (void) /♦ уничтожить список ♦/
{ /♦ последовательно удаляются все элементы списка ♦/ for( L2_GotoBeg(); !L2_AtEnd(); L2_DelAfterО);
int L2_InsBefore (Type value) /♦ вставить до указателя ♦/ {
L2_Item *pos;
/♦ захватываем место для нового элемента */ if ( !(pos=(L2_Item*)GetPlaceО) ) return -1; pos->value = value; /* заносим значение ♦/ pos->next » after; /* корректируем ссылки списка ♦/ pos->prev « before; after->prev = pos; before->next = pos; before = pos; /* корректируем указатель списка ♦/
return 0;
int L2.DelBefore (void) /♦ удалить до указателя ♦/ { L2_Item ♦pos; if (L2_AtBeg()) return -1; pos = before; /♦ запоминаем позицию удаления ♦/ before s pos->prev; /♦ корректируем указатель списка ♦/ before->next » after; /♦ корректируем ссылки списка ♦/ after->prev = before; FreePlace(before); /♦ освобождаем память ♦/ return 0; ? int L2.TakeBefore (Type ♦dst) /♦ взять до указателя ♦/ if (L2_AtBeg()) return -1; ♦dst = before->value; /♦ передаем значение ♦/ L2_DelBefore(); /♦ удаляем элемент ♦/ return 0; } int L2_GetBefore (Type *dst) /♦ прочитать до указателя ♦/ if (L2_AtBegO) return -1; ♦dst = before->value; /♦ передаем значение ♦/ return 0; } int L2_SetBefore (Type value) /♦ изменить до указателя ♦/ г
if (L2_AtBeg()) return -1; before->value = value; return 0; int L2_StepForward (void) /♦ изменяем значение ♦/ /♦ передвинуть вперед ♦/
1 if (L2_AtEnd()) return -1; before = after; after = after return 0; ->next;
void L2_GotoBeg (void) /♦ встать в начало ♦/
before = ftbase; after = base.next;
}
int L2_AtBeg (void) /♦ указатель в начале ? */
{
return before == Abase;
}
int L2_IsEmpty (void) /♦ список пуст ? ♦/
return before == after;
}
/* Остальные функции строятся аналогично */
/* конец файла list2.с ♦/
Комментарий к реализации. Заметим, что элемент base отличается от других элементов списка, поскольку он не хранит других данных, кроме ссылок на первый и последний элементы. Таким образом, поле base.value представляет собой “чистую” потерю. В принципе, можно построить реализацию, не использующую подобного элемента, но это несколько усложнит алгоритмы включения и исключения элементов, поскольку потребует дополнительных проверок не находится ли текущая позиция в начале или конце списка. Списки часто используются для хранения различных указателей, т.е. данных, занимающих весьма малый объем памяти (4 байта). Поэтому нецелесообразно усложнять алгоритмы для достижения столь мизерной “экономии”. При реализации на языке C++ эту проблему можно эффективно решить с использованием механизма наследования классов, где элемент списка будет являться производным классом от класса типа “чистой” двойной связки.
В некоторых задачах достаточно поддерживать ссылки между элементами списка только в одном направлении, что находит свое отражение в понятии однонаправленного списка. Для описания элемента такого списка будет достаточно иметь структуру
typedef struct LI {
Type value; struct LI ♦next;
} LI„Item;
В однонаправленном списке в каждый момент времени обычно разрешается доступ только к одному элементу, который мы будем называть текущим элементом. Нетрудно понять, что подобное определение элемента списка делает возможным перемещение текущей позиции только в одном направлении — от начала к концу списка (находясь в конкретной позиции, мы не знаем местоположения предыдущего элемента). Поэтому следует договориться о том, как мы должны интерпретировать операции добавления и удаления элементов. Заметим, что в двунаправленном списке эти операции являются взаимно обратными, т.е. добавление и последующее удаление элемента с одной и той же стороны от текущей позиции не изменяют состояния списка. Естественно, подобное свойство взаимной обратности операций добавления и удаления желательно сохранить и для однонаправленого списка. Здесь возможны два подхода. При первом подходе удаляется текущий элемент, а новым текущим становится следующий за ним. Добавляемый элемент вставляется “перед” текущим и становится новым текущим. Этот подход иллюстрируется рисунком 6.2.
исходное состояние: 1 текущая позиция
Vc)——»/е)—►
добавили элемент f: 1 текущая позиция
(J)— -*ff)——►fd)—»/е
удалили элемент f: 1 текущая позиция
fa)—ZbY- -*(с)—«/сП—►
Рис. 6.2. Добавление и удаление элементов при первом подходе.
Данный подход легко реализовать, взяв за основу двунаправленный список и выбросив все действия, относящиеся к ссылке prev, но оставив двойной указатель текущей позиции. При этом текущим элементом в однонаправленном списке будет
являться элемент по указателю after. Действительно, в этом случае нам известна позиция предыдущего элемента (before), '/ и мы можем выполнить вставку элемента перед текущищим, a также корректно установить ссылки списка при удалении^
Второй подход не использует двойного указателя текущей позиции. В этом случае мы не можем удалить текущий элемент, поскольку нам не известна позиция предыдущего и, следовательно, мы не сможем замкнуть ссылки списка при удалении. Однако здесь легко отнести эти операции к следующему за текущим элементу. Итак, удаляется элемент, следующий за текущим, и добавляемый элемент ставится за текущим, текущая позиция не изменяется.
исходное состояние:
(а)—►ГК добавили элемент f:
Га)— удалили элемент f:
Га?)—►ГЬ'
I текущая позиция К)—»/d)—*Ге)—►
I текущая позиция с)— | текущая позиция с)—►ГсГ)—►(К)—►
Рис, 6.3. Добавление и удаление элементов при втором подходе.
Далее мы рассмотрим реализацию именно этого второго подхода. Полученная при таких соглашениях система предписаний однонаправленного списка может выглядеть так:
• Создать список.
• Уничтожить список.
• Добавить элемент за текущим.
• Удалить элемент за текущим.
• Прочитать текущий элемент.
• Изменить текущий элемент.
• Доступ к элементу за текущим.
• Передвинуть текущую позицию вперед.
• Встать в начало списка.
• Список пуст?
• Текущая позиция в конце списка?
Реализацию однонаправленного списка мы также построим с использованием дополнительного элемента base. Для разнообразия мы приведем здесь параметризованную реализацию на языке С 4--К
//
// Файл listl.h
// C++ реализация однонаправленного списка элементов типа Туре
И
#ifndef LIST1JLINCLUDED #define LIST1JLINCLUDED
template <class Type> class Ll_Item { public: /* элемент списка ♦/
Ll_Item ♦next; /» указатель на следующий элемент ♦/
Type value; /» значение элемента ♦/
template <class Type> class Listl /♦ сам список ♦/
{ private:
Ll_Item<Type> ♦current; /♦ указатель текущей позиции ♦/
Ll_Item<Type> base; /♦ базовый элемент списка ♦/ public:
Listl () { current = base.next « ftbase; } "Listl ();
// Добавить элемент за текущим int Insert (Type value);
// Удалить элемент за текущим int Remove О;
// Прочитать текущий элемент int Get (Type &dst)
{ if ( current==&base ) return -1; dst = current->value;
return 0; }
// Изменить текущий элемент int Set (Type value) { if ( current==Abase ) return -1; current->value = value;
return 0; }
// Доступ к элементу за текущим.
Туре ♦ NextElem () { if (AtEndO) return (Type*)0;
return Ь(current->next->value); }
// Передвинуть текущую позицию вперед.
int Step О
{ if (AtEndO) return -1; current = current->next; return 0;
} // передвинуть указатель списка в начало void GotoBeg О { current = Abase; } II указатель в конце списка ?
int AtEnd () { return current->next = Abase; } // список пуст ?
int IsEmpty () { return base.next==Abase; } };
template <class Type>
Listl<Type>::~Listl()
for(GotoBeg() ; !AtEnd() ; RemoveO);
}
template <class Type>
int Listl<Type>::Insert (Type value) { Ll_Item<Type> *pos = new Ll_Item<Type>; if (!pos) return -1;
pos->value = value;
pos->next = current->next;
current->next = pos;
return 0;
template <class Type> int Listl<Type>:-.Remove () { if (AtEndO) return -1;
Ll_Item<Type> *pos = current->next; current->next = pos->next;
delete pos;
return 0;
#endif
11 конец файла listl.h
Комментарий к реализации. Наиболее простые методы работы со списком реализованы непосредственно в описании класса. Более сложные, занимающие несколько строк текста, вынесены из описания класса.
Заметим, что при позиции указателя в начале списка текущий элемент отсутствует (на самом деле — это служебный элемент base). Такое решение позволяет добавлять новые элементы непосредственно в начало списка, поскольку по нашему соглашению они добавляются за текущей позицией.
Списки чрезвычайно широко используются в программировании. Это и понятно, ведь основным достоинством такого способа хранения является возможность размещать наборы данных, не заботясь о том, чтобы соседние в логическом смысле элементы данных оказывались рядом и в памяти. Помимо приведенных здесь примеров, возможно множество модификаций способов работы с данными, организованными в линейные цепочки в соответствии с теми или иными признаками. В ряде практических случаев некоторые из приведенных выше предписаний оказываются ненужными, в других случаях требуются свои специфические функции и т.д. Наверное невозможно описать и формализовать все многообразие списочных структур. Часть примеров содержится в упражнениях к этому разделу, другие варианты подходов к реализации разного рода списков встречаются в последующих разделах книги.
6.3 Упражнения
6.1. Реализуйте однонаправленные и двунаправленные списки без использования вспомогательного элемента base. Для этого можно ввести дополнительные указатели, определяющие начальный и конечный элементы списка (для однонаправленного списка — только указатель на начало). В крайних элементах списка соответствующей ссылке устанавливается нулевое значение. Потребуются дополнительные проверки, чтобы различать состояние пустого и непустого списка и правильно корректировать эти дополнительные указатели при работе в окрестности начала и конца списка.
6.2. Реализуйте стек, дек, очередь с неограниченным количеством элементов на основе списочных структур. Фактически это сведется к реализации списков, где операции добавления и удаления производятся только в начале или конце.
6.3. Реализуйте кольцевой список без введения дополнительного элемента base (т.е. последний элемент списка ссылается на первый). В этом случае операция установки указателя в начало теряет смысл.
6.4. Добавьте в построенные реализации функцию поиска заданного элемента списка (текущая позиция устанавливается на найденный элемент) и функцию, выполняющую заданную операцию с каждым элементом списка (текущая позиция остается без изменения).
7 Деревья
7.1 Определения и обходы
Понятие списка, которое мы рассмотрели в предыдущем разделе, естественным образом обобщается на структуры с множественными связями между отдельными элементами. Одной из таких
структур является дерево, В математике дерево определяется как связный граф, не содержащий циклов. Если в этом графе выделена одна вершина, то говорят, что дерево имеет корень. Мы будем рассматривать именно такие деревья. Наличие корня в дереве сразу определяет некоторое отношение подчиненности вершин. Для ббльшей четкости изложения введем несколько определений.
Определение 1. Расстоянием (или длиной пути) между двумя вершинами А и В дерева назовем количество ребер графа, содержащихся в связной цепочке ребер, соединяющих А и В. (Поскольку дерево — это граф без циклов, расстояние между двумя вершинами определяется однозначно.)
Определение 2. Вершина В называется потомком вершины А, если расстояние между А и В равно 1 и расстояние от А до корня меньше, чем расстояние от В до корня дерева. Вершину А будем также называть родителем вершины В.
Определение 3. Будем говорить, что вершина А принадлежит fc-му уровню дерева, если расстояние от А до корня дерева равно к.
Очевидно, что уровень 0 дерева содержит только корень, а уровень к дерева образован потомками всех вершин уровня к — 1.
Определение 4. Ветвью дерева назовем связную последовательность вершин, начинающуюся в корне и оканчивающуюся на вершине, не имеющей потомков. Длиной ветви назовем число вершин в этой ветви.
Определение 5. Дерево, в котором каждая вершина имеет не более двух потомков, называется бинарным, в противном случае будем называть дерево произвольным.
Деревья играют весьма важную роль в программировании. В частности, процесс грамматического разбора предложений алгоритмического языка во время компиляции программы приводит к порождению некоторых деревьев, описывающих структуру этого предложения. Некоторые алгоритмы обработки данных (например, быстрые сортировки) используют сопоставление эле
ментов данных с вершинами некоторого дерева. Информацинно-поисковые и справочные системы используют древовидные структуры для организации доступа к необходимой информации и т.д.
Мы начнем обсуждение реализации деревьев с самого простого случая — бинарных деревьев. Итак, каждая вершина имеет не более двух потомков. Например, мы можем иметь дерево, представленное такой схемой:
Рис. 7.1. Пример бинарного дерева.
Чтобы реализовать хранение и работу с данными, содержащимися в вершинах дерева, нам необходимо каким-то образом представить существующие связи между между отдельными вершинами. Так как каждая вершина связана ребрами не более, чем с тремя другими вершинами, то мы можем естественным образом обобщить списочный подход:
typedef struct Tr {
Type value;
struct Tr ♦prev,*left>*right;
} TreeNode;
где указатели left и right показывают на потомков, a prev — на родителя. При этом, если вершина не имеет соседей в каком-нибудь направлении, то соответствующая ссылка имеет нулевое значение.
Такой способ представления каждой отдельной вершины является исчерпывающим для бинарного дерева. Действительно,
имея в распоряжении данные о конкретной вершине, мы можем переместиться в любую соседнюю с ней вершину (у нас есть необходимые указатели). Таким образом, мы можем свободно перемещаться по дереву и, в принципе, добраться до любой заданной вершины из любой другой вершины, если, конечно, будем знать куда в каждый момент двигаться.
В практическом плане работа с деревьями обычно подчинена решению каких-то конкретных задач и состоит в формировании дерева по определенным правилам и последующем его анализе. Поэтому мы пока не будем формализовывать предписания работы с деревом, а обсудим вопрос о так называемом обходе дерева.
Итак, пусть дерево уже как-то сформировано и его элементы размещены в памяти. Задача состоит в том, чтобы посетить каждую вершину дерева и выполнить некоторую обработку значений, хранящихся в этих вершинах (например, напечатать их, подсчитать сумму значений, определить максимум, обнаружить одинаковые поддеревья и т.п.)
Заметим, что дерево можно определить рекурсивно.
Рекурсивное определение дерева. 1. Пустое множество вершин есть (пустое) дерево;
2. Одна вершина, не связанная ни с какой другой вершиной, образует дерево и является корнем этого дерева;
3. Пусть имеется к деревьев Ti,..., Tk с корнями Ai,..., Ak, тогда, связывая вершину А с вершинами Ai,..., А^, мы получим новое дерево, в котором А есть корень, a Ti... 7*. — поддеревья.
Исходя из этого определения видно, что для обхода дерева очень удобно использовать рекурсию. Для бинарного дерева возможны три принципиально разных способа обхода: сверху-вниз, слева-направо, снизу-вверх. Смысл этих названий заключается в том, в каком порядке обрабатываются данные из текущей вершины дерева и соответствующих левого и правого поддеревьев. Приведем для примера функции обхода дерева с подсчетом максимума (предполагая, что в вершинах хранятся
числовые значения). Напомним, что отсутствие потомков у данной вершины характеризуется нулевым значением соответствующего указателя. Таким образом, мы можем проверять значение указателя текущей позиции на равенство нулю, чтобы прекратить последовательность рекурсивных вызовов функции.
Обход сверху-вниз:
void Up-Down (TreeNode ♦pos, Type *max)
if (Ipos) return ;
if ( ♦max < pos->value ) ♦max=pos->value;
Up-Down (pos->left, max);
Up.Down (pos->right, max);
Обход слева-направо:
void Left-Right (TreeNode ♦pos, Type ♦max)
if (!pos) return ;
Left-Right (pos->left, max);
if ( ♦max < pos->value ) ♦max=pos->value;
Left_Right (pos->right, max);
Обход снизу-вверх:
void DownJJp (TreeNode ♦pos, Type ♦max)
if (!pos) return ;
Down_Up (pos->left, max);
Down_Up (pos->right, max);
if ( *max < pos->value ) ♦max=pos->value;
Если мы имеем указатель на корень дерева, то вызов этих процедур для подсчета максимума может выглядеть так:
Туре щах;
TreeNode ♦root;
max = root->value;
Up.Down (root, fcmax); /♦ или ♦/ Left-Right (root, ftmax); /♦ или ♦/
Down.Up (root, fanax);
Каждая из этих функций перебирает вершины дерева по-своему. Например, для дерева, изображенного на рис. 7.1, последовательность обработки вершин при выполнения проверки if (*max<pos->value) будет следующей:
для обхода сверху-вниз ABDHIECFJKLG;
для обхода снизу-вверх HIDEBJLKFGCA;
для обхода слева-направо HDIBEAJFKLCG.
Отметим, что в этих функциях нигде не используется ссылка на предыдущий элемент (prev). Действительно, эта ссылка нужна для перемещения по дереву по направлению к корню. Однако в приведенных выше процедурах это перемещение происходит “автоматически” за счет запоминания текущего локального значения параметра pos в системном стеке при организации € последовательности рекурсивных вызовов. Таким образом., при конкретной реализации дерева указатель prev не нужен, если обработка вершин дерева производится с помощью рекурсивных процедур. Включать или нет этот указатель в описание структуры вершины дерева TreeNode зависит от решаемых задач и способов обработки вершин дерева. Для большинства дальнейших примеров этот указатель не требуется, и можно считать, что тип TreeNode определяется как
typedef struct Tr { Type value; struct Tr *left,*right;
} TreeNode;
Следует сказать, что экономия памяти за счет исключения указателя prev в случае очень “глубоких” деревьев может вызвать определенные трудности при выполнении программы из-за переполнения системного стека в связи с большой вложенностью рекурсивных вызовов. Поэтому, несмотря на то, что
Глава II. Базовые алгоритмы и структуры рекурсивные алгоритмы зачастую выглядят более элегантными и короткими, в ряде случаев более эффективными могут оказаться нерекурсивные алгоритмы обработки вершин дерева.
Рассмотрим теперь принципы реализации произвольных деревьев. К сожалению, в этом случае нам уже не удастся хранить в текущей вершине указатели на каждого потомка, поскольку мы не можем предсказать, сколько их будет в конкретном дереве. Даже если мы имеем некоторую оценку максимального количества потомков для каждой вершины, то резервировать место под хранение всех таких указателей может оказаться слишком накладным. Оказывается, что в случае произвольного дерева можно обойтись всего двумя (или тремя) указателями на каждую вершину, если немного усложнить процедуру перемещения по дереву. Идея состоит в следующем. Возьмем всех потомков данной конкретной вершины и свяжем их в однонаправленный список в том порядке, в котором они появляются в дереве. В родительскую вершину поместим указатель на начало этого списка. Таким образом, в каждой вершине будут храниться два указателя: на следующий элемент в списке “братьев” и на начало списка потомков данной вершины. При необходимости прямого перемещения назад к корню, можно добавить еще один указатель на родительскую вершину. Как всегда, нулевое значение указателя соответствует отсутствию последующего элемента (т.е. концу списка потомков или концу ветви).
Рис. 7.2. Схема ссылок в произвольном дереве.
На этом рисунке пунктирными линиями изображены логические связи между вершинами исходного дерева, а сплошными
линиями — связи, определяемые указателями, хранящимися в реализации дерева. Определение типа TreeNode здесь может выглядеть, например, так
typedef struct Tr {
Type value;
struct Tr ♦next, ♦down;
} TreeNode;
где указатель next отвечает за связь “братьев”, а указатель down указывает на списов потомков данной вершины.
Процедуры обхода произвольного дерева строятся по аналогии с бинарным деревом. Правда, обход слева-направо теряет смысл, так как неясно в какой момент (т.е. между какими потомками) следует обрабатывать родительскую вершину. Приведем для примера процедуру обхода сверху-вниз для той же задачи, что и раньше (для вычисления максимума).
void Up.Down (TreeNode *pos, Type ♦max) {
if (!pos) return ;
if ( ♦max < pos->value ) *max=pos->value;
pos = pos->down;
while (pos)
{ Up_Down (pos, max); pos = pos->next;
Отметим, что чисто топологически реализация произвольного дерева соответствует реализации некоторого бинарного дерева (так как каждый элемент имеет две ссылки на “последующие” элементы). Поэтому в тех задачах обходов произвольных деревьев, где не требуется отслеживать принадлежность элементов определенному уровню, можно применять алгоритмы обходов бинарных деревьев.
7.2 Деревья поиска
Во многих задачах требуется обеспечить эффективный поиск и размещение данных, которые имеют между собой некоторое отношение порядка. Простейшим примером может служить набор чисел с естественными отношениями “больше” или ‘меньше . Если мы рассмотрим упорядоченный числовой массив, то, как известно (метод деления пополам), процедура поиска конкретного значения в таком массиве может быть реализована с вычислительной сложностью (т.е. числом арифметических операций, необходимых для выполнения работы) порядка O(log2N), где N — количество элементов в массиве. Однако, процедура вставки элемента в упорядоченный массив требует уже O(N) операций, так как при этом нужно “раздвинуть” элементы массива, чтобы освободить место для нового элемента. Добавление элемента в неупорядоченный массив выполняется всего за 0(1) действий (элемент просто приписывается в конец массива), но поиск уже приходится выполнять последовательным просмотром, что требует 0(N) действий. Эти две крайние точки в оценках трудоемкости добавления и поиска вызывают желание построить реализацию хранения и поиска набора данных с “промежуточными” характеристиками трудоемкости. Идеальным средством для этого служат бинарные деревья.
Определриир 6. Назовем ключам вершины дерева некоторое значение, которое однозначно вычисляется по содержательной информации, хранящейся в данной вершине и связано некоторым отношением порядка с ключами других вершин. Ключ используется для поиска или сравнения вершин дерева.
Чтобы не усложнять приводимых далее примеров, мы будем считать, что ключей вершины, определяемой указателем ров, является само значение pos->value. Это предположение не. вводит существенных ограничений, поскольку в программной реализации перед сравнением всегда можно предусмотреть вызов некоторой функции, вычисляющей значение ключа по значению pos->value.
Определение 7. Будем называть бинарное дерево деревом поиска, если для любой вершины ключ этой вершины не меньше ключа любой вершины левого поддерева и строго меньше ключа любой вершины правого поддерева.
Деревья поиска являются очень удобным средством для хранения наборов данных, когда основными операциями с этими данными является добавление, удаление и поиск. Последнее определение задает инвариант:
pos->left->value <= pos->value < pos->right->value
Этот инвариант позволяет легко построить рекурсивные процедуры работы с деревом поиска. Действительно, сравнивая значение ключа искомого элемента с ключем текущей вершины, мы затем переадресуем его на левое или правое поддеревья в зависимости от результата сравнения. Подобное продвижение элемента по ветвям дерева завершается, когда обнаружится совпадение ключей, либо очередное поддерево окажется пустым.
Реализуем процедуру поиска данного элемента в поддереве. В качестве параметров этой процедуры разумно будет выбрать указатель на стартовую вершину поиска, сам искомый элемент, а возвращаемое значение — указатель на найденную вершину с требуемым ключем, либо 0, если такая вершина отсутствует в дереве.
/♦
* Рекурсивный поиск в дереве поиска
♦/
TreeNode ♦T.Search (Type х, TreeNode *start) {
if ( ’start ) return 0; /♦ дерево пусто ♦/
if ( x == start->value ) return start; /♦ нашли ♦/
if ( x < start->value ) return T_Search(x,start->left);
else return T_Search(x,start->right);
Нерекурсивный вариант этой процедуры выглядит еще проще.
/♦
♦ Нерекурсивный поиск в дереве поиска
♦/
TreeNode ♦T^Search (Type х, TreeNode *start) {
while ( start )
{ if ( x == start->value ) break; start = ( x < start->value ) ? start->left : start->right;
} return start;
}
Аналогично строится процедура добавления элемента в дерево поиска. Здесь следует сделать одно замечание. Мы можем подходить к формированию дерева с двух различных позиций, а именно, дублировать или не дублировать элементы с одинаковыми ключами. В первом случае процедура добавления будет всегда включать в дерево новый элемент, во втором случае при обнаружении вершины с тем же ключом процедура будет просто завершаться (раз такой элемент уже есть — еще раз его добавлять не надо). Наш пример будет относиться к первому варианту. Относительно параметров и возвращаемого значения примем для определенности следующие решения: параметры — добавляемый элемент и указатель на корень дерева, возвращаемое значение — указатель на корень всего дерева, либо ноль, если добавить не удалось. Для размещения новой вершины в памяти будем как и в случае списков использовать некоторую функцию GetPlace(), возвращающую при каждом обращении указатель на блок памяти размером sizeof (TreeNode) байт.
/♦
* Рекурсивное добавление нового элемента в дерево ♦/
TreeNode *T_AddElement (Type х, TreeNode *root)
TreeNode *pos;
if ( !root ) /♦ пустое дерево ♦/
{ root • (TreeNode*) GetPlaceO; if ( root )
{ root->value = x;
root->left = root->right = 0;
}
}
else /♦ непустое дерево -> рекурсия ♦/
{ if ( x<=root->value )
{ pos = T.AddElement (x,root->left)) )
if (pos) root->left=pos; else return 0;
} else
{ pos = T.AddElement (x,root->right)) ) if (pos) root->right=pos; else return 0;
}
return root;
Нетрудно построить и нерекурсивную процедуру, хотя выглядит она менее элегантно.
/♦
* Нерекурсивное добавление нового элемента в дерево
♦/
TreeNode ♦T.AddElement (Type х, TreeNode *root)
{
TreeNode *pos,*old;
int dir;
/♦ пустое дерево ♦/ if ( .’root )
{ pos = (TreeNode*) GetPlaceO;
if ( pos )
{ pos->left = pos->right = 0;
pos->value = x;
}
return pos;
}
/♦ непустое дерево ♦/
for (pos=root; pos; ) /♦ поиск позиции добавления '*/
{ old = pos;
if ( x<=pos->value ) { pos=pos->left; dir=0; }
else { pos=pos->right; dir=l; }
}
pos = (TreeNode*) GetPlaceO;
if ( !pos ) return 0;
pos->left = pos->right = 0;
pos->value = x;
if (dir) old->right = pos;
else old->left = pos;
return root;
Комментарии к программе. Указатель old определяет родительскую вершину по отношению к добавляемому элементу. Поскольку мы здесь отказались от рекурсии, то для того, чтобы установить нужные ссылки, требуется знать где — слева или справа — будет присоединен новый элемент к этой вершине. Для этого мы вводим переменную dir, которая хранит направление последнего сделанного поворота при спуске по ветви (0 — налево, 1 —направо). Последующая проверка значения переменной dir позволяет правильно установить ссылки от родительской вершины.
Теперь обсудим алгоритм удаления элемента. Если элемент является концевым или имеет только одного потомка, то удаление не вызывает особых проблем. Достаточно перенести ссылку от родительской вершины на соответствующего потомка. В случае с двумя потомками удалить элемент так просто не удастся. Действительно, здесь уже имеется три ссылки (от родителя к данной вершине и от вершины к двум потомкам). Эти ссылки невозможно замкнуть друг на друга. Идея удаления состоит в том, что удаляемая вершина как структурный элемент дерева на самом деле остается на месте, но данные, хранящиеся в этой вершине, заменяются на другие. Поясним эту идею на примере. Рассмотрим дерево, изображенное на рисунке, где в вершинах дерева проставлены ключи элементов. Пусть мы хотим удалить из этого дерева элементы с ключами 5 и 12.
Рис. 7.3. Дерево до удаления элементов.
Найдем в дереве вершины, содержимое которых можно подставить вместо удаляемых данных так, чтобы дерево сохранило свойство упорядоченности (осталось деревом поиска). В нашем примере этими вершинами, очевидно, будут вершины с ключами 4 (для 5) и 11 (для 12). Перенесем данные из этих вершин в “удаляемые” вершины (с ключами 5 и 12).
Рис. 7.4. Сделана замена значений, должны быть удалены помеченные вершины.
Теперь можно удалить вершины (отмеченные двойной рамкой), хранившие эти данные ранее, поскольку они имеют только по одному потомку.
Рис. 7.5. Дерево после удаления помеченных вершин.
Анализируя рассмотренный пример, мы приходим к следующему неформальному алгоритму удаления.
1. Если удаляемая вершина является концевой (не имеет потомков), то достаточно освободить память, занимаемую этой вершиной, и обнулить соответствующую ссылку от родительской вершины.
2. Если удаляемая вершина имеет ровно одного потомка, то после удаления вершины из памяти ссылка от родительской вершины переставляется на этого потомка.
3. В случае двух потомков сначала в левом поддереве удаляемой вершины ищется вершина с максимальным ключем. Заметим, что эта “максимальная” вершина обязательно является либо концевой, либо имеет только одного потомка. Для того, чтобы ее найти, достаточно спускаться по самой правой ветви левого поддерева до тех пор, пока не обнаружится нулевая ссылка направо. Найдя нужную “максимальную” вершину, переносим данные из нее в “удаляемую” вершину. Теперь “максимальную” вершину можно удалить, что выполняется с помощью пунктов 1 или 2.
Заметим, что пункты 1 и 2 можно реализовать одной и той же последовательностью операторов, а пункт 3 следует рассматривать не столько как удаление элемента динамической 78
структуры данных, сколько как удаление указанных данных из этой структуры.
Реализация рассмотренного алгоритма приводит к следующей программе.
/♦
* Удаление из дерева поиска
♦/
TreeNode ♦ T_DelElement (Type х, TreeNode *root)
TreeNode «pos;
/♦ пустое дерево ♦/
if ( !root ) return 0;
/♦ непустое дерево ♦/
if ( x==root->value ) /♦ если удаляется корень ♦/
{ /♦ не более одного потомка ♦/
if ( !root->left ) return root->right;
if ( !root->right ) return root->left;
/♦ два потомка ♦/
/♦ ищем "максимальную0 вершину для подмены */
for ( poseroot->left; pos->right; ) pos = pos->right;
root->value = pos->value;
/* удаляем не нужную уже ''максимальную" вершину */ root->left = T.DelElement (pos->value ,root->left) ;
else /♦ рекурсия, если удаляется не корень ♦/
{ if ( x<root->value )
root->left = T_DelElement (x,root->left);
else
root->right « T.DelElement (x,root->right) ;
return root;
}
7.3 Сбалансированные деревья поиска
Деревья поиска хороши тем, что вычислительная сложность (т.е. количество арифметических и логических операций) выполнения
процедур поиска, добавления и удаления элемента зависит от длины пути от корня дерева до интересующей нас вершины и в худшем случае определяется длиной максимальной ветви дерева. В случае дерева, в котором вершины имеют, как правило, двух потомков длина максимальной ветви оценивается величиной O(log2 N), где N — общее число вершин дерева. Однако, надеяться на то, что дерево поиска, сформированное с помощью описанного выше алгоритма добавления, окажется именно таким, в общем случае мы не можем. Действительно, если данные, последовательно поступающие на вход процедуры добавления, окажутся упорядоченными, например, по убыванию, то каждый новый элемент будет добавляться в левое поддерево относительно последнего добавленного элемента. Таким образом, дерево выродится в линейный список, а поиск в таком дереве будет в среднем иметь сложность O(JV). С другой стороны, те же самые данные можно организовать в виде другого дерева поиска, где каждая ветвь будет иметь длину порядка O(log2 ЛГ).
Рис. 7.6. Два дерева поиска и одними и теми же данными
Нельзя ли так организовать процесс добавления элементов в дерево поиска, чтобы все его ветви “росли” по возможности равномерно? Ответ на этот вопрос — да. Для большей четкости дальнейшего изложения введем несколько определений.
Определение 8. Бинарное дерево называется идеально сбалансированным, если длины любых двух его ветвей (считая от корня) отличаются не более чем на единицу.
Идеально сбалансированное дерево решает поставленную задачу, так как в нем длина любой ветви не превосходит величины [log2 ЛГ] 4-1. К сожалению, формирование такого дерева достаточно трудоемкая процедура. Поэтому мы несколько ослабим требования на идеальность балансировки дерева и попытаемся за счет этого построить более эффективные алгоритмы. Итак, вместо идеально сбалансированного дерева введем понятие сбалансированного дерева.
Определение 9. Длиной дерева будем называть длину его максимальной ветви.
Таким образом, длина дерева — это максимальное расстояние от корня до концевых вершин.
Определение 10. Бинарное дерево называется сбалансированным, если в любой его вершине длины левого и правого поддеревьев отличаются не более чем на 1.
Очевидно, что идеально сбалансированное дерево является сбалансированным. Обратное неверно, как видно из примера, изображенного на рисунке 7.7.
Рис. 7.7. Сбалансированное, но не идеально сбалансированное, дерево.
Видно, что в каждой вершине выполнено условие сбалансированности, но длины двух ветвей, исходящих от корня и
выделенных двойной линией отличаются на 2.
Упражнение. Доказать, что длина “наихудшего” сбалансированного дерева превосходит длину идеально сбалансированного дерева с таким же числом вершин не более чем в 1.5 раза.
Указание. Нужно построить “наихудшее” сбалансированное дерево, т.е. такое, в котором в каждой вершине (за исключением концевых) левое поддерево длинее правого на единицу. Обозначив через N(fc) количество элементов в таком дереве, имеющем длину fc, можно получить рекуррентные соотношения
N(Q) = О, N(l) = 1, AT(fc) = N(k - 1) + N(k - 2) + 1, из которых и выводится требуемое утверждение.
Сформулированное выше упражнение показывает, что трудоемкость поиска в сбалансированном дереве есть также величина порядка O(log2N). Но самое главное — это то, что добавление и удаление элементов в таком дереве также можно выполнить с трудоемкостью O(log2 TV). Опишем эти процедуры. Прежде всего отметим, что мы имеем дело с деревом поиска и размещение элементов в узлах дерева должно удовлетворять условию упорядоченности ключей в левом и правом поддеревьях. С другой стороны, наличие нескольких элементов с одинаковыми ключами может войти в противоречие либо с требованием упорядоченности, либо с требованием сбалансированности. Действительно, достаточно рассмотреть случай, когда все элементы имеют один и тот же ключ. Обычное дерево поиска в этом случае выродится в одну (левую) ветвь. Организовав те же самые элементы в сбалансированное дерево, мы нарушим требование превосходства ключей в правом поддереве по отношению к ключам левого. В дальнейшем, рассматривая сбалансированные деревья, мы будем считать, что все элементы в них имеют различные ключи. Естественно, что алгоритмы работы со сбалансированным деревом окажутся сложнее, чем алгоритмы работы с обычным деревом поиска. Поэтому здесь мы ограничимся описанием рекурсивных процедур.
Добавление элемента подчиняется тем же принципам, что и для обычного дерева поиска. Но добавленный в дерево элемент может нарушить сбалансированность в вершинах, расположенных выше. Следовательно, нам придется восстанавливать сбалансированность, т.е. некоторым образом перестраивать дерево на обратном проходе рекурсии. Для этого нам необходимо иметь информацию о текущей сбалансированности дерева. Для разрешения последнего требования мы будем в каждой вершине хранить показатель ее сбалансированнойсти, например, как значение разности длин правого и левого поддерева.
typedef struct Tr {
Type value;
int balance;
struct Tr *left, *right; } TreeNode;
Если поле balance имеет значения —1,0,1, то данная вершина сбалансирована, в противном случае нам придется перестраивать дерево. Сначала поясним процесс добавления элемента на схеме. Итак, наша процедура добавляет элемент в поддерево с корнем А, рекурсивно вызывая себя для левого или правого поддерева вершины А в зависимости от результата сравнения добавляемого элемента со значением, расположенным в вершине А. Возвращаясь из рекурсивных вызовов, процедура добавления балансирует дерево. Таким образом, вернувшись в вершину А, мы должны установить правильный баланс в этой вершине. Для этого нам надо знать как изменились длины поддеревьев в результате добавления. Вернувшись в конце концов к корню всего дерева, мы получим полностью сбалансированное дерево с добавленным элементом. Способ балансировки в вершине А зависит от того, в какое поддерево (левое или правое) был добавлен элемент, поэтому для определенности рассмотрим случай добавления в левое поддерево. Рассмотрим состояние дерева до и после добавления элемента.
Рис. 7.8. Поддерево до и после добавления
Здесь AL' и AR обозначают соответственно правое и левое поддеревья в вершине A, a AL — поддерево, получившееся после добавления элемента. Отметим, что по предположению рекурсии дерево AL будет уже сбалансированным и наша задача — сбалансировать поддерево в корнем А. Обозначим через Лдь, Лдя, fiAL' длины соответствующих поддеревьев. Возможны два случая:
1. hAL = Лд£/, здесь ничего делать не надо, поскольку для вершины А в смысле баланса ничего не изменилось.
2. Лдь = Ьаь’ + 1 (т.е. длина левого поддерева увеличилась), здесь возможны варианты в зависимости от первоначального значения баланса в вершине А.
Таблица, 7Л.
старый баланс в вершине А новый баланс в вершине А длина дерева в вершине А балансировка
1 0 не изменилась не нужна
0 -1 увеличилась на 1 не нужна
-1 -2 увеличилась на 1 нужна
Заметим, что в последнем случае старая длина дерева в вершине А равнялась Лд = Лд£'+1 = Лая+2 (так как при балансе —1 мы имеем Лд^г = Лдд -Ь 1). Обозначим к = Наь>< Тогда для нового дерева имеем Лдд = к + 1, Лдя = к — 1. Так как баланс в вершине А был равен — 1, то к > 0. Следовательно, в дереве AL есть по крайней мере две вершины, и мы можем представить наше новое дерево в виде \ п
Рис. 7.9. Длины и балансы подеревьев при добавлении в левое поддерево для баланса —1 в вершине А.
где BL yl BR — поддеревья корня В поддерева AL, справа от вершин указаны длины соответствующих поддеревьев, а в вершине А проставлен реально получившийся баланс. Поскольку дерево с корнем В уже сбалансировано нашей рекурсивной процедурой, мы можем рассмотреть формально три случая
1. Баланс в В есть 0, т.е. Ьвь = Лвя = к. Перестраиваем дерево следующим образом (в вершинах указаны старые и новые балансы и длины).
Рис. 7.10. Перестройка при балансе В, равном 0.
Из этой диаграмы видно, что длина нового дерева увеличилась по сравнению со старой (было к 4-1, стало к+2). Нетрудно заметить, что упорядоченность вершин и поддеревьев тоже сохранилась.
2. Баланс в В есть -1, т.е. Лдь = к, Hbr = к - 1.
Рис. 7.11. Перестройка при балансе В, равном -1.
Этот случай отличается от предыдущего только расстановкой балансов и тем, что длина нового поддерева с корнем А совпадает со старой длиной. £
3. Баланс в В есть 1, т.е. Iibl = Л — 1, Ъ>вя = к.
Рис. 7.12. Перестройка при балансе В, равном 1.
Здесь длина нового дерева не увеличилась по сравнению со старым, баланс в новом корне С всегда равен нулю, а балансы в вершинах А и В зависят от старого баланса в вершине С (на диаграмме указаны возможные длины поддеревьев CL и CR).
Назовем Ll-перестройкой преобразование дерева в соответствии с пунктами 1 и 2, а преобразование из пункта 3 — L2-перестройкой.
Суммируя вышесказанное, составим сводную таблицу балансировки для случая добавления в левое поддерево.
Таблица, 7.2.
балансы изм .длины перестройка
старые АВС новые АВС
1 - - 0 - - 0 -
0 - - -1 - - 1 -
-1 -1 - 0 0 - 0 L1
-1 0 - -1 1 - 1 L1
-110 ООО 0 L2
-1 1 1 0-10 0 L2
-1 1 -1 1 0 0 0 L2
Более внимательный анализ диаграмм и таблиц показывает,3 что если после добавления и балансировки дерева баланс его\ :7 корня оказывается равным нулю, то длина этого дерева не 1 # возрастает и, следовательно, случай 1 (Ll-перестройка с балансом ) В, равным нулю) никогда не возникает. Таким образом, при построении программы мы можем не рассматривать этот случай.
При добавлении элемента в правое поддерево рассуждения проводятся аналогично. Опираясь на построенные диаграммы и таблицы, можно реализовать процедуру добавления с балансировкой. Для удобства выделим процедуры перестройки дерева с расстановкой необходимых балансов в отдельные функции. Функция Rebuild.Ll будет перестраивать дерево и корректировать балансы в соответствием со схемой Ll-перестройки, Функция Rebuild_L2 — в соответствии со схемой Ь2-перестройки. Функции Rebuild.Rl и Rebuild_R2 являются их симметричными аналогами применительно к добавлению в правое поддерево. Все эти функции будут возвращать указатель на новый корень полученного поддерева.
TreeNode ♦ Rebuild.Ll ( TreeNode *А )
TreeNode «В;
В = A->left;
A->left = B->right;
B->right = А;
if (B->balance) { A->balance = 0; B->balance = 0; } else { A->balance =-l; B->balance = 1; }
return B;
TreeNode ♦ Rebuild_L2 ( TreeNode *A ) {
TreeNode *B, *C;
В = A->left; C = B->right;
A->left = C->right;
B->right = C->left;
C->left = B; C~>right » A; svitch ( C->balance ) {
case 0: A->balance = 0; B->balance = 0; break;
case -1: A->balance = 1; B->balance = 0; break;
case 1: A->balance = 0; B->balance =-l;
C->balance = 0; return C;
TreeNode ♦ Rebuild.Rl ( TreeNode *A ) {
TreeNode *B;
В = A->right;
A->right = B->left;
B->left = A;
if ( B->balance ) { A->balance = 0; B->balance = 0; } else { A->balance = 1; B->balance = -1;}
return B;
}
TreeNode ♦ Rebuild_R2 ( TreeNode *A ) {
TreeNode *B, *C;
В » A->right;
C = B->left;
П. 7. Деревья .—----
= C->right;
A->right = C->left;
C->left = A;
C->right = B;
switch ( C->balance )
{
case 0: A->balance = 0; B->balance = 0; break;
case 1: A->balance = -1; B->balance = 0; break;
case -1: A->balance = 0; B->balance = 1;
}
C->balance = 0;
return C;
Теперь реализация функции добавления с балансировкой не составляет труда. Как видно из схем перестройки дерева, после балансировки корнем может стать другая вершина, поэтому естественно в качестве возвращаемого значения для нашей функции выбрать указатель на новый полученный корень. Заметим также, что нам надо знать увеличилась ли длина дерева в процессе добавления. Поэтому нам потребуется еще один дополнительный параметр grow, который будет равен удлинению дерева после добавления. Итак, мы приходим к следующей реализации.
/♦
* Добавить элемент х в дерево поиска с корнем root
* с балансировкой.
♦
* Если корень не существует (root==0), создается новое дерево.
* grow - признак удлинения дерева.
* Возвр. указатель на корень или 0, если нет памяти.
*/
TreeNode ♦T.AddBalance (Type х, TreeNode ♦root, int ♦grow) {
int incr;
♦grow = 0;
/♦ пустое дерево ♦/
if ( !root )
{ root = (TreeNode*) GetPlaceO; if ( root )
{ root->left = root->right = 0; root->value = x;
root->balance = 0;
♦grow = 1;
} return root;
/♦ непустое дерево ♦/ if ( x<sroot->value ) /♦ левая балансировка ♦/ { root->left = T_AddBalance(x,root->left,&incr);
if ( incr )
{ switch ( root->balance ) { case 0: root->balance = -1; *grow=l; break;
case 1: root->balance = 0; break;
case -1:
switch ( root->left->balance ) {
case -1: root = Rebuild_Ll(root); break;
case 1: root = Rebuild_L2 (root);
else
/♦ правая балансировка ♦/
{ root->right = T_AddBalance(x,root->right,&incr); if ( incr ) { switch (root->balance)
{ case 0: root->balance = 1; ♦grow=l; break; case -1: root->balance = 0; break;
case 1:
switch ( root->right->balance ) {
f
case 1: root = Rebuild.Rl(root); break;
case -1: root = Rebuild_R2(root);
}
}
return root;
Замечание. В данной реализации есть некоторое неудобство. Мы договорились возвращать нуль в случае нехватки памяти для размещения нового элемента. Но так как корень дерева меняется в процессе добавления, то типичный фрагмент программы, заполняющей дерево, скажем, целыми числами, читаемыми из файла, мог бы выглядеть так:
typedef int Type;
FILE *fin;
Type x;
TreeNode ♦root=0;
int grow;
while ( fscan! (fin, ”7.d" ,&x)==l )
root = T.AddBalance (x,root,&grow);
Как следствие, указатель на корень может быть безвозвратно потерян, и мы не получим доступ к уже сформированному к этому моменту дереву. Правильный вариант заполнения должен учитывать эту особенность и может быть, например, таким:
typedef int Type;
FILE *fin;
Type x;
TreeNode ♦root=0, *pos; int grow;
while ( fscanf(fli '*7.d’',&x)==l )
{ pos = T.AddBalance (x,root,&grow); if (pos) root=pos; else break;
I
Теперь рассмотрим удаление из сбалансированного дерева. В целом эта процедура аналогична удалению из обычного дерева поиска. Если удаляемая вершина имеет не более одного потомка, то достаточно переставить ссылку с родительской вершины на соответствующего потомка. Если же потомков два, то, как и раньше, в левом поддереве ищется вершина для подмены значения удаляемой вершины. Отличие алгоритма связано в необходимостью балансировки текущей вершины, если при удалении элемента длина левого или правого поддеревьев уменьшилась. Отметим, что процедуры перестройки оказываются точно такими же, как и в случае добавления, поскольку разбалансировка при удалении из левого поддерева совпадает с разбалансировкой при добавлении в правое поддерево. Поэтому рассмотрим удаление из левого поддерева без особых дополнительных пояснений. Итак, мы имели поддерево^вершиной А и старой длиной k + 1, и при удалении уменьшилась длина поддерева AL. Если балансы А были равны —1 или 0, то перестройка не нужна, а балансировка сводится только к коррекции баланса вершины А. Если баланс А был равен 1, то наше поддерево принимает вид
Рис. 7.13. Удаление элемента из левого поддерева.
Опять рассмотрим балансы в вершине В.
1. Баланс В есть 0. Выполняется Rl-перестройка.
Длина поддерева с вершиной А не изменилась.
2. Баланс В есть 1. Выполняется Rl-перестройка.
Рис. 7.15. Перестройка при балансе В, равном 1.
Длина поддерева с вершиной А уменьшилась.
3. Баланс В есть —1. Выполняется Я2-перестройка.
Рис. 7.16. Перестройка при балансе В, равном —1.
Длина поддерева с вершиной А уменьшилась, а балансы в вершинах А и В зависят от старого баланса С.
Сводная информация о замене балансов при удалении из левого поддерева приведена в таблице 7.16.
Заметим, что если после удаления и балансировки длина дерева уменьшается, то баланс корня всегда будет равен нулю. К сожалению, в отличие от процедуры добавления, этот факт не позволит упростить программу, поскольку в данном случае удаление и соответствующая балансировка выполняются для левого поддерева, а перестройка захватывает правое поддерево (баланс поддерева AL нигде не участвует).
Таблица 7.3.
балансы изм.ДЛИНЫ перестройка
старые ABC новые ABC
1 - - 0 - - -1 -
0 - - 1 - - 0 -
-1 41 - 1 4 QA R1
-1 0 - 0 0 { -i R1
-1 -1 0 0 0 0 -i R2
-1 -1 -1 -p ф 0 -1 R2
-1 “I 1 O-flL о -1 R2
Параметры функции для удаления элемента устроены точно так же, как и для функции добавления. Приведем ее текст без дальнейших пояснений.
/♦
* Удалить элемент х из дерева поиска с корнем root
* с балансировкой
* Возвр. указатель на корень нового дерева.
♦ /
TreeNode ♦T^DelBalance (Type х, TreeNode ♦root, int *grow) {
int incr;
TreeNode *pos;
♦grow = 0;
/♦ пустое дерево ♦/
if ( !root ) return 0;
/♦ непустое дерево ♦/ if ( x==root->value ) { /♦ элемент имеет только одного потомка */
if ( root->left==0 )
{ ♦grows-1;
pos=root->right;
FreePlace(root); return pos;
if ( root->right==0 )
{ ♦grows-1;
pos=root->left;
FreePlace(root);
return pos;
}
/♦ элемент имеет обоих потомков ♦/
/♦ ищем элемент для подмены ♦/
for ( pos=root->left; pos->right; ) pos = pos->right; root->value ® pos->value;
root->left = T.DelBalance(pos->value,root->left,fcincr) ; if (incr) { switch ( root->balance )
{ case -1: root->balance=0; ♦grow=-l; break;
case 0: root->balance=l; break; case 1:
switch ( root->right->balance ) {
case 1: «grows-l;
case 0: root = Rebuild.Rl(root); break;
case -1: root = Rebuild_R2(root);
♦grow = -1; }
}
}
}
else
{ if ( x<root->value )
{ root->left = T.DelBalance (x,root->left,&incr); if (incr) { switch ( root->balance )
{ case -1: root->balance=0; ♦grow=-l; break; case 0: root->balance=l; break;
case 1:
switch ( root->right->balance ) {
case 1: ♦grow=-l;
case 0: root = Rebuild.Rl(root); break;
case -1: root = Rebuild_R2(root);
♦grow = -1;
else
{ root->right = T.DelBalance (x,root->right,&incr); if (incr) { switch ( root->balance )
{ case 1: root->balance=0; ♦grow=-l; break; case 0: root->balance=-l; break;
case -1: switch ( root->left->balance ) {
case -1: ♦grow=-l;
case 0: root = Rebuild.Ll(root); break;
case 1: root = Rebuild.L2(root); ♦grow = -1;
}
}
}
}
return root;
7.4 В-деревья
Встречаются ситуации, когда обрабатываемые наборы данных невозможно полностью разместить в оперативной памяти. В этом случае их частично приходится хранить на диске и по мере необходимости считывать в память, предварительно освобождая место и записывая обратно на диск не используемые в данный момент данные. В такой постановке задачи самыми неэффективными по времени являются именно операции обмена с диском. Таким образом, возникает проблема минимизации количества обращений к диску, возможно, за счет некоторого увеличения накладных расходов по памяти и времени доступа для данных, уже находящихся в оперативной памяти.
Для достижения этой цели удобным средством являются так называемые В-деревья. Дадим определение этой структуры.
Определение 11. В-деревом порядка п называется древовидная структура, удовлетворяющая следующим условиям:
• вершиной дерева является массив, способный вместить 2п элементов данных;
• в каждой вершине элементы данных расположены в массиве вершины в порядке возрастания их ключей.
• каждая вершина, кроме корневой, содержит не менее п и не более 2п элементов данных;
• вершина, содержащая к (п < к < 2п) элементов данных, имеет ровно к -I- 1-го потомка, либо является концевой, т.е. не имеет потомков;
• если вершина имеет к элементов, то ключи всех элементов поддерева г-го потомка меньше ключа г-го элемента и больше ключа (г — 1)-го элемента родительской вершины (для 0-го и к потомков рассматриваются только 0-й и (к-1)-й элементы, Соответственно);
• все концевые вершины лежат на одном уровне дерева;
В-дерево можно рассматривать как обобщение идеально
сбалансированного дерева поиска на случай множественного числа потомков.
низ
15|1б|17|18|
Рис. 7.17. Числовое В-дерево порядка 2, глубины 2.
Рассмотрим для простоты ситуацию, когда порядок дерева п является некоторым фиксированным числом (например, 2048). В этом случае реализацию В-дерева порядка п можно построить на основе структуры
tdefine п 2048 typedef struct _BTN {
Type value [2*n]; /♦ значения элементов ♦/
int k; /* количество элементов */
struct _BTN ♦down[2*n+l] ; /♦ ссылки на потомков ♦/
} BTreeNode;
где массив value предназначен для хранения элементов данных, значение к есть фактическое количество элементов данных в этой вершине, массив down определяет ссылки на потомков.
При размещении В-дерева в памяти мы вынуждены резервировать место для 2п элементов в каждой вершине. Следовательно, возможны потери памяти, которые в наихудшем случае сравнимы с количеством размещенных элементов данных. Нетрудно подсчитать, что длина В-дерева, содержащего N элементов данных, не превосходит O(lognN), что при п > 2 существенно меньше, чем у бинарного дерева. В-деревья обычно применяются в тех случаях, когда данные для каждой вершины В-дерева имеют значительный объем и изначально хранятся на диске. При работе с таким деревом его вершины считываются с диска по мере необходимости. Таким образом, доступ к
любому элементу требует прохождения по ветви дерева от корня до требуемого элемента, что можно осуществить за O(logn2Vj обращений к диску, считывая каждый раз массив данных длины 2п.
Поскольку реализация В-дерева должна обеспечивать возможность считывания с диска данных для вершин-потомков, в структуру BTreeNode можно ввести еще массив ссылок на место размещения данных этих вершин-потомков на диске, например, в виде смещений от начала соответствующего дискового файла:
#define п 2048
typedef struct _BTN {
Type value [2*n];
int k;
struct _BTN ♦down[2*n+l];
unsigned long file_offset[2*n+l]; /♦смещения в файле*/ } BTreeNode;
В этом случае ненулевой указатель down [к] определяет местоположение соответствующей вершины-потомка в памяти, а при нулевом значении down [к] мы прочитаем вершину из файла по смещению f ile.of f set [к], разместим ее в памяти, а адрес этого размещения занесем в down [к]. Для концевой вершины можно считать, что все значения массива f ile_off set равны нулю.
Опишем алгоритм поиска конкретного элемента х. Будем считать, что в нашем распоряжении есть процедура бинарного поиска элемента в заданной вершине В-дерева
Туре ♦ BT.NodeSearch( Type х, BTreeNode ♦node, int ♦ind);
которая возвращает указатель на найденный элемент или 0 в случае неудачи, а по указателю ind записывается индекс найденного элемента в массиве в случае успеха, либо индекс потомка, в котором нужно далее искать х, т.е.
О, если x<pos->value[0];
к, если x>pos->value [pos->k-l];
i, если pos->value[i-i]<x<pos->value[i] для 0<i<pos->k.
Для чтения вершины с диска и размещения ее в памяти у нас будет процедура ReadKodeFromDisk, которая имеет параметром требуемое смещение и возвращает адрес, по которому она разместила в памяти прочитанную вершину.
Процедура поиска элемента, которую мы собираемся построить, получает в качестве параметров искомый элемент х, стартовую вершину поиска node и возвращает указатель на найденный элемент, или 0 при отсутсвии такового.
Туре ♦ BT.Search (Type х, BTreeNode *node) { int ind;
Type *find;
// для пустого дерева ничего не делаем if ( !node ) return 0;
И пытаемся найти требуемый элемент if ( find = BT_NodeSearch(х,node,&ind) ) // нашли в корневой вершине return find;
else
{ 11 переходим к поиску в потомке, if ( !node->down[ind] )
{ // потомка нет в памяти, надо считать его с диска if ( !node->offset[ind] )
И концевая вершина return 0;
else
{ // пытаемся прочитать с диска node->down[ind]
= ReadNodeFromDisk (node->offset[ind]);
// проверим, удалось или нет if ( ! no de-> down [ind] ) return 0;
} }
II теперь потомок в памяти, ищем в нем return BT.Search(х,node->down[ind] );
} }
Не принимая во внимание действий по определению файла с данными и различных проверок корректности, использование этой процедуры может выглядеть, например, так:
BTreeNode ♦ root;
Type ♦ find;
root = ReadNodeFromDisk (0);
find = BT_Search(x,root);
(Здесь предполагается, что данные корневой вершины записаны в самом начале дискового файла.)
Нетрудно подсчитать, что сложность поиска в В-дереве порядка п с N элементами, в наихудшем случае сводится к проходу от корня до концевой вершины с выполнением бинарного поиска в вершинах каждого уровня, что составляет О(к^2(2п)1о^ЛГ) ~ O(log2 N) арифметических операций и сравнений.
Обсудим теперь идею алгоритма добавления элемента. Сначала отыскивается концевая вершина, в которую можно добавить требуемый элемент в соответствии с упорядоченностью существующих элементов. Если добавление элемента в массив этой вершины не превышает допустимый размер (напомним, что это 2п), то выполняется вставка в упорядоченный массив, и на этом процесс завершается. Если в концевой вершине (обозначим ее А) уже размещено 2п элементов, то, добавляя новое значение, мы получаем упорядоченный набор из 2п + 1 элементов. По определению В-дерева такое количество элементов не может быть размещено в вершине. Создается новая концевая вершина (обозначим ее В), и первые п элементов набора размещаются в старой вершине, последние п — во вновь созданной вершине, а средний элемент набора (обозначим его у) вставляется в родительскую вершину. При этом справа от у в родительской вершине вставляется ссылка на нового потомка В. Если прямое добавление у в родителькую вершину невозможно (она уже имела 2п элементов), то опять выполняется ее разделение на две вершины, а средний элемент переносится в вершину выше по ветви. При полной занятости всех вершин в ветви этот процесс
переноса среднего элемента распространяется до корня. Если корень также заполнен, то он аналогично разделяется на две вершины, а средний элемент образует новый корень. В отличие от бинарных деревьев поиска, В-дерево растет “снизу-вверх”. Самым трудоемким шагом в процедуре добавления является процесс разделения вершин, который требует “раздвигания” массивов данных для вставки нового элемента. Таким образом, наилучшая оценка трудоемкости составляет в среднем O(lognNlog2n + п) операций (спуск по ветви и одна вставка), а наихудшая оценка — O(nlogn7V) (происходит разделение вершин во всей ветви). Отметим, что последняя оценка не является такой уж обременительной, поскольку появляется много вершин, заполненных лишь наполовину, и последующие добавления уже долго не будут вызывать разделения вершин.
Алгоритм удаления элемента из В-дерева также имеет общие черты с удалением из бинарного дерева. Если нужный элемент лежит в концевой вершине, то удаление не составляет труда. Если же этот элемент расположен в другой вершине, то сначала он заменяется на максимальный элемент из поддерева, берущего свое начало от “левой” ссылки удаляемого элемента. Нетрудно понять, что этот элемент лежит в концевой вершине. Теперь можно удалить этот максимальный элемент. В результате удаления элемента из концевой вершины (обозначим ее А) может оказаться, что количество элементов в ней станет равным п — 1, т.е. нарушится одно из условий В-дерева. В этом случае производится балансировка, состоящая в объединении элементов вершины А, элемента у родительской вершины, для которого “левая” ссылка указывает на А и элементов соседней концевой вершины В (определяемой правой ссылкой от у). Полученный набор данных делится на равные (с точностью до одного элемента) “левую” и “правую” части, разделяемые “средним” элементом. Средний элемент заменяет у в родительской вершине, левая часть записывается в А, а правая — в В. Если в вершине В только п элементов, то такое слияние вершин невозможно (опять
нарушится условие В-дерева). В этом случае весь объединенный набор (его длина равна 2п) записывается в А, вершина В удаляется, и из родительской вершины также удаляется элемент у вместе со ссылкой на В. При удалении у из родительской вершины, число элементов в ней также может уменьшиться до п - 1. В этом случае аналогично перераспределяются элементы двух соседних вершин данного уровня (либо вершины сливаются в одну). Описанный процесс может распространиться до корня. Если количество элементов в корне при этом станет равным нулю (а это возможно только при слиянии двух его потомков), то корень удаляется, а новым корнем становится единственная объединенная при последнем слиянии вершина. Глубина дерева при этом уменьшается на единицу. Легко подсчитать, что сложность удаления совпадает со сложностью добавления и составляет от O(lognNlog2n 4- п) до O(nlognN) операций в зависимости от текущей заполненности вершин.
7.5 Упражнения
7.1. Реализуйте описанные выше деревья в виде классов на языке C++.
7.2. Постройте аналоги процедур обхода сверху-вниз и снизу-вверх для произвольных деревьев.
7.3. Постройте процедуры обхода для получения следующей информации о деревьях.
1. Определите длину бинарного (или произвольного) дерева (т.е. длину максимальной ветви).
2. Определите количество концевых элементов бинарного (произвольного) дерева
3. Определите количество ветвей, имеющих максимальную длину.
4. Определите количество элементов, лежащих на уровне к.
5. Найдите максимальный элемент среди всех элементов fc-ro уровня.
6. Проверьте является ли бинарное дерево сбалансированным.
7. Подсчитайте число несбалансированных вершин в бинарном дереве.
8. Подсчитайте показатель сбалансированности для бинарного дерева (т.е. максимальную разницу между длинами правого и левого поддеревьев для каждой вершины).
9. Распечатайте значения всех вершин fc-ro уровня дерева.
7.4. Реализуйте процедуры добавления и удаления элементов некоторого типа Туре на базе В-дерева.
7.5. Разработайте формат файла для сохранения В-дерева на диске и реализуйте процедуры добавления, удаления и поиска элементов некоторого типа Туре на базе В-дерева, при условии, что все дерево не помещается в оперативную память.
7.6. Реализуйте произвольное дерево, элементами которого являются текстовые символы. На базе такого дерева можно организовать словарь, в котором каждой ветви будет соответствовать некоторое слово.
8 Множества
Структуры данных, с которыми мы имели дело в предыдущих параграфах, предполагали наличие некоторых логических связей между элементами. Эти связи могли быть описаны в терминах “первый - последний” или “следующий - предыдущий”. В то же время существуют задачи, где упорядоченость данных не является существенной характеристикой на внешнем уровне представления. Для описания таких наборов данных наиболее подходит математическое понятие множества. С точки зрения задач обработки данных работа с множеством заключается в операциях добавления, удаления элемента, поиска конкретного
элемента, а также перебора всех элементов, принадлежащих данному множеству. Отдельную область составляют операции с множествами как с цельными объектами — объединение, пересечение и др. Эти операции можно реализовать на основе операций поиска, добавления, удаления элементов в каждом отдельном множестве. При конкретизации предписаний работы с множеством может получиться следующий результат:
• Создать множество (пустое).
• Уничтожить множество.
• Добавить элемент.
• Удалить данный элемент.
• Элемент принадлежит множеству ?
• Взять какой-нибудь элемент из множества.
• Множество пусто ?
• Для каждого элемента выполнить указанную операцию.
Списки и деревья можно рассматривать как некоторые реализации множеств, поскольку они позволяют организовать перебор всех элементов, а таже поиск элемента по его значению. Легко видеть, что на списках можно реализовать процедуру последовательного поиска, а поиск в бинарном дереве аналогичен методу деления пополам. Процедуры просмотра списка или обхода дерева реализуют операцию перебора в таком множестве. Однако, нас интересуют такие реализации множеств, которые были бы наиболее эффективны в отдельных частных случаях. Действительно, при большом числе элементов процедура последовательного поиска в списке может оказаться неприемлемой по времени выполнения, представление в виде дерева требует как минимум двух ссылок на каждый элемент, что вызывает увеличение объема используемой памяти.
В разделах данной главы мы опишем некоторые подходы к реализации множеств, которые можно использовать как отдельно, так и в дополнение к спискам или деревьям.
8.1 Битовая реализация множества
Рассмотрим один простой но важный частный случай эффективной реализации множества на основе существенного использования специфики постановки задачи.
Пусть нам требуется реализовать подмножество множества целых чисел, лежащих в диапазоне от 0 до некоторого числа Mnax — 1. В этом случае нам достаточно иметь массив из Nmax элементов, каждый из которых может принимать значения 0 и 1, т.е. элемент массива с номером к будет иметь значение 1, если число к принадлежит нашему множеству, и 0 — в противном случае. Таким образом, для реализации подобного множества нам достаточно хранить массив из Мпах бит, а для добавления или удаления элемента нужно устанавливать соответствующий бит этого массива в 1 или 0. Так как позиция каждого бита легко определяется по его номеру в массиве, то операции добавления и удаления можно выполнить очень эффективно. Реализация подобного множества сводится к реализации битового массива, которая основана на следующем очевидном способе: выделяется некоторый массив целых чисел, каждое из которых рассматривается как набор из фиксированного количества бит. Определение местоположения конкретного бита сводится в вычислению по-рядкого номера элемента базового массива чисел и определении номера нужного нам бита в этом элементе. Так как во многих процессорах за одно обращение к памяти можно прочитать 4 байта (32 бита), то мы примем в качестве базового типа числового массива тип unsigned long int. Нетрудно видеть, что если к — интересующий нас элемент числового множества, то номером элемента в базовом числовом массиве будет целая часть от деления А; на 32, а номером бита в этом элементе — остаток от деления fc на 32. Поскольку 32 — это степень двойки, то для повышения быстродействия деления и вычисления остатка можно воспользоваться битовыми операциями сдвига и логического умножения.
/♦
♦ Реализация множества элементов O...Nmax-l
♦ 4 байта на каждую ячейку хранения битов
♦ /
typedef unsigned long int BaseType;
#define cell_num(x) ((x)»5) /♦ номер ячейки ♦/
#define cell_bit(x) ((x)&0xlFL) /♦ номер бита в ячейке ♦/
BaseType * mem; /♦ указатель на массив базовых ячеек */
int Set Init (unsigned long maxsize)
unsigned long n;
n = cell.num(maxsize) +1;
mem = (BaseType*) calloc (n,sizeof(BaseType));
return (mem) ? maxsize : 0;
int Set.Find (unsigned long x) { return (int) ( mem [cell.num (x)] & (l«cell.bit(x)) ); }
void Set.Put (unsigned long x)
{ *(mem+cell.num(x)) 1= ( l«cell_bit (x) ) ; }
void Set.Del (unsigned long x)
{ *(mem+cell.num(x)) &= ~( l«cell-bit (x) ) ; }
Замечание к реализации. Здесь для краткости опущены проверки значения элемента множества на принадлежность заданному диапазону [0,ЛГШах “ !]• Для обеспечения надежности работы функции поиска, добавления и удаления должны делать такие проверки перед обращением к ячейкам, поскольку при некорректном значении элемента х обращение по указателю mem+cell_num(x) может вызвать аварийное завершение программы по защите памяти (access violation, segmentation fault и т.п.).
Заметим, что с такими множествами чрезвычайно легко выполнять объединения, пересечения и т.д. Действительно, для этого достаточно выполнить соответствующую операцию с ячейками базовых числовых массивов (например, для объединения —
операцию |, для пересечения ~ операцию &).
Битовая реализация множества достаточно редко применяется для больших числовых множеств, хотя можно привести примеры и с значительным количеством элементов. Как правило подобные реализации применяются тогда, когда нужно эффективно устанавливать и проверять состояния относительно небольшого числа объектов, описываемые в терминах "да/нет"(т.е. 1 и 0). Если же объекты множества имеют более сложную структуру, то битовое представление всех возможных состояний этих объектов может потребовать слишком много памяти и, следовательно, стать непримемлемым. В следующем разделе мы рассмотрим другой подход к построению множеств, который можно рассматривать как обобщение битового подхода.
8.2 Хеширование
Рассмотрим ситуацию, когда в каждый момент времени нам нужно работать с относительно небольшим подмножеством некоторого множества, которое содержит необозримое количество элементов. Типичным примером может служить множество слов в некотором конкретном тексте. Действительно, это множество относительно невелико, в то время как множество всех возможных слов (произвольных комбинаций печатных символов) содержит огромное количество элементов. Идея метода состоит в разделении исходного большого множество на несколько классов эквивалентности относительно некоторой функции (так называемой хеш-функции). Само слово хеширование происходит от английского слова hash, что дословно означает “рубить, крошить”. Опишем идею хеширования более формально. Итак, пусть М — исходное множество всех возможных элементов интересующего нас типа, a N С М — подмножество, с которым мы хотим в данный момент работать. Пусть на множестве М определена некоторая функция /, принимающая значения 0,...,р — 1, где р — некоторое натуральное число. Тогда функция f разбивает
множество М на классы эквивалентности М*:
Мк={хЕМ : f(x) = k}.
Теперь при работе с множеством N для каждого интересующего нас элемента х нам достаточно вычислить значение к = f(x) и далее работать с множеством Nk = Mk П N. При удачном выборе хеш-функции f количество элементов в множестве Nk будет в среднем в р раз меньше, чем во всем множестве N и, следовательно, поиск, добавление, удаление элементов будут выполняться существенно быстрее. Естественно, подобное ускорение работы не является гарантированным. Для любой хеш-функции можно указать такое множество ЛГ, что оно будет содержать элементы только одного класса эквивалентности и никакого выигрыша в быстродействии не будет. Однако, такая ситуация является скорее исключением, чем правилом и в большинстве практических применений удается выбрать хеш-функцию так, чтобы она более-менее равномерно распределяла элементы по классам эквивалентности.
Бытовым примером применения метода хеширования может служить телефонная записная книжка, где хеш-функция сопоставляет каждому слову (фамилии) его первую букву. Действительно, при поиске информации о данном человеке мы первым делом открываем страницу записной книжки на первую букву фамилии (“вычисляем” хеш-функцию), а затем ищем или добавляем нужную запись в пределах этой страницы (работаем с множеством Л^).
В программировании метод хеширования может быть реализован многими способами. Мы рассмотрим только два из них. Первый метод использует списки. Пусть мы имеем реализацию р независимых списков. Тогда естественно сопоставить fc-й список fc-му подмножеству Nk- Вычислив для интересующего нас элемента х значение хеш-функции к = /(х), мы переадресуем операции поиска, добавления, удаления элемента соответствующим процедурам работы с к-м списком. За выполнение операций
поиска или добавления и удаления в списках ответственны уже реализации самих списков, например, поиск может выполняться последовательным посмотром, добавление — всегда в начало списка, или любым другим способом.
Рис. 8.1. Схема хеш-реализации на основе списков.
Сопоставление каждого подмножества значению хеш-функции обычно выполняется с помощью хеш-таблицы. В случае со списками данная таблица представляет собой массив, в котором fc-й элемент содержит указатель на начало списка Л-го подмножества. Если какое-либо из подмножеств пусто, то соответствующий элемент хеш-таблицы равен нулю. Строго говоря, применение списков в подобной реализации не является обязательным. С тем же успехом это могут быть, например, бинарные деревья. В этом случае элементы каждого подмножества Nk можно разместить в дереве поиска по некоторому дополнительному критерию упорядоченности с вытекающей отсюда логарифмической сложностью поиска элемента в этом дереве, а в хеш-таблицу поместить указатели на корни этих деревьев.
Использование ссылочных структур для реализации каждого подмножества требует некоторых накладных расходов памяти на организацию ссылок. Например, если мы резервирует место для хранения п элементов со средним размером а байт каждый, а хеш-функция может принимать р различных значений, то
для хранения множества с помощью списков нам потребуется (а 4- Ь)п 4- pb байт, где b — количество байт в представлении адреса (обычно Ь = 4). Для деревьев (две ссылки на элемент) эта величина будет равна (а 4- 2Ь)п 4- рЬ. В случае, когда а ~ Ь, накладные расходы памяти могут составить значительный процент от общей памяти, отводимой для реализации множества.
Второй из рассматриваемых нами методов хеширования не использует дополнительной памяти в явном виде, но расплачивается за это усложнением алгоритмов добавления и, особенно, удаления. Это метод часто называют методом проб (см., например, [5]). Идея метода состоит в следующем. Пусть множество N содержит не более п элементов. Выберем диапазон значений хеш-функции (т.е. р) несколько ббльшим, чем п. Возьмем массив из р ячеек и будем размещать в нем элементы нашего множества (или указатели на эти элементы) в соответствии со значениями хеш-функции. Таким образом, если дать этому массиву имя Л, то для элемента х положим h[k] = х, где к = /(т). Однако, подобное размещение не всегда возможно. Действительно, при добавлении в множество нового элемента у может оказаться, что к = f(x) = /(?/), т.е. элемент у должен быть помещен в ячейку, которая уже занята элементом х. В этом случае попробуем разместить у в ячейку h[k 4-1], если и она занята, то попробуем разместить в Л[к4-2], и т.д. При достижении ячейки h[p — 1] перейдем к началу массива и продолжим пробы с ячейки Л[0]. Поскольку р > п, то рано или поздно найдется свободная ячейка для размещения у.
Поиск элемента х в множестве выполняется аналогично. Сначала проверяется ячейка Л[к], где к = /(т), если она не пуста и не содержит т, то проверяется следующая ячейка h[k 4- 1], и т.д. Поиск заканчивается обнаружением либо х, либо пустой ячейки. На первый взгляд подобный алгоритм не выглядит эффективным — вероятность коллизий (совпадений значений хеш-функции для различных элементов) кажется достаточно высокой. Однако это не совсем так. Рассмотрим сначала процесс добавления. Действительно, пусть хеш-функция равномерно
рассеивает элементы и мы имеем р ячеек для размещения, тп из которых уже заняты. Тогда вероятность того, что некоторая ячейка уже занята есть вероятность того, что свободна — qi = 2-—. Таким образом, с первой попытки элемент размещается с вероятностью qi = Вероятность разместить элемент со второй попытки вычисляется как произведение вероятности отказа при первой пробе на вероятность успеха во второй (при условии отказа в первой), т.е.
m p — m q2 = —----—.
p p-1
Проводя аналогичные рассуждения далее, получаем общую формулу для вероятности разместить элемент за к проб:
р — m j-r m — г
-p'-fc+l 11 p-i ’ r 1=0 r
Количество проб можно рассматривать как случайную величину, которая принимает значение к с вероятностью qk- Таким образом, ожидаемому среднему количеству проб при размещении или поиске элемента соответствует математическое ожидание этой случайной величины, т.е. сумма
E(m,p) = tn =
As=l
Обозначая через а коэффициент заполнения массива: a = получаем окончательную оценку для количества проб
E(m,p) = E(a) = -±-
1 — a
Приведем таблицу значений E(m,p) для некоторых a.
Таблица 8.1.
a ВД
0.1 1.И
0.3 1.43
0.5 2.00
0.7 3.33
0.9 10.0
Из этой таблицы вытекает несколько любопытных следствий. Во-первых, ожидаемое число проб не зависит от количества элементов в рабочем множестве, оно зависит только от коэффициента заполнения массива. Во-вторых, сравнительно небольшие накладные расходы памяти (порядка 20-30%) уже обеспечивают хорошие характеристики трудоемкости поиска (3-4 пробы)-Однако, при приближении коэффициента заполнения к единице, трудоемкость работы резко возрастает, поскольку в массиве образуются длинные участки заполненных ячеек, что приводит к коллизиям для большого числа значений хеш-функции.
К сожалению, при данном подходе весьма трудоемким является удаление элементов. Действительно, при удалении необходимо сохранять структуру заполнения массива, при которой каждый элемент должен быть расположен на позиции своего хеШ-значения или правее в непрерывном участке занятых ячеек. Ячейка может быть освобождена, если при этом не нарушаются правила размещения элементов, находящихся справа. Если это не так, то в освобождаемую ячейку следует записать подходящий элемент из правой части непрерывного участка занятых ячеек, что может повлечь за собой аналогичные действия для заполнения вновь освободившегося места перемещаемого элемента, и так далее до конца непрерывного участка. Таким образом, метод проб можно считать эффективным, если операция удаления элементов из множества в решаемой задаче выполняется достаточно редко.
Отдельную проблему при реализации хеширования составляет выбор хорошей хеш-функции. Эта функция должна обеспечи
вать равномерное рассеивание поступающего потока ключей элементов множества на диапазон своих значений. Кроме того, хеш-функция должна вычисляться достаточно быстро. Обычно подобные функции строятся на основе предварительного изучения статистики распределения значений ключей элементов и построения преобразования входного распределения ключей в равномерное распределение. Наиболее часто хеширование применяется для работы с множествами текстовых строк (слов). В этом случае используется специфическое перемешивание битов, составляющих коды символов слова так, чтобы малые изменения в битовом представлении слова порождало далеко отстоящие значения хеш-функции. Не вдаваясь в подробности, приведем в качестве примера одну из таких функций, отображающую текстовую строку в 32-битовое целое число. Если взять к младших битов этого числа, то мы получим достаточно равномерную хеш-функцию, принимающую 2к значений.
/* специальное перемешивание битов ♦/ ♦define mixCa.b.c) \
{\ a=a-b; b=b-c; c=c-a; a=a-b; b=b-c; c=c-a; a=a-b; b=b-c; a=a-c; a=a~(c»13); \ b=b-a; b=b*(a«8); \ c=c-b; c=c*(b»13); \ a=a-c; a=a~(c»12); \ b=b-a; b=b~(a«16); \ c=c-b; c=c~(b»5); \ a=a-c; a=a*(c»3); \ b=b-a; b=b*(a«10); \
c=c-a; i c=c-b; c=c*(b»15); \
j typedef unsigned long int u_long;
/♦ Хеш-функция
*s - указатель на входную строку
* length - количество символов входной строки
* Возвр. значение - 32-битовое значение хеш-функции
♦/
u.long hash( unsigned char *s, u.long length)
{
u.long a,b>c; /♦ рабочие переменные ♦/
u.long len; /♦ длина оставшейся части строки ♦/
/* формируем начальное внутренне состояние */
а = Ъ = 0х9е3779Ь9; /♦ это пропорция золотого сечения ♦/
с = 0; /♦ здесь можно поставить любое значение */
/* сворачиваем входную строку до длины в 12 байт */
for (len=length; len>=12; len-=12, s+=12) {
а += (u.long) s[0] I ( (u.long) s [1] «8) I
( (u.long) s [2] «16) | ( (u.long) s[3] «24);
b += (u.long) s [4] I ( (u.long) s [5] «8) I
( (u.long) s [6] «16) I ((u.long) s [7] «24) ;
c += (u.long)s[8] I ( (u.long) s [9] «8) I
( (u.long) s [10] «16) I ((u.long)s[ll]«24); mix(a,b,c);
/♦ перемешиваем биты в оставшихся 11 байтах */
с += length;
switch(len) /♦ оператор break здесь не нужен! ♦/
{
case 11: с += ((u.long) s [10] «24) ;
case 10: с += ( (u.long) s [9] «16) ;
case 9 : c += ((u.long) s [8] «8) ;
case 8 : b += ( (u.long) s [7] «24) ;
case 7 : b += ( (u.long) s [6] «16) ;
case 6 : b += ( (u.long) s [5] «8) ;
case 5 : b += (u.long)s[4];
case 4 : a += ((u.long) s [3] «24) ;
case 3 : a += ( (u.long) s [2] «16) ;
case 2 : a += ((u.long) s[l] «8) ;
case 1 : a += (u.long)s[0];
}
mix(a,b,c);
return c;
}
Практическое тестирование этой функции на примерах разнообразных текстов дает весьма хорошие результаты в смысле
равномерности выходного распределения хеш-значений.
8.3 Упражнения
8.1. При создании системы автоматизированной продажи билетов на авиарейсы требуется построить битовое множество, элементы которого характеризуют продан или нет билет на конкретные место, рейс, дату. Оцените приблизительный объем памяти, необходимый для хранения такого множества, для города с интенсивным пассажиропотоком (например, для Москвы). Для упрощения подсчетов можно считать, что дата, рейс и место фиксируются при покупке не ранее, чем за 45 дней.
8.2. Добавьте в функции битовой реализации множества защиту на случай выхода значения элемента из границ диапазона множества. Как это сделать наиболее эффективно?
8.3. Постройте битовую реализацию нескольких числовых множеств с различными диапазонами изменения значений элементов. Добавьте к этой реализации функции, выполняющие объединение, пересечение, вычитание, дополнение множеств и т.п.
8.4. Составьте программу вычисления простых чисел на основе битовой реализации множества и алгоритма решета Эратосфена. Проведите тестирование соотношения (время работы)/(количество простых чисел) при использовании различных объемов оперативной памяти для хранения множества.
8.5. Для множества слов предлагается использовать хеш-функцию, вычисляемую по формуле /(х) = 52aiX£(modp), где Xi — коды символов слова х, — некоторые весовые коэффициенты. Проверьте как рассеивает данная хеш-функция слова из достаточно большого словаря (10-20 тыс. слов) при а, = 1 и различных р. Попробуйте экспериментально подобрать коэффициенты так, чтобы рассеивание было наиболее равномерным для заданных категорий текстов (русский, английский тексты, тексты программ и т.п.).
8.6. Реализуйте хеш-множества по методу проб и методу массива списков с полным набором операций множества. Проведите тестирование времени работы различных операций на примере множества слов и хеш-функции из предыдущей задачи.
8.7. Реализуйте хеш-множества по методу проб и проведите тестирование для определения среднего количества проб при добавлении и поиске в зависимости от коэффициента заполнения массива, содержащего элементы.
9 Контейнеры
Контейнерами принято называть программные реализации, предназначенные для сохранения данных в памяти в течение некоторого периода времени. При добавлении набора данных контейнер размещает данные в памяти и возвращает указатель на место размещения. Используя этот указатель, мы можем получить доступ к значениям данных. Когда необходимость в использовании данных отпадет, их можно удалить из контейнера и тем самым освободить дополнительное место для размещения новых данных. Система предписаний контейнера выглядит очень просто.
• Создать контейнер.
• Разместить данные.
• Удалить данные.
• Очистить контейнер.
• Закончить работу.
Типичный пример контейнерной организации работы с данными представляют собой функции malloc и free в языке С или операторы new и delete в языке C++. Эти средства полностью решают поставленную задачу. Но в ряде случаев универсальность этих средств превращается в недостаток, приводящий к нерациональному использованию памяти и некоторому
увеличению времени выполнения программ. Корни подобной нерациональности растут из необходимости иметь возможность в любой момент удалить размещенные данные, получая на входе только указатель, а для этого контейнер обязан дополнительно хранить служебную информацию о длине размещенных данных. Другой, пожалуй, даже более существенной причиной является необходимость выравнивания данных в памяти. Например, архитектурные особенности многих процессоров требуют, чтобы числа типа double размещались по адресам, кратным 8, числа типа long int — по адресам, кратным 4, и т.п. Поэтому некоторые реализации функции malloc сразу выделяют память, начинающуюся с адреса, кратного 16. В результате при размещении записи длиной 17 байт мы теряем 15 байт до следующего подходящего адреса. Далее, в результате добавления и удаления данных память может оказаться фрагментированной на отдельные участки (занятые и свободные), взаимное расположение и длины которых невозможно предсказать заранее. Выбор подходящего свободного участка памяти для размещения новой порции данных с сохранением достаточного быстродействия превращается в совсем нетривиальную задачу.
Все вышесказанное относится к ситуации, когда размещаемые данные имеют непредсказуемые заранее размеры. Но если мы имеем какую-либо дополнительную информацию о данных (например, все данные имеют фиксированный размер), то процедуры размещения и удаления можно существенно упростить и ускорить, сэкономив при этом некоторую часть памяти. Именно с такой ситуацией мы сталкиваемся при реализации ссылочных структур данных (списки и деревья). Каждый такой элемент (элемент списка или вершина дерева) имеет фиксированный размер, и мы можем воспользоватся этим фактом, чтобы организовать их размещение и удаление более эффективно, чем это делали бы стандартные функции типа malloc и free. Другой пример дает ситуация, когда в процессе работы данные только накапливаются и не удаляются по отдельности, а только все сразу. В этом случае
нам не надо отслеживать фрагментацию памяти, поскольку она просто не может возникнуть. Конкретных частных ограничений подобного рода может быть великое множество, поэтому ниже мы просто рассмотрим несколько примеров, иллюстрирующих возможные подходы к реализации контейнеров.
9.1 Контейнер для элементов фиксированного размера
Рассмотрим следующую постановку задачи. Требуется организовать контейнер для элементов заданного типа Туре, причем известно ограничение на их максимальное количество. Введем объединение
typedef union _U {
Type value;
union JJ *next;
} AllocCell;
Пусть NMAX — максимальное количество элементов контейнера. Создадим массив ячеек типа AllocCell и в начале работы свяжем последовательно все ячейки в однонаправленный список с помощью указателя next. Пусть указатель AllocCell *FreeCell определяет начало этого списка. Теперь при добавлении элемента в контейнер мы исключаем ячейку из начала списка свободных и возвращаем ее адрес в качестве места для размещения. При удалении элемента соответствующая ячейка снова добавляется в начало списка свободных.
В предложенной схеме контейнера есть одно узкое место. Попытка освободить уже свободную ячейку может привести к разрушению структуры списка свободных. Устранить этот недостаток можно проверкой списка свободных ячеек на наличие в нем удаляемой ячейки. Однако такое решение будет весьма неэффективным, поскольку нам придется последовательно просматривать весь список свободных. При практической работе проверка может давать неприемлемые временные характиристики, и от нее лучше
Глава IL В^овые алгоритмы и структуры вообще отказаться. В результате, подобную схему контейнера без проверки удаления можно рекомендовать для программ, где корректность адресов удаляемых элементов обеспечивается другими средствами, например, как составную часть тщательно отлаженной Реализации списочных или древовидных структур.
Заметим, что ограничение на максимальное количество размещаемых элементов легко снять. Для этого достаточно выделить новый блок (массив ячеек) и выделять память для элементов в этом новом блоке. При этом освобождающиеся ячейки будут включаться в единый список свободных, проходящий по всем таким блокам. Для того, чтобы иметь возможность очистить целиком весь контейнер, эти блоки следует связать в единый список.
9.2 Контейнер для хранения текстовых строк
В программах, выполняющих обработку текстовых файлов, часто возникает необходимость сохранять в памяти большое количество Разнообразных текстовых строк, а указатели на эти строки передавать в структуры, обеспечивающие эффективный поиск (например, в деревья или хеш-множества). Как правило, для подобных задач не требуется удалять отдельные строки в процессе рабоТы? они удаляются только все сразу в конце работы. Обсудим идеи построение контейнера для такого рода задач.
Итак, постановка задачи сводится к следующим требованиям:
• контейнер должен обеспечивать размещение строк произвольной длины в памяти, при этом адрес размещения может быть Л1обым (выравнивание не требуется);
• строки не удаляются, допускается лишь освобождение всего контейнера в целом;
• следует обеспечить стандартный доступ ко всей строке по указателю на ее начало;
• следует по возможности снизить накладные расходы памяти.
Выделим стандартными средствами некоторый блок памяти и будем последовательно размещать строки в этом блоке вплотную друг к другу. Если для размещения очередной строки уже недостаточно места в остатке блока, то выделим новый такой же блок и разместим строку в этом новом блоке (т.е. строки не разрезаются между блоками). Все созданные блоки свяжем в однонаправленный список, чтобы обеспечить возможность освобождения всего контейнера. Если какая-либо строка настолько длинна, что не помещается в целом блоке, то специально для нее выделим отдельный блок бблыпего размера. Таким образом, реализация представляет собой список блоков, а добавление строк напоминает добавление элементов в стек.
Мы не будем приводить здесь подробную реализацию описанных идей, а ограничимся лишь описанием необходимых объектов и прототипов функций подобного контейнера.
int InitContainer (size.t block.size);
// Функция создает пустой контейнер,
// предусматривающий блоки указанного размера.
И Возвр.значение: 0 - успех, -1 - неудача, char ♦ PutString (char *src);
// Функция размещает строку src в памяти.
И Возвр.значение: указатель на место размещения, //О - отказ в размещении (нет памяти).
void ClearContainer (void);
// Функция очищает весь контейнер
Для реализации контейнера можно ввести следующие объекты.
typedef struct _CBLK { // тип - блок контейнера
char *field; // указатель на поле для строк struct .CBLK *next; И указатель на следующий блок
} ContBlock;
ContBlock *current; size.t room_left;
char *free.pos;
size.t std.size;
// указатель на текущий блок в списке И количество свободных байт в блоке // начало свободного места в блоке И стандартный размер блока
Заметим, что из всех операций со списками нам нужно лишь добавление нового блока. Поэтому нам достаточно иметь только указатель current и добавление нового блока производить по схеме
ContBlock ♦new.block;
new_block = (ContBlock*)malloc(sizeof(ContBlock)); new„block->field = (char*) malloc(std_size);
new_block->next = current; current = new„block;
(в этом примере для краткости опущены проверки выделения памяти функцией malloc). Закончить реализацию контейнера предоставляется читателю.
9.3 Идеи реализации функций типа malloc и free
Функции malloc и free предназначены для захвата и освобождения участков памяти заранее неизвестного размера. В этом смысле мы можем говорить о них как о контейнере для элементов произвольных типов. Очевидно, что реализация подобного контейнера должна сохранять необходимую информацию о размерах и размещении занятых и свободных областей памяти. В этом разделе мы рассмотрим самые простые идеи построения подобных функций. Прежде всего обсудим требования, предъявляемые к реализации.
• Исходными данными для выделения памяти является только размер области (количество байт).
• Исходными данными для освобождения захваченной ранее области является только ее адрес.
• Запросы на выделение и освобождение памяти, вообще говоря, могут поступать в произвольном порядке.
• Следует минимизировать накладные расходы и непроизводительные потери памяти.
• Следует минимизировать время работы процедур выделения и освобождения памяти.
Последние два пункта этого списка в некотором смысле противоречат друг другу. Действительно, процедуры выделения и освобождения памяти должны анализировать сложившееся распределение свободных и занятых участков памяти. Чем меньше времени они будут уделять этой работе, тем больше вероятность, что найденый свободный участок окажется не самым лучшим с точки зрения рационального использования памяти, а освобождение памяти не уменьшит фрагментацию свободных участков.
Итак, будем считать, что в нашем распоряжении есть один большой участок памяти, и мы будем нарезать из него кусочки в соответствии с запросами на выделение памяти. Поскольку освобождение памяти происходит не обязательно в порядке обратном ее захвату, то через некоторое время вся память окажется фрагментированной на занятые и свободные участки, имеющие различные размеры и сменяющие друг друга в произвольном порядке. Таким образом, для анализа фрагментации памяти нам необходимо знать адрес начала каждого такого участка и его длину в байтах. Указанную информацию можно поместить в структуру
typedef struct {
unsigned long size;
void *addr;
} AllocUnit;
Создадим два множества: в одном будем хранить данные о свободных участках памяти, во втором — о занятых. Захват памяти теперь сводится к отысканию наиболее подходящего свободного участка в множестве свободных. Найденный участок удаляется из множества свободных, от него “отрезается” нужная часть, информация о которой помещается в множество занятых,
Глава II. Базовые алгоритмы и структуры а оставшаяся свободная часть порождает новый элемент в множестве свободных. Поскольку исходными данными при захвате является размер запрашиваемой области, то именно это значение должно быть ключем поиска в множестве свободных.
Параметром процедуры освобождении памяти является адрес освобождаемой области. Таким образом, этот адрес становится ключем поиска в множестве занятых. Найденная область исключается из множества занятых и включается в множество свободных. При этом может потребоваться слияние вновь освобожденной области с соседними свободными.
Наиболее простой вариант — организовать эти два множества в виде бинарных деревьев поиска элементов типа AllocUnit. Множество свободных будет упорядочено по размеру, а множество занятых — по адресу размещения. Так как реализация дерева требует двух ссылок на потомки, то накладные расходы составят 16 байт (по 4 байта на длину, адрес и две ссылки в дереве) на каждую свободную или занятую область памяти. Накладные расходы можно еще уменьшить, если размещать данные о свободной области в самой этой области. Однако, такая реализация имеет один существенный недостаток. Дело в том, что вершины дерева свободных, соответствующие смежным областям памяти, могут оказаться в дереве далеко друг от друга. Поэтому при выполнении операции слияния смежных свободных областей нам придется обходить все дерево (напомним, что оно упорядочено по размерам областей). Для повышения эффективности операции освобождения можно выполнять слияние свободных областей только в том случае, когда операция захвата не находит свободной области требуемого размера. В качестве другого решения этой проблемы можно предложить следующее. Определим некоторый набор размеров выделяемых областей и по запросу на выделение памяти будем предоставлять наименьшую область, которая может удовлетворить требуемый запрос. Например, зададим набор размеров: 2, 4, 8, 16, 32, 48, 64, 96, 128, 192, 256 байт. Теперь при запросе на выделение 35
байт мы захватываем область в 48 байт, для запроса на 120 байт выделяем 128 байт и т.п. Для работы с областями каждого из фиксированных размеров выделим отдельный контейнер, работающий по принципам, описанным в разделе 9.1. Выделение областей, превышающих 256 байт, обслуживаем с помощью деревьев. В пользу такого способа управления памятью можно привести следующие доводы: а) как правило, объемы памяти для размещения малых объектов совпадают с указанными размерами; б) потери от несоответствия размеров запрашиваемой памяти и выделяемой области компенсируются малыми накладными расходами при реализации контейнеров для данных фиксированного размера; в) области большого размера запрашиваются реже, чем малого, поэтому деревья для описания свободных и занятых областей могут оказаться сравнительно небольшими.
В некоторых ситуациях при построении контейнерных реализаций в главу угла ставится быстродействие, достигаемое за счет упрощения алгоритма захвата памяти и вытекающих из этого возможных потерь. Одним из подобных способов может быть воплощение идеи контейнера для хранения строк. Для хранения данных выделяется некоторый блок памяти, и данные размещаются в нем последовательно. При этом достаточно хранить указатель на первый свободный адрес в незаполненной пока части блока. Одновременно ведется подсчет общего количества записей п, размещенных в указанном блоке. При удалении записи значение п уменьшается на единицу, но указатель свободной части блока не изменяется и фрагментация занятых и формально освобожденных участков не анализируется. Только когда общее количество записей, размещенных в блоке, становится равным нулю, тогда весь блок целиком считается свободным и размещение данных в нем может начаться опять с его первого байта. При таком варианте алгоритма требуется всего три операции на добавление записи (проверка достаточности места в свободной области, увеличение счетчика количества записей, сдвиг указателя свободной области). Для удаления
требуется две операции — уменьшение счетчика и проверка его на нулевое значение.
Такой грубый способ управления памятью может оказаться весьма эффективным, если в системе есть некоторый избыток свободной памяти. Действительно, память обычно запрашивается отдельными процедурами или программами, которые освобождают ее по окончании своей работы. При этом ситуация, когда большие объемы памяти одновременно запрашиваются многими программами, случается достаточно редко. Таким образом, быстродействующий алгоритм выделения/освобождения памяти способствует скорейшему завершению процедура или программы и возврату захваченной памяти с возможностью ее использования другими процедурами.
В реальных программных системах функции управления выделением и освобождением памяти могут оказаться весьма хитроумными, что связано с необходимостью найти разумный компромисс между универсальностью, быстродействием и рациональным расходованием памяти.
Литература
[1] Б.Керниган, Д. Ритчи, А. Фьюэр. Язык программирования Си. Задачи по языку Си. М.: “Финансы и статистика”, 1985.
[2] Б. Страуструп. Язык программирования C++. Киев, “Диа-Софт”, 1993.
[3] Ирэ Пол. Объектно ориентированное программирование с использованием C++. Киев, “ДиаСофт Лтд”, 1995.
[4] А. Г. Кушниренко, Г. В. Лебедев. Программирование для математиков. М., “Наука”, 1988.
[5] Н. Вирт. Алгоритмы и структуры данных. М., “Мир”, 1989.
[6] Д. Ван Тассел. Стиль, разработка, эффективность, отладка и испытание программ. М., “Мир”, 1985.
Учебное издание
Валединский Владимир Дмитриевич Пронкин Юрий Николаевич
Вычислительные системы и программирование II
М.: Издательство ЦПИ при механико-математическом факультете МГУ, 2000,-128 с.
Подписано в печать 17.03.2000 г.
Формат 60x90 1/16. Объем 8 п.л.
Заказ 7. Тираж 500 экз.
Изд-во ЦПИ при механико-математическом факультете МГУ г. Москва, Воробьевы горы.
Лицензия на издательскую деятельность ЛР № 040746, от 12.03.1996г.
Отпечатано с оригинал-макета на типографском оборудовании механико-математического факультета и Франко-русского центра им. А.М. Ляпунова.