Класс String

В предыдущей лекции мы говорили о символьном типе char и строках постоянной длины, задаваемых массивом символов. Основным типом при работе со строками является тип string, задающий строки переменной длины. Класс String в языке C# относится к ссылочным типам. Над строками – объектами этого класса – определен широкий набор операций, соответствующий современному представлению о том, как должен быть устроен строковый тип.

Объявление строк. Конструкторы класса string

Объекты класса String объявляются как все прочие объекты простых типов – с явной или отложенной инициализацией, с явным или неявным вызовом конструктора класса. Чаще всего, при объявлении строковой переменной конструктор явно не вызывается, а инициализация задается строковой константой. Но у класса Sring достаточно много конструкторов. Они позволяют сконструировать строку из:

• символа, повторенного заданное число раз;
• массива символов char[];
• части массива символов.

Некоторым конструкторам в качестве параметра инициализации можно передать строку, заданную типом char*. Но все это небезопасно, и подобные примеры приводиться и обсуждаться не будут. Приведу примеры объявления строк с вызовом разных конструкторов: Read more »

Класс Object и массивы

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

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

Быстрая сортировка Хоара

Продолжая тему рекурсии, познакомимся с реализацией на C# еще одного известного рекурсивного алгоритма, применяемого при сортировке массивов. Описанный ранее рекурсивный алгоритм сортировки слиянием имеет один существенный недостаток – для слияния двух упорядоченных массивов за линейное время необходима дополнительная память. Разработанный Ч. Хоаром метод сортировки, получивший название быстрого метода сортировки – QuickSort, не требует дополнительной памяти. Хотя этот метод и не является самым быстрым во всех случаях, но на практике он обеспечивает хорошие результаты. Нужно отметить, что именно этот метод сортировки встроен в класс System.Array.

Идея алгоритма быстрой сортировки состоит в том, чтобы выбрать в исходном массиве некоторый элемент M, затем в начальной части массива собрать все элементы, меньшие M. Так появляются две подзадачи размерности – k и n-k, к которым рекурсивно применяется алгоритм. Если в качестве элемента M выбирать медиану сортируемой части массива, то обе подзадачи имели бы одинаковый размер и алгоритм быстрой сортировки был бы оптимальным по времени работы. Но расчет медианы требует своих затрат времени и усложняет алгоритм. Поэтому обычно элемент M выбирается случайным образом. В этом случае быстрая сортировка оптимальна лишь в среднем, а для плохих вариантов (когда в качестве M всякий раз выбирается минимальный элемент) имеет порядок n2.

Несмотря на простоту идеи, алгоритм сложен в своей реализации, поскольку весь построен на циклах и операторах выбора. Я проводил построение алгоритма параллельно с обоснованием его корректности, введя инварианты соответствующих циклов. Текст обоснования встроен в текст метода. Приведу его, а затем дам некоторые объяснения. Вначале, как обычно, приведу нерекурсивную процедуру, вызывающую рекурсивный метод: Read more »