Текст книги "Фундаментальные алгоритмы и структуры данных в Delphi"
Автор книги: Джулиан Бакнелл
сообщить о нарушении
Текущая страница: 1 (всего у книги 36 страниц)
Annotation
Книга "Фундаментальные алгоритмы и структуры данных в Delphi" представляет собой уникальное учебное и справочное пособие по наиболее распространенным алгоритмам манипулирования данными, которые зарекомендовали себя как надежные и проверенные многими поколениями программистов. По данным журнала "Delphi Informant" за 2002 год, эта книга была признана сообществом разработчиков прикладных приложений на Delphi как «самая лучшая книга по практическому применению всех версий Delphi».
В книге подробно рассматриваются базовые понятия алгоритмов и основополагающие структуры данных, алгоритмы сортировки, поиска, хеширования, синтаксического разбора, сжатия данных, а также многие другие темы, тесно связанные с прикладным программированием. Изобилие тщательно проверенных примеров кода существенно ускоряет не только освоение фундаментальных алгоритмов, но также и способствует более квалифицированному подходу к повседневному программированию.
Несмотря на то что книга рассчитана в первую очередь на профессиональных разработчиков приложений на Delphi, она окажет несомненную пользу и начинающим программистам, демонстрируя им приемы и трюки, которые столь популярны у истинных «профи». Все коды примеров, упомянутые в книге, доступны для выгрузки на Web-сайте издательства.
Джулиан Бакнелл
Введение
Почему книга посвящена алгоритмам именно на Delphi?
Что я должен предварительно знать?
Какая версия Delphi мне нужна?
Что и где я могу найти в книге, или, другими словами, из чего состоит эта книга?
Что это за странные конструкции $ifdef в коде?
От изготовителя fb2.
Благодарности
Глава 1. Что такое алгоритм?
Что такое алгоритм?
Анализ алгоритмов
О-нотация
Лучший, средний и худший случаи
Алгоритмы и платформы
Виртуальная память и страничная организация памяти
Пробуксовка
Локальность ссылок
Кэш процессора
Выравнивание данных
Пространство или время
Длинные строки
Использование ключевого слова const
Осторожность в отношении автоматического преобразования типов
Тестирование и отладка
Утверждения
Комментарии
Протоколирование
Трассировка
Анализ покрытия
Тестирование модулей
Отладка
Резюме
Глава 2. Массивы.
Массивы
Типы массивов в Delphi
Стандартные массивы
Динамические массивы
Новые динамические массивы
Класс TList, массив указателей
Краткий обзор класса TList
Класс TtdObjectList
Массивы на диске
Резюме
Глава 3. Связные списки, стеки и очереди
Односвязные списки
Узлы связного списка
Создание односвязного списка
Вставка и удаление элементов в односвязном списке
Соображения по поводу эффективности
Использование начального узла
Использование диспетчера узлов
Класс односвязного списка
Двухсвязные списки
Вставка и удаление элементов в двухсвязном списке
Использование начального и конечного узлов
Использование диспетчера узлов
Класс двухсвязного списка
Достоинства и недостатки связных списков
Стеки
Стеки на основе односвязных списков
Стеки на основе массивов
Пример использования стека
Очереди
Очереди на основе односвязных списков
Очереди на основе массивов
Резюме
Глава 4. Поиск.
Процедуры сравнения
Последовательный поиск
Массивы
Связные списки
Бинарный поиск
Массивы
Связные списки
Вставка элемента в отсортированный контейнер
Резюме
Глава 5. Сортировка
Алгоритмы сортировки
Тасование массива TList
Основы сортировки
Самые медленные алгоритмы сортировки
Пузырьковая сортировка
Шейкер-сортировка
Сортировка методом выбора
Сортировка методом вставок
Быстрые алгоритмы сортировки
Сортировка методом Шелла
Сортировка методом прочесывания
Самые быстрые алгоритмы сортировки
Сортировка слиянием
Быстрая сортировка
Сортировка слиянием для связных списков
Резюме
Глава 6. Рандомизированные алгоритмы.
Генерация случайных чисел
Критерий хи-квадрат
Метод средних квадратов
Линейный конгруэнтный метод
Тестирование
Тест на однородность
Тест на пропуски
Тест "покер"
Тест "сбор купонов"
Результаты выполнения тестов
Комбинирование генераторов
Аддитивные генераторы
Тасующие генераторы
Выводы по алгоритмам генерации случайных чисел
Другие распределения случайных чисел
Списки с пропусками
Поиск в списке с пропусками
Вставка в список с пропусками
Удаление из списка с пропусками
Полная реализация класса связного списка
Резюме
Глава 7. Хеширование и хеш-таблицы
Функции хеширования
Простая функция хеширования для строк
Функции хеширования PJW
Разрешение конфликтов посредством линейного зондирования
Преимущества и недостатки линейного зондирования
Удаление элементов из хеш-таблицы с линейным зондированием
Класс хеш-таблиц с линейным зондированием
Другие схемы открытой адресации
Квадратичное зондирование
Псевдослучайное зондирование
Двойное хеширование
Разрешение конфликтов посредством связывания
Преимущества и недостатки связывания
Класс связных хеш-таблиц
Разрешение конфликтов посредством группирования
Хеш-таблицы на диске
Расширяемое хеширование
Резюме
Глава 8. Бинарные деревья.
Создание бинарного дерева
Вставка и удаление с использованием бинарного дерева
Перемещение по бинарному дереву
Обход в ширину, симметричный обход и обход в глубину
Обход по уровням
Реализация класса бинарных деревьев
Деревья бинарного поиска
Вставка в дереве бинарного поиска
Удаление из дерева бинарного поиска
Реализация класса дерева бинарного поиска
Перекомпоновка дерева бинарного поиска
Скошенные деревья
Реализация класса скошенного дерева
Красно-черные деревья
Вставка в красно-черное дерево
Удаление из красно-черного дерева
Резюме
Глава 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, и, в конечном счете, понять, что более эффективное решение задачи может обеспечить совершенно другая структура данных.
По сути, алгоритмы представляют собой своего рода кровеносные сосуды той работы, которую мы называем программированием. Начинающие программисты очень часто остерегаются иметь дело с формальными алгоритмами. Полагаю, что поначалу пугает даже само слово, правда, лишь до тех пор, пока не состоится более близкое знакомство с алгоритмами. Запомните одну важную вещь: любая программа может трактоваться как некий алгоритм, который должен получить у пользователя данные, должным образом обработать их и выдать обратно предсказуемый результат.
Стандартные алгоритмы были разработаны и обкатаны учеными в области компьютерных наук с целью использования их "рабочими лошадками", коими являемся мы с вами. Профессиональное использование базовых алгоритмов – это то, что удерживает нас на плаву как профессионалов, придает уверенности и дает нам возможность заявлять о знании того или иного языка программирования. Например, если вам хорошо известно, что такое хеш-таблицы, их достоинства и недостатки, где и почему они применяются, когда какой реализации отдавать предпочтение, то вы сможете совершенно по-другому взглянуть на рабочий проект подсистемы или приложения и найти места, где возможно получить выгоду от использования хеш-таблиц. Если алгоритмы сортировки вызывают не панику, а лишь легкую улыбку, вы понимаете глубинные основы их функционирования и знаете, кода отдавать предпочтение сортировке простыми вставками, а когда -быстрой сортировке, возможно, вы безо всяких колебаний реализуете один из алгоритмов в рамках своего приложения, а не будете бесцельно терять время на эксперименты со стандартными компонентами Delphi. (приведу лишь одну "жуткую" историю из современной программистской лирики. Некий программист использовал скрытый на форме компонент TListBox, добавлял в него набор строк, а затем устанавливал значение свойства Sorted равным true, тем самым, надеясь отсортировать эти строки.)
Полагаю, сейчас в ваших головах крутится одна мысль: "Понятно, писать книги по алгоритмам – это хорошо, но зачем при этом беспокоиться о каких-то там Delphi или Kylix?"
–
Кстати, давайте примем следующее соглашение, иначе мне придется ужасно много раз писать "Delphi или Kylix". Когда я говорю "Delphi или Kylix", в действительности я имею в виду либо Delphi, либо Kylix. В конце концов, Kylix получил известность, в основном, как система Delphi для Linux, находящаяся на этапе предварительного выпуска. Таким образом, в этой книге под "Delphi или Kylix" понимается либо Delphi для Windows, либо Kylix для Linux.
–
Итак, почему Delphi? На самом деле, на то имеются две причины: язык Object Pascal и операционная система. Язык, встроенный в среду Delphi, имеет множество конструкций, которые не доступны в других языках, конструкций, которые существенно упрощают инкапсуляцию эффективных алгоритмов и структур данных и делают ее более естественной. Примером могут послужить такие вещи, как свойства. Или, скажем, механизм исключений, генерируемых в случае возникновения непредвиденных ситуаций и ошибок. Несмотря на то что стандартные алгоритмы можно кодировать на Delphi и без применения таких специфических языковых конструкций, я довольно-таки твердо убежден, что в этом случае мы безвозвратно теряем и красоту, и эффективность реализаций, предпосылками которых является язык. Мы лишаем себя возможности исследовать все "закоулки" этого замечательного языка программирования. В этой книге мы собираемся повсеместно использовать всю мощь, присущую языку Object Pascal в среде Delphi. Я не думаю, что у программистов на Java будут возникать какие-то сложности с интерпретацией и переводом кода на свой язык. Однако раз уж я выбрал Delphi, то Delphi и буду придерживаться.
Следует принять во внимание еще одну вещь. Как традиционно предполагается, алгоритмы являются общими, по крайней мере, на одном и том же центральном процессоре и в среде одной и той же операционной системы. Конечно, алгоритмы можно оптимизировать под среду Windows или Linux. Можно добиться большей эффективности при их выполнении на семействе процессоров Pentium, в случае использования различных типов кэш-памяти или подсистем виртуальной памяти в средах разных операционных систем. Подобным возможностям оптимизации в книге уделяется отдельное внимание. Тем не менее, мы не будем доходить в своей погоне за эффективностью до кодирования на языке ассемблера, оптимизированного под конвейерную архитектуру новых процессоров, – я должен был хоть где-нибудь это сказать!
В конечном счете, в книге, посвященной алгоритмам, нуждается само сообщество разработчиков на Delphi, причем в такой, которая бы отражала этот конкретный язык программирования, используемые операционные системы и процессоры. Ну, так вот она, книга. Она не суть переписанная книга, посвященная алгоритмам с реализацией на другом языке программирования. Напротив, книга написана с нуля автором, который на протяжении всей своей практики работал с Delphi ежедневно, зарабатывает себе на жизнь тем, что пишет библиотечное программное обеспечение и немало знает о сложностях, связанных с созданием коммерческих подпрограмм, классов и инструментальных средств.
Что я должен предварительно знать?
В этой книге отнюдь не предпринимается попытка обучить кого-либо программированию на 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.
Для решения упомянутых проблем каждый файл с исходным кодом, сопровождающий данную книгу, содержит в самом начале следующее включение:
{$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 операции замены
“(^” на “”
“^)” на “”
“(_” на “”
“_)” на “”
(как вы догадываетесь, в запросе надо будет нажать кнопку «Заменить все»)
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.
