Джулиан М. Бакнелл - Фундаментальные алгоритмы и структуры данных в Delphi

связанные с массивами. Мы посмотрим на стандартную языковую поддержку массивов, в том числе и динамических массивов, обсудим достоинства, недостатки и методику применения класса TList, а затем разработаем класс, инкапсулирующий в себе массив записей. Ввиду того, что строка, как структура данных, также представляет собой массив, мы кратко коснемся и ее.

В главе 3 вводятся понятие связного списка в двух его ипостасях: односвязный и двухсвязный списки. Мы ознакомимся с тем, как создавать стеки и очереди с использованием для их внутреннего представления как связных списков, так и массивов.

Глава 4 представляет собой введение в алгоритмы поиска, в особенности, в алгоритмы последовательного и бинарного поиска. Будет показано, как при помощи бинарного поиска осуществлять вставку элементов в сортированные массивы и связные списки.

Глава 5 посвящена алгоритмам сортировки. Мы посмотрим на различные методы сортировки: пузырьковую и шейкер-сортировку, сортировку выбором и простыми вставками, сортировку методом Шелла, быструю сортировку и сортировку слиянием. Алгоритмы сортировки будут применяться в отношении к массивам и связным спискам.

В главе 6 обсуждаются алгоритмы, которые генерируют или требуют для своего функционирования случайные числа. Будут рассмотрены различные реализации генераторов псевдослучайных чисел, а также сортированной структуры данных с возможностью пометки, именуемой списком с пропусками, в которой для поддержания сбалансированного состояния используется генератор псевдослучайных чисел.

Глава 7 вводит понятия хеширования и хеш-таблиц, включая их базовые определения, области и причины применения, а также связанные с ними достоинства и недостатки. Рассматривается множество стандартных алгоритмов хеширования. Одной из проблем, которые возникают при использовании хеш-таблиц, является так называемый конфликт, или коллизия. Мы посмотрим, как разрешать коллизии при помощи разнообразных видов зондирования и связывания.

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

Глава 9, в основном, имеет дело с очередями по приоритету. Во время обсуждения таких очередей рассматривается структура сортирующего дерева. Подробно изучаются базовые операции на сортирующем дереве, такие как пузырьковый подъем и просачивание вниз. Кроме того, анализируется новый алгоритм сортировки на сортирующем дереве - пирамидальная сортировка.

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

Глава 11 сконцентрирована вокруг нескольких технологий сжатия. Подробно рассматриваются такие алгоритмы сжатия, как Шеннона-Фано, Хаффмана, с применением скошенного дерева и LZ77.

В главу 12 включено несколько дополнительных сложных тем, которые смогут удовлетворить аппетит даже самых искушенных программистов, склонных к исследованию алгоритмов и структур данных. Глава принесет несомненную пользу также и рядовым программистам.

В самом конце книги приводится список использованной литературы, который поможет быстро найти источники, содержащие дополнительную или более подробную информацию, касающуюся рассмотренных в книге алгоритмов. Список включает, помимо прочих, и чисто академические источники.

Что это за странные конструкции $ifdef в коде?

Все коды примеров, представленных в книге, за несколькими специальным образом помеченными исключениями, будут компилироваться в средах Delphi1, 2, 3, 4, 5 и 6, а также Kylix 1. (Впрочем, должны поддерживаться и будущие версии компиляторов. Дополнительную информацию по этому поводу можно найти по адресу --">