спектром случаев применения. Подробно рассматриваются вопросы построения и поддержки бинарных деревьев, а также методы прохода по узлам дерева. Затрагиваются вопросы несбалансированных деревьев, образующихся в результате вставки данных в сортированном порядке. В главе приводится набор алгоритмов балансировки, среди которых скошенное дерево и красно-черное дерево.
Глава 9, в основном, имеет дело с очередями по приоритету. Во время обсуждения таких очередей рассматривается структура сортирующего дерева. Подробно изучаются базовые операции на сортирующем дереве, такие как пузырьковый подъем и просачивание вниз. Кроме того, анализируется новый алгоритм сортировки на сортирующем дереве - пирамидальная сортировка.
В главе 10 можно найти исчерпывающую информацию о конечных автоматах и об их применения для решения определенного класса задач. После рассмотрения некоторых стандартных примеров использования детерминированных конечных автоматов приводятся глубокие исследования регулярных выражений, а также алгоритмы их синтаксического анализа и компиляции в недетерминированные конечные автоматы. В конце главы приводятся примеры применения конечных автоматов для ввода или отклонения строк.
Глава 11 сконцентрирована вокруг нескольких технологий сжатия. Подробно рассматриваются такие алгоритмы сжатия, как Шеннона-Фано, Хаффмана, с применением скошенного дерева и LZ77.
В главу 12 включено несколько дополнительных сложных тем, которые смогут удовлетворить аппетит даже самых искушенных программистов, склонных к исследованию алгоритмов и структур данных. Глава принесет несомненную пользу также и рядовым программистам.
В самом конце книги приводится список использованной литературы, который поможет быстро найти источники, содержащие дополнительную или более подробную информацию, касающуюся рассмотренных в книге алгоритмов. Список включает, помимо прочих, и чисто академические источники.
Что это за странные конструкции $ifdef в коде?
Все коды примеров, представленных в книге, за несколькими специальным образом помеченными исключениями, будут компилироваться в средах Delphi1, 2, 3, 4, 5 и 6, а также Kylix 1. (Впрочем, должны поддерживаться и будущие версии компиляторов. Дополнительную информацию по этому поводу можно найти по адресу http://www.boyet.com/dads.) Несмотря на приложенные мною усилия, некоторые отличия в коде для различных версий Delphi и Kylix все же имеют место.
Дабы решить все вопросы, связанные с этими отличиями, я решил поместить в код множество конструкций $IFDEF, которые обеспечивают условную компиляцию отдельных фрагментов кода. Компания Borland (Inprise) предлагает набор определений для официальных платформ WINDOWS, WIN32 и LINUX, а также набор определений для версий компиляторов VERnnn.
Для решения упомянутых проблем каждый файл с исходным кодом, сопровождающий данную книгу, содержит в самом начале следующее включение:
{$1 TDDefine.inc}
В этом включаемом файле находятся читабельные определения компилятора для различных версий:
DelphiN определение для конкретной версии Delphi, N = 1, 2, 3, 4, 5, 6
DelphiNPlus определение для конкретной или более поздней версии Delphi, N = 1, 2, 3, 4, 5, 6 KylixN определение для конкретной версии Kylix, N = 1
KylixNPlus определение для конкретной или более поздней версии Kylix, N = 1
HasAssert определение, поддерживает ли компилятор Assert
Кроме того, я предполагаю, что каждый компилятор, за исключением Delphi1, поддерживает длинные строки.
Типографские соглашения
Основной текст книги, то есть обсуждения, описания, постановки задач, представлен этим шрифтом.
Коды всех листингов напечатаны моноширинным шрифтом.
Базовые понятия, термины и ключевые фразы выделены курсивом.
-----------------------
Во многих местах книги можно встретить примечания наподобие этого. Примечания служат для того, чтобы подчеркнуть нечто очень важное, а также предупредить о тех или иных особенностях или предостеречь о подводных камнях.
-----------------------
От изготовителя fb2.
I. Вначале, протестируем вашу читалку.
C2H5OH, E=mc2
Если предыдущую строку вы видите в таком виде:
C2H5OH, E=mc2
Значит, ваша читалка не поддерживает надстрочные и подстрочные символы (к сожалению, [пока] это бывает очень часто).
Для такого случая, в данном файле, я применяю следующие соглашения:
Пример надстрочных символов:
Теорема Ферма x(^n^) + y(^n^) = z(^n^)
Пример подстрочного символа:
Формула воды H(_2_)O
Согласен, непривычно, неудобно, некрасиво…, но я выбрал такое оформление для удобства «везунчиков» у которых, читалка показывает все правильно.
Легким движением вы превратите книгу в удобНОваримую.
Порядок действий (алгоритм):
1. Распаковать данный файл(если это архив).
2. Открыть файл подходящим текстовым редактором (не сочтите за рекламу, я пользуюсь Notepad++)
3. Произведите 4 операции замены
“(^” на “<sup>”
“^)” на “</sup>”
“(_” на “<sub>”
“_)” на “</sub>”
(как вы догадываетесь, в запросе надо будет нажать кнопку «Заменить все»)
4. Сохраните файл, если хочется, сожмите в архив. И будет вам счастье.
Ну, а нам, всем остальным, придется мучаться с тем, что есть…
II. Еще одно огорчение:
примеры кода в книге приведены без отступов. Т.е. примеры читаются очень плохо. Виноват в этом формат fb2, не отрабатываются отступы (или я чего-то не знаю :( ).
Но тут решение есть. Скачайте исходники по адресу http://boyet.com/Code/ToDADS_source.zip
Вот и все.
Успехов w_cat.
