Как обычно, для демонстрации примеров данной главы построено Решение с именем главы Ch7. В Решение включены три проекта. Проект DLL с именем SearchAndSorting содержит два сервисных класса Service<T> и SortService<T>, методы которых реализуют алгоритмы поиска по образцу и сортировки массивов. Проект Windows с именем SearchAndSort имеет традиционную архитектуру с главной кнопочной формой. Два интерфейсных класса FormSearch и FormSorting обеспечивают интерфейс пользователя, позволяющий анализировать методы поиска и сортировки из DLL, подключенной к проекту. Консольный проект SymbolsAndStrings содержит класс Testing, большое число методов которого представляют собой различные тесты, иллюстрирующие работу со строками и символами. К этому проекту также подключена DLL, так что часть тестов позволяет работать с методами поиска и сортировки в консольном варианте.
Эта глава завершает вводную часть курса, изложение начал программирования. Поэтому в разделе алгоритмы и задачи основное внимание уделено методам поиска и сортировки, представляющим необходимую начальную часть образования программиста.
Классы построенной DLL являются универсальными классами с параметрами. Такие классы будут подробно рассматриваться в последующих главах курса. Возможно, не совсем корректно по отношению к читателю использовать в примерах еще не описанный инструментарий. Но, выбирая между методичностью изложения и примерами, с самого начала демонстрирующими возможности языка и стиль программирования, я склоняюсь в пользу примеров.
Вначале было слово.
Так говорит история человечества. В истории компьютеров вначале было число. Долгое время вместо термина "компьютер" использовались аббревиатуры "ЭВМ" (Электронная Вычислительная Машина) и "ЦВМ" (Цифровая Вычислительная Машина), что подчеркивало цифровую сущность первых компьютеров. И использовались они тогда в отраслях, связанных с военными применениями, в зарождающейся космической отрасли, в физике - в тех областях, где господствовала цифра. Тогда в почете были физики, а не лирики с их, казалось бы, ненужными текстами.
В первых языках программирования - Фортране и Алголе практически отсутствовали средства представления текстовой информации и работы с ней. В сборнике упражнений по Алголу, подготовленном на факультете ВМК МГУ и вышедшем в 1975 году, нет ни одного упражнения по работе с текстовой информацией, все упражнения предназначены для работы с числами. Приведу еще цитату из книги, вышедшей в 1980 году и посвященной обзору расплодившихся тогда языков программирования: "Можно сказать, что для "научных" языков программирования характерно полное или почти полное отсутствие средств для работы со строками литер".
Однако время господства цифры прошло, и ей пришлось уступить символу, занявшему законное первое место в компьютерных программах. Первые задачи по обработке текстов были связаны с потребностями самого программирования. Появление алгоритмических языков стимулировало развитие теории трансляции - теоретической и практической дисциплине, занимающейся переводом текстов с одного языка на другой. Для формальных языков, каковыми являются языки программирования, задача перевода успешно решена. Для естественных языков, несмотря на некоторые успехи, впечатляющих результатов пока не получено.
Широкое применение компьютеров не только в инженерных дисциплинах, но и в бизнесе, также способствовало развитию работы с текстовыми документами.
Появление персональных компьютеров в каждом доме, а затем и появление компьютерных сетей, создало новую реальность - информационный мир. Ежедневно миллионы людей создают новые тексты, размещая их в Интернете - этом громадном хранилище текстов. Денно и нощно поисковые машины перелопачивают эту груду, индексируя их, наводя хоть какой-то порядок, позволяющий по запросу найти нужный текст. Без людей, создающих тексты, и без компьютеров, обрабатывающих эти тексты, Интернет как хранилище информации был бы бесполезным.
Здесь есть еще одна невидимая сторона дела - алгоритмическая сложность задач, решаемых в процессе поиска. Пользователям Интернета, далеким от понимания алгоритмов, может казаться совершенно естественным, что на их запрос уже через секунды выдается большое число ссылок на тексты с запрашиваемой информацией. Пользователи могут жаловаться, что ссылок слишком много, не все из них действительно соответствуют запросу, но в целом система работает удовлетворительно. У специалиста, представляющего, какие объемы текстов следует просмотреть для получения ответов, работоспособность системы должна вызывать изумление и уважение. Примитивные алгоритмы работы с текстами не смогли бы привести к успеху поиска.
Интернет - далеко не единственная область, где подобные алгоритмы играют важнейшую роль. Молекулярная биология (и ее раздел - биоинформатика) является сегодня бурно развивающейся научной областью. Как ни странно (а, может быть, вполне естественно), при анализе структур ДНК и РНК, при расшифровке генома человека работа с текстами играет определяющую роль. В книге Дэна Гансфилда "Строки" подробно рассматриваются алгоритмы работы с текстами как необходимый инструментарий решения задач вычислительной биологии. Приведу из нее некоторые цитаты, поясняющие, как биологическая информация представляется в виде текста: "Можно получить биологически осмысленные результаты, рассматривая ДНК как одномерную строку символов". Аналогичное, но более сильное предположение делается и о белках. Информация, которая лежит за биохимией, клеточной биологией, может быть представлена обычной строкой, составленной из 4-х символов G, А, Т и С. Для биологии организмов эта строка является исходной структурой данных.
Для работы с текстами на языке C# библиотека классов FCL предлагает целый набор разнообразных классов, сосредоточенных в разных пространствах имен этой библиотеки. Классы для работы с текстами находятся как в основном пространстве имен System, так и в пространствах System.Text и System.Text.RegularExpression.
Классы C#, используемые для представления строк, - char, сhar[], string, StringBuilder - связаны между собой, и из объекта одного класса нетрудно получить объект другого класса. Конструктору класса string можно передать массив символов, создав, тем самым, объект класса string. Для обратного преобразования из string в char[] следует вызвать метод ToCharArray, которым обладают объекты класса string. Достаточно вызвать метод ToString объекта StringBuilder для преобразования объекта класса StringBuilder в объект класса string. Обратное преобразование можно выполнить, передавая конструктору класса StringBuilder объект string.
