Чтение онлайн

Обход по уровням

Реализация класса бинарных деревьев

Деревья бинарного поиска

Вставка в дереве бинарного поиска

Удаление из дерева бинарного поиска

Реализация класса дерева бинарного поиска

Перекомпоновка дерева бинарного поиска

Скошенные деревья

Реализация класса скошенного дерева

Красно-черные деревья

Вставка в красно-черное дерево

Удаление из красно-черного дерева

Резюме

Глава 9. Очереди по приоритету и пирамидальная сортировка.

Очередь по приоритету

Первая простая реализация

Вторая простая реализация

Сортирующее дерево

Вставка в сортирующее дерево

Удаление из сортирующего дерева

Реализация очереди по приоритету при помощи сортирующего дерева

Пирамидальная сортировка

Алгоритм Флойда

Завершение пирамидальной сортировки

Расширение очереди по приоритету

Восстановление свойства пирамидальное

Отыскание произвольного элемента в сортирующем дереве

Реализация расширенной очереди по приоритету

Резюме

Глава 10. Конечные автоматы и регулярные выражения.

Конечные автоматы

Использование конечного автомата: синтаксический анализ

Синтаксический анализ файлов с разделяющими запятыми

Детерминированные и недетерминированные конечные автоматы

Регулярные выражения

Использование регулярных выражений

Синтаксический анализ регулярных выражений

Компиляция регулярных выражений

Сопоставление строк с регулярными выражениями

Резюме

Глава 11. Сжатие данных.

Представление данных

Сжатие данных

Типы сжатия

Потоки битов

Сжатие с минимальной избыточностью

Кодирование Шеннона-Фано

Кодирование Хаффмана

Кодирование с использованием скошенного дерева

Сжатие с использованием словаря

Описание сжатия LZ77

Особенности кодирования литеральных символов и пар расстояние/длина

Восстановление с применением алгоритма LZ77

Сжатие LZ77

Резюме

Глава 12. Дополнительные темы.

Алгоритм считывания-записи

Алгоритм производителей-потребителей

Модель с одним производителем и одним потребителем

Модель с одним производителем и несколькими потребителями

Поиск различий между двумя файлами

Вычисление LCS двух строк

Вычисление LCS двух файлов

Резюме

Эпилог

Список литературы

Джулиан Бакнелл

Фундаментальные алгоритмы и структуры данных в Delphi

Введение

Вы взяли в руки эту книгу, она вас чем-то заинтересовала, и вы даже подумываете, не купить ли ее?.. В голове возникают мысли наподобие: "Да, наверное, стоит купить, однако прежде бы выяснить ряд вопросов..."

Почему книга посвящена алгоритмам именно на Delphi?

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

Разумеется, для описания большинства алгоритмов в подобного рода книгах не используется Delphi, Kylix или Pascal. Некоторые авторы предпочитают для описания алгоритмов пользоваться псевдокодом, некоторые - языком С, другие выбирают для этих целей язык С++, а часть авторов - вообще какой-либо суперсовременный язык. В самой знаменитой, давно и часто используемой книге, посвященной алгоритмам, для иллюстрации самих алгоритмов выбран язык ассемблера, которого вообще не существует (язык ассемблера MIX в книге "Искусство программирования для ЭВМ" Дональда Кнута [11, 12, 13]). Действительно, в книгах, содержащих в своих названиях слово "практический", для иллюстрации реализации алгоритмов используются языки С, С++ и Java. Является ли это большой проблемой? В конце концов, алгоритм - это алгоритм, стало быть, какая разница, на чем демонстрировать его работу? И зачем, собственно, покупать книгу, посвященную алгоритмам с иллюстрациями на Delphi?

Я утверждаю, что на сегодняшний день Delphi представляет собой уникальную систему из числа языков и сред, используемых для разработки приложений. Во-первых, подобно Visual Basic, Delphi является средой для быстрой разработки приложений для 16- и 32-разрядных операционных систем Windows, а также, в случае Kylix, для Linux. Умело пользуясь мышью, компоненты можно швырять на форму также просто, как пшеницу на молодоженов. Еще немного щелчков мышью и чуть-чуть кодирования - и, пожалуйста!
– компоненты связаны между собой сложным и непротиворечивым образом, снабжены обработчиками событий, и все вместе, образуют ни что иное, как завершенное бизнес-приложение.

Во-вторых, подобно С++, Delphi дает возможность близко подобраться к сердцу операционной системы через множество API-интерфейсов. В ряде случаев доступ к API-интерфейсам предоставляет компания Borland (Inprise) в рамках среды Delphi, в других ситуациях разработчики переносят заголовочные файлы на С в среду Delphi (в рамках проекта Jedi (Джедай) на Web-сайте www.delphi-jedi.org). Так или иначе, но Delphi благополучно делает эту работу и манипулирует функциями операционной системы по собственному усмотрению.

Программисты на Delphi условно делятся на два "лагеря" - программисты прикладных приложений и так называемые системные программисты. Иногда можно встретить и уникальных представителей, которые делают обе работы. Тем не менее, есть у представителей обеих "лагерей" одна общая черта - они должны хорошо разбираться в глубинной сути мира алгоритмов. Какой бы длинной или короткой была ваша программистская практика, рано или поздно, вы дойдете до момента, когда крайне необходимо самостоятельно закодировать, скажем, бинарный поиск. И, конечно же, перед тем как приступить к решению упомянутой проблемы, потребуется решить задачу, связанную с разработкой процедуры сортировки определенного вида данных, дабы бинарный поиск смог корректно функционировать. Иногда при помощи профилировщика удается идентифицировать узкое место в TStringList, и, в конечном счете, понять, что более эффективное решение задачи может обеспечить совершенно другая структура данных.

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