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

Дабы решить все вопросы, связанные с этими отличиями, я решил поместить в код множество конструкций $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.

Благодарности

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

С первыми двумя джентльменами, к сожалению, я никогда не разговаривал лично и не встречался, однако это те люди, которые до сих пор держат мои глаза широко открытыми и постоянно питают мой энтузиазм в безбрежном мире алгоритмов. Если бы не они, кто знает, где бы я был сейчас и чем бы занимался. Я имею в виду Дональда Кнута (Donald Knuth) (www.es.staff.stanford/edu/-knuth/) и Роберта Седжвика (Robert Sedgewick) (www.cs.princeton.edu/-rs/). В действительности, книга Седжвика, посвященная алгоритмам [20], как раз и сподвигла меня на начало моей творческой деятельности. Это была первая книга подобного рода, которую я даже решился приобрести, причем в то время я только-только вникал в программирование на Turbo Pascal. Дональд Кнут вообще не требует какого-либо представления. Его поистине великолепные труды [11, 12, 13] по-прежнему находятся на верхушке всего дерева алгоритмов; впервые я воспользовался этой книгой во время учебы в Королевском колледже Лондонского университета при получении степени бакалавра по математике.

Несколько лет спустя, следующим человеком, кому я хотел бы выразить свою благодарность, стал Ким Кокконен (Kim Kokkonen). Он предоставил мне работу в компании TurboPower Software (www.turbopower.com) и дал мне возможность настолько досконально изучить компьютерные науки, насколько я даже не мог и мечтать. Хочу поблагодарить также и всех сотрудников компании TurboPower Software, а также тех ее клиентов, которых я знал на протяжении многих лет. Благодарю Роберта Делросси (Rober DelRossi), президента TurboPower Software, за поощрение всех моих начинаний.

Следующей идет маленькая компания, к сожалению, ныне не работающая, которая называлась Natural Systems. В 1993 году эта компания выпустила продукт под названием Data Structures for Turbo Pascal (Структуры данных для Turbo Pascal). Я купил этот продукт, и, по моему мнению, это было не особенно удачное приобретение. О да, продукт работал неплохо, однако я не был согласен ни с его дизайном, ни с реализацией, кроме того, скорость функционирования оставляла желать лучшего. Именно этот продукт побудил меня написать собственную бесплатную библиотеку EZSTRUCS для Turbo Pascal 7, от которой, собственно и пошла моя хорошо известная бесплатная библиотека структур данных для Delphi.

Эти усилия были первым проблеском моего действительного понимания структур данных, поскольку зачастую понимание полностью съедается необходимостью быстрой сдачи работы.

Хочу выразить благодарность Крису Фризелду (Chris Frizell), редактору и владельцу журнала The Delphi Magazine (www.thedelphimagazine.com). Он как в воду глядел, предоставив мне возможность обсудить множество алгоритмов на страницах его поистине бесценного журнала, в конечном итоге отдав мне отдельную ежемесячную колонку Algorithms Affresco. Без его содействия и поддержки эта книга могла бы и не появиться, во всяком случае, даже если бы она и появилась, она бы уж точно была намного хуже. Я настоятельно рекомендую всем разработчикам подписаться на журнал The Delphi Magazine, поскольку, по моему мнению, он был, есть и будет наиболее глубоким, фундаментальным и серьезным периодическим изданием для широчайшего круга программистов на Delphi. Спасибо всем читателям моей колонки за их суждения и комментарии.

Под занавес, я хотел бы поблагодарить всех сотрудников издательства Wordware (www.wordware.com), в том числе моих редакторов, издателя Джима Хилла (Jim Hill) и выпускающего редактора Вес Беквис (Wes Beckwith). Джим поначалу был несколько обескуражен моим предложением издать книгу, посвященную алгоритмам, однако он очень быстро проникся моими идеями и оказывал всемерную поддержку на протяжении всего времени подготовки книги. Кроме того, я хочу выразить самые теплые благодарности научным редакторам: Стиву Тексейра (Steve Teixeira), одному их авторов Delphi X Developer's Guide, и моему другу Энтону Паррису (Anton Parris).

И, в заключение, хочу выразить благодарность и еще раз признаться в любви своей жене, Донне (вот кто был основной движущей силой, постоянно побуждающей меня к работе над книгой). Без ее любви, энтузиазма и поощрения я не смог бы прожить все эти годы. Спасибо тебе, любящее сердце. Ты знаешь, что рядом с тобой бьется второе такое же!

Джулиан М. Бакнелл Колорадо Спрингс, апрель, 1999 года - февраль 2001 года

Глава 1. Что такое алгоритм?

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

Несмотря на то что темой этой книги будут алгоритмы, структуры данных и их реализация в коде, мы рассмотрим и некоторые чисто процедурные моменты: как написать код, который позволит упростить отладку в случае возникновения проблем, как выполнять тестирование кода и как убедиться в том, что изменения, вносимые в одном месте, не вызовут ошибок в другом месте.

Что такое алгоритм?

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

Алгоритм (algorithm) представляет собой пошаговую инструкцию выполнения вычислений или процесса. Это достаточно вольное определение, но как только читатель поймет, что ему нечего бояться алгоритмов, он легко научиться их идентифицировать.