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

• Название: Фундаментальные алгоритмы и структуры данных в Delphi
• Автор: Джулиан Бакнелл
• Издательство: ДиаСофтЮП
• Жанр: Программирование
• Год: 2003
• ISBN: ISBN 5-93772-087-3

Книга "Фундаментальные алгоритмы и структуры данных в Delphi" представляет собой уникальное учебное и справочное пособие по наиболее распространенным алгоритмам манипулирования данными, которые зарекомендовали себя как надежные и проверенные многими поколениями программистов. По данным журнала "Delphi Informant" за 2002 год, эта книга была признана сообществом разработчиков прикладных приложений на Delphi как «самая лучшая книга по практическому применению всех версий Delphi».

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

Несмотря на то что книга рассчитана в первую очередь на профессиональных разработчиков приложений на Delphi, она окажет несомненную пользу и начинающим программистам, демонстрируя им приемы и трюки, которые столь популярны у истинных «профи». Все коды примеров, упомянутые в книге, доступны для выгрузки на Web-сайте издательства.

---

Что я должен предварительно знать?

В этой книге отнюдь не предпринимается попытка обучить кого-либо программированию на Delphi. Необходимо знать основы разработки приложений на Delphi: создание новых проектов, написание кода, компиляцию, отладку и так далее. Я вынужден предупредить, что в книге не используются компоненты. Вы должны четко представлять, что такое классы, процедуры и методы, а также ссылки на них, владеть механизмом нетипизированных указателей, уметь использовать тип TList и потоки, инкапсулированные в семейство TStream. Очень важно владеть основами объектно-ориентированной методологии, в частности, представлять, что такое инкапсуляция, наследование, полиморфизм и делегирование. Вас не должна пугать объектная модель, реализованная в рамках Delphi!

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

Итак, на данный момент можно с уверенностью заявить, что вы должны обладать определенным опытом программирования на Delphi. То и дело придется сталкиваться со структурами данных, лежащими в основе TList и иже с ними, посему следует четко представлять себе, какие структуры данных доступны, и как их использовать. Может статься, что вам необходимо разработать простую подпрограмму сортировки, однако все, что содержит доступный вам источник - так это написанный кем-то код на языке С++, а ни времени, ни желания переводить этот код на Delphi нету. А, может, вас интересует книга по алгоритмам, в которой вопросы увеличения производительности и эффективности описываются столь же хорошо, как и сами алгоритмы? Такая книга перед вами.

Какая версия Delphi мне нужна?

Готовы ли вы к тому, что я сейчас скажу? Любая версия. За исключением раздела, посвященного использованию динамических массивов в Delphi 4 и тех же массивов в Kylix в главе 2, части материала в главе 12 и небольших фрагментов кода тут и там, приведенный в книге код будет компилироваться и выполняться под управлением любой версии Delphi. Не считая небольших порций кода, специфических для конкретной версии, о который только что было упомянуто, я протестировал весь код, приведенный в книге, во всех версиях Delphi и Kylix.

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

Что и где я могу найти в книге, или, другими словами, из чего состоит эта книга?

Книга состоит из двенадцати глав и списка использованной литературы.

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

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

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

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

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

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

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

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

Глава 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.

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