Наследование и универсальность

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

public void Swap(ref T x1, ref T x2)

{

T temp;

temp = x1; x1 = x2; x2 = temp;

}

Если тип T – это вполне определенный тип, например int, string или Person, то никаких проблем не существует, все совершенно прозрачно. Но как быть, если возникает необходимость обмена данными разного типа? Неужели нужно писать копии этой процедуры для каждого типа? Проблема легко решается в языках, где нет контроля типов – там достаточно иметь единственный экземпляр такой процедуры, прекрасно работающий, но лишь до тех пор, пока передаются аргументы одного типа. Когда же процедуре будут переданы фактические аргументы разного типа, то немедленно возникнет ошибка периода выполнения, и это слишком дорогая плата за универсальность.

В типизированных языках, не обладающих механизмом универсализации, выхода практически нет – приходится писать многочисленные копии Swap. Read more »

Интерфейсы

Слово “интерфейс” многозначное и в разных контекстах оно имеет различный смысл. В данной лекции речь идет о понятии интерфейса, стоящем за ключевым словом interface. В таком понимании интерфейс – это частный случай класса. Интерфейс представляет собой полностью абстрактный класс, все методы которого абстрактны. От абстрактного класса интерфейс отличается некоторыми деталями в синтаксисе и поведении. Синтаксическое отличие состоит в том, что методы интерфейса объявляются без указания модификатора доступа. Отличие в поведении заключается в более жестких требованиях к потомкам. Класс, наследующий интерфейс, обязан полностью реализовать все методы интерфейса. В этом – отличие от класса, наследующего абстрактный класс, где потомок может реализовать лишь некоторые методы родительского абстрактного класса, оставаясь абстрактным классом. Но, конечно, не ради этих отличий были введены интерфейсы в язык C#. У них значительно более важная роль. Read more »

Проектирование класса Rational

В заключение этой лекции займемся проектированием класса Rational, описывающего известный в математике тип данных – рациональные числа. По ходу проектирования будут вводиться новые детали, связанные с описанием класса. Начнем проектирование, как обычно, с задания тега <summary>, описывающего назначение класса, его свойства и поведение. Вот этот текст: Read more »

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

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

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

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

Операторы языка C#

Состав операторов языка C#, их синтаксис и семантика унаследованы от языка С++. Как и положено, потомок частично дополнил состав, переопределил синтаксис и семантику отдельных операторов, постарался улучшить характеристики языка во благо программиста. Посмотрим, насколько это удалось языку C#.

Оператор присваивания

Как в языке С++, так и в C# присваивание формально считается операцией. Вместе с тем запись:

X= expr;

следует считать настоящим оператором присваивания, так же, как и одновременное присваивание со списком переменных в левой части:

X1 = X2 = … = Xk = expr;

В отличие от языка C++ появление присваивания в выражениях C# хотя и допустимо, но практически не встречается. Например, запись:

if(x = expr)…

часто используемая в С++, в языке C# в большинстве случаев будет воспринята как ошибка еще на этапе компиляции.

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